- 第一讲
- 第1章 概论——2（存储结构，ADT，算法特征，算法量度）
- 第2章 线性表、栈和队列——3（栈和表达式,栈和递归）
- 第2章 线性表、栈和队列——4（栈和递归,队列）
- 第3章 字符串——1（字符串概念、ADT、简单模式匹配
- 第3章 字符串——2（模式匹配、KMP算法）
- 第4章 二叉树——1（二叉树的概念和ADT）
- 第4章 二叉树——3（二叉树的非递归后序周游）
- 第4章 二叉树——4（二叉树的广度周游，二叉树实现和穿线二叉树）
- 第2章 线性表、栈和队列——1（线性表ADT和存储结构）
- 第2章 线性表、栈和队列——2（栈的存储和应用）
- 第4章 二叉树——7（堆）
- 第4章 二叉树——8（Huffman树）
- 第4章 二叉树——5（二叉树的线索化）
- 第5章 树——1（树的基本概念和周游）
- 第4章 二叉树——6（二叉搜索树
- 第5章 树——3（树的 顺序存储、带右链先根）
- 第5章 树——2（树的广度周游和存储
- 第6章 图——4（图的单源最短路径Dijstra算法）
- 第5章 树——2（树的广度周游和存储
- 第5章 树——4（树的 左链层次次序表示,带度数后根,树计数）
- 第6章 图——5（图的Floyd算法和最小支持树的prim算法
- 第6章 图——6（图的kruskal算法）
- 第7章 内排序——1（内排序基本概念和插入排序）
- 第6章 图——1（图的概念）
- 第6章 图——2（图的存储和周游
- 第12章 高级树结构——3（AVL树的效率， 自组织数据结构，伸展树，决策树）
- 第12章 高级树结构——2（AVL树）
- 第12章 高级树结构——1（Trie树，最佳二叉搜索树）
- 第11章 高级线性表——1（多维数组，矩阵，广义表，内存管理）
- 第10章 索引——3（B树，索引的性能分析）
- 第10章 索引——2（B树,B树）
- 第10章 索引——1（索引基本概念，线性索引，倒排索引）
- 第9章 检索——3（闭散列，探测算法）
- 第9章 检索——2（集合检索，散列函数，开散列法）
- 第9章 检索——1（检索的基本概念，顺序检索）
- 第8章 文件管理和外排序——3（败方树，多路归并）
- 第8章 文件管理和外排序——2（置换选择排序、二路归并、选择树）
- 第8章 文件管理和外排序——1（文件的基本概念）
- 第7章 内排序——7（总结、地址排序）
- 第7章 内排序——6（基数排序）
- 第6章 图——3（图的拓扑排序）
- 第7章 内排序——2（二分插入排序,冒泡排序和shell排序）
- 第7章 内排序——3（快速排序）
- 第7章 内排序——4（归并排序）
- 第7章 内排序——5（堆排序 、桶式排序）
课程名称：数据结构（Data Structure）
任课教师：常宝宝（北京大学计算语言学研究所副教授）
学时：4学时/周 （2学时授课，2学时上机）
课程概要：
以C++语言为基础，重点介绍线性表、栈、对列、树和二叉树等基本数据结构和相关算法、各种检索和排序算法。概要介绍图结构和相关算法。除详细讲授数据基本概念和具体算法外，对每种数据结构给出其C++语言实现，并给出定性或定量的算法分析。
课程目标：
（1） 进一步培养学生的程序设计能力，加深对C++语言的掌握和运用。
（2） 培养学生学会分析研究计算机加工的数据对象的特性，以便选择适当的数据结构以及相应的算法。
（3） 初步掌握算法的时间分析和空间分析的技巧。
（4） 通过同步上机实习，进一步锻炼学生的动手能力，培养学生解决实际问题的能力。
1.1 为什么要学习数据结构 1.2 什么是数据结构 1.3 抽象数据类型 1.4 算法的特性及分类 1.5 算法的效率度量 1.6 数据结构的选择和评价
北京大学信息学院 版权所有,转载或翻印必究 Page 12
1.1 为什么要学习数据结构
计算机软件与理论学科的专业基础课程 后续专业课程学习的必要知识与技能准备
编译技术要使用栈,散列表及语法树 操作系统中用队列,存储管理表及目录树 数据库系统运用线性表,多链表,及索引树 etc.
增强读者求解复杂问题的能力
北京大学信息学院 版权所有,转载或翻印必究 Page 13
1.2 什么是数据结构 (data structure)
数据的逻辑结构 数据的存储结构 数据的运算
北京大学信息学院 版权所有,转载或翻印必究 Page 14
1.2.1 数据的逻辑结构
反映了我们对数据含义的解释 数据的逻辑结构可以用一组数据(表示为结点集合 K),以及这些数据之间的一组二元关系(关系集合 R)来表示:( K ,R )
K是由有限个结点组成的集合,每一个结点都代表一个数据 或一组有明确结构的数据 而关系集R是定义在集合K上的一组关系,其中每个关系 (relation) r(r∈R)都是K×K上的二元关系,用它描述结 点数据之间的逻辑关系
北京大学信息学院 版权所有,转载或翻印必究 Page 15
数据的逻辑结构(示例)
家族人员
把每个成员个体的属性描述作为数据结点,而全部人员组成 结点集K 家族的各类亲属关系就是一组关系R, 其中如母系血缘关系 r,远亲关系r*,和非血缘的亲情关系r"等等,每一个关系要 给出具体人员的关系元组 例如:母子关系(王爱莲,张选) 兄弟关系(张选,张立) 妯娌关系 (王爱莲,李美英)
北京大学信息学院 版权所有,转载或翻印必究 Page 16
结点的类型
基本数据类型
整数类型(integer):该类型规定了所能表示的整数范围, 在计算机中一般使用1个字节到4个字节来存储整数 实数类型(real):计算机的浮点数据类型所能表示的数值范 围和精度是有限的. 机器一般使用4个字节到8个字节来存 储浮点数 布尔类型(boolean):取值为真(true)和假(false),在 C++语言中一般使用整数0表示false,用非0表示真
北京大学信息学院 版权所有,转载或翻印必究 Page 17
结点的类型
基本数据类型
字符类型(char):用单个字节(8bit,最高位bit为 0)表示ASCII字符集中的字符.
汉字符号需要使用2个字节(每个字节的最高位bit为1) 的编码,单个字节对于汉字是没有独立含义的.
北京大学信息学院
版权所有,转载或翻印必究
Page 18
在C++中把双字节表示中文符号的字节类型称 为w_char类型(wide character). 目前国际上已经采用了统一的扩展字符集合标准 UNICODE,这一标准允许英,日,韩,阿拉伯 语等文字的混合文字处理
北京大学信息学院
版权所有,转载或翻印必究
Page 19
结点的类型
基本数据类型
指针类型(pointer):用于表示机器内存地址,指 针表示指向某一内存单元的地址.
由于机器的指令系统一般采用32 bit或64bit的地址长 度,所以指针类型也相应地用4个字节或8个字节来表示 一个指针.
北京大学信息学院 版权所有,转载或翻印必究 Page 20
指针值的存储和指针值的运算方式,在形式上与 正整数相似. 但指针的运算一般仅限于两个指针地址的比较, 加减,或对一个指针增减一个整数量等
北京大学信息学院
版权所有,转载或翻印必究
Page 21
结点的类型
复合数据类型
复合类型是由基本数据类型组合而成的数据结构类型.例 如:在程序语言中常用的数组类型,结构(记录)类型等皆 属复合数据类型 复合数据类型本身,又可以参与定义结构更为复杂的结点类 型. 结点的类型不限于基本数据类型,可以根据应用的需要来灵 活定义
北京大学信息学院 版权所有,转载或翻印必究 Page 22
结构的分类
讨论逻辑结构(K,R)的分类,一般把讨论重点放在 关系集R上.用R的性质来刻划数据结构的特点,并对 数据结构进行分类
线性结构(linear structure) 树型结构(tree structure) 图结构(graph structure)
北京大学信息学院 版权所有,转载或翻印必究 Page 23
线性结构
这种结构在程序设计中应用最多. 它的关系r 是一种线性关系,或称为"前后关系",有时 也称为"大小关系".关系r是有向的,且满足全序性和 单索性等约束条件
全序性是指,线性结构的全部结点两两皆可以比较前后(关 系r) 单索性是指,每一个结点x都存在唯一的一个直接后继结点 y.如果其他结点z在y之前,则这个z也一定在x之前,不会 在x,y之间