学时与学分： 学时：64 学分：4
课程性质、目的及任务：
本课程是电子信息工程专业的一门重要的指定选修课，通过本课程的教学，重点培养学生利用数据结构的知识解决电子信息工程中各种特定的数据组织和数据存储问题的能力。
本课程的主要任务是讨论现实世界中数据的各种逻辑结构，在计算机中的存储结构以及进行各种非数值运算的算法。目的是使学生掌握数据组织、存储和处理的常用方法，为以后进行软件开发和学习后续专业课程打下基础。
通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系； 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的步骤和算法分析方法； 掌握数据结构在排序、查找和路由选择等常用算法中的应用。
课程内容、教学要求及学时分配：
一、理论教学 （48学时）
1、绪论（2学时）
1、教学内容
数据结构研究的主要内容、数据结构中涉及的基本概念、算法的概念、描述方法以及评价标准。
2、教学要求
掌握数据结构的基本概念，了解抽象数据类型，了解算法时间复杂度和空间复杂度的分析，了解算法的描述方法。
3、教学重点和难点
重点是数据的逻辑结构、存储结构及数据运算三方面的概念及相互关系；难点是算法复杂度的分析方法。
2、线性表（2学时）
1、教学内容
线性表的定义和基本操作、线性表的顺序存储结构、线性表的链式存储结构、循环链表、线性表的应用举例。
2、教学要求
理解线性表的定义及其运算；理解顺序表和链表的定义、组织形式、结构特征和类型说明；掌握在顺序表和链表上实现的插入、删除和按值查找的算法；了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。
3、教学重点难点
教学重点：线性表的定义及逻辑上的特点；顺序表上插入、删除和定位运算的实现；单链表的结构特点及类型说明；头指针和头结点的作用及区别；指针操作；定位、删除、插入运算在单链表上的实现；循环链表、双链表的结构特点；循环链表、双链表上删除与插入运算的实现。
教学难点：头结点在链表中的作用；指针操作；删除、插入运算中的指针操作顺序；双链表上指针的操作顺序。
3、栈和队列（4学时）
1、教学内容
栈的概念、存储结构及其基本操作、队列的概念、存储结构及其基本操作、栈与队列的应用举例。
2、教学要求
理解栈的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现；理解队列的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。
3、教学重点和难点
教学重点：栈上的基本运算；栈的顺序存储结构及运算实现；栈的链式存储结构；入栈、出栈等运算在链栈上的实现；队列上的基本运算；队列的顺序存储结构及其上的运算实现；队列的链式存储结构；入队、出队等运算在链队列上的实现。
教学难点：顺序栈的溢出判断条件；循环队列的队空、队满判断条件；循环队列上的插入、删除操作。
4、串（2学时）
1、教学内容
串的定义、存储结构和基本运算、模式匹配。
2、教学要求
了解串的逻辑定义；掌握串的两种存储方式。
3、教学重点和难点
教学重点：串的两种存储方式，串的模式匹配算法。
教学难点：串的模式匹配算法。
5、数组和广义表（6学时）
1、教学内容
数组的定义、基本运算和存储结构、特殊矩阵的压缩存储、广义表的定义、术语、存储结构、运算、递归算法设计。
2、教学要求
了解串的逻辑定义；掌握用顺序存储串及堆存储串时的特点及在这两种存储方式下基本操作的实现；了解改进的模式匹配算法；掌握数组的顺序存储结构及特殊矩阵的存储方式；了解稀疏矩阵的压缩存储方式—三元组表。
3、教学重点和难点
教学重点：多维组的两种顺序存储方式，稀疏矩阵的三元组表表示方法。
教学难点：稀疏矩阵的压缩存储表示下的运算的实现。
6、树和二叉树（8学时）
1、教学内容
树的定义和存储结构、二叉树的定义、性质、存储结构、二叉树的遍历、线索算法、树和二叉树的转换、哈夫曼树及其应用。
2、教学要求
深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；理解并掌握二叉树的三种遍历算法；掌握二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题。
3、教学重点和难点
教学重点：二叉树的定义、逻辑特点及五种基本形态；二叉树的五个性质；在二叉树上定义的基本运算；二叉树的链式存储结构及其类型说明；二叉树的顺序存储结构及其类型说明；二叉树的三种遍历方法及其算法；以遍历为基础在二叉树上实现的几种运算；哈夫曼树和哈夫曼编码。
教学难点：二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的主要区别。
7、图（8学时）
1、教学内容
图的定义、图的存储结构、图的遍历操作、图的几个典型应用问题。
2、教学要求
理解图的基本概念及术语；掌握图的两种存储结构(邻接矩阵和邻接表)方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；领会拓扑排序、关键路径、最短路径的算法思想。
3、教学重点和难点
教学重点：理解图的定义、术语及其含义；掌握各种图的邻接矩阵表示法及其类型说明；理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；领会生成树和最小生成树的概念；
掌握由Prim算法思想构造最小生成树的过程；领会拓扑序列和拓扑排序的概念；理解拓扑排序的算法思想；理解关键路径的算法思想；理解最短路径的算法思想。
教学难点：正确理解与区别图的常用术语；区别图的两种存储结构的不同点及其应用场合；关键路径的算法思想；最短路径的算法思想。
8、查找（8学时）
1、教学内容
静态查找表及查找算法：顺序查找、折半查找、动态查找表及查找算法：二叉排序树、哈希表及查找算法。
2、教学要求
了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度；理解并掌握二叉排序树的各种算法；
3、教学重点和难点
教学重点：查找表的基本概念及查找原理；查找表的顺序存储结构、顺序表及其类型说明；查找运算在查找表和有序表上的实现；二叉排序树的定义、性质及各结点间的键值关系；二叉排序树的查找算法和基本思想；散列表及散列存储和散列查找的基本思想；各种散列表的组织、解决冲突的方法；在散列表上实现查找、插入和删除运算的算法。
教学难点：各种查找算法的实现；二叉排序树上的插入和删除算法；解决冲突的方法。
9、排序（8学时）
1、教学内容
排序的概念，直接插入排序、希尔排序、快速排序、，堆排序、归并排序。
2、教学要求
领会排序的基本思想和基本概念；理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤和时空效率分析；
3、教学重点和难点
教学重点：排序基本概念及稳定排序和非稳定排序的区别；插入排序的基本思想、基本步骤；冒泡排序的基本思想、基本步骤和算法分析；快速排序的基本思想、基本步骤和算法分析；直接选择排序的基本思想、基本步骤和算法分析；堆排序的基本思想、基本步骤和算法分析；归并排序的思想；二路归并排序的算法和时空性能。
教学难点：快速排序算法实现；堆排序算法实现；希尔排序算法实现；归并排序算法实现；基数排序算法实现。
二、实践教学 （16学时）（上机地点：信息实验中心）
1、线性表及其应用（2学时）
熟练掌握线性表的各种存储结构及插入、删除等操作的算法的实现，通过线性表结构解决现实中的一些问题。
2、树及其应用（4学时）
熟悉树的各种存储结构的特性和应用树的结构解决具体问题。
3、图及其应用 （4学时）
熟悉图的各种存储结构的特性应用图的结构解决具体问题
4、查找技术 （4学时）
熟练掌握常用的一些查找算法，深入理解各种查找算法的结构特点及各算法之间的区别，能通过所学的查找算法解决一些实际问题。
课程成绩评分方法
本课程分为理论教学和实验教学两部分。实验当堂考核，不另设实验考试；习题要完成规定习题量的3/4才能参加期终闭卷笔试。
总成绩的计算方法：总成绩=平时（10%）+实验（20%）+考试（70%）
推荐教材及参考书：
教材：《数据结构C++语言描述》 作者：William Ford,William Topp，译者：刘卫东 沈官林，清华大学出版社
参考书：《算法与数据结构》 傅清祥 王晓东编著，电子工业出版社
《数据结构》 许卓群 张乃孝等编著，高等教育出版社
《数据结构》 杨正宏编著，中国铁道出版社
《数据结构》 张世和编著，清华大学出版社
《数据结构与算法》（英文影印版） 作者：Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman，清华大学出版社
先修课程：C语言程序设计
修课对象：电子信息工程、通信工程等专业本科生。
撰 稿 人：谢靖
审 定 人： 王勇