《数据结构》学习指导

1、数据结构学习指导 说明：本指导以数据结构（C语言版）（严蔚敏等编著，清华大学出版社1997 年出版，国家级优秀教材特等奖 ）和数据结构题集 （严蔚敏等编著 ,清华大学 出版社 1999年出版）为教学主要参考书。 一、绪论 1、学习目的： 明确数据结构课程在本专业知识结构中的地位，作用。课程的 特点，教学的要求，方法。明确数据结构所研究的问题以及有关基本概念。初 步掌握抽象数据类型的表示与实现，初步明确算法分析的作用与分析的重点， 初步掌握算法分析的方法。 矚慫润厲钐瘗睞枥庑赖賃軔朧。 2、学习重点：数据的逻辑结构、存储结构及其算法，数据结构的有关概念，抽 象数据类型及其表示与实现，算法，算法设

2、计的要求，算法的时间复杂度和算 法的空间复杂度。 聞創沟燴鐺險爱氇谴净祸測樅。 3、学习难点： 数据结构的有关概念， 抽象数据类型的表示与实现；算法的时间 复杂度分析。 4、课程内容与基本要求 （一）数据结构的引入 （1）三个世界：现实世界，信息世界，机器世界。 数据结构要解决的就是实现从现实世界到信息世界， 再由信息世界到机器世界 的转换，从而实现用计算机来解决问题的目的。 残骛楼諍锩瀨濟溆塹籟婭骒東。 （2）非数值问题 （结合三个世界讲 ）：控制，管理，数据处理 （3）数值问题：数值计算 （4）数据结构：从学科角度讲，数据结构是一门研究非数值计算的程序设计问题 中计算机操作对象以及他们之间

3、的关系和操作等等的学科。 酽锕极額閉镇桧猪訣锥顧荭 钯。 （二）课程的地位，性质，作用。 （1）地位: 计算机专业的核心课程之一。 （2）性质 : 算法理论基础和软件设计的技术基础课。 （3）作用: 程序设计的基础， 编译程序，操作系统， 数据库系统及软件系统和应 用程序的基础 （三）数据结构的产生和发展 （四）课程的特点，学习的要求 教材：数据结构（C语言版）严蔚敏等编著 北京 清华大学出版社1997年 参考书：数据结构许卓群等编著 北京 高等教育出版社 1987年 数据结构实用教程（C/C+描述）徐孝凯北京清华大学出版社1999年 数据结构题集严蔚敏等编著 北京 清华大学出版社 1999年

4、 数据结构导学苏光奎等编著 北京 清华大学出版社 20XX 年 数据结构 （C 语言篇 ） 习题与解析 李春葆编著 北京 清华大学出版社 20XX 年 数据结构实验指导书 唐开山 自编讲义 20XX 年 (五) 基本概念和术语 数据 数据元素 数据对象 (4) 数据结构 :按某种逻辑关系组织起来的一批数据， 按一定的存储表示方式把它 存储到计算机的存储器中，并在这些数据上定义了一个运算的集合，叫做一个 数据结构。 彈贸摄尔霁毙攬砖卤庑诒尔肤。 数据结构综合三方面的内容：数据的逻辑结构，数据的存储结构及其运算。且 不涉及元素本身的内容。 (5) 结构：数据元素相互之间的关系。 a) 四类基本结构

5、； b) 表示形式 (6) 逻辑结构 (7) 物理结构(存储结构 ) (8) 元素或结点 (9) 数据域 (10) 数据元素之间关系的两种表示方法：顺序映像 顺序存储结构；非顺序映 像链式存储结构。 (11) 存储结构的描述 (12) 数据类型 (13) 抽象数据类型 (14) 抽象数据类型按其值的不同特性分为三种类型 (15) 抽象数据类型可用三元组表示 (16) 多型数据类型 (六) 抽象数据类型的表示和实现 概述 用伪码和类 c 语言作为描述工具 (2) 基本约定 (3) 抽象数据类型 triplet 的表示和实现 赋值参数和引用参数 部分基本操作及其实现：构造三元组 (七) 算法和算法

6、分析 算法的概念 算法的五个特性 有穷性 确定性 可行性 输入 输出 (3) 算法设计的要求 正确性 可读性健壮性效率与低存储量需求 (4) 算法效率的度量 事后统计方法 事前分析估算的方法 (5) 时间复杂度： 时间复杂度的确定：算法中基本操作，重复执行的次数是问题规模 n 的基本 函数f(n),算法的时间量度记做T(n)=0(f(n),则f(n)为该问题的渐进时间复杂， 简称时间复杂度。 謀荞抟箧飆鐸怼类蒋薔點鉍杂。 只需选择一种基本操作来讨论算法的时间复杂度。只需求出它关于 n 的增长 率为何即可。 线性查找的平均时间复杂度和最坏时间复杂度。 (6) 空间复杂度：算法的存储空间需求。 5

7、、作业 P7 1.3, 1.5，P8 1.8 中、(3)、(5)、(7)、(8),P10 1.12, 1.14 厦礴恳蹒骈 時盡继價骚卺癩龔。 二、线性表 1、 学习目的：明确线性表的概念与基本运算；明确顺序表和链表的定义、组织 形式、结构特征和类型说明；熟练掌握线性表的顺序存储结构和链接存储结构 (单链表、循环链表、双向链表)及其基本运算的实现原理和方法。茕桢广鳓鯡选 块网羈泪镀齐鈞。 2、 学习重点：线性表的定义及逻辑上的特点；顺序表上插入、删除和定位运算 的实现；单链表的结构特点及类型说明；头指针和头结点的作用及区别；指针 操作；定位、删除、插入运算在单链表上的实现；循环链表、双链表的结

8、构特 点；循环链表、双链表上删除与插入运算的实现。鹅娅尽損鹤惨歷茏鴛賴縈诘聾。 3、学习难点：指针操作；删除、插入运算中的指针操作顺序；双链表上指针的 操作顺序。 4、课程内容与基本要求 籟丛妈羥为贍债蛏练淨槠挞曉。 (一) 线性表类型的定义 (1) 线性表的四个特性 定义 (3) 抽象数据类型线性表的定义 (二) 线性表的顺序表示和实现 (1) 有关概念 线性表的顺序表示 存储位置公式 线性表的动态分配顺序存储结构，及初始化的操作。 基本操作 结构定义 初始化：in tin itlist_sq(sqlist *l) 线性表中插入元素：int listinsert(sqlist *l,int

9、i,int e) 动态存储分配函数realloc的使用 线性表中删除元素：int listdelete_sq (sqlist *l int i, int *e)預頌圣鉉儐歲龈讶骅籴買闥龅。 算法分析 n+11n 插入：期望值(平均次数)：Eis二二 pi(n-i+1)=(n-i+1)= n+1 -2 n 1 n n 删除：期望值(平均次数)：Edl=v qi( n-1)=a (n-1)= i =1n i #2 两个集合归并的不同合并法：条件：有序与无序渗釤呛俨匀谔鱉调硯錦鋇絨钞。 (三) 线性链表 (1) 线性表顺序存储结构的缺点 (2) 结点，线性表链式存储结构及其特点 每个结点只包含一个指

10、针域的链表称为线性链表或单链表 (3) 线性表的单链表存储结构定义 带头结点的单链表 线性链表的基本操作 得到第 i 个元素操作 getelem_l(linklist l ,lnt i,elemtype *e) 铙誅卧泻噦圣骋贶頂廡缝勵 罴。 插入元素操作 listinsert_l(linklist l,int i,elemtype e) 删除第 i 个元素操作 listdelete_l(linklist l,int i,elemtype *e) 擁締凤袜备訊顎轮烂蔷報赢 无。 建立单链表操作 creatlist_l(linklist l,int n) 合并两个单链表 mergelist_l(

11、linklist la,linklist lb,linklist lc) 贓熱俣阃歲匱阊邺镓騷鯛 汉鼉。 (四) 线性表的静态单链表存储结构 (1) 结构描述 (2) 存储线性表的特点 基本算法 ： 查找元素算法 int locateelem_sq(slinklist s,int e) 求 (A-B)U(B-A) 算法 (五) 循环链表 (1) 特点：单链表中最后一个结点的指针域指向头结点，形成一个环。 (2) 逻辑结构 (3) 只设立尾指针将两个线性表并成一个表的操作 (4) 循环链表结束判断 (六) 双向链表 (1) 特点：结点中有两个指针域，其一指向直接后继，另一指向直接前趋 (2) 逻

12、辑结构 (3) 双向链表存储结构的结点定义 (4) 带头结点的双向循环链表 逻辑结构 结点指针关系 插入结点时指针变化状况 删除结点的指 针变化状况 带头结点双向循环链表的插入操作list in sert_dul(duli nklist l,i nt i,i nt e)坛搏乡囂 忏蒌鍥铃氈淚跻馱釣。 带头结点双向循环链表的删除操作listdelete_dul(dulinklist l,int i,int *e)蜡變黲 癟報伥铉锚鈰赘籜葦繯。 (7) 带头结点的单链线性表应用举例 在第个元素之前插入元素 int listinsert_l(linklist l,int i,int e) 買鲷鴯譖昙

13、膚遙闫撷凄届嬌 擻。 合并两个非递减单链线性表 int mergelist_l(linklist la,linklist lb,linklist *le) 綾镝鯛駕櫬鹕踪韦辚糴飙钪麦。 (七) 一元多项式的表示及相加 (1) 一元多项式的逻辑结构 (2) 两种结构表示，重点讨论链式存储结构 (3) 抽象数据类型一元多项式的定义 抽象数据类型 polynomial 的实现 (5) 基本操作的算法描述 建立一有序链表 void crealepolyn(polynomail p,int m) 合并两个多项式 void addpolyn(polynomial pa,polynomail pb) 驅踬髏

14、彦浃绥譎饴憂锦 諑琼针。 了解两个多项式相乘 5、作业 P13 2.1，2.2，2.3，2.4，2.5， 2.6，2.7，2.8，2.9，2.11， 2.19，2.21， 2.22 猫虿驢绘燈鮒诛髅貺庑献鵬缩。 三、栈和队列 1、学习目的： 明确栈和队列的概念、 特征及在其上所定义的基本运算，熟练掌 握在两种存储结构上对栈和队列所施加的基本运算的实现。掌握循环队列的基 本运算；了解多栈共享邻接空间；了解双端队列。 锹籁饗迳琐筆襖鸥娅薔嗚訝摈。 2、学习重点： 栈的定义及逻辑特点； 入栈、出栈等运算在两种存储结构栈上的 实现；队列的定义及逻辑特点； 入队、出队等运算在两种存储结构栈上的实现； 循

15、环队列的顺序存储结构及其运算实现。 構氽頑黉碩饨荠龈话骛門戲鷯。 3、学习难点：循环队列的队空、队满判断条件；循环队列上的插入、 删除操作。 4、课程内容与基本要求 (一) 栈的有关概念 (1) 栈的引入 (2) 栈的定义 (3) 栈的逻辑结构及进出栈 栈的抽象数据类型的定义 (ADT stack) 栈的插入元素的操作称入栈 push 栈的删除栈顶元素的操作称出栈 pop (二) 栈的表示和实现 (1) 顺序栈 结构定义 顺序栈表示 顺序栈的基本操作 基本操作的算法描述 a) 栈初始化 int initstack(sqstack s) b) 访问栈顶 int getop(sqstack s,s

16、elemtype e) c) 入栈 int push(sqstack s,selemtype e) d) 出栈 int pop(sqstack s,selemtype *e) (2) 链式栈 结构定义 链式栈表示 链式栈的基本操作 基本操作 (三) 栈的应用举例 (1) 数制转换：算法 (2) 括号匹配的检验：思路 (3) 行编辑程序：思路 (4) 迷宫求解和表达式求值作为实践内容 (四) 队列的有关概念 (1) 定义 (2) 特点：是一种先进先出(FIFO)结构 (3) 队列的表示 (4) 队列的抽象数据类型定义 (5) 关于双端队列 (五) 队列的顺序存储结构 (1) 结构定义 (2) 基

17、本操作 初始化操作int initsqueue(squeue *sq) 入队操作 int putsq(squeue *sq, elemtype e) 出队操作 int outsq(squeue *sq, elemtype *e) (六) 队列的链式存储表示和基本操作(带头结点) (1) 结构定义：结点、结构 (2) 链式队列的表示 (七) 队列的链式存储结构的基本操作(带头结点) (1) 初始化 入队 出队 (八) 循环队列 (1) 循环队列的引入：顺序存储结构中，一般顺序队列的缺点 (2) 循环队列的处理方法 (3) 队满与队空的判断： 两种方法：设置一标志以区别是队满还是队空；另一种方法是

18、损失一个元素 空间，一般用后一种方法。 队满判断：(q.rear+1)%maxsize=q.fr ont; 队空：q.front=q.rear; 指针(下标)移动增1的处理： q.fro nt=(q.fro nt+1)%maxsize; q.rear=(q.rear+1)%maxsize; (九) 循环队列的基本操作 (1) 结构定义 (2) 初始化循环队列 int initqueue(squque *q) (3) 求队列长度 int queuelength (sqqueue q) 入队 int enqueue(sqqueue *q,elemtype e) 出队 int dequeue (sq

19、queue *q, elemtype *e) 5、作业 p22 3.3，3.4，3.7， 3.12，3.13，3.28，3.30 四、串和数组 1、学习目的：明确串的概念、 存储方式和常用的串运算；明确多维数组的结构 特点和在内存中的两种顺序存储方式；掌握串的基本运算及其初步应用；了解 串操作在文本编辑中的应用。明确数组的概念、数组的顺序存储的特点；掌握 数组的基本操作方法；掌握稀疏矩阵和特殊矩阵的存储方法；了解广义表的定 义和基本运算。 輒峄陽檉簖疖網儂號泶蛴镧釃。 2、学习重点：串的基本概念、基本运算；串的两种存储方式；多维数组的逻辑 结构；多维组的两种顺序存储方式；计算给定元素在存储区中

20、的地址；对称矩 阵、三角矩阵的压缩存储方式；稀疏矩阵的三元组表表示方法。 尧侧閆繭絳闕绚勵蜆 贅瀝纰縭。 3、学习难点： 串的基本运算及其综合应用； 稀疏矩阵的压缩存储表示下的运算 的实现。 4、课程内容与基本要求 (一) 串的基本概念 (1) 定义： (2) 子串、主串、位置、相等、空格串 (3) 特点 :串的逻辑结构与线性表极为相似；串的操作与线性表差别很大，线性 表中一般以单链表操作为主， 而在串操作中常以串的整体为操作对象。 识饒鎂錕缢 灩筧嚌俨淒侬减攙。 (4) 串的抽象数据类型的定义 (二) 五种基本操作： (1) 串赋值 strassign， (2) 串比较 strcompare

21、， (3) 求串长 度 strlength，(4) 串连接 concat， (5) 求子串 substring 凍鈹鋨劳臘锴痫婦胫籴铍賄鹗。 (三) 串的表示和实现(三种表示) (1) 定长顺序存储表示 结构定义 串赋值： Int strassign(sstring s1,sstring s2) 串比较： Int strcompare (sstring s1,sstring s2) 求串长度： Int strlen(sstring s) 串连接： Int concat (sstring s1,sstring s2) 求子串：int substr(sstring t,sstring s,int

22、pos,int len恥諤銪灭萦欢煬鞏鹜錦聰櫻郐。 (2) 堆内存存储表示 实现特点 (堆分配存储含义 )：动态分配一组地址连续的存储单元有存放串值 字符序列。 结构定义，注意动态分配 基本操作 (a) 生成操作 strassign(hstring t,char *chars) (b) 求长度 strlength (c) 两串比较 int strcompare (hstring s,hstring t) (d) 清空串 clearstring (hstring s) (e) 串联接int concat (hstring t,hstring s1,hstring s2鯊腎鑰诎漣鉀沩懼統庫摇饬缗。

23、 (f) 求子串 int substring (hstring sub, hstring s,int pos,int len)硕癘鄴颃 诌攆檸攜驤蔹鸶胶据。 (g) 子串定位 int index(hstring s,hstring t,int pos) (3) 串的块链表存储表示 概念 结构定义 串处理效率 (存储密度 ) 优缺点 (四) 串操作应用举例 (了解) (1) 文本编辑的基本操作 查找、输入、删除、替换 (2) 文本编辑的实现方法 建立行表：行号、起始地址、长度等 页表：页号、起始地址、长度 设立页、行、字符指针。用动态数组实现为方便 光标的捕捉 (五) 数组的概念 (1) 特点：

24、线性表的扩充 表中的数据元素本身也是一个数据结构 (2) 数组的定义：抽象数据类型数组的定义形式 (3) 二维数组的解释 (4) 数组的顺序表示 二维数组的两种存储方式：以列序为主；以行序为主 储位置的公式：二维；多维 (5) 结构定义 (6) 基本操作算法 初始化 int initarray(array *a,int dim) va_start(ap,dim) ap是存放各维容量的数组 求下标元素a(j0,j1,j2jOdm的地址 int locate(array a,va_list ap,int *off) (六) 矩阵的压缩存储 (1) 压缩存储的有关概念 压缩存储：为多个值相同的元素分

25、配一个存储空间，对零元不分配空间 特殊矩阵：值相同的元素或者零元素在矩阵中的颁布有一定规律 稀疏矩阵：非零元个数的矩阵 (2) 特殊矩阵 对称矩阵 (a) 概念 (b) 压缩存储方法 (c) 下标对应关系 三角矩阵 对角矩阵 (3) 稀疏矩阵 含义 ADT 稀疏矩阵的定义 压缩存储 (三种方法 )：(a) 三元组顺序表 (b) 行逻辑链接的顺序表 (c) 十字 链表 (4) 三元组顺序表 三元组表示 结构定义 转置算法 1( 保持以行为存储 ) int tpm(tsmatrix m, tsmatrix t) 转置算法 2( 较高效的算法。了解 ) (5) 了解行逻辑链接的顺序表和十字链表 (七

26、) 广义表的有关概念 . (1) 线性表的推广 ,也称为列表 . (2) 形式 (3) 有关概念 (4) 三个重要结论 (5) 求表头和表尾 (八) 广义表的存储结构 (了解 ) (1) 两种结点结构 . 表结点：用以表示列表 原子结点：用以表示原子 (2) 广义表的头尾链表存储表示 5、作业 P274.3，4.4，4.5，4.6, P29 4.18，4.24 ，P31 5.1，5.2，5.3，5.8，5.10， 5.11 阌擻輳嬪諫迁择楨秘騖輛埙鵜。 五、树和二叉树 1、学习目的： 明确树的基本概念及性质； 明确树的各种存储结构；明确二叉树 的概念及其二叉树的顺序存储表示和链接存储表示；熟练

27、掌握二叉树的性质和 遍历，掌握前序、中序、后序遍历的递归算法与非递归算法；明确线索二叉树 的概念；掌握前序线索化二叉树的有关算法；了解中序、后序线索化二叉树的 有关算法问题；初步掌握树、森林与二叉树的转换；明确哈夫曼树的概念，掌 握哈夫曼树的构造方法并能初步应用。 氬嚕躑竄贸恳彈瀘颔澩纷釓鄧。 2、学习重点：树的存储结构；二叉树的定义、逻辑特点及五种基本形态；二叉 树的性质； 在二叉树上定义的基本运算； 二叉树的链式存储结构及其类型说明； 二叉树的三种遍历方法及其算法；以遍历为基础在二叉树上实现的几种基本运 算；哈夫曼树和哈夫曼算法；森林与二叉树的转换。 釷鹆資贏車贖孙滅獅赘慶獷緞。 3、学习

28、难点： 二叉树的递归定义； 三种遍历的主要区别； 二叉树上的复杂运算； 线索化前序线索二叉树的算法；哈夫曼算法及其应用。森林与二叉树的转换。 怂阐譜鯪迳導嘯畫長凉馴鸨撟。 4、课程内容与基本要求 (一) 树的定义 (1) 树的引入 (2) 树的定义 (递归定义 )及表示 (3) 树的抽象数据类型定义 (4) 树的其他表示形式 . 嵌套集合 广义表 凹入表 (二) 树的基本术语 结点、结点的度、叶子 (终端结点 )、分支结点 (非终端结点 )、树的度、孩子、双 亲、兄弟、祖先、子孙、层次、堂兄弟、树的深度、有序树、无序树、森林。 谚辞調担鈧谄动禪泻類谨觋鸾。 (三) 二叉树的有关概念： (1)

29、概念(递归定义 ) (2) ADT 二叉树的定义 (3) 二叉树的五种基本类型 (四) 二叉树的性质 (1) 二叉树的四个性质及其证明 (2) 满二叉树的概念及特点 (3) 完全二叉树的概念及特点 (五) 二叉树的存储结构 (1) 二叉树的顺序存储结构 结构定义 特点及适用性 (2) 链式存储和二叉树结构 二叉链表和三叉链表结构 二叉链表结点结构定义 基本操作 (六) 编历二叉树 (1) 遍历的概念 (2) 编历二叉树的方法 (3) 三种编历的递归算法定义 先序编历、 中序编历、 后序编历二叉树的操作定义 (4) 编历二叉树的三个递归算法 (5) 编历二叉树的非递归算法 (6) 了解建立二叉树

30、 (七) 线索二叉树的引入、表示及其存储表示 (1) 对二叉树的遍历实质上是对一个非线性结构进行线性化操作。 (2) 在以二叉链表作为存储结构时，结点的前驱和后继信息只能在遍历的动态 过程中得到。 (3) 问题的提出：如何保存这种在遍历过程中得到的信息？ (4) 解决的办法 按某种次序遍历使其变为线索二叉树的过程 线索化 (5) 三种线索二叉树的表示 (6) 二叉树的二叉线索存储表示 (八) 建立线索二叉树及其遍历算法 (1) 建立前序线索二叉树算法 (2) 前序线索二叉树的遍历算法 (3) 建立中序线索二叉树算法 (4) 中序线索二叉树的遍历算法 后序线索二叉树是不完美的 (九) 树的其它存

31、储结构 (1) 双亲 (数组)表示法 方法 存储结构定义 特点 (2) 孩子 (链表)表示法 方法 存储结构定义 特点 与双亲 (数组 )表示法结合起来 嘰觐詿缧铴嗫偽 純铪锩癱恳迹。 (3) (左)孩子 (右)兄弟表示法 (二叉树或二叉链表表示法 ) 方法 存储结构定义 特点 (十) 森林与二叉树的转换 (1) 转换的基础 (2) 树与二叉树之间的对应关系 (3) 森林与二叉树的对应关系 (4) 森林转换成二叉树的定义 (5) 二叉树转换成森林 (十一 ) 树和森林的遍历 (1) 树的遍历 先根遍历树 后根遍历 (2) 森林的遍历 先序遍历森林中序遍历森林 (十二 ) 最优二叉树(赫夫曼树)

32、 (1) 路径及路径长度 路径 路径长度 树的路径长度 完全二叉树是路径长度最短的二叉树。 (2) 树的带权路径长度 带权结点 结点的带权路径长度 树的带权路径长度 (3) 最优二叉树 (赫夫曼树 ) 最优二叉树概念 相同结点及权值构造不同的二叉树得到不同 wpl 的情况 (4) 如何构造赫夫曼树：赫夫曼算法的四个步骤 (5) 图示构造过程。 (十三 ) 赫夫曼编码 (1) 前缀编码： (2) 编码总长最短的二进制前缀编码 (3) 赫夫曼树的存储表示及其有关算法描述 思想方法 顺序存储结构 构造赫夫曼树和求出 n 个字符的赫夫曼编码算法描述。 条件：W有放n个字符的权值(均0) 构造赫夫曼树

33、HT 逆向求每个字符的赫夫曼编码 HC 从根出发，遍历赫夫曼树的算法 (4) 电文示例 (5) 链式存储的赫夫曼树构造及编码生成介绍 5、作业 P38 6.1，6.3，6.4，6.5，P39 6.7, 6.12，6.14，6.15，6.20，P41 6.21， 6.22, 6.23，6.26，6.27，P42 6.42，6.43，6.47 熒绐譏钲鏌觶鷹緇機库圆鍰缄。 六、图 1、学习目的：明确图的基本概念；掌握图的邻接矩阵存储与邻接表存储方法； 明确图的遍历的概念；掌握图的深度优先搜索与宽度优先搜索算法；掌握计算 图的连通分量、构造图的生成树和最小生成树、求图的最短路径、拓补排序和 关键路径

34、的构造方法及其应用；基本掌握求最小生成树、最短路径、关键路径 的算法； 鶼渍螻偉阅劍鲰腎邏蘞阕簣择。 2、学习重点：理解图的定义、术语及其含义；图的邻接矩阵和邻接表表示法； 图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；生成树和最小生成 树的概念；由Prim算法思想构造最小生成树按 Prim算法思想和算法；拓扑序 列、拓扑排序的概念及算法思想和算法；关键路径的概念、算法思想和算法； 最短路径的概念、算法思想和算法。 纣忧蔣氳頑莶驅藥悯骛覲僨鴛。 3、学习难点： 理解与区别图的常用术语； 区别图的两种存储结构的不同点及其 应用场合；求最小生成树算法思想和算法；求关键路径算法思想和算法；求最

35、 短路径算法思想和算法。 颖刍莖蛺饽亿顿裊赔泷涨负這。 4、课程内容与基本要求 (一) 图的有关概念 (1) 几种结构的特点 线性表： “一对一 ”结构 树： “一对多 ”结构 图： “多对多 ”结构 (2) 图的应用广泛 (3) 图的定义 概念 抽象数据类型定义 (4) 图的术语 顶点、弧、弧尾、弧头、有向图、边、无向图 顶点数与边数的关系、完全图、稀疏图、稠密图 权、网、子图 邻接点、依附、相关联、顶点的度 无向图 出度、入度 有向图 路径、回路、简单路径 连通、连通图、连通分量 无向图 强连通图、强连通分量 有向图 生成树、生成森林 (二) 图的存储结构 (1) 数组表示法 邻接矩阵表示

36、。 结构定义 顶点的度和邻接矩阵中元素的关系 图的邻接矩阵的存储算法。 (a) 实现框架 (b) 构造无向网算法及时间复杂度 (2) 邻接表 表示方法 邻接表结构定义 图示 特点 (3) 十字链表和邻接多重表 (了解 ) (三) 图的遍历 (1) 图的遍历的概念 概念 图的遍历的复杂性 遍历的方法：深度优先搜索和广度优先搜索 (2) 深度优先搜索 (Depth first search) 深度优先搜索方法 ( 类似于树的先序遍历 ) 图示遍历过程 非递归深度优先遍历图的算法步骤 ( 三个步骤 ) 非递归深度优先遍历图的算法描述 ( 邻接表存储图 ) 整个图的遍历算法 时间复杂度 (3) 宽度优

37、先搜索 (Boreadth_first_search) 宽度优先搜索方法 ( 类似于树的按层次遍历 ) 图示遍历过程 广度优先遍历图的算法步骤 ( 三个步骤 ) 广度优先遍历图的算法描述 ( 邻接表存储图 ) 时间复杂度 (四) 图的连通性问题 (1) 无向图的连通分量及生成树 求连通分量的方法 连通性及最小生成树，生成过程 生成森林、生成过程 了解生成树和建立生成森林的算法 (2) 有向图的强连通分量， 求强连通分量方法 求强连通分量 (五) 最小生成树 (无向图 ) (1) 最小生成树所代表的问题 (2) 最小生成树算法基础 (MST 性质 ) (3) 普里姆算法 (prim) 算法思想

38、算法步骤 ( 五个步骤 ) 生成过程 算法实现中的方法 算法描述 生成过程有关量的变化表 算法的时间复杂度 (4) 克鲁斯卡尔算法 算法思想 算法步骤 生成过程 算法实现中的方法 算法的时间复杂度 (六) 有向无环图 (directed acycline graph)DAG 图 (1) 概念 (2) 用途 (七) 拓扑排序 (Topologeical sort) (1) 有关概念 拓扑排序。 偏序与全序 AOV网、求拓扑有序序列 (2) 拓扑排序算法 算法步骤 存储结构及辅助空间 算法描述 算法时间复杂度 可用 DFS 算法进行拓扑排序 (八) 关键路径 (1) AOE 网 AOE 网的特点和

39、作用 AOE 网有待研究的问题 (a) 完成整项工程至少需要多少时间 (b) 哪些活动是影响工程进度的关键 (2) 关键路径 (Critical path) 概念 关系分析：活动的最早开始时间e(i) 、最迟开始时间 l(i) 、事件的最早发生 时间ve(j)和最迟发生时间vl(j)之间的关系濫驂膽閉驟羥闈詔寢賻減栖綜。 求e(i)、l(i)、ve(j)、vl(j)和关键活动 算法步骤 (四个步骤 ) (a) 求各顶点事件的最早发生时间 ve (b) 求各顶点的最迟发生时间 vl 及输出各关键活动 算法时间复杂度 提高关键活动的速度对提早完成整个工程的制约因素 (九) 最短路径问题 (1) 最

40、短路径的概念 (2) 从某个源点到其余各顶点的最短路径问题描述 (3) Dijkstra 算法 算法思想 算法设计分析 (三个要点 ) 算法步骤 (三个步骤 ) 算法描述 void shortestpath.dij(mgraph g,i nt vo,pathmatrix *p,shortpathtable *D)銚銻縵哜鳗鸿锓謎 諏涼鏗穎報。 最短路径生成的过程 算法时间复杂度 (4) 每一对顶点之间的最短路径 (常用两种办法 ) (5) floyd 算法 算法思想 方法 算法描述 算法分析1、最短路径生成的过程 5、作业 P47 7.1，7.5，7.7，P48 7.9，7.10，7.11，7

41、.13, P49 7.22，7.27挤貼綬电麥 结鈺贖哓类芈罷鸨。 七 查找 1、学习目的：明确查找的有关概念，掌握顺序查找、二分查找、线性插值和分 区查找以及二叉排序树查找的方法及算法；明确哈希查找的概念，掌握造哈希 表、哈希函数的构造及冲突处理方法及算法；初步掌握查找长度的计算；掌握 平衡二叉树的构造方法；了解 B-树和B+树的概念。赔荊紳谘侖驟辽輩袜錈極嚕辫。 2、学习重点： 查找表的基本概念及查找原理； 查找表的顺序存储结构；查找运 算在查找表和有序表上的实现；二叉排序树的定义、性质及各结点间的键值关 系；二叉排序树的查找算法和基本思想；平衡二叉排序树的概念；散列表及散 列存储和散列查

42、找的基本思想；各种散列表的组织、解决冲突的方法；在散列 表上实现查找、插入和删除运算的算法。查找方法的时间复杂度计算。 塤礙籟馐决 穩賽釙冊庫麩适绲。 3、 学习难点：二叉排序树上的插入算法；平衡二叉树的旋转平衡方法；散列表 上的有关算法；查找方法的时间复杂度计算。 裊樣祕廬廂颤谚鍘羋蔺递灿扰。 4、课程内容与基本要求 (一) 查找的有关概念 (1) 查找表 (2) 查找经常的操作 (四种 ) (3) 静态和动态查找表 (4) 关键字、主关键字、次关键字 (5) 查找的概念 (6) 根据不同的情况有多种查找的方法。 数据元素类型定义及有关函数 (二) 静态查找表的抽象数据类型 (三) 顺序表的

43、查找 (1) 查找表的存储及顺序存储结构 (2) 顺序查找的过程 (3) 查找算法描述 (4) 性能分析 分析对象 分析方法 平均查找长度的计算 关于不等概率的查找情况。 查找不成功情况时 (四) 有序表的查找。 (1) 折半查找 折半查找过程 算法描述 查找长度 (2) 了解其它有序表查找。 斐波那契查找： 插值查找。 (3) 索引顺序表的查找(分块查找) 查找方法。 通常的分块方法 算法分析及重要的结论 (五) 动态查找表 (1) 概念 (2) 抽象数据类型 (六) 二叉排序树 (1) 概念 (2) 二叉排序树的查找 查找方法 查找算法描述。 (3) 二叉排序树的插入 方法。 插入算法。

44、操作过程 (4) 二叉排序树的删除 方法(四种情况) 删除算法。 (5) 查找平均长度 (七) 平衡二叉树 (1) 有关概念 定义平衡因子 (2) 二叉排序树的平衡化 平衡化思想(AVL树) 平衡化方法(四种情况) (四个步骤) 平衡二叉排序树上插入一个新的数据元素的步骤 二叉树排序树结点类型 了解有关算法 (a) 右旋转处理(LL) (b) 左旋转处理(RR) (c) 以指针t所指结点为根的二叉树作左平衡旋转处理 (d) 插入算法 平衡树查找长度 (八) B-树和B+树 (1) B-树的概念 (2) B-树查找过程 B+树的概念 (九) 哈希表 (1) 哈希查找和哈希表 概念(基本思想 )

45、哈希表 (2) 关于冲突 冲突的概念 避免冲突的辨证性 (3) 哈希函数的构造方法 “好”的哈希函数 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 选择哈希函数应考虑的因素 (4) 理冲突的方法 处理冲突的目标 开方定址法 再哈希法 链地址法 建立一个公共溢出区 (5) 哈希表的查找 开放定址哈希表的存储结构 查找算法 插入算法 (6) 查找分析 查找长度的计算 查找过程分析 哈希表的装填因子 5、作业 P54: 9.1，9.2，9.3，P56 9.9，9.10，9.19， 9.20，9.21 八排序 1、学习目的： 明确排序的有关概念， 掌握基本的内排序： 插入排序，冒泡

46、排序， 希尔排序，快速排序，选择排序，堆排序，归并排序，基数排序等排序方法及 相应的算法；了解外排序的基本概念及方法。初步掌握时间复杂度、空间复杂 度的计算及评价。 仓嫗盤紲嘱珑詁鍬齊驁絛鯛鱧。 2、学习重点： 排序基本概念及内排序、 稳定排序和非稳定排序及其区别；插入 排序的基本思想、和算法；冒泡排序的基本思想和算法；希尔排序的基本思想 和算法；快速排序的基本思想和算法；直接选择排序的基本思想和算法；堆排 序的基本思想和算法；归并排序的基本思想和算法；两个有序文件合并的方法 和算法；二路归并排序的基本思想和算法；基数排序的基本思想和算法；各排 序算法的时空性能。 绽萬璉轆娛閬蛏鬮绾瀧恒蟬轅。

47、 3、学习难点：快速排序、堆排序、基数排序的方法和算法及其算法的时间复杂 度分析。 4、课程内容与基本要求 (一) 排序的有关概念 (1) 排序的功能 (2) 定义 -是一种操作 (3) 关键字及排序的唯一性 (4) 排序方法的稳定性 (5) 排序方法的分类 : (6) 排序过程依据不同原则分类 (7) 按所需工作量分 (8) 两种基本操作 (9) 三种存储方式 (10) 待排记录的数据类型 (二) 直接插入排序 (1)算法思想 (2) 实现中的技术：设置监视哨 (3) 算法描述： void insertsort(sqlist l) (4) 排序过程 (5) 算法分析 时间复杂度 空间复杂度 算法的稳定性 (三) 折半插入排序 (