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

《数据结构单链表实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构单链表实验报告.docx（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告班号：1906姓名：吴晓坤学号：191030257设计日期：5.14上机环境：Windows 10+ devcppreturn false;elseelse找到第i-1个节点*p q=p-next;q指向第i个节点if (q=NULL)假设不存在第i个节点，返回falsereturn false;e=q-data;p-next=q-next;从单链表中删除*q节点free(q);释放*q节点return true;返回true表示成功删除第i个节点)void Split(LinkList *&L,ElemType x)(LinkList *p=L-next, *q, *r;L-

2、next=NULL;初始化L为空链表r=L; 是新链表的尾结点指针while(p!=NULL)(if(p-datanext;p-next=L-next;L-next=p;if (p-next=NULL)(r=P；p=q;else(r-next=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(以c 进行划分n”,x);Split(L,x);printf(L:n)

3、;DispList(L);DestroyList(L);LinkList *F;ElemType b=acbedhgf;CreateListR(F,b,n);printf(F:);DispList(L);ElemType y=d;printf(以 c 进行划分n”,y);Split(F,y);printf(F:);DispList(F);DestroyList(F);return 0;1 .实验题目：将单链表按基准划分。2 .实验工程目的：掌握单链表的应用和算法设计。3 .实验工程的程序结构(程序中的函数调用关系图):.实验工程包含的各个文件中的函数的功能描述：Split(LinkList *

4、&L/ElemType x):将单链表中所有数据结点按x进行划分。4 .算法描述或流程图：开始；初始化单链表L；创立单链表Lacbdehgf；输出单链表L；以d进行划分；输出单链表L；销毁单链表L；初始化单链表F；创立单链表Facbedhgf；输出单链表F；以d进行划分；输出单链表F；销毁单链表F；结束；5 .实验数据和实验结果分析：实验数据：acbdehgf; acbedhgfL：a c b d e h g f 以d进行划分L：b c a d e h g fF:a c b e d h g f 以d进行划分F：bcaedhgfProcess exited after 0. 1457 secon

5、ds with return value 0 请按任意键继续. 结果分析：由于使用对大于d的数据使用尾插法建表，假设比d大的 数据在d的前面，划分后仍会在d的前面，该函数只能划分没有这种 情况的链表。6 .实验体会：应用单链表数据时，需要透彻理解指针的用法，不然 很容易出错。7 .程序清单：#include #include typedef char ElemType;typedef struct LNode定义单链表结点类型ElemType data;struct LNode *next; LinkList;void CreateListF(LinkList *&L,日emType a,in

6、t n)头插法建表 (LinkList *s;L=(LinkUst*)malloc(sizeof(LinkList);L-next=NULL;for(int i=0;idata=ai;s-next=L-next;L-next=s;)void CreateListR(LinkList *&L,ElemType aJnt n)(LinkList *s,*r;L=(LinkList*)malloc(sizeof(LinkList);L-next=NULL;r=Lfor(int i=O;idata=ai;r-next=s;r=s;)r-next=NULL;)void lnitList(LinkList

7、 *&L)初始化线性表(L=(LinkList *)malloc(sizeof(LinkList);创立头结点L-next=NULL;)void DestroyList(LinkList *&L) 销毁线性表(LinkList *p=L,*q=p-next;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!

8、=NULL)i+;p=p-next;return(i);void DispList(LinkList *L) 输出线性表LinkList *p=L-next;while (p!=NULL)printf(%c ,p-data);p=p-next;)printf(n);)bool GetElem(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个数据节点，

9、返回1 e=p-data;return true;int LocateElem(LinkList *L,ElemType e) 按元素值查找 int i=l;LinkList *p=L-next; /p指向开始节点,i置为1(即开始节点的 序号为1)while (p!=NULL & p-data!=e) 查找 data 值为 e 的节点，其序号 为i p=p-next;i+；)if (p=NULL)不存在元素值为e的节点，返回0return(O);else存在元素值为e的节点，返回其逻辑序号ireturn(i);)bool Listlnsert(LinkList *&L,int i,ElemT

10、ype 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=(LinkList *)malloc(sizeof(LinkList);s-data=e;创立新节点*s,其data域置为es-next=p-next; 将*s 插入到*p 之后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个节点，返回false