数据结构实验报告(2015级).doc

《数据结构实验报告(2015级).doc》由会员分享，可在线阅读，更多相关《数据结构实验报告(2015级).doc（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告专 业 _年 级 _学 号 _学生姓名 _指导老师 _华中师范大学信息管理系编I 实验要求1每次实验中有若干习题，每个学生至少应该完成其中的两道习题。2上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。3独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。4上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。II 实验内容实验一 线性表【实验目的】1熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。2通过编程、上机调试，进一步理解线性表的

2、基本概念,熟练运用C语言实现线性表基本操作。3熟练掌握线性表的综合应用问题。【实验内容】1一个线性表有n个元素（nMAXSIZE, MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。 2. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求：指定的值x由键盘输入；程序能处理空链表的情况。 3设有头结点的单链表，编程对表中的作一值只保留一个结点，删除其余值相同的结点。要求：该算法用函数（非主函数）实现；在主函数中调用创建链表的

3、函数创建一个单链表，并调用该函数，验证算法的正确性。4已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。要求：该算法用函数Reverse(head,p)实现，其中head为表头指针，p指向要交换的结点；在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。5设有一个单链表，编写能够完成下列功能的算法：找出最小值的结点，且打印该数值；若该数值是奇数，则将其与直接后继结点交换；若该数值是偶数，则将其直接后继结点删除。要求：编写主函数验证算法的正确性。6在一链表中，已知每个结点含有三个域：data、next和prior，其中prio

4、r域为空，设计一个算法，使每个结点的prior指向它的前驱结点，形成双向循环链表。要求：建立一个结点中含有三个域的单链表；在主函数中调用此算法，构成双向循环链表；在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。7用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。 要求：通讯录是按姓名项的字母顺序排列的； 能查找通讯录中某人的信息；提示：可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为工作结点，需从链表的首结点开始比较，如果工作结点的数据比链中的当前结点

5、的数据小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实习小结实验二 堆栈与队列【实验目的】1学习如何使用C语言实现堆栈与队列。2熟悉堆栈与队列的基本操作及应用。【实验内容】1 现有一顺序循环队列，其结构描述为：# define MAX 100typedef struct ElemType queueMaxQueueSize; int front; / 队头指针int count; / 计数器 QueueType;要求：设计队列的几种几种操作：初始

6、化、进队、出队、取队头元素和判断队列是否非空。编写一个主函数进行测试。2已知Q是一个非空队列，S是一个空栈。编写算法实现：将队列Q中的所有元素逆置。要求：调用堆栈和队列的操作函数实现该算法。编写一个主函数进行测试。3设计一个算法，将计算机产生的n个随机数分为奇数、偶数两组，并将它们分别压入两个栈中，然后在屏幕上输出。4编写一个程序，反映病人到医院看病排队看医生的情况。在病人排队过程中，主要重复两件事：病人到达诊室，将病历交给护士，排到等候队列中候诊。护士从等待队列中取出下一个病人的病历，该病人进入诊室就诊。要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下：排队输入排队病人的

7、病历号，加入到病人排队队列中；就诊病人排队队列中最前面的病人就诊，并将其从候诊队列中删除；查看排队从队首到队尾列出所有的排队病人的病历号；不再排队，余下依次就诊从队首到队尾列出所有的排队病人的病历号，并退出运行；下班退出运行。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实习小结实验三 串【实验目的】1掌握串的基本运算。2掌握有关串的比较、复制和转换等操作的实现。3熟悉串的有关应用问题。【实验内容】1设计一个算法，统计输入字符串中各个不同字符出现的频度。设字符串中的合法字符为AZ这26个字母和09这10个数字（串的存储结构自行选择）。2已知字符串S1中存放一段英文，写出

8、算法format(S1,S2,S3,n),将其按给定的长度n格式化成两端对齐的字符串S2,其多余的字符送S3（即将字符串S1拆分成字符串S2和字符串S3，要求字符串S2长度为n且首尾字符不得为空格字符）。3输入一篇短文，统计其中所出现的单词的频率（单词间以空格隔开）。4采用动态顺序结构存储串，编写算法：求用户输入串S中出现的第一个最长重复子串的下标和长度。一个字符串中重复最长的部分，比如说有如下字符串： abcdbcdbcb 对于这个字符串最长的重复子串为bcdbc。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实习小结实验四 数组【实验目的】1进一步熟悉关于数组的压缩

9、存储的有关概念。2掌握数组在压缩存储下的有关运算。【实验内容】1如果矩阵A中存在这样一个元素Aij满足下列条件：Aij是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。编写算法计算mn的矩阵A的所有马鞍点。2设矩阵A、B和C均为采用压缩存储方式存储的n阶上三角矩阵，矩阵元素为整数类型，要求：设计算法实现矩阵相加运算：C=A+B；设计算法实现矩阵相乘运算：C=AB；在主函数中设定矩阵A和B，并调用该算法验证其正确性。3编写一个算法，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实

10、习小结实验五 二叉树【实验目的】1理解和掌握二叉树的定义、性质、存储结构、遍历原理与实现方法。1 建立二叉树并对其进行简单操作。2 进一步熟悉二叉树的应用。【实验内容】1 设计算法实现以下操作：建立一棵二叉树（二叉树中的结点的数据为字符型）；统计二叉树中的结点数；统计二叉树中叶子数；输出所有的叶子结点；输出所有从叶子结点到根结点的路径。2单词排序试将一段英文中出现的单词按词典的顺序打印出来，同时应注明每个单词在该段文章中出现的次数。提示：将一段英文中出现的单词按词典的顺序打印的过程，就是由一个无序序列构造为有序序列的过程，这个过程可以通过构造二叉排序树，并按中序遍历来实现。3编写一个算法，判断

11、以二叉链表存储的二叉树中否为完全二叉树，并用主函数进行测试。4已知在以二叉链表存储的二叉树BT中，p和q指向二叉树中两个不同的结点，试编写一算法，求包含p和q所指结点的最小子树。5若二叉树以三叉链表作为其存储结构，编写一个不设堆栈进行中序遍历的非递归算法。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实习小结实验六 查找与排序【实验目的】1 进一步熟悉各种查找与排序的算法，并对各种算法的效率进行比较和测试。【实验内容】1 排序算法比较。要求：调用函数int rand(void)产生100000个待排序的数据；测试下列各排序函数的机器实际执行时间：a.直接插入排序； b.

12、希尔排序 c.选择排序d.冒泡排序 e.堆排序 f.快速排序g.归并排序 h.基数排序2编写一个程序读入一个字符串，统计该字符串中出现的字符及其次数，然后输出结果。要求用一个二叉树保存处理结果，字符串中的每个不同字符用树中结点描述，每个结点包含四个域：字符该字符出现的次数指向ASCII码小于该字符的左子树的指针指向ASCII码大于该字符的右子树的指针3编写判定给定的二叉树是否是二叉排序树的算法。并用主函数进行验证。4编写一个非递归的快速排序算法。并用主函数进行验证。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实习小结实验七 综合练习【实验目的】1在掌握基本概念的基础上

13、，综合运用线性结构和树结构以及排序和查找算法进行复杂结构程序设计。【实验内容】1试将一棵普通树转换成二叉树，同时转换而成的二叉树按前序、中序、后序进行遍历，并输出遍历后结点的序列。例如，下面左图是一棵普通树，用括号表示法表示为：A(BC(FG)DE)，右图是转换后的二叉树。 提示：从分析输入的树串形式可知，左括号后面的字符为左括号前面字符的左子树，括号内的字符关系是兄弟，则转化为二叉树后，后面字符为其前一字符的右子树。所以，依据左右括号及字符间的关系，可以生成结点的左右子树。2建立学生成绩管理系统，要求：数据用线性表的链式存贮，并给出菜单界面。系统中功能包括：录入数据。给出学号，删除该学生的数

14、据。给出学号，查询该学生的数据，并打印查询结果。以学生成绩为基础，对学生数据按降序排序，并输出排序结果。插入新的学生数据，并保持降序不变。打印排好序之后的学生数据。【实验报告】实习时间： 实习地点： 实习机号：具体实验内容程序调试过程实习小结实验报告的规范1需求分析：以无歧义的陈述说明程序设计的任务，强调程序要做什么？明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；测试数据：合法数据和非法数据及结果。2总体设计：说明本程序中用到的所有数据类型的定义、程序的总体框架。3详细设计：实现总体设计中定义的所有数据类型，对每个操作写出伪码算法或画出算法流程图，并画出模块的调用关系图。4调试分析：调试过程中遇到问题的解决办法以及对设计与实现的回顾讨论和分析；算法的时空分析（包括基本操作和其他算法的时间复杂度和空间复杂度的分析）和改进设想等。5用户使用说明：说明程序的使用方法，详细列出每一步的操作步骤。6测试结果：列出测试结果，包括输入和输出，测试数据应该完整和严格。7附录：打印出带汁释的源程序。