课程详情
课程评价
spContent=如果说C语言只教您基本驾驶(编程)技术,那么数据结构课程则教您漂移、飞跃、侧驶…(编写高质量程序),和挑选、修理、改装、设计汽车。数据结构课程就像杂草丛中的青蒿,庄稼地里的红高粱,说不定因此给您带来“诺贝尔”奖,助您从生(学生)到猿(程序员),从猿到狮(算法大师)。
—— 课程团队
课程概述

2019年1月课程被教育部评为国家精品在线开放课程

 

1.  课程性质和地位 

 

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

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

          

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

 

2.  课程目标

 

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

 

3.  教学环节

 

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

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

 

4.  课堂教学设计

 

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

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

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

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

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

       

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


5.  实践教学设计

 

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

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

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

 

6.  教学模式设计

 

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

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

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

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

授课目标

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

课程大纲
预备知识

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

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

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

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

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

证书要求

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

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

参考资料

(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要积极参与师生互动,主动获得教师的指导。