《数据结构》实验指导书3635.doc

《数据结构》实验指导书3635 33.知之为知之，不知为不知，是知也 ——《论语》 《数据结构》 实验指导书 肇庆学院计算机科学系 编 前 言 　　数据结构是信息与计算科学专业中一门重要的专业基础课程 当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练 因此，数据结构课程在计算机应用专业中具有举足轻重的作用 　　本书是针对《数据结构》教程的上机实验指导书，内容包括线性表、栈和队列、串、数组和稀疏矩阵、递归、树状结构、图、查找、排序等 书后附录中给出了学生应提交的实验报告的格式 　　本上机实验指导书旨在通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会 　　本实验指导书的内容都是基于C语言的，因此，要求学生对C语言要有一定的了解 建议使用Turbo C 2.0或VC++作为实验平台 根据学生的实际情况，本上机实验指导书的内容大多数为基本算法的综合验证，也包括部分算法设计 本上机实验指导书共有9个实验内容，每个实验约为4课时 　　由于作者对《数据结构》知识所知有限，书中难免存在错误，恳请读者及时加以指正，以便改进 如有对于本书的意见和建议，请与编者联系，E-mail：lg@zqu.edu.cn 衷心感谢！ 　　编 者 　　 目录 前 言 实验一 顺序表 1 实验二 单链表 3 实验三 栈和队列 5 实验四 串 7 实验五 数组 8 实验六 树和二叉树 10 实验七 图 12 实验八 查找 14 实验九 排序 16 参考资料 18 附录1：肇庆学院计算机系实验报告格式 19 附录2：上机实习注意事项 21 实验一 顺序表 一、预备知识 　　1.顺序表的存储结构形式及其描述 　　2.顺序表的建立、查找、插入和删除操作 二、实验目的 　　1.掌握顺序表的存储结构形式及其描述 　　2.掌握顺序表的建立、查找、插入和删除操作 三、实验内容 　　1.编写函数,输入一组整型元素序列,建立一个顺序表 　　2.编写函数,实现对该顺序表的遍历 　　3.编写函数,在顺序表中进行顺序查找某一元素,查找成功则返回其存储位置i,否则返回错误信息 　　4.编写函数,实现在顺序表的第i个位置上插入一个元素x的算法 　　5.编写函数,实现删除顺序表中第i个元素的算法 　　6.编写利用有序表插入算法建立一个有序表的函数 　　7.编写函数,利用以上算法，建立两个非递减有序表,并把它们合并成一个非递减有序表 　　8.编写函数,实现输入一个元素x,把它插入到有序表中,使顺序表依然有序 　　9.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法 四、实验说明 　　1.顺序表的存储定义 　　　　#define MAXSIZE 100 //顺序表的最大元素个数 　　　　typedef int ElemType；//顺序表的元素类型 　　　　typedef struct list 　　　　 {ElemType elem[MAXSIZE];//静态线性表 　　　　 int length; //顺序表的实际长度 　　　　 } SqList;//顺序表的类型名 五、注意问题 　　1.插入、删除时元素的移动原因、方向及先后顺序 　　2.理解不同的函数形参与实参的传递关系 六、实验报告 　　根据实验情况和结果撰写并递交实验报告 实验二 单链表 一、预备知识 　　1.动态链表的存储结构形式及其描述 　　2.单链表的建立、查找、插入和删除操作 二、实验目的 　　1.掌握单链表的存储结构形式及其描述 　　2.掌握单链表的建立、查找、插入和删除操作 三、实验内容 　　1.编写函数,实现随机产生或键盘输入一组元素,建立一个带头结点的单链表（无序） 　　2.编写函数,实现遍历单链表 　　3.编写函数,实现把单向链表中元素逆置（不允许申请新的结点空间） 　　4.编写函数,建立一个非递减有序单链表 　　5.编写函数,利用以上算法，建立两个非递减有序单链表,然后合并成一个非递减链表 　　6.编写函数,在非递减有序单链表中插入一个元素使链表仍然有序 　　7.编写函数,实现在非递减有序链表中删除值为x的结点 　　8.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法 四、实验说明 　　1.单链表的类型定义