数据结构与算法实习实验指导书分析.doc

数据结构与算法课程实习 实验指导书 上海第二工业大学 计算机与信息学院软件工程系 目录 实验一 顺序表的基本操作 2 实验二 链表的基本操作 3 实验三 二叉树的基本操作 4 实验四 综合应用 5 附录A 实验报告示例 10 附录B 实验报告封面、评语得分表 13 附录C 最后要提交的文档形式 15 实验一 顺序表的基本操作 【实验目的】 掌握顺序存储的概念，学会对顺序表的基本操作。 加深对顺序存储数据结构的理解，逐步培养解决实际问题的能力。 【实验性质】 设计型实验 【实验内容】 1、实现顺序表显示； 2、实现顺序表插入； 3、实现顺序表查找（显示比较次数）； 4、实现顺序表删除（显示移动次数）； 5、实现顺序表排序（分别实现简单选择、快速，显示比较次数、移动次数）； 6、实现顺序表的折半查找（显示比较次数）； 7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置； 8、顺序表有序插入（显示比较次数、移动次数）， 屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素； 屏幕显示比较次数和移动次数，应有溢出判断和报告； 9、要求以较高的效率实现删除顺序表中元素值在x到y(x和y自定)之间的所有元素； 10、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次； *11、编程实现顺序表的shell排序（步长为5，3，1）； *12、编程实现堆排序算法； *13、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）。 【实验环境】 VC++ 6.0 【实验要求】 将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。 实验二 链表的基本操作 【实验目的】 掌握链表的概念，学会对链表进行操作。 加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。 【实验性质】 设计型实验 【实验内容】 1、实现单链表的创建； 2、实现单链表的显示； 3、实现单链表的查找（显示比较次数）； 4、实现单链表的插入； 5、实现单链表的删除（显示比较次数）； 6、对已创建的链表（数据不限）进行直接插入排序； 7、将链接存储线性表逆置，即最后一个结点变成第1个结点，原来倒数第2个结点变成第2个结点，如此等等； 8、生成有序的两个单链表A和B（链表的数据和个数自定），其首结点指针分别为a和b，要求将两个单链表合并为一个有序的单链表C，其首结点指针为c，并且合并后的单链表的数据不重复； 9、将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a和b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序； 10、请编程实现链栈的基本操作函数，并通过调用这些基本函数，实现十进制和八进制转换的功能。 【实验环境】 VC++ 6.0 【实验要求】 将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。 实验三 二叉树的基本操作 【实验目的】 掌握二叉树的概念，学会对二叉链表进行操作。 加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。 【实验性质】 设计型实验 【实验内容】 1、实现二叉树的创建； 2、用递归方法分别先序、中序、后序遍历以Tree为根指针的二叉树； 3、编写递归算法，计算二叉树中叶子结点的数目； 4、编写递归算法，计算二叉树的深度； 5、编写递归算法，将二叉树中所有结点的左、右子树相互交换； 6、使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树； 7、在以Tree为根指针的二叉排序树中查找结点； 8、从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）； 9、用非递归算法，先序遍历以Tree为根指针的二叉树； 提示：用数组 BiTNode *stack[max] 构成堆栈，利用这个堆栈实现功能。 10、用凹入表示法的表示以Tree为根指针的二叉树，例如： // 324 // 123 // 746 // 690 // 567 11、用广义表表示以Tree为根指针的二叉树，例如 // (324(123(746,690),567)) 12、对以Tree为根指针的二叉树，从根结点开始，逐层从左到右