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

PAGE 1 南昌航空大学实验报告 课程名称： 数据结构 实验名称： 实验二：线性表的链式存储结构 班 级： 080611 学生姓名： 赖凌 学号： 指导教师评定： 签 名: 题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。 一、需求分析 ⒈实现两张线性表的链式存储，合并及删除值相同元素的操作。 ⒉ 在演示过程序中，用户敲击键盘，即可观看演示结果。 ⒊ 程序执行的命令包括： （1）构造线性链表A （2）构造线性链表B （3）求两张表的并 （4）删除C中值相同的元素 二、概要设计 ⒈ 为实现上述算法，需要线性表的抽象数据类型： ADT LinkList List { 数据对象：D={ai:|ai∈ElemSet,i=1…n,n≥0} 数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,…n≥0} 基本操作: Status InitList( LinkList L) //操作结果：构造一个空的线性链表L。 Status MakeNode ( Link p, ElemType e ); // 分配由p指向的值为e 的结点，并返回ＯＫ；若分配失败，则返回ＥＲＲＯＲ Status Append (LinkList L,Link s); //将指针s所指（彼此以指针相链接）的一串结点链接在线性链表L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点 Status ListEmpty(LinkList L); //若线性链表L为空表，则返回TRUE，否则返回ERROR。 Int ListLength(LinkList L); //返回线性链表中L最后一个结点的位置。 ElemType GetCurElem(Link p); //已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值 Position GetHead (LinkList L); //返回线性链表L中头结点的位置 Position GetLast( LInkList L); //返回线性链表L中最后一个结点的位置 }ADT LinkList 2. 本程序有三个模块： ⑴ 主程序模块 void main(){ 初始化； { 接受命令； 显示结果； ｝ ｝ ⑵ 线性链表单元模块：实现线性链表抽象数据类型； ⑶ 结点结构单元模块：定义线性链表中的结点结构。 三、详细设计 ⒈元素类型，结点类型 struct node { int date; struct node *next; }; 2.对抽象数据类型中的部分基本操作的伪码算法如下： struct node * creat() { struct node *head,*pa,*pb; head=(struct node *)malloc(sizeof(struct node)); if(!head) exit(0); pa=head; pb=(struct node *)malloc(sizeof(struct node)); if(!pb) exit(0); scanf(%d,pb-date); if(!pb-date) { head-next=NULL; free(pb); return head; } while(pb-date) { pa-next=pb; pa=pb; pb=(struct node *)malloc(sizeof(struct node)); if(!pb) exit(0); scanf(%d,pb-date); } pa-next=NULL; free(pb); return head; } void print(struct node*l) { struct node *p;int i=0; p=l-next; if(p) {