线性表的顺序存储结构_实验报告样例

年南昌航空大学实验报告（用实验报告纸，手写）

课程名称： 数据结构 实验名称： 实验一 线性表的顺序存储结构 班 级： 080611 学生姓名： 赖凌 学号： 08061101 指导教师评定： 签 名:

题目：有两张非递减有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C仍为

非递减有序的，并删除C中值相同的表。

一、需求分析

⒈ 本演示程序根据已有的6位学生的信息，实现两张表的合并及删除值相同元素的操作，不需要用户

重新输入学生的信息。

⒉ 在演示过程序中，用户敲击键盘，即可观看演示结果。

⒊ 程序执行的命令包括：

（1）构造线性表A （2）构造线性表B （3）求两张表的并 （4）删除C中值相同的元素

二、概要设计

⒈ 为实现上述算法，需要线性表的抽象数据类型：

ADT Stack {

数据对象：D={ai:|ai∈ElemSet,i=1…n,n≥0}

数据关系：R1={|ai-1,ai∈D,i=2,…n≥0}

基本操作:

init(list *L)

操作结果：构造一个空的线性表L。

ListLength(List *L)

初始条件：线性表L已经存在

操作结果：返回L中数据元素的个数。

GetElem(List L, int i, ElemType *e)

初始条件：线性表L已经存在，1≤i≤ListLength(&L)

操作结果：用e返回L中第i个数据元素的值。

EqualList(ElemType *e1,ElemType *e2)

初始条件：数据元素e1,e2存在

操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。

Less_EquaList(ElemType *e1,ElemType *e2)

初始条件：数据元素e1,e2存在

操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。

LocateElem(List *La,ElemType e,int type)

初始条件：线性表La已经存在

操作结果：判断La中是否有与e相同的元素。

MergeList(List *La,List *Lb,List *Lc)

初始条件：非递减线性表La，Lb已经存在

操作结果：合并La，Lb得到Lc，Lc仍按非递减有序排列。

UnionList(List *La ,List *Lb)

初始条件：线性表La，Lb已经存在

操作结果：将所有在Lb而不在La中的元素插入到La中表尾的位置。

PrintList(List L)

初始条件：线性表L已经存在

操作结果：打印出表L。

ListInsert(List *L, int i, struct STU e)

初始条件：线性表L已经存在，1≤i≤ListLength(&L)+1

操作结果：在表L中第i个位置前插入元素e，L的长度加1。

2. 本程序有三个模块：

⑴ 主程序模块

void main(){

初始化；

{

接受命令；

显示结果；

｝

｝

⑵ 线性表单元模块：实现线性表抽象数据类型；

⑶ 结点结构单元模块：定义线性表中的结点结构。 }ADT List

三、详细设计

⒈元素类型，结点类型

struct STU{ char name[20]; //学生名字、学号、年龄、分数 char stuno[10]; int age; int score; };

typedef struct STU ElemType; //元素类型

struct LIST{

ElemType *elem; }; int length; //表的长度、大小 int listsize; typedef struct LIST list; //结点类型

2.对抽象数据类型中的部分基本操作的伪码算法如下：

int init(List *L)

{

L→elem=(ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE); If(!L→elem) exit (OVERFLOW); L→length=0; L→listsize= LIST_INIT_SIZE; Return OK;

}//初始化表

int ListLength(List *L)

{

return L→length;

}//返回表长

void GetElem(List L, int i, ElemType *e)

{

*e=L.elem[i];

} //返回元素

int locateElem(List *La, ElemType e, int type)

{

int I; switch(type) //确定元素在表中的位置 { case EQVAL; for(i=0;i

}

void MergeList(List *La, List *Lb, List *Lc)

{ //将两个表合并成Lc

ElemType *pa,*pb,*pc,*pa_last,*pb_last; Pa=La→elem;pb=Lb→elem; Lc→Listsize=Lc→length=La→length+Lb→length; Pc=Lc→elem==(ElemType *)malloc(Lc→listsize*sizeof(ElemType)); if (!Lc→elem) exit(OVERFLOW); pa_last=La→elem+La→length-1; pb_last=Lb→elem+Lb→length-1;

if(EqualList(&La→elem[i],&e)) return 1;break; break; default; } return 0;

{

} if (Less_EqualList(pa,pb)) *pc++=*pa++; else *pc++=*pb++;

while (pa

while (pb

}

void UnionList(List *La, List *Lb)

{

}

int ListInset(List *L,int i,struct STU e)

{ //将元素插入表Ｌ中

3.主函数和其他函数的伪码算法

void main()

{

}

La_len=ListLength(La);Lb_len=ListLength(Lb); For(i=0;iL→length+1) return ERROR; q=&(L→elem[i-1]); for(p=L→elem[L→length-1];p>=q;p--) *(p+1)=*p; *q=e; ++(L→length); return OK; }//ListInsert Before i Initialization();//初始化 ReadCommand(cmd);//读入一个操作符 MakeList(La);printList(La);//产生并打印La MakeList(Lb);printList(Lb);// 产生并打印Lb OperateList(La,Lb);

void Initialization()

{//系统初始化

}

int ReadCommand(cmd)//任意键入一个字符

{

}

void MakeList(La)

{

}

void OperateList(La,Lb)

{

}

4 函数调用关系

MergeList(&La,&Lb,&Lc); UnionList(&La,&Lb); ListInsert(&La,i,e); cmd=getch(); return 1; clrscr();

Less_EqualList

四、调试分析 ⒈ 刚开始输入时，漏掉了一些变量参数的标记"&"，有的则错加了"&"，使得程序运行出来的结果不正

确，使调试程序时费时不少。

⒉ 程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。 ⒊ 算法的时空分析

各操作的算法时间复杂度比较合理

init,ListLength,GetElem,EqualList,Less_EqualList为O(1)

LocateElem,ListInsert,printList为O(n),UnionList为O(mn),MergeList为O(n)。

4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，

各模块有较好的可重用性。

五、用户手册

⒈ 本程序的运行环境为windows xp操作系统，执行文件为Exp1Prb1.c；

⒉ 进入演示程序后，完成编译，连接（即同时按下Ctrl F9）进入演示界面，用户键入任一符号，都

能看完整个演示过程。

六、测试结果

(1)同时键入Ctrl F9，演示为：

-----------------List Demo is running-------------- First is InsertList function name stuno age stu1 stu3 100001 80 100002 80 score 1000 1000 score 1000 1000 1000 (2)键入任意字符，演示为： name stuno age stu1 stu3 stu5 100001 80 100002 80 100003 80 List A length now is 3. name stuno age stu2 stu4 stu6 100001 80 100002 80 100001 80 score 1000 1000 1000 (3)键入任意字符，演示为： List B length now is 3. name stuno age stu1 stu2 stu3 stu4 stu5 stu6 100001 80 100001 80 100002 80 100002 80 100003 80 100001 80 score 1000 1000 1000 1000 1000 1000 (4)键入任意字符，演示为： Second is UnionList function. Now union List A and List B... name stuno age score

stu1 stu2 stu3 stu4 stu5 stu6 100001 80 100002 80 100003 80 100001 80 100002 80 100001 80 1000 1000 1000 1000 1000 1000 List A length now is 6. (5) 键入任意字符，退出演示界面，回到编辑状态。

七、附录：题一源程序

//------头文件

#include

#include

#include

//符号常量

#define ERROR O

#define OK 1

#define EQUAL 1

#define OVERFLOW -1

#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量

#define LISTINCREMENT 10//线性表存储空间的分配增量

//类型声明

struct STU{//定义学生结构体类型，包括姓名，学号，年龄，成绩

char name[20]; char stuno[10]; int age; int score;

}stu[50];

typedef struct STU ElemType;//用ElemType代替学生

struct LIST

{//定义表LIST为结构体类型

};

typedef struct LIST List;//用list代表结构体LIST

int init(List *L)

{//构造一个空的线性表

L→elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

ElemType *elem;//存储空间基址 int length;//当前长度 int listsize;//当前分配的存储容量

If (!L→elem) exit(OVERFLOW);// 存储分配失败

L→length=0;//空表长度为0

L→listsize=LIST_INIT_SIZE;//初始存储容量

Return ok;

}

int ListLength(List *L)

{//求表L的长度

}

void GetElem(List L, int i, ElemType *e)

{

}

int EqualList(ElemType *e1,ElemType *e2)

{//以元素e1,e2中的姓名项是否相等作为判定e1,e2是否相等的标准

}

int Less_EqualList(ElemType *e1,ElemType *e2)

{//以姓名（字符串）的≤作为判定e1≤e2的标准

}

int LocateElem(List *La,ElemType e,int type)

{//判断La中是否有与e符合关系type的元素

int i; suitch(type) { } return 0;

return L→length; *e=L.elem[i]; if (strcmp(e1→name,e2→name)==0) return 1; return 0; else if (strcmp(e1→name,e2→name)

}

void MergeList(List *La,List *Lb,List *Lc)

{//合并表La,Lb,用Lc存储。已知La,Lb元素值按非递减排列，Lc中值也按非递减排列 ElemType *pa,*pb,*pc,*pa_last,*pb_last;

pa=La→elem;pb=Lb→elem;

Lc→listsize=Lc→length=La→length+Lb→length;

Pc=Lc→elem=(ElemType *)malloc(Lc→listsize*sizeof(ElemType));

if (!Lc→elem) exit(OVERFLOW);//存储分配失败

pa_last=La→elem+La→length-1;

pb_last=Lb→elem+Lb→length-1;

while(pa

{//合并，Lc元素按非递减排列

}

while (pa

while (pb

}

void UnionList(List *La ,List *Lb)

{//将所有在Lb中而不在La中的元素插入到La中

}

int printlist(List L)

{//输入表L

}

if (Less_EqualList(pa,pb)) *pc++=*pa++; else *pc++=*pb++; int La_len,Lb_len; int i; ElemType e; La_len=Listlength(La);Lb_len=Listlength(Lb);//求线性表长度 for(i=0;i

int ListInsert(List *L,int i,struct STU e)

{//在表L中第i位上插入e

}

main

{

struct STU e;//定义结构体变量e List La,Lb,Lc;//定义结构体变量，即表La,Lb,Lc Clrscr(); Printf("\n\n--------List Demo is running ----------\n\n"); Printf("First is InsertList function.\n");

init(&La);//创建一个新表La

strcpy(e.name, "stu1");

strcpy(e.stuno, "100001");

e.age=80;

e.score=1000;

ListInsert(&La,1,e);//在La的第1位上插入stu1的数据元素 strcpy(e.name, "stu3");

strcpy(e.stuno, "100002");

e.age=80;

e.score=1000;

ListInsert(&La,2,e);//在La的第2位上插入stu3的数据元素 Printlist(La);//输出La

Printf("List A length now is %d.\n\n",La.length); Getch();

strcpy(e.name, "stu5");

strcpy(e.stuno, "100003");

e.age=80;

e.score=1000;

ListInsert(&La,3,e);//在表La的第3位上插入stu5的数据表 printlist(La);//输出表La

printf("List A length now is %d.\n\n",La.length); getch();

struct STU *p,*q; if (*iL→length+1) return ERROR;//i值不合法 q=&(L→elem[i-1]); for(p=&L→elem[L→length-1];p>=q;--p) *(p+1)=*p; *q=e; ++L→length; return ok;

init(&Lb);//创建一张新表Lb

strcpy(e.name, "stu2");

strcpy(e.stuno, "100001");

e.age=80;

e.score=1000;

ListInsert(&Lb,1,e);//在表Lb的第1位上插入stu2的数据 strcpy(e.name, "stu4");

strcpy(e.stuno, "100002");

e.age=80;

e.score=1000;

ListInsert(&Lb,2,e);// 在表Lb的第2位上插入stu4的数据 strcpy(e.name, "stu6");

strcpy(e.stuno, "100001");

e.age=80;

e.score=1000;

ListInsert(&Lb,3,e);// 在表Lb的第3位上插入stu6的数据 printlist(Lb);//输出表Lb

printf("List B length now is %d.\n\n",Lb.length);

getch();

MergeList(&La,&Lb,&Lc);//合并表La,Lb,用表Lc存储（非递减有序） Printlist(Lc);//输出表Lc

getch();

printf("Second is UnionList function.\n ");

printf("Now Union List A and List B---\n ");

UnionLIst(&La,&Lb);//合并La,Lb，并删除值相同的元素，用La存储 Printlist(La);//输出La

Printf("List A length now is %d.\n\n ",La.length);

getch();

}

11