2023年数据结构单链表实验报告.docx
洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期11. 7实验名称链表的基本操作成绩实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作 算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，Vi s ual C+6. 0实验内容：1 .问题描述以单链表为存储结构实现以下基本操作：(1) 在第i个元素前插入一个新元素。(2) 查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提醒信息。(3) 删除第i个元素，若成功，给出提醒信息并显示被删元素的值；不成功 给出失败的提醒信息。2 .数据结构类型定义 typedef st r uct Li n kNod e dint V a 1 u e ;os t ruct LinkNo d e * Next;Node, *Li n kL i st;.模块划分(1)初始化链表:v oid I nitList (L i nk L ist * L);(2)创建链表:尾插法:in t Cr e a teF r o mTail (LinkL i st L)；(3)在指定位置插入元素：int I n s L ist ( L in k List L , i n t i, i n t e )；(4 )在指定位置删除元素：i n t DelLis t (LinkLi st L, int i, int *e); 返回值说明：返回ERROR插入失败，返回OK插入成功；(5)按位置查找链表元素：in t GetList(L i nkList L, int i, int * e);.具体设计void init_ 1 ink 1 i s t ( L i nkLi s t *1)/*对单链表进行初始化*/(L i nkList) ma lloc (si zeo f (Node) ) ；/*申请结点空间*/式* 1 )->nex t =NULL;/ *置为空表*/ void Crea teF r omH ead (Lin k List L) (N ode *s;«>char c;int f 1 a g= 1 ;while(flag) /*flag初值为1,当输入$时，置f lag为0,建表结束*/c= g et c h a r ();。if(c!='$')°3 s = (N ode * ) m a 1 loc ( s i zeo f (No d e) )； /* 建立新结点 s*/ 8S->d a ta=c；。s > n ext=L->next； /*将 s 结点插入表头*/。 一>n e x t=s ;oelseflag=0;)v oid C r eateFromTa i 1 (LinkL i s t L )(Node * r, * s ;0ch a r c ;1 n t flag = 1; /*设立一个标志，初值为1,当输入$ 时，flag为 0,建表结束*/。r=L ;/* r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/w h il e ( f lag)/*循环输入表中元素值，将建立新结点s插入表尾*/。c=getc h ar ()；。i f (c!='$')oo 。 s= (N ode*) ma Hoc ( s i zeof (N o de); s->data= c ;。r->next= s ;。r=s；0e 1 segfla g =0;3 r>ne x t=N ULL;/*将最后一个结点的n e x t链域置为空，表达链表的结束*/。)Nod e * Ge t (Li n k L i st L, i nt i )/*在带头结点的单链表L中查找第i个结点，若找到(1 WiWn),则返回该结 点的存储位置；否则返回NULL*/(int j;N ode * p ;°P=L;° j =0；/*从头结点开始扫描* /while (p->n e xt! = NULL)&& ( j< i )(wp=p->ne x t; /大扫描下一结点 */gj + +;/*己扫描结点计数器*/)i f(i = j)«oret u rn p; /*找到了第i个结点*/ ®el s er e tur n NULL; /* 找不到，iWO 或 i>n */No d e *Loc a te( Li n kList L, Ele mType k ey)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结 点的位置P,否则返回NULL*/ (No d e *p;P=L-> n e xt； /*从表中第一个结点开始*/ owhil e (p!=NULL)if (p-> data ! =key) 叩=p >next;e 1 s e。obr e a k；/*找到结点值=key时退出循环*/retur n p；)in t I n s L is t (LinkLi s t L, i n t i, ElemType e) /*在带头结点的单链表L中第i个位置插入值为e的新结点s */ (N ode * p re, *s;int k;pre=L;k = 0 ;/*从头开始，查找第i l个结点*/wh i le(pr e !=NULL&&kV i -1)/*表未查完且未查到第i-l个时反复，找到pr e指向第i-1个*/。*pre= p r e->ne x t;ok = k+l;。/*查找第i-1结点*/oi f(! pre)/*如当前位置P r e为空表已找完尚未数到第i个，说明插入位置不合理*/。p r intf (插入位置不合理！ )；。re t urn ERROR；»s= ( N ode*) mall o c (s i z e of (Nod e ) ；/ *申请一个新的结点 S */®s-> d a t a=e；/*值e置入s的数据域* /as > n e x t = pre-> n ext/*修改指针，完毕插入操作*/pr e >next = s;ore t u r n 0 K;)i n t D e 1 L ist (Lin k L i s t L, int i , ElemType * e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量* e中*/(Node * p re, * r ;«»int k;op r e=L;k=0;while( p re->next!=NULL && k< i - 1)/*寻找被删除结点i的前驱结点i -1使p指向它* /(pre=pre > next；ok = k + 1 ；。 gg"*查找第i -1个结点*/0 i f (! (pre-> next)/* 即 while 循环是由于 p->ne x t = NULL 或 i<I而跳出的，而是由于没有找到合法的前驱位置，说明删除位置i不合法。*/。-print f (删除结点的位置i不合理！ )；return ERR 0 R;r= p re-> next;叩 r e->next= p re->n e xt->nex t ；/ *修改指针，删除结点 r*/*e = r->dat a ;r e e (r) ;/*释放被删除的结点所占的内存空间*/oprintf （成功删除结点!”）;re t u rn OK;intListLe n gth(LinkList L)/*求带头结点的单链表L的长度*/(Nod e * p ；ftint j;®p=L-> next;j = 0；/*用来存放单链表的长度*/h i 1 e(p!=NULL)。叩二 p >next;gj+；Jreturn j；。/ *j为求得的单链表长度*/ 5.测试数据及结果* S JL先后入查找3、册！除。、否找3、删除。、<<endlWi H作怦一 W1 的泊 入入，作谟当痣2源雪。请.A.插3 - .中 « I警6肝 BF选吉4前入一串单字行数据.；G?BV x当前转性表为:%金叁蚩的蜂作:1、以T吉束！插入2、查找3、删除。、退出摹的 理18荤 塾F的 入入线餐 鬻5诜 语雪。语的在岁杳甥9的 £8 翼您 拿治军 >二 64 1时5选H 文坛3、册”除。、：艮中退出退出O 1" C:Win d owsSy$te m 32D ebu gC ppl.exe"请输入一串单字符数据，以M结束！56789*当前线性表为：5 6 7 8 9请选择您要的操作：1、插入2、查找3、删除0、退出3道蒯A簿要删除的数据的位置：7雪前嶷表为：5 6 7 8 9请选择您要的操作：工、插入2、查找3、删除0、退出金帮勰鹦除的数据的位置：17 8 9请选择您要的操作：1、插入2、查找3、删除。、退出实验总结：在调试的时候发现在头插法的时候出现错误，通过逻辑思考与调试，发现错误 所在，并且更改。
