资源描述：
《线性表的建立.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、线性表的建立、插入和删除班级：计科021姓名：罗晶晶学号：日期：2005/4/25实验题目：1、建立一个顺序存储的线性表，实现线性表的插入、删除操作2、建立一个单链表，实现单链表的插入、删除操作一、运行环境：visualC++二、需求分析1．程序的功能：（1）建立一个按关键字有序的线性表，从键盘上输入一个数，将该数插入到表中，使该线性表插入数据后仍按关键字有序。（2）建立一个线性表，从键盘上输入一个数，查找表中是否存在该数，若有则删除所有与该数相等的数。2．测试数据：l顺序存储的线性表：已建立一个有序的线性表为：１ ３
2、 ３ ４ ９ 请输入要插入的数据：８插入数据后的顺序表为：１ ３ ３ ４ ８ ９请输入要删除的数据：３删除后的顺序表为：１ ４ ８ ９l单链表：请输入记录，输入0则结束：120现在链表中的2个记录是：12请输入要插入的记录：1现在链表中的3个记录是：1120请输入要删除的数据：1删除了：1现在链表中的2个记录是：12三、概要设计1．顺序表的抽象数据类型的定义：ADTList{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{<
4、ai-1,ai>
5、ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),称i为ai在线性表中的位序。}基本操作：InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。GetElem(L,i,&e)初始条件：线性表L已
6、存在，且1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，e为给定值，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。ListTraverse(L,visit())初始条件：线性表L已存在，Visit()为某个访问函数。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ListInsert(&L,
7、i,e)初始条件：线性表L已存在，且1≤i≤LengthList(L)+1。操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList一、详细设计1．采用c语言定义相关的数据类型；#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ int*elem; intleng
8、th; intlistsize;}SQLIST;2．其中部分操作的伪码算法如下：voidCreate(SQLIST&L)//建立线性表{ L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!L.elem)printf("为线性表分配空间失败!"); L.length=0; L.listsize=LIST_INIT_SIZE;}voidInsert(SQLIST&A,intx)//实现有序的插入操作{ if(A.length==A.listsize)prin
9、tf("线性表错误!");if(x>A.elem[A.length-1])A.elem[A.length]=x;else{inti=0;while(x>=A.elem[i])i++;for(intj=A.length;j>=i;j--)A.elem[j+1]=A.elem[j];A.elem[i]=x;}A.length++;}voidlistdelete(SQLIST&L,intx)//实现有序的删除操作{inti=0;if(L.length==0)cout<<"ERROR"<10、gth){if(L.elem[i]==x){for(intj=i+1;j<=L.length-1;++j)L.elem[j-1]=L.elem[j];L.length--;}elsei++;}3、#include#includetypedefstructstudent//单链表的存储结构{lo
