数据结构与算法实验——单链表的定义与操作.docx

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

1、单链表的定义和操作实验报告开始输出实验名称及功能界面F定义的各种变量, 其 I!flag=lflag=l?月目头插法建立 卜元素单链表 breaka breaka breaka break， breaka break一 .A一一A break4 Krpnlc，L/l VCllxa break结束调试报告1.在执行清空单链表的函数后，再执行判断空链表的函数时，输出The LinkListis not empty!,与预期实验结果不符，而编译和组建时均为发出错误和警告 信号。后经过单步运行调试后，发现是清空单链表的函数出了问题(while(q) 循环语句出了问题)，应该把循环控制语句q改为P,修改

2、完毕后现已得到正 确结果“The LinkList is empty!”。2.程序设计初期因没有优先考虑到用户体验，造就了流水线的链表功能调用。 经老师提醒和建议，我又在整理实验报告之前，在原来的程序基础上添加了 switch语句和while循环语句，以实现随时调用。使用说明c: UsersAdm i n i stratorDesktop数据结构实验 f i n i shedDebug I ink I i st. exe操作界面)lease input ten numbers:是否继续操作，是为I.否为。：I用头插法建立十元素单链表98 ?. 6. 5432. 1 日是否继续操作，是为1,否为

3、日： 1遍历单链表中的所有元素清输入功能号n :5The length of the LinkList is 10 !是否继续操作，是为1 ,否为8 ：1求单链表的长度hFhe 3 th element of the LinkList is 6 !强否继磋操儡鄙1,否的目：1查找第3位元素Fhe 5 is in the place of the LinkList, 4!是否继续操作，是为1,否为：1求第一个元素值为5的位置H我入功能号n:8定否继续操作，是为1,否为0：在第5个元素前插入元素3请输入功能号n: / 6. 3543210是否继续操作，是为1,否为8:1遍历当前单链表青输入功能号n

4、 :5The length of the LinkList is 1 1 ?是否继续操作，是为1,否为8：1求当前单链表的长度请输入功能号n: 9是否继续操作，是为1,否为8:1删除值为6的第一个元素输入功能号498T4321是否继续操作，是为1,否为0：1遍历当前链表请输入功能号n: 2是否继续操作，是为1 ,否为8 :;是否继续操作，是为1,否为0:清空单链表检验空链表,lease input 5 elements to create the LinkList: 12946 遍历当前单链表的元素为：12946是否继续操作，是为1,否为： B用尾插法建立单链表及结束心得体味1 .做这个实验前

5、，自以为数据结构知识学得已算牢靠，加之自身的动手能力还 算强，便没有以一种严谨的态度去编写程序，导致在即将大功告成之时， 浮现了一个没有编译、组建问题，而却与预期结果大相径庭的失误，只 得从头一步一步调试过来，不仅浪费了时间，也花费了不少精力。直到最后 才晓得，是循环语句的判别条件P写成为了q。经过这次惨重的教训，我蓦 地 觉得自己的编程素质还很低，亟待提升。以后编程大可不要马糊大意了, 定 要有严谨的思维。2 .程序设计初期因没有优先考虑到用户体验，造就了流水线的链表功能调用。 经老师提醒和建议，我又在整理实验报告之前，在原来的程序基础上添加了 switch语句和while循环语句，以实现随

6、时调用。漆老师说的的确很有道理， 实验不应仅仅是完成任务，而应该将之视为难得的实践机会。既然开始了， 就要把它做的全面美观，要时时刻刻为用户着想。单链表的定义和操作实验报告实验名称单链表的定义和操作实验目的1 .熟悉C语言的上机环境。掌握C语言的基本结构；2 .定义单链表的结点类型；3 .熟悉对单链表的具体函数定义和一些基本操作；4 .通过对单链表的定义掌握线性表的链式存储结构的特点。实验内容编制一个演示单链表插入、删除、查找等操作的程序。问题描述用数据结构相关知识，实现单链表的定义和操作。该程序包括单链表结构类型以 及对单链表操作的具体的函数定义（包括：初始化单链表、清空单链表、检查单 链表

7、是否为空、遍历单链表、求单链表的长度、从单链表表中查找元素、从单链 表表中查找与给定元素值相同的元素在链表中的位置、向单链表中插入元素、从 单链表中删除元素、用尾插法建立单链表）。问题分析该实验是基于C语言和数据结构知识基础的对单链表的基本操作的检验，无需设 计复杂的算法，程序语句也相对简单。因此，我直接按要求定义了对单链表操作 的具体函数，并于主函数中实现对应的功能调用，其中，功能选择靠switch语句 实现。实验步骤1 .需求分析本演示程序用VC+编写，完成单链表的生成，任意位置的插入、删除，以及 确定某一元素在单链表中的位置等操作。输入的形式和输入值的范围：插入元素时需要输入插入的位置和

8、元素的值； 删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中， 元素的值都是整数。输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内 容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置。程序所能达到的功能：完成单链表的生成(通过插入操作)、插入、删除、查 找等操作。测试数据：插入操作中挨次输入0,1,2,3,4, 5,6, 7,8,9生成一个单链表2 .概要设计1)为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT LinkList 数据对象：D= ai | ai IntegerSet, i=0,1,2, , n, nNO数据关系

9、：R= |ai, ai+1 D基本操作：Void Listinsert(LinkList l,int i,DataType x)初始条件：单链表I已存在操作结果：将元素x插入到单链表I的i位置Void ListDel(LinkList I,DataType x)初始条件：单链表I已存在操作结果：将单链表L中值为x的元素删除int ListGet(LinkList L,DataType x)初始条件：单链表I依存在操作结果：单链表I中查找是否元素x,若存在，返回元素在表中的位置2)本程序包含7个函数：主函数main()清空单链表函数LinkedListClear。检查单链表是否为空函数 Link

10、edListEmpty()遍历单链表函数LinkedListTraverse ()求单链表的长度函数 LinkedListLength ()从单链表表中查找元素函数LinkedListGet ()查找与给定元素 的位置函数LinkedListLocateO插入元素函数LinkedListlnsert ()删除元素函数 LinkedListDel ()用尾插法建立单链表函数LinkedListCreat ()函数说明#include#include#includedefine FALSE 0 逻辑值define TRUE 1 逻辑值typedef int DataType;struct Node

11、链表的结点类型DataType data;struct Node* next;);typedef struct Node* PNode ：指向结点指针typedef struct Node* LinkList;/指向链表指针创建空单链表：带头结点的空链表LinkList LinkListlnit()LinkList p;p= (LinkList)mal 1 oc(sizeof (struct Node);为表头结点申请空间 if(p=NULL)printf(nOut of space!nH); return NULL;)elsep-next=NULL;) return p;)清空单链表void

12、 LinkListClear(LinkList I)(PNode p=l,q=p-next;while(p)cfree(p);p=q;if(q) q=p-next;)l-next=NULL;j判断是否为空链表 int LinkListEmpty(LinkList I)return l-next=NULL;j遍历单链表中所有元素 void LinkListTraverse(LinkList I)(LinkList p=l;while(p-next)(printf(H%d n,p-next-data); p=p-next;1printf(nn);求单链表的长度int LinkListLength(

13、LinkList |)int len=O;LinkList p=l;while(p-next)len+;p=p-next;)return len;查找第i位元素DataType LinkListGet(LinkList I,int i)(PNode p=l;int j=0;while(jnext;j+；)1return p-data;)求x元素的存储位置int LinkListLocate(LinkList I,DataType x)(PNode p;int i=1;if(l=NULL) return 0;p=1-next;while(p!=NULL&p-next-data!=x)p=p-ne

14、xt;i+；)return i;)在第i + 1个元素前插入值为x的元素void LinkListlnsert(LinkList I,int i,DataType x)PNode p,q;int j=0;P=l；while(p!=NULL&jnext;J+；)if(j!=i) (printf(nThe value of i=%d is not reasonableAn);q=(PNode)malloc(sizeof(struct Node);if(q!=NULL) (q-data=x;q-next=p-next; p-next=q;)单链表单个结点的删除void LinkListDel(Lin

15、kList l,DataType x) (PNode p,q;p=l;p=p-next;if (p-next=NULL)没找到 x (printf(nNot existin);j else(q=p-next;p-next=p-next-next;/del free(q);用尾插法建立单链表LinkList LinkListCreat(int n)int i;PNode rear,sLinkList first;first=(LinkList)nBlloc(sizeof (struct Node);rear才irst;printf (Please input %d elements to cre

16、ate the LinkList:,n); for(i=0; idata);rear-next=s;rear=S;rear-next=NULL;return first;int main(int argc, char *argv 口)W I . pr mtf Iprintf (*n);pr i ntf (*单链表的定义和操作*n”);printf(*n);,. f 11V f1 r |- i j pr i ntf (*)n);pr i ntf (*功能选择与实现*n”);printf (*n”）；printf (1.用头插法建立十元素单链表*n);printf (2.清空单链表*n”)prin

17、tf (*3.判断是否为空链表*rT);printf (4.遍历单链表中所有元素*n”);pr intf(5.求单链表的长度*rT);printf(6.查找第i位元素*n“);printf C*7 .求x元素的存储位置*n”);printf (*8 .在第i + 1个元素前插入x*n”);printf (9.单链表单个结点的删除*n“);printf (10.用尾插法建立单链表*n);printf (*n”);prntf (*)n);int ab, i,x,n,flag=1;LinkList ppLinkListlnitO ；LinkList q=LinkListlnitO ; 创建指向链表的

18、头结点int len, jud;DataType data;whi le(f lag)printf （n请输入功能号n: t）;scanf(d”,&n);switch(n)case 1 :printf(HPlease input ten numbers:n);for(i=0;i10;i+)scanf(%d*,&a);LinkListlnsert (p, 0, a);在第一个元素前插入新结点break;case 2:LinkListClear(p); 清空单链表break;case 3:jud=LinkListEmpty(p);if(jud) 检查单链表是否为空printf(MThe LinkL

19、ist is empty!nM);elseprintf(HThe LinkList is not empty!nn);break;case 4:LinkListTraverse(p);遍历单链表中所有元素break;case 5:len=LinkListLength(p);printf (/z1he length of the LinkList is %d !n, len);/求单链表的长度 break;case 6:printf (请输入 i:t);scanf(H%d,&i);data=LinkListGet(p,i);printf (The %d th element of the Lin

20、kList is %d !n, i, data);查找单链表中的 第i位元素break;case 7: printf (请输入x: t)；scanf(-d”,&x);b=LinkListLocate(p,x);printf CThe %d is in the place of the LinkList, %d !n, x, b); 查找单链表中的x break;case 8: printf (请输入元素a和位置i:t);scanf(H%d %d,&a,&i);LinkListlnsert (p, i, a);在第1个元素前插入新结点 break;case 9: printf (请输入 x: t);scanf(-d”,&x);LinkListDel(p,x);删除值为x的第一个元素break;case 10:q=LinkListCreat(5);用尾插法建立长度为5的单链表printf (遍历当前单链表的元素为：)；LinkListTraverse(q);遍历单链表中所有元素printf (是否继续操作，是为1,否为0:t);scanf(,%d,&flag);return 0;程序流程图