数据结构报告

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;intlength;intlistsize;SqList;线性链表结构的定义：typedef structLNodeElemType data;struct LNode *next;LNode, *LinkList;二、算法描述： 先将两个表的元素从键盘输入，然后再将两个表相加，得到第三个表。 在合并后的表中找到值相同的元

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(pa<=pa_last&&pb<=pb_last) / 判断 La， Lb 是否结尾if(*pa<=*pb) / 比较大小，影响插入的顺序 *pc+=*pa+;else*pc+=*pb+;while(pa<=pa_last) / 可能存在没有插完的情况*pc+=*pa+;while(pb<=pb_last)*pc+=*pb+;return Lc;单链表类 C/ 合并链表 La,Lb,LcLNode *MergeList_L(LinkList La,LinkList Lb,LinkList Lc) pa=La-&g

5、t;next; pb=Lb->next;Lc=pc=La;while(pa&&pb) if(pa->data<=pb->data) pc->next=pa; pc=pa; pa=pa->next;else pc->next=pb; pc=pb; pb=pb->next;pc->next=pa?pa:pb;free(Lb);return Lc;三、程序清单：#include <stdio.h>#include <malloc.h>struct int *elem;int length;int lists

6、ize;A,B,C;struct nodeint data;struct node *next;*HA,*HB,*HC;void del_order()int i,j;for(i=0;i<C.listsize-1;i+)if(C.elemi=C.elemi+1)for(j=i+2;j<=C.listsize-1;j+)C.elem j-1=C.elemj;C.listsize-;printf("n 删除后线性表 C 的值： n");for(i=0;i<C.listsize;i+)printf("%d ",C.elemi);merge_o

7、rder()int i=0,j=0,k=0;C.listsize=A.listsize+B.listsize;C.elem=(int *)malloc(C.listsize*sizeof(int);if(C.elem=NULL)return 0;while(i<A.listsize&&j<B.listsize)if(A.elemi<B.elem j)C.elemk+=A.elemi+;elseC.elemk+=B.elem j+;while(i<A.listsize)C.elemk+=A.elemi+;while( j<B.listsize)C.e

8、lemk+=B.elemj+;printf(" 线性表 C 的值为： n");for(k=0;k<C.listsize;k+)printf("%d ", C.elemk);del_order();creat_order() int i;printf(" 请输入线性表 A 和表 B 的长度 :n");scanf("%d%d",&A.listsize,&B.listsize);A.length=A.listsize;B.length=B.listsize;A.elem=(int *)malloc(

9、A.listsize*sizeof(int);B.elem=(int *)malloc(B.listsize*sizeof(int);if(A.elem=NULL|B.elem=NULL)return 0;printf(" 请有序输入线性表 A 的值 n");for(i=0;i<A.listsize;i+)scanf("%d",&(A.elemi);printf(”请有序输入线性表B的值n");for(i=0;i<B.listsize;i+)scanf("%d",&(B.elemi);merge_

10、order();merge_list()struct node *pa,*pb,*q;HC=q=(struct node *)malloc(sizeof(struct node); while(HA!=NULL&&HB!=NULL)if(HA->data<=HB->data)q->next=HA;HA=HA->next;elseq->next=HB;HB=HB->next;q=q->next;while(HA!=NULL)q->next=HA;HA=HA->next;q=q->next;while(HB!=NUL

11、L)q->next=HB;HB=HB->next;q=q->next;q=NULL;printf(" 线性表 C 的值为： n");for(q=HC->next;q!=NULL;q=q->next)printf("%d ",q->data);creat_list()struct node *p,*q;int la,lb;printf("n 请输入线性表 A 和 B 的长度 :n");scanf("%d%d",&la,&lb);HA=p=(struct node *

12、)malloc(sizeof(struct node);if(p=NULL)return ;printf(" 请输入线性表 A 的值 :n");while(la->0)scanf("%d",&p->data);q=p;p=(struct node *)malloc(sizeof(struct node);q->next=p;q->next=NULL;HB=p;printf(" 请输入线性表 B 的值： n");while(lb->0)scanf("%d",&p->

13、data);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();if(ch='a')creat_order();else if(ch='b')creat_list();elsegoto GO;四、运行结果：五、分析与总结：时间复杂度： O(n)空间复杂度： O(1)这是第一次上数据结构实验课，虽然之前学过

14、C 语言，可是真到了自己编写程序的时候， 还是不知道该从何下手， 编写的过程中更是错误连连，开始没有使用 #define 定义，根本就 无法运行，后来出来了一个简单的结果， 成就感还是有的。 然后继续在现有程序上进行改进， 最后出来了这个结果。编写程序还是需要耐心， 注意大小写，中文括号之类的小问题，再多看书， 基本就能编出简 单的程序，最后在现有程序上进行改进，就能一步步做好。实验（二）实验时间2015 年实验地点中栋604实验题目栈、队列1）掌握栈、队列的思想及其存储实现；实验目的2）掌握栈、队列的常见算法的程序实现及应用。实验内容：1）利用栈和算符优先算法，实现表达式求值。2）采用顺序存

15、储实现循环队列的初始化、入队、出队操作。实验内容测试数据：(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入队一、结构定义：栈：#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef structint *base;int *top;int stacksize;SqStack;队列：typedef struct QNodeint data;struct QNode *next;QNod

16、e,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;二、算法描述：（一）、算术表达式算法基本思想：1、 首先置操作数栈为空栈，表达式起始符'# '为运算符栈的栈底元素。2、 依次读入表达式中每个字符，若是操作数则进 OPND 栈，若是运算符则和 OPTR 栈顶 运算符比较优先权后进行相应的操作， 直至整个表达式求值完毕 (即 OPTR 栈的栈顶元 素和当前读入的字符均为 # '。operandType evaluateExpression()/ 算术表达式 求值的算符优先算法。设 OPTR 和

17、 OPND 分别为运算符栈和运算数栈/OP 为运算符号的集合InitState(OPTR); Push(OPTR, '# ');InitState(OPND); c = getchar();While( c != #' | getop(OPTR) != #' )If ( !In(c,OP)/ 当前输入若为运算数则压入 OPND 栈Push (OPND,c);c = getchar();Else Switch (Precede (getop(OPND),c)/ 比较输入运算符和运算符栈顶元素的优先级大小Case <': / 栈顶元素优先级低 ,吧当前

18、运算符压入 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 G

19、eTop(OPND); / 返回运算结果， 此时 OPND 的栈顶元素即为最终运算结果。 二)、队列/ 构造一个空队列 Qint InitQueue(SqQueue *Q)Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);if(!Q->base) / 存储分配失败exit(0);Q->front=Q->rear=0; / 下标初始化为 0return 1;/ 返回 Q 的元素个数 ,即队列的长度int QueueLength(SqQueue Q)return(Q.rear-Q.front+MAXQSIZE)%M

20、AXQSIZE;/ 插入元素 e 为 Q 的新的队尾元素int EnQueue(SqQueue *Q,QElemType e)if(Q->rear+1)%MAXQSIZE=Q->front) / 队列满return 0;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXQSIZE;return 1;/ 若队列不空 ,则删除 Q 的队头元素 ,用 e 返回其值 ,并返回 1;否则返回 0int DeQueue(SqQueue *Q,QElemType *e)if(Q->front=Q->rear) / 队列空retur

21、n 0;*e=Q->baseQ->front;Q->front=(Q->front+1)%MAXQSIZE;return 1;三、程序清单：栈#include <stdio.h>#include <malloc.h>#include <stdlib.h>/OPND 栈struct NDint *base;int *top;int size;OPND;/OPTR 栈struct TRchar *base;char *top;int size;OPTR;/ 构建 OPND 空栈struct ND InitStack_ND(struct N

22、D *S)S->base=(int *)malloc(10*sizeof(int);S->top=S->base;S->size=1;/ 构建 OPTR 空栈struct TR InitStack_TR(struct TR *S)S->base=(char *)malloc(10*sizeof(char);S->top=S->base;S->size=1;/ 用 e 返回 OPND 栈的顶元素struct ND TOP_ND(struct ND *S,int *e)/if(S->base=S->top)/return 0;*e=*(S

23、->top-1);/用e返回OPTR栈的顶元素 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,int e) *(S->top)=e;+(S->top);/ 在 OPTR 栈中插入 estruct TR PUSH_TR(struct TR *S,char e) *(S->top)=e;+(S->top);/ 删除 OPND 顶栈struct

24、 ND POP_ND(struct ND *S,int *e)/if(S->base=S->top)/return 0;-(S->top);*e=*(S->top);/ 删除 OPTR 顶栈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;char c77 ='>','>','<

25、;','<','<','>','>','>','>','<','<','<','>','>',I ， J J J J J J J'>','>','>','>','<','>','>',I，JJJJ

26、JJ J'>','>','>','>','<','>','>',I，JJJJJJ J'<','<','<','<','<','=',' ',IJJJJJJJ J'>','>','>','>',' ',

27、'>','>',I，JJJJJJ J'<','<','<','<','<',' ','='IJJJJJJJ;switch(a)case '+':i=0;break;case '-':i=1;break;case '*':i=2;break;case '/':i=3;break;case '(':i=4;break;case '

28、;)':i=5;break;case '#':i=6;break;switch(b)case '+':j=0;break;case '-':j=1;break;case '*':j=2;break;case '/':j=3;break;case '(':j=4;break;case ')':j=5;break;case '#':j=6;break;return cij;/ 计算 a 和 b 的值int Operate(int a, char theta, in

29、t b)int i,j,result;i=a;j=b;switch(theta)case '+':result=i+j; break; case '-':result=i-j; break; case '*':result=i*j; break; case '/':result=i/j; break;return result;int In(char c)switch(c)case '+':case '-':case '*':case '/':case '(&

30、#39;:case ')':case '#':return 1;break;default:return 0;int C(char z)int i,s=0;for(i=0;zi!=0;i+) s=s*10+(zi-'0');return s;int Expression()int i,d;char z5;char x,theta,c;int a,b;InitStack_TR(&OPTR);PUSH_TR(&OPTR,'#');InitStack_ND(&OPND);TOP_TR(&OPTR,&

31、;x); c=getchar(); while(c!='#'|x!='#')if(In(c)=0)i=0;dozi=c;c=getchar();while(c>='0'&&c<='9');zi=0;d=C(z);PUSH_ND(&OPND,d);elseswitch(Precede(x,c)case '<':/ 栈顶元素优先级低PUSH_TR(&OPTR,c);c=getchar();break;case '=':POP_TR(&OPTR,&

32、amp;x);/ 脱括号并接受下一字符c=getchar();break;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;main()int c;printf("请输入要计算的表达式，以字符#结

33、束:n");c=Expression();printf("Result=%dn",c);队列#include <stdio.h>#include <malloc.h>struct Nodechar *elem;int lenght;int front;int rear;Q;/ 创建队列InitQueue()printf(" 请输入队列 Q 的长度 :n");scanf("%d",&Q.lenght);Q.elem=(char *)malloc(Q.lenght*sizeof(char);Q.f

34、ront=Q.rear=1;/ 队列情况input_Queue()int i=Q.front;printf("n 此时队列长为 %dn",(Q.rear-Q.front+Q.lenght)%Q.lenght);printf("n 此时队列 Q 中的情况为 :n");while(i!=Q.rear)printf("%c ",Q.elemi);i=(i+1)%Q.lenght;/ 入队enqueue(char *s)while(*s!='0')if(Q.rear+1)%Q.lenght=Q.front)printf(&qu

35、ot; 队列已满，不能入队 n");return ;Q.elemQ.rear=*s;Q.rear=(Q.rear+1)%Q.lenght;s+;/ 出队DeQueue(int num)if(Q.front=Q.rear)printf("n 队列为空 n");return ;printf("n 出队的数据为 :n");while(num!=0)if(Q.front=Q.rear)printf(" 队列为空 n");return ;printf("%c ",Q.elemQ.front);Q.front=(Q.

36、front+1)%Q.lenght;num-;C()char s20;int b;int a;InitQueue();while(b)0.结束 n");printf(" 请选择 1. 入队2. 出队scanf("%d",&b);if(b=1)printf("n 请输入要入队的数据 :n");scanf("%s",&s);enqueue(s);input_Queue();printf("n");else if(b=2)printf(" 请输入出队数据个数： n"

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

38、储实现。实验目的2） 掌握二叉树的遍历思想。3）掌握二叉树的常见算法的程序实现。1）输入字符序列，建立二叉链表。2）求先序、中序和后序遍历序列，并显示输出。实验内容3）求二叉树的深度，并显示输出。4）求二叉树的结点总数，并显示输出。测试数据：输入字符序列 ABC? DE? G? F?一、结构定义#include <cstdlib>#include <iostream>#include <stack>#define charchartypedef struct BiTNodechar data;BiTNode *lchild,*rchild;*BiTree;二

39、、算法描述void CreateBiTree(BiTree *T) / 创建树TElemType ch;scanf("%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(BiTre

40、e T)int i,j;if(!T)return 0;if(T->lchild)i=BiTreeDepth(T->lchild); / 递归求深度 elsei=0;if(T->rchild)j=BiTreeDepth(T->rchild);elsej=0;return i>j ? i+1 : j+1;/先序递归遍历T,对每个结点调用函数Visit 一次且仅一次void PreOrderTraverse(BiTree T,int(*Visit)(TElemType)if(T) / T 不空Visit(T->data); / 先访问根结点PreOrderTrav

41、erse(T->lchild,Visit); /再先序遍历左子树PreOrderTraverse(T->rchild,Visit); /最后先序遍历右子树/中序递归遍历T,对每个结点调用函数Visit 次且仅一次void InOrderTraverse(BiTree T,int(*Visit)(TElemType)if(T)InOrderTraverse(T->lchild,Visit); /先中序遍历左子树Visit(T->data); / 再访问根结点InOrderTraverse(T->rchild,Visit); /最后中序遍历右子树/后序递归遍历T,对每

42、个结点调用函数Visit 次且仅一次int PostOrderTraverse(BiTree T,int(*Visit)(TElemType)/返回结点个数if(T) / T 不空PostOrderTraverse(T->lchild,Visit); /PostOrderTraverse(T->rchild,Visit); /; / 最后访问根结点int m;m=Visit(T->data);return m;三、程序清单#include <stdio.h>#include <malloc.h>struct BiTNodechar data;struc

43、t BiTNode *lchild,*rchild;*head;/ 先序遍历void PreOrderTraverse(struct BiTNode *T)先后序遍历左子树再后序遍历右子树if(T)PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);/ 中序遍历void InOrderTraverse(struct BiTNode *T)if(T)InOrderTraverse(T->lchild);printf("%c ",T->data);InOrderTraverse(T->rc

44、hild);/ 后序遍历void PostOrderTraverse(struct BiTNode *T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);creat_Bi()struct BiTNode *p;char ch;ch=getchar();if(ch=' ')p=NULL;elseif(!(p=(struct BiTNode *)malloc(sizeof(struct BiTNode)return 0;p->data=ch;p->lchild=creat_Bi()

45、;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(struct BiTNode *T)if(T=NULL)return 0;elsereturn statistics(T->lchild)+statistics(T->rchild)+1;void ergodic_statistics()PreOrderTraverse(head);printf("n 二叉树 head 的中序遍历为 :n");InOrderTraverse(head);printf("n 二叉树 head 的后序