《数据结构 实验指导手册》由会员分享，可在线阅读，更多相关《数据结构 实验指导手册（16页珍藏版）》请在金锄头文库上搜索。
1、数学与计算机科学学院计算机科学与技术专业数据结构课程实验指导手册目录实验1：顺序表的定义及其相关操作算法的实现 1实验2：链表的定义及其相关操作算法的实现 2实验3：栈和队列的定义及其基本操作算法的实现 4实验4：串模式匹配算法的设计与实现 5实验5：二叉树的创建、遍历及其它基本操作的实现 6实验6：哈夫曼树及哈夫曼编码的算法实现 7实验 7：查找算法的实现（1） 8实验 8：查找算法的实现（2） 9实验9：几个主要排序算法的实现与比较 10实验所需 学时数2学时实验目的1）熟悉VC环境下线性表在顺序存储结构中的实现方法2）熟练掌握顺序表的创建，插入，删除等基本操作算法的实现3）加强和深化C程
2、序的编写、编译和调试能力实验内容1）编程实现在顺序存储的有序表中插入一个兀素（数据类型为整型）2）编程实现把顺序表中从i个元素开始的k个元素删除（数据类型为整型）实验所需 器材计算机及VC+ 6.0软件内容要求：1）建立有序表：12, 23, 46, 67, 85插入元素分别为：5, 59, 94 验证代码的正确性2）建立顺序表：4, 5, 2, 1, 6, 3, 5测试数据：i=1, k=3 ;i=4, k=5 ;i=0, k=2分别验证代码的正确性实验结果：1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不
3、无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。实验所需 学时数2学时实验目的1）熟悉VC环境下线性表在链式存储结构中的实现方法2）熟练掌握单链表的创建，插入，删除等基本操作算法的实现3）提高C程序中指针的熟练运用能力4）训练学生利用链表的知识来解决实际问题，为今后的学习打好基础实验内容通讯录管理（必做内容）；约瑟夫环（选做内容）实验所需 器材计算机及VC+ 6.0软件必做内容要求：1.通讯者的结点类型定义如下:typedefstruct charnum5;编号charname9;姓名c
4、harsex3;性别charphone13;电话charaddr31;地址DataType ;2. 线性表的链式存储结构定义如下：typedef struct node 结点类型定义DataType data ;结点数据域struct node * next ; 结点指针域 ListNode ;typedef ListNode * LinkList ;ListNode * p ;定义一个指向结点的指针变量LinkList head ;定义指向单链表的头指针3. 主控菜单设计要求程序运行后，给出6个菜单项的内容和输入提示：1. 通讯录链表的建立2. 通讯者结点的插入3. 通讯者结点的查询4. 通
5、讯者结点的删除5. 通讯录链表的输出0.退出管理系统 请选择05使用数字05来选择菜单项，其他输入则不起作用。选做内容要求：约瑟夫（Joseph）问题的一种描述是：30个旅客同乘一条船，因为严重超载，加上风高浪 大，危险万分。因此船长告诉乘客，只有将全船一半的旅客投入海中，其余人才能幸免于难。 无奈，大家只好同意这种办法，并议定30个人围成一圈，由第一个人数起，依次报数，数到第 9人，便把他投入大海，然后再从他的下一个人数起，数到第9人，再将他扔进大海中，如此循 环地进行，直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置？1. 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的
6、编号。2. 为了不失一般性，将30改为一个任意输入的正整数n而报数上限（原为9）也为一个任选 的正整数k。这样该算法描述如下：（1）创建含有n个结点的单循环链表；（2）生者与死者的选择：p指向链表第一个结点，初始i置为1；while （iv=n/2）删除一半的结点 从p指向的结点沿链前进k-1步； 删除第k个结点（q所指向的结点）；p指向q的下一个结点； 输出其位置q-data；i自增1；（3）输出所有生者的位置。3. 测试结果对于总人数30,报数上限为9,则死者编号为：9，18，27，6，16，26，7，19，30，12，24，8，22，5，23生者编号为：1，2，3，4，10，11，13，
7、14，15，17，20，21，25，28，29实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。实验所需 学时数2学时实验目的1) 掌握栈和队列这两种特殊线性表的定义与实现。2) 通过解决实际问题，灵活运用栈和队列的特性，加深对这两种结构的理解和 认识。实验内容数制转换；回文判定实验所需 器材计算机及VC+ 6.0软件内容要求：1. 将十进制数N和其
8、他d进制数之间进行转换是计算机实现计算的基本问题，解决 方案很多，其中最简单的方法是除d取余法。例如，(1348) 10= (2504) 8,其转 化过程如下所示：NN div 8N mod 8134816841682102125202从中可以看出，最先产生的余数4是转换结果的最低位，这正好符合栈的“后进先出”的特性。 所以可以用顺序栈来模拟这个过程。2. 假设称正读和反读都相同的字符序列为“回文”，例如，abba和abcba是回文，abcde 和ababab则不是回文。请编写一个程序判别读入的一个以为结束符的字符序列是否是“回 文”。提示：由于依次输入的字符序列中不含特殊的分隔符，则在判别是
9、否是“回文”时，一种比较 合适的做法是，同时利用“栈”和“队列”两种结构。实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。实验 4：串模式匹配算法的设计与实现实验所需 学时数2学时实验目的1）熟悉串类型的实现方法和文本模式匹配方法2）熟悉如何利用模式匹配算法实现一般的文本处理技术实验内容顺序串的模式匹配算法实验所需 器材计算机及VC+ 6.0软件内
10、容要求：1. 在串的基本操作中，在主串中杳找模式串的模式匹配算法是文本处理中最常用、最重要 的操作之。所谓子串的定位就是求子串在主串中首次出现的位置，又称为模式匹配或 串匹配。模式匹配的算法很多，在这里只要求用最简单的朴素模式匹配算法。2. 顺序串的类型定乂如下：# define MaxStrSize 256可根据需要自己定义大小typedef struct char chMaxStrSize ;/ch是一个可容纳256个字符的字符数组int length; SString ;定义顺序串类型3. 测试数据：主串：Through a retrospective look at the mathe
11、matics teaching at USTC, this article summarizes universitys teaching achievements in past 45 years”子串：teaching输出结果应为：子串teaching出现在主串中的次数为：22次匹配位置分别为：46102；实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或
12、无故缺席。实验 5：二叉树的创建、遍历及其它基本操作的实现实验所需 学时数2学时实验目的1）掌握二叉树的结构特征，以及两种存储结构的特点及适用范围2）掌握二叉树的先序、中序、后序、层次遍历的方法3）培养学生综合运用多种数据结构解决实际问题的能力实验内容建立一棵以二叉链表作存储结构的二叉树，然后按先序、中序、后序和层次的顺 序分别遍历这棵二叉树。实验所需 器材计算机及VC+ 6.0软件内容要求：1. 以二叉链表作存储结构创建如下二叉树：2. 输出二叉树的中序遍历序列和后序遍历序列，以验证所建二叉树的正确性；3. 按二叉树的层次输出所建二叉树各层的结点，要求同层的结点自左向右排列。（提示： 用到两
13、个队列P、Q。其中P存放当前层上的结点，Q存放下一层的结点。）实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。实验 6：哈夫曼树及哈夫曼编码的算法实现实验所需 学时数2学时实验目的1) 掌握哈夫曼树的基本概念及其存储结构；2) 掌握哈夫曼树的建立算法；3) 掌握哈夫曼树的应用(哈夫曼编码和译码)。实验内容对输入的一串电文字符实现哈夫曼编码，再对哈夫
14、曼编码生成的代码串进行译码， 输出电文字符串。实验所需 器材计算机及VC+ 6.0软件内容要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈 夫曼树2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding):根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding):利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。测试数据：输入字符串“this*program*is*my*favourite”完成这28个字符的编码和译码。实验结果1、演示程序运行结果。2、说明调试过程中出现的现象学生实验评价依据：优：实验认真、刻苦，有钻研精神，不无故缺席。良：能认真对待实验，不无故缺席。中：基本能认真对待实验，不无故缺席。差：对待实验不够认真，有少量迟到、早退或无故缺席现象。 不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。实验所需 学时数2学时实验目的1）掌握查找的基本概念；2）熟悉静态查找表的特点和适用场合；3）掌握顺序查找、二分法查找
