课程名称：数据结构

  学时数：60，周学时：4

  建议参考书：

  《数据结构C语言》 严蔚敏 吴伟民  清华大学出版社 2008-3

  适用专业：计算机软件技术，计算机应用技术

  先修课程：C语言

  一、       课程的教学目的与要求

   从课程性质上讲，“数据结构”是一门专业技术基础课。它的教学要求是：学会从问

  题入手，分析研究计算机加工的数据结构的特性，以便为应用所涉及的数据选择适当

  的逻辑结构、存储机构及其相应的操作算法，并初步掌握时间和空间分析技术。另一

  方面，本课程的学习过程也是进行复杂程序设计的训练过程，要求学生会书写符合软

  件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。

  二、学时安排

  有关教学要求分为三级：掌握(A)、理解(B)、了解(C)，重点（△），难点（※）

  三、内容纲要和教学目标

  第一章 绪论

    教学内容：

  1.1  数据结构概念

    1.2  基本概念和术语

    1.3  抽象数据类型的表示与实现

  1.4  算法和算法分析

  教学目标：

  1、了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理

  结构概念及逻辑结构与物理结构间的关系

  2、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价

  3、掌握计算语句频度和估算算法时间复杂度的方法

  第二章  线性表

  教学内容：

  2.1  线性表的类型定义

  2.2  线性表的顺序表示和实现

  2.3  线性表的链式表示和实现

  2.4  一元多项式的表示及相加

     教学目标：

  1、了解线性表的逻辑结构特性，以及线性表的两种存储实现方式

  2、熟练掌握两种存储结构的描述方法。链表是本章的重点和难点。

  3、熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现；

  4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构；

  5、能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

  第三章  栈和队列

  教学内容：

  3.1  栈

  3.2  栈的应用举例

  3.3  栈与递归的实现

  3.4  队列

  3.5  离散事件模拟

     教学目标：

  1、掌握栈和队列的定义、特性，并能正确应用它们解决实际问题；

  2、熟练掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；

  3、熟练掌握队列的顺序表示、链表表示以及相应操作的实现。

  第四章 串

  教学内容：  

  4.1  串类型定义

  4.2  串的表示和实现

  4.3  串的模式匹配算法

  4.4  串操作应用举例  

  教学目标：

         1、理解串的基本操作的定义，能利用这些基本操作来实现串的其它各种操作的方法；

  2、熟练掌握在串的顺序存储结构上实现串的各种操作的方法

  3、了解串操作的应用方法和特点。

  第五章  数组和广义表

  教学内容：

          5.1  数组的定义

          5.2  数组的顺序表示和实现

          5.3  矩阵的压缩存储

          5.4  广义表的定义

          5.5  广义表的存储结构

          5.6  m元多项式的表示

          5.7  广义表的递归算法

       教学目标：

  第六章  树和二叉树

  教学内容：

           6.1  树的定义和基本术语

           6.2  二叉树

           6.3  遍历二叉树和线索二叉树

           6.4  树和森林

           6.6  赫夫曼树及其应用

     教学目标： 

  1．领会树和二叉树的类型定义，理解树和二叉树的结构差别。

  2．熟记二叉树的主要特性，并掌握它们的证明方法。

  3．熟练掌握二叉树的各种遍历算法，能灵活运用遍历算法实现二叉树的其它操作。

  4．理解二叉树的线索化过程及在中序线索化树上找给定结点的前驱和后继方法。

  5．熟练掌握二叉树和树的各种存储结构及其建立的算法。

  6．学会编写实现树的各种操作的算法。

  7．了解最优树的特性，掌握建立最优树和赫夫曼编码的方法。

  第七章  图

      教学内容：

            7.1  图的定义和术语

            7.2  图的存储结构

            7.3  图的遍历

            7.4  图的连通性问题

            7.5  有向无环图及其应用

            7.6  最短路径

  教学目标：

  1．领会图的类型定义。

  　　     2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。

  　　     3．熟练掌握图的两种遍历算法。

  　　     4．理解各种图的应用问题的算法。 

  第九章  查找

  　  教学内容：

           9.1  静态查找表

           9.2  动态查找表

           9.3  哈希表

  教学目标：

  　　    1．理解“查找表”的结构特点以及各种表示方法的适用性；

  　　    2．熟练掌握以顺序表或有序表表示静态查找表时的查找方法；

  　　    3．熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系；

  　　    4．熟练掌握二叉查找树的构造和查找方法；

  　　    5．理解二叉平衡树的构造过程；

  　　    6．熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；

  　　    7．掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概

  率情况下查找成功时的平均查找长度 

  第十章  内部排序

  10.1  概述

      10.2  插入排序

    10.3  快速排序

    10.4  选择排序

      10.5  归并排序

      10.6  基数排序

    10.7  各种内部排序方法的比较讨论

     教学目标：

  1．理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同

  的分类方法，基于"关键字间的比较"进行排序的方法可以按排序过程所依据的

  不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。

   2．掌握各种排序方法的时间复杂度的分析方法。能从"关键字间的比较次数"分析

  排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排

  序可分为三类：O (n2) 的简单排序方法，O (n·logn) 的高效排序方法和O 

  (d·n)的基数排序方法。

  3．理解排序方法"稳定"或"不稳定"的含义，弄清楚在什么情况下要求应用的排序

  方法必须是稳定的。 

  四 考核方式

  闭卷考试   占总成绩的80–70%

  平时成绩（作业和课堂考勤等）  占总成绩的 20-30%