单链表实验报告

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

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

3、# i nc 1 ude< s t dio、h> / E OF(=Z 或 F6) ,NULL# i ncl u de< s t dli b、h> / / srand ( ) , r a nd( ), exi t (n)# i nc 1 u de<mal 1 o c h) / / mal I o c ( ), a 1 loc ( ), rea 1 loc ()等# i nc 1 ude <1 i mi ts. h> / INT_MAX等# i n clu d estring、h )# inc 1 u d e (ctype> h ># i n

4、clu d e<m ath、h > / f loo r (), cei 1 ( ), a b s()#inc 1 ude (iostream h> / / c o ut, cin#in c lude<timex h > / / clock ( ),CLK_TCK, c 1 ock_t# d e f i neTRUE1# de f ineFALSE0#de f i neOK1# d e fineERROR0# d efineINFE A S IBLE1# define OVE RFLOW一2t y pedefi n tStatus：/ St a t u s 就是函数

5、得类型，/其值就是函数结果状态代码，如OK等typ e d e fintE 1 emT y p e；t y pe d ef stru c t LNod eElemType da t a;/结点得数据域« s tr u c t LNo de * n e xt；/结点得指针域 LNode, *LinkLi s t：/LinkLis t为指向结构体LNode得指针类型/初始化单链表算法步骤：1. 生成新结点作为头结点，用头指针L指向头结点.2. 头结点得指针域置空.S t atu s I n i t Lis t_L(L i nkL i s t &L)L二n ew LNo de；。/

6、生成新结点作为头结点，用头指针L指向头结点：丄一>ne x t=NULL; 9/头结点得指针域置空»ret urn OK;/单链表得取值算法步骤：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个结点，用参数

7、e保存当前结点得数据域，返回0K.Sta t us GetElem_L (Link List L, in t i, E 1 emTyp e &e)丄inkLi s t p;j n t j；p 二L>next：d=l;while (p & &jV i )ap = p-> next；0+j;df(! p I ji) return ER R O R;e= p data;r et u r n OK;/单链表得按值查找算法步骤：1. 用指针P指首元结点。2. 从首元结点开始依次顺着链域皿壮向下查找，只要指向当前结点得指针p不为空, 并且P所指结点得数据域不等于给左值e

8、 ,则循环执行以下操作:p指向下一个结 点°3. 返回p.若查找成功,p此时即为结点得地址值,若查找失败,p得值即为NULL。 int LocateElem_L( L in k List L, ElemType e)iin k List p;in t j ;p 二 L next；d = 1 :while ( p &&p-d a t a ! =e)Q p-p>ne x t;j卄；jif ( p ) r e t u rn j;e 1 se return 0 :/单链表得插入算法步骤：1. 查找结点a：,并由指针p指向该结点.2. 生成一个新结点* s。3. 将新结点

9、次s得数据域置为e。4. 将新结点*$得指针域指向结点a“5. 将结点*p得指针域指向新结点* s.St a tus L i stInsert_L( L in kList &L, i nt i, ElemTy p e e )ii n kL i s t p二L, s：dnt j二0;while (p&&(jV i -D)。np 二 p>next;if (! P I j> i -1)0 a retu r n ERROR；ns二new L N od e ；s > d a t a=e：s >nex t =p) n ext；np-next= s : ret

10、urn O K ;/单链表得删除1. 査找结点a-并由指针p指向该结点。2临时保存待删除结点乞得地址在q中，以备释放。3. 将结点次P得指针域指向a i得直接后继结点.4. 释放结点a：得空间.S tatus L istD e let e _L(LinkList &L, i n t i) n kL i st p二L, q：i n t j二0；呵hi.le (pnext) &&(j<iT)0 ap二p>n e xt：卄j;if ( ! p ) next) I I ( j > i - 1 )return ERROR;a q =p->ne x t:p-

11、ne x t = q >next;dele t e q;return OK：/单链表得输岀算法步骤：1. 将指针p指向L得next域。2. 输出p指针得数据。3. 将指针p后移。4. 循环第2, 3步，直到p指针为空(NULL)。voi d L istPri n t_L ( L inkL i st L)丄 i nkLis t p ；p=L >n e x t;)do0 a p r i n tf ( H %5d'* , p->d a ta):巾二 p >n ext;w h ile (p):vo i d m a in ()int i, n, e ;L i nkL i

12、s t L;if (In i tList_L(L)；P r i ntf (”单链表创建成功！ n”)：°printf ("请输入您要输入得数据个数n： n ")：scan f (” d",&n)：oprintf (”请输入您要输入得数据：n”)；of or (i=l; i <=n： i+)s canf (” $ d ", &e)；«Lis t Inse r t _L (L, i, e )；pr i n t f ("当前单链表得内容为:n")：Li s tP r int_L (L)；°

13、pri n tf (v n ");print f ("请输入您要插入得数据e及其位苣i，使用空格键隔开： n ”)； s canf ( " %d %d”，&e,&i);i f (ListInsert_L(L, i, e)prin t f ( '当前单链表得内容为:n”)：ListPrint_L (L)；>e 1 s e。p r i n t f ("i 值越界!n")；prin t f ("n ")；°pri ntf("请输入您要取得数据序号： n ”)；scanf (” d

14、"，&i)：i f (Ge tElem_L (L, i,e)。printf (*第<1 位数据得值为：dn", i , e);4el s e。ap r intf ( i 值越界！ n ");，pri n t f (”请输入要查找得数据值： n ”)；oscanf ("%d", & e)；i f(!Loca t eEle m_L (L» e)pr i ntf （"査无此值！ n"）；elseprintf ("数据%d 在d 号位置n, e, Locat e El e m_L ( L , e)：。4°print f (”请输入要删除得数据得序号：n");o s canf C%dM , & i );oi f (ListDelete.L (L, i)。printf(?，删除后单链表得内容为：n”)；。ListP r in t _L (L)：吃Ise4 printf ("输入有误！ ”);J>pr i ntf ("n” )；五、结果分析与总结图1结果分析：如图1所示，输入正确数据时，程序各个功能执行正常。设置输入数据个数为5 , 可以输入5个数据，按回车后，可以显示我们当前单链表中得数据内容。继续输