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

数据结构实验报告评分满分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 <stdio.h>#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->n>c->n) return -1; int i=0;int j=0;int k=0; c->n=a->n+b->n; while(i<a->n&&j<b->n) if(a->elemi<b->elemj) c->elemk+=a->elemi+; else c->elemk+=b->elemj+; while(i<a->n) c->elemk+=a->elemi+; while(j<b->n) c->elemk+=b->elemj+; return 0;void output(SqList *pL) for(int i=0;i<pL->n;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 <stdio.h>#include <stdlib.h>#include <malloc.h>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) <= (pb->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 <stdio.h>#include <malloc.h>#define CreateNode(p) p=(Node *)malloc(sizeof(Node)#define DeleteNode(p) free(void *)p)bool beErased(int d)if(d>=2&&d<=5) return true;else return false;typedef struct nodeint data;struct node *next;struct node *pre;Node;void initiate(Node *p0)int d;scanf("%d",&d);Node *p,*temp;p0->data = 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 = s; s = s->next; DeleteNode(temp); DeleteNode(p);int main(int argc, char* argv)Node *l;CreateNode(l);printf("请输入一串整数（以0为结尾）：");initiate(l);l = del(l);if(l!=NULL)print(l); release(l);printf("n");return 0;