数据结构c语言版实验教案

1、数据结构实验教案授课教师：许四平适用专业：信息与计算科学使用班级：13信计1、2 授课时间：2015年秋季授课学时：14学时使用教材：数据结构 严蔚敏 主编实验指导书：数据结构实验指导书，数理学院编，2012年版湖北理工学院数理学院实 验 安 排 表周次日期实验课题学时实验报告次数43.24实验一线性表的顺序存储实验（验证性）2学时143.25实验一线性表的顺序存储实验（验证性）2学时153.31 实验二单链表实验（验证性）2学时154.1实验二单链表实验（验证性）2学时164.7实验三 栈、队列（验证性）3学时164.8实验三 栈、队列（验证性）3学时1105.5实验四 树与二叉树（验证性）

2、4学时1105.6实验四 树与二叉树（验证性）4学时113 5.26实验五 查找（验证性）3学时113 5.27实验五 查找（验证性）3学时1数据结构设计性实验项目1. 线性表的合并：已知线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。分别采用顺序存储结构和链式结构来实现。2. 线性表的逆置：设有一个线性表（e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1, en-2, , e1, e0）。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。3. 约瑟夫

3、环的实现：设有n个人围坐一圈，用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人， 现从某个位置 s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。如 n=8, m=4 ,s=1时， 设每个人的编号依次为 1，2，3，开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。检查程序的正确性和健壮性。(1)采用数组表示作为求解过程中使用的数据结构。(2) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。4. 数制转换： 利用顺序栈和

4、链栈实现数制转换5. 二叉树的遍历：分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。6. 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现8种字符a,b,c,d,e,f,g,h，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计Huffman编码，并计算其平均码长。(1) 初始化：从键盘读入8个字符，以及它们的权值，建立Huffman树。(2)编码：根据建立的Huffman树，求每个字符的Huffman编码。对给定的待编码字符序列进行编码。(3) 译码：利用已经建立好的Huffman树，对上面的编码

5、结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。(4) 打印 Huffman树。7. 学生成绩管理查询系统：每个学生的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。请设计一个管理系统达到如下基本要求：（1） 初始化：建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：分析数据对象和它们之间的关系，并以合适的方式进行组织（可选择无序的顺序表、有序的顺序表或索引顺序

6、表来进行存储表示）；（2） 查找：综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；（3） 输出：有选择性地输出满足一定条件的数据记录，如输出地区编号为"01"，并且总分在550分以上的学生的信息；（4） 计算：计算在等概率情况下该查找表的平均查找长度。 8. 排序：编制程序让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。注意：每三、四个同学组成一个小组。每个实验中的题目，可分别由不同的同学完成。其它题目可以相互交流，以利于互相提高。数据结构验证性实验项

7、目实验一 线性表的顺序存储一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。二、实验学时2学时三、实验任务1、 生成一个顺序表并动态地删除任意元素和在任意位置插入元素。2、 将两个有序表合并成一个有序表。四、实验重点、难点1、 在顺序表中移动元素。2、 在顺序表中找到正确的插入位置。五、操作要点 (一)顺序表基本操作的实现问题描述 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第

8、i个元素之后的所有元素前移一个位置。基本要求 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。实现提示 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。程序实现#include <stdio.h>#include <conio.h>typedef int DataType ;# define maxnum 20typedef structint datamaxnum;int length;SeqList;/*插入函数*/int insert(SeqList *L , int i , DataType x)/* 将新结点x插入到顺序表L第i个位置

9、 */ int j ;if( i<0 | i>(*L).length +1) printf(" n i 值不合法 ! "); return 0;if(* L).length >=maxnum-1) printf(" n 表满不能插入!"); return 0; for(j=(*L).length;j>=i;j-) (*L).dataj+1=(*L).dataj;(*L).datai = x;(*L).length+;return 1;/*删除函数*/int delete( SeqList *L ,int i) /*从顺序L中删除第

10、i个结点*/ int j ;if( i<0| i>(*L).length ) printf(" n 删除位置错误 ! ") ;return 0;for(j=i+1;j<=(*L).length;j+)(*L).dataj-1 =(*L).dataj;(*L).length-;return 1;/*生成顺序表*/void creatlist(SeqList * L) int n , i , j ;printf("请输入顺序表 L 的数据个数：n") ;scanf("%d" , &n) ;for(i=0 ; i&

11、lt;n ; i+) printf("data%d =" , i) ; scanf("%d",&(*L).datai);(*L).length=n-1;printf("n") ;/*creatlist */*输出顺序表 L*/printout(SeqList * L) int i ;for (i=0 ; i<=(* L).length ; i+) printf(" data%d=", i) ; printf("%d", (*L).datai);/*printout */printf

12、("n");main() SeqList *L ;char cmd ;int i , t , x;clrscr() ;creatlist(L);doprintf("ni , I - 插入n") ;printf("d , D - 删除n") ;printf("q , Q - 退出n") ;docmd=getchar() ;while(cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='

13、;D')&&(cmd!='q')&&(cmd!='Q');switch(cmd) case 'i': case 'I':printf("nPlease input the DATA: ");scanf("%d",&x) ;printf("nWhere? ");scanf("%d",&i) ;insert(L,i,x) ;printout(L);break ;case 'd':cas

14、e 'D' :printf("nWhere to Delete? ");scanf("%d",&i);delete(L,i);printout(L);break ;while(cmd!='q')&&(cmd!='Q');（二）有序顺序表的合并问题描述 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc基本要求 lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表程序实现#include<stdio.h>#incl

15、ude<stdlib.h># define OK 1# define ERROR 0/* 定义ElemType为int或别的自定义类型 */typedef int ElemType;/* 链式存储类型 */typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/* 单链表的建立(头插法)*/void CreateList_L(LinkList &L,int n) /CreateList_L() function /To Creatre a LinkList L with HeadNode i

16、nt i;LNode *p;L=(LinkList)malloc(sizeof(LNode);L->next=NULL;printf("Please input the data for LinkList Nodes: n");for(i=n;i>0;-i)p=(LinkList)malloc(sizeof(LNode);scanf("%d",&p->data); /Reverse order inputing for Creating a LinkListp->next=L->next;L->next=p;/

17、end of forif(n) printf("Success to Create a LinkList !n");else printf("A NULL LinkList have been created !n");/end of CreateList() function void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)LinkList pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&a

18、mp;pb)if(pa->data<=pb->data)pc->next=pa;pc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;free(Lb);void main()LinkList La,Lb,Lc,p;int n;printf("请输入La的长度n:");scanf("%d",&n);CreateList_L(La,n);printf("输出La的内容：");p=La->nex

19、t;while(p)printf("%d->",p->data);p=p->next;printf("n");printf("请输入Lb的长度n:");scanf("%d",&n);CreateList_L(Lb,n);printf("输出Lb的内容：");p=Lb->next;while(p)printf("%d->",p->data);p=p->next;printf("n");MergeList_L(

20、La,Lb,Lc);printf("输出Lc的内容：");p=Lc->next;while(p)printf("%d->",p->data);p=p->next;printf("n");六、注意事项1、 删除元素或插入元素表的长度要变化。2、 在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的元素复制到总表去即可。实验二 单链表一、实验目的及要求1、掌握用在TC环境下上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现3、进一步掌握循环单链表的插入、删除、查找算

21、法的实现二、实验学时2学时三、实验任务1、在带头结点的单链表h中第i个数据元素之前插入一个数据元素。2、将两个有序单链表合并成一个有序单链表。3、生成一个循环单链表。4、在循环单链表中删除一个节点。四、实验重点、难点1、 在单链表中寻找到第i-1个结点并用指针p指示。2、 比较两个单链表的节点数据大小。3、循环单链表中只有一个节点的判断条件。4、在循环单链表中删除一个节点。五、操作要点（一）单链表基本操作的实现1、实现栈的顺序存储和链式存储。#include<stdio.h>#include<stdlib.h># define STACK_INIT_SIZE 100#

22、define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1# define ERROR 0/* 定义SElemType为int或别的自定义类型 */typedef int SElemType;/*链式栈的存储类型*/typedef struct SNode SElemType data; struct SNode *next;SNode,*LinkStack;/*取链式栈顶元素*/int GeTop_L(LinkStack top,SElemType &e) if(!top->next) printf("Erro

23、r!It's an empty LinkStack!n");return (ERROR); else e=top->next->data;return (OK); /*将元素压入链式栈*/int Push_(LinkStack top,SElemType &e) SNode *q; q=(LinkStack)malloc(sizeof(SNode); q->data=e; q->next=top->next; top->next=q; return(OK);/*将元素弹出链式栈*/int Pop_L(LinkStack top,SE

24、lemType &e)SNode *q;e=top->next->data;q=top->next;top->next=q->next;free(q);return(OK);/* 定义SElemType为int或别的自定义类型 */typedef int SElemType;/* 顺序栈的存储类型 */typedef struct/define structure SqStack() SElemType *base; SElemType *top; int stacksize;SqStack;/*构造空顺序栈*/int InitStack(SqStack

25、&S)/InitStack() sub-function S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) printf("Allocate space failure !n");return (ERROR); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return (OK); /InitStack() end/*取顺序栈顶元素*/int GetTop(SqStack S,SElemType &e)/GetTop() s

26、ub-function if(S.top=S.base) printf("It's a empty SqStack !n");/if empty SqStack return (ERROR); e=*(S.top-1); return (OK); /GetTop() end/*将元素压入顺序栈*/int Push(SqStack &S,SElemType e)/Push() sub-function *S.top+=e; return (OK); /Push() end/* 将元素弹出顺序栈*/int Pop(SqStack &S,SElemType

27、 &e)/Pop() sub-function e=*-S.top; return (OK); /Pop() end void main()int i,j;SqStack s;LinkStack s1;SElemType e;InitStack(s);s1=(LinkStack)malloc(sizeof(SNode);s1 -> next = NULL;printf("顺序栈的元素：n");for(i=1;i<=8;i+)scanf("%d",&e);Push(s,e);printf("顺序栈出栈：n")

28、;for(i=1;i<=8;i+)Pop(s,e);printf("%d ",e);printf("n");printf("链式栈的元素：n");for(j = 1;j<=8;j+)scanf("%d",&e);Push_(s1,e);printf("链式栈出栈：n");while(NULL != s1 -> next)Pop_L(s1,e);printf("%d ",e);printf("n");2、利用顺序栈或链栈实现数制转换

29、。#include<stdio.h>#include<stdlib.h># define STACK_INIT_SIZE 100# define STACKINCREMENT 10# define MAXQSIZE 100# define OK 1# define ERROR 0 /* 定义SElemType为int或别的自定义类型 */typedef int SElemType;/* 顺序栈的存储类型 */typedef struct/define structure SqStack() SElemType *base; SElemType *top; int sta

30、cksize;SqStack; /*构造空顺序栈*/int InitStack(SqStack &S)/InitStack() sub-function S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) printf("Allocate space failure !n");return (ERROR); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return (OK); /InitStack() endint StackEmp

31、ty(SqStack S)if(S.top=S.base)return OK;elsereturn ERROR;/*取顺序栈顶元素*/int GetTop(SqStack S,SElemType &e)/GetTop() sub-function if(S.top=S.base) printf("It's a empty SqStack !n");/if empty SqStack return (ERROR); e=*(S.top-1); return (OK); /GetTop() end/*将元素压入顺序栈*/int Push(SqStack &

32、;S,SElemType e)/Push() sub-function *S.top+=e; return (OK); /Push() end/* 将元素弹出顺序栈*/int Pop(SqStack &S,SElemType &e)/Pop() sub-function e=*-S.top; return (OK); /Pop() end/*利用顺序栈实现对于输入的任意一个非负十进制整数，输出与其等值的八进制数。*/void Conversion() SqStack S; SElemType N,e; InitStack(S); scanf("%u",&am

33、p;N); while(N) Push(S,N%8); N=N/8; printf("Conversed to Oct.number="); while(!StackEmpty(S) Pop(S,e); printf("%d",e); printf("n"); void main() Conversion(); 3、实现循环队列的存储和链队列的基本操作。 #include<stdio.h>#include<stdlib.h># define OK 1# define ERROR 0typedef int QEl

34、emType;/* 链队列的存储类型 */typedef struct QNode/define structure QNode QElemType data; struct QNode *next;QNode,*QueuePtr;typedef struct LinkQueue/define structure LinkQueue QueuePtr front; QueuePtr rear;LinkQueue;/*构造空链式队列*/int InitQueue(LinkQueue &Q)/InitQueue() sub-function Q.front=Q.rear=(QueuePtr

35、)malloc(sizeof(QNode); if(!Q.front) printf("Overflow !n"); return (ERROR); Q.front->next=NULL; return (OK); /InitQueue() end/* 销毁链式队列*/int DestroyQueue(LinkQueue &Q)/DestroyQueue() sub-function while(Q.front) Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; return (OK); /Dest

36、royQueue() end/* 在链式队列尾插入新元素*/int EnQueue(LinkQueue &Q,QElemType e)/EnQueue() sub-function QNode *p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) printf("Overflow !n"); return (ERROR); p->data=e; p->next=NULL; if(Q.front=NULL) Q.front=Q.rear=p; return (OK); Q.rear->next=p; Q.rear=

37、p; return (OK); /EnQueue() end/*在链式队列头删除旧元素*/int DeQueue(LinkQueue &Q,QElemType &e)/DeQueue() sub-function if(Q.front=Q.rear) printf("If it was deleted, it's empty !n"); return (ERROR); QNode *p; p=Q.front->next; e=p->data; Q.front->next=p->next; free(p); return (OK

38、); /DeQueue() endvoid main()LinkQueue L;int i, n, e;if(!InitQueue(L)exit(0);printf("请输入要写入队列的元素的个数："); scanf("%d",&n); printf("请输入要写入队列的元素："); for(i = 0; i< n;i+) scanf("%d",&e); if(EnQueue(L, e) break; DeQueue(L,e); printf("删除的元素为%dn", e)

39、; if(DestroyQueue(L)printf("销毁队列成功。n"); 六、注意事项 1、在第i个节点前删除或插入节点需要用指针来表示第i-1个节点。2、在合并链表时需要设置多个指针变量。3、如果不是要删除的节点则指针后移，否则删除该节点。七、思考题1、编程实现两个循环单链表的合并。实验三 栈、队列一、实验目的及要求1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用。2、掌握栈和队列的特点，即先进后出与先进先出的原则。3、掌握栈和队列的基本操作实现方法。二、实验学时3学时三、实验任务1. 实现栈的顺序存储2. 利用栈实现数制转换四、实验重点、难点

40、1. 进栈、出栈栈顶指针都要改变。2. 数制转换结束的判断条件。五、操作要点（一）实现栈的顺序存储# define MAXSIZE 100 typedef int ElemType;typedef struct ElemType dataMAXSIZE; int top;SeqStack; void InitStack(SeqStack *s) s->top=0; return 1;int StackEmpty(SeqStack *s) if(s->top=0) return 1; else return 0;int StackFull(SeqStack *s) if(s->

41、top=MAXSIZE-1) return 1; else return 0; void Push(SeqStack *s,int x) if (StackFull(s) printf("the stack is overflow!n"); return 0; else s->datas->top=x; s->top+; void Display(SeqStack *s) if(s->top=0) printf("the stack is empty!n"); else while(s->top!=0) printf(&qu

42、ot;%d->",s->datas->top); s->top=s->top-1; ElemType Pop(SeqStack *s) if(StackEmpty(s) return 0; else return s->data-s->top; ElemType StackTop(SeqStack *s) int i;if(StackEmpty(s) return 0; else i=s->top-1;return s->datai; /*返回栈顶元素的值，但不改变栈顶指针*/ main(SeqStack *p) int n,i,

43、k,h,x1,x2,select; printf("create a empty stack!n"); InitStack(p); printf("input a stack length:n"); scanf("%d",&n); for(i=0;i<n;i+) printf("input a stack value:n"); scanf("%d",&k); Push(p,k); printf("select 1:Display()n"); printf

44、("select 2:Push()n"); printf("select 3:Pop()n"); printf("select 4:StackTop()n"); printf("input a your select(1-4):n"); scanf("%d",&select); switch(select) case 1:Display(p); break; case 2:printf("input a push a value:n"); scanf("%d

45、",&h); Push(p,h); Display(p); break; case 3:x1=Pop(p); printf("x1->%dn",x1); Display(p); break; case 4:x2=StackTop(p);printf("x2->%d",x2);break; （二）利用栈实现数制转换 # define MAXSIZE 100typedef int ElemType； /*将顺序栈的元素定义为整型*/typedef struct ElemType dataMAXSIZE; int top;SeqS

46、tack; void InitStack(SeqStack *s) s->top=0; return 1;int StackEmpty(SeqStack *s) if(s->top=0) return 1; else return 0;int StackFull(SeqStack *s) if(s->top=m-1) return 1; else return 0; void Push(SeqStack *s,int x) if (StackFull(s) printf("the stack is overflow!n"); return 0; else

47、s->datas->top=x; s->top+; ElemType Pop(SeqStack *s) ElemType y; if(StackEmpty(s) printf("the stack is empty!n"); return 0; else y=s->datas->top; s->top=s->top-1; return y; ElemType StackTop(SeqStack *s) if(StackEmpty(s) return 0; else return s->datas->top;void De

48、c_to_Ocx (int N) /* n是非负的十进制整数，输出等值的八进制数*/SeqStack *S； /*定义一个顺序栈*/ElemType x； Init_SeqStack(S)； /*初始化栈*/if(N<0) printf("nError,The number must be over 0。")； return； if(!N) Push(S,0)；while(N) /*自右向左产生八进制的各位数字，并将其进栈*/ Push(S，N%8)； /*余数入栈 */ N=N/8； /*商作为被除数*/ printf("Number %d convert

49、ed to OCT:",N);while(StackEmpty(S) /*栈非空时退栈输出*/ x=Pop(S)； printf(“%d”,x)； printf("n"); main( ) int n; printf("Input a number to convert to OCT:n");scanf("%d",&n);Dec_to_Ocx (n);六、注意事项1、进栈、出栈栈顶指针都要改变。 2、数制转换余数入栈后商作为被除数。七、思考题1、实现循环队列的顺序存储实验四 树与二叉树一、实验目的及要求1、进一步掌握

50、指针变量、动态变量的含义。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。二、实验学时4学时三、实验任务1、 以二叉链表作存储结构，编写前序、中序、后序及层次顺序遍历二叉树的算法。2、 以二叉链表作存储结构，编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法四、实验重点、难点 1、前序、中序、后序及层次顺序遍历二叉树的算法。2、计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法。五、操作要点1、分别以顺序存储结构和二叉链表作存储结构，试编程实现前序、中序、后序及层次顺序遍历二

51、叉树的算法。 顺序存储结构：程序代码：#include<stdio.h>#include<iostream.h>#define OK 1#define ERROR 0#define MAX_TREE_SIZE 100typedef char TElemType ;typedef TElemType SqBiTreeMAX_TREE_SIZE;int Create(SqBiTree & bt,int &n)/层序创建二叉树的各个节点元素cout<<"'*'表示结束创建，'/'表示空节点"<

52、;<endl;TElemType c;int i=0;cout<<"请按层依次创建各个节点:"cin>>c;while(c!='*')bt+i=c;cin>>c; n=i;cout<<"二叉树创建完毕!"<<endl; return OK;int LevelOrderTraverse(SqBiTree bt,int n)/层序遍历int i; for( i=1;i<=n;i+) if(bti='/') continue; else if(i=n) co

53、ut<<bti; else cout<<bti<<"->" cout<<endl;return OK;int PreOrederTraverse(SqBiTree bt,int i,int n)/先序遍历if(i<=n) if(bti!='/') cout<<bti<<"->" if(2*i<=n) PreOrederTraverse(bt,2*i,n); if(2*i+1)<=n) PreOrederTraverse(bt,2*i+1,

54、n); return OK;int InOrederTraverse(SqBiTree bt,int i,int n)/中序遍历 if(2*i<=n) InOrederTraverse(bt,2*i,n);if(i<=n)if(bti!='/'&& i!=n ) cout<<bti<<"->"else if(bti!='/'&& i=n ) cout<<bti; if(2*i+1)<=n) InOrederTraverse(bt,2*i+1,n); return OK;int PosOrederTraverse(SqBiTree bt,int i,int n)/后序遍历 if(2*i<=n) PosOrederTraverse(bt,2*i,n); if(2*i+1)<=n) PosOrederTraverse(bt,2*i+1,n);if(i<=n)if(bti!='/'&&i!=1) cout<<bti<<"-&g