课程编号：08232
课程英文名称：Data Structure
学时数：2+1 学分数：3
适用层次和专业：地理信息系统本科 测绘工程本科
一、课程的性质和目的
数据结构（Data Structure）是信息学科中的核心课程之一，也是基础和必修的科目。数据结构是介于数学，计算机硬件和计算机软件三者之间的一门核心课程,它是一门综合性的专业基础课，是学习操作系统、编译原理、数据库原理等计算机专业核心课程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。
统过本课程的学习，使学生掌握数据结构和算法设计与分析的基本知识通过本课程的学习，使学生掌握数据结构和算法设计与分析的基本知识，各种基本数据结构的定义，存储结构、相应的算法以及应用，掌握基本的数据结构与算法的关系。培养地理信息系统专业的学生分析问题、解决问题的能力，学会对处理的数据建立抽象数据类型，利用抽象数据类型进行程序设计。掌握对典型的数据结构的各种基本操作，并培养学生理论结合实际应用，设计有效的算法和数据结构的能力。
二、本课程主要教学内容及各章节学时分配
理论部分：
第1章 算法分析(2学时)
主要知识点： 算法分析的两种方法，时间复杂度的三种表示方法Big-O，Ω和θ。
第2章 数组(2学时)
主要知识点：线性表及其操作，一维数组，二维数组、三维数组及n维数组的java表示与实现方法。数组的应用与实现：矩阵、多项式、上三角形和下三角形、幻方及生命游戏
第3章 栈与队列(4学时)
第一节 栈和队列基本概念
主要知识点：栈的定义、栈的表示与实现
第二节 栈的入栈与出栈
主要知识点：栈的入栈与出栈算法
第三节 队列与循环队列的入队与出队
主要知识点：队列与循环队列的入队与出队算法
第四节 栈与队列的应用
主要知识点：中缀表达式转为前缀表达式或后缀表达式以及它们的计算
第4章 链表（3学时）
第一节 单向链表
主要知识点：插入结点操作、删除结点操作、将两链表相连、将链表反转和计算链表长度
第二节 循环链表
主要知识点：插入结点操作、删除结点操作、两个循环链表相连
第三节 双向链表
主要知识点：插入结点操作、删除结点操作
第四节 链表的应用
主要知识点：以链表表示栈、以链表表示队列、多项式相加
第5章 递归（1学时）
主要知识点： n阶乘、斐波纳契数、将输入的词组以先进后出法打印、汉诺塔的递归与非递归实现
第6章 树结构（4学时）
第一节 树的一些专有名词
主要知识点：结点、祖先、父结点、兄弟结点、非终端结点、终端结点、结点的度、层次、高度和深度
第二节 二叉树
主要知识点：二叉树的定义、二叉树的性质、满二叉树与完美二叉树的定义
第三节 二叉树的表示方法
第四节 二叉树遍历
主要知识点：中序遍历、先序遍历和后序遍历
第五节 二叉查找树
主要知识点：二叉查找树的定义、插入、删除与查询树和森林
第六节 其他论题
主要知识点：将树和森林转化为二叉树，决定唯一的二叉树
第7章 堆结构（1学时）
主要知识点：堆的定义、二叉树调整成堆的方法，堆中结点的插入与删除，max heap、min heap和max-min heap、min-max heap的定义
第8章 平衡二叉查找树、2-3树与2-3-4树及B树（1学时）
主要知识点：平衡二叉查找树的定义、平衡二叉查找树结点的插入与删除操作
第9章 图结构(4学时)
第一节 图的定义和术语
主要知识点：有向图、无向图、完全图、子图、路径、连通图、长度、回路、度、入度与出度
第二节 图的数据结构表示法
主要知识点：数组表示法、邻接链表
第三节 图的遍历
主要知识点：深度优先搜索、广度优先搜索
第四节 扩展树与最小生成树
主要知识点：最小生成树的三种算法：prim、krushal和sollion算法
第五节 最短路径
主要知识点：Dijkstra算法
第10章 排序 (3学时)
第一节 冒泡排序
主要知识点：冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、希尔排序、二叉树排序、基数排序
第11章 查找 (1学时)
主要知识点：顺序查找、二叉查找、二叉搜索树、哈希查找
实验部分：
实验一 NetBeans IDE 7.0.1程序结构及简单操作
主要内容：
1. 实现1.1.1的数组相加的功能
2. 通过程序，来验证1.1的练习题
3. 编写程序，实现斐波那契序列能够打印出Fibonacci（n）（分别用两种方式的实现，递归与非递归）
教学要求：
1. 通过在NetBeans IDE 7.0.1软件中实现简单的功能代码，熟悉NetBeans 的编程环境。
2. 了解JAVA语言的程序的基本结构，为以下验证各种数据结构奠定理论础和操作技巧。
实验二 链表
主要内容：
1. 实现第四章的程序集锦中的单向链表的节点的插入与删除的功能
2. 实现第四章的程序集锦中的单向循环链表的节点的插入与删除的功能
3. 实现第四章的程序集锦中的双向链表的节点的插入与删除的功能
教学要求：
1.通过在NetBeans IDE 7.0.1软件中分别实现单向链表、单向循环链表和双向链表的节点的插入与删除的功能代码，熟悉链表的数据结构及其算法。
2.通过比较单向链表、单向循环链表和双向链表的节点的插入与删除的代码，掌握各种链表的插入与删除的具体算法实现步骤。
实验三 栈与队列
主要内容：
1. 实现第三章的程序集锦中的栈的入栈与出栈
2. 实现第三章的程序集锦中的队列的入队与出队
3. 实现第三章的程序集锦中的中缀表达式转换为后缀表达式
教学要求：
1.通过在NetBeans IDE 7.0.1软件中分别实现第三章的程序集锦中的前两个程序，熟悉栈和队列的数据结构，分别掌握栈的入栈出栈和队列的入队出队的具体算法实现。
2.通过在NetBeans IDE 7.0.1软件中实现第三章的程序集锦中的第三个程序，掌握栈和队列的综合应用，进一步熟悉入栈出栈和队列的入队出队的算法实现。
实验四 递归
主要内容：
1. 实现利用递归计算n的阶乘
2. 实现利用递归计算费波纳契序列（与第一章的进行比较一下）
3. 实现利用递归解汉渃塔问题
教学要求：
通过在NetBeans IDE 7.0.1软件中分别实现第五章的程序集锦中的三个程序，熟悉运用递归解决复杂问题的方法，进一步掌握栈的入栈出栈和队列的入队出队等操作的具体算法实现。
实验五 二叉树
主要内容：
二叉查找树结点的增加与删除
教学要求：
通过在NetBeans IDE 7.0.1软件中分别实现第六章的程序集锦中的二叉查找树结点的增加与删除，熟悉运用链表这种数据结构表示二叉树的方法，二叉查找树结点的增加与删除的算法实现，同时进一步复习并熟悉前面学的链表的操作。
实验六 排序
主要内容：
1.冒泡排序
2.选择排序
3.插入排序
4.快速排序
教学要求：
通过在NetBeans IDE 7.0.1软件中分别实现第十二章的程序集锦中的前四个程序，掌握冒泡排序、选择排序、插入排序和快速排序的方法，及其算法实现。
实验七 查找
主要内容：
1.顺序查找
2.二叉查找
教学要求：
通过在NetBeans IDE 7.0.1软件中分别实现第十三章的程序集锦中的前两个程序，掌握顺序查找和二叉查找的方法及其算法实现。
四、本课程与其他有关课程的联系
学习本课程前，学生应具有计算机技术的基础知识，以便使学生顺利掌握程序设计等内容。先修课程为《计算机基础》、《高级语言程序设计》。
五、教学方法与手段
根据教学目的，采用多媒体等现代教学设施进行讲授、演示，辅助讨论、师生互动、板书等形式，使学生有效地调动学生的学习积极性，促进学生的积极思考，激发学生的潜能。
六、学时分配表
理论部分：
章 |
学 时 分 配 |
合计 |
讲课 |
习题课 |
实验课 |
上机课 |
讨论课 |
其他 |
1 |
2 |
|
|
4 |
|
|
6 |
2 |
2 |
|
|
4 |
|
|
6 |
3 |
6 |
|
|
6 |
|
|
12 |
4 |
5 |
|
|
6 |
|
|
11 |
5 |
1 |
|
|
2 |
|
|
3 |
6 |
6 |
|
|
6 |
|
|
12 |
7 |
1 |
|
|
|
|
|
1 |
8 |
1 |
|
|
|
|
|
1 |
9 |
4 |
|
|
|
|
|
4 |
10 |
5 |
|
|
6 |
|
|
11 |
11 |
1 |
|
|
2 |
|
|
3 |
实验部分：
实验项目 |
实验性质 |
学时 |
实验一 NetBeans IDE 7.0.1程序结构及简单操作 |
综合性实验 |
4 |
实验二 链表（选作） |
综合性实验 |
4 |
实验三 栈与队列 |
综合性实验 |
6 |
实验四 递归 |
综合性实验 |
6 |
实验五 二叉树（选作） |
综合性实验 |
2 |
实验六 排序 |
综合性实验 |
6 |
实验七 查找 |
综合性实验 |
6 |
七、成绩考核方式
1.平时成绩考核办法：出勤情况（占30%中的30%），提问情况等课堂表现（占30%中的20%）
2．实验成绩考核办法：实验成果及实习报告（占30%中的50%）
3．期末考试考核办法：闭卷笔试占70%
4．课程综合成绩评定：期末占70%，平时和实验共占30%，
八、推荐教材与学习资源
1、推荐教材：
罗文劼 王苗 张小莉.数据结构与算法（java版）.机械工业出版社.2013.7
2、主要学习资源：
(1) 蔡明志.数据结构（java版）.中国铁道出版社. 2006.7
(2)严蔚敏 吴伟民.数据结构.清华大学出版社.1997
(3)黄国瑜.数据结构c语言版.清华大学出版社. 2002.1
(4) 李春堡.数据结构习题与解析.清华大学出版社. 2000.1
(5)王晓东.数据结构与算法设计.电子工业出版社. 2002.3
大纲修订人：隋晓丽
大纲审定人： 李长坡
制订日期：2014年8月
