中国人民解放军理工大学

图片
课程概述

1.  课程性质和地位 

 

    “数据结构”是计算机科学与技术、网络工程、信息安全等专业本科生的专业基础课程中的一门重要的核心课程。

    在计算机学科中,本课程与其他课程的关系如图1所示。图中,大学数学、计算机基础、离散数学、C/C++语言等是本课程的先导课程,而其它课程(如操作系统、编译原理、计算机网络等)均以本课程作为先导课程。图中已罗列出一些专业课所用到本课程中的相关知识,比如,操作系统课程会用到队列、存储管理表等。本课程也是算法分析与设计、计算复杂性理论等高级课程的基础。因此,本课程在计算机教学工作中具有重要的地位。

          

                                      图1  数据结构课程与其他课程的关系图

 

2.  课程目标

 

    通过本课程的教学,使学习者懂得数据结构的一般原理,掌握表、树、图等基本结构的特点,各结构的存储表示和所涉及的运算,完成各运算的算法及其实现方法,学会对算法的评价方法。使学习者具有一定的算法设计能力,较强的程序设计能力,和实际应用能力,能够针对给定的简单问题设计出求解算法,包括问题的抽象、数据的提取、数据的组织、数据结构的确定(逻辑结构)、算法设计、数据的存储形式(物理结构)、编程实现、程序的调试和测试等。也为学习后续专业课程,设计系统程序打下坚实的理论基础和实践基础。

 

3.  教学环节

 

    本课程通过视频授课、课外作业、教材阅读、上机实践,以及师生互动等环节实现课程目标。

    学习者通过观看本课程提供的授课视频接受课堂教学,学习基本知识;通过阅读本课程指定的教材(《数据结构与算法》(第二版).陈卫卫 王庆瑞编著.北京:高等教育出版社.  2015.07),预习和复习视频授课内容;通过完成指定的“书面”练习题和上机练习题,巩固和充实课堂知识;学习者和教师互动,由一方向另一方提出问题请其解答,学习者以其释疑,教师则以其检查学习者完成学业的情况。

 

4.  课堂教学设计

 

    课堂教学内容分为三大部分:基础知识(第一讲)、基本模型(第二至九讲)、基本问题(第十讲)。

    基础知识部分是学习后续内容的基础,包括概念(算法的概念,数据结构的概念)、标准(对算法的评价标准)、方法(算法的描述方法和评价方法)。

    基本模型部分是本课程最主要部分。这部分以查找、插入、删除运算为主线全面而系统地介绍表、树、图等基本数据结构的特点、存储方法、完成各运算的算法设计方法和实现程序、时空效率。因为,查找、插入、删除不仅是最基本的、最常用的,而且往往也是不可分的(通常联合使用,极少单独使用),其它某些运算还可以转化为这三种运算。将这三种运算构成的运算集作为一个整体,可以得出结构的整体时空效率。

    最后一部分,以问题为导向(这里选用排序问题),介绍求解同一个问题的多种不同处理算法,通过对算法的评价,分析各算法的特点、效率、适用情况。

    图2展示了这些课堂教学内容之间的关联关系。

       

图2  数据结构教学内容之间的概念图


5.  实践教学设计

 

    本课程设计的实践教学(即上机实验)题分为基础性、综合性设计性三大类。

    基础性(即知识验证性)类实验题主要用于巩固课堂知识,其难度不大,实现程序不长(小程序),通常只需要将教材中的程序进行简单拼装,简单改造,简单模仿,简单细化。

   综合性和设计性实验题属于大作业,实现程序较长,难度较大。顾名思义,完成综合性实验题需要将多个知识点进行综合,而完成设计性实验题则要实现从建模到解模的全过程,即实验者要独立完成:问题的抽象,数据的提取,数据的组织,数据结构的确定(逻辑结构),算法设计,数据的存储形式(物理结构),编程实现,程序的调试和测试等步骤。

 

6.  教学模式设计

 

    对于基本概念,在讲清基本概念条文的同时,尽可能多地举例阐述概念的内涵,并强调规范术语用词,培养严谨的科学作风。

    对于算法设计,遵循“少而精”的原则,突出重点,以点带面,通过对比,使学习者逐步建立设计“好”算法的意识。

    对于表、树、图三大基本结构,依照“逻辑结构→物理结构→基本运算→基本算法→算法评价”这个脉络,研究每种结构的特点,给学习者一个清晰的研究主线,使学习者能够根据问题的特点选择合适的数据结构,进一步理解研究数据结构的意义。

    对于学习者,可以按照“读、仿、改、究”的学习模式逐步提升自己的程序(算法)设计能力,并以此衡量自己当前达到的水平。具体地说,“读”就是研读(本课程中给出的)经典算法及其实现代码,领会算法设计思路、描述方式和实现代码的程序结构;“仿”是指对现有的求解原问题的算法进行简单搭建和修改,写出用来求解与原问题相近的新问题的模仿算法;而“改”则是,当应用场景或用户需求发生较大改变时,能够对现有算法进行改进,写出改进算法,这一阶段至关重要,不仅起到了深化理解知识的作用,而且对算法设计能力、分析能力,改进点的定位,改进措施的选定都是极大考验和锻炼;“究”指的是研究和探索给定问题的性质、特征,确定求解策略,设计出性能良好的求解算法。

授课目标
通过本课程的教学,使学习者懂得数据结构的一般原理,掌握表、树、图等基本结构的特点,学会对算法的评估方法。培养学习者的算法设计能力、程序设计能力,以及用软件方法处理问题的能力,培养学习者的分析、对比、归纳、综合和创新能力,为后续学习专业课程,设计系统程序打下坚实的理论基础。
证书要求

    (1)个人提出申请证书要求,在缴纳一定的费用之后,参与统一的笔试测试。

    (2)笔试成绩在60~84分的,发给课程合格证书,笔试成绩达到85分及以上的,发给优秀证书。

预备知识

学习者应具备以下几个方面的基础知识:

 l 熟练掌握C/C++(传引用)语言;

 l 掌握基本图论知识,初步概率知识;

 l 掌握常用的数学术语、集合和关系、对数、级数求和、递归和递推等概念;

 l 熟练运用一种编程环境(例如,VC编译环境)。

授课大纲

课程大纲如下表所示。其中,第七讲由李清老师讲授,其余部分由陈卫卫老师讲授。

内容进度

基本要求

能力与素质培养

第一讲  概述(2h)

1.1 为什么要学习数据结构

1.2  数据结构的概念

1.3  算法的概念和描述

1.4  算法评价

1.准确复述数据结构的基本概念、所要研究的对象和研究方法;

2.准确理解算法的概念、算法和程序的关系、算法的描述形式;

3.准确解释算法评价的一般标准和方法,正确计算简单算法时间复杂性的阶;

4.熟练运用算法描述工具,正确解释伪代码与源代码的区别,会用类C书写算法。

通过这部分内容的教学,使学习者对算法、数据结构和程序三者之间的关系有全面的认识,培养他们算法描述能力,以及结构化程序设计能力,使其对解决实际问题的全过程有清楚的认识。深刻认识算法在软件开发中的作用,树立设计和选择“好”算法的意识。

第二讲  顺序表(4h)

2.1  表结构的基本概念

2.2  顺序表的插入和删除

2.3  顺序表的查找

2.4  应用示例

 

第三讲 链表(上)(2h)

3.1  基本概念

3.2  单向链表的构造

3.3  单向链表的输出和查找

第四讲 链表(下)(4h)

4.1  链表的种类

4.2  复杂链表的基本操作

4.3  有序链表的构造

4.4  应用示例

第五讲 栈和队(2h)

5.1 

5.2 

第六讲散列表(2h)

6.1  散列函数

6.2  散列表的处理算法

1.准确描述表结构的基本概念,比较顺序表与链表的存储特点;

2.正确运用顺序表的插入、删除、查找方法及相关算法,分析算法的效率;

3.正确使用简单链表的构造、插入、删除、查找等一般方法;

4.正确分析对简单链表加表头监督结点、表尾监督结点,构成循环链表等方法的特点,设计构造双向链表、双向循环链表算法;

5.正确构建栈运算算法和栈的应用,掌握队运算算法;

6.准确解释散列存储的特点、散列函数的构造方式;正确构建散列表的构造、插入、删除的方法,分析散列冲突的解决办法,计算散列冲突后的再散列位置。

表结构是一种重要的结构之一,通过这部分内容的教学,使学习者弄懂直接存储(顺序存储)和链式存储的区别,以及时空转换的关系,开阔学习者的思路,培养学习者抽象思维能力;掌握多种程序设计方法,培养学习者科学思维方法,提高学习者的综合素质和创新能力。通过综合上机练习,熟练地掌握各种链操作,为学习后续内容打下坚实的基础。

 

第七讲 树结构(8h)

7.1 树的基本概念和存储方法

7.2 二叉树的遍历

7.3 二叉树的构造

7.4 检索树

7.5 平衡树

7.6 哈夫曼树

1.准确解释树的有关概念、树的存储表示、特殊的树结构;

2.正确运用二叉树递归遍历算法,学会递归程序设计方法;

3.正确实现二叉树构造算法;

4.准确解释检索树的意义,正确实现检索树的构造、查找、插入、删除算法;

5.准确解释平衡树的原理,知道如何构造平衡树,如何对平衡树进行插入、删除操作;

6.  正确实现哈夫曼算法,设计哈夫曼编码。

树结构是一种非常重要的结构,通过这部分的学习,使学习者对树结构有整体的认识。通过对树递归遍历、递归构造等算法的训练,加强学习者递归思维能力和想象力。强调与课堂教学内容相配套的上机练习,促进对递归的理解和递归程序设计能力的提高。

 

第八讲 图结构(上)(4h)

8.1 图的定义和有关术语

8.2 图的存储方法

8.3 图的遍历

8.4 图遍历算法的应用示例

8.5 最短路径 

第九讲 图结构(下)(4h)

9.1 最小生成树

9.2 最短路径

1.准确解释图的有关术语,比较图的一般存储形式的特点;

2.准确比较先深搜索和先广搜索算法思想,正确运用先深搜索解决应用问题;

3.正确运用构造最小生成树的两个基本算法(Kruskal算和Prim算法);

4.正确运用求最短路径问题的Dijkstra算法。

图属于复杂的数据结构,图与网络结构,与最优化问题有着密切联系。通过对图结构算法的教学,培养学习者的空间想象力和解决实际问题的能力。通过剖析求解图问题的算法,指导学习者深入思维,创造好的算法和好的实现算法的方法。配合上机练习,使学习者受到编制大型程序的训练。

 

第十讲 排序(6h)

10.1 基本概念

10.2 插入排序

10.3 交换排序

10.4 选择排序

10.5 合并排序

10.6 基数排序

1.准确解释排序算法的分类

2.正确运用插入排序、交换排序、选择排序和合并排序的一般方法;

3.正确运用基本基数排序算法;

4.正确比较不同排序方法的性能特点、效率和适用情况。

通过求解排序问题,训练学习者算法设计能力,并能把排序算法中用到的算法设计技术移植到求解其它问题的算法设计中去。

 

复习和答疑(2h)


 


参考资料

(1)教材

      陈卫卫,王庆瑞编著.数据结构与算法(第二版).北京:高等教育出版社, 2015.07

               (“十二五”普通高等教育本科国家级规划教材)

         部分参考答案下载地址:http://pan.baidu.com/s/1o83yAi2 (pdf文件,若下载后后缀消失,请手工添加文件后缀)

(2)参考书

l  张铭等编著. 数据结构与算法.北京:高等教育出版社, 2008

l  陈越主编. 数据结构. 北京:高等教育出版社, 2012

l  Robert Sedgewick著,周良忠  译.C算法(第一卷,基础、数据结构、排序和搜索)(第三版).北京:人民邮电出版社 POSTS & TELECOM  PRESS,2004

l  Robert Sedgewick著,周良忠  译.C算法(第二卷 图算法).北京:人民邮电出版社 POSTS & TELECOM  PRESS,2004

l  计算机程序设计艺术(第3版).Donald E.Knuth  著,苏运霖  译.北京:国防工业出版社 Addison Wesley,2002

第1卷  基本算法

第2卷  半数值算法

第3卷  排序与查找

 

常见问题

本课程的学习者,要注意以下事项,确保教学活动能够深入、有效地进行。

l要事先具备基本的C语言基础知识,避免降低听课效果。

l视频授课的内容是基础的核心内容,要认真学习,细心领会。

l要按时完成教师指定的作业,尤其是上机实践作业。

l要积极参与师生互动,主动获得教师的指导。