《2013级本数据结构实验教案》由会员分享，可在线阅读，更多相关《2013级本数据结构实验教案（36页珍藏版）》请在金锄头文库上搜索。
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. 线性表的逆置：设有一个线性表（e0, e1, , en-2, en-1），请编写一个函数将这个线性表原地逆置，即将线性表内容置换为（en-1, en-2, , e1, e0）。线性表中的数据可以为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。3. 约瑟夫环的实现：设有n个人围坐一圈，用整数序列1, 2, 3, , n表示顺序围坐在圆桌周围的人， 现从某个位置 s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到
3、m的人出列，如此下去，直到所有人都出列为此。试设计确定他们的出列次序序列的程序。如 n=8, m=4 ,s=1时， 设每个人的编号依次为 1，2，3，开始报数，则得到的出列次序为4，8，5，2，1，3，7，6。检查程序的正确性和健壮性。(1)采用数组表示作为求解过程中使用的数据结构。(2) 采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点,必须注意空表和非空表的界限。4. 数制转换： 利用顺序栈和链栈实现数制转换5. 二叉树的遍历：分别以顺序存储结构和二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。6. 赫夫曼树与赫夫曼编码：已知某系统在通信联络中只可能出现
4、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树，对上面的编码结果译码。译码的过程是分解电文中的字符串，从根结点出发，按字符0和1确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。(4) 打印Huffman树。7. 学生成绩管理查询系统：每
5、个学生的数据信息有准考证号（主关键字）、姓名、语文、英语、数学、和总分等数据项，所有学生的信息构成一个学生成绩表。假设准考证号的头两位表示地区编号。请设计一个管理系统达到如下基本要求：（1） 初始化：建立一个学生成绩表，输入准考证号、姓名、语文、英语、数学，然后计算每个学生的总分，存入相应的数据项；注意：分析数据对象和它们之间的关系，并以合适的方式进行组织（可选择无序的顺序表、有序的顺序表或索引顺序表来进行存储表示）；（2） 查找：综合应用基本查找算法完成数据的基本查询工作，并输出查询的结果；（3） 输出：有选择性地输出满足一定条件的数据记录，如输出地区编号为01，并且总分在550分以上的学生
6、的信息；（4） 计算：计算在等概率情况下该查找表的平均查找长度。8. 排序：编制程序让机器随机产生2000个整数，放入一个数组中；对此2000个随机数序列分别用冒泡排序、快速排序、希尔排序和堆排序方法进行排序，并比较它们的运行时间。注意：每三、四个同学组成一个小组。每个实验中的题目，可分别由不同的同学完成。其它题目可以相互交流，以利于互相提高。数据结构验证性实验项目实验一 线性表的顺序存储一、实验目的及要求1、掌握在TC环境下调试顺序表的基本方法2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现。二、实验学时2学时三、实验任务1、 生成一个顺序表并动态地删除任意元素和
7、在任意位置插入元素。2、 将两个有序表合并成一个有序表。四、实验重点、难点1、 在顺序表中移动元素。2、 在顺序表中找到正确的插入位置。五、操作要点 (一)顺序表基本操作的实现问题描述 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。基本要求 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。实现提示 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。程序实现#include #include typede
8、f 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(*L).length +1) printf( n i 值不合法 ! ); return 0;if(* L).length =maxnum-1) printf( n 表满不能插入!); return 0; for(j=(*L).length;j=i;j-) (*
9、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 删除位置错误 ! ) ;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 ;pr
10、intf(请输入顺序表 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*/printout(SeqList * L) int i ;for (i=0 ; i=(* L).length ; i+) printf( data%d=, i) ; printf(%d, (*L).datai);/*printout */printf(n);main() SeqList *
11、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!=D)&(cmd!=q)&(cmd!=Q);switch(cmd) case i: case I:printf(nPlease input the DATA: );scanf(%d,&x) ;printf(nWhere? );scanf(%d,&i) ;ins
12、ert(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);（二）有序顺序表的合并问题描述 已知顺序表la和lb中的数据元素按非递减有序排列，将la和lb表中的数据元素，合并成为一个新的顺序表lc基本要求 lc中的数据元素仍按非递减有序排列，并且不破坏la和lb表程序实现#include#include# define OK 1# define ERROR 0/* 定义Elem
13、Type为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 int 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 for Creating a LinkListp-next=L-next;L-next=p;/end of forif(n) printf(Suc
