第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
数据结构实验报告1-线性表-两个有序表的归并-实验内容及要求.docx
数据结构实验报告
学号：xxxxxxxxxxx
知识范畴：线性表
姓名：xxxxxx
实验题目：两个有序线性表的归并算法
实验内容及要求：
专业：计算机科学与技术
完成日期：2019 年 03 月 18 日
评分
满分——5 分
从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建
立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为
一个有序线性表；输出归并后的有序线性表。
从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺
序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两个升序链
表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。
实验目的：掌握两个有序线性表的归并算法。
数据结构设计简要描述：
1. 链表采用带附加头结点单向升序链表；每个结点包括整型类型的数据域和一个指针域。
2. 顺序存储结构采用只含一个节点的顺序存贮结构实现；结点包括整型类型的数组，数
组最大值和实际长度值。
算法设计简要描述：
比较两个升序链表的数据域，按照有小到大取出节点，按取出节点顺序采用“先入先出”
法重构链表。
输入/输出设计简要描述：
从键盘输入以空格(或 CR 或 TAB)分隔的若干不等于 0 的整数，直到输入 0 时停止输入，
且输入的数据小到大，按整数输入次序建立结点并顺序连接结点。
输出各结点的整数值时，每个整数采用 5 列字符域宽。
输入与输出有文字提示。
编程语言说明：
使用 Code：：Blocks 编程。主要代码采用 C 语言实现 ；动态存储分配采用 C 语言的 malloc
实现；输入与输出采用 C 语言的 scanf 和 printf 函数实现；程序注释采用 C 规范。
主要函数说明：
1. 链表存储结构的主要函数
LinkList createLink();
//输入若干非 0 整数，用先入先出法建立带附加头结点单向链表
//返回附加头结点指针
// 创建头结点，返回头结点指针
LinkList createNode();
void displayLink(LinkList h);
LinkList mergerLink(LinkList ha, LinkList hb, LinkList hc);
第三个链表保持升序
//输出链表中的数据，自变量 h 传入单向链表附加头结点指针
//连个链表合并为一个链表，使得
1 / 8
2.链式存储结构的主要函数
Status initiate(SqList *pL, int max_size); //初始化节点的参数，以及给节点的整形数组动态分配
//内存
void display(SqList * p);
void insert(SqList * p);
//输出节点数组中的数据
//在节点数组中插入数据，数据必须从小到大，且输入 0 结束输入，或
//者超出 max_size 自动停止
Status merger(SqList *la, SqList *lb, SqList *lc);
程序测试简要报告：
//对于 la, lb 按升序归并到 lc 中
(1) 测试实例 1
程序输入
-45 -18 -5 1 45 88 2101 0
-89 -78 -1 5 88 0
程序输出
the first link is:
-45
-18
-5
1
45
88 2101
the second link is:
-89
-78
-1
5
88
merger link by the first and second link:
-89
-78
-45
-18
-5
-1
1
5
45
88
88 2101
结论
程序输出结果与期望输出结果相符。
(2) 测试实例 2
程序输入
-888 -98 -5 1 2 88 0
-55
-9
-4
2
58
88
98 1000
程序输出
the first link is: -888
-98
-5
the second link is:
-55
-9
-4
1
2
2
58
88
88
98 1000
merger link by the first and second link:
-888
-98
-55
-9
-5
-4
1
2
2
58
88
88
98 1000
结论
程序输出结果与期望输出结果相符。
源程序代码：
1. 采用链表采用带附加头结点单向升序链表的代码
//predefine.h
#include
#include
//定义一个带有一个数据和一个指针的结构体
typedef struct node
2 / 8
{
int nNumber;
struct node *next;
}LinkNode, *LinkList;
//main.c
//实验题目：两个有序线性表的归并算法
#include
#include
#include "Predefine.h"
extern LinkList createLink();
extern LinkList createNode();
extern void displayLink(LinkList h);
extern LinkList mergerLink(LinkList ha, LinkList hb, LinkList hc);
int main()
{
LinkList h1, h2, h3;
printf("please input the first link until input zero, must from small to large:");
h1 = createLink();
printf("the first link is:");
displayLink(h1);
printf("please input the second link until input zero, must from small to large:");
h2 = createLink();
printf("the second link is:");
displayLink(h2);
h3 = createNode();
printf("merger link by the first and second link:");
displayLink(mergerLink(h1,h2,h3));
return 0;
}
//createNode.c
#include "predefine.h"
//创建一个链表头结点，数据域不存储数据
LinkList createNode()
{
LinkList p = (LinkList)malloc(sizeof(LinkList));
if(p)
3 / 8
{
p->next = NULL;
}
else{exit(0);}
return p;
}
//createLink.c
#include "predefine.h"
extern LinkList createNode();
//创建一个先入先出的链表，直到输入 0 结束
LinkList createLink()
{
LinkList p, last, h = createNode();
last = h;
int e;
while(1)
{
scanf("%d",&e);
if(!e) break;//输入的数字为 0，跳出循环
p = createNode();
p->nNumber = e;
last->next = p;
last = p;
}
return h;
}
//displayLink.c
#include "Predefine.h"
//输出链表的数据域
void displayLink(LinkList h)
{
LinkList p = h->next;//p 指向有数据的第一个节点
//如果 p 不为空，继续遍历链表
while(p)
{
printf("%5d",p->nNumber);
p = p->next;
4 / 8
}
printf("\n");
}
//mergerLink.c
#include "Predefine.h"
//连个链表合并为一个链表，使得第三个链表保持升序
LinkList mergerLink(LinkList ha, LinkList hb, LinkList hc)
{
LinkList pa, pb, pc, p;
pa = ha->next;
pb = hb->next;
pc = hc;
while(pa && pb)
{
if(pa->nNumber <= pb->nNumber)
{
p = pa;
pa = pa->next;
pc->next = p;
pc = p;
}
else{
p = pb;
pb = pb->next;
pc->next = p;
pc = p;
}
if(pa) pc->next = pa;//如果 pa 所指的链表没有遍历完，直接接到 pc 所指链表之后
if(pb) pc->next = pb;//如果 pb 所指的链表没有遍历完，直接接到 pc 所指链表之后
ha->next = hb->next = NULL;
}
return hc;
}
2. 采用顺序存储结构归并的代码
//predefine.h
#include
#include
typedef struct
{
int *elme;
int max_size;//顺序表最大容量
int n;//线性表实际长度
}SqList;
typedef enum {ERROR, OK} Status;
5 / 8
//main.c
#include
#include
#include "predefine.h"
extern Status initiate(SqList *pL, int max_size);
extern void display(SqList * p);
extern void insert(SqList * p);
extern Status merger(SqList *la, SqList *lb, SqList *lc);
int main()
{
SqList la, lb, lc;
//如果拉 la,lb,lc 初始化失败，程序退出执行
if(!(initiate(&la, 10)==OK && initiate(&lb, 10)==OK && initiate(&lc, 30)==OK))
{
printf("initiate failed!\n");
exit(0);
}
printf("please input the first link until input zero, must from small to large:");
insert(&la);
printf("please input the second link until input zero, must from small to large:");
insert(&lb);
//如果 la,lb 插入成功，便执行归并算法
if(merger(&la, &lb,&lc)==OK)
{
printf("merger link by the first and second link:");
display(&lc);
}
else
printf("merger failed!\n");
return 0;
}
//merger.c
#include "predefine.h"
//对于 la, lb 按升序归并到 lc 中
Status merger(SqList *la, SqList *lb, SqList *lc)
{
if(la->n + lb->n >lc->max_size)
return ERROR;
int i, j, k;
i = j = k = 0;
lc->n = la->n + lb->n;
while(in && jn)
{
if(la->elme[i] < lb->elme[j])
6 / 8
else
lc->elme[k++] = la->elme[i++];
lc->elme[k++] = lb->elme[j++];
}
while(i < la->n)
lc->elme[k++] = la->elme[i++];
while(j < lb->n)
lc->elme[k++] = lb->elme[j++];
return OK;
}
//initiate.c
#include "predefine.h"
//初始化节点的参数，以及给节点的整形数组动态分配内存
Status initiate(SqList *pL, int max_size)
{
pL->n = 0;
pL->max_size = max_size;
pL->elme = (int *)malloc(sizeof(int)*max_size);
if(NULL == pL)
{
return ERROR;
}
return OK;
}
//display.c
#include "predefine.h"
void display(SqList *p)
{
int i = 0;
//以节点的实际长度控制循环
while(i < p->n)
{
printf("%5d",p->elme[i]);
i++;
}
printf("\n");
}
//insert.c
#include "predefine.h"
//在节点数组中插入数据，数据必须从小到大，且输入 0 结束输入，或者超出 max_size 自动停
止
void insert(SqList * p)
{
7 / 8
int e;
scanf("%d",&e);
while(p->nmax_size && e)
{
p->elme[p->n] = e;
(p->n)++;
scanf("%d",&e);
}
}
8 / 8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
