单链表实验报告————————————————————————————————作者：————————————————————————————————日期：计算机与信息技术学院综合性、设计性实验报告专业：网络工程年级／班级：大二 2016—2017学年第一学期课程名称数据结构指导教师李四学号姓名16０8３2４０XX 张三项目名称单链表的基本操作实验类型综合性／设计性实验时间2017.10.3 实验地点216机房一、实验目的（１）熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。
二、实验仪器或设备(1)硬件设备：CＰU为Pｅntium 4以上的计算机,内存２G以上（２）配置软件:Microsｏft Windｏws 7与VC++6．０三、总体设计（设计原理、设计方案及流程等)设计原理：单链表属于线性表,线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的。
因此,对于某个元素来说，不仅需要存储其本身的信息,还需要存储一个指示其直接后继的信息。
设计方案:采用模块化设计的方法，设计各个程序段,最终通过主函数实现各个程序段的功能。
设计时，需要考虑用户输入非法数值,所以要在程序中写入说可以处理非法数值的代码。
设计流程:1.引入所需的头文件;2.定义状态值；3.写入顺序表的各种操作的代码；写入主函数,分别调用各个函数。
在调用函数时，采用iｆ结构进行判断输入值是否非法,从而执行相应的程序四、实验步骤（包括主要步骤、代码分析等）#inclｕdｅ<ｓtdio．h＞／/ EOF(=^Z或F6）,ＮUＬL#inclｕde＜ｓtdlｉb.ｈ＞ // sｒand（），raｎd（）,eｘｉt(n)#inｃlude＜ｍalloｃ.h> // mａlloc( )，alloc( ),ｒｅａllｏc（）等＃iｎcluｄe<lｉmiｔs.ｈ> /／IＮT_MAX等#iｎclude<stｒing.ｈ>#ｉｎｃｌuｄe<cｔｙpe．ｈ＞#iｎcludｅ<maｔh.h> // floor(),ceil( ),abs( )#ｉnclude＜ｉosｔreａm．h＞ // coｕt,cｉn＃iｎclｕde<tiｍｅ.ｈ> // clｏｃk（),ＣLK＿ＴCK,ｃlock＿t#ｄefine ＴRＵＥ 1#define FALSE 0＃ｄeｆine ＯＫ 1＃define ERROR 0＃defiｎｅINFEＡSIBＬE -1＃ｄｅfine OVEＲFLOW -2ｔｙpedef int Sｔａtuｓ; ／/ Sｔａtuｓ是函数的类型, //其值是函数结果状态代码，如ＯＫ等typｅdeｆ int ＥleｍＴypｅ;typedeｆ sｔruct ＬNode｛ElemＴｙpe ｄａｔa; //结点的数据域stｒｕct LNｏde *ｎexｔ; ／/结点的指针域}LＮode,*LinkＬiｓｔ; //LiｎkLisｔ为指向结构体LNoｄｅ的指针类型//初始化单链表算法步骤：1.生成新结点作为头结点，用头指针Ｌ指向头结点。
2.头结点的指针域置空。
Staｔuｓ InitLｉｓｔ_Ｌ（LｉnｋＬｉst ＆L){ﻩL＝new LＮode;ﻩ//生成新结点作为头结点,用头指针L指向头结点;L->next=NＵLL; ﻩ//头结点的指针域置空rｅturｎ OK;}//单链表的取值算法步骤:1.用指针P指首元结点，用j做计数器初值赋为1.2.从首元结点开始依次顺着链域next向下访问,只要指向当前结点的指针ｐ不为空（NULL)，并且没有到达序号为i的结点，则循环执行以下操作：P指向下一结点；计数器j相应加１；3．退出循环时,如果指针p为空，或者计数器j大于i,说明指定的序号i值不合法(i 大于表长n或ｉ小于等于0),取值失败返回ERROR，否则取值成功，此时j=ｉ时，p所指的结点就是要找的第ｉ个结点，用参数ｅ保存当前结点的数据域,返回OK。
Ｓtａtus ＧetElem＿L(LinkＬisｔ L， inｔｉ，ElemTｙpe &e）{ﻩLinｋList ｐ;ﻩint j;ﻩp=L->neｘt；ﻩj=1;ﻩwhile(p&&ｊ<ｉ){ﻩp=p－＞nｅxt;ﻩ+＋j;}ﻩif（!p||j>i) reｔｕrn ERＲOR；ﻩe＝p->data;ﻩretuｒｎOＫ;}//单链表的按值查找算法步骤:1.用指针ｐ指首元结点。
2.从首元结点开始依次顺着链域nexｔ向下查找，只要指向当前结点的指针p不为空,并且p所指结点的数据域不等于给定值e,则循环执行以下操作:p指向下一个结点。
3.返回p。
若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
ｉnt LocaｔeElem_L(LinkＬist L,ＥｌemＴyｐe e){ﻩLｉnｋLisｔｐ;ﻩinｔ j；p=Ｌ－>ｎeｘｔ;ｊ＝1;ｗhile(p&&ｐ-＞ｄaｔa!=e)ﻩ{ﻩp＝p->nexｔ;j++；｝ﻩiｆ(p) retｕrｎ j;ﻩelｓe ｒeturn 0;}//单链表的插入算法步骤:1.查找结点aｉ-１并由指针p指向该结点。
2.生成一个新结点*s。
3.将新结点＊ｓ的数据域置为e。
4.将新结点*s的指针域指向结点ａi。
5.将结点＊p的指针域指向新结点＊s。
Sｔatus LisｔInseｒt_L(LｉnkList &Ｌ,int ｉ,ＥlｅmＴype e){ﻩLiｎkLiｓt ｐ=L,s;iｎｔ j=0;ﻩwhilｅ(p&&(j<i-1)){ﻩﻩp=p->neｘt;ﻩ+＋j;ﻩ}ﻩif(!p||j>i－1){reｔuｒn ERＲOR;ﻩ｝ﻩｓ=nｅw LＮode；s-＞ｄａtａ=e;ﻩs－>nｅｘｔ=ｐ－＞ｎext;p->neｘt=s；ﻩreｔurｎＯK;｝/／单链表的删除1.查找结点ａi－1并由指针p指向该结点。
2.临时保存待删除结点a i的地址在q中，以备释放。
3.将结点*p的指针域指向a i的直接后继结点。
4.释放结点ａi的空间。
Status LｉstＤelｅｔe_L（ＬinkＬist &Ｌ,int i) ｛ＬiｎkLiｓt p=Ｌ,q;ﻩint j＝0；ｗhile（(p-＞neｘt)&&(j<ｉ-1)){p＝p－＞next;++j;}iｆ(（!p->next)｜｜(j>ｉ-1)）{ﻩﻩrｅｔｕrn ERROR;}q=p－>next;ﻩｐ->nexｔ=q->neｘｔ；delete q;reｔurn ＯＫ;}//单链表的输出算法步骤:1.将指针ｐ指向L的next域。
2.输出p指针的数据。
3.将指针p后移。
4.循环第2,3步，直到p指针为空（NULL）。
void ＬisｔPｒint＿Ｌ(LinkLｉst Ｌ){ﻩLinｋLisｔ p;p=Ｌ->ｎexｔ;ﻩｄｏﻩ{ﻩﻩpｒintf（＂％5d＂,p－>ｄata)；ﻩp=ｐ－>next;}ｗhile(ｐ);}void mａin(){ﻩint i,n，e;ＬinkＬiｓｔＬ;if(InｉtＬisｔ_Ｌ(L));ｐrintf（＂单链表创建成功！\n"）；printf("请输入您要输入的数据个数n：＼ｎ");scanf("%d＂,＆n）;pｒｉnｔf（"请输入您要输入的数据:\n");ﻩfor(i＝1；ｉ<=ｎ;i++){scａnf（"%ｄ",&e);LｉstＩnsert_Ｌ(L,i,ｅ）;ﻩ}ﻩpriｎtｆ("当前单链表的内容为：\n");ListＰriｎt＿L(L);ﻩpｒｉnｔf（＂\n＂）;prｉｎtf（"请输入您要插入的数据e及其位置i，使用空格键隔开:\n")；ﻩscａnｆ("％d ％d",&e，＆ｉ);ﻩｉf(LｉstInｓｅrt_L(Ｌ,i,ｅ))ﻩ｛ﻩpriｎｔf("当前单链表的内容为:\n")；ListPｒinｔ_Ｌ(L）;}ﻩelse{ﻩｐrｉnｔf("i值越界！＼ｎ"）;｝ﻩｐｒintf("\n");ﻩｐrｉntf("请输入您要取的数据序号:\ｎ")；ﻩｓcaｎf("%d"，&i);if(ＧetEleｍ_L（L,ｉ，ｅ）){ﻩpｒｉｎtf("第%d位数据的值为:%ｄ＼n＂,i,e);}ｅｌsｅ{ﻩﻩｐrintf("i值越界！\n＂);}ﻩprintｆ（"请输入要查找的数据值:＼n"）;ﻩｓcanｆ（"%d"，＆ｅ);iｆ(!LｏcａteEｌem＿L(L，e))ﻩ｛ｐrｉnｔf("查无此值!\n");}ﻩelseﻩ{prｉntf(＂数据％d在％d号位置\n",ｅ，LｏcateＥleｍ＿L(L,e));ﻩﻩ}prinｔf(＂请输入要删除的数据的序号:\n"）；ﻩsｃａｎf（＂％d＂，&i）;if(ＬistDelｅｔe_L(Ｌ,ｉ))ﻩ{ﻩﻩprintf（"删除后单链表的内容为:＼ｎ");ﻩﻩLiｓtPriｎｔ_Ｌ(L);}elｓe{ﻩpｒintf("输入有误!")；ﻩ｝ﻩprｉntｆ(＂\n"）；}五、结果分析与总结图１结果分析：如图１所示,输入正确数据时,程序各个功能执行正常。
设置输入数据个数为5，可以输入5个数据,按回车后，可以显示我们当前单链表中的数据内容。
继续输入下一指令:输入要插入的数据及位置,使用空格键隔开，回车后，可以看到已经成功插入。
继续输入所取的数据序号,可以查找该数据的值。
输入要查找的数据,可以返回该数据的位置。
输入要删除的数据，可以返回删除该元素后的单链表的内容。
总结:在单链表中,对数据元素ａ来说,除了存储其本身的信息之外，还需存储一个指i示其直接后继的信息。
这两部分信息组成数据元素a的存储映像,称为结点。
它ｉ包括两个域;其中存储数据元素的域称为数据域;存储直接后继的域称为指针域。
教师签名:年月日。