数据结构实验线性表的顺序存储结构.docx
《数据结构实验线性表的顺序存储结构.docx》由会员分享，可在线阅读，更多相关《数据结构实验线性表的顺序存储结构.docx（12页珍藏版）》请在冰点文库上搜索。
数据结构实验线性表的顺序存储结构
南昌航空大学实验报告
课程名称：
数据结构实验名称：
实验一线性表的链式存储结构
班级：
080611学生姓名：
冯武明学号：
16
指导教师评定：
XXX签名:
XXX
题目：
设计并实现以下算法：
给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。
一、需求分析
⒈先构造两个多项式链表，实现两个多项式的和及删除值为零元素的操作，不同用户输入的多项式不同。
⒉在演示过程序中，用户需敲击键盘输入值，即可观看结果。
⒊程序执行的命令包括：
（1）构造多项式链表A
（2）构造多项式链表B（3）求两张链表的和（4）删除值为零元素，即不创建链表。
二、概要设计
⒈为实现上述算法，需要线性表的抽象数据类型：
ADTStack{
数据对象：
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（linkh,links）
初始条件：
数据元素e1,e2存在
操作结果：
以e1,e2中的姓名项作为判定e1,e2是否相等的依据。
delfirst（linkh,link*q）
初始条件：
数据元素e1,e2存在
操作结果：
以e1,e2中的姓名项（为字符串）的≤来判定e1,e2是否有≤的关系。
append（linklist*L,links）
初始条件：
线性表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（ListL）
初始条件：
线性表L已经存在
操作结果：
打印出表L。
ListInsert（List*L,inti,structSTUe）
初始条件：
线性表L已经存在，1≤i≤ListLength（&L）+1
操作结果：
在表L中第i个位置前插入元素e，L的长度加1。
}ADTList
2.本程序有三个模块：
⑴主程序模块
voidmain（）{
初始化；
{
接受命令；
显示结果；
｝
｝
⑵链表单元模块：
实现表抽象数据类型；
三、详细设计
⒈元素类型，结点类型
typedefstruct{
int*elem;
intlength;
intlistsize;
}sqlist;
sqlist*La,*Lb,*Lc;
2.对抽象数据类型中的部分基本操作的伪码算法如下：
voidinitlist（sqlist*L）
{
L->elem=（int*）malloc（listinitsize*sizeof（int））;
L->length=0;
L->listsize=listinitsize;
}//初始化表
voidadd（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--;
elseif（*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.主函数
voidmain（）
{
voidinitlist（sqlist*L）;
voidadd（sqlist*La,sqlist*Lb,sqlist*Lc）;
sqlist*La,*Lb,*Lc;
inti,p,num;
initlist（La）;
initlist（Lb）;
initlist（Lc）;
printf（"pleaseinputthenumbersofyouwantaboutLa:
\n"）;
scanf（"%d",&num）;
printf（"\n"）;
for（i=0;i{
scanf（"%d",&p）;
La->elem[i]=p;
La->length++;
}
printf（"pleaseinputthenumbersofyouwantaboutLb:
\n"）;
scanf（"%d",&num）;
printf（"\n"）;
for（i=0;i{
scanf（"%d",&p）;
Lb->elem[i]=p;
Lb->length++;
}
printf（"\n\n\n\nthelistofLa:
\n"）;
for（i=0;ilength;i++）
{
printf（"%6d",La->elem[i]）;
}
printf（"\n\n\n\nthelistofLa:
\n"）;
for（i=0;ilength;i++）
{
printf（"%6d",Lb->elem[i]）;
}
printf（"\n\n\n"）;
add（La,Lb,Lc）;
printf（"\n\n\nthelistofLc:
\n"）;
for（i=0;ilength+Lb->length;i++）
{
printf（"%6d",Lc->elem[i]）;
}
getch（）;
}
4.函数调用关系
main
InitializationMakeListOperateListReadCommandprintList
addList
initlist
initlist
四、调试分析
1调试程序时，因为没有注意到指针变量与普通变量对成员的引用所用符号不同，将指针变量引用所用符号写成‘.’，导致程序出现大量错误，耽误了大量的调试时间。
警告shunxu~1.c18:
可能在'La'定义以前使用了它在main函数中，将'La'放在main前即可消除警告。
注意定义各线性表变量为指针变量，这样可以返回函数。
⒉程序采用逐个输入的方法创建La,Lb,在元素较多时，会使得程序很庞大，不利于检查错误等。
⒊算法的时空分析
各操作的算法时间复杂度比较合理
Init（）为O
（1），voidadd（）为O（mn）。
4.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调试也较顺利，各模块有较好的可重用性。
五、用户手册
⒈本程序的运行环境为windowsxp操作系统，执行文件为shunxubiao.c；
⒉进入演示程序后，按规定输入数值后便可看到结果，按任意键退出。
六、测试结果
1、键入数值
2、输出结果
3、键入任意字符，退出演示界面，回到编辑状态。
七、附录：
题一源程序
#include
#definelistinitsize20
#definelistincrement10
typedefstruct{
int*elem;
intlength;
intlistsize;
}sqlist;
main（）
{
voidinitlist（sqlist*L）;
voidadd（sqlist*La,sqlist*Lb,sqlist*Lc）;
sqlist*La,*Lb,*Lc;
inti,p,num;
initlist（La）;
initlist（Lb）;
initlist（Lc）;
printf（"pleaseinputthenumbersofyouwantaboutLa:
\n"）;
scanf（"%d",&num）;
printf（"\n"）;
for（i=0;i{
scanf（"%d",&p）;
La->elem[i]=p;
La->length++;
}
printf（"pleaseinputthenumbersofyouwantaboutLb:
\n"）;
scanf（"%d",&num）;
printf（"\n"）;
for（i=0;i{
scanf（"%d",&p）;
Lb->elem[i]=p;
Lb->length++;
}
printf（"\n\n\n\nthelistofLa:
\n"）;
for（i=0;ilength;i++）
{
printf（"%6d",La->elem[i]）;
}
printf（"\n\n\n\nthelistofLa:
\n"）;
for（i=0;ilength;i++）
{
printf（"%6d",Lb->elem[i]）;
}
printf（"\n\n\n"）;
add（La,Lb,Lc）;
printf（"\n\n\nthelistofLc:
\n"）;
for（i=0;ilength+Lb->length;i++）
{
printf（"%6d",Lc->elem[i]）;
}
getch（）;
}
voidadd（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--;
elseif（*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--;
}
voidinitlist（sqlist*L）
{
L->elem=（int*）malloc（listinitsize*sizeof（int））;
L->length=0;
L->listsize=listinitsize;
}
（注：
文档可能无法思考全面，请浏览后下载，供参考。
可复制、编制，期待你的好评与关注）
升级会员 