西南交大赵宏宇数据结构实验报告线性表.docx

数据结构实验报告评分满分5分学号：2014112024 姓名：宋思雨 专业：计算机科学与技术知识范畴：线性表 完成日期：2016年03月17日实验题目：两个有序线性表的归并算法实验内容及要求：从键盘输入数据，建立两个有序线性表(每个线性表的输入数据按由小到大次序输入来建立线性表，不必考虑排序算法)；输出建好的这两个有序线性表；将这两个有序线性表归并为一个有序线性表；输出归并后的有序线性表。从键盘实现数据输入与输出的格式自拟；要求完成两个同样功能的程序，一个程序采用顺序存储结构，另一个程序采用链表实现线性表的存储。其中链表实现时，要求利用两个升序链表的结点实现归并，即归并时不能新建结点，归并后原来两个升序链表的存储空间不在存在。实验目的：掌握两个有序线性表的归并算法。数据结构设计简要描述：顺序存储结构使用结构体，结构体中带有数组以及数组的最大存储空间。链式存储结构同样使用结构体定义结点，用带附加头结点单向链表，每个结点包括整型或浮型类型的数据域和一个指针域。算法设计简要描述：顺序与链式两种存储均为依次互相比较两线性表中值的大小。顺序存储是新申请存储空间将数据依次存入静态数组中，链式存储是利用原有空间将结点按照数据大小进行重新连接。输入/输出设计简要描述：从键盘以从小到大的顺序输入以空格(或CR或TAB)分隔的若干不等于0的整数，直到输入0时停止输入，按整数输入次序建立结点并顺序连接结点。编程语言说明： 使用Visual C+和C编程。顺序表结构部分采用C语言实现；各函数使用的是C语言的编写规范，输出与输入使用的是printf和scanf；链式表结构部分使用的是C+语言；输入和输出分别采用cin和cout;注释采用C/C+规范。主要函数说明：LinkList crt()/创建链表void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)/归并算法排序void prt(LinkList h)/输出存储的元素程序测试简要报告：测试1：测试2：源程序代码：1.顺序存储：#include stdafx.h#include #define MAX_N 10typedef struct int elemMAX_N; int n; int maxsize;SqList;void initiate(SqList *pL) int a; pL-n=0; pL-maxsize=MAX_N; while(1) scanf(%d,&a); if(a=0|pL-n=MAX_N)break; pL-elempL-n+=a; int merge(SqList *a,SqList *b,SqList *c) if(a-n+b-nc-n) return -1; int i=0;int j=0;int k=0; c-n=a-n+b-n; while(in&jn) if(a-elemielemj) c-elemk+=a-elemi+; else c-elemk+=b-elemj+; while(in) c-elemk+=a-elemi+; while(jn) c-elemk+=b-elemj+; return 0;void output(SqList *pL) for(int i=0;in;i+) printf(%3d,pL-elemi);printf(n);int main() SqList a,b,c; initiate(&a);initiate(&b); c.n=MAX_N; merge(&a,&b,&c); output(&c); return 0;2.链表：#include #include #include typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next;LNode, *LinkList;#define CreateNode(p) p=(LinkList)malloc(sizeof(LNode)#define DeleteNode(p) free(void*)(p)LinkList crt() LinkList p,last,h;CreateNode(h);last=h;int e;while(1)scanf(%d,&e);if(e=0)break;CreateNode(p);p-data=e;last-next=p;last=p;last-next=NULL;return h;void prt(LinkList h)LinkList p;CreateNode(p);p=h-next;while(p)printf(%d ,p-data);p=p-next; DeleteNode(p);void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)LinkList pa,pb,pc,p;CreateNode(p);CreateNode(pa);CreateNode(pb);CreateNode(pc);pa = La-next;pb = Lb-next;Lc = pc;while(pa & pb)if(pa-data) data)p=pa;.pa=pa-next;pc-next=p;pc=p;elsep=pb;pb=pb-next;pc-next=p;pc=p;if(pa)pc-next=pa;if(pb)pc-next=pb;int main()LinkList La,Lb,Lc;La = crt();prt(La);Lb = crt();prt(Lb);printf(nGet:);MergeList(La,Lb,Lc); prt(Lc);return 0;附加题：实验题目：双向循环链表中满足条件的结点的删除实验内容及要求：已知双向循环链表(不带附加头结点)某结点地址p。编写算法，删除链表中结点data域值满足条件beErased的所有结点。若执行删除操作后链表中无剩余结点，函数返回NULL；否则，函数返回某剩余结点地址。实验目的：掌握双向循环链表的使用数据结构设计简要描述： 双向循环链表使用结构体定义其中结点，每个结点中包含一个整型数据，两个结点指针域，一个前趋指针，一个后继指针。算法设计简要描述： 双向循环链表中删除结点同单向链表中算法类似。输入/输出设计简要描述：从键盘输入以空格(或CR或TAB)分隔的若干不等于0的整数，直到输入0时停止输入，建立结点并连接结点。输出各结点的整数值时，每个整数采用3列字符域宽。输入与输出有文字提示。编程语言说明：使用Visual C+编程。 主要代码采用C语言实现 ；动态存储分配采用C的malloc和free操作符实现；输入与输出采用C的scanf和printf流。主要函数说明：bool beErased(int d) /满足此条件的结点删除void initiate(Node *p0) /输入若干非0整数，建立双向循环链表Node* del(Node *p)/删除满足条件的结点void print(Node *p) /输出链表中的数据void release(Node *p) /释放申请的结点空间程序测试简要报告：(1) 测试实例1程序输入请输入一串整数（以0为结尾）：1 3 4 5 7 9 0程序输出删除满足条件的数据后，所剩数据为： 1 7 9结论程序输出结果与期望输出结果相符。源程序代码：/双向循环链表删除某结点#include stdafx.h#include #include #define CreateNode(p) p=(Node *)malloc(sizeof(Node)#define DeleteNode(p) free(void *)p)bool beErased(int d)if(d=2&ddata = d;p0-next=p0;p0-pre=p0;temp = p0;while(1)scanf(%d,&d);if(d=0) break;CreateNode(p);p-data = d;p0-pre = p;p-next = p0;p-pre = temp;temp-next = p;temp = p;Node* del(Node *p)Node *q,*s;q=p-next;while(q!=p)if(beErased(q-data)s=q; q=q-next;s-pre-next = q;q-pre = s-pre;DeleteNode(s);else q=q-next;if(beErased(p-data)if(p-next=p) DeleteNode(p);printf(此链表已空n); return NULL;s=p; p=p-next;s-pre-next = p;p-pre = s-pre;DeleteNode(s);return p; int print(Node *p)Node *s=p-next;printf(删除满足条件的数据后，所剩数据为：);printf(%3d,p-data);while(s!=p)printf(%3d,s-data);s = s-next;return 0;void release(Node *p) Node *s=p-next; Node *temp; while(s!=p) temp