资源描述：
《数据结构上机报告：编写一个程序,实现单链表的各种基本运算.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
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；（1
2、2）释放单链表。3.概要设计（1）为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：ADTLinearList{数据对象：D={ai
3、ai∈IntegerSet,i=0,1,2,…,n,n≥0}结构关系：R={
4、ai,ai+1∈D}基本操作：InitList_L(L)操作前提：L是一个未初始化的线性表操作结果：将L初始化为一个空的线性表CreateList_L(L)操作前提：L是一个已初始化的空表操作结果：建立一个非空的线性表LListInsert_L(L,pos,e)操作前提：线性表L已存在操作结果：将元素e插入到线性表L的po
5、s位置ListDelete_L(L,pos,e)操作前提：线性表L已存在操作结果：将线性表L中pos位置的元素删除，删除的元素值通过e返回LocateList_L(L,e)操作前提：线性表L已存在操作结果：在线性表L中查找元素e，若存在，返回元素在表中的序号位置；若不存在，返回-1DestroyList_L(&L)初始条件：线性表L已存在操作结果：销毁线性表ListEmpty_L(L)初始条件：线性表已存在操作结果：若L为空表，则返回ERROR，否则返回FALSEListLength_L(L)初始条件：线性表L已存在操作结果：返回L中数据元素个数GetEle
6、m_L(L,I,&e)初始条件：线性表L已存在操作结果：用e返回L中第i个数据元素值}（1）本程序包含10个函数：主函数main()初始化单链表函数InitList_L()显示单链表内容函数DispList_L()插入元素函数ListInsert_L()删除元素函数ListDelete_L()查找元素函数LocateList_L()创建链表函数CreateList_L()链表元素长度函数ListLength_L()判断链表是否为空函数ListEmpty_L()取值函数GetElem_L()各函数间调用关系如下：mainInitListDispListCrea
7、teListListLengthListEmptyDestroyListGetElemListInsertListDeleteLocateElem(3)主函数的伪码main(){说明一个单链表L；初始化L；建立L；显示L；}1.详细设计采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义如下：（1）类型定义typedefintElemType;typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;（1）基本操作的伪码算法l初始化BoolIni
8、tLinkList(LinkList*L){*L=申请新结点;如果申请失败，返回失败标志；(*L)->next=NULL;返回成功标志；}l建立单链表BoolCrtLinkList(LinkListL)/*L是已经初始化好的空链表的头指针，通过键盘输入元素值，利用尾插法建单链表L*/{rear=L;打印输入提示：“请输入若干个正整数（用空格分隔），并用-1结束：”读入一个数x;当x不是结束标志时，循环做如下处理：{申请一个新结点s；如果申请失败，返回失败标志；将x送到s的data域;rear->next=s;rear=s;读入下一个数x;}rear->nex
9、t=NULL;返回成功标志；}l显示单链表（输出）voidDispLinkList(LinkListL){p=首元素结点地址;while(p不空){打印结点p的元素值；p=下一个结点地址;}}l插入操作boolInsLinkList(LinkListL,intpos,ElemTypee)/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/{从“头”开始，查找第i-1个结点pre;if(查找失败){显示参数错误信息;returnERROR;}else{申请一个新的结点s;将e放入s的数据域;将s插到pre后面;returnOK;}}l删除操作boo
10、lDelLinkList(LinkListL,int
