数据结构实验线性表的顺序存储结构

南昌航空大学实验报告

课程名称： 数据结构 实验名称： 实验一 线性表的链式存储结构 班 级： 080611 学生姓名： 冯武明 学号： 16 指导教师评定： XXX 签 名: XXX

题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成

多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析

⒈ 先构造两个多项式链表，实现两个多项式的和及删除值为零元素的操作，不同用户输入的多项式不同。

⒉ 在演示过程序中，用户需敲击键盘输入值，即可观看结果。 ⒊ 程序执行的命令包括：

（1）构造多项式链表A （2）构造多项式链表B （3）求两张链表的和 （4）删除值为零元素，即不创建链表。

二、概要设计

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

ADT Stack {

数据对象：D={ai:|ai∈ElemSet,i=1…n,n≥0} 数据关系：R1={|ai-1,ai∈D,i=2,…n≥0} 基本操作:

init(linklist *L)

操作结果： destroylist(List *L)

clearlist(List *L)

初始条件：线性表L已经存在，1≤i≤ListLength(&L) 操作结果：用e返回L中第i个数据元素的值。 insfirst(link h,link s)

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

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

delfirst(link h,link *q)

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

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

append(linklist *L,link s)

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

操作结果：判断La中是否有与e相同的元素。 remove(linklist *L,link *q)

初始条件：非递减线性表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

三、详细设计

⒈ 元素类型，结点类型

typedef struct{ int *elem; int length; int listsize; }sqlist;

sqlist *La,*Lb,*Lc;

2. 对抽象数据类型中的部分基本操作的伪码算法如下： void initlist(sqlist *L) {

L->elem=(int*)malloc(listinitsize*sizeof(int)); L->length=0;

L->listsize=listinitsize; } //初始化表

void add(sqlist *La,sqlist *Lb,sqlist *Lc) {

int *pa,*pb,*pc,*pa_last,*pb_last; pa=La->elem; pb=Lb->elem;

Lc->listsize=Lc->length=La->length+Lb->length; pc=Lc->elem=(int*)malloc((Lc->listsize)*sizeof(int));

pa_last=La->elem+(La->length-1); pb_last=Lb->elem+(Lb->length-1); while(pa<=pa_last&&pb<=pb_last) {

if(*pa_last<*pb_last) *pc++=*pa_last--; else if(*pa_last>*pb_last) *pc++=*pb_last--; else {

*pc=*pa_last; pc++; pa_last--; pb_last--; } }

while(pa<=pa_last) *pc=*pa_last--; while(pb<=pb_last) *pc=*pb_last--;

}//将两个表合并成Lc

3. 主函数 void main() {

void initlist(sqlist *L);

void add(sqlist *La,sqlist *Lb,sqlist *Lc);

sqlist *La,*Lb,*Lc; int i,p,num;

initlist(La); initlist(Lb); initlist(Lc);

printf(\"please input the numbers of you want about La:\\n\"); scanf(\"%d\printf(\"\\n\"); for(i=0;iscanf(\"%d\ La->elem[i]=p; La->length++; }

printf(\"please input the numbers of you want about Lb:\\n\"); scanf(\"%d\

printf(\"\\n\"); for(i=0;iscanf(\"%d\ Lb->elem[i]=p; Lb->length++; }

printf(\"\\n\\n\\n\\nthe list of La:\\n\"); for(i=0;ilength;i++) {

printf(\"%6d\ }

printf(\"\\n\\n\\n\\nthe list of La:\\n\"); for(i=0;ilength;i++) {

printf(\"%6d\ }

printf(\"\\n\\n\\n\");

add(La,Lb,Lc);

printf(\"\\n\\n\\nthe list of Lc:\\n\"); for(i=0;ilength+Lb->length;i++) {

printf(\"%6d\ } getch(); }

4 .函数调用关系

main

Initialization MakeList OperateList ReadCommand printList

initlist

addList

initlist

四、调试分析

⒈ 调试程序时，因为没有注意到指针变量与普通变量对成员的引用所用符号不同，将指针

变量引用所用符号写成‘.’，导致程序出现大量错误，耽误了大量的调试时间。警告 shunxu~1.c 18: 可能在'La'定义以前使用了它在 main 函数中，将'La'放在main前即可消除警告。注意定义各线性表变量为指针变量，这样可以返回函数。

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

⒊ 算法的时空分析

各操作的算法时间复杂度比较合理 Init（）为O(1)，void add()为O(mn)。

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

调试也较顺利，各模块有较好的可重用性。

五、用户手册

⒈ 本程序的运行环境为windows xp操作系统，执行文件为shunxubiao.c； ⒉ 进入演示程序后，按规定输入数值后便可看到结果，按任意键退出。

六、测试结果

1、键入数值

2、输出结果

3、 键入任意字符，退出演示界面，回到编辑状态。

七、附录：题一源程序

#include

#define listinitsize 20 #define listincrement 10 typedef struct{ int *elem; int length; int listsize; }sqlist;

main() {

void initlist(sqlist *L);

void add(sqlist *La,sqlist *Lb,sqlist *Lc);

sqlist *La,*Lb,*Lc; int i,p,num;

initlist(La); initlist(Lb); initlist(Lc);

printf(\"please input the numbers of you want about La:\\n\"); scanf(\"%d\printf(\"\\n\");

for(i=0;iscanf(\"%d\ La->elem[i]=p; La->length++; }

printf(\"please input the numbers of you want about Lb:\\n\"); scanf(\"%d\

printf(\"\\n\"); for(i=0;iscanf(\"%d\ Lb->elem[i]=p; Lb->length++;

}

printf(\"\\n\\n\\n\\nthe list of La:\\n\"); for(i=0;ilength;i++) {

printf(\"%6d\ }

printf(\"\\n\\n\\n\\nthe list of La:\\n\"); for(i=0;ilength;i++) {

printf(\"%6d\ }

printf(\"\\n\\n\\n\");

add(La,Lb,Lc);

printf(\"\\n\\n\\nthe list of Lc:\\n\");

for(i=0;ilength+Lb->length;i++) {

printf(\"%6d\ }

getch(); }

void add(sqlist *La,sqlist *Lb,sqlist *Lc) {

int *pa,*pb,*pc,*pa_last,*pb_last; pa=La->elem; pb=Lb->elem;

Lc->listsize=Lc->length=La->length+Lb->length; pc=Lc->elem=(int*)malloc((Lc->listsize)*sizeof(int));

pa_last=La->elem+(La->length-1); pb_last=Lb->elem+(Lb->length-1); while(pa<=pa_last&&pb<=pb_last) {

if(*pa_last<*pb_last) *pc++=*pa_last--; else if(*pa_last>*pb_last) *pc++=*pb_last--; else {

*pc=*pa_last; pc++; pa_last--; pb_last--; } }

while(pa<=pa_last) *pc=*pa_last--; while(pb<=pb_last) *pc=*pb_last--; }

void initlist(sqlist *L) {

L->elem=(int*)malloc(listinitsize*sizeof(int));

L->length=0;

L->listsize=listinitsize; }

（注：文档可能无法思考全面，请浏览后下载，供参考。可复制、编制，期待你的好评与关注）