数据结构实验报告
评分 满分——5分 学号：2014111990 姓名：陶瑜 专业：计算机科学与技术 知识范畴：线性表 完成日期：2016年03月19日 实验题目：两个有序线性表的归并算法 实验内容及要求：
从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为一个有序线性表；输出归并后的有序线性表。
从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两个升序链表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。 实验目的：掌握两个有序线性表的归并算法。
数据结构设计简要描述：采用带附加头结点方式建立单向链表；每个结点包括整型类型的数据域和一个指针域。第一个程序以数组的形式建立单向顺序存储的线性表，第二个程序以指针的形式建立链式存储的线性表。
算法设计简要描述：线性表排序采用比较大小交换位置的算法实现；线性表的归并采用先比较两个线性表的结点数据大小，按顺序将数据插入原线性表的方法重构链表。
输入/输出设计简要描述：从键盘输入若干整数数据，以回车作为输入结束标志，将输入数据按从小到大顺序排序好后输出。当输入好两个线性表的数据时，回车显示归并后的线性表数据。输出各结点的整数值时，每个整数采用6列字符域宽。输入与输出有文字提示。
编程语言说明：使用Visual C++编程。 主要代码采用C语言实现 ；动态存储分配采用C的malloc和free操作符实现；输入与输出采用C++的cin和cout流；程序注释采用C/C++规范。
主要函数说明：
void InitList(SqList &L); //输入若干整数，建立带附加头结点的单向顺序存储链表 void ShowList(SqList &L) //显示线性表中的所有元素
SqList UnionList(SqList &L1, SqList &L2)//按从小到大的顺序归并两个顺序存储的链表 void SortList(SqList &L) //线性表元素排序
LinkList *CreateList() //输入若干整数，建立带附加头结点的单向链式存储链表 SqList MergeList(SqList L1,SqList L2) //按从小到大顺序归并两个链式存储的有序链表
程序测试简要报告： ? 测试实例1
1 / 7
结论 程序输出结果与期望输出结果相符。 ? 测试实例2
结论 程序输出结果与期望输出结果相符。 ? 测试实例3
结论 程序输出结果与期望输出结果相符。
源程序代码：// 试验1_1.cpp : 顺序存储结构实现两个有序链表的归并 #include \#include
#define N 1000//线性表大小
#define LIST_SIZE 1000//线性表最大长度
typedef struct{
int p[N]; int length; int list_size;
2 / 7
}SqList;
void InitList(SqList &L){//初始化线性表 }
void ShowList(SqList &L){//显示线性表中的所有元素 }
SqList UnionList(SqList &L1, SqList &L2){//按从小到大的顺序组合两个线性表
SqList L3;
L3.list_size = LIST_SIZE;//初始化线性表最大长度
if (L1.length + L2.length < L3.list_size){//初始化线性表实际长度 } else { }
int i = 0, j = 0, k = 0;
while (k < L3.list_size){//判断线性表长度是否超出最大长度，舍去超出最大长度的
while (i < L1.length&&j < L2.length){
if (L1.p[i] < L2.p[j]){
3 / 7
cout << \输入线性表数据：\int temp;
L.length = 0;//初始化线性表实际长度为0 L.list_size = LIST_SIZE;//初始化线性表最大长度 while (1){ }
cin >> temp; char c = getchar(); L.p[L.length++] = temp;
if (c == '\\n')break;//输入回车结束数据输入
for (int i = 0;i cout << endl; cout < L3.length = L1.length + L2.length; cout << \数据超出限定大小，超出部分将被遗弃！\L3.length = L3.list_size; 数据 } } } } L3.p[k++] = L1.p[i++]; else{ } L3.p[k++] = L2.p[j++]; while (i < L1.length) L3.p[k++] = L1.p[i++];//将剩下的数据插入到新线性表后 while (j < L2.length) L3.p[k++] = L2.p[j++]; break; return L3; void SortList(SqList &L){//线性表元素排序 } void main(){ } 4 / 7 int len = L.length; for (int i = 0; i for (int j = i + 1; j < len; j++){ } if (L.p[i]>L.p[j]){//交换元素位置，确保小的在前 } int t = L.p[i]; L.p[i] = L.p[j]; L.p[j] = t; SqList L1,L2; InitList(L1); SortList(L1); ShowList(L1); InitList(L2); SortList(L2); ShowList(L2); SqList L3 = UnionList(L1,L2); ShowList(L3); system(\ // 数据机构实验1_2.cpp : 链式存储结构实现两个有序链表的归并 #include \#include typedef struct Data{ LinkList *CreateList(){ //建立单向链表 LinkList *pHead,*pLast,*pTemp; int temp; pLast=pHead=(LinkList*)malloc(sizeof(LinkList)); cout<<\输入线性表数据:\while(1){ pTemp=(LinkList*)malloc(sizeof(LinkList)); cin>>temp;//使用temp用来存储用户输入的当前数据 pTemp->num=temp;//将temp中的数据存入数据节点中 int num; Data *next; }LinkList,*SqList; pLast->next=pTemp;//指针指向下一节点 pLast=pTemp; } void ShowList(LinkList *pHead){ //显示链表中的素有数据 LinkList *p=pHead->next;//定义p指针来从头到位读取链表中的数据 while(p){ 5 / 7 } char c=getchar(); if(c=='\\n')break;//调用getchar()函数来获取用户输入的回车键，结束输入 pLast->next=NULL; return pHead; } } cout< cout< void SortList(LinkList *pHead){ } SqList MergeList(SqList L1,SqList L2){ //按从小到大顺序归并两个有序链表 SqList s,p,q,pr; q=L2->next; while (q) { } return L1; 6 / 7 //对链表中所有数据按从小到大顺序排列 LinkList *p1,*p2; p1=pHead->next; for(;p1->next;p1=p1->next){ } for(p2=p1->next;p2;p2=p2->next){ } if(p1->num>p2->num){ } int t=p1->num; p2->num=t; p1->num=p2->num; pr = L1; p = L1->next; s = q; q = q->next; while (p && p->num s->next = p; pr->next = s; pr = p; p = p->next; 的数据，执行while循环 } void main() { LinkList *pHead1, *pHead2,*pHead3; pHead1=CreateList(); SortList(pHead1); ShowList(pHead1); pHead2=CreateList(); SortList(pHead2); ShowList(pHead2); pHead3=MergeList(pHead1,pHead2); ShowList(pHead3); getch(); } 7 / 7 百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库数据结构实验报告一在线全文阅读。
相关推荐：
