线表的顺序存储结构和实现 (2).doc

石家庄经济学院实 验 报 告学 院: 专 业: 计算机 班 级: 学 号: 姓 名: 信息工程学院计算机实验中心制实验题目：线性表的顺序存储结构和实现实验室： 机房4 设备编号： 10 完成日期： 2012年03月25号 一、实验内容1.熟悉C 语言的上机环境，掌握C 语言的基本结构。2.会定义线性表的顺序存储结构。3.熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。二、实验目的掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基本算法。三、实验的内容及完成情况1. 需求分析(1)线性表的抽象数据类型ADT的描述及实现。本实验实现使用Visual c+6.0实现线性表顺序存储结构的表示及操作。具体实现要求：(2)完成对线性表顺序存储结构的表示和实现。(3)实现对线性表的建立和初始化。(4)实现对线性表插入和删除部分元素。2概要设计抽象数据类型线性表的定义： ADT LIST抽象对象：D=ai|ai=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#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;c2-1.h#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef structElemType *elem;int length;int listsize;Sqlist;B02-1.hStatus InitList_Sq(Sqlist &L)L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;Status Listlength(Sqlist L)return L.length;Status GetElem(Sqlist L,int i,ElemType &e)if(iL.length)return ERROR;e=L.elemi-1;return OK;Status ListInsert_Sq(Sqlist &L,int i,ElemType e)ElemType *newbase,*p,*q;if(iL.length+1)return ERROR;if(L.length=L.listsize)newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;Status ListDelete_Sq(Sqlist &L,int i,ElemType &e)ElemType *p,*q;if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;（2）主函数的伪码算法C4.h#includec1.h#includec2-1.h#includeb02-1.hvoid main()Sqlist la;ElemType ea;InitList_Sq(la);ListInsert_Sq(la,2,88);ListInsert_Sq(la,3,90);ListDelete_Sq(la,5,ea);printf(%d,ea);4. 调试分析语法错误比较多 5用户使用说明打开可执行程序，即Visual c+6.0环境下，参照用户选择界面提示即可使用本程序6测试结果 程序具体执行如下：7附录 源程序如下：1C1.h的源程序#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int status;2c2_1的源程序#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef int ElemType;typedef struct ElemType *elem; int length; int listsize;SqList;3b021.hstatus InitList_Sq(SqList &L)L.elem = (ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType);if (! L.elem)exit(OVERFLOW);L.length = 0;L.listsize = LIST_INIT_SIZE;return OK;status ListLength(L)RETURN L.length;status GetElem(SqList L,int i,ElemType &e)if(iL.length)return ERROR;e=L.elemi-1;return OK;status ListInsert_Sq(Sqlist &L,int i,ElemType &e)ElemType *newbase,*p,*q;if(iL.length+1)return ERROR; if(L.Length=L.Listsize)newbase=(ElenType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(EiemType);if(!newbase)exit(OVERFLOW);L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;status ListDelet_Sq(SqList &L,int i,ElemType &e)ElemType,*p,*q;if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;main2-1.h:#includec1.h#includec2-1.h#inclu