数据结构实验一线性表及其应用实验二栈和队列的应用实验三树和二叉树的建立和应用

1、DONGFANG COLLEGE，FUJIAN AGRICULTURE AND FORESTRY UNIVERSITY课程名称：数据结构系 别：计算机系年级专业：2010级电子信息工程学 号： 1050302103姓名：廖少兵任课教师：谢储辉成绩：2012年12月25日实验一线性表及其应用【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验帮助学生加深对 C 语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操

2、作）。【实验内容】1 线性表顺序存储的基本操作参考程序：/*线性表顺序存储的基本操作*/#include <stdio.h>#define MaxSize 50typedef char ElemType;struct ListElemType listMaxSize;int size;void setnull(struct List *p)p->size=0;int length(struct List *p)return(p->size);int get(struct List *p,int i)if (i>p->size)return(-1);elser

3、eturn(p->listi-1);int locate(struct List *p,ElemType x)int i=0;while (i<p->size && p->listi!=x) i+;if (i=p->size)return(-1);elsereturn(i+1);void insert(struct List *p,ElemType x,int i)int j;if (i<1 && i>p->size+1)printf("位置参数不正确,不能进行插入操作!n");elsep-&g

4、t;size+;for (j=p->size-1;j>=i;j-) /*结点向后移动,腾出一个位置*/p->listj=p->listj-1;p->listj=x;void delete(struct List *p,int i)int j;if (i>p->size | i<1)printf("位置参数不正确,不能进行删除操作!n");elsefor (j=i-1;j<p->size-1;j+) /*结点向前移动,覆盖该删除的结点*/p->listj=p->listj+1;p->size-;di

5、splay(struct List *p)int j;if (p->size=0)printf("该线性表为空,不能显示!n");elseprintf("线性表:");if (p->size=1) /*只有一个结点的情况*/printf("%c",p->listp->size);else /*有一个以上结点的情况*/for (j=0;j<p->size-1;j+)printf("%c",p->listj);printf("%c",p->listj)

6、; /*显示最后一个结点*/printf("n");main()struct List L;setnull(&L);insert(&L,'a',1);insert(&L,'b',2);insert(&L,'a',1);insert(&L,'c',2);insert(&L,'d',1);insert(&L,'e',2);display(&L);printf("值:%c 位置:%dn",'a&

7、#39;,locate(&L,'a');printf("位置:%d 值:%cn",4,get(&L,4);printf("删除第 2 个结点后");delete(&L,2);display(&L);printf("删除第 2 个结点后");delete(&L,2);display(&L);printf("删除第 1 个结点后");delete(&L,1);display(&L);printf("删除第 1 个结点后"

8、);delete(&L,1);display(&L);2 线性表链式存储的基本操作/*线性表链式存储-单链表的基本操作*/#include <stdio.h>#include <malloc.h>typedef char ElemType;struct LNodeElemType data;struct LNode *next;setnull(struct LNode *p)*p=NULL;int length(struct LNode *p)int n=0;struct LNode *q=*p;while (q!=NULL)n+;q=q->nex

9、t;return(n);ElemType get(struct LNode *p,int i)int j=1;struct LNode *q=*p;while (j<i && q!=NULL) /*查找第 i 个结点*/q=q->next;j+;if (q!=NULL) /*找到了第 i 个结点*/return(q->data);elseprintf("位置参数不正确!n");int locate(struct LNode *p,ElemType x)int n=0;struct LNode *q=*p;while (q!=NULL &am

10、p;& q->data!=x) /*查找data 域为 x 的第一个结点*/q=q->next;n+;if (q=NULL) /*未找到 data 域等于 x 的结点*/return(-1);else /*找到data 域等于 x 的结点*/return(n+1);void insert(struct LNode *p,ElemType x,int i)int j=1;struct LNode *s,*q;s=(struct LNode *)malloc(sizeof(struct LNode); /*建立要插入的结点 s*/s->data=x;q=*p;if (i=

11、1) /*插入的结点作为头结点*/s->next=q;*p=s;elsewhile (j<i-1 && q->next!=NULL) /*查找第 i-1 个结点*/q=q->next;j+;if (j=i-1) /*找到了第 i-1 个结点,由 q 指向它*/s->next=q->next; /*将结点 s 插入到 q 结点之后*/q->next=s;else printf("位置参数不正确!n");void delete(struct LNode *p,int i)int j=1;struct LNode *q=*

12、p,*t;if (i=1) /*删除链表的头结点*/t=q;*p=q->next;elsewhile (j<i-1 && q->next!=NULL) /*查找第 i-1 个结点*/q=q->next;j+;if (q->next!=NULL && j=i-1) /*找到第 i-1 个结点,由 q 指向它*/t=q->next; /*t 指向要删除的结点*/q->next=t->next; /*将q 之后的结点删除*/else printf("位置参数不正确!n");if (t!=NULL) /

13、*在 t 不为空时释放该结点*/free(t);void display(struct LNode *p)struct LNode *q;q=*p;printf("单链表显示:");if (q=NULL) /*链表为空时*/printf("链表为空!");else if (q->next=NULL) /*链表只有一个结点时*/printf("%cn",q->data);else /*链表存在一个以上的结点时*/while (q->next!=NULL) /*显示前面的结点*/printf("%c"

14、,q->data);q=q->next;printf("%c",q->data); /*显示最后一个结点*/printf("n");main()struct LNode *head;setnull(&head);insert(&head,'a',1);insert(&head,'b',2);insert(&head,'a',2);insert(&head,'c',4);insert(&head,'d',3);i

15、nsert(&head,'e',1);display(&head);printf("单链表长度=%dn",length(&head);printf("位置:%d 值:%cn",3,get(&head,3);printf("值:%c 位置:%dn",'a',locate(&head,'a');printf("删除第 1 个结点:");delete(&head,1);display(&head);printf(&qu

16、ot;删除第 5 个结点:");delete(&head,5);display(&head);printf("删除开头 3 个结点:");delete(&head,3);delete(&head,2);delete(&head,1);display(&head);3 双链表的基本操作/*双链表的基本操作*/#include <stdio.h>#include <malloc.h>typedef char ElemType;struct DNodeElemType data;struct DNo

17、de *left,*right;setnull(struct DNode *p)*p=NULL;int length(struct DNode *p)int n=0;struct DNode *q=*p;while (q!=NULL)n+;q=q->right;return(n);ElemType get(struct DNode *p,int i)int j=1;struct DNode *q=*p;while (j<i && q!=NULL) /*查找第 i 个结点*/q=q->right;j+;if (q!=NULL) /*找到了第 i 个结点*/ret

18、urn(q->data);elseprintf("位置参数不正确!n");int locate(struct DNode *p,ElemType x)int n=0;struct DNode *q=*p;while (q!=NULL && q->data!=x) /*查找data 域为 x 的第一个结点*/q=q->right;n+;if (q=NULL) /*未找到 data 域等于 x 的结点*/return(-1);else /*找到data 域等于 x 的结点*/return(n+1);void insert(struct DNod

19、e *p,ElemType x,int i)int j=1;struct DNode *s,*q;s=(struct DNode *)malloc(sizeof(struct DNode); /*建立要插入的结点 s*/s->data=x;s->left=s->right=NULL;q=*p;if (i=1) /*插入的结点作为表头结点*/s->right=q;if (q!=NULL) /*原来的双链表不为空*/q->left=s;*p=s;elsewhile (j<i-1 && q->right!=NULL) /*查找第i-1 个结点

20、*/q=q->right;j+;if (j=i-1) /*找到了第 i-1 个结点,由 q 指向它*/if (q->right!=NULL) /*q 不是最后一个结点*/s->right=q->right; /*将结点s 插入到q 结点和之后结点 q->right 之间*/q->right->left=s;s->left=q;q->right=s;else /*q 是最后一个结点*/s->left=q; /*将 s 作为表尾结点*/q->right=s;else printf("位置参数不正确!n");voi

21、d delete(struct DNode *p,int i)int j=1;struct DNode *q=*p,*t;if (i=1) /*删除链表的头结点*/t=q;q=q->right;if (q!=NULL) /*当双链表不只一个结点时*/q->left=NULL;*p=q;elsewhile (j<i-1 && q->right!=NULL) /*查找第i-1 个结点*/q=q->right;j+;if (q->right!=NULL && j=i-1) /*找到第 i-1 个结点,由 q 指向它*/t=q->

22、;right; /*t 指向要删除的结点*/if (t->right!=NULL) /*删除的结点不是最后结点*/q->right=t->right; /*将 q 之后的结点删除*/q->right->left=q;else /*删除的结点是最后结点*/q->right=NULL;else printf("位置参数不正确!n");if (t!=NULL) /*在 t 不为空时释放该结点*/free(t);void display(struct DNode *p)struct DNode *q;q=*p;printf("双链表显示

23、:");if (q=NULL) /*链表为空时*/printf("链表为空!");else if (q->right=NULL) /*链表只有一个结点时*/printf("%cn",q->data);else /*链表存在一个以上的结点时*/while (q->right!=NULL) /*显示前面的结点*/printf("%c",q->data);q=q->right;printf("%c",q->data); /*显示最后一个结点*/printf("n&q

24、uot;);main()struct DNode *dhead;setnull(&dhead);insert(&dhead,'a',1);insert(&dhead,'b',2);insert(&dhead,'a',2);insert(&dhead,'c',4);insert(&dhead,'d',3);insert(&dhead,'e',1);display(&dhead);printf("双链表长度=%dn",l

25、ength(&dhead);printf("位置:%d 值:%cn",3,get(&dhead,3);printf("值:%c 位置:%dn",'a',locate(&dhead,'a');printf("删除第 1 个结点:");delete(&dhead,1);display(&dhead);printf("删除第 5 个结点:");delete(&dhead,5);display(&dhead);printf("

26、删除开头 3 个结点:");delete(&dhead,3);delete(&dhead,2);delete(&dhead,1);display(&dhead);4 顺序表的应用约瑟夫问题的实现【问题描述】设有 n 个人围坐在圆桌周围，现从某个位置 m（1mn）上的人开始报数，报数到 k的人就站出来。下一个人，即原来的第k+1 个位置上的人，又从1 开始报数，再报数到 k的人站出来。依此重复下去，直到全部的人都站出来为止。试设计一个程序求出出列序列。这是一个使用循环链表的经典问题。因为要不断地出列，采用链表的存储形式能更好地模拟出列的情况。【数据描述】

27、建立一个不带头结点的循环链表，其中的 n 个人用 n 个结点来表示。Typedef int Elemtype;Typedef struct Cnode Elemtype data;struct Cnode *next;CNode;【C 源程序】#include <stdio.h>#include <stdlib.h>#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int Elemtype;/*定义数据元素类型 */typedef struct C

28、node Elemtype data;struct Cnode *next;CNode;CNode *joseph;/*定义一个全局变量 */Status Create_clist(CNode *clist,int n) CNode *p,*q;int i;clist=NULL;for(i=n;i>=1;i-) p=(CNode *)malloc(sizeof(CNode);if(p=NULL)return OVERFLOW; /*存储分配失败 */p->data=i;p->next=clist;clist=p;if(i=n)q=p;/*用 q 指向链表的最后一个结点 */q

29、->next=clist; /*把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表 */joseph=clist; /*把创建好的循环链表头指针赋给全局变量 */return OK; /*end */Status Joseph(CNode *clist,int m,int n,int k) int i;CNode *p,*q;if(m>n) return ERROR;/*起始位置错 */if(!Create_clist(clist,n)return ERROR; /*循环链表创建失败 */p=joseph; /*p 指向创建好的循环链表 */for(i=1;i<m;

30、i+)p=p->next; /*p 指向 m 位置的结点 */while(p) for(i=1;i<k-1;i+)p=p->next; /* 找出第 k 个结点 */q=p->next;printf("%d ",q->data);/*输出应出列的结点 */if(p->next=p)p=NULL; /*删除最后一个结点 */else p->next=q->next;p=p->next;free(q); /*while */clist=NULL; /* end */void main( ) int m,n,k,i;CNode

31、 *clist;clist=NULL;/*初始化 clist */printf("n 请输入围坐在圆桌周围的人数 n：");scanf("%d",&n);printf("n 请输入第一次开始报数人的位置 m：");scanf("%d",&m);printf("n 你希望报数到第几个数的人出列?");scanf("%d",&k);Create_clist(clist,n);/*创建一个有n 个结点的循环链表 clist */printf("n

32、出列的顺序如下：n");Joseph(clist,m,n,k);getch();/*main */【测试数据】1、请输入围坐在圆桌周围的人数 n：7请输入第一次开始报数人的位置 m：3你希望报数到第几个数的人出列? 2出列的顺序如下：4 6 1 3 7 5 22、请输入围坐在圆桌周围的人数 n：13请输入第一次开始报数人的位置 m：5你希望报数到第几个数的人出列? 6出列的顺序如下：10 3 9 4 12 7 5 2 6 11 8 1 133、请输入围坐在圆桌周围的人数 n：21请输入第一次开始报数人的位置 m：3你希望报数到第几个数的人出列? 9出列的顺序如下：11 20 8 18

33、 7 19 10 2 15 9 4 1 21 3 6 14 12 13 5 16 17【实验总结】熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；通过本章实验帮助学生加深对 C 语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）通过这个实验让我体会到做实验时,一定要亲力亲为,务必要将每个步骤,每个细节弄清楚,弄明白,实验后,还要复习,思考,这样,你的印象才深刻,记得才牢固。实验二栈和队列的应用【实验目的】1熟练掌握栈和队列的结构，以及这两种数据结构

34、的特点；2能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；3熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述【实验内容】1顺序栈的基本操作/*顺序栈的基本操作*/#include <stdio.h>#define MaxSize 100typedef char ElemType;typedef structchar stackMaxSize;int top; stacktype;void initstack(stacktype *S)S->top=-1;void push(stacktype *S,ElemType x

35、)if (S->top=MaxSize) printf("栈上溢出!n");elseS->top+;S->stackS->top=x;void pop(stacktype *S)if (S->top=-1) printf("栈下溢出!n");else S->top-;ElemType gettop(stacktype *S)if (S->top=-1) printf("栈空!n");else return(S->stackS->top);int empty(stacktype *S

36、)if (S->top=-1) return(1);else return(0);void display(stacktype *S)int i;printf("栈中元素:");for (i=S->top;i>=0;i-)printf("%c ",S->stacki);printf("n");main()stacktype *st;printf("建立一空栈n");initstack(st);printf("栈空:%dn",empty(st);printf("依

37、次插入 a,b,c,d 元素n");push(st,'a');push(st,'b');push(st,'c');push(st,'d');display(st);printf("退一次栈n");pop(st);printf("栈顶元素:%cn",gettop(st);printf("退一次栈n");pop(st);display(st);2链式栈的基本操作/*链式栈的基本操作*/#include <malloc.h>typedef char Ele

38、mType;typedef struct linknodeElemType data;struct linknode *next; linkstack;void initstack(linkstack *S)*S=NULL;void push(linkstack *S,ElemType x)linkstack *q;q=(linkstack *)malloc(sizeof(linkstack);q->data=x;q->next=*S;*S=q;void pop(linkstack *S)linkstack *t;if (*S=NULL) printf("栈下溢出!n&q

39、uot;);elset=*S;*S=t->next;free(t);ElemType gettop(linkstack *S)if (*S=NULL) return(-1);else return(*S)->data);int empty(linkstack *S)if (*S=NULL) return(1);else return(0);void display(linkstack *S)linkstack *q;printf("栈中元素:");q=*S;while (q!=NULL)printf("%c ",q->data);q=q

40、->next;printf("n");main()linkstack *stack;printf("建立一空栈n");initstack(&stack);printf("栈空:%dn",empty(&stack);printf("依次插入 a,b,c,d 元素n");push(&stack,'a');push(&stack,'b');push(&stack,'c');push(&stack,'d')

41、;display(&stack);printf("退一次栈n");pop(&stack);printf("栈顶元素:%cn",gettop(&stack);printf("退一次栈n");pop(&stack);display(&stack);3栈的应用/*栈的应用:求表达式值*/#include <stdio.h>#define MAX 100char expMAX; /*存储转换成的后缀表达式*/void trans() /*将算术表达式转换成后缀表达式*/char strMAX

42、; /*存储原算术表达式*/char stackMAX; /*作为栈使用*/char ch;int sum,i,j,t,top=0;/*t 作为 exp 的下标,top 作为 stack 的下标,i 作为 str 的下标*/printf("*n");printf("* 输入一个求值的表达式,以#结束。只能包含+,-,*,/运算符和正整数*n");printf("*n");printf("算术表达式:");i=0; /*获取用户输入的表达式*/doi+;scanf("%c",&stri);

43、 while (stri!='#' && i!=MAX);sum=i; /*记录输入表达式总的字符个数*/t=1;i=1;ch=stri;i+;while (ch!='#')switch(ch)case '(': /*判定为左括号*/top+;stacktop=ch;break;case ')': /*判定为右括号*/while (stacktop!='(')expt=stacktop;top-;t+;top-;break;case '+': /*判定为加减号*/case '

44、-':while (top!=0 && stacktop!='(')expt=stacktop;top-;t+;top+;stacktop=ch;break;case '*': /*判定为'*'或'/'号*/case '/':while (stacktop='*' | stacktop='/')expt=stacktop;top-;t+;top+;stacktop=ch;break;case ' ':break;default:while (c

45、h>='0' && ch<='9') /*判定为数字*/expt=ch;t+;ch=stri;i+;i-;expt='#'t+;ch=stri;i+;while (top!=0)expt=stacktop;t+;top-;expt='#'printf("nt 原来表达式:");for (j=1;j<sum;j+) printf("%c",strj);printf("nt 后缀表达式:",exp);for (j=1;j<t;j+) p

46、rintf("%c",expj);void compvalue() /*计算后缀表达式的值*/float stackMAX,d; /*作为栈使用*/char ch;int t=1,top=0; /*t 作为 exp 的下标,top 作为 stack 的下标*/ch=expt;t+;while (ch!='#')switch (ch)case '+':stacktop-1=stacktop-1+stacktop;top-;break;case '-':stacktop-1=stacktop-1-stacktop;top-;bre

47、ak;case '*':stacktop-1=stacktop-1*stacktop;top-;break;case '/':if (stacktop!=0)stacktop-1=stacktop-1/stacktop;elseprintf("nt 除零错误!n");exit(0);/*异常退出*/top-;break;default:d=0;while (ch>='0' && ch<='9') /*判定为数字字符*/d=10*d+ch-'0' /*将数字字符转换成对

48、应的数值*/ch=expt;t+;top+;stacktop=d;ch=expt;t+;printf("nt 计算结果:%gn",stacktop);main()trans();compvalue();4 顺序队的基本操作/*顺序队的基本操作*/#include <stdio.h>#define MaxSize 100typedef char ElemType;typedef structElemType queueMaxSize;int front,rear; queuetype;void initqueue(queuetype *Q)Q->front=

49、Q->rear=-1;void enter(queuetype *Q,ElemType x)if (Q->rear=MaxSize) printf("队列上溢出!n");elseQ->rear+; /*队尾指针后移*/Q->queueQ->rear=x; /*新元素赋给队尾单元*/void delete(queuetype *Q)if (Q->front=Q->rear)printf("队列为空!n");elseQ->front+;ElemType gethead(queuetype *Q)if (Q-&g

50、t;front=Q->rear)printf("队列为空!n");elsereturn(Q->queueQ->front+1);int empty(queuetype *Q)if (Q->front=Q->rear) return(1); /*为空,则返回 true*/else return(0); /*不为空,则返回 flase*/void display(queuetype *Q)int i;printf("队列元素:");for (i=Q->front+1;i<=Q->rear;i+)printf(&

51、quot;%c ",Q->queuei);printf("n");main()queuetype *qu;printf("初始化队列 qun");initqueue(qu);printf("队列空:%dn",empty(qu);printf("依次入队 a,b,c,d 元素n");enter(qu,'a');enter(qu,'b');enter(qu,'c');enter(qu,'d');display(qu);printf(&quo

52、t;出队一次n");delete(qu);printf("队首元素:%cn",gethead(qu);printf("出队一次n");delete(qu);display(qu);5循环队的基本操作/*循环队的基本操作*/#include <stdio.h>#define MaxSize 4typedef char ElemType;typedef structElemType queueMaxSize;int front,rear; queuetype;void initqueue(queuetype *Q)Q->front

53、=Q->rear=-1;void enter(queuetype *Q,ElemType x)if (Q->front=-1 && (Q->rear+1)=MaxSize)printf("队列上溢出!n"); /*front 处于初始状态,元素个数大于 MaxSize 时上溢出*/else if (Q->rear+1) % MaxSize = Q->front)printf("队列上溢出!n");elseQ->rear=(Q->rear+1) % MaxSize; /*队尾指针后移*/Q->

54、queueQ->rear=x; /*新元素赋给队尾单元*/void delete(queuetype *Q)if (Q->front=Q->rear)printf("队列为空!n");elseQ->front=(Q->front+1) % MaxSize;ElemType gethead(queuetype *Q)if (Q->front=Q->rear)printf("队列为空!n");elsereturn(Q->queue(Q->front+1) % MaxSize);int empty(queu

55、etype *Q)if (Q->front=Q->rear) return(1); /*为空,则返回 true*/else return(0); /*不为空,则返回 flase*/void display(queuetype *Q)int i=Q->front+1;if (!empty(Q)printf("队列元素:");while (i % MaxSize)!=Q->rear)printf("%c ",Q->queuei+ % MaxSize);if (Q->rear!=-1) /*不为初始状态时显示 rear 所指

56、元素*/printf("%c",Q->queuei % MaxSize);printf("n");else printf("队列为空,不能显示n");main()queuetype *qu;printf("初始化队列 qun");initqueue(qu);printf("队列空:%dn",empty(qu);printf("依次入队 a,b,c,d,e 元素n");enter(qu,'a');enter(qu,'b');enter(qu

57、,'c');enter(qu,'d');enter(qu,'e');display(qu);printf("出队三次n");delete(qu);delete(qu);delete(qu);display(qu);printf("依次入队 x,y 元素n");enter(qu,'x');enter(qu,'y');display(qu);printf("出队三次n");delete(qu);delete(qu);delete(qu);display(qu)

58、;printf("出队一次n");delete(qu);6链式队的基本操作/*链式队的基本操作*/#include <stdio.h>typedef char ElemType;struct qnodeElemType data;struct qnode *next;typedef struct queuestruct qnode *front;struct qnode *rear; linkqueue;void initqueue(linkqueue *Q)Q=(struct queue *)malloc(sizeof(struct queue);Q->

59、front=Q->rear=NULL;void enter(linkqueue *Q,ElemType x)linkqueue *s;s=(struct queue *)malloc(sizeof(struct queue);s->data=x;s->next=NULL;if (Q->rear=NULL) /*若链队为空,则新结点是队首结点又是队尾结点*/Q->front=Q->rear=s;elseQ->rear->next=s; /*将 s 结点链到队尾,rear 指向它*/Q->rear=s;void delete(linkqueue *Q)linkqueue *t;if (Q->front=NULL)printf("队列为空!n");else if (Q->front=Q->rear) /*只有一个结点时*/t=Q->front;Q->front=Q->rear=NULL;elset=Q->front;Q->front=Q->front->next;fr