《数据结构实验》教学大纲
一、实验课名称：中文名：数据结构实验
英文名：Experiments in Data Structure
二、实验课性质：独立设课
三、适用专业：数学与应用数学，信息与计算科学，统计学，信息管理与信息系统
四、采用教材及参考书：
1、李春葆，《数据结构习题与解析》（C语言篇），清华大学出版社，2000.1
2、严蔚敏、吴伟民，《数据结构》（C语言版），清华大学出版社，1997.4
五、学时学分：
课程总学时：64； 课程总学分：4； 实验课总学时：36
六、实验项目名称和学时分配
序号 | 实验项目名称 | 学时 分配 | 实验 属性 | 实验 类型 | 实验者类别 | 每组 人数 | 必开/选开 |
1 | 抽象数据类型的实现 | 3 | 基础 | 综合 | 本科生 | 1 | 必开 |
2 | 线性表的基本操作 | 3 | 基础 | 设计 | 本科生 | 1 | 必开 |
3 | 栈和队列及其应用 | 6 | 基础 | 设计 | 本科生 | 1 | 必开 |
4 | 树和二叉树的建立及应用 | 9 | 基础 | 设计 | 本科生 | 1 | 必开 |
5 | 图的建立及应用 | 6 | 技术 | 设计 | 本科生 | 1 | 必开 |
6 | 查算法的实现 | 3 | 技术 | 设计 | 本科生 | 1 | 必开 |
7 | 内排序算法的实现 | 3 | 技术 | 设计 | 本科生 | 1 | 必开 |
8 | 综合实验 | 3 | 专业 | 设计 | 本科生 | 1 | 必开 |
七、实验教学的目的和要求
计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习编写计算机程序仅仅了解计算机语言是不够的，还必须掌握数据组织、存储和运算的一般方法，这是数据结构课程中学习和研究的内容。由于数据结构的原理和算法较抽象，而该课程一般在本科低年级开设，对于计算机程序设计知识的初学者，理解和掌握其中的原理就显得较为困难。具体要求如下：
1、熟练掌握C语言的编辑、编译、调试程序；
2、会书写类C语言的算法，并将算法转变为程序实现；
3、正确理解各种数据结构的逻辑特性、存储表示和基本操作的算法实现；
4、有较强的逻辑分析能力；
5、针对不同的问题选择合适的数据结构，提高算法设计的能力和动手实验的技能；
6、学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结
构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术；
7、本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚、正确易读，符合软件工程的规范，从而培养学生的数据抽象能力；
8、通过若干数据结构应用实例，引导学生学习数据类型的使用，为今后学习面向对象的程序设计做一些铺垫。
八、实验项目的内容和要求
1、 抽象数据类型的实现
实验内容：将类C语言描述的算法转换成C源程序上机调试并通过
实验要求：
1) 熟悉类C语言的书写规范，复习高级程序设计语言的使用方法，学会分析基本的算法时间复杂度和空间复杂度；
2) 了解抽象数据类型的定义、表示和实现方法，会利用高级语言中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作；
3) 加深理解数据的逻辑结构和物理结构。
2、 线性表的基本操作
实验内容：选择不同的存储结构，实现线性表的建立、插入、删除、合并等操作
实验要求：
1) 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；
2) 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；
3) 进一步熟练C语言的使用（特别是函数参数、指针类型、链表的使用）。
3、 栈和队列及其应用
实验内容：栈类型的两种实现方法；循环队列和链队列的基本操作实现算法
实验要求：
1) 熟练掌握栈和队列这两种特殊的线性表，熟悉它们的特性，能在实际问题背景下灵活运用；
二叉树的遍历及应用实验报告2) 能够在两种存储结构上实现栈和队列的基本运算，特别注意栈满、栈空、队列满、队列空的判断条件及描述方法。
4、 树和二叉树的建立及应用
实验内容：树的各种存储结构，各种操作的算法实现（建立、遍历、二叉树的线索化、最优树）
实验要求：
1) 熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现；
2) 重点掌握二叉树的生成、遍历及求深度等算法；
3) 掌握二叉树的线索化及线索二叉树的遍历算法，掌握赫夫曼树的含义及其应用；
4) 掌握运用递归方式描述算法及编写递归C程序的方法，提高算法分析和程序设计能力。
5、 图的建立及应用
实验内容：图的各种存储结构，各种操作的算法实现（建立、遍历、有向图和无向图的几个重要算法）
实验要求：
1) 熟练掌握图的邻接矩阵和邻接表的存储方式；
2) 实现图的一些基本运算，特别是深度遍历和广度遍历；
3) 掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。
6、查算法的实现
实验内容：各种查算法的思想和实现， 散列技术
实验要求：
1) 熟练掌握各种静态查表的查（顺序查法、折半查法、索引顺序表查）；
2) 熟练掌握二叉排序树的构造方法和查算法，了解二叉平衡树的建立和维护平衡的方法；
3) 会计算各种查方法在等概率情况下查成功时的平均查长度；
4) 熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。
7、内排序算法的实现
实验内容：各种内部排序算法的思想和实现
实验要求：
1) 熟练掌握各种排序的算法思想、方法及稳定性；
2) 对已知一组数据，能写出其具体的排序过程、算法及完整程序，并上机调试；
3) 了解每一种排序的时间及空间复杂度，理解开发高效算法的可能性和寻、构造高效算法的方法。
8、综合实验
实验内容：综合解决一个较复杂的问题
实验要求：
1) 对前面所学的数据结构进行复习总结，对有一定难度的题目，学会分解问题，自上而下，逐步解决；
2) 在掌握现有数据结构的基础上，对不同的问题，尝试改进相应的数据结构。
以上所有实验应配备的主要设备名称和台件数如下：
序号 | 设备名称 | 每组应配台件数 | 现有台数 | 备注 |
所有 | PII及以上的微机 | 1 | ||
九、实验课考核方式：
1、实验报告：每次实验要求写实验报告（具体格式统一印制）。
2、考核方式：期末考试形式为机考。最后成绩核算，平时成绩占20%~30%，期末考试占70%~80%。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论