资源描述:
《线性表的链式存储结构.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、石家庄经济学院实验报告学院:信息工程学院专业:计算机信息工程学院计算机实验中心制《数据结构》实验报告姓名张文楚学号409109070515日期2011.4.17-8节实验室计算机基础实验室指导教师张有华设备编号实验题目实验三线性表的链式存储结构一实验内容1.进一步熟悉C语言的上机环境,掌握C语言的基本结构。2.会定义线性表的链式存储结构。3.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。二实验目的掌握链式存储结构的特点,了解、掌握并实现单链表的常用的基本算法。三需求设计线性表抽象数据类型的描述及实现ADTList{数据对象:数据关系:基本操作:构造一个空的线性表LInitL
2、ist();销毁线性表LDestroyList();将L重置为空表ClearList();判断L是否为空ListEmpty();求表长ListLength();查找元素LocateElem();求前驱PriorElem();求后继NextElem();插入元素ListInsert();删除元素ListDelete();元素调用visit()函数ListTraverse(L,visit())}ADTList;程序具体实现要求:1.创建一个线性表2.能输出所有数据元素3.能求线性表长度4.能插入删除元素5.能查找元素6.能求元素的前驱和后继7.用户操作界面如下:******************
3、*****************1.构造线性表*2.插入元素*3.删除元素*4.查找元素*5.显示表长*6.求后继*7.求前驱*8.输出所有元素*0.结束程序运行***********************************请输入您的选择(0,1,...,8):四详细设计步骤1:给出线性表的抽象数据类型的定义。ADTList{数据对象:数据关系:基本操作:InitList(&L);操作结果:构造一个空的线性表L。DestroyList(&L)初始条件:线性表L已存在。操作结果:销毁线性表L。ClearList(&L)初始条件:线性表L已存在。操作结果:将L重置为空表。ListEmpt
4、y(L)初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE。ListLength(L)初始条件:线性表L已存在。操作结果:返回L中数据元素个数。GetElem(L,i,&e)初始条件:线性表L已存在,1≤i≤ListLength(L)。操作结果:用e返回L中第i数据个元素的值。LocateElem(L,e,compare())初始条件:线性表L已存在,compare()是数据元素判定函数。操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在,则返回值为0。PriorElem(L,cur_e,&pre_e)初始条件:线性表
5、L已存在。操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败,pre_e无定义NextElem(L,cur_e,&next_e)初始条件:线性表L已存在。操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,否则操作失败,next_e无定义。ListInsert(&L,i,e)初始条件:线性表L已存在,1≤i≤ListLength(L)+1。操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete(&L,i,&e)初始条件:线性表L已存在且非空,1≤i≤ListLength(L)。操作结果:删除
6、L的第i个数据元素,并用e返回其值,L的长度减1。ListTraverse(L,visit())初始条件:线性表L已存在。操作结果:依次对L的每个数据元素调用函数visit()。一旦visit()失败,则操作失败。}ADTList;步骤2:用C语言给出线性表的链式存储结构及相关操作的声明。//单链表的存储结构typedefstructLNode{ElemTypedata;//结点数据域structLNode*next;}LNode,*LinkList;基本操作的声明:StatusInitList_L(LinkList&L);StatusDestroyList_L(LinkList&L);S
7、tatusClearList_L(LinkList&L);intListEmpty_L(LinkListL);intListLength_L(LinkListL);StatusGetElem_L(LinkListL,inti,ElemType&e);intLocateElem_L(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)