数据结构单链表实验报告.docx

1 .实验题目：将单链表按基准划分。2 .实验项目目的：掌握单链表的应用和算法设计。3 .实验项目的程序结构(程序中的函数调用关系图):IJL4 .实验项目包含的各个文件中的函数的功能描述：SPlit(LinkList*&L,EIemTyPex):将单链表中所有数据结点按X进行划分。5 .算法描述或流程图：开始；初始化单链表L；创建单链表LXcbdehgf'输出单链表L；以d进行划分；输出单链表L；销毁单链表L5初始化单链表F；创建单链表F"acbedhgf"输出单链表F；以d进行划分；输出单链表F；销毁单链表F；结束；6 .实验数据和实验结果分析：实验数据：acbdehgf;acbedhgfL:bcadehgfFlacbedhgf以d进行划分F：bcaedhgfProcessexitedafter0.1457secondswithreturnvalue0请按任意键继续.结果分析：由于使用对大于d的数据使用尾插法建表，若比d大的数据在d的前面，划分后仍会在d的前面，该函数只能划分没有这种情况的链表。7 .实验体会：应用单链表数据时，需要透彻理解指针的用法，不然很容易出错。8 .程序清单：#include<stdio.h>#include<malloc.h>typedefcharEIemType;typedefstructLNOde定义单链表结点类型EIemTypedata;structLNode*ne×t;LinkList;voidCreateListF(LinkList*&L,ElrmTyPeazintn)头插法建表(LinkList*s;L=(LinkList*)malloc(sizeof(LinkList);L->next=NULL;for(inti=O;i<n;i+)(s=(LinkList*)malloc(sizeof(LinkList);s->data=ai;s->next=L->next;L->next=s;)voidCreateListR(LinkList*&L,日emTypeazintn)(LinkList*s,*r;L=(UnkList*)malloc(sizeof(LinkList);L->next=NULL;r=L;for(inti=0;i<n;i+)(s=(LinkList*)malloc(sizeof(LinkList);s->data=ai;r->next=s;r=s;r->next=NULL;)voidlnitList(LinkList*&L)初始化线性表(L=(LinkList*)malloc(sizeof(LinkList);创建头结点L->next=NULL;)voidDestroyList(LinkList*&L)销毁线性表(LinkList*p=L,*q=p->next;while(q!=NULL)(free(p);p=q;q=p->next;free(p);)boolListEmpty(LinkList*L)判线性表是否为空表(return(L->next=NULL);)intListLength(LinkList*L)求线性表的长度(LinkList*p=L;inti=0;while(p->ne×t!=NULL)(i+；p=p->next;)return；)voidDiSPLiSt(LinkLiSt*L)输出线性表(LinkList*p=L->next;while(p!=NULL)printf("%c",p->data);p=p->next;printf("n");)boolGetElem(LinkList*L,intizElemType&e)求线性表中某个数据元素值(intj=0;LinkList*p=L;/p指向头节点J置为0(即头节点的序号为0)while(j<i&&p!=NLL)找第i个节点j+；p=p->next;)if(P=NULL)不存在第i个数据节点,返回0returnfalse;else存在第i个数据节点,返回1e=p->data;returntrue;intLocateElem(LinkList*L,日emTypee)按元素值查找inti=l;LinkList*p=L->ne×t;/p指向开始节点,i置为1(即开始节点的序号为1)while(p!=NULL&&p->data!=e)查找data值为e的节点,其序号为ip=p->next;i+;)if(P=NULL)不存在元素值为e的节点,返回0return(0);else存在元素值为e的节点,返回其逻辑序号ireturn(i);)boolListlnsert(LinkList*&L,inti,ElemTypee)插入数据元素(intj=0;LinkList*p=Lz*s;/p指向头节点,j置为0(即头节点的序号为0)while(j<i-l&&p!=NULL)查找第i-1个节点j+；p=p->next;if(P=NULL)未找到第il个节点,返回falsereturnfalse;else找到第i-1个节点*p,插入新节点并返回1s=(LinkList*)malloc(sizeof(LinkList);s->data=e;创建新节点*s,其data域置为es->next=p->next;将*s插入到*p之后p->next=s;returntrue;)boolListDelete(LinkList*&L,inti,EIemType&e)删除数据元素(intj=0;LinkList*p=L,*q;/p指向头节点,j置为。(即头节点的序号为0)while(j<i-l&&p!=NULL)查找第i-1个节点j+；p=p->next;if(P=NULL)未找到第i-1个节点,返回falsereturnfalse;else找到第i-1个节点*pq=p->next;q指向第i个节点if(q=NLL)若不存在第i个节点,返回falsereturnfalse;e=q->data;p->next=q->ne×t;从单链表中删除*q节点free(q);释放*q节点returntrue;返回true表示成功删除第i个节点)voidSplit(LinkList*&L,EIemTyPex)(LinkList*p=L->nextz*q,*r;L->next=NULL;初始化L为空链表r=L;/r是新链表的尾结点指针while(p!=NULL)(if(p->data<x)若p结点值小于x,使用头插法插入到开头(q=p->next;p->next=L->ne×t;L->next=p;if(p->next=NULL)(r=P；)p=q;else(r->next=p;r=p;p=p->next;)r->next=NULL;)intmain()LinkList*L;EIemTypea="acbdehgf"intn=8;CreateListR(Lza,n);printf("L:");DispList(L);EIemTypex=,d'Printf("以c进行划分n,1,x);Spit(L,x);printf("L:");DispList(L);DestroyList(L);LinkList*F;EIemTypeb="acbedhgf,;CreateListR(F,b,n);printf("F:");DispList(L);EIemTypey='d,;Printf("以c进行划分n,1,y);Spit(F,y);Printf(E)DispList(F);DestroyList(F);return0;