数据结构试验参考指导书C语言版罗先文.doc

——信息管理系
 
《数据构造》实验指引书
《DATA STRUCTURES》
罗先文
LUOXIANWEN
 
 
西南大学信息管理系
Iinformation dept. SouthWest University
 
January 24，
 
 
写在上机实习之前
上机实践是学生对本门课程所学知识一种全面、综合能力训练，是与课堂听讲、自学和练习相辅相成必不可少一种教学环节，也是对课堂教学与实践教学效果一种检查。普通，实时习题复杂得多，也更接近实际。实习着眼于原理与应用结合，使学生学会如何把书上学到知识运用于解决实际问题过程中去，培养从事软件开发设计工作所必须基本技能；另一方面，能使书上知识变“活”，起到深化理解和灵活掌握教学内容目。平时练习较偏重于如何编写功能单一“小”算法，而实习题是软件设计综合训练，涉及问题分析，总体构造设计，顾客界面设计，程序设计基本技能和技巧，多人合伙，以至一整套软件工程规范训练和科学作风培养。此外，尚有很重要一点是：机器是比任何教师都严肃主考者。
为了达到上述目，本篇安排了7个主实习单元，各单元训练重点在于基本数据构造，而不强调面面俱到。各实习单元与教科书各章具备紧密相应关系，在个别实习单元中安排有难度差别不等各种实习题，以便学生选做。
此外，每个实习题采用了统一格式，实验目、实验内容、实验规定、程序实现、程序运营状况和源程序清单等5个某些构成。
在每个实习单元都提供了一种完整实当代码，仅供同窗们参照，绝大多数同窗在上机实习时千万不要机械照抄本附录所提供范文。而是应当自己独立思考和设计你算法和程序，并争取在规定期间内如期完毕上机工作任务。对于个别成绩较差同窗，实在是没法完毕任务建议你不妨抄一遍附录中样题，以增强你感性结识，强化你实践基本，提高你实践能力。本附录样题所有用c语言编写，并所有上机调试通过，但由于时间比较仓促，样题中提供算法和程序并不是最佳算法和程序，相信不少同窗一定有能力设计出更好算法和程序。随着计算机学科不断发展，可以使用语言工具越来越丰富，在本篇中实习示例还只是应用面向过程语言进行设计和编写程序，同样实习题，读者也可以用面向对象语言来实现。咱们但愿实习报告示例能起到一种抛砖引玉作用，在通过同窗们努力学习和积极使用后来，更多更优良设计范例能不断涌现。
文中存在不当之处，敬请各位不吝赐教！
 
 
目录
《数据构造》实验大纲 4
实验一、线性表操作 2
实验二、栈和队列应用 6
实验三、多维数组和串 12
实验四、树和二叉树操作 17
实验五、图操作 23
实验六、各种查找操作 30
实验七、各种排序操作 37
《数据构造》实验大纲
一.  课程名称：数据构造及算法分析
课程编号：
课程学时：70
课程学分：
实验时数：20
二.  所属实验室名称：计算机中心
三.  实验教材及参照书：
【1】数据构造题集（C语言版） 清华大学出版社
【2】DATA STRUCTURES WITH C++ 清华大学出版社
【3】本材料之后附录
四.  实验内容和目：
掌握四种基本数据构造：集合、线性构造、树形构造、网状构造在求解实际问题中应用，以及培养书写规范文档技巧。学习基本查找和排序技术。规定学生具备编制相称规模程序能力。养成一种良好程序设计风格。
五.  考核方式：上机考试、编程并运营通过。
六.  实验环境：
硬件最低规定：586微型计算机，主频450MHZ以上，内存64MB以上，硬盘10G，有软驱。每个学生每次上机实验使用一台计算机。
软件：C语言或Visual C++
七.  实验项目及安排
 
序号
实验
名称
类别
学
时
目与安排
备注
必选
选开
1
链表、数组
Ö
 
4
插入、删除、合并、排序、查找
 
2
栈与队列
Ö
 
4
 
 
3
递规算法
Ö
 
4
汉诺塔问题
 
4
树及应用
Ö
 
4
递规、非递规遍历
 
5
图及应用
Ö
 
4
遍历算法、最小生成树
 
6
排序查找
Ö
 
4
排序、查找算法比较分析
 
7
串及应用
 
Ö
4
匹配算法
 
8
线索树
 
Ö
4
中序线索化操作
 
 
 
 
实验一、线性表操作
一、实验目
1．掌握用 C语言调试程序基本办法。
2．掌握线性表基本运算，如插入、删除等。
二、实验内容
1．线性表在顺序存储构造上插入元素，删除元