一、实验内容及要求:
1.从键盘输入数据,建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建立线性表,不必考虑排序算法);输出建好的这两个有序线性表;将这两个有序线性表归并为一个有序线性表;输出归并后的有序线性表。
2.从键盘实现数据输入与输出的格式自拟;要求完成两个同样功能的程序,一个程序采用顺序存储结构,另一个程序采用链表实现线性表的存储。其中链表实现时,要求利用两个升序链表的结点实现归并,即归并时不能新建结点,归并后原来两个升序链表的存储空间不在存在。
二、主要说明
1.数据结构设计简要描述:
顺序存储结构使用结构体,结构体中带有数组以及数组的最大存储空间。
链式存储结构同样使用结构体定义结点,用带附加头结点单向链表,每个结点包括整型或浮型类型的数据域和一个指针域。
2.算法设计简要描述:
顺序与链式两种存储均为依次互相比较两线性表中值的大小。顺序存储是新申请存储空间将数据依次存入静态数组中,链式存储是利用原有空间将结点按照数据大小进行重新连接。
第一个程序是通过动态分配内存,初始化两个线性表,然后通过两表相同索引之间值的比较,将其重新赋给新建立的第三个表从而实现两表的合并;
第二个程序是通过建立表头,设置循环分别建立两个链表,然后通过两表中data数值的比较,使第三个表等于第一个表,排序后全部插入第一个表,最后释放第二个表,从而实现量表的合并。
3.输入/输出设计简要描述:
第一个程序从键盘以从小到大的顺序输入以空格(或CR或TAB)分隔的若干不等于0的整数,直到输入0时停止输入,按整数输入次序建立结点并顺序连接结点。
第二个程序从键盘乱序输入以空格(或CR或TAB)分隔的若干不等于0的整数,直到输入0时停止输入,按排序后整数输入次序建立结点并顺序连接结点。
4.编程语言说明:
编程平台:Visual Stdio 2019。编程语言:c语言。
5.主要函数说明:
第一个程序:首先通过InitList函数为线性表动态分配空间,然后通过Input为线性表赋值,初始化好后通过MergeList函数合并两线性表,最后通过Output函数输出线性表。
第二个程序:首先通过CreateList函数在动态创建表头的同时依次指向下一个节点并赋值,再用函数SortList给输入的数排序,然后通过MergeList合并两线性表,最后用OutputList输出线性表。
三、源程序代码:
程序一:
运行示例:
程序源码:
#include<stdio.h> #include<stdlib.h> #define LIST_INIT_SIZE 100 typedef struct { int *elem; int length; int listsize; }SqList; void InitList(SqList &L) { L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int)); if (!L.elem) exit(1); L.length = 0; L.listsize = LIST_INIT_SIZE; } void Input(SqList& L) { int x; while (1) { scanf_s("%d", &x); if (x == 0 || L.length >= LIST_INIT_SIZE) break; L.elem[L.length++] = x; } } void Output(SqList &L) { for (int i = 0; i < L.length; i++) { printf("%3d", L.elem[i]); } } void MergeList(SqList &La, SqList &Lb, SqList &Lc) { int i = 0, j = 0, k = 0; Lc.length = La.length + Lb.length; while (i < La.length && j < Lb.length) { if (La.elem[i] < Lb.elem[j]) { Lc.elem[k] = La.elem[i]; i++; } else { Lc.elem[k] = Lb.elem[j]; j++; } k++; } while (k < Lc.length) { if (i == La.length) { Lc.elem[k] = Lb.elem[j]; j++; } else { Lc.elem[k] = La.elem[i]; i++; } k++; } } int main() { SqList a, b, c; InitList(a); InitList(b); InitList(c); printf("输入第一个线性表数据:"); Input(a); printf("输入第二个线性表数据:"); Input(b); printf("第一个有序线性表:"); Output(a); printf("\n"); printf("第二个有序线性表:"); Output(b); printf("\n"); MergeList(a, b, c); printf("归并后的有序线性表:"); Output(c); }
程序二:
运行示例:
程序源码:
#include<stdio.h> #include<stdlib.h> #define LIST_INIT_SIZE 100 typedef struct LNode { int data; struct LNode* next; }LNode,*LinkList; LinkList CreatList() { LinkList head, tail,p; int e; head = (LinkList )malloc(sizeof(LNode)*LIST_INIT_SIZE); tail = head; scanf_s("%d", &e); while (e) { p = (LinkList )malloc(sizeof(LNode) * LIST_INIT_SIZE); p->data = e; tail->next = p; tail = p; scanf_s("%d", &e); } tail->next = NULL; return head; } void OutputList(LinkList L) { LinkList p = L->next; while (p) { printf("%3d", p->data); p = p->next; } } void SortList(LinkList L) { LinkList p, q; int temp; for(p=L;p!=NULL;p=p->next) for (q = p->next; q != NULL; q = q->next) { if (p->data >q->data) { temp = p->data; p->data = q->data; q->data = temp; } } } void MergeList(LinkList La, LinkList Lb) { LinkList pa, pb, pc; pa = La->next; pb = Lb->next; pc = La; free(Lb); while(pa && pb) if (pa->data <= pb->data) { pc->next = pa; pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } if (pa) pc->next = pa; else pc->next = pb; } int main() { LinkList La,Lb; printf("输入第一个链表:"); La = CreatList(); SortList(La); printf("输入第二个链表:"); Lb = CreatList(); SortList(Lb); printf("第一个排序后的链表:"); OutputList(La); printf("\n"); printf("第二个排序后的链表:"); OutputList(Lb); MergeList(La, Lb); printf("\n"); printf("归并后的链表:"); OutputList(La); }