線性表的链式存储结构和实现.docVIP

石家庄经济学院 实 验 报 告 学 院: 专 业: 计算机 班 级: 学 号: 姓 名: 信息工程学院计算机实验中心制 实验题目：线性表的链式存储结构和实现 实验室： 机房4 设备编号： 09 完成日期： 2012.04.09 一、实验内容 1.会定义线性表的链式存储结构。 2.熟悉对单链表的一些基本操作(建表、插入、删除等)和具体的函数定义。 二、实验目的 掌握链式存储结构的特点，掌握并实现单链表的常用的基本算法。 三、实验的内容及完成情况 1. 需求分析 (1)线性表的抽象数据类型ADT的描述及实现。 本实验实现使用Visual c++6.0实现线性表链式存储结构的表示及操作。具体实现要求： (2)完成对线性表链式存储结构的表示和实现。 (3)实现对单链表的创建。 (4)实现对单链表的插入和删除操作。 2．概要设计 抽象数据类型线性表的定义：ADT LIST{ 抽象对象：D=｛ai|ai-Elemset,i=1,2,…,n,n=0｝ 数据关系：R1=｛ai-1,ai-D,i=2,…,n｝ 基本操作： InitList(L) 操作结果：构造一个空的线性表L。 DestoryList(L) 初始条件：线性表L已存在。 操作结果：销毁线性表L CLearList(L) 初始条件：线性表L已存在。 操作结果：将L重置为空表。 ListEmpty(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) 初始条件：线性表L已存在。 操作结果：若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(L)。 操作结果：删除L中第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L,visit()) 初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit（）失败，则操作失败。 ｝ADT List 3．详细设计 （1）抽象数据类型线性表链式存储结构的表示和实现 c1.h: #includestdio.h #includestdlib.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; c2.h: typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode,*Linklist; ; b02-1.h: int Createlist_L(Linklist L,int n) { Linklist p; int i; L=(Linklist)malloc(sizeof(LNode)); L-next=NULL; for(i=n;i0;--i) { p=(Linklist)malloc(sizeof(LNode));