2023年数据结构单链表实验报告

洛阳理工学院实验报告系别计算机系班级学号姓名课程名称数据结构实验日期11.7实验名称链表的基本操作成绩实验目的：熟悉掌握线性表链式存储结构，掌握与应用查找、插入、删除等基本操作算法，训练和提高结构化程序设计能力及程序调试能力。实验条件：计算机一台，VisualC++6.0实验内容：.问题描述以单链表为存储结构实现以下基本操作：在第i个元素前插入一个新元素。查找值为x的某个元素。若成功，给出x在表中的位置；不成功给出提醒信息。删除第i个元素，若成功，给出提醒信息并显示被删元素的值；不成功给出失败的提醒信息。.数据结构类型定义typedefstructLinkNodedintVa1ue;ostructLinkNode*Next;}Node,*LinkList;.模块划分(1)初始化链表:voidInitList(LinkList*L);(2)创建链表:尾插法:intCreateFromTail(LinkListL)；(3)在指定位置插入元素：intInsList(LinkListL,inti,inte)；(4)在指定位置删除元素：intDelList(LinkListL,inti,int*e);返回值说明：返回ERROR插入失败，返回OK插入成功；(5)按位置查找链表元素：intGetList(LinkListL,inti,int*e);.具体设计voidinit_1ink1ist(LinkList*1)/*对单链表进行初始化*/{(LinkList)malloc(sizeof(Node))；/*申请结点空间*/式*1)->next=NULL;/*置为空表*/}voidCreateFromHead(LinkListL)(Node*s;«>charc;intf1ag=1;while(flag)/*flag初值为1,当输入〃$〃时，置flag为0,建表结束*/c=getchar();。if(c!='$')°{3s=(Node*)ma1loc(sizeof(Node))；/*建立新结点s*/8S->data=c；。。。s—>next=L->next；/*将s结点插入表头*/［一>next=s;}oelseflag=0;))voidCreateFromTai1(LinkListL)(Node*r,*s;0charc;ntflag=1;/*设立一个标志，初值为1,当输入〃$〃时，flag为0,建表结束*/。r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag)/*循环输入表中元素值，将建立新结点s插入表尾*/。{^c=getchar()；。if(c!='$')oo{。s=(Node*)maHoc(sizeof(Node));s->data=c;。。r->next=s;。。r=s；0}e1seg{flag=0;3r—>next=NULL;/*将最后一个结点的next链域置为空，表达链表的结束*/。))}Node*Get(LinkListL,inti)/*在带头结点的单链表L中查找第i个结点，若找到(1WiWn),则返回该结点的存储位置；否则返回NULL*/(intj;Node*p;°P=L;°j=0；/*从头结点开始扫描*/while((p->next!=NULL)&&(j<i))(wp=p->next;/大扫描下一结点*/gj++;/*己扫描结点计数器*/)if(i==j)«oreturnp;/*找到了第i个结点*/®elsereturnNULL;/*找不到，iWO或i>n*/Node*Locate(LinkListL,ElemTypekey)/*在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置P,否则返回NULL*/(Node*p;P=L->next；/*从表中第一个结点开始*/owhile(p!=NULL)if(p->data!=key)叩=p—>next;e1se。obreak；/*找到结点值=key时退出循环*/returnp；)intInsList(LinkListL,inti,ElemTypee)/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/(Node*pre,*s;intk;pre=L;k=0;/*从〃头〃开始，查找第i—l个结点*/while(pre!=NULL&&kVi-1)/*表未查完且未查到第i-l个时反复，找到pre指向第i-1个*/。｛*pre=pre->next;ok=k+l;｝。。。/*查找第i-1结点*/oif(!pre)/*如当前位置Pre为空表已找完尚未数到第i个，说明插入位置不合理*/。printf(〃插入位置不合理！〃)；。returnERROR；»s=(Node*)malloc(sizeof(Node))；/*申请一个新的结点S*/®s->data=e；/*值e置入s的数据域*/as—>next=pre->next/*修改指针，完毕插入操作*/pre—>next=s;oreturn0K;)intDe1List(LinkListL,inti,ElemType*e)/*在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中*/(Node*pre,*r;«»intk;opre=L;k=0;while(pre->next!=NULL&&k<i-1)/*寻找被删除结点i的前驱结点i-1使p指向它*/(pre=pre—>next；ok=k+1；。｝gg"*查找第i-1个结点*/0if(!(pre->next))/*即while循环是由于p->next=NULL或i<I而跳出的，而是由于没有找到合法的前驱位置，说明删除位置i不合法。*/。｛-printf(〃删除结点的位置i不合理！〃)；^returnERR0R;r=pre->next;叩re->next=pre->next->next；/*修改指针，删除结点r*/*e=r->data;ree(r);/*释放被删除的结点所占的内存空间*/

oprintf（〃成功删除结点!”）;returnOK;}intListLength(LinkListL)/*求带头结点的单链表L的长度*/(Node*p；ftintj;®p=L->next;j=0；/*用来存放单链表的长度*/hi1e(p!=NULL){。叩二p—>next;gj++；Jreturnj；。/*j为求得的单链表长度*/}5.测试数据及结果*SJL先后入查找3、册！］除。、否找3、删除。、<<endlWiH作怦一W1的泊入入，作谟当痣2源雪。请.A.插3-*SJL先后入查找3、册！］除。、否找3、删除。、<<endlWiH作怦一W1的泊入入，作谟当痣2源雪。请.A.插3-.・中«I警6肝BF选吉4前入一串单字行数据.；G?BVx当前转性表为:%%金叁蚩的蜂作:1、以T吉束！插入2、查找3、删除。、退出摹的理18荤塾F的入入线餐鬻5诜语雪。语的在岁杳甥9的£8^翼您拿治军>二641时5选H文坛3、册”除。、：艮中退出退出请输入一串单字符数据，以M结束！56789*