单链表实验报告

1、单链表实验报告计算机与信息技术学院综合性、设计性实验报告专业：网络工程年级/班级：大二 2016 2017 学年第一学期课程名称数据结构指导教师李四学号姓名16083240XX 张三项目名称单链表的基本操作实验类型综合性/设计性实验时间2017.10.3实验地点216 机房一、实验目的（1）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。二、实验仪器或设备（1） 硬件设备：CPU为Pentium 4以上的计算机，内存2G以上（2） 配置软件：Microsoft Windows 7与VC+6.0三、总体设计（设计原理、设计方案及流程等）设计原理：单链表属于线性表，线性表的存储

2、结构的特点是：用一组任意存储单元存 储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个 指示其直接后继的信息。设计方案：采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序 段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说 可以处理非法数值的代码。设计流程：1. 引入所需的头文件；2. 定义状态值；3. 写入顺序表的各种操作的代码；写入主函数，分别调用各个函数。在调用函数时，采用 if 结构进行判断输 入值是否非法，从而执行相应的程序四、实验步骤（包括主要步骤、代码分析等）#include

3、 / EOF（=AZ或F6）,NULL#in cludesrand( ) ,rand( ),exit( n)#i nclude/malloc( ),alloc( ),realloc()等#i nclude / INT_MAX等#i nclude#in clude#in clude/floor(),ceil( ),abs()#i nclude / cout,c in#in clude/clock( ),CLK_TCK,clock_t#defi neTRUE1#defi neFALSE0#defi neOK1/#defi neERROR0#defi neINFEASIBLE -1#defi neO

4、VERFLOW-2typedefintStatus;/ Status是函数的类型,/其值是函数结果状态代码，如OK等typedefintElemType;typedef struct LNodeElemType data;/结点的数据域struct LNode *n ext; /结点的指针域LNode,*Li nkList; /Li nkList为指向结构体LNode的指针类型/初始化单链表算法步骤：1.生成新结点作为头结点，用头指针L指向 头结点。2.头结点的指针域置空。Status InitList_L(L in kList &L)L=new LNode;/生成新结点作为头结点，用

5、头指针L指向头结点；L-next=NULL; /头结点的指针域置 空return OK;/单链表的取值算法步骤：1.用指针P指首元结点，用j做计数器初值赋为1.2.从首元结点开始依次顺着链域 访问，只要指向当前结点的指针(NULL,并且没有到达序号为则循环执行以下操作：P指向下一结点； 计数器j相应加1；3.退出循环时，如果指针p为空，或者计数器 大于i，说明指定的序号i值不合法(i大于表长n或i小于等于0)，取值失败返回ERROR否则取值成功，此时j=i时，p所指的结点就是 要找的第i个结点，用参数e保存当前结点的数 据域，返回0KStatus GetElem_L(LinkList L, i

6、nt i,ElemType &e)Lin kList p;int j;p=L-n ext;j=1;while(p&jn ex t;n ext向下p不为空i的结点，+j;if(!p|ji) return ERROR; e=p-data;return OK;/单链表的按值查找算法步骤:1.用指针p指首元结点。2.从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e， 则循环执行以下操作：p指向下一个结点。3.返回p。若查找成功，p此时即为结点的 地址值，若查找失败，p的值即为NULLint LocateElem_L(Lin

7、kList L,ElemType e)LinkList p;int j;p=L-n ext;j=1;while(p&p-data!=e)p=p-n ext;j+；if(p) return j;else return 0;/单链表的插入算法步骤：1.查找结点an并由指针p指向该结点。2.生成一个新结点*s。3.将新结点*s的数据域置为e。4.将新结点*s的指针域指向结点a。5.将结点*p的指针域指向新结点*s。StatusListI nsert_L(Li nkList& L,i nti, ElemType e)Lin kList p=L,s; in t j=0;while(p&a

8、mp;(jn ex t;+j;if(!p|ji-1)return ERROR; s=new LNode;s-data=e;s-n ext=p-next;p-n ext=s;return OK;/单链表的删除1.查找结点an并由指针p指向该结点。2.临时保存待删除结点a的地址在q中， 以备释放。3.将结点*p的指针域指向ai的直接后继结 点。4.释放结点ai的空间。Status ListDelete_L(LinkList &L,int i)Lin kList p=L,q;in t j=0;while(p- next)&(jn ext;+j；if(!p-next)| (ji-1)

9、return ERROR;q=p-n ex t;p-n ext=q-n ex t;delete q;return OK;/单链表的输出算法步骤：1.将指针p指向L的next域2.输出p指针的数据。3.将指针p后移。4.循环第2,3步，直到p指针为空(NULL。void ListPri nt_L(Li nkList L)Lin kList p;p=L-n ex t;doprin tf(%5d,p-data);p=p-n ex t;while(p);void mai n()int i,n,e;Li nkList L;if(I nitList_L(L);prin tf(单链表创建成功！n);pri

10、ntf(“请输入您要输入的数据个数n: n);sca nf(%d,&n);prin tf(请输入您要输入的数据：n);for(i=1;i=n ;i+)sea nf(%d, &e);List In sert_L(L,i,e);prin tf(当前单链表的内容为：n);ListPrint_L(L);pri ntf(n “);printf(请输入您要插入的数据e及其位置i，使用空格键隔开:n);seanf(%d %d,&e,&i);if(ListInsert_L(L,i,e)prin tf(当前单链表的内容为：n);ListPr in t_L(L);elseprint

11、f(i值越界！n);pri ntf(in “);pri ntf(“请输入您要取的数据序号：n);sea nf(%d,&i);if(GetElem_L(L,i,e)printf(“第%d位数据的为:%dn,i,e);elseprintf(i值越界！n);printf(请输入要查找的数据值：n);sca nf(%d, &e);if(!LocateElem_L(L,e)printf(查无此值!n);elseprintf(数据%d在%d号位n,e,LocateElem_L(L,e);printf(请输入要删除的 数据的序号n);sea nf(%d,&i);if(ListDelete_L(L,i)图 i结果分析：如图 1 所示，输入正确数据时，程序各个功能执行正常。设置输入数据个数为 5,可以输入 5 个数据，按回车后，可以显示我们当前单链表中的数据内容。继续 输入下一指令：输入要插入的数据及位置，使用空格键隔开，回车后，可以看 到已经成功插入。继续输入所取的数据序号，可以查