数据结构与算法
分享
课程详情
课程评价
spContent=“数据结构与算法”是计算机相关学科的专业基础核心课程,对应于学科中问题求解的理论、抽象和设计的方法论,在学科知识体系中处于核心位置。课程涉及构筑计算机求解问题过程的两大基石:刻画实际问题中信息及其关系的数据结构和描述问题解决方案的逻辑抽象的算法。欢迎小伙伴们加入学习吧!
—— 课程团队
课程概述

我们生活的现实世界中所有物质都可以抽象为数字、文字、声音、图像和视频,这些数据存储在计算机中,构成了信息世界,经过处理后又服务于我们社会生活的方方面面。

人们利用计算机的目的是解决实际的应用问题。数据结构与算法的研究涉及构筑计算机求解问题过程的两大基石:一是刻画实际问题中信息及其关系的数据结构,二是描述问题解决方案的算法。所以说“数据结构与算法”这门课程是计算机专业课程的核心。

作为学科的专业基础核心课程,《数据结构与算法》对应于学科中问题求解的理论、抽象和设计的方法论,在学科知识体系中具有核心的重要位置。它既是对以往课程的深入和扩展,也为深入地学习其他专业课程打下基础,课程中涉及到的基本的线性结构、树、图等数据结构和查找、排序算法,是计算机科学的基本功。B+树、散列(Hash)等高级数据结构,也是数据库、操作系统、编译原理、计算机网络等重要专业课程的基础。本课程在计算机学科中与其他课程的关系如图 1 所示。


数据结构及其处理算法是设计与实现系统软件和大型应用软件的重要基础,“数据结构与算法”课程是计算机相关专业重要的专业技术基础课程。该课程的内容对于培养学生的计算思维、系统分析与设计、算法设计与分析、程序设计与实现等学科基本能力非常重要。本课程系统地介绍了软件开发中常用的数据结构以及相应的存储结构和操作算法,包括常用的查找技术、排序技术、递归技术等。

掌握“数据结构”中的基本概念、合理组织数据的基本方法、高效处理数据的基本算法、常用的经典算法、通用的程序设计技术,以及面对实际问题时选择恰当数据结构并设计高效算法的能力,培养学生用计算思维分析问题的能力,提高学生上机解决较大规模实际问题的能力,为进一步的软件开发打下坚实的基础。

1.课程体系

课程突出数据组织方法与实现技术构成,慕课约30个学时,由基本概念、基本结构(线性、树、图)和基本技术(查找、排序)三大部分组成。基本概念部分重点讲述数据结构定义、内容、方法、评价以及前续基础与课程要求,明确数据结构是什么、学什么、怎么学数据结构。基本结构部分重点讲述线性结构、树、图的逻辑结构、存储结构及其加工处理基本算法。基本技术部分包括查找和排序两类经典技术,贯穿了参数传递、指针处理技术、数组应用、递归与队列等重要的程序设计技术;力求表现经典算法思路,为学习者继续展拓提供线索。M课视频每讲均附有小结,每章均有典型题例,便于总结提高。

2.课程特点

《数据结构与算法》的学习过程是进行复杂程序设计的训练过程。技能培养的重要程度不亚于知识传授。难点在于让学生理解、习惯、掌握构造思维算法方式。针对《数据结构与算法》技术性与综合性较突出的特点,实施了“指导—大运动量实践—反馈”教学法。通过作业练习、课堂练习、课程实习、课程设计实践过程,促进了学生逻辑抽象能力的培养。

3.资源特色

建设了支撑教学过程与自主学习两个面向的立体化教学资源,配备多媒体课件、讲义、书中各算法的实现代码及动画演示等资源支撑教学过程。

面向教学过程资源:与课程内容特点相适应的多媒体课件。以动画展现算法的实现过程,便于对抽象算法本质的理解。

面向自主学习扩展的教学资源:涵盖练习测试、同步训练、教学大纲、课堂视频、参考文献、ACM训练等教学资源,促进学生线上线下主动学习,入门提高。

让我们一起进入《数据结构与算法》课程的学习,共同提高计算思维能力。 


授课目标
通过典型数据结构和算法的学习,以及算法设计和实现的训练,养成敏锐的洞察力。并逐步掌握如何整合信息,提炼数据和数据结构,配置相应的运算和处理算法,完成信息化系统的集成。培养“站在计算机角度”思维的意识和建模能力、解模技巧,达到“传承知识、开发智力、培养能力、提高素质”的目的。
课程大纲

 

第一章 基本概念 [孙挺]

1.1 什么是数据结构

1.2 抽象数据类

1.3 算法及其复杂性估计

 

第二章 线性结构 [刘辛]

 

2.1 引入线性表

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

2.3 线性链表结构类型定义

2.4 线性链表的常用算法实现

2.5 链队列

2.6 循环队列

2.7 顺序栈的表示与实现

2.8 栈的应用

 

第三章 [王宝凤]

 

3.1 树的引入、定义与存储

3.2 二叉树定义及性质

3.3 二叉树的遍历

3.4 二叉搜索树

3.5 平衡二叉树

3.6 哈夫曼树与哈夫曼编码

 

第四章 查找 [王洪峰]

 

4.1 顺序查找

4.2 折半查找

4.3 散列查找


[孙挺]

 

5.1 什么是图

5.2 图的存储表示

5.3 图的遍历

5.4 图的应用

5.5 最小生成树问题

5.6 拓扑排序

 

第六章 排序[王洪峰]

 

6.1 简单排序(冒泡、插入)

6.2 希尔排序

6.3 快速排序

6.4 堆排序

6.5 归并排序

6.6 基数排序

6.7排序算法的比较



预备知识

      学过一门编程语言,具有一定编程基础,即可理解主要内容,因为数据结构本质上是不依赖于编程语言的,且编程练习平台可以接受多种语言代码的提交。但由于算法描述多用类似C语言的伪码,如果学过C语言会更容易接受。

如果预修“离散数学”,对计算机处理离散结构的基本理论和方法有较为系统的理解,则对更扎实地掌握本课程内容有很大帮助,但并不是必须的。


证书要求

     这门课的一个重要目的是,帮助大家明白一些经典的数据结构为什么存在、以及在什么情况下可以最好地解决什么样的问题。要做到这一点,非自己动手解决问题不可。

     与程序设计课程类似,每一周的课后,我们都留有两类练习,一类是在线完成的选择、是非或填空题;一类是在程序设计能力的配套练习网站ACM(http://acm.zknu.edu.cn)上的编程练习题。你可以自己注册帐户,随时进行练习,并不限于发布练习的时段。

      课程过半时,我们将安排一次期中考试,是在线完成的选择、是非或填空题,不包括编程题。期中考试在两周内完成均有效。

     最后,在期末后一周,我们会安排一次在线期末考试,需要在某一天内用连续的120分钟完成。

 

     本课程获得证书的资格,由以下因素决定:

  1. 编程练习:必须在期末考试前在ACM(http://acm.zknu.edu.cn)课程题目集中获得200分及以上,才有资格获得证书,但是分数不会带入总评成绩;

  2. 期中考试:得分占总评分数的40%

  3. 期末考试:得分占总评分数的60%

    此外,若你的期末考试成绩高于期中考试或者无期中成绩,则期末占100%;若你的期末考试成绩低于期中考试,则期中考试占40%,期末考试占60%


     满足条件1并且总评成绩达到60分及以上者,可以获得本课程的合格证书。


参考资料

1.《数据结构》(C语言版),严蔚敏 吴伟民 编著,清华大学出版社,2016年1月

2.《数据结构题集》,严蔚敏 吴伟民  米宁 编著,清华大学出版社,2015年11月

3. 课程练习网站:

· http://acm.zknu.edu.cn 提供编程体验平台。 



常见问题

Q1:本课程的选课条件是什么

A:本课程的主要对象是大学本、专科生,但不限于大学生。只要你是计算机编程爱好者、具有基本的C语言程序设计基础,有热情,有决心,就能学好。

 

Q2:我没有学过C语言,但学过JavaC#或者Python等语言,是否可以选学本课程?

AJavaC#或者Python等语言的编程思路和C/C++语言是相通的,尽管本课程是主要采用C语言描述算法,但你采用JavaC#或者Python等语言描述算法完全是可以的。

 

Q3你的数据结构与算法课程为什么说采用C/C++语言来描述算法?

A:本课程的算法主要采用C语言面向过程方式来描述的。由于纯C语言中调用函数时,只有实参到形参的单向值传递,算法设计不方便简洁,而C++语言中提供了引用运算符(&)可以方便地实现实参和形参的双向传递。这里说采用C/C++语言来描述算法,实际上仅仅使用了C++语言中的引用运算符,其他都是采用纯C语言的知识。

 

Q4:你的数据结构与算法课程为什么不采用C++面向对象方法来描述算法?

A:采用C++面向对象方法可以更加完美地描述算法,但考虑到绝大部分在校学生学习数据结构与算法课程时,仅仅学习过C语言,还没有学习过C++面向对象程序设计,所以本课程主要采用C语言面向过程方式来描述算法。

 

Q5数据结构与算法课程的上机实验采用什么编译器?

A:如果采用C/C++语言描述算法,可以采用Visual C++ 6.0Dev C++Borland C++或者Visual Studio .NETC/C++语言编译器上机实验。由于算法中采用引用运算符(&),所以不适合采用Turbo C 2.0(或者更低版本)编译器,除非你将算法采用标准C语言描述,不使用引用运算符(&)。

 

Q6:数据结构与算法课程和算法设计与分析课程有什么不同和联系?

A:数据结构与算法课程主要学习各种数据结构,其算法设计是围绕各种数据结构展开的。而算法设计与分析课程学习更通用的算法设计方法,即算法策略,如动态规划、贪心法和分支限界法等。

 

Q7:数据结构与算法课程中讲解哪些数据结构?

A:数据结构课程中讲解的数据结构从逻辑结构上分为线性结构、树形结构和图三类。线性结构包括线性表、栈和队列等,树形结构包括树和二叉树等。

 

Q8:数据结构中的算法为什么需要用计算机语言描述出来?

A:从理论上讲,算法可以用自然语言、伪码和计算机语言来描述。但一个学习计算机的学生,应该熟练使用计算机语言(如C/C++)来描述算法。从而才能够从计算机的角度来求解问题。

 

Q9:如何学好数据结构与算法课程?

A:老师传授给你的是知识,而解决问题需要能力,能力是个性化的,只有通过自已的实训才能得到。对于一个对计算机编程感兴趣的学生,只有编写和调试n多的程序,才能获得程序设计的能力,继而具备初步的软件设计和开发基础。只想听几堂课而不进行大量课外研习和上机实践就想获取这种“能力”是不可能的。