[2017年整理]北京理工大学数据结构实验报告选作1.doc
文本预览下载声明
《数据结构与算法统计》
实验报告
学院：
班级：
学号：
姓名：
一、实验目的
1.熟悉VC++6.0环境，学习使用C++实现链表的存储结构；
2.通过编程，上机调试，进一步理解线性表、链表的基本概念。
二、实验内容
归并顺序表（选作）。
请按以下要求编程实现：
从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。
将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka和linkb为空表。输出linkc。
对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。
例如：linka输入为：10 20 30 40 50 0
linkb输入为：15 20 25 30 35 40 45 50 0
归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50
删除重复后的linkc为：10 15 20 25 30 35 40 45 50
三、程序设计
1、概要设计
说明程序的主要功能，主程序的流程以及各个程序模块之间的调用关系，给出主要流程图。
应用单链线性表寄存数字序列。
⑴单链线性表的抽象数据类型线性表的定义如下：
ADT LinkList {
数据对象：
D = { ai | ai ?ElemSet, i=1,…,n，n≥0 }
数据关系：
R1 = { ai-1, ai | ai-1,ai ?D, i=2, …,n }
基本操作：
Creat(LinkList L)
操作结果：构造单链线性表L。
MergeList(LinkList La,LinkList Lb,LinkList Lc)
初始条件：单链线性表La，Lb，Lc已经存在。
操作结果：归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
Delete(LinkList L)
初始条件：链表L已经存在。
操作结果：删除L中的重复元素。
Output(LinkList L)
初始条件：单链线性表L已经存在。
操作结果：输出单链线性表L中的各项值。
} ADT LinkList
⑵主程序流程
主程序首先调用Creat(LinkList L)函数，构造单链线性表La，Lb;再调用MergeList(LinkList La,LinkList Lb,LinkList Lc)函数归并La，Lb，得到新的单链线性表Lc，Lc的元素也按值非递减排列;再释放La，Lb的头结点；再调用Delete(LinkList L) 删除Lc中的重复元素；最后调用Output(LinkList L)函数，在屏幕上显示计算结果。
⑶模块调用关系
由主函数模块调用创建模块、归并模块、删除模块和输出模块。
⑷流程图
2、详细设计
⑴数据类型设计
typedef struct LNode
{
int data;
LNode *next;
}LNode,*LinkList; //结点类型，指针类型
⑵操作算法设计
void Creat(LinkList L)// 构造单链线性表L
{
LinkList p,q;
int num;
L=(LinkList)malloc(sizeof(LNode));
L-next=NULL;
p=L;//建立头结点
scanf(%d,num);
while(num!=0)// 每个序列以输入0为结束标记。
{
q=(LinkList)malloc(sizeof(LNode));
q-data=num;
q-next=p-next;
p-next=q; //插入到表尾
p=q;
scanf(%d,num);
}
}
void MergeList(LinkList La,LinkList Lb,LinkList Lc)
//归并La，Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
{
LinkList pa,pb,pc,p,q;
pa=La-next;
pb=Lb-next;
Lc=(LinkList)malloc(sizeof(LNode));
Lc-next=NULL;
pc=Lc; //建立头结点
while(papb)
{
q=(LinkList)malloc(sizeof(LNode));
if(pa-data=pb-data)
//La，Lb中的数据
显示全部