数据结构报告

1、湖南师范大学工程与设计学院数据结构实验报告姓名:沈毕年级:2014专业:应用电子技术学号:201430181029任课教师：肖柳明开课时间：20152016学年第一学期实验（一）实验时间2015 年实验地点中栋603实验题目线性表的存储及操作1）掌握顺序存储结构和链式存储结构的特点；实验目的2） 掌握常见算法。实验内容：已知两个按元素值有序的线性表A和B,编程实现：将 A和B有序归并成一个按元素值有序的线性表。实验步骤：实验内容1）从键盘输入两个按元素值有序的线性表A和B的值；2）根据输入把数据元素分别以顺序存储结构和线性链表存储；3）有序归并成一个新的按元素值有序的线性表C；4）输出显示合并

2、后的线性表C。测试数据：A= (3,5,8,11)，B= (2,6,8,9,11,15,20 )一、结构定义：typedef int ElemType;typedef int Status;顺序存储结构的定义：typedef structElemType *elem;intlen gth;intlistsize;SqList;线性链表结构的定义：typedef struct LNodeElemType data;struct LNode *n ext;LNode, *Li nkList;二、算法描述：先将两个表的元素从键盘输入，然后再将两个表相加，得到第三个表。在合并后的表中找到值相同的元素，

3、将后面的元素前移以删除值相同的元素，最后将表的长度减1得到最终的结果。顺序表LA，LB合为LCSqlist MergeList_sq(Sqlist La,Sqlist Lb, Sqlist Lc) pa=La.elem,pb=Lb.elem,*pc;paast=La.elem+La.le ngth-1;pb_last=Lb.elem+Lb .len gth-1;Lc.li stsize=Lcen gth=La .len gth+Lb .len gth;pc=Lc.elem=(i nt *) malloc(Lc.listsize*sizeof(i nt);if(!Lc.elem)/ 分配失败ex

4、it(0);while(pa=pa_last&pb=pb_last) / 判断 La， Lb 是否结尾if(*pa=*pb)II比较大小，影响插入的顺序*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)/可能存在没有插完的情况*pc+=*pa+;while(pbn ext; pb=Lb-n ext;Lc=pc=La;while(pa&pb) if(pa-datadata) pc-n ext=pa;pc=pa;pa=pa-n ext;else pc-n ext=pb;pc=pb;pb=pb-n ext;pc- n ext=pa?pa:pb;free(Lb);ret

5、urn Lc;三、程序清单：#i nclude #i nclude struct int *elem;int len gth;int listsize;A,B,C;struct nodeint data;struct node *n ext;*HA,*HB,*HC;void del_order()int i,j;for(i=0;iC.listsize-1;i+)if(C.elemi=C.elemi+1) for(j=i+2;j=C.listsize-1;j+) C.elemj-1=C.elemj;C.listsize-;printf(n删除后线性表C的值：n);for(i=0;iC.lists

6、ize;i+)prin tf(%d ”,C.elemi);merge_order()int i=O,j=O,k=O;C.l istsize=A .l istsize+B .l istsize;C.elem=(i nt *)malloc(C .l istsize*sizeof(i nt); if(C.elem=NULL)return 0;while(iA.listsize&jB.listsize)if(A.elemiB.elemj)C.elemk+=A.elemi+;elseC.elemk+=B.elemj+;while(iA.listsize) C.elemk+=A.elemi+;while(

7、jB.listsize) C.elemk+=B.elemj+;printf(”线性表C的值为：n); for(k=0;kC.listsize;k+)prin tf(%d , C.elemk); del_order();creat_order() int i;printf(请输入线性表 A和表B的长度:n); sca nf(%d%d, &A.listsize,&B.listsize);A. len gth=A.listsize;B. len gth=B.listsize;A. elem=(i nt *)malloc(A .l istsize*sizeof(i nt);B. elem=(i nt

8、*)malloc(B .l istsize*sizeof(i nt); if(A.elem=NULL|B.elem=NULL)return 0;printf(请有序输入线性表A的值n”)；for(i=0;iA.listsize;i+)scan f(%d,&(A.elemi);printf(请有序输入线性表B的值n);for(i=0;idatadata)q-n ext=HA; HA=HA- next;elseq-n ext=HB;HB=HB-n ext;q=q_n ext;while(HA!=NULL)q-n ext=HA;HA=HA- next;q=q_n ext;while(HB!=NULL

9、)q-n ext=HB;HB=HB-n ext;q=q_n ext;q=NULL;printf(线性表C的值为：n);for(q=HC-n ext;q!=NULL;q=q_n ext)prin tf(%d ,q-data);creat_list()struct node *p,*q;int la,lb;printf(n请输入线性表 A和B的长度:n);sea nf(%d%d, &la,&l b);HA=p=(struct node *)malloc(sizeof(struct no de); if(p=NULL)return ;printf(请输入线性表A的值:n);while(la-0)sc

10、an f(%d，& p-data);q=p;p=(struct node *)malloc(sizeof(struct no de); q_n ext=p;q- next=NULL;HB=p;printf(请输入线性表B的值：n); while(lb-0)scan f(%d,&p-data);q=p;p=(struct node *)malloc(sizeof(struct no de); q_n ext=p;q- next=NULL;merge_list();main ()char ch;GO:printf(a:顺序存储nb:线性链表n); ch=getchar();if(ch=a)crea

11、t_order();else if(ch=b)creat_list();elsegoto GO;四、运行结果:五、分析与总结: 时间复杂度：0(n) 空间复杂度：0(1)这是第一次上数据结构实验课，虽然之前学过C语言，可是真到了自己编写程序的时候，还是不知道该从何下手，编写的过程中更是错误连连，开始没有使用#define定义，根本就无法运行，后来出来了一个简单的结果，成就感还是有的。然后继续在现有程序上进行改进， 最后出来了这个结果。编写程序还是需要耐心， 注意大小写，中文括号之类的小问题，再多看书，基本就能编出简单的程序，最后在现有程序上进行改进，就能一步步做好。实验（二）实验时间2015

12、年实验地点中栋604实验题目栈、队列1）掌握栈、队列的思想及其存储实现；实验目的2）掌握栈、队列的常见算法的程序实现及应用。实验内容：1）利用栈和算符优先算法，实现表达式求值。2）采用顺序存储实现循环队列的初始化、入队、出队操作。实验内容测试数据：(1) 3 X5 + 9 5 X(6 3)3）循环队列大小为11 , d , e, b , g , h入队；d , e出队；i, j,k, l, m入队；b出队；n , o , p , q , r入队一、结构定义：栈：#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10typedef struc

13、tint *base;int *top;int stacksize;SqStack;队列：typedef struct QNodeint data;struct QNode *n ext;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;Lin kQueue;二、算法描述：(一)、算术表达式算法基本思想：1、首先置操作数栈为空栈，表达式起始符 为运算符栈的栈底元素。2、 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈顶运 算符比较优先权后进行相应的操作，直至整个表达式求值完毕(即OPTR栈的栈顶元

14、素 和当前读入的字符均为#。opera ndType evaluateExpressi on()算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈/OP为运算符号的集合InitState(OPTR); Push(OPTR, #);In itState(OPND); c = getchar();While( c != # getop(OPTR) !=)#If ( !In(c,OP)当前输入若为运算数则压入OPND栈Push (OPND,c);c = getchar();Else Switch (Precede (getop(OPND),c)比较输入运算符和运算符栈顶元素的

15、优先级大小Case栈顶元素优先级低，吧当前运算符压入 OPTRPush(OPTR,c); c = getchar();Break;Case =: /脱括号并接收下一个字符Pop(OPTR,x); c = getchar();Break;Case 弹出OPTR栈顶元素和OPND的两个栈顶元素进行运算并将结果入OPND栈Pop(OPTR,theta); / 弹出 OPTR 栈顶元素Pop(OPND,b);Pop(OPND,a); / 弹出 OPND 的两个栈顶元素Push (OPND,Operate(a,theta,b); 进行运算并将结果入 OPND 栈Break;Return GeTop(OP

16、ND);/返回运算结果，此时OPND的栈顶元素即为最终运算结果。二)、队列/构造一个空队列Qint Ini tQueue(SqQueue *Q)Q-base=(QElemType *)malloc(MAXQSIZE*sizeof(QEIemType);if(!Q-base) /存储分配失败exit(0);Q-fro nt=Q-rear=0;下标初始化为 0return 1;/返回Q的元素个数，即队列的长度int QueueLe ngth(SqQueue Q)return(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE;II插入元素e为Q的新的队尾元素int En Queu

17、e(SqQueue *Q,QEIemType e)if(Q-rear+1)%MAXQSIZE=Q-fro nt) /队列满return 0;Q-baseQ-rear=e;Q-rear=(Q-rear+1)%MAXQSIZE;return 1;1；否则返回0/若队列不空，则删除Q的队头元素，用e返回其值，并返回int DeQueue(SqQueue *Q,QEIemType *e)if(Q-fro nt=Q-rear)/ 队列空return 0;*e=Q-baseQ-fro nt;Q-fro nt=(Q-fro nt+1)%MAXQSIZE;return 1;三、程序清单：栈#i nclude

18、#i nclude #i nclude /OPND 栈struct NDint *base;int *top;int size;OPND;/OPTR 栈struct TRchar *base;char *top;int size;OPTR;/构建OPND栈struct ND In itStack_ND(struct ND *S) _S-base=(i nt *)malloc(10*sizeof(i nt);S-top=S-base;S-size=1;/构建OPTF空栈struct TR In itStack_TR(struct TR *S) _S-base=(char *)malloc(10*

19、sizeof(char);S-top=S-base;S-size=1;/用e返回OPND栈的顶元素struct ND TOP_ND(struct ND *S,i nt *e) _/if(S-base=S-top)/return 0;*e=*(S-top-1);/用e返回OPTF栈的顶元素struct TR TOP_TR(struct TR *S,char *e) _/if(S-base=S-top)/return 0;*e=*(S-top-1);/在OPND栈中插入estruct ND PUSH_ND(struct ND *S,i nt e) _*(S-top)=e;+(S-top);/在OP

20、TF栈中插入estruct TR PUSH_TR(struct TR *S,char e) _*(S-top)=e;+(S-top);/删除OPNDK栈struct ND POP_ND(struct ND *S,i nt *e) _if(S-base=S-top)/return 0;-(S-top);*e=*(S-top);/删除OPTF顶栈struct TR POP_TR(struct TR *S,char *e) _if(S-base=S-top)/return 0;-(S-top);*e=*(S-top);/运算符优先级char Precede(char a,char b)int i,j

21、;char c77= = I J J J J J J J J =0&c=9);zi=0;d=C(z);PUSH_ND(&OPND,d);elseswitch(Precede(x,c)case :/退栈并将运算结果入栈POP_TR(&OPTR, &theta);POP_ND(&OPND,&b);POP_ND(&OPND,&a); /deletePUSH_ND(&OPND,Operate(a,theta,b); break;TOP_TR(&OPTR，& x);TOP_ND(&OPND,&d);return d;mai n()int c;printf(请输入要计算的表达式，以字符#结束:n);c=E

22、xpressio n();prin tf(Result=%dn,c);队列#i nclude #in clude struct Nodechar *elem;in t le nght;int front;int rear;Q；/创建队列Ini tQueue()printf(”请输入队列Q的长度:n);sea nf(%d,&Q.le nght);Q.elem=(char *)malloc(Qen ght*sizeof(char);Q.fro nt=Q.rear=1;/队列情况in put_Queue()int i=Q.fro nt;printf(n此时队列长为 %dn,(Q.rear-Q.fro

23、nt+Q.lenght)%Q.lenght);printf(n此时队列Q中的情况为:n);while(i!=Q.rear)prin tf(%c ”,Q.elemi);i=(i+1)%Q.le nght;/入队enqueue(char *s)while(*s!=0)if(Q.rear+1)%Q.le nght=Q.fro nt)printf( 队列已满，不能入队n);return ;Q.elemQ.rear=*s;Q.rear=(Q.rear+1)%Q.le nght;s+;/出队DeQueue(i nt num)if(Q.fro nt=Q.rear)printf(n队列为空 n);return

24、 ;printf(n出队的数据为:n);while( nu m!=0)if(Q.fro nt=Q.rear)printf(”队列为空 n);return ;prin tf(%c ,Q.elemQ.fro nt);Q.fro nt=(Q.fro nt+1)%Q.le nght; num-;C()char s20;int b;int a;Ini tQueue();while(b)0. 结束 n);printf( 请选择1.入队 2. 出队 sca nf(%d,&b);if(b=1)prin tf(n请输入要入队的数据:n);sca nf(%s, &s);enq ueue(s);in put_Que

25、ue();prin tf(n);else if(b=2)printf(”请输入出队数据个数：n);sca nf(%d,&a);DeQueue(a);in put_Queue();prin tf(n);else if(b=0)return 0;elseprintf(”请重新输入n);main ()C()；四、运行结果：五、分析与总结：时间复杂度：0(n)0PND栈和空间复杂度：0(1)用栈来做算式的运算最重要的就是排好不同运算符之间的优先级关系，如果0PTR栈做好了的话基本就很简单了，只需要注意进栈和出栈不要出错即可。实验（三）实验时间2015 年实验地点中栋604实验题目二叉树的常见操作1）掌

26、握二叉树的存储实现。实验目的2）掌握二叉树的遍历思想。3）掌握二叉树的常见算法的程序实现。1）输入字符序列，建立二叉链表。2）求先序、中序和后序遍历序列，并显示输出。实验内容3）求二叉树的深度，并显示输出。4）求二叉树的结点总数，并显示输出。测试数据：输入字符序列 ABC? DE? G? F?一、结构定义#in elude #in elude #in elude #defi ne charchartypedef struct BiTNodechar data;BiTNode *lchild,*rchild;*BiTree;二、算法描述void CreateBiTree(BiTree *T)/

27、创建树TElemType ch;scan f(%c,&ch);if(ch=Nil)/ 空 *T=NULL;else*T=(BiTree)malloc(sizeof(BiTNode);if(!*T)exit(0);(*T)-data=ch; / 生成根结点CreateBiTree(&(*T)-lchild); /构造左子树CreateBiTree(&(*T)-rchild); /构造右子树/返回T的深度int BiTreeDepth(BiTree T)if(!T)return 0;if(T-lchild)i=BiTreeDepth(T-lchild);递归求深度elsei=0;if(T-rchi

28、ld)j=BiTreeDepth(T-rchild);elsej=0;return ij ? i+1 : j+1;/先序递归遍历 T,对每个结点调用函数Visit 一次且仅一次void PreOrderTraverse(BiTree T,int(*Visit)(TEIemType)if(T) / T 不空Visit(T-data); /先访问根结点PreOrderTraverse(T-lchild,Visit); /再先序遍历左子树PreOrderTraverse(T-rchild,Visit); / 最后先序遍历右子树/中序递归遍历T,对每个结点调用函数Visit 一次且仅一次void In

29、 OrderTraverse(BiTree T,i nt(*Visit)(TEIemType)if(T)In OrderTraverse(T-lchild,Visit); /先中序遍历左子树Visit(T-data); /再访问根结点In OrderTraverse(T-rchild,Visit); /最后中序遍历右子树/后序递归遍历T,对每个结点调用函数Visit 一次且仅一次int PostOrderTraverse(BiTree T,int(*Visit)(TEIemType)返回结点个数if(T) / T 不空PostOrderTraverse(T-lchild,Visit); / 先

30、后序遍历左子树PostOrderTraverse(T-rchild,Visit); / 再后序遍历右子树;/最后访问根结点int m;m=Visit(T-data);return m;三、程序清单#i nclude #i nclude struct BiTNodechar data;struct BiTNode *lchild,*rchild;*head;/先序遍历void PreOrderTraverse(struct BiTNode *T)if(T)prin tf(%c ,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchil

31、d);中序遍历void In OrderTraverse(struct BiTNode *T)if(T)InO rderTraverse(T-lchild);prin tf(%c ,T-data);InO rderTraverse(T-rchild);/后序遍历void PostOrderTraverse(struct BiTNode *T)if(T)PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);prin tf(%c ,T-data);creat_Bi()struct BiTNode *p;char ch;ch=getchar(

32、);if(ch=)p=NULL;elseif(!(p=(struct BiTNode *)malloc(sizeof(struct BiTNode) return 0;p-data=ch;p-lchild=creat_Bi(); p-rchild=creat_Bi();return p;depth(struct BiTNode *T)int dl,dr;if(T=NULL)return 0;elsedl=depth(T-lchild);dr=depth(T-rchild);if(dl=dr)return dl+1;elsereturn dr+1;/计算二叉树的节点个数statistics(st

33、ruct BiTNode *T)if(T=NULL)return 0;elsereturn statistics(T-lchild)+statistics(T-rchild)+1;void ergodic_statistics()printf(n二叉树head的先序遍历为：n);PreOrderTraverse(head);printf(n二叉树head的中序遍历为:n);InO rderTraverse(head);printf(n二叉树head的后序遍历为:n);PostOrderTraverse(head);printf(n 二叉树 head 的深度为：dn,depth(head); p

34、rintf(二叉树 head 的节点总数为:%dn,statistics(head);main ()head=creat_Bi(); ergodic_statistics();四、运行结果五、分析和总结时间复杂度0(n)空间复杂度0(n)做二叉树最重要的思想就时递归，在一个函数中可以反复递归，最后求出二叉树的深度、节点数以及它的各种遍历。实验（四）实验时间2015 年实验地点中栋604实验题目查找的有关操作实验目的1）掌握顺序查找算法的思想及程序实现。2）掌握折半查找算法的思想及程序实现。1）根据输入数据，采用顺序查找实现某一已知的关键字的查找，并显示查找结果。2）利用实验一建立有序表，采用折

35、半查找实现某一已知的关键字的查实验内容找，并显示查找结果。测试数据：1)输入数据(45,21,76,36,54,19,64,82,29，91)，查找 64 和 90。2) 有序表(05,13,19,21,37,56,64,75,80,88,92)，查找 64 和 90。一、结构定义#in elude #in elude #i nclude using n amespace std;#define intint#define SSNUM 11#defi ne BSTNUM 6struct SSTablein t*elem;int len gth;typedef struct BiTNodeint

36、 data;BiTNode *lchild,*rchild;*BiTree;二、算法描述Status Search_Seq(SSTable ST, int key) 顺序查找ST.elemO=key;for( i=ST.length; !EQ(ST.elemi,key); -i);return i;Status Search_B in( SSTable ST,i nt key) 折半查找low =1,high=ST .len gth;while(low=high) mid=(low+high)/2;if(EQ(key,ST.elemmid) return mid;else if (LT(key

37、,ST.elemmid) high=mid-1;else low=mid+1;return 0;三、程序清单#i nclude #i nclude structint *ad;int len ght;s；void search_fold()int a,low,mid,high;printf(请输入要查找的数据：n);scan f(%d,&a);low=1;high=s .len ght;mid=(low+high)/2;while(low=high)if(a=s.admid-1)break;elseif(ahigh)printf(%d在有序表S中不存在”,a);elseprintf(%d是有序

38、表 S中第%d个数,a,mid);void creat_fold()int i;printf(”请输入表格S的长度：n); sca nf(%d, &s.le nght);s.ad=(i nt *)malloc(s.le nght*sizeof(i nt); printf(”请有序输入表格 S的值：n); for(i=0;i0;i-)if(s.adi=a)break;if(i=0)printf(数据 %d 不存在 n,a);elseprintf(数据 %d 在第 %d 个位置 n,a,i+1);void creat_order()int i;printf(请输入表格S的长度：n);sca nf(

39、%d, &s.le nght);s.ad=(i nt *)malloc(s.le nght*sizeof(i nt);printf(请输入表格S的值：n);for(i=0;is .len ght;i+)sca nf(%d, &s.adi);search_order();main () char m;printf(a:顺序查找b:折半查找n);m=getchar();if(m=a)creat_order();elsecreat_fold();四、运行结果F :滤牲誰査Jg-五、分析和总结时间复杂度：顺序查找 0( n)折半查找O(log2 n)空间复杂度：0(1)顺序查找时在0号位置设置哨兵位，

40、然后从后往前查找，能够得到结果。 折半查找只能用于有序表实验（五）实验时间2016 年实验地点中栋604实验题目排序实验目的1）掌握常见的排序算法的思想及其适用条件。2）掌握常见的排序算法的程序实现。实验内容输入一组关键字序列分别实现下列排序：1）实现简单选择排序、直接插入排序和冒泡排序。一、结构定义#i nclude #i nclude #defi ne M 9 using n amespace std; struct SLnodeint *r;int len gth;二、算法描述int s,i,j,t;for(i=0;ai;i+)s=i;for(j=i+1;aj;j+) if(asaj)

41、s=j; t=ai; ai=as;as=t;void bubble_sort(i nt a)int i,j;int temp=0;for(i=0;ai;i+)for(j=i+1;aj;j+) if(aiaj)temp=ai;ai=aj; aj=temp;i=0;while(ai)prin tf(%d”,ai+);void in sert_sort(i nt a)int i,j;int temp;for ( i=1; ai; i+)temp=ai;j=i-1;while (j=0)& (tempaj) aj+1=aj;j-;aj+1=temp;i=0;while(ai)/prin tf(%d ,ai+)