单链表实验报告

计算机与信息技术学院综合性、设计性实验报告专业：网络工程年级/班级：大二2016—2017学年第一学期课程名称数据结构指导教师李四学号姓名16083240XX张三项目名称单链表的基本操作实验类型综合性/设计性实验时间2017.10.3实验地点216机房一、实验目的（1）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。二、实验仪器或设备（1）硬件设备：CPU为Pentium4以上的计算机，内存2G以上（2）配置软件：MicrosoftWindows7与VC++6.0三、总体设计（设计原理、设计方案及流程等）设计原理：单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。设计方案：采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。设计流程：1.引入所需的头文件；2.定义状态值；3.写入顺序表的各种操作的代码；写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输入值是否非法，从而执行相应的程序四、实验步骤（包括主要步骤、代码分析等）#includestdio.h//EOF(=^Z或F6),NULL#includestdlib.h//srand(),rand(),exit(n)#includemalloc.h//malloc(),alloc(),realloc()等#includelimits.h//INT_MAX等#includestring.h#includectype.h#includemath.h//floor(),ceil(),abs()#includeiostream.h//cout,cin#includetime.h//clock(),CLK_TCK,clock_t#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;//Status是函数的类型,//其值是函数结果状态代码，如OK等typedefintElemType;typedefstructLNode{ElemTypedata;//结点的数据域structLNode*next;//结点的指针域}LNode,*LinkList;//LinkList为指向结构体LNode的指针类型//初始化单链表算法步骤：1.生成新结点作为头结点，用头指针L指向头结点。2.头结点的指针域置空。StatusInitList_L(LinkList&L){L=newLNode;//生成新结点作为头结点，用头指针L指向头结点；L-next=NULL;//头结点的指针域置空returnOK;}//单链表的取值算法步骤：1.用指针P指首元结点，用j做计数器初值赋为1.2.从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有到达序号为i的结点，则循环执行以下操作：P指向下一结点；计数器j相应加1；3.退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或i小于等于0），取值失败返回ERROR，否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保存当前结点的数据域，返回OK。StatusGetElem_L(LinkListL,inti,ElemType&e){LinkListp;intj;p=L-next;j=1;while(p&&ji){p=p-next;++j;}if(!p||ji)returnERROR;e=p-data;returnOK;}//单链表的按值查找算法步骤：1.用指针p指首元结点。2.从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行以下操作：p指向下一个结点。3.返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。intLocateElem_L(LinkListL,ElemTypee){LinkListp;intj;p=L-next;j=1;while(p&&p-data!=e){p=p-next;j++;}if(p)returnj;elsereturn0;}//单链表的插入算法步骤：1.查找结点ai-1并由指针p指向该结点。2.生成一个新结点*s。3.将新结点*s的数据域置为e。4.将新结点*s的指针域指向结点ai。5.将结点*p的指针域指向新结点*s。StatusListInsert_L(LinkList&L,inti,ElemTypee){LinkListp=L,s;intj=0;while(p&&(ji-1)){p=p-next;++j;}if(!p||ji-1){returnERROR;}s=newLNode;s-data=e;s-next=p-next;p-next=s;returnOK;}//单链表的删除1.查找结点ai-1并由指针p指向该结点。2.临时保存待删除结点ai的地址在q中，以备释放。3.将结点*p的指针域指向ai的直接后继结点。4.释放结点ai的空间。StatusListDelete_L(LinkList&L,inti){LinkListp=L,q;intj=0;while((p-next)&&(ji-1)){p=p-next;++j;}if((!p-next)||(ji-1)){returnERROR;}q=p-next;p-next=q-next;deleteq;returnOK;}//单链表的输出算法步骤：1.将指针p指向L的next域。2.输出p指针的数据。3.将指针p后移。4.循环第2,3步，直到p指针为空（NULL）。voidListPrint_L(LinkListL){LinkListp;p=L-next;do{printf(%5d,p-data);p=p-next;}while(p);}voidmain(){inti,n,e;LinkListL;if(InitList_L(L));printf(单链表创建成功！\n);printf(请输入您要输入的数据个数n:\n);scanf(%d,&n);printf(请输入您要输入的数据：\n);for(i=1;i=n;i++){scanf(%d,&e);ListInsert_L(L,i,e);}printf(当前单链表的内容为：\n);ListPrint_L(L);printf(\n);printf(请输入您要插入的数据e及其位置i，使用空格键隔开:\n);scanf(%d%d,&e,&i);if(ListInsert_L(L,i,e)){printf(当前单链表的内容为：\n);ListPrint_L(L);}else{printf(i值越界！\n);}printf(\n);printf(请输入您要取的数据序号：\n);scanf(%d,&i);if(GetElem_L(L,i,e)){printf(第%d位数据的值为:%d\n,i,e);}else{printf(i值越界！\n);}printf(请输入要查找的数据值：\n);scanf(%d,&e);if(!LocateElem_L(L,e)){printf(查无此值!\n);}else{printf(数据%d在%d号位置\n,e,LocateElem_L(L,e));}printf(请输入要删除的数据的序号：\n);scanf(%d,&i);if(ListDelete_L(L,i)){printf(删除后单链表的内容为：\n);ListPrint_L(L);}else{printf(输入有误！);}printf(\n);}五、结果分析与总结图1结果分析：如图1所示，输入正确数据时，程序各个功能执行正常。设置输入数据个数为5，可以输入5个数据，按回车后，可以显示我们当前单链表中的数据内容。继续输入下一指令：输入要插入的数据及位置，使用空格键隔开，回车后，可以看到已经成功插入。继续输入所取的数据序号，可以查找该数据的值。输入要查找的数据，可以返回该数据的位置。输入要删除的数据，可以返回删除该元素后的单链表的内容。总结：在单链表中，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素ai的存储映像，称为结点。它包括两个域；其中存储数据元素的域称为数据域；存储直接后继的域称为指针域。教师签名：年月日