**大学实验报告
学院： 专业： 班级：
注：各学院可根据教学需要对以上栏木进行增减。表格内容可根据内容扩充。
第二篇：线性表的顺序存储结构实验报告
南昌航空大学实验报告
课程名称： 数据结构 实验名称： 实验一 线性表的顺序存储结构
班 级： 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={ai:|ai∈ElemSet,i=1…n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈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;i<L→length-1;i++)
{
if (L→elem[i]<L→elem[i+1])
InputList(L);//输入为递增时，要重新输入
i=0;
}
}//CheckList
void MergeList(List *La, List *Lb, List *Lc)
{ //表La和Lb合并为Lc
Pa=La→elem;pb=Lb→elem;//pa,pb分别指向La,Lb的第一个元素
Lc→Listsize= La→length+Lb→length;
Lc→elem==(ElemType *)malloc(Lc→listsize*sizeof(ElemType));
pc=Lc→elem;//pc指向表Lc的第一个元素
pa_last=La→elem+La→length-1;//表La最后一个元素的地址
pb_last=Lb→elem+Lb→length-1;// 表Lb最后一个元素的地址
while (pa<=pa_last&&pb<=pb_last)
{//表La,Lb都未操作完时
if (*pa<=*pb) *pc++=*pb++;
else *pc++=*pa++;
}
while (pa<=pa_last) *pc++=*pa++;//将La的剩余部分接到Lc
while (pb<=pb_last) *pc++=*pb++;//将Lb的剩余部分接到Lc
}//MergeList
void DeleteSame(List *L)
{ //删除表中相同的元素
int j=0;
for(i=1;i<=L→length-1;i++)
if(L→elem[i]!=L→elem[j]) L→elem[++j]=L→elem[i];//前后不等时i,j均往后移。
L→length=++j;
}
3.主函数和其他函数的伪码算法
void main()
{
Initialization();//初始化
do {
input (List L);//输入一个线性表L
Operate(List L);//对表进行操作
}while (未执行DeleteSame)
}//main
void Initialization()
{
clrscr();//清屏
屏幕出现提示信息；
now input the list of A:
}// Initialization
void Input(List L)
{//输入线性表L
do{L=getch();}
while(L!=-32768);
}//Input
void Operate(List L)
{//对刚输入的表L进行操作
do{CheckList(La);
InputList(La);
}
while(La不是非递增有序的);printlist(La);
do{CheckList(La);
InputList(La);
}
while(Lb不是非递增有序的);printlist(Lb);
MergeList(La,Lb,Lc);
DeleteSame(Lc);
printlist(Lc);
}
4 函数调用关系
main
Initialization OperateList Input
DeleteSame printlist MergeList CheckList InputList
四、调试分析
⒈ 由于对指针部分的C语言成分有所淡忘，导致一些变量的"&"，"*"使用混乱，使调试费时不少。比如MergeList函数中有if(*pa<=*pb)，一开始写成了if(pa<=pb)，结束程序运行结果不正确。
⒉输入时，元素间隔应为空格。一开始调试用的是"，"，使程序无法运行。因此应注意输入的格式。
3.本程序模块划分合格，使各部分基本独立，因而具有较高的可重用性。
4. 算法的时空分析
各操作的算法时间复杂度比较合理
其中init为O(1),InputList,CheckList,MergeList,DeleteSame,printlist为O(n)。
5.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构：元素结点、线性顺序表、主控模块，使得设计时思路清晰，使调试也较顺利，各模块有较好的可重用性，受到了一次良好的程序设计训练。
五、用户手册
⒈ 本程序的运行环境为windows 98操作系统，执行文件为Exp1Wsh2.c；
⒉ 进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面：
根据提示信息，用户输入数据（整型），以-32768为输入结束的标志。
4.输入完毕（两张表）后，用户只需键入回车键，就能观看操作结果了。
六、测试结果
(1)同时键入Ctrl F9，进入用户界面，屏幕上出现：
Now input the list of A:
(2)输入：1__2__3__-32768,键入回车键，屏幕上出现：
Your input is wrong.Please try again:
(3)输入：9__5__0__-2__-32768，回车，出现：
9 5 0 -2
回车，出现：
Now input the List of B:
(4)输入：10__5__0__-1__-3__-5__-10，回车，出现：
10 5 0 -1 -3 -5 -10
(5) 回车，出现：
Now merge the List A and B:
10 9 5 5 0 0 -1 -2 -3 -5 -10
(6) 回车，出现：
Now delete the same elements in List C:
10 9 5 0 -1 -2 -3 -5 -10
(7) 回车，退出用户界面，返回编辑状态。
七、附录：源程序
//------头文件
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
//符号常量
#define ERROR O
#define OK 1
#define OVERFLOW -1
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量
#define LISTINCREMENT 10//线性表存储空间的分配增量
typedef int ElemType;
//类型声明
typedef struct LIST{
ElemType *elem;
int length;
int listsize;
} List;
int init(List *L);//初始化，创建一张空表
void InputList(List *L);//人工输入一张表L
void CheckList(List *L);//检验表L是否是非递增有序的
void MergeList(List *La,List *Lb,List *Lc);//合并La,Lb，用Lc存储
void DeleteSame(List *L);//删除L中值相同的元素
void printlist(List *L);//打印表L
main()
{
List La,Lb,Lc;//定义结构体变量，即表La,Lb,Lc
init(&La); init(&Lb); init(&Lc);
printf("Now please input the List of A:\n ");
InputList(&La);
CheckList(&La); printf("\n");
printlist(&La); printf("\n");
getch();
printf("Now please input the List of B:\n ");
InputList(&Lb);
CheckList(&Lb); printf("\n");
printlist(&Lb); printf("\n");
getch();
printf("Now Merge the List of A and B:\n ");
MergeList(&La,&Lb,&Lc);
printlist(&Lc); printf("\n \n");
getch();
printf("Now delete the same elements in List C:\n\n ");
DeleteSame(&Lc);
printlist(&Lc);
getch();
}
int init(List *L)
{//构造一个空的线性表
L->elem=(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;i<L->length-1;i++)
if (L->elem[i]<L->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(pa<=pa_last&&pb<=pb_last)
{//表La,Lb都还未操作完时
if (*pa<=*pb) *pc++=*pb++;//将较大者插入Lc中，从而Lc为非递增有序
else *pc++=*pa++;
}
while (pa<=pa_last) *pc++=*pa++; //插入La的剩余元素
while (pb<=pb_last) *pc++=*pb++; //插入Lb的剩余元素
}
void DeleteSame(List *L)
{
int i,j=0;
for (i=1;i<=L->length-1;i++)
if(L->elem[i]!=L->elem[j])
L->elem[++j]=L->elem[i];
L->length=++j;
}
void printlist(List *L)
{//输入表L
int i;
for (i=0;i<L->length;i++)
printf("%d\t",L->elem[i]);
printf("\n");
}