《数据结构单链表实验报告》由会员分享，可在线阅读，更多相关《数据结构单链表实验报告（14页珍藏版）》请在金锄头文库上搜索。
1、ddmap+oi SMopu!M :碧:丑叩丁ms :甄目44倒Z9Z0E0T6T :含素邮痢善：莎我906T :含珞吊徘魏活耕解1 .实验题目：将单链表按基准划分。2.实验项目目的：掌握单链表的应用和算法设计。3 .实验项目的程序结构(程序中的函数调用关系图):4.实验项目包含的各个文件中的函数的功能描述：Split(LinkList *&L,ElemType x):将单链表中所有数据结点按x进行划分。5 .算法描述或流程图：开始；初始化单链表L；创建单链表Lacbdehgf；输出单链表L；以d进行划分；输出单链表L；销毁单链表L；初始化单链表F；创建单链表Facbedhgf；输出单链表F；
2、 以d进行划分；输出单链表F；销毁单链表F； 结束；6 .实验数据和实验结果分析: 实验数据：acbdehgf; acbedhgfL:a c b d e h g f 破行划分L:b c a d e h g fF: a c b e d h g f 侦破行划分 Flbcaedhgf实验结果:Process esited after 0. 1457 seconds with return value 0 青按任意键继续一.结果分析：由于使用对大于d的数据使用尾插法建表，若比d大的 数据在d的前面，划分后仍会在d的前面，该函数只能划分没有这种 情况的链表。7 .实验体会：应用单链表数据时，需要透彻理解
3、指针的用法，不然很容易出错。8.程序清单： #include #include typedef char ElemType;typedef struct LNode/定义单链表结点类型ElemType data;struct LNode *next; LinkList;void CreateListF(LinkList *&L,ElemType a,int n)/头插法建表LinkList *s;L=(LinkList*)malloc(sizeof(LinkList);L-next=NULL;for(int i=0;idata=ai;s-next=L-next;L-next=s;void Cr
4、eateListR(LinkList *&L,ElemType a,int n)LinkList *s,*r;L=(LinkList*)malloc(sizeof(LinkList);L-next=NULL;r=L;for(int i=0;idata=ai;r-next=s;r=s;r-next=NULL;void InitList(LinkList *&L)初始化线性表L=(LinkList *)malloc(sizeof(LinkList);创建头结点L-next=NULL;void DestroyList(LinkList *&L)销毁线性表LinkList *p=L,*q=p-next
5、;while (q!=NULL)free(p);p=q;q=p-next;free(p);bool ListEmpty(LinkList *L) 判线性表是否为空表return(L-next=NULL);int ListLength(LinkList *L)求线性表的长度LinkList *p=L;int i=0;while (p-next!=NULL)i+;p=p-next;return(i);void DispList(LinkList *L) 输出线性表LinkList *p=L-next;printf(%c ,p-data);p=p-next;printf(n);bool GetEle
6、m(LinkList *L,int i,ElemType &e)/ 求线性表中某个数据元素值int j=0;LinkList *p=L;/p指向头节点,j置为0(即头节点的序号为0)while (jnext;if (p=NULL)不存在第i个数据节点，返回0return false;else存在第i个数据节点，返回1 e=p-data;return true;int LocateElem(LinkList *L,ElemType e) 按元素值查找 int i=1;LinkList *p=L-next; /p指向开始节点,i置为1(即开始节点的序号为1)while (p!=NULL & p-d
7、ata!=e) /查找 data 值为 e 的节点，其序号 为i p=p-next;i+;if (p=NULL)不存在元素值为e的节点，返回0return(0);else存在元素值为e的节点，返回其逻辑序号ireturn(i);bool ListInsert(LinkList *&L,int i,ElemType e) 插入数据元素int j=0;LinkList *p=L,*s;/p指向头节点,j置为0(即头节点的序号为0)while (jnext;if (p=NULL)未找到第i-1个节点，返回falsereturn false;else找到第i-1个节点*p,插入新节点并返回1 s=(L
8、inkList *)malloc(sizeof(LinkList);s-data=e;创建新节点*s,其data域置为es-next=p-next; 将*s 插入到*?之后p-next=s;return true;bool ListDelete(LinkList *&L,int i,ElemType &e) /删除数据元素int j=0;LinkList *p=L,*q;/p指向头节点,j置为0(即头节点的序号为0)while (jnext;if (p=NULL)未找到第i-1个节点，返回falsereturn false;else找到第i-1个节点*pq=p-next;/q指向第i个节点if
9、 (q=NULL)若不存在第i个节点，返回falsereturn false;e=q-data;p-next=q-next;/从单链表中删除*4节点free(q);释放*4节点return true;/返回true表示成功删除第i个节点void Split(LinkList *&L,ElemType x)LinkList *p=L-next, *q, *r;L-next=NULL;/初始化L为空链表r=L;/r是新链表的尾结点指针while(p!=NULL)if(p-datanext;p-next=L-next;L-next=p;if (p-next=NULL)r=p;p=q;elser-ne
10、xt=p;r=p；p=p-next;r-next=NULL;int main() LinkList *L;ElemType a=acbdehgf;int n=8;CreateListR(L,a,n);printf(L:);DispList(L);ElemType x=d;printf(以知进行划分n,x);Split(L,x);printf(L:);DispList(L);DestroyList(L);LinkList *F;ElemType b=acbedhgf;CreateListR(F,b,n);printf(F:);DispList(L);ElemType y=d;printf(以知进行划分n,y);Split(F,y);printf(F:);DispList(F);DestroyList(F);return 0;
