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

《数据结构单链表实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构单链表实验报告.docx（11页珍藏版）》请在第壹文秘上搜索。

1、1 .实验题目：将单链表按基准划分。2 .实验项目目的：掌握单链表的应用和算法设计。3 .实验项目的程序结构(程序中的函数调用关系图):IJL4 .实验项目包含的各个文件中的函数的功能描述：SPlit(LinkList*&L,EIemTyPex):将单链表中所有数据结点按X进行划分。5 .算法描述或流程图：开始；初始化单链表L；创建单链表LXcbdehgf输出单链表L；以d进行划分；输出单链表L；销毁单链表L5初始化单链表F；创建单链表Facbedhgf;输出单链表F；以d进行划分；输出单链表F；销毁单链表F；结束；6 .实验数据和实验结果分析：实验数据：acbdehgf;acbedhgfL:

2、bcadehgfFlacbedhgf以d进行划分F：bcaedhgfProcessexitedafter0.1457secondswithreturnvalue0请按任意键继续.结果分析：由于使用对大于d的数据使用尾插法建表，若比d大的数据在d的前面，划分后仍会在d的前面，该函数只能划分没有这种情况的链表。7 .实验体会：应用单链表数据时，需要透彻理解指针的用法，不然很容易出错。8 .程序清单：#include#includetypedefcharEIemType;typedefstructLNOde定义单链表结点类型EIemTypedata;structLNode*net;LinkList;

3、voidCreateListF(LinkList*&L,ElrmTyPeazintn)头插法建表(LinkList*s;L=(LinkList*)malloc(sizeof(LinkList);L-next=NULL;for(inti=O;idata=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;idata=ai;r-next=s;r=s;r-nex

4、t=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;i

5、nti=0;while(p-net!=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(jnext;)if(P=NULL)不存在第i个数据节点,返回0returnfalse;else存在第i个数据

6、节点,返回1e=p-data;returntrue;intLocateElem(LinkList*L,日emTypee)按元素值查找inti=l;LinkList*p=L-net;/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;LinkL

7、ist*p=Lz*s;/p指向头节点,j置为0(即头节点的序号为0)while(jnext;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

8、置为。(即头节点的序号为0)while(jnext;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-net;从单链表中删除*q节点free(q);释放*q节点returntrue;返回true表示成功删除第i个节点)voidSplit(LinkList*&L,EIemTyPex)(LinkList*p=L-nextz*q,*r;L-next=NULL;初始化L为空链表r=L;/r是新链表的

9、尾结点指针while(p!=NULL)(if(p-datanext;p-next=L-net;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;