《数据结构上机报告：编写一个程序,实现单链表的各种基本运算》由会员分享，可在线阅读，更多相关《数据结构上机报告：编写一个程序,实现单链表的各种基本运算（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构上机报告2011年3月9日1. 姓名学号同组成员无实验题目及要求2. 编写一个程序，实现单链表的各种基本运算需求分析建立一个单链表，实现单链表的初始化，插入、删除节点等功能，以及确定某一元素在单链表中的位置。（1）初始化单链表；（2）依次采用尾插入法插入a,b,c,d,e元素；（3）输出单链表L；（4）输出单链表L的长度；（5）判断单链表L是否为空；（6）输出单链表L的第三个元素；（7）输出元素a的位置；（8）在第4个元素位置上插入f元素；（9）输出单链表L；（10）删除L的第3个元素；（11）输出单链表L；（12）释放单链表。3. 概要设计（1）为了实现上述程序功能，需要定义一个简化
2、的线性表抽象数据类型:ADTLinearList数据对象：D=ai|aIntegerSet,i=0,1,2,n,n0结构关系：R=|a,ai+1D基本操作：InitList_L（L）操作前提：L是一个未初始化的线性表操作结果：将L初始化为一个空的线性表操作前提：L是一个已初始化的空表操作结果：建立一个非空的线性表LListInsert_L(L,pos,e)操作前提：线性表L已存在操作结果：将元素e插入到线性表L的pos位置ListDelete_L(L,pos,e)操作前提：线性表L已存在操作结果：将线性表L中pos位置的元素删除，删除的元素值通过e返回LocateList_L(L,e)操作前提
3、：线性表L已存在操作结果：在线性表L中查找元素e，若存在，返回元素在表中的序号位置；若不存在，返回-1DestroyList_L(&L)初始条件：线性表L已存在操作结果：销毁线性表ListEmpty_L(L)初始条件：线性表已存在FALSE操作结果：若L为空表，则返回ERROR，否则返回ListLength_L(L)初始条件：线性表L已存在操作结果：返回L中数据元素个数GetElem_L(L,I,&e)初始条件：线性表L已存在操作结果：用e返回L中第i个数据元素值2)本程序包含10个函数：主函数main()初始化单链表函数InitList_L()显示单链表内容函数DispList_L()插入元
4、素函数ListInsert_L()删除元素函数ListDelete_L()查找元素函数LocateList_L()创建链表函数CreateList_L()链表元素长度函数ListLength_L()main判断链表是否为空函数ListEmpty_L()取值函数GetElem_L()各函数间调用关系如下:InitListDispListCreateListListLengthListEmptyDestroyListGetElemListInsertListDeleteLocateElem(3)主函数的伪码main()说明一个单链表L；初始化L；建立L；显示L；详细设计采用单链表实现概要设计中定义
5、的抽象数据类型，有关的数据类型和伪码算法定义如下：(1)类型定义typedefintElemType;typedefstructLNodeElemTypedata;/数据域structLNode*next;/指针域LNode,*LinkList;2)基本操作的伪码算法初始化BoolInitLinkList(LinkList*L)*L=申请新结点;如果申请失败，返回失败标志；(*L)-next=NULL;返回成功标志；建立单链表BoolCrtLinkList(LinkListL)/*L是已经初始化好的空链表的头指针，通过键盘输入元素值，利用尾插法建单链表L*/rear=L;打印输入提示：“请输入
6、若干个正整数(用空格分隔)，并用-1结束：读入一个数x;当x不是结束标志时，循环做如下处理：申请一个新结点s；如果申请失败，返回失败标志；将x送到s的data域;rear-next=s;rear=s;读入下一个数x;rear-next=NULL;返回成功标志；显示单链表(输出)voidDispLinkList(LinkListL)卩=首元素结点地址；while(p不空)打印结点p的元素值；卩=下一个结点地址；插入操作boolInsLinkList(LinkListL,intpos,ElemTypee)/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/从“头”开始，查找第i-1个结
7、点pre;if(查找失败)显示参数错误信息;returnERROR;else申请一个新的结点s;将e放入s的数据域;将s插到pre后面;returnOK;删除操作boolDelLinkList(LinkListL,intpos,ElemType*e)*e中*/*在带头结点的单链表L中删除第pos个元素，并将删除的元素保存到变量查找待删除结点i的前驱结点，并用pre指向它;if(查找失败)显示参数错误信息;returnERROR;elser=pre-next;修改指针，删除结点r;释放被删除的结点所占的内存空间;returnOK;查找操作intLocLinkList(LinkListL,Elem
8、Typee)/*在带头结点的单链表L中查找其结点值等于e的结点，若找到则返回该结点的序号位置k,否则返回-1*/p=首元素结点地址4. if（p-data!=e）p=p-next;k+;elsebreak;if（p不空）returnk;elsereturn-1;调试分析开始运行时会出现DebugError,DAMAGE:AfterNormalblock,搜索后了解到是内存越界操作，检查后发现内存分配L和S=(LinkList)malloc(sizeof(LNode)写成了=(LinkList)malloc(sizeof(LinkList)，修改后正常。5. 使用说明6. 程序执行后，界面直接输
9、出要求的结果测试结果C*D:C01PUTERSCIEHCEffiSKB5675TDebug5675T.eze初始化单犍拠依次米用尾插法插入已,b,c,d,e兀素心输出尊链表L：abcde里链裹L疝慰J：5知单链表L的第三个元素为：c里链表L中刊的铮为：1吞第4个元素位畫E插入f元素冏输出单链夷L：abcfde0删陈L歯第3个元素1输出单链表L：abfdeR昭挥放单链表LPressanykeytocontinue头节点数据域为空/尾插法建表附件#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineNULL0t
10、ypedefintStatus;typedefintElemType;typedefstructLNodeElemTypedata;structLNode*next;LNode,*LinkList;StatusInitList_L(LinkList&L)/初始化线性表L=(LinkList)malloc(sizeof(LNode);/L指向头节点，L-next=NULL;returnOK;/InitList_LStatusDispList_L(LinkList&L)/输出线性表LinkListp=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;r
11、eturnOK;/DispList_LStatusCreateList_L(LinkList&L,ElemTypea,intn)LinkLists,r;inti;L=(LinkList)malloc(sizeof(LNode);r=L;for(i=0;idata=ai;r-next=s;r=s;r-next=NULL;returnOK;/CreateList_LStatusListLength_L(LinkListL)LinkListp=L;intn=0;while(p-next!=NULL)n+;p=p-next;return(n);/ListLength_L/求线性表的长度StatusLi
12、stEmpty_L(LinkListL)return(L-next=NULL);/ListEmpty_L/判断单链表是否为空StatusDestroyList_L(LinkList&L)LinkListp=L,q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);returnOK;/DestroyList_L/销毁线性表StatusGetElem_L(LinkListL,inti,ElemType&e)/L为带头节点的单链表的头指针。/当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORintj=0;LinkListp=L;while(
13、jnext;if(p=NULL)returnERROR;elsee=p-data;returnOK;/GetElem_LStatusListInsert_L(LinkList&L,inti,ElemTypee)/插入数据元素intj=0;LinkListp=L,s;/*找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素*/while(jnext;if(p=NULL)returnERROR;elses=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;returnOK;/List
14、Insret_LStatusListDelete_L(LinkList&L,inti,ElemType&e)/删除数据元素intj=0;LinkListp=L,q;while(jnext;if(p=NULL)returnERROR;elseq=p-next;/q为要删除的元素节点if(q=NULL)returnERROR;e=q-data;/e为删除节点的数据区域p-next=q-next;free(q);returnOK;/ListDelete_LintLocateElem_L(LinkListL,ElemTypee)/按元素值查找元素LinkListp=L-next;inti=1;while(p!=NULL&p-data!=e)p=p-next;i+;/如果要插入的节点为头节点，则退出if(p=NULL)returnERROR;elsereturn(i);/LocateElem_Lintmain()ElemTypee,a5=a,b,c,d,e;LinkListL;printf(1)初始化单链表Ln);InitList_L(L);/初
