1、数据结构实验报告- 1 -湖南师范大学工程与设计学院数据结构实验报告姓 名： 年 级：2015 级专 业：计算机科学与技术学 号：任课教师：开课时间：20162017 学年第一学期数据结构实验报告- 2 -实验（一）实验时间 2016 年 12 月 8 日星期四实验地点 前栋 403实验题目 线性表的存储及操作实验目的1) 掌握顺序存储结构和链式存储结构的特点；2) 掌握常见算法。实验内容一内容：已知两个按元素值有序的线性表 A 和 B，编程实现：将 A 和 B 有序归并成一个按元素值有序的线性表，然后删除值相同的元素。二步骤：1) 从键盘输入两个按元素值有序的线性表 A 和 B 的值；2)
2、根据输入把数据元素分别以顺序存储结构和线性链表存储；3) 有序归并成一个新的按元素值有序的线性表 C；4) 输出显示合并后的线性表 C；5) 分别在顺序存储结构和线性链表存储结构上删除值相同的元素，并显示删除后的线性表。数据结构实验报告- 3 -一结构定义（逻辑结构、存储结构）:struct Node int *elem;int length;int listsize;A,B,C;struct nodeint data;struct node *next; *HA,*HB,*HC;二.算法描述（类 C 语言+流程图）： 先将两个表的元素从键盘输入，然后再将两个表相加，得到第三个表。在合并后的表
3、中找到值相同的元素，将后面的元素前移以删除值相同的元素，最后将表的长度减 1 得到最终的结果。/顺序表 LA，LB 合为 LCSqlist MergeList_sq(Sqlist La,Sqlist Lb, Sqlist Lc) pa=La.elem,pb=Lb.elem,*pc;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(int *) malloc(Lc.listsize*sizeof(int);if(!Lc.elem
4、) /分配失败exit(0);while(panext; pb=Lb-next;Lc=pc=La;while(papc=pa;pa=pa-next;else pc-next=pb; pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);数据结构实验报告- 5 -return Lc; 三.程序清单（关键模块和语句加以注释说明）:#include #include struct Node int *elem;int length;int listsize;A,B,C;struct nodeint data;struct node *next; *HA,*HB,*HC
5、;void del_order()int i,j;for(i=0;inext;while(q!=NULL)if(q-data!=p-data) printf(“%d “,q-data);p=q;q=q-next;void merge_list()struct node *pa,*pb,*q;HC=q=(struct node *)malloc(sizeof(struct node);while(HA!=NULLHA=HA-next; elseq-next=HB;HB=HB-next;q=q-next;while(HA!=NULL)q-next=HA;HA=HA-next;q=q-next;wh
6、ile(HB!=NULL)q-next=HB;数据结构实验报告- 8 -HB=HB-next;q=q-next;q=NULL;printf(“线性表 C 的值为：n“);for(q=HC-next;q!=NULL;q=q-next)printf(“%d “,q-data);del_list();void creat_list()struct node *p,*q;int la,lb;printf(“n 请输入线性表 A 和 B 的长度:n“);scanf(“%d%d“,HA=p=(struct node *)malloc(sizeof(struct node);printf(“请输入线性表 A
7、 的值:n“);while(la0)scanf(“%d“,q=p;p=(struct node *)malloc(sizeof(struct node);q-next=p;q-next=NULL;HB=p;printf(“请输入线性表 B 的值：n“);while(lb0)scanf(“%d“,q=p;p=(struct node *)malloc(sizeof(struct node);q-next=p;q-next=NULL;merge_list();main() char ch;GO:printf(“a:顺序存储 nb:线性链表 n“);ch=getchar();数据结构实验报告- 9
8、-if(ch=a)creat_order();else if(ch=b)creat_list();elsegoto GO;四.运行结果（运行界面图及说明）:测试数据：A=（3,5,8,11 ）， B=（2,6,8,9,11,15,20 ）1.线性表为顺序存储类型时:2.线性表为链式存储类型时:数据结构实验报告- 10 -3.在选择线性表数据存储类型时输入数据不合法:五.分析与总结（算法的时间、空间分析，以及改进）:时间复杂度：O(n)空间复杂度：O(1)这是第一次上数据结构实验课，虽然之前学过 C 语言，可是真到了自己编写程序的时候，还是不知道该从何下手，编写的过程中更是错误连连，根本就无法运行，后来出来了一个简单的结果，成就感还是有的。然后继续在现有程序上进行改进，最后出来了这个结果。编写程序还是需要耐心，注意大小写，中文括号之类的小问题，再多看书，基本就能编出简单的程序，最后在现有程序上进行改进，就能一步步做好。
