南 京 中 医 药 大 学
《数据结构》实验教学大纲
（适用于计算机类及相关专业）
课程名称： 数据结构 英文名称：Data Structure
课程类别： 专业基础必修课 课程编码：080182
课程学分： 3 课程学时：72
开课单位： 人工智能与信息技术学院 实验室： 人工智能与信息技术学院实验室
实验（实训）项目数： 12 课程负责人：李新霞
课程简介
数据结构除了是计算机科学与技术专业、软件工程专业及相关专业的教学计划中的核心课程，也是信息管理与信息系统及电子商务等相关专业的专业基础课。该课程在数据结构、算法及抽象数据类型等概念的基础上，介绍线性表、栈、队列和串、数组、树和二叉树、图等常用数据结构，并讨论查找、排序和索引技术，对学生的算法分析和设计能力进一步提高，并为后续相关等课程的学习奠定基础。
二、教学目标与基本要求
通过教学，学生获得有关的应用软件所要用到的各种数据结构知识，掌握常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算法知识。提高软件设计和编程技能。初步学会对不同的存储结构和相应算法的对比，有一定的算法改进能力。在学习中提高专业学习的自信、兴趣和自觉性，并感悟程序设计者的严谨的态度。结合研究型教学、自主性学习，了解数据结构的最新发展动态，以树立科学精神和创新思维。
（一）实践技能目标
1、注重培养学生独立思考能力，学会科学地分析和解决问题。
2、培养学生运用数据结构和程序设计语言通过计算机解决实际问题的能力。
3、培养学生进一步提高程序设计质量的能力。
（二）素质教育目标
1、具备运用数据结构的理论方法进行高质量程序设计的素质
2、具有良好的团队合作精神。
3、培养学生求真务实、讲求时效和一丝不苟的学习态度。
4、为学生形成良好的职业道德打下基础。
（三）创新能力培养目标
1、培养学生数据抽象能力，能为应用涉及的数据选择合适的逻辑结构。
2、培养学生理解计算机思维方式能力，能为各种逻辑结构设计合适的存储结构。
3、培养学生理论联系实际能力及自学能力。
基本要求
安装Visual Studio编译环境，提前完成实验任务的代码编写，课堂上主要完成调试，解决问题，不会的不理解的当堂提问寻求帮助。
三、实验（实训）项目、内容与学时分配
序号 | 实验项目名称 | 学时 | 内容提要 | 实验类型 |
基础性 | 综合设计性 | 创新性 |
1 | 线性表的的实现 | 3 | [实验目的] 1、掌握线性表的存储结构 2、验证顺序表和单链表及其基本操作 3、理解算法与程序的关系，能够将顺序表和单链表相关算法转换为对应的程序。 [实验内容] 1、建立含有若干元素的顺序表和单链表 2、对已建立的顺序表和单链表实现插入、删除、查找等基本操作 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
2 | 集合运算 | 3 | [实验目的] 1、掌握线性表的应用 2、理解如何选择存储结构 [实验内容] 1、建立两个单链表分别表示两个集合 2、通过单链表的基本操作实现集合的并、交、差及判断相等的功能（每位同学选一个即可） [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
3 | 栈和队列的实现 | 3 | [实验目的] 1、掌握栈和队列的存储结构 2、验证顺序栈和循环队列及其基本操作 3、理解算法与程序的关系，能够将顺序栈和循环队列相关算法转换为对应的程序。 [实验内容] 1、建立空的顺序栈和循环队列 2、对已建立的栈和队列实现插入、删除、取栈顶、队头元素等基本操作 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
4 | 病人就医管理 | 3 | [实验目的] 1、掌握队列的应用 2、理解如何选择存储结构 [实验内容] 1、建立队列，用来存储病人挂号信息 2、通过队列的基本操作模拟实现病人就医管理过程 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
5 | 串的实现及应用 | 3 | [实验目的] 1、掌握串的存储结构 2、验证串及其基本操作 3、理解算法与程序的关系，能够将串相关算法转换为对应的程序。 [实验内容] 1、分别建立空串和含有若干字符的串 2、对已建立的串实现求长度、判断相等、取子串等基本操作 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
6 | 二叉树的建立和遍历 | 3 | [实验目的] 1、掌握二叉树的逻辑结构 2、掌握二叉树的二叉链表存储结构 3、验证二叉树的二叉链表存储及其遍历操作。 [实验内容] 1、建立一棵含有n个结点的二叉树，采用二叉链表存储 2、输出前序、中序、后序遍历该二叉树的遍历结果 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
7 | 统计二叉树叶子数 | 3 | [实验目的] 1、掌握二叉树遍历操作的应用 [实验内容] 1、生成一棵二叉树 2、设计递归算法求叶子结点的个数 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
8 | 图的建立与遍历 | 3 | [实验目的] 1、掌握图的逻辑结构 2、掌握图的邻接矩阵和邻接表存储结构 3、验证图的邻接矩阵和邻接表存储及其遍历操作。 [实验内容] 1、建立无向图的邻接矩阵存储和有向图的邻接表存储 2、分别对建立的无向图和有向图进行深度优先遍历和广度优先遍历 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
9 | 图的连通性判断 | 3 | [实验目的] 理解连通性的定义 掌握连通性判断的方法 了解DFS和BFS的应用
[实验内容] 1、设计一个程序生成图并判断该图是否连通，如不连通，输出其联通分量个数。 2、连通 OR 不连通 描述：给定一个无向图，一共n个点，m条边。请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入 第一行两个数n,m（5<=n<=40000,1<=m<=100000） 接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
10 | 查找算法实现 | 3 | [实验目的] 1、掌握各种查找算法的基本思想 2、掌握各种查找算法的实现 3、掌握各种查找算法的时间性能。 [实验内容] 1、对给定的查找集合，运用不同的查找算法查找与给定值k相等的元素 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
11 | 排序算法实现 | 3 | [实验目的] 1、掌握各种排序算法的基本思想 2、掌握各种排序算法的实现 3、掌握各种排序算法的时间性能。 [实验内容] 1、对同一组数据分别运用不同的排序算法进行排序，并输出排序结果 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
12 | 综合实验 | 3 | [实验目的] 1、掌握基本数据结构的特点 2、掌握基本数据结构的实现 3、掌握基本数据结构的应用。 [实验内容] 1、分析给定的问题，选择需要的逻辑结构 2、根据操作需要，选择合适的存储结构 3、设计算法实现相应功能 [实验方法及原理] 编写代码，上机调试。 |
| √ |
|
四、教材及主要参考资料
1. 教材
[1]王红梅等.《数据结构(C++版)学习辅导与实验指导》，清华大学出版社，2011
2. 参考资源
（1）电子资源：
①《数据结构》 南京中医药大学电子教学平台
http://e.njucm.edu.cn
②数据结构，国家精品资源共享课
网址https://www.icourse163.org/learn/NWU-298002?tid=1450350442#/learn/announce
③各大OJ平台
（2）参考书：
①苏仕华.《数据结构课程设计》，机械工业出版社，2010
②王红梅.《数据结构学习辅导与实验指导》，清华大学出版社，2011
③刘光然.《数据结构实践训练教程》，南开大学出版社，2009
