第一章
数据结构
复 习 要 点
第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。
第3章：1. 概念: 栈、队列和循环队列; 2. 栈和队列的初始化、插入和删除算法；3. 栈、队列和循环队列的空、满条件。
第5章：数组、三元组和十字链表的定义
第6章：1. 各种定义；2.二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3. 树和森林的存储、遍历以及与二叉树的相互转换；4. Huffman树的构造。
第7章：1. 图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2.最小生成树、关键路径和最短路的算法实现。
第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。
第10章：1.基本排序算法(冒泡、简单选择、直接插入)的编程；2.其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3. 各种排序的稳定性。
第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。
作业：2.2, 2.3, 2.6, 2.7, 2.8, 2.15, 2.19, 2.20
第3章：1. 概念: 栈、队列和循环队列; 2. 栈和队列的初始化、插入和删除算法；3. 栈、队列和循环队列的空、满条件。
作业：3.1, 3.6, 3.11,
第5章：数组、三元组和十字链表的定义
第6章：1. 各种定义；2.二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3. 树和森林的存储、遍历以及与二叉树的相互转换；4. Huffman树的构造。
作业：6.5, 6.6, 6.14, 6.19, 6,23, 6.26, 6.27, 6.28, 6.37, 6.38, 6,47
第7章：1. 图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2.最小生成树、关键路径和最短路的算法实现。
作业：7.1, 7.7, 7.11, 7.13
第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。
作业：9.9, 9.11, 9.14,
第10章：1.基本排序算法(冒泡、简单选择、直接插入)的编程；2.其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3. 各种排序的稳定性。
作业：10.1, 10.3
第一章 绪论
第二节 基本概念和术语
1.3 抽象数据类型的表示与实现
类C语言的简要说明
例1-7 抽象数据类型Triplet的表示与实现
1.4 算法和算法分析
算法 算法(Algorithm)就是对特定问题求解步骤的一种合理的描述。它有如下特征：有穷性；确定性；可行性。当然需要输入初始条件-输入，和操作结果-输出。
算法设计的要求 1. 正确性；2. 可读性；3.健壮性； 4. 高效率性和低存储性
1.4 算法和算法分析
算法效率的度量—时间和空间的度量 衡量一个算法的效果（好坏），最广泛采用的标准主要是看这个算法解决问题所花费的时间长短，当然一般还要看所需要的存储空间。但是一个算法执行所花费的时间既与计算机的速度有关，也与要求解的实例有关。为了客观公正，必需要一个通用的标准。
这个标准就是找一个参变量--问题的规模(Size), 即一个实例按二进制编码输入到计算机的编码长度，也就是所占存储的大小。问题的规模通常用整数量n表示。一般情况是数据元素的大小假定为1个单位，这样问题的规模n就是数据元素的个数(大部分情况都是这样)。
为了便于比较同一问题的不同算法或者分析一个问题的算法复杂性，通常的做法是，从算法中选取几种对于所研究的问题来说是基本操作的原操作，以该基本算法重复执行的次数作为算法的时间度量。这个度量一般是n的某个函数f(n)，算法的时间复杂度记作T(n)=O(f(n)). 如：
时间复杂度分为最坏情况、最好情况和平均情况下的时间复杂度。
空间复杂度是衡量一个算法所需存储空间尺度，记作
S(n)=O(f(n)).
2.3 线性表的链式表示和实现
线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单、直观的公式来表示。然而, 这种存储结构的弱点是: 在作插入或删除操作时,需移动大量数据元素，特别是当数据元素本身的大小比较大时尤为如此。
线性表的链式存储结构--它不再要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表可随机存取的优点（即查找不是很方便）。
2.3.1 线性链表
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,对每个数据元素 来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素的存储映像,称为结点(node)。它包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。
>>>带头结点的单链表：即在单链表的第一的结点之前附设一个不存储任何信息的结点，这个结点称为头结点。<<<
3. 单链表的删除操作
4. 查找、插入和删除算法的时间复杂度
算法2.8, 2.9和2.10的复杂度均为O(n)
因为要操作第i个结点，必须首先要找到第i-1个结点。
2.3.2 循环链表 3.1 栈（后进先出表、LIFO表）
3.1.1 抽象的数据类型的定义
3.1.2 栈的表示和实现
循环链表(circular linked list)是另一种形式的链式存储结构.它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
2.3.3 双向链表
第一章的作业 2.2, 2.4, 2.6, 2.7, 2.8 2.15, 2.21
2.4 一元多项式的表示和实现
两个多项式相加的算法
3.4 队 列
队列(queue)是一种先进先出(first in first out,缩写为FIFO)的线性表。它只允许在表的一端进行插入, 而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫队尾(Rear), 删除的一端叫队头(Front).
队列的链式表示和实现---链队列
本章的作业
第3.3 3.4 3.13 3.28题
第4章 串(string，或字符串)
串也就是字符串。计算机上的非数值处理的对象基本上是字符串数据。在事务处理程序中,顾客的姓名和地址以及货物的名称、产地和规格等一般是作为字符串处理的。又如信息检索系统、文字编辑程序、问答系统、自然语言翻译系统以及音乐分析程序等,都是以字符串数据作为处理对象的。对字符串数据的处理比处理整数和浮点数要复杂得多。
4.1 串类型的定义
串(string，字符串)是由零个或多个字符组成的有限序列,一般记为S =‘abcdef’ . 其中,S是串的名,用单引号括起来的字符序列是串的值, 字符可以是字母、数字、汉字或其他字符; 串中字符的数目称为串的长度。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称作主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。称两个串是相等的当且仅当这两个串的值相等。也就是说,只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。零个字符的串称为空串(null string),它的长度为零。
4.2 串的表示和实现
4.2.1定长顺序存储表示
4.2.2 堆分配存储表示
4.2.3 串的块链存储表示
4.3 串的模式匹配算法
串(string，字符串)是由零个或多个字符组成的有限序列. 串中任意个连续的字符组成的子序列称为该串的子串(模式串),包含子串的串相应地称作主串。子串的定位操作通常称做串的模式匹配。如果主串中有子串，则称匹配成功；否则匹配失败或叫匹配不成功。
4.3.1 求子串位置的定位函数Index(S,T,pos)
int Index(SString S, SString T; int pos){
succ=0;
for(i=pos;(i<=S[0]-T[0]+1 && succ=0);++i){
j=1;
while(j>0 && j<=T[0]) j=(S[i+j-1]==T[j])?j+1:0;
if(j>T[0]) succ=i;
}
return succ;
}
以上算法的时间复杂性
最好情况：O(n+m)
最坏情况：O(n*m)
4.3.2模式匹配的一种改进算法 ---- KMP算法
这种改进算法是D. E. Knuth与V. R. Pratt和J. H. Morris同时发现的,因此人们称它为克努特一莫里斯一普拉特操作(简称为KMP算法)。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作。
4.4 串的操作应用举例
4.4.1 文本编辑
4.4.2 建立词索引表
4.4.3 程序和文章的编译
4.4.4 文本文件的压缩
4.4.5 ……
复 习
基本内容包括：数据类型的定义，三种存储表示（定长顺序存储结构、块链存储结构、堆分配存储结构）和各种基本操作的实现；串的模式匹配算法。
学习要点：主要围绕基本内容展开。
第3和4章的作业题
第3.3 3.4 3.13 3.28题
第4.4 4.7 4.17 4.25题
第5章 数组和广义表
数组是同学们已经很熟悉的一种数据类型,几乎所有的程序设计语言都把数组类型设定为固有类型。
广义表也是线性表的一种推广，它的每一项不光是单个的元素，也可以是一个子广义表。如
D=(( ),(a),(b,c),(a,b,c),(a,(b,c)))
数组和广义表可以看成是线性表在下述含义上的扩展: 表中的数据元素本身也是一个数据结构。本章讨论它们的定义和实现。
5.1 数组的定义
二维数组
5.2 数组的顺序表示和实现
由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动。因此,采用顺序存储结构表示数组是自然的事了。
由于存储单元是一维的结构,而数组是个多维的结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题，即按照什么样的次序来存储数组元素。对二维数组，一般有行优先和列优先两种方式。
5.3 矩阵的压缩存储
矩阵是很多科学与工程计算问题中研究的数学对象。在数值分析中经常出现一些阶数很高的矩阵,同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间,可以对这类矩阵进行压缩存储。所谓压缩存储是指: 为多个值相同的元只分配一个存储空间；对零元不分配空间。
假若值相同的元素或者零元素在矩阵中的分布有一定规律,则我们称此类矩阵为特殊矩阵;反之,称为稀疏矩阵。
5.3.1 特殊矩阵
初等矩阵
对称矩阵
上三角矩阵
三对角矩阵
5.3.2 稀疏矩阵
三元组顺序表
行逻辑链接的顺序表
十字链表
1. 三元组顺序表
矩阵转置的两个算法
算法二（快速转置算法）：
本算法需要附设num和cpot两个向量。num[col]表示矩阵M中第col列中非零元的个数, cpot[col]指示M中第col列的第一个非零元在转置后的三元组中的恰当位置。
附：两个矩阵相加的算法
Status AddSMatrix(TSMatrix A,TSMatrix B, TSMatrix &C〉{
//采用三元组顺序表存储A,B和C,求C=A+B。
p=1; q=1; r=1;
while(p<=A.tu && q<=B.tu){
if(A.data[p].i=B.data[q].i && A.data[p].j=B.data[q].j)
{ C.data[r].e=A.data[p].e+B.data[q].e; ++p;++q;
if(C.data[r].e!=0){C.data[r].i=A.data[p].i;C.data[r].j=A.data[p].j; ++r; } }
else
if(A.data[p].i ++r; ++p;} else { C.data[r].e=B.data[q].e; C.data[r].i=B.data[q].i;C.data[r].j=B.data[q].j; ++r; ++q;} } while(p<=A.tu){ C.data[r].e=A.data[p].e; C.data[r].i=A.data[p].i;C.data[r].j=A.data[p].j; ++r; ++p;} while(q<=B.tu){ C.data[r].e=B.data[q].e; C.data[r].i=B.data[q].i;C.data[r].j=B.data[q].j; ++r; ++q;} } C.tu=r-1; C.mu=A.mu;C.nu=A.nu; } 2. 行逻辑链接的顺序表 为了便于随机存取任意一行的非零元,则需知道每一行的第二个非零元在三元组表中的位置。为此,可将上节快速转置矩阵的算法中创建的,指示"行"信息的辅助数组cpot固定在稀疏矩阵的存储结构中。称这种"带行链接信息"的三元组表为行逻辑链接的顺序表。 3. 十字链表 这里，每个非零元可用一个含5个域的结点表示,其中i, j和e这3个域分别表示该非零元所在的行、列和非零元的值, 向右域right用以链接同一行中下一个非零元,向下域down用以链接同一列中下一个非零元。同一行的非零元通过right域链接成一个线性链表,同一列的非零元通过down域链接成另一个线性链表, 每个非零元既是某个行链表中的一个结点,又是某个列链表中的一个结点,整个矩阵构成了一个十字交叉的链表,故称这样的存储结构为十字链表。每个行链表和列链表都设一个头指针，头指针构成两个一维数组。 4. 稀疏矩阵的其它存储方法 “行”信息的辅助数组cpot+（列下标域和非零元素域）的二元组顺序表。 （非零元素以行为主序时排列的顺序号+非零元素域）的二元顺序表 第二部分： 广义表 广义表是线性表的一种推广，它的每一项不光是单个的元素(原子)，也可以是一个子广义表(子表)。如D=(a,b,(a,b,c),(a,(b,c))) 三、广义表的一个实例：n元多项式的表示 四、广义表的递归算法 求广义表的深度 复制广义表 建立广义表 第6章 树和二叉树 树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用,如在编译程序中,可用树来表示源程序的语法结构。又如在数据库系统中,树形结构也是信息的重要组织形式之一。 6.1 树的定义和基本术语 树(Tree)是n(n>=0)个结点的有限集。在任意一棵非空树中: (1)有且仅有一个特定的称为根(Root)的结点; (2) 当n>1时, 其余结点可分为m(m>0)个互不相交的有限集Tl ,T2,…,Tn, 其中每一个集合Ti本身是一棵树, 并且称为根的子树(Subtree). 6.2 二叉树 一、定义： 二叉树(Binary Tree)是另一种树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 二、抽象数据类型的定义：(见书本121-123页) 三、性质： 性质1 在二叉树的第i层上至多有 个结点。 性质2 性质3 四、二叉树的存储结构： 1、顺序存储结构： 用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素, 即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。 五(6.3.1)、遍历二叉树: 在树中查找具有某种特征的结点, 或者对树中全部结点逐一进行某种处理(访问)。这样的过程称为遍历二叉树(traversing binary tree)。 先序遍历(PreOrderTraverse)：若二叉树为空, 则空操作;否则 (1) 访问根结点; (2) 先序遍历左子树; (3) 先序遍历右子树。 中序遍历(InOrderTraverse): 若二叉树为空,则空操作;否则 (1) 中序遍历左子树; (2) 访问根结点; (3) 中序遍历右子树。 后序遍历(PostOrderTraverse): 若二叉树为空,则空操作;否则 (1) 后序遍历左子树; (2) 后序遍历右子树; (3) 访问根结点。 层次遍历(LevelOrderTraverse): 若二叉树为空,则空操作;否则 从上到下、从左到右按层次遍历二叉树。 先(前)序遍历二叉树的非递归算法 Status PreOrderTraverse(BiTree T, Status( * Visit)(TElemType e))){ //先序遍历二叉树的非递归算法。 If(T){ InitStack(S); Push(S,T); while(!StackEmpty(S)){ Pop(S, p); if(!Visit(p->data)) return ERROR; // printf(T->data) if (p->rchild) Push(S, p->rchild); //p的右儿子先进栈； if (p->lchild) Push(S, p->lchild); // p的左儿子进栈； } // while return OK; }// if }// PreOrderTraverse. Status PreOrderTraverse_1(BiTree T, Status( * Visit)(TElemType e))){ //先序遍历二叉树的非递归算法。S为栈，top为栈顶指针。 p=T; S.top=S.base; while(S.top!=S.base || p!=NULL){ while(!p){ if(!Visit(p->data)) return ERROR; // printf(p->data) if (p->rchild) { if(S.top-S.base>=S.stacksize){ //栈满，输出错误 return OVERFLOW} else {++S.top =p->rchild}; //p的右儿子进栈； } p= p->lchild; // p的左儿子进栈； } // while if(S.top!=S.base){p=S.top; S.top--}; }// while }// PreOrderTraverse. 后序遍历二叉树的非递归算法 Status PostOrderTraverse(BiTree T, Status( * Visit)(TElemType e))){ //后序遍历二叉树的非递归算法1。S为栈，top为栈顶指针。 p=T; InitStack(S); while(!StackEmpty(S)|| p!=NULL){ while(!p){ push(S,p); if (p->lchild) {p=p->lchild;} else{p=p->rchild;} } Pop(S, p); if(!Visit(p->data)) return ERROR; // printf(p->data) 访问p. while(!StackEmpty(S) && S.top->rchild= =p){ Pop(S,p); if(!Visit(p->data)) return ERROR; // printf(p->data) 访问p. } if(!StackEmpty(S)) {p=s.top->rchild;} else {p=NULL;} }// while }// PostOrderTraverse. 二叉树的其他基本操作 求二叉树的深度，或求以结点x为根的子树的算法； 查找值为x的结点； 求树中叶子结点的个数； 判断一棵二叉树是否为完全二叉树； 求二叉树中结点x的所有祖先，或子孙； 二叉树的拷贝。 6.3.2 线索二叉树 在一棵二叉树的存储结构中加入按某种遍历次序的链所得到的树为线索二叉树。从而有先(中、后)线索二叉树。 6.4 树和森林 6.4.1 树的存储结构 二、孩子表示法 四、孩子兄弟（二叉树或二叉链表）表示法 6.4.3 树和森林的遍历 先根（次序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树； 后根（次序）遍历：先依次后根遍历根的每棵子树，然后访问树的根结点； 6.6 赫夫曼(Huffman)树及其应用 6.6.1 最优二叉树（赫夫曼树） 6.6.2 Huffman编码 第7章 图 图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系, 每个数据元素只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关. 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。 7.1 图的定义及相关的术语 在图中的数据元素通常称做顶点(Vertex), V是顶点的有穷非空集合; VR是两点之间的关系集合。若〈v,w〉VR, 则表示从v到w的一条弧(Arc),且称v为弧尾(Tail)或初始点(Initial node),称w为弧头(Head)或终端点(Terminal node ), 此时的图称为有向图(Digraph)。若以无序对(v,w)代替两个有序对,表示v和w之间的一条边(Edge), 此时的图称为无向图(Undirected graph)。 7.2 图的存储结构 7.2.1 数组表示法 1、邻接矩阵 2. 关联矩阵 7.2.2 邻接表 邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,用以连接与此顶点相邻的所有顶点；也就是说，第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。 逆邻接表：对有向图的每个顶点建立一个以它 为头的邻接表，也就是说，把有向 图的每条弧反向后得到的新的有向 图的邻接表。 7.2.3 十字链表 十字链表(Orthogonal List〉是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表. 与数组的十字链表存储类似. 有时也适合于无向图. 7.2.4 邻接多重表(Adjacency Multilist) 其中,mark为标志域,可用以标记该条边是否被搜索过;ivex和jvex为该边依附的两个顶点在图中的位置;ilink指向下一条依附于顶点ivex的边;jlink指向下一条依附于顶点jvex的边,info为指向和边相关的各种信息的指针域。 其他存储结构 如：三元组存储结构或广义表 7.3 图的遍历 从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(Traversing Graph)。通常有两条遍历图的路径:深度优先搜索(Depth First Search)和广度优先搜索(Breadth First Search)。 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。 7.4.2 有向图的强连通分量 1. 算法步骤： 7.4.3 最小生成树 假设要在n个城市之间建立一个通信联络网, 则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。 在每两个城市之间都可以设置一条线路, 相应地都要付出一定的经济代价。n个城.市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条, 以使总的耗费最少呢? 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree)(简称为最小生成树, 最小支撑树，MST)的问题。一棵生成树的代价就是树上各边的代价之和。 2. 克鲁斯卡尔(kruskal)算法 实例：见书本P176. 算法的正确性证明 算法的实现 算法的时间复杂性：O(elog e) 3. 破回路法 基本思想：在网络中找一个回路，然后在此回路中删除权值最大的边，直到网络中无回路为止。 7.4.4 关节点和重连通分量 定义： 假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点(articulation point, cut vertex)。一个没有关节点的连通图称为是重连通图(2-连通图，biconnected graph)。在2-连通图上,任意一对顶点之间至少存在两条内部不交的路径。 若在连通图上至少删去k个顶点才能破坏图的连通性,则称此图的连通度为k. 7.5 有向无环图(DAG)及其应用 7.5.1 拓扑排序 2. 拓扑排序的算法： 重复下述两步，直到全部顶点被输出，或者当前图中不存在入度为0的顶点为止（存在回路）： (1) 在有向图中选一个没有入弧的顶点且输出之； (2) 从图中删除该顶点以及与它相关联的弧。 7.8.2 关键路径 AOE-网络(Activity on Edge): 顶点表示事件，弧表示活动 ，权表示活动持续的时间。 关键路径：网络中路径长度最长的路径。 关键活动：最早开始时间与最迟开始时间相等的活动。 求关键活动的算法思想 附：其它的图和网络问题 网络中所有点对之间的最短路问题(7.6.2) 旅行售货员问题； 中国邮递员问题； 最大流问题和最小费用流问题； 最大对集问题； 运输问题和指派问题； 求图的连通度、边连通度和染色问题。 作业 7.1 7.7 7.10 7.11 7.13 第7章 图 图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系, 每个数据元素只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关. 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。 7.1 图的定义及相关的术语 在图中的数据元素通常称做顶点(Vertex), V是顶点的有穷非空集合; VR是两点之间的关系集合。若〈v,w〉VR, 则表示从v到w的一条弧(Arc),且称v为弧尾(Tail)或初始点(Initial node),称w为弧头(Head)或终端点(Terminal node ), 此时的图称为有向图(Digraph)。若以无序对(v,w)代替两个有序对,表示v和w之间的一条边(Edge), 此时的图称为无向图(Undirected graph)。 7.2 图的存储结构 7.2.1 数组表示法 1、邻接矩阵 2. 关联矩阵 7.2.2 邻接表 邻接表(Adjacency List)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,用以连接与此顶点相邻的所有顶点；也就是说，第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。 逆邻接表：对有向图的每个顶点建立一个以它 为头的邻接表，也就是说，把有向 图的每条弧反向后得到的新的有向 图的邻接表。 7.2.3 十字链表 十字链表(Orthogonal List〉是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表. 与数组的十字链表存储类似. 有时也适合于无向图. 7.2.4 邻接多重表(Adjacency Multilist) 其中,mark为标志域,可用以标记该条边是否被搜索过;ivex和jvex为该边依附的两个顶点在图中的位置;ilink指向下一条依附于顶点ivex的边;jlink指向下一条依附于顶点jvex的边,info为指向和边相关的各种信息的指针域。 其他存储结构 如：三元组存储结构或广义表 7.3 图的遍历 从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(Traversing Graph)。通常有两条遍历图的路径:深度优先搜索(Depth First Search)和广度优先搜索(Breadth First Search)。 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。 7.4.2 有向图的强连通分量 1. 算法步骤： 7.4.3 最小生成树 假设要在n个城市之间建立一个通信联络网, 则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。 在每两个城市之间都可以设置一条线路, 相应地都要付出一定的经济代价。n个城.市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条, 以使总的耗费最少呢? 可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树(Minimum Cost Spanning Tree)(简称为最小生成树, 最小支撑树，MST)的问题。一棵生成树的代价就是树上各边的代价之和。 2. 克鲁斯卡尔(kruskal)算法 实例：见书本P176. 算法的正确性证明 算法的实现 算法的时间复杂性：O(elog e) 3. 破回路法 基本思想：在网络中找一个回路，然后在此回路中删除权值最大的边，直到网络中无回路为止。 7.4.4 关节点和重连通分量 定义： 假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点(articulation point, cut vertex)。一个没有关节点的连通图称为是重连通图(2-连通图，biconnected graph)。在2-连通图上,任意一对顶点之间至少存在两条内部不交的路径。 若在连通图上至少删去k个顶点才能破坏图的连通性,则称此图的连通度为k. 7.5 有向无环图(DAG)及其应用 7.5.1 拓扑排序 第9章 查找 查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。由于"集合"中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。 对查找表经常进行的操作有:(1)查询某个"特定的"数据元素是否在查找表中; (2)检索某个"特定的"数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删去某个数据元素。若对查找表只作前两种统称为"查找"的操作,则称此类查找表为静态查找表(Static Search Table); 若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类表为动态查找表(Dynamic Search Table). 几个相关的概念：关键字(主关键字,次关键字), 查找成功. 9.1 静态查找表 9.1.1 顺序表的查找 3. 算法分析：包括时间复杂性、空间复杂性以及其它性能。 定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为算法在查找成功时的平均查找长度(Average Search Length, ASL). 4. 线性链表的查找 见书本29页的算法2.8 9.1.2 有序表的查找 折半查找 mid=[(low+high)/2] 斐波那契查找 9.1.3 静态树表的查找 9.1.4 索引顺序表的查找 以上两小节只作简单介绍 9.2 动态查找表 9.2.1 二叉排序树和平衡二叉树 二、平衡二叉树(AVL树) 平衡二叉树(Balanced Binary Tree): 对二叉排序树的每棵子树，其左右子树的深度之差的绝对值不超过1。某结点的平衡因子=左子树的深度-右子树的深度对平衡二叉树的查找算法与二叉排序树的查找相同，其算法难度主要是插入和删除的实现，而且插入和删除算法所花的时间要大于二叉排序树的插入和删除算法所花的时间。 插入：插入->求平衡因子->旋转操作（P234-235）。 删除：?????? 第9章 查找 查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。由于"集合"中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。 对查找表经常进行的操作有:(1)查询某个"特定的"数据元素是否在查找表中; (2)检索某个"特定的"数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删去某个数据元素。若对查找表只作前两种统称为"查找"的操作,则称此类查找表为静态查找表(Static Search Table); 若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类表为动态查找表(Dynamic Search Table). 几个相关的概念：关键字(主关键字,次关键字), 查找成功. 9.1 静态查找表 9.1.1 顺序表的查找 3. 算法分析：包括时间复杂性、空间复杂性以及其它性能。 定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为算法在查找成功时的平均查找长度(Average Search Length, ASL). 4. 线性链表的查找 见书本29页的算法2.8 9.1.2 有序表的查找 折半查找 mid=[(low+high)/2] 斐波那契查找 9.1.3 静态树表的查找 9.1.4 索引顺序表的查找 以上两小节只作简单介绍 9.2 动态查找表 9.2.1 二叉排序树和平衡二叉树 二、平衡二叉树(AVL树) 平衡二叉树(Balanced Binary Tree): 对二叉排序树的每棵子树，其左右子树的深度之差的绝对值不超过1。某结点的平衡因子=左子树的深度-右子树的深度对平衡二叉树的查找算法与二叉排序树的查找相同，其算法难度主要是插入和删除的实现，而且插入和删除算法所花的时间要大于二叉排序树的插入和删除算法所花的时间。 插入：插入->求平衡因子->旋转操作（P234-235）。 删除：?????? 9.2.2 B-树和 B+树 一、B-树 定义：B-树 查找：结点内部二分查找，结点间树查找 插入：分裂 删除：合并 9.3 哈希(Hash)表 9.3.1 什么是哈希表 哈希函数：记录的关键字到它的存储地址的一个映射 冲突：两个不同的关键字得到相等的哈希函数值，这种现象称为冲突。 同义词：具有相同哈希函数值的两个关键字称为同义词。 哈希表：根据设定的Hash函数和处理冲突的方法将一组关键字映射到一个有限的地址集（区间）上，并以关键字在地址集的“像”作为记录在表中的存储位置，这种表称为Hash表。 9.3.2 哈希函数的构造方法 直接定址法 数字分析法 平方取中法 折叠法 除留余数法 随机数法 9.3.3 处理冲突的方法 开放地址法 再哈希法 链地址法 建立一个公共溢出区 第10章 内部排序 排序(Sorting)是将一个数据元素(或记录)的任意序列, 重新排列成一个按关键字有序的序列。确切定义：(见书P263). 排序的稳定性：两个关键字相等的记录在排序完成后位次的大小没有发生改变，则称这个排序方法是稳定的；否则就是不稳定的。 排序方法的分类：内部排序和外部排序 内部排序算法的分类： 10.2 插入排序 10.2.1 直接插入排序 算法思想：将一个记录插入到一个已经排好序的有序表中，得到一个新的、长度增加1的有序表。 10.2.2 其他插入排序 折半插入排序 2-路插入排序 表插入排序：关键字的排序+记录的重排 10.2.3 希尔排序(Shell's Sort ) 希尔排序(Shell's Sort )又称“缩小增量排序”。首先给出一组数列(d1,d2,…,dn),满足d1>d2>…>dn=1.它的基本思想是：在第i步时，先按照下标差距为di将整个记录序列分割成若干子序列，然后分别对子序列进行直接插入排序。最后对全体记录进行一次直接插入排序。 10.3 快速排序 1、冒泡排序( Bubble Sort ) Void Bubble_Sort(Sqlist &L); { ch=L.length; //ch标记每趟结束后做最后一次交换的记录下标 while(ch>0){ m=ch-1; ch=0; for( k=1;m;++k) if(L.r[k].key >L.r[k+1].key) {L.r[k]L.r[k+1]; ch=k;} } } 2、快速排序 10.4 选择排序 10.4.1 简单选择排序 Void SelectSort(Sqlist &L){ //对顺序表L作简单选择排序 for(k=1; k for(j=k+1; j<=L.length; ++j) if(min>L.r[j].key){min=L.r[j].key; I=j;} if(I!=k) L.r[k]L.r[I]; } //for k }//SelectSort 10.4.2 树形选择排序 堆的定义 如何从无序表来构造一个堆 如何调整堆 复 习 要 点 第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。 第3章：1. 概念: 栈、队列和循环队列; 2. 栈和队列的初始化、插入和删除算法；3. 栈、队列和循环队列的空、满条件。 第5章：数组、三元组和十字链表的定义 第6章：1. 各种定义；2.二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3. 树和森林的存储、遍历以及与二叉树的相互转换；4. Huffman树的构造。 第7章：1. 图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2.最小生成树、关键路径和最短路的算法实现。 第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。 第10章：1.基本排序算法(冒泡、简单选择、直接插入)的编程；2.其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3. 各种排序的稳定性。
新书推荐
近期最受关注书籍
|
|
