线性表的顺序存储结构实验报告例文.docx

线性表的顺序存储结构实验报告 南昌航空大学实验报告 课程名称：数据结构实验名称：实验一线性表的顺序存储结构 班级： XXX 学生姓名： XXX 学号： XXXXX 指导教师评定： XXX 签名: XXX 设计并实现以下算法：有两张非递增有序的线性表A，B，采用顺序存储结构，两张表合并用C表存，要求C仍为非递增有序的，并删除C表中值相同的多余元素 一、需求分析 ⒈本程序中，要求输入到表A,B中的元素是整形的，并且要按非递增顺序输入，否则系统会给出“出 错信息”输出结果应该是一个不含有重复元素的非递增的表 ⒉本程序以用户和计算机的对话方式执行，即在计算机演示界面上显示“提示信息”后，由用户在键 盘上输入相应的信息；相应的输入数据和运算结果显示在其后 ⒊程序执行的命令包括： （1）构造线性表A （2）构造线性表B （3）检验表A,B是否非递减有序（4）求表A与B的合并（5）删除表中值相同的多余元素（6）结束 4.测试数据 （1）A=1 2 3 （2）A=9 5 0 -2 B=10 5 0 -1 -3 -5 -10 二、概要设计 ⒈为实现上述算法，需要线性表的抽象数据类型： ADT Stack { 数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0} 数据关系：R1={|a i-1,a i∈D,i=2,…n} 基本操作: init(list *L) 操作结果：构造一个空的线性表L。

InputList(List *L) 初始条件：线性表L已经存在 操作结果：人工输入了一张表 CheckList(List *L) 初始条件：线性表L已经存在 操作结果：判断L是否非递增有序，若为否，则重新输入 MergeList(List *La,List *Lb,List *Lc) 初始条件：非递增线性表La，Lb已经存在 操作结果：合并La，Lb得到Lc，Lc仍按非递增有序排列 DeleteSame(List *L) 初始条件：非递增线性表L已经存在 操作结果：删除了L中值相同的元素 PrintList(List L) 初始条件：线性表L已经存在 操作结果：打印出表L }ADT List 2. 本程序有三个模块： ⑴主程序模块 void main(){ 初始化； do{ 接受命令； 显示结果； ｝while(执行完毕) ｝ ⑵线性表单元模块：实现线性表抽象数据类型； ⑶结点结构单元模块：定义线性表中的结点结构。

三、详细设计 ⒈元素类型，结点类型 typedef int ElemType; //元素类型 struct LIST{ ElemType *elem; int length; int listsize; }; typedef struct LIST list; //结点类型 2.对抽象数据类型中的部分基本操作的伪码算法如下： int init(List *L) { //初始化表L L→elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);//为线性表顺序结构分配空间 If(!L→elem) exit (ERROR); L→length=0; L→listsize= LIST_INIT_SIZE; Return OK; }//init List void InputList(List *L) { //构造表Ｌ int flag=-32768;//输入结束的标志 scanf("%d",&n); //输入元素 while(n!=flag) {//继续输入 L→elem[j++]=n; L→length=j; Scanf("%d",&n); } }//InputList void CheckList(List *L) { for (i=0;ielem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L->elem) exit(OVERFLOW);// 存储分配失败 L->length=0;//空表长度为0 L->listsize=LIST_INIT_SIZE;//初始存储容量 return OK; } void InputList(List *L) { int n,j=0; int flag=-32768;//输入结束标志 scanf("%d ",&n); while(n!=flag) { L->elem[j++]=n; L->length=j; scanf("%d ",&n); } } void CheckList(List *L) { int i; for(i=0;ilength-1;i++) if (L->elem[i]elem[i+1]) {printf("Your input is wrong.Please try again:\n "); InputList(L);//重新输入表L i=0; } } void MergeList(List *La,List *Lb,List *Lc) { ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La->elem;pb=Lb->elem; Lc->length=La->length+Lb->length; Lc->listsize= La->length+Lb->length; Lc->elem=(ElemType *)malloc(Lc->listsize*sizeof(ElemType)); pc=Lc->elem; pa_last=La->elem+La->length-1;//La最后一个元素的地址 pb_last=Lb->elem+Lb->length-1; //Lb最后一个元素的地址 while(paelem[i]!=L->elem[j]) L->elem[++j]=L->elem[i]; L->length=++j; } void printlist(List *L) {//输入表L int i; for (i=0;ilength;i++) printf("%d\t",L->elem[i]); printf("\n"); } 。