《数据结构》实验教学大纲
课程名称：数据结构实验/Data Structure Experiments
课程编码：23000400923 课程负责人： 张艳玲 课程性质： 独立设课 开设学期： 第二学年 第2学期
学时学分：课程总学时 64 课程总学分 3.5 ，其中实验总学时 16实验总学分0.5 开设实验项目数： 6 ，其中必做实验项目数 6 选做实验项目数 0 适用专业： 计算机学院各专业 综合性、设计性实验项目数： 1 ，总学时： 4
主笔人： 高崇志 主审人： 日期： 2012 年 12 月 1日
一、实验教学目标及基本要求（150字左右）
本课程是一门理论和实践紧密结合的基础课，它的任务是讨论现实世界中的各种逻辑结构、在计算机中的存储结构以及实现各种操作的算法问题，为今后进一步学习后续专业课程，进行软件开发和应用打好基础。实验课紧扣理论课教学，实现理论课所学的数据组织、存储、处理的基本方法。
实验目的是要求学生使用C语言编程，实现理论课所学的数据组织、存储、处理的基本方法。要求学生具备基本的程序设计能力，用C代码不能成为表达算法思想的障碍，能自如地根据具体问题的内容设计相应是输入输出方式及输入数据的合理性校验。具体的要求如下：
1、验证性实验以传授知识为主，要求学生掌握基础知识、基本技能。在教学中教师讲解基本数据结构和算法。教师辅导多一些，教师在传授知识的同时，逐步培养学生严格认真，独立思考的实验态度。
2、综合性实验以掌握解决问题的方法为主线。综合性实验要求学生利用所学的数据结构和算法，在实验过程中解决所碰到的具体问题，通过实验报告总结提高。教师以解答学生的疑问为主，在学生实验中遇到问题时，不是简单地帮助学生排除故障，而是提出产生故障的几种可能性，由学生自行排除，鼓励学生提出问题和不同的见解。
二、实验项目的设置（说明：①若大纲面向2个及以上专业，其实验项目设置情况不同，则在下表中添加
一列“面向专业”；②实际选做项目总学时 + 必做项目总学时 = 课程实验总学时。）
序号 实验 学时 每组人数 实验 要求 1、必做 2、选做 实验类型 1、基础性 2、综合性 3、设计性 4、探究性 实验编码 实验项目名称 内容提要 1 2 230100019 链式存储结构的基本操作 230100020 树和二叉树的实现 对单链表，链式堆栈，链式队列的插入，删除，查找，定位等操作 多元树的层次遍历、先根2 1 1 2 4 1 1 2 遍历、后根遍历，二叉树的递归算法：计算高度、结点个数、交换左右儿子 图的表示法、生成树的概3 230100021 图的遍历生成树 念、图的深度优先、广度优先遍历算法 插入排序、选择排序、希4 230100022 排序算法 尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、基数排序。 5 230100023 查找算法 实现二分查找、二叉排序、查找树，哈希查找。 在每个队伍允许插队的情况下，若你在排队，有6 230100024 插队买票 一个以上的朋友要求插队，你可以安排他们的顺序，若没有朋友，则排在队伍的最后面。 4 1 1 3 2 1 1 2 2 1 1 2 2 1 1 2
三、实验教学方式
1、验证性实验以传授知识为主，要求学生掌握基础知识、基本技能。在教学中教师讲解基本数据结构和算法。教师辅导多一些，教师在传授知识的同时，逐步培养学生严格认真，独立思考的实验态度。
2、综合性实验以掌握解决问题的方法为主线。综合性实验要求学生利用所学的数据结构和算法，在实验过程中解决所碰到的具体问题，通过实验报告总结提高。教师以解答学生的疑问为主，在学生实验中遇到问题时，不是简单地帮助学生排除故障，而是提出产生故障的几种可能性，由学生自行排除，鼓励学生提出问题和不同的见解。
四、考核方式与评分标准
考核主要是平时实验报告和操作考试，由教师出一定数量的实验题目，学生采取抽签形式在规定的时间里完成，主要考核学生对基本数据结构和算法的理解和掌握能力。成绩构成比例为：平时成绩70%（含预习、操作情况，实验报告，实验方案设计）+操作考试成绩30%。考核成绩分为优秀、良好、中等、及格和不及格五个等级。
五、教材（指导书）及主要参考书
1、严蔚敏，《数据结构》，清华大学出版社，2006年9月 2、刘大有，《数据结构》，高等教育出版社，2005年7月
3、朱站立，《数据结构——使用C++语言》，西安电子科技大学出版社，2007年9月
4、Sara Baase, Allen Van Gelder，《Computer Algorithms introduction to Design and Analysis》( Third Edition )，高等教育出版社，2002年3月
插队买票
是数据结构课程设计的题目，用C++的思想来写，本来给的程序是C的，贴出来给个参考（有部分被我改成了C++，比如类）
但是程序要C++ 实验要求如下： 本实验假设售票大厅有多个售票窗口，无论到哪个窗口买票都必须排队，但是新来的人不一定排在队尾，允许插队（即直接排在朋友的后面）。 假设已经在排队的人不会离开，也不会移到其他队伍去。买到票的人依次出队。每个人仅买一次票，买完票就离开。每个人都有名字。 每个来买票的人先进行观察判断： 1． 如果所有的队伍中都没有发现朋友，则选择最短的队伍排在其队尾； 2． 如果所有的队伍中仅发现一个朋友，则可以（不是必须）插在此朋友的后面；但是，插队前应考查是否合算，插入此位置离窗口的距离（即队伍前面的人数）必须小于其他队伍的长度，否则应选择最短的队伍排在其队尾； 3． 如果所有的队伍中发现多个朋友，这种情况就比较复杂： （1） 如果多个朋友是集中在一个队伍里，则可以插在最后那个朋友的后面； （2） 如果多个朋友是分散在多个队伍里，则插队的原则是离售票窗口最近； 4． 如果朋友排在队伍的第一位（即队首），则不允许插队； 本实验要求编写程序模拟这种排队买票时允许插队的情形。要求程序中应用散列表来存放和查找数据，应用求余法构造合理的散列函数，应用平方探测法来解决Hash映射的冲突现象。程序可能需要四个文本文件： （1） 初始化文件input.txt，包含售票窗口及其购票队伍的初始设置 （2） 朋友组文件friend.txt，同一个名字也可能出现在不同的组 （3） 来购票的人的完整名单people.txt，其中包含出现在friend.txt中的名字；文件中名字的顺序表示不同的到来顺序；文件中每行有一个名字，如果某行有多个名字则表示他们同时到达售票厅（这是比较复杂的情形） （4） 售票结果文件output.txt（按售票窗口分组显示），可以考虑各窗口卖票的节奏（即售票员的售票速度）
