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

DONGFANG COLLEGE，FUJIAN AGRICULTURE AND FORESTRY UNIVERSITY课程名称：数据结构系 别：计算机系年级专业：2010级电子信息工程学 号： 1050302103姓名： 廖少兵任课教师： 谢储辉成绩：2012年12月25日实验一 线性表及其应用【实验目的】1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4. 通过本章实验帮助学生加深对 C 语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。【实验内容】1 线性表顺序存储的基本操作参考程序：/*线性表顺序存储的基本操作*/#include #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 (ip-size)return(-1);elsereturn(p-listi-1);int locate(struct List *p,ElemType x)int i=0;while (isize & 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 (ip-size+1)printf(位置参数不正确,不能进行插入操作!n);elsep-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 (ip-size | i1)printf(位置参数不正确,不能进行删除操作!n);elsefor (j=i-1;jsize-1;j+) /*结点向前移动,覆盖该删除的结点*/p-listj=p-listj+1;p-size-;display(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;jsize-1;j+)printf(%c,p-listj);printf(%c,p-listj); /*显示最后一个结点*/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,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 个结点后);delete(&L,1);display(&L);2 线性表链式存储的基本操作/*线性表链式存储-单链表的基本操作*/#include #include 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-next;return(n);ElemType get(struct LNode *p,int i)int j=1;struct LNode *q=*p;while (jnext;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 & 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=1) /*插入的结点作为头结点*/s-next=q;*p=s;elsewhile (jnext!=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=*p,*t;if (i=1) /*删除链表的头结点*/t=q;*p=q-next;elsewhile (jnext!=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) /*在 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,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);insert(&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(删除第 5 个结点:);delete(&head,5);display(&head);printf(删除开头 3 个结点:);delete(&head,3);delete(&head,2);delete(&head,1);display(&head);3 双链表的基本操作/*双链表的基本操作*/#include #include typedef char ElemType;struct DNodeElemType data;struct DNode *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 (jright;j+;if (q!=NULL) /*找到了第 i 个结点*/return(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 DNode *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 (jright!=NULL) /*查找第i-1 个结点*/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);void 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 (jright!=NULL) /*查找第i-1 个结点*/q=q-right;j+;if (q-right!=NULL & j=i-1) /*找到第 i-1 个结点,由 q 指向它*/t=q-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(双链表显示:);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);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,length(&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(删除开头 3 个结点:);delete(&dhead,3);delete(&dhead,2);delete(&dhead,1);display(&dhead);4 顺序表的应用约瑟夫问题的实现【问题描述】设有 n 个人围坐在圆桌周围，现从某个位置 m（1mn）上的人开始报数，报数到 k的人就站出来。下一个人，即原来的第k+1 个位置上的人，又从1 开始报数，再报数到 k的人站出来。依此重复下去，直到全部的人都站出来为止。试设计一个程序求出出列序列。这是一个使用循环链表的经典问题。因 为要不断地出列，采用链表的存储形式能更好地模拟出列的情况。【数据描述】建立一个不带头结点的循环链表，其中的 n 个人用 n 个结点来表示。Typedef int Elemtype;Typedef struct Cnode Elemtype data;struct Cnode *next;CNode;【C 源程序】#include #include #define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int Elemtype;/*定义数据元素类型 */typedef struct Cnode 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-next=clist; /*把链表的最后一个结点的链域指向链表的第一个结点，构成循环链表 */joseph=clist; /*把创建好的循环链表头指针赋给全局变量 */return OK; /*end */Status Joseph(CNode *clist,int m,int n,int k) int i;CNode *p,*q;if(mn) return ERROR;/*起始位置错 */if(!Create_clist(clist,n)return ERROR; /*循环链表创建失败 */p=joseph; /*p 指向创建好的循环链表 */for(i=1;inext; /*p 指向 m 位置的结点 */while(p) for(i=1;inext; /* 找出第 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 *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 出列的顺序如下：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 7 19 10 2 15 9 4 1 21 3 6 14 12 13 5 16 17【实验总结】 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；通过本章实验帮助学生加深对 C 语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）通过这个实验让我体会到做实验时,一定要亲力亲为,务必要将每个步骤,每个细节弄清楚,弄明白,实验后,还要复习,思考,这样,你的印象才深刻,记得才牢固。实验二 栈和队列的应用【实验目的】1熟练掌握栈和队列的结构，以及这两种数据结构的特点；2能够在两种存储结构上实现栈的基本运算，特 别注意栈满和栈空的判断条件及描述方法；3 熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述【实验内容】1 顺序栈的基本操作/*顺序栈的基本操作*/#include #define MaxSize 100typedef char ElemType;typedef structchar stackMaxSize;int top; stacktype;void initstack(stacktype *S)S-top=-1;void push(stacktype *S,ElemType x)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)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(依次插入 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 typedef char ElemType;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);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-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);display(&stack);printf(退一次栈n);pop(&stack);printf(栈顶元素:%cn,gettop(&stack);printf(退一次栈n);pop(&stack);display(&stack);3 栈的应用/*栈的应用:求表达式值*/#include #define MAX 100char expMAX; /*存储转换成的后缀表达式*/void trans() /*将算术表达式转换成后缀表达式*/char strMAX; /*存储原算术表达式*/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); 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 -: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 (ch=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;jsum;j+) printf(%c,strj);printf(nt 后缀表达式:,exp);for (j=1;j=0 & ch=9) /*判定为数字字符*/d=10*d+ch-0; /*将数字字符转换成对应的数值*/ch=expt;t+;top+;stacktop=d;ch=expt;t+;printf(nt 计算结果:%gn,stacktop);main()trans();compvalue();4 顺序队的基本操作/*顺序队的基本操作*/#include #define MaxSize 100typedef char ElemType;typedef structElemType queueMaxSize;int front,rear; queuetype;void initqueue(queuetype *Q)Q-front=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-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;irear;i+)printf(%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(出队一次n);delete(qu);printf(队首元素:%cn,gethead(qu);printf(出队一次n);delete(qu);display(qu);5循环队的基本操作/*循环队的基本操作*/#include #define MaxSize 4typedef char ElemType;typedef structElemType queueMaxSize;int front,rear; queuetype;void initqueue(queuetype *Q)Q-front=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-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(queuetype *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 所指元素*/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,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);printf(出队一次n);delete(qu);6链式队的基本操作/*链式队的基本操作*/#include 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-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;free(t);ElemType gethead(linkqueue *Q)if (Q-front=Q