本数据结构实验教案

1、数据结构实验教案授课教师：许四平 适用专业：信息与计算科学 使用班级： 13 信计 1、2 授课时间： 2012 年秋季 授课学时： 14 学时使用教材：数据结构 严蔚敏 主编实验指导书：数据结构实验指导书， 数理学院编， 2012 年版湖北理工学院数理学院实验安排表周次日期实验课题学时实验报 告次数33.23线性表的顺序存储2133.26线性表的顺序存储2154.4单链表2154.9单链表2174.20栈、队列3174.23栈、队列3184.27树与二叉树2184.29树与二叉树2195.10树与二叉树2195.10树与二叉树21146.9查找31146.10查找31数据结构设计性实验项目1

2、. 线性表的合并：已知线性表 La 和 Lb 的元素按值非递减排列。归并 La 和 Lb 得 到新的线性表 Lc， Lc 的元素也按值非递减排列。分别采用顺序存储结构和链式结构来 实现。2. 线性表的逆置：设有一个线性表( eo, e 1,e n-2, e n-i)，请编写一个函数将这个线性表原地逆置，即将线性表内容置换为(en-i, e n-2,e i, e o)。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。3. 约瑟夫环的实现：设有 n 个人围坐一圈，用整数序列 i, 2, 3, , n 表示顺序围坐在圆桌周围的人，现从某个位置 s上的人开始报数，数到

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

4、序及层次顺序遍历二叉树的算法。6. 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现8 种字符a,b,c,d,e,f,g,h ,其概率分别为 o.o5 , o.29 , o.o7 , o.o8 , o.14 , o.23 , o.o3 , o.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 个元素时，也必须把第 i

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

9、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 中删除第 i 个结点 */ int j ;if( i(*L).length ) printf( n 删除位置错误 ! ) ;retur

10、n 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 ; in ; i+) printf(data%d = , i) ; scanf(%d,&(*L).datai);(*L).length=n-1;printf(n) ;/*creatlist */* 输出顺序表 L*/ print

11、out(SeqList * L) int i ;for (i=0 ; i=(* L).length ; i+) printf( data%d=, i) ;printf(%d, (*L).datai);/*printout */ printf(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) ;do cmd=getchar() ;while(cmd!=i)&(cmd!=I)&(cmd!=

12、d)&(cmd!=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:case D :printf(nWhere to Delete? );scanf(%d,&i);delete(L,i);printout(L); break ; while(cmd!=q)&(cmd!=Q); (二)有序顺序表的合并问题描述已知顺

13、序表la和lb中的数据元素按非递减有序排列，将 la和lb表中的数据元素，合并 成为一个新的顺序表 lc基本要求lc中的数据元素仍按非递减有序排列，并且不破坏 la和lb表 程序实现 #include#include# define OK 1# define ERROR 0/* 定义ElemType为int或别的自定义类型 */typedef int ElemType;/* 链式存储类型 */typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/* 单链表的建立 (头插法 )*/void CreateList

14、_L(LinkList &L,int n)/CreateList_L() function /To Creatre a LinkList L with HeadNodeint i;LNode *p;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;printf(Please input the data for LinkList Nodes: n); for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&p-data);/Reverse order inputing forCreating

15、a LinkListp-next=L-next; L-next=p;/end of forif(n) printf(Success to Create a LinkList !n);else printf(A NULL LinkList have been created !n); /end of CreateList() functionvoid MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) LinkList pa,pb,pc; pa=La-next;pb=Lb-next; Lc=pc=La;while(pa&pb) if(pa-da

16、tadata) pc-next=pa;pc=pa;pa=pa-next;else pc-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-next;while(p)printf(%d-,p-data); p=p-next;printf(n);printf( 请输入 Lb 的长度 n:); scanf(

17、%d,&n); CreateList_L(Lb,n);printf( 输出 Lb 的内容： ); p=Lb-next;while(p)printf(%d-,p-data); p=p-next;printf(n);MergeList_L(La,Lb,Lc); printf( 输出 Lc 的内容： ); p=Lc-next;while(p)printf(%d-,p-data); p=p-next;printf(n);六、注意事项1、删除元素或插入元素表的长度要变化。2、在合并表中当某一个表到表尾了就不用比较了，直接将另一个表的元素复制到 总表去即可。实验二 单链表、实验目的及要求1、掌握用在TC环

18、境下上机调试单链表的基本方法2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现3、进一步掌握循环单链表的插入、删除、查找算法的实现、实验学时2学时三、实验任务1、在带头结点的单链表 h中第i个数据元素之前插入一个数据元素。2、将两个有序单链表合并成一个有序单链表。3、生成一个循环单链表。4、在循环单链表中删除一个节点。四、实验重点、难点1、在单链表中寻找到第i-1个结点并用指针p指示。2、比较两个单链表的节点数据大小。3、循环单链表中只有一个节点的判断条件。4、在循环单链表中删除一个节点。五、操作要点 (一)单链表基本操作的实现1 、实现栈的顺序存储和链式存储。#inclu

19、de #include# define STACK_INIT_SIZE 100# 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,SE

20、lemType &e) if(!top-next) printf(Error!Its 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,SEle

21、mType &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 &S) /InitStack() s

22、ub-functionS.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() sub-functionif(S.top=S.base)printf(Its a

23、 empty SqStack !n);/if empty SqStackreturn (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 &e)/Pop() sub-functione=*-S.top;return (OK); /Pop() end void main

24、()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); for(i=1;i=8;i+)Pop(s,e); printf(%d ,e);printf(n);printf( 链式栈的元素： n); for(j = 1;j next) Pop_L(s1,e);printf(%d ,e

25、);printf(n);2、利用顺序栈或链栈实现数制转换。#include#include# 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 stac

26、ksize;SqStack;/* 构造空顺序栈 */int InitStack(SqStack &S)/InitStack() sub-functionS.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 StackEmpty(SqStack S)if(S.to

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

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

29、tackEmpty(S)Pop(S,e);printf(%d,e);printf(n);void main()Conversion();3、实现循环队列的存储和链队列的基本操作。#include#include# define OK 1# define ERROR 0 typedef int QElemType;/* 链队列的存储类型 */ typedef struct QNode/define structure QNode QElemType data;struct QNode *next; QNode,*QueuePtr;typedef struct LinkQueue/define s

30、tructure LinkQueue QueuePtr front;QueuePtr rear; LinkQueue;/* 构造空链式队列 */int InitQueue(LinkQueue &Q) /InitQueue() sub-function Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front) printf(Overflow !n); return (ERROR);Q.front-next=NULL;return (OK); /InitQueue() end/* 销毁链式队列 */int DestroyQueue(Lin

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

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

33、 e=p-data;Q.front-next=p-next; free(p);return (OK); /DeQueue() end void main()LinkQueue L; int i, n, e;if(!InitQueue(L) exit(0);printf( 请输入要写入队列的元素的个数： ); scanf(%d,&n);printf( 请输入要写入队列的元素： );for(i = 0; itop=0;return 1;int StackEmpty(SeqStack *s) if(s-top=0) return 1;else return 0;int StackFull(SeqSt

34、ack *s) if(s-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(%d-,s-datas-top);s-top=s-top-1;ElemType Po

35、p(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,k,h,x1,x2,select; printf(create a empty stack!n);InitStack(p); printf(input a stack length

36、:n); scanf(%d,&n);for(i=0;i%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;SeqStack;printf(n);void InitStack(SeqStack *s) s-top=0; return 1;int StackEmpty

37、(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 s-datas-top=x; s-top+;ElemType Pop(SeqStack *s) ElemType y;if(StackEmpty(s) printf(the stack i

38、s empty!n); return 0;else y=s-datas-top;s-top=s-top-1;return y; if(StackEmpty(s) return 0; else return s-datas-top;void Dec_to_Ocx (int N) /* nSeqStack *S ；/*ElemType x ；Init_SeqStack(S) ； /*ElemType StackTop(SeqStack *s)是非负的十进制整数，输出等值的八进制数 */ 定义一个顺序栈 */ 初始化栈 */if(N0) printf(nError,The number must b

39、e over 0。 ) ；return ；if(!N) Push(S,0) ； while(N) /* 自右向左产生八进制的各位数字，并将其进栈 */ Push(S， N%8；)/* 余数入栈 */N=N/8 ； /* 商作为被除数 */ printf(Number %d converted to OCT:,N);while(StackEmpty(S) /* 栈非空时退栈输出 */ x=Pop(S) ； printf( “%d” ,x) ；main( ) int n;printf(Input a number to convert to OCT:n);scanf(%d,&n);Dec_to_O

40、cx (n);六、注意事项1、进栈、出栈栈顶指针都要改变。2 、数制转换余数入栈后商作为被除数。七、思考题1、实现循环队列的顺序存储实验四 树与二叉树一、实验目的及要求1、进一步掌握指针变量、动态变量的含义。2、掌握二叉树的结构特性，以及各种存储结构的特点和适用范围。3、掌握用指针类型描述、访问和处理二叉树的运算。二、实验学时4学时三、实验任务1、 以二叉链表作存储结构， 编写前序、 中序、 后序及层次顺序遍历二叉树的算法。2、 以二叉链表作存储结构，编写计算二叉树深度、所有结点总数、叶子结点数、 双孩子结点个数、单孩子结点个数的算法四、实验重点、难点1、前序、中序、后序及层次顺序遍历二叉树的

41、算法。2、计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点 个数的算法。五、操作要点 1、分别以顺序存储结构和二叉链表作存储结构，试编程实现前序、中序、后序及层次 顺序遍历二叉树的算法。顺序存储结构：程序代码：#include#include#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

42、* 表示结束创建， /表示空节点 endl;TElemType c;int i=0;coutc;while(c!=*)bt+i=c;cinc;n=i;cout 二叉树创建完毕 !endl;return OK;int LevelOrderTraverse(SqBiTree bt,int n)/ 层序遍历 int i;for( i=1;i=n;i+)if(bti=/) continue;elseif(i=n) coutbti;elsecoutbti;coutendl;return OK;int PreOrederTraverse(SqBiTree bt,int i,int n)/ 先序遍历 if(

43、i=n) if(bti!=/) coutbti;if(2*i=n)PreOrederTraverse(bt,2*i,n);if(2*i+1)=n)PreOrederTraverse(bt,2*i+1,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 )coutbti;elseif(bti!=/& i=n ) coutbti;if(2*i+1)=n)InOrederTraverse(bt,2*i+1

44、,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)coutbti;if(i=1) coutbti;return OK;void main()cout 顺序存储结构二叉树 endl;SqBiTree Bt;int i=1;int Length;Create(Bt,Length);cout 该二叉树按层序遍历的遍历结

45、果为 :;LevelOrderTraverse(Bt,Length); coutendl 按先序遍历的结果为 :; PreOrederTraverse(Bt,i,Length);coutendl; coutendl 按中序遍历的结果为 :; InOrederTraverse(Bt,i,Length);coutendl; coutendl 按后序遍历的结果为 :; PosOrederTraverse(Bt,i,Length);coutendl; cout201240410111 周逊 endl;运行结果：二叉链表存储结构：程序代码：#include using namespace std; #d

46、efine ERROR 1 #define OK -1 typedef char TElemType;/* 二叉树节点的存储类型 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode, *BiTree;/* 建立二叉树 */ int CreateBiTree(BiTree &T) TElemType ch;cinch; if(ch=#) T=NULL; else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) coutdata=ch;CreateBiT

47、ree(T-lchild); /create lchild CreateBiTree(T-rchild); /create rchild return (OK);int PreOrderTraverse(BiTree T) if(T) coutdata;if (PreOrderTraverse(T-lchild) if (PreOrderTraverse(T-rchild) return (OK);return (ERROR); /if endelse return (OK); /PreOrderTraverse() end/PreOrderTravers sub-function/visite T/traverse lchild/traverse rchildint InOrderTraverse(BiTree T) /InOrderTraverse sub-function if(T) if (InOrderTraverse(T-lchild) /traver