己所不欲，勿施于人——孔子
所属课程名称：数据结构基础。
英文名称： fundamentals of data structure
所属课程编号：0901202
面向专业： 计算机及电类专业。
课程总学时： 64 ；实验学时 32 ；
课程学分： 4.5
一。 实验目的。
通过上机实验，使学生深刻理解基础数据结构和算法的概念并能实际应用和进一步拓展教学内容，系统掌握典型数据结构和算法的设计与分析方法，培养用数据结构对现实对象进行建模并解决实际问题的能力，掌握数据结构的定义、表示以及操作实现相互关联的规律，增强动手能力，增强专业性程序设计和构建软件系统的能力，提高分析问题和解决问题的能力，提高专业素质，培养协作精神和创新能力。
二。 实验内容、学时分配与组织。
序号。实验项目名称。
内容提要。实验性质。
实验类型。学时分配。
每组人数。备注。
随机漫游。用数组count表示蟑螂到达每块地砖的次数，蟑螂位置用 (i, j) 表示，八个方向的随机游走通过生成均匀分布随机数k（0≤k≤7）模拟。
每到达一块地砖，相应次数加1
当蟑螂至少到达每块地砖一次时，模拟完成。
应打印最终的count数组。
专业基础。提高型。
选做。环链单变量多项式系统。
设计和实现一个用带头结点的环链表表示单变量多项式的系统。
应使用局部资源管理技术。
实现并测试的操作包括：输入、输出、复制构造、赋值、析构、相加、相减、相乘和计算多项式的值。
专业基础。提高型。
必做。双链环表。定义带头结点的双链环表的模板类，包括dbllistnode，dbllist和dbliterator三个模板类。
除了实现游标成员函数first( )next( )notnull( )和nextnotnull( )之外，再实现一个成员函数previous( )
专业基础。提高型。
选做。基于模板的二叉树类。
写出基于模板的二叉树类定义，并进一步定义二叉树的中序、前序、后序和按层次遍历游标类，最后写一个函数分别以上述4种顺序打印所有树元素。
专业基础。提高型。
必做。命题演算公式系统。
设计一种命题演算公式的符号表示，写一个函数，读入一个公式的符号表示并生成其二叉树表示。
分析并测试该函数的计算时间。
专业基础。研究创新型。
选做。优先队列的实现方法比较。
分别用最大堆、无序线性表和有序线性表实现优先队列，并比较这三种实现的运行性能。
专业基础。研究创新型。
必做。深度优先搜索。
分别用邻接矩阵和邻接表表示图，设计实现深度优先搜索的完整算法，并用适当的实例测试其正确性。
专业基础。提高型。
必做。最小生成树。
写出实现最小生成树算法的完整程序，并用适当的实例测试其正确性。
专业基础提高型。
选做。aoe网络设计一个算法，输入aoe网络，输出：所有事件及其最早开始时间和最迟开始时间，所有活动及其最早开始时间、最迟开始时间和关键度，关键网络专业基础提高型。
必做。排序方法性能研究用随机排列生成器生成平均情况数据，测量插入排序、快速排序、归并排序、堆排序和基数排序的平均运行时间专业基础研究创新型。
必做。生成归并段用随机数生成器生成输入记录表，测量并分析生成归并段算法生成的归并段的平均长度专业基础研究创新型。
选做。二叉查找树性能研究设计一个算法，对一棵初始为空的二叉查找树作n次插入每次插入的关键字值由均匀随机生成器生成，测量所生成二叉树的高度h，并将h/log2n作为n的函数用曲线画出专业基础研究创新型。
选做。b树用合理的外存地址模拟指针，实现b树的查找、插入和删除算法专业基础研究创新型。
选做三。 教学管理模式与注意事项。
1. 实验任务由任课教师课堂教学中下达。
2. 学生在实验前必须理解和掌握课程有关内容，深入分析实验问题，提出并尽可能优化解决方案，设计实验必须的全部数据结构和算法，规划生成实验测试数据的方法。
3. 任课教师适当提示实验要求及注意事项，并检查预习情况。
4. 研究生助教现场辅导学生上机实验。
5. 实验小组人数一般为2人，每个实验的时间为4-6小时，由学生独立上机完成，所有实验都要求能够通过程序设计实现，并运行正确。
6. 要求学生熟悉c++程序设计语言及相应的开发环境，逐项记录数据，并完成实验报告。
7. 学生在完成全部"必做"实验的同时，可根据自己的实际情况，选择"选做"实验实验时间按学校计算机实验中心排定的计划，同时鉴于目前多数学生已拥有自己的计算机，也可用其它时间完成实验。
8. 注意诚信教育，鼓励学生之间开展讨论和交流，但坚决反对抄袭行为四。 成绩评定与占课程总成绩的比例。
1． 任课教师和研究生助教小组根据每个学生实验预习情况、必做实验完成情况、软件质量、实验数据的准确性、选做实验的数量和完成情况，以及对实验报告的批改，按优秀、良好、中等、及格和不及格档次进行评分，并将成绩记录在册。
2．任课教师汇总实验成绩，实验成绩与平时作业成绩占课程总成绩的30%
五。 设备与器材配置。
1． 微机 （要求安装c++语言及开发环境） 1台/每个学生。
2． 打印机（多组学生共享）
3． 耗材若干六。 实验任务书与参考资料。
1. 金远平。 数据结构（c++
描述）.清华大学出版社，2005
2. 徐冬梅。 数据结构实验指导书，东南大学讲义，2004
3. e. horowitz, s.
sahni, d. mehta. fundamentals of data structures in c++.
computer science press.1995
4. 殷人昆等。数据结构（用面向对象方法与c++描述）.清华大学出版社。2001
己所不欲，勿施于人——孔子
数据结构基础
内容简介。本书是最经典数据结构教材的最新版本，国内外大多数的同类教材都是以本书为蓝本编写而来的。本书用c作为描述语言，全面而生动地介绍了数据结构的有关知识，如数组 栈 队列 链表 树和图，以及构成所有软件基础的排序散列技术。此外，本书还介绍了各种高级或特殊数据结构，如优先级队列 高效二叉查找树 多路...
数据结构基础
文件输入输出。include include using namespace std int main file fin,fout fin fopen rscanf d x fscanf stdin,d x fout fopen w fprintf d x frpintf stdout,d x in...
数据结构基础
读万卷书，行万里路 刘彝 所属课程名称 数据结构基础。英文名称 fundamentals of data structure 所属课程编号 0901202 面向专业 计算机及电类专业。课程总学时 64 实验学时 32 课程学分 4.5 一。实验目的。通过上机实验，使学生深刻理解基础数据结构和算法的概...