线性表的链式存储结构实验报告.docVIP

南昌航空大学实验报告

课程名称:数据结构实验名称:实验二:线性表的链式存储结构

班级:080611学生姓名:赖凌学号:

指导教师评定:签名:

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

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

一、需求分析

?实现两张线性表的链式存储，合并及删除值相同元素的操作。

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

?程序执行的命令包括:

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

二、概要设计

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

ADTLinkListList{

数据对象:D={a:|a?ElemSet,i=1?n,n?0}ii

数据关系:R1={a,a|a,a?D,i=2,?n?0}i-1ii-1i

基本操作:

StatusInitList(LinkListL)

//操作结果:构造一个空的线性链表L。

StatusMakeNode(Linkp,ElemTypee);

//分配由p指向的值为e的结点，并返回,,;若分配失败，则返回,,,,,

StatusAppend(LinkListL,Links);

//将指针s所指(彼此以指针相链接)的一串结点链接在线性链表L的最后一个

结点之后，并改变链表L的尾指针指向新的尾结点

StatusListEmpty(LinkListL);

//若线性链表L为空表，则返回TRUE，否则返回ERROR。

IntListLength(LinkListL);

//返回线性链表中L最后一个结点的位置。

ElemTypeGetCurElem(Linkp);

//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值

PositionGetHead(LinkListL);

//返回线性链表L中头结点的位置

PositionGetLast(LInkListL);

//返回线性链表L中最后一个结点的位置

1

}ADTLinkList

2.本程序有三个模块:

?主程序模块

voidmain(){

初始化;

{

接受命令;

显示结果;

,

,

?线性链表单元模块:实现线性链表抽象数据类型;

?结点结构单元模块:定义线性链表中的结点结构。三、详细设计

?元素类型，结点类型

structnode

{

intdate;

structnode*next;

};

2.对抽象数据类型中的部分基本操作的伪码算法如下:structnode*creat()

{

structnode*head,*pa,*pb;

head=(structnode*)malloc(sizeof(structnode));

if(!head)exit(0);

pa=head;

pb=(structnode*)malloc(sizeof(structnode));

if(!pb)exit(0);

scanf(%d,pb-date);

if(!pb-date)

{

head-next=NULL;

free(pb);

returnhead;

}

while(pb-date)

2

{

pa-next=pb;

pa=pb;

pb=(structnode*)malloc(sizeof(structnode));

if(!pb)exit(0);

scanf(%d,pb-date);

}

pa-next=NULL;

free(pb);

returnhead;

}

voidprint(structnode*l)

{

structnode*p;inti=0;

p=l-next;

if(p)

{

while(p)

{

if(i%5==0)

printf(\n);

printf(%6d,p-date);

p=p-next;

i++;

}

}

else

{

printf(ThelistyouhavedcreatedisNULL!!!!!!\n\n);

}

printf(\n\n);

}

voidaddlist(structnode*la,structnode*lb,structnode*lc)

3

{

structnode*pa,*pb,*pc,*q;

pa=la-next;

pb=lb-next;

pc=