实验报告
实验类型__综合设计__实验室_软件实验室三__一、实验题目
线性表的基本操作
二、实验目的和要求
1)掌握线性表的特点
2)掌握线性表的顺序存储结构和链式存储结构的基本运算及应用。
3)尽可能考虑算法的健壮性
4)实验报告中要写出测试数据、错误分析以及收获。
三、需求分析
本演示程序用c++6.0编写，完成单链表和顺序表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
1、输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数
2、输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值，查找操作后显示要查找元素的位置
3、程序所能达到的功能：完成能完成两种存储结构的基本运算以及二级菜单的运用
4、测试数据
1)输入2，建立一个链表
2)插入操作中依次输入11,22,33,44,55，生成一个单链表
3)查找操作中依次输入22,44，返回这,2个元素在单链表中的位置
4)删除操作中依次输入3，删除位于3的元素
5)输入1，建立一个顺序表，再做类似上述数据测试
四、概要设计
为了实现上述程序功能，需要定义
1、单链表的抽象类型如下：
ADT LinkList {
数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
数据关系：R={|ai,ai+1 ∈D}
基本操作：
CreateList_L1(&L)
操作结果：构造一个空的单链表L.
ListInsert_L1(&L,i,e)
初始条件：单链表L已存在
操作结果：将元素e插入到单链表L的第i位置前
ListInsert_L2(&L,i,e)
初始条件：单链表L已存在
操作结果：将元素e插入到单链表L的第i位置后
ListDelte_L(&L,i)
初始条件：单链表L已存在
操作结果：将单链表L中i位置的元素删除
GetElem_L(L,i)
初始条件：单链表L依存在
操作结果：单链表L中查找第i个元素并返回其元素
length_l(&L)
初始条件：单链表L已存在
操作结果：将单链表L的长度值返回
}
2、顺序表的抽象数据类型
ADT list {
数据对象：D={ai|ai∈Elem Set,i=0,1,2,…,n,n≥0}
数据关系：R={|ai,ai+1 ∈D}
基本操作：
Initlist_Sq (&L)
操作结果：构造一个空的顺序表L.
ListInsert_Sq (&L,i,e)
初始条件：顺序表L已存在
操作结果：将元素e插入到顺序表L的第i位置
ListDelete_Sq (&L,i，&e)
初始条件：顺序表L已存在
操作结果：将顺序表L中i位置的元素删除，元素值置入e中返回 locate_Sq (L,e)
初始条件：顺序表L依存在
操作结果：顺序表L中查找元素e并返回其位置
}
3、本程序包含三个模块
1)主程序模块：
协调各函数的调用，实现所要求的功能;
2)顺序表模块：
实现线性表顺序存储后的基本操作；
3）单链表模块:
实现线性表链式存储后的基本操作。
4、各模块之间的调用关系如下：
主程序模块
顺序表模块单链表模块
五、详细设计
1、顺序表的元素类型
typedef struct
{int *elem;
int length;
int listsize;
}SqList;
2、顺序表的基本操作
int Initlist_Sq(SqList *L)
//构造一个新的线性表
//如果没有开辟成功返回错误
void ListInsert_Sq(SqList *L,int i,int e)
//在第i个位置插入元素e
void listshow_Sq(SqList *L)
//输出顺序表元素
int locate_Sq(SqList *L,int e)
//查找元素e，并返回其位置
int ListDelete_Sq(SqList *L,int i,int *e)
//删除第i个位置上的元素，并返回其元素
其中部分操作的伪码算法如下：
int ListDelete_Sq(SqList *L,int i,int *e)//删除第i个位置上的元素，并返回其元素
{int j;
if((i<1)||(i>L->length))
return ERROR;
*e=L->elem[i-1];
j=i-1;
while(jlength)
{L->elem[j]=L->elem[j+1];
j++;
}
L->length--;
}
3、单链表的元素类型，结点类型和指针类型
typedef struct LNode
{int date;
struct LNode *next;
}LNode,*LinkList;
4、单链表的基本操作
void CreateList_L1(LNode *l)
//初始化链表
int ListInsert_L1(LNode *l,int i,int e)
//第i个位置前插入
int ListInsert_L2(LNode *l,int i,int e)
//第i个位置后插入
int GetElem_L(LNode *l,int i)
//访问第i个元素
int ListDelte_L(LinkList l,int i)
//删除第i个元素
int length_l(LNode *l)
//求链表的长度
void show_l(LNode *l)
//输出链表
其中部分操作的伪码算法如下：
