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 语言,可是真到了自己编写程序的时候,还是不知道该从何下手,编写的过程中更是错误连连,根本就无法运行,后来出来了一个简单的结果,成就感还是有的。然后继续在现有程序上进行改进,最后出来了这个结果。编写程序还是需要耐心,注意大小写,中文括号之类的小问题,再多看书,基本就能编出简单的程序,最后在现有程序上进行改进,就能一步步做好。