数据结构实验2链表的基本操作

《数据结构》实验报告院系光电信息科学系专业电子信息工程姓名潘成瑶学号2012级2班2014一、实验题目链表的根本操作二、需求分析编写链表根本操作函数。①初始化链表InitList(LIST*L,intms)②向链表指定位置插入元素InsertList1(LIST*L,intitem,intrc)③向有序链表指定位置插入元素InsertList2(LIST*L,intitem,intrc)④删除指定元素之的链表记录DeleteList(LIST*L,intitem)⑤查找链表中的元素FindList(LIST*L,intitem)⑥输出链表元素OutputList(LIST*L)调用上述函数实现以下操作，操作步骤如下：①初始化链表 ②调用插入函数建立一个链表③在链表中寻找指定的元素④在链表中删除指定值的元素⑤遍历并输出链表三、概要设计为了实现上述程序功能，需要定义一个简化的单链表抽象数据类型：ADTLinearList{数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}结构关系：R={<ai,ai+1>|ai,ai+1∈D}根本操作：OutputLis(LinkListL)操作前提：L是一个未初始化的链表InitLinkList(L，n)操作前提：L是一个未初始化的单链表操作结果：将L初始化为一个空的单链表InertList(L,pos,e)操作前提：单链表L已存在操作结果：将元素e插入到单链表L的pos位置DeleteLinkList(L,pos,e)操作前提：单链表L已存在操作结果：将单链表L中pos位置的元素删除，删除的元素值通过e返回findList(L,e)操作前提：单链表L已存在操作结果：在单链表L中查找元素e，假设存在，返回元素在表中的序号位置；假设不存在，返回-1}本程序包含6个函数：主函数main()初始化单链表函数IniList()显示单链表内容函数outputList()插入元素函数InsertList()删除元素函数DeeteList()查找元素函数findList()主函数的伪码main(){说明一个单链表L；初始化L；建立L；显示L；循环做下面处理，直到读入的选项是“退出”：{清屏；显示菜单；读入选项；根据具体选项，读入需要的数据，调用相应的函数进行处理，然后对得到的结果做必要的后处理，如打印输出。}}详细设计采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义如下：类型定义typedefintElemType;typedefstructnode{ElemTypedata;structnode*next;}Node,*LinkList;根本操作的伪码算法为了方便，在单链表中设头结点，其data域没有意义。初始化voidInitList(LinkList*L){*L=申请新结点;如果申请失败，返回失败标志；(L)->next=NULL;返回成功标志；/*L是已经初始化好的空链表的头指针，通过键盘输入元素值，利用尾插法建单链表L*/q=L;打印输入提示：“请输入假设干个正整数〔用空格分隔〕，并用-1结束：”读入一个数x;当x不是结束标志时，循环做如下处理：{申请一个新结点p；如果申请失败，返回失败标志；将x送到p的data域;q->next=p;q=p读入下一个数x;}q->next=NULL;返回成功标志；}显示单链表voidoutputList(LinkListL){p=首元素结点地址; while(p不空){打印结点p的元素值；p=下一个结点地址;}}插入操作boolInertList(LinkListL,intpos,inte)/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/{从“头”开始，查找第i-1个结点pre;if(查找失败){显示参数错误信息;returnERROR;}else{申请一个新的结点s;将e放入s的数据域;将s插到pre后面;returnOK;}}删除操作boolDeLeteist(LinkListL,intitem){//在带头结点的单链表L中，删除第pos个元素，并由e返回其值LinkListp=L,q;intj=0;while(p->next&&j<item-1){//寻找第item个结点,令p指向其前趋 p=p->next;++j;}//if(!(p->next)||j>item-1) returnerror;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点OutputLis(L);}//ListDelete_L查找操作intfindList(LinkListL,inte){ intj=1;LinkListp;p=L->next;while(j<item){ p=p->next;j++;}printf("%d\n",p->data);}五、调试分析1.在调试过程中总会遇到缺了逗号或者双引号的情况，所以我们得尽量减少这些低级错误的概率。2.而且在调试的过程中，由于output函数没有在其他程序之前先定义，到后面就无法把查入和删除的链表输出。所以要在定义其他函数之前先把输出链表的函数先定义好。3.在main中函数调用经常会把调用的函数打错，而无法调用自定义函数。使用说明程序执行过程如下：提示用户输入插入的位置和数；用户按要求输入插入的位置和数屏幕显示插入数后的链表；提示用户输入指定删除的位置；用户按要求输入删除的位置；屏幕显示删除后的链表；提示用户输入寻找的数；用户按要求输入寻找的数；屏幕显示该数的位置；测试结果1.向链表指定位置插入元素2.在链表中查找指定的元素3.在链表中删除指定值的元素9．附录#include<stdio.h>#include<malloc.h>typedefstructlist{intdata;structlist*next;}LIST;voidInitList(LIST**p){//初始化链表*p=NULL;}voidInsertList1(LIST**p,intrc,intitem){//向链表指定位置【rc】插入元素【item】inti;LIST*u,*q,*r;//u为新结点，q插入点前驱，r为插入点后继u=(LIST*)malloc(sizeof(LIST));u->data=item;for(i=0,r=*p;i<rc&&r!=NULL;i++)//i!=rc{q=r;r=r->next;}if(r==*p)//p==NULL//插入首结点或p为空指针*p=u;elseq->next=u;u->next=r;}voidInsertList2(LIST**p,intitem)//向有序链表【p】插入键值为【item】的结点{LIST*u,*q,*r;//u为新结点，q插入点前驱，r为插入点后继u=(LIST*)malloc(sizeof(LIST));u->data=item;//p!=NULLfor(r=*p;r!=NULL&&r->data<item;q=r,r=r->next);//从链表首结点开始顺序查找//插入首结点或p为空指针if(r==*p)*p=u;//r->next=u;elseq->next=u;u->next=r;}intDeleteList(LIST**p,intitem)////删除键值为【item】的链表结点，返回0为删除成功，1为没找到{LIST*q,*r;//q为结点前驱，r为结点后继q=*p;if(q==NULL)//链表为空return1;if(q->data==item)//要删除链表首结点{*p=q->next;//p=q->link更改链表首结点指针free(q);//释放被删除结点的空间return0;//删除头结点成功}for(;q->data!=item&&q->next!=NULL;r=q,q=q->next);//q!=NULL&&p//寻找键值为【item】的结点//r为结点，q为结点后继if(q->data==item)//找到结点{r->next=q->next;//被删结点从链表中脱离free(q);//释放被删除结点的空间return0;//删除成功}return1;//没有指定值的结点，删除失败}intFindList(LIST*p,intitem){//查找键值【item】的链表结点位置，返回≥1为找到，-1为未找到inti;for(i=1;p->data!=item&&p!=NULL;p=p->next,i++);//查找键值【item】的链表结点return(p==NULL)?-1:i;//找到返回【i】}voidOutputList(LIST*p){//输出链表结点的键值while(p!=NULL){printf("%4d",p->data);p=p->next;}}voidFreeList(LIST**p){//释放链表空间LIST*q,*r;for(q=*p;q!=NULL;){r=q;//q=*pq=q->next;free(r);}*p=NULL;//将链表首结点指针置空}voidmain(){LIST*p;intop,i,rc;InitList(&p);while(1){printf("\n请选择操作1：指定位置追加2：升序追加3：查找结点\n");printf("4、删除结点5：输出结点6、清空链表0：退出\n");fflush(stdin);scanf("%d",&op);switch(op){case0:return;case1:printf("\n请输入新增结点位置和键值：");scanf("%d%d",&rc,&i);InsertList1(&p,rc,i);break;case2:printf("\n请输入新增结点键值：");scanf("%d",&i);InsertList2(&p,i);break;case3:printf("\n请输入要查找结点的键值：");scanf("%d",&i);rc=FindList(p,i);if(rc>0)printf("位置为【%d】\n",rc);elseprintf("没找到！");break;case4:printf("\n请输入要删除结点的键值：");scanf("%d",&i)