武汉大学

图片
课程概述

从本质上讲,数据结构属于编程类的课程,是程序设计语言课程的进阶篇。首先,程序是对数据的操作,由输入产生输出。对于比较复杂的数据,就需要从数据结构的角度来组织和存储数据,如采用数组还是链表存储结构更加高效;另外,对于比较复杂的数据操作,就需要采用一些特定的数据结构来求解,如判断一个表达式中的括号是否匹配,就需要采用栈来处理。所以数据结构课程中讲解人们在软件开发中常见的各种数据结构,并从逻辑结构到存储结构,再到运算算法设计3个层面加以学习。

程序设计解决问题往往有多种方法,且不同方法之间的效率可能相差甚远。程序的时间和空间效率,不仅跟数据的组织方式有关,也跟处理流程的巧妙程度有关。本课程将介绍有关数据组织、算法设计、时间和空间效率的概念和通用分析方法,帮助学生学会数据的组织方法和一些典型算法的实现,能够针对问题的应用背景分析,选择合适的数据结构,从而培养高级程序设计技能。

从计算机科学专业的课程设置来看,数据结构是重要的专业基础课。在计算机软件类课程体系中处于承上启下的核心地位,它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法,另一方面为进一步学习其他专业课(如算法设计与分析、操作系统、软件工程等)奠定坚实的理论与实践基础。


授课目标
通过本课程的学习,使学习者具备基本的数据组织和数据处理能力,在求解问题时选择适当的数据结构、存储结构及相应算法设计的能力,并且能够创造性地进行算法设计和程序设计。
证书要求

     通过视频学习,完成测试、作业和考试。总成绩由各分项成绩汇总后评定设置“合格”(达到60分)、“优秀”(达到80分)两档课程标准,由任课教师签发课程结业证书,其中成绩“优秀”者将颁发优秀证书。


预备知识

C语言程序设计。具备初步的C程序设计知识,将有助于深入学习本课程的内容。


授课大纲

1 绪论

  1讲―数据结构总览

  2讲―什么是数据结构

  3讲―数据结构求解问题的过程

  4讲―算法及其描述

  5讲―算法分析基础

  6讲―其他情况的算法分析

 第7讲-本周小结

2 线性表(上)

  1讲―线性表的基本概念

  2讲―线性表的顺序存储结构

  3讲―顺序表算法设计

  4讲―单链表

  5讲―单链表的算法设计

 第6讲-本周小结

3 线性表(下)

  1讲―双链表

  2讲―循环链表

  3讲―线性表的应用

  4讲―有序表

 第5讲-本周小结

4 栈和队列

  1讲―栈的定义和顺序栈

  2讲―链栈

  3讲―队列的定义和顺序队

  4讲―链队

  5讲―栈和队列求解迷宫问题

 第6讲-本周小结

5

  1讲―串的概念和存储结构

  2讲―串的模式匹配

 第3讲-本周小结

6 递归

  1讲―什么是递归

  2讲―递归算法的设计

 第3讲-本周小结

7 数组和稀疏矩阵

  1讲―数组

  2讲―稀疏矩阵

 第3讲-本周小结

8 树和二叉树(上)

  1讲―树的概念

  2讲―树的运算和存储结构

  3讲―二叉树的概念

  4讲―二叉树的存储结构

  5讲―二叉树基本运算及其实现

 第6讲-本周小结

9 树和二叉树(下)

  1讲―二叉树的遍历

  2讲―二叉树遍历的应用

  3讲―二叉树的构造

  4讲― 线索二叉树

  5讲―哈夫曼树

 第6讲-本周小结

10 图(上)

  1讲―图的概念

  2讲―图的存储结构

  3讲―图的遍历

  4讲―图遍历的应用

 第5讲-本周小结

11周图(下)

  1讲―最小生成树和Pim算法

  2讲―求最小生成树的Kruskal算法

  3讲―最短路径和Dijkstra算法

  4讲―求最短路径的Floyd算法

  5讲―拓扑排序

  6讲―求关键路径

  7讲―小算法解决大问题

 第8讲-本周小结

12 查找

  1讲―查找的概念

  2讲―线性表的查找

  3讲―二叉排序树

  4讲―平衡二叉树

  5讲―B树和B+

  6讲―哈希表的查找

 第7讲-本周小结

13 内排序

  1讲―排序的概念

  2讲―插入排序

  3讲―交换排序

  4讲―选择排序

  5讲―归并排序

  6讲―基数排序

  7讲―內排序的比较

 第8讲-本周小结

14 外排序

  1讲―外排序概述

  2讲―磁盘排序―生成初始归并段

  3讲―磁盘排序―多路平衡归并

  4讲―磁盘排序―最佳归并树

 第5讲-本周小结

参考资料

[1] 数据结构教程(第4版) 清华大学出版社 2013

[2] 数据结构教程学习指导  清华大学出版社 2013

[3] 数据结构教程上机实验指导  清华大学出版社 2013

  

常见问题

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(或者更低版本)编译器。

 

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

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

 

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

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

 

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

A:从理论上讲,算法可以用自然语言、伪码和计算机语言来描述。但一个学习计算机的学生,应该熟练使用计算机语言(如C/C++)来描述算法。如同一个英语专业的学生,必须能够用英语思考问题并表达。学会并熟练采用计算机语言描述算法就是从计算机的角度来求解问题。

 

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

A:这个问题的回答既简单又困难,用我在《数据结构简明教程》中的作者寄语来回答吧:“老师教给我们的是知识,而解决问题需要能力,能力是个性化的,只有通过自已的实训才能得到。对于一个学计算机专业的学生,只有编写和调试n多的程序,才会获得程序设计的能力,继而具备初步的软件设计和开发基础,别无它法。只想听几堂课而不经过大量课外研习和上机实践就想获取这种“能力”是不可能的。”


授课老师
李春葆

李春葆

教授

分享