线性表的链式存储结构和实现

《线性表的链式存储结构和实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、石家庄经济学院实验报告学院:专业:计算机班级:学号:姓名:信息工程学院计算机实验中心制实验题目：线性表的链式存储结构和实现实验室：机房4设备编号：09完成日期：2012.04.09一、实验内容1.会定义线性表的链式存储结构。2.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。二、实验目的掌握链式存储结构的特点，掌握并实现单链表的常用的基本算法。三、实验的内容及完成情况1.需求分析(1)线性表的抽象数据类型ADT的描述及实现。本实验实现使用Visualc++6.0实现线性表链式存储结构的表示及操作。具体实现要求：(2)完成对线性表链式存储结构

2、的表示和实现。(3)实现对单链表的创建。(4)实现对单链表的插入和删除操作。2．概要设计抽象数据类型线性表的定义：ADTLIST{抽象对象：D=｛ai

3、ai<-Elemset,i=1,2,…,n,n>=0｝数据关系：R1=｛

4、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)初始条件：线性表L已存在。操作结果：

5、若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的数据元素，且不是最后一个，则用pre_e返回它的后继，否则操作失败，pre_e无定义。ListInsert(&L,I,e)初始条件：线性表L已存在，1<=i<=ListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,I,&e)初始条件：线性表L已存在且非空，1<=i<=ListLength

6、(L)。操作结果：删除L中第i个数据元素，并用e返回其值，L的长度减1。ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数visit()。一旦visit（）失败，则操作失败。｝ADTList3．详细设计（1）抽象数据类型线性表链式存储结构的表示和实现c1.h:#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2ty

7、pedefintStatus;c2.h:typedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*Linklist;;b02-1.h:intCreatelist_L(Linklist&L,intn){Linklistp;inti;L=(Linklist)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(Linklist)malloc(sizeof(LNode));scanf("%d",&p->data);p

8、->next=L->next;L->next=p;}returnOK;}StatusGetElem_L(LinklistL,inti,ElemType&e){Linklistp;intj;p=L->next;j=1;while(p&&jnext;++j;}if(!p

9、

10、j>i)returnERROR;e=p->data;returnOK;}StatusListInsert_L(Linklist&L,inti,ElemTypee){Linklistp,s;intj;p=L;j=0;while(p&&jnext;++j;}

11、if(!p

12、

13、j>i-1)returnERROR;s