数据结构 实验

《数据结构 实验》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验训练题目一、作业习题部分第2章1.设线性表存储在数组A[1..arrsize]的前elenum个分量中，且递增有序。试编写一个算法：将x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。2.已知单链表L中的结点是按值非递减有序排列的，试编写一算法将值为X的结点插入到表L中，使得L仍然有序。3.用单链表作存储结构，编写一个实现线性表中元素逆置的算法。4.已知一个单链表中的数据元素含有三类字符（即字母字符，数字字符和其它字符），试编写算法，构造三个循环链表，使每个循环链表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空

2、间。5.试编写一个算法，找出一个循环链表中的最小值。第3章1：算术表达式的计算输入格式：一行一个算术表达式，可以输入若干行输出格式：一行一个输出结果样例：输入样例：2*（3+4）6+2*8/4输出样例1410【基本要求】运算对象均为整数【选作内容】运算对象扩充为可以是带小数位的浮点数1第5章1.以二叉链表作存储结构，编写一个算法将二叉树左、右子树进行交换的算法。2.一棵具有n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行前序遍历。3.试编写算法判别两棵二叉树是否等价。如果T1和T2都是空二叉树，或T1和T2的根结点的值相同，并且T1的左子树与

3、T2的左子树是等价的；T1的右子树与T2的右子树是等价的。4.设计一个实现一棵二叉树复制的算法。5.编写一个将二叉树的所有叶子结点从左向右链接成单链表的算法。6.设具有n个结点的完全二叉树采用顺序存储结构，试写一个算法将该顺序存储结构转换为二叉链式存储结构。7.设具有n个结点的二叉树采用二叉链式存储结构，试写出一个算法将该二叉链式存储结构转换为顺序存储结构。第8章1.分别写出用邻接矩阵和邻接表做图的存储结构，并分别实施广度优先遍历和深度优先遍历。选做题：1.写出求最小生成树的算法。【可以考虑完成实验5】第7章1.写出二分查找算法。2.编写一个采用二叉链式结构做存储结构的

4、二叉排序树建立和查找算法。【可以考虑完成实验4】2选做题：1.用拉链方法解决冲突的散列存储及查找。第9章1.写出快速排序算法。2.写出冒泡排序算法。3.写出直接选择排序算法。【可以考虑完成实验6】实验0C++复习【实验目的】ò熟悉和掌握VC环境下的编译、调试和执行的方法及步骤ò复习C++有关的语法及编程技术；ò熟悉加深ADT表示方法及实现的理解。【编程要求】ò良好的编程风格（可参考附录《C++CodeStandard》/《高质量C++/C编程指南》）;ò必要的注释；（简单要求如下）1.readme文件对上交的实验内容文件或目录作适当的解释；2.每个.cpp文件中注释信息

5、至少包含以下内容：（1）版权信息。（2）文件名称，标识符，摘要或模块功能说明。（3）当前版本号，作者/修改者，完成日期。（4）版本历史信息。//（1）--（4）部分写在文件头（5）所有的宏定义，非局部变量都要加注释（6）所有函数前有函数功能说明，输入输出接口信息，以及调用注意事项（7）函数关键地方加注释3.每个.h文件中对关键接口信息/变量声明信息等加注释3【参考资料】ò《C++面向对象程序设计》教材ò《C++CodingStandard》ò《高质量C++/C编程指南》ò《数据结构》教材ò《数据结构》实验辅导书【评分标准】òE<60:在规定时间内上交实验程序及文档,基本

6、要求中的大部分内容未完成。ò60

7、，设计思想十分清晰，编程风格好，界面美观大方。0．1顺序存储操作的实现【问题描述】实现顺序存储的插入、删除和查找等操作【实验内容】ò必做内容一、顺序存储的插入、删除和查找菜单：1.初始化2.插入3.删除4.查找5.退出4插入操作的要求输入：（1）插入位置i（2）插入元素值输出：（1）插入之前的元素序列（2）插入之后的元素序列删除操作的要求输入：（1）删除位置i输出：（1）删除之前的元素序列（2）删除之后的元素序列查找操作的要求输入：待查找的元素值输出：查找成功与否ò选做内容（1）用MFC的单文档窗口和菜单设计界面。（2）添加两个菜单功能，