数据结构
复 习 要 点
第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。
第3章：1 概念: 栈、队列和循环队列; 2 栈和队列的初始化、插入和删除算法；3 栈、队列和循环队列的空、满条件。
第5章：数组、三元组和十字链表的定义
第6章：1 各种定义；2二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3 树和森林的存储、遍历以及与二叉树的相互转换；4 Han树的构造。
第7章：1 图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2最小生成树、关键路径和最短路的算法实现。
第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。
第10章：1基本排序算法(冒泡、简单选择、直接插入)的编程；2其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3 各种排序的稳定性。
第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。
作业：22, 23, 26, 27, 28, 215, 219, 220
第3章：1 概念: 栈、队列和循环队列; 2 栈和队列的初始化、插入和删除算法；3 栈、队列和循环队列的空、满条件。
作业：31, 36, 311,
第5章：数组、三元组和十字链表的定义
第6章：1 各种定义；2二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3 树和森林的存储、遍历以及与二叉树的相互转换；4 Han树的构造。
作业：65, 66, 614, 619, 6,23, 626, 627, 628, 637, 638, 6,47
第7章：1 图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2最小生成树、关键路径和最短路的算法实现。
作业：71, 77, 711, 713
第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。
作业：99, 911, 914,
第10章：1基本排序算法(冒泡、简单选择、直接插入)的编程；2其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3 各种排序的稳定性。
作业：101, 103
第一章 绪论
第二节 基本概念和术语
13 抽象数据类型的表示与实现
类C语言的简要说明
例1-7 抽象数据类型Trplt的表示与实现
14 算法和算法分析
算法 算法(Algrth)就是对特定问题求解步骤的一种合理的描述。它有如下特征：有穷性；确定性；可行性。当然需要输入初始条件-输入，和操作结果-输出。
算法设计的要求 1 正确性；2 可读性；3健壮性； 4 高效率性和低存储性
14 算法和算法分析
算法效率的度量—时间和空间的度量 衡量一个算法的效果（好坏），最广泛采用的标准主要是看这个算法解决问题所花费的时间长短，当然一般还要看所需要的存储空间。但是一个算法执行所花费的时间既与计算机的速度有关，也与要求解的实例有关。为了客观公正，必需要一个通用的标准。
这个标准就是找一个参变量--问题的规模(Sz), 即一个实例按二进制编码输入到计算机的编码长度，也就是所占存储的大小。问题的规模通常用整数量n表示。一般情况是数据元素的大小假定为1个单位，这样问题的规模n就是数据元素的个数(大部分情况都是这样)。
为了便于比较同一问题的不同算法或者分析一个问题的算法复杂性，通常的做法是，从算法中选取几种对于所研究的问题来说是基本操作的原操作，以该基本算法重复执行的次数作为算法的时间度量。这个度量一般是n的某个函数(n)，算法的时间复杂度记作T(n)=O((n)) 如：
时间复杂度分为最坏情况、最好情况和平均情况下的时间复杂度。
空间复杂度是衡量一个算法所需存储空间尺度，记作
S(n)=O((n))
23 线性表的链式表示和实现
线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单、直观的公式来表示。然而, 这种存储结构的弱点是: 在作插入或删除操作时,需移动大量数据元素，特别是当数据元素本身的大小比较大时尤为如此。
线性表的链式存储结构--它不再要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表可随机存取的优点（即查找不是很方便）。
231 线性链表
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,对每个数据元素 来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素的存储映像,称为结点(nd)。它包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。
>>>带头结点的单链表：即在单链表的第一的结点之前附设一个不存储任何信息的结点，这个结点称为头结点。<<<
3 单链表的删除操作
4 查找、插入和删除算法的时间复杂度
算法28, 29和210的复杂度均为O(n)
因为要操作第个结点，必须首先要找到第-1个结点。
232 循环链表 31 栈（后进先出表、LIFO表）
311 抽象的数据类型的定义
312 栈的表示和实现
循环链表(rlar lnd lst)是另一种形式的链式存储结构它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
233 双向链表
第一章的作业 22, 24, 26, 27, 28 215, 221
24 一元多项式的表示和实现
两个多项式相加的算法
34 队 列
队列(q)是一种先进先出(rst n rst t,缩写为FIFO)的线性表。它只允许在表的一端进行插入, 而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫队尾(Rar), 删除的一端叫队头(Frnt)
队列的链式表示和实现---链队列
本章的作业
第33 34 313 328题
第4章 串(strng，或字符串)
串也就是字符串。计算机上的非数值处理的对象基本上是字符串数据。在事务处理程序中,顾客的姓名和地址以及货物的名称、产地和规格等一般是作为字符串处理的。又如信息检索系统、文字编辑程序、问答系统、自然语言翻译系统以及音乐分析程序等,都是以字符串数据作为处理对象的。对字符串数据的处理比处理整数和浮点数要复杂得多。
41 串类型的定义
串(strng，字符串)是由零个或多个字符组成的有限序列,一般记为S =‘abd’ 其中,S是串的名,用单引号括起来的字符序列是串的值, 字符可以是字母、数字、汉字或其他字符; 串中字符的数目称为串的长度。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称作主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。称两个串是相等的当且仅当这两个串的值相等。也就是说,只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。零个字符的串称为空串(nll strng),它的长度为零。
42 串的表示和实现
421定长顺序存储表示
422 堆分配存储表示
423 串的块链存储表示
43 串的模式匹配算法
串(strng，字符串)是由零个或多个字符组成的有限序列 串中任意个连续的字符组成的子序列称为该串的子串(模式串),包含子串的串相应地称作主串。子串的定位操作通常称做串的模式匹配。如果主串中有子串，则称匹配成功；否则匹配失败或叫匹配不成功。
431 求子串位置的定位函数Indx(S,T,ps)
nt Indx(SStrng S, SStrng T; nt ps){
s=0;
r(=ps;(<=S[0]-T[0]+1 && s=0);++){
j=1;
whl(j>0 && j<=T[0]) j=(S[+j-1]==T[j])j+1:0;
(j>T[0]) s=;
}
rtrn s;
}
以上算法的时间复杂性
最好情况：O(n+)
最坏情况：O(n)
432模式匹配的一种改进算法 ---- KMP算法
这种改进算法是D E Knth与V R Pratt和J H Mrrs同时发现的,因此人们称它为克努特一莫里斯一普拉特操作(简称为KMP算法)。此算法可以在O(n+)的时间数量级上完成串的模式匹配操作。
44 串的操作应用举例
441 文本编辑
442 建立词索引表
443 程序和文章的编译
444 文本文件的压缩
445 ……
复 习
基本内容包括：数据类型的定义，三种存储表示（定长顺序存储结构、块链存储结构、堆分配存储结构）和各种基本操作的实现；串的模式匹配算法。
学习要点：主要围绕基本内容展开。
第3和4章的作业题
第33 34 313 328题
第44 47 417 425题
第5章 数组和广义表
数组是同学们已经很熟悉的一种数据类型,几乎所有的程序设计语言都把数组类型设定为固有类型。
广义表也是线性表的一种推广，它的每一项不光是单个的元素，也可以是一个子广义表。如
D=(( ),(a),(b,),(a,b,),(a,(b,)))
数组和广义表可以看成是线性表在下述含义上的扩展: 表中的数据元素本身也是一个数据结构。本章讨论它们的定义和实现。
51 数组的定义
二维数组
52 数组的顺序表示和实现
由于数组一般不作插入或删除操作,也就是说,一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不再发生变动。因此,采用顺序存储结构表示数组是自然的事了。
由于存储单元是一维的结构,而数组是个多维的结构,则用一组连续存储单元存放数组的数据元素就有个次序约定问题，即按照什么样的次序来存储数组元素。对二维数组，一般有行优先和列优先两种方式。
53 矩阵的压缩存储
矩阵是很多科学与工程计算问题中研究的数学对象。在数值分析中经常出现一些阶数很高的矩阵,同时在矩阵中有许多值相同的元素或者是零元素。有时为了节省存储空间,可以对这类矩阵进行压缩存储。所谓压缩存储是指: 为多个值相同的元只分配一个存储空间；对零元不分配空间。
假若值相同的元素或者零元素在矩阵中的分布有一定规律,则我们称此类矩阵为特殊矩阵;反之,称为稀疏矩阵。
531 特殊矩阵
初等矩阵
对称矩阵
上三角矩阵
三对角矩阵
532 稀疏矩阵
三元组顺序表
行逻辑链接的顺序表
十字链表
1 三元组顺序表
矩阵转置的两个算法
算法二（快速转置算法）：
本算法需要附设n和pt两个向量。n[l]表示矩阵M中第l列中非零元的个数, pt[l]指示M中第l列的第一个非零元在转置后的三元组中的恰当位置。
附：两个矩阵相加的算法
Stats AddSMatrx(TSMatrx A,TSMatrx B, TSMatrx &C〉{
//采用三元组顺序表存储A,B和C,求C=A+B。
p=1; q=1; r=1;
whl(p<=At && q<=Bt){
(Adata[p]=Bdata[q] && Adata[p]j=Bdata[q]j)
{ Cdata[r]=Adata[p]+Bdata[q]; ++p;++q;
(Cdata[r]!=0){Cdata[r]=Adata[p];Cdata[r]j=Adata[p]j; ++r; } }
ls
(Adata[p]
{ Cdata[r]=Adata[p]; Cdata[r]=Adata[p];Cdata[r]j=Adata[p]j;
++r; ++p;}
ls
{ Cdata[r]=Bdata[q]; Cdata[r]=Bdata[q];Cdata[r]j=Bdata[q]j;
++r; ++q;}
}
whl(p<=At){
Cdata[r]=Adata[p]; Cdata[r]=Adata[p];Cdata[r]j=Adata[p]j; ++r; ++p;}
whl(q<=Bt){
Cdata[r]=Bdata[q]; Cdata[r]=Bdata[q];Cdata[r]j=Bdata[q]j; ++r; ++q;}
}
Ct=r-1; C=A;Cn=An;
}
2 行逻辑链接的顺序表
为了便于随机存取任意一行的非零元,则需知道每一行的第二个非零元在三元组表中的位置。为此,可将上节快速转置矩阵的算法中创建的,指示"行"信息的辅助数组pt固定在稀疏矩阵的存储结构中。称这种"带行链接信息"的三元组表为行逻辑链接的顺序表。
3 十字链表
这里，每个非零元可用一个含5个域的结点表示,其中, j和这3个域分别表示该非零元所在的行、列和非零元的值, 向右域rght用以链接同一行中下一个非零元,向下域dwn用以链接同一列中下一个非零元。同一行的非零元通过rght域链接成一个线性链表,同一列的非零元通过dwn域链接成另一个线性链表, 每个非零元既是某个行链表中的一个结点,又是某个列链表中的一个结点,整个矩阵构成了一个十字交叉的链表,故称这样的存储结构为十字链表。每个行链表和列链表都设一个头指针，头指针构成两个一维数组。
4 稀疏矩阵的其它存储方法
“行”信息的辅助数组pt+（列下标域和非零元素域）的二元组顺序表。
（非零元素以行为主序时排列的顺序号+非零元素域）的二元顺序表
第二部分： 广义表
广义表是线性表的一种推广，它的每一项不光是单个的元素(原子)，也可以是一个子广义表(子表)。如D=(a,b,(a,b,),(a,(b,)))
三、广义表的一个实例：n元多项式的表示
四、广义表的递归算法
求广义表的深度
复制广义表
建立广义表
第6章 树和二叉树
树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可用树来形象表示。树在计算机领域中也得到广泛应用,如在编译程序中,可用树来表示源程序的语法结构。又如在数据库系统中,树形结构也是信息的重要组织形式之一。
61 树的定义和基本术语
树(Tr)是n(n>=0)个结点的有限集。在任意一棵非空树中: (1)有且仅有一个特定的称为根(Rt)的结点; (2) 当n>1时, 其余结点可分为(>0)个互不相交的有限集Tl ,T2,…,Tn, 其中每一个集合T本身是一棵树, 并且称为根的子树(Sbtr)
62 二叉树
一、定义： 二叉树(Bnary Tr)是另一种树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
二、抽象数据类型的定义：(见书本121-123页)
三、性质：
性质1 在二叉树的第层上至多有 个结点。
性质2
性质3
四、二叉树的存储结构：
1、顺序存储结构：
用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素, 即将完全二叉树上编号为的结点元素存储在如上定义的一维数组中下标为-1的分量中。
五(631)、遍历二叉树:
在树中查找具有某种特征的结点, 或者对树中全部结点逐一进行某种处理(访问)。这样的过程称为遍历二叉树(travrsng bnary tr)。
先序遍历(PrOrdrTravrs)：若二叉树为空, 则空操作;否则
(1) 访问根结点; (2) 先序遍历左子树; (3) 先序遍历右子树。
中序遍历(InOrdrTravrs): 若二叉树为空,则空操作;否则
(1) 中序遍历左子树; (2) 访问根结点; (3) 中序遍历右子树。
后序遍历(PstOrdrTravrs): 若二叉树为空,则空操作;否则
(1) 后序遍历左子树; (2) 后序遍历右子树; (3) 访问根结点。
层次遍历(LvlOrdrTravrs): 若二叉树为空,则空操作;否则
从上到下、从左到右按层次遍历二叉树。
先(前)序遍历二叉树的非递归算法
Stats PrOrdrTravrs(BTr T, Stats( Vst)(TElTyp ))){
//先序遍历二叉树的非递归算法。
I(T){ IntSta(S); Psh(S,T);
whl(!StaEpty(S)){
Pp(S, p);
(!Vst(p->data)) rtrn ERROR; // prnt(T->data)
(p->rhld) Psh(S, p->rhld); //p的右儿子先进栈；
(p->lhld) Psh(S, p->lhld); // p的左儿子进栈；
} // whl
rtrn OK;
}//
}// PrOrdrTravrs
Stats PrOrdrTravrs_1(BTr T, Stats( Vst)(TElTyp ))){ //先序遍历二叉树的非递归算法。S为栈，tp为栈顶指针。 p=T; Stp=Sbas; 由小说迷 www.xiaoshuom.com 收集整理，看更快的更新请到小説迷p--}; }// whl }// PrOrdrTravrs
后序遍历二叉树的非递归算法
Stats PstOrdrTravrs(BTr T, Stats( Vst)(TElTyp ))){ //后序遍历二叉树的非递归算法1。S为栈，tp为栈顶指针。 p=T; IntSta(S); whl(!StaEpty(S)|| p!=NULL){ whl(!p){
psh(S,p); (p->lhld) {p=p->lhld;}
ls{p=p->rhld;}
} Pp(S, p);
(!Vst(p->data)) rtrn ERROR; // prnt(p->data) 访问p whl(!StaEpty(S) && Stp->rhld= =p){
Pp(S,p);
(!Vst(p->data)) rtrn ERROR; // prnt(p->data) 访问p }
(!StaEpty(S)) {p=stp->rhld;} ls {p=NULL;}
}// whl }// PstOrdrTravrs
二叉树的其他基本操作
求二叉树的深度，或求以结点x为根的子树的算法；
查找值为x的结点；
求树中叶子结点的个数；
判断一棵二叉树是否为完全二叉树；
求二叉树中结点x的所有祖先，或子孙；
二叉树的拷贝。
632 线索二叉树
在一棵二叉树的存储结构中加入按某种遍历次序的链所得到的树为线索二叉树。从而有先(中、后)线索二叉树。
64 树和森林
641 树的存储结构
二、孩子表示法
四、孩子兄弟（二叉树或二叉链表）表示法
643 树和森林的遍历
先根（次序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；
后根（次序）遍历：先依次后根遍历根的每棵子树，然后访问树的根结点；
66 赫夫曼(Han)树及其应用
661 最优二叉树（赫夫曼树）
662 Han编码
第7章 图
图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系, 每个数据元素只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。
71 图的定义及相关的术语
在图中的数据元素通常称做顶点(Vrtx), V是顶点的有穷非空集合; VR是两点之间的关系集合。若〈v,由小说迷 www.xiaoshuom.com 收集整理，看更快的更新请到小説迷d graph)。
72 图的存储结构
721 数组表示法
1、邻接矩阵
2 关联矩阵
722 邻接表
邻接表(Adjany Lst)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,用以连接与此顶点相邻的所有顶点；也就是说，第个单链表中的结点表示依附于顶点V的边(对有向图是以顶点V为尾的弧)。
逆邻接表：对有向图的每个顶点建立一个以它 为头的邻接表，也就是说，把有向 图的每条弧反向后得到的新的有向 图的邻接表。
723 十字链表
十字链表(Orthgnal Lst〉是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表 与数组的十字链表存储类似 有时也适合于无向图
724 邻接多重表(Adjany Mltlst)
其中,ar为标志域,可用以标记该条边是否被搜索过;vx和jvx为该边依附的两个顶点在图中的位置;ln指向下一条依附于顶点vx的边;jln指向下一条依附于顶点jvx的边,n为指向和边相关的各种信息的指针域。
其他存储结构
如：三元组存储结构或广义表
73 图的遍历
从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(Travrsng Graph)。通常有两条遍历图的路径:深度优先搜索(Dpth Frst Sarh)和广度优先搜索(Bradth Frst Sarh)。
74 图的连通性问题
741 无向图的连通分量和生成树
在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。
742 有向图的强连通分量
1 算法步骤：
743 最小生成树
假设要在n个城市之间建立一个通信联络网, 则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路, 相应地都要付出一定的经济代价。n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条, 以使总的耗费最少呢
可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树(Mn Cst Spannng Tr)(简称为最小生成树, 最小支撑树，MST)的问题。一棵生成树的代价就是树上各边的代价之和。
2 克鲁斯卡尔(rsal)算法
实例：见书本P176
算法的正确性证明
算法的实现
算法的时间复杂性：O(lg )
3 破回路法
基本思想：在网络中找一个回路，然后在此回路中删除权值最大的边，直到网络中无回路为止。
744 关节点和重连通分量
定义： 假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点(artlatn pnt, t vrtx)。一个没有关节点的连通图称为是重连通图(2-连通图，bnntd graph)。在2-连通图上,任意一对顶点之间至少存在两条内部不交的路径。 若在连通图上至少删去个顶点才能破坏图的连通性,则称此图的连通度为
75 有向无环图(DAG)及其应用
751 拓扑排序
2 拓扑排序的算法：
重复下述两步，直到全部顶点被输出，或者当前图中不存在入度为0的顶点为止（存在回路）：
(1) 在有向图中选一个没有入弧的顶点且输出之；
(2) 从图中删除该顶点以及与它相关联的弧。
782 关键路径
AOE-网络(Atvty n Edg): 顶点表示事件，弧表示活动 ，权表示活动持续的时间。
关键路径：网络中路径长度最长的路径。
关键活动：最早开始时间与最迟开始时间相等的活动。
求关键活动的算法思想
附：其它的图和网络问题
网络中所有点对之间的最短路问题(762)
旅行售货员问题；
中国邮递员问题；
最大流问题和最小费用流问题；
最大对集问题；
运输问题和指派问题；
求图的连通度、边连通度和染色问题。
作业
71 77 710
711 713
第7章 图
图(Graph)是一种较线性表和树更为复杂的数据结构。在线性表中,数据元素之间仅有线性关系, 每个数据元素只有一个直接前驱和一个直接后继; 在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即其孩子结点)相关,但只能和上一层中一个元素(即其双亲结点)相关 而在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。由此,图的应用极为广泛,特别是近年来的迅速发展,已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。
71 图的定义及相关的术语
在图中的数据元素通常称做顶点(Vrtx), V是顶点的有穷非空集合; VR是两点之间的关系集合。若〈v,由小说迷 www.xiaoshuom.com 收集整理，看更快的更新请到小説迷d graph)。
72 图的存储结构
721 数组表示法
1、邻接矩阵
2 关联矩阵
722 邻接表
邻接表(Adjany Lst)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,用以连接与此顶点相邻的所有顶点；也就是说，第个单链表中的结点表示依附于顶点V的边(对有向图是以顶点V为尾的弧)。
逆邻接表：对有向图的每个顶点建立一个以它 为头的邻接表，也就是说，把有向 图的每条弧反向后得到的新的有向 图的邻接表。
723 十字链表
十字链表(Orthgnal Lst〉是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表 与数组的十字链表存储类似 有时也适合于无向图
724 邻接多重表(Adjany Mltlst)
其中,ar为标志域,可用以标记该条边是否被搜索过;vx和jvx为该边依附的两个顶点在图中的位置;ln指向下一条依附于顶点vx的边;jln指向下一条依附于顶点jvx的边,n为指向和边相关的各种信息的指针域。
其他存储结构
如：三元组存储结构或广义表
73 图的遍历
从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次。这一过程就叫做图的遍历(Travrsng Graph)。通常有两条遍历图的路径:深度优先搜索(Dpth Frst Sarh)和广度优先搜索(Bradth Frst Sarh)。
74 图的连通性问题
741 无向图的连通分量和生成树
在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。
742 有向图的强连通分量
1 算法步骤：
743 最小生成树
假设要在n个城市之间建立一个通信联络网, 则连通n个城市只需要n-1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。
在每两个城市之间都可以设置一条线路, 相应地都要付出一定的经济代价。n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条, 以使总的耗费最少呢
可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,也就是使总的耗费最少。这个问题就是构造连通网的最小代价生成树(Mn Cst Spannng Tr)(简称为最小生成树, 最小支撑树，MST)的问题。一棵生成树的代价就是树上各边的代价之和。
2 克鲁斯卡尔(rsal)算法
实例：见书本P176
算法的正确性证明
算法的实现
算法的时间复杂性：O(lg )
3 破回路法
基本思想：在网络中找一个回路，然后在此回路中删除权值最大的边，直到网络中无回路为止。
744 关节点和重连通分量
定义： 假若在删去顶点v以及和v相关联的各边之后,将图的一个连通分量分割成两个或两个以上的连通分量,则称顶点v为该图的一个关节点(artlatn pnt, t vrtx)。一个没有关节点的连通图称为是重连通图(2-连通图，bnntd graph)。在2-连通图上,任意一对顶点之间至少存在两条内部不交的路径。 若在连通图上至少删去个顶点才能破坏图的连通性,则称此图的连通度为
75 有向无环图(DAG)及其应用
751 拓扑排序
第9章 查找
查找表(Sarh Tabl)是由同一类型的数据元素(或记录)构成的集合。由于"集合"中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。
对查找表经常进行的操作有:(1)查询某个"特定的"数据元素是否在查找表中; (2)检索某个"特定的"数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删去某个数据元素。若对查找表只作前两种统称为"查找"的操作,则称此类查找表为静态查找表(Stat Sarh Tabl); 若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类表为动态查找表(Dyna Sarh Tabl)
几个相关的概念：关键字(主关键字,次关键字), 查找成功
91 静态查找表
911 顺序表的查找
3 算法分析：包括时间复杂性、空间复杂性以及其它性能。
定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为算法在查找成功时的平均查找长度(Avrag Sarh Lngth, ASL)
4 线性链表的查找
见书本29页的算法28
912 有序表的查找
折半查找 d=[(lw+hgh)/2]
斐波那契查找
913 静态树表的查找 914 索引顺序表的查找
以上两小节只作简单介绍
92 动态查找表
921 二叉排序树和平衡二叉树
二、平衡二叉树(AVL树)
平衡二叉树(Baland Bnary Tr): 对二叉排序树的每棵子树，其左右子树的深度之差的绝对值不超过1。某结点的平衡因子=左子树的深度-右子树的深度对平衡二叉树的查找算法与二叉排序树的查找相同，其算法难度主要是插入和删除的实现，而且插入和删除算法所花的时间要大于二叉排序树的插入和删除算法所花的时间。
插入：插入->求平衡因子->旋转操作（P234-235）。
删除：
第9章 查找
查找表(Sarh Tabl)是由同一类型的数据元素(或记录)构成的集合。由于"集合"中的数据元素之间存在着完全松散的关系,因此查找表是一种非常灵便的数据结构。
对查找表经常进行的操作有:(1)查询某个"特定的"数据元素是否在查找表中; (2)检索某个"特定的"数据元素的各种属性; (3)在查找表中插入一个数据元素; (4)从查找表中删去某个数据元素。若对查找表只作前两种统称为"查找"的操作,则称此类查找表为静态查找表(Stat Sarh Tabl); 若在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,则称此类表为动态查找表(Dyna Sarh Tabl)
几个相关的概念：关键字(主关键字,次关键字), 查找成功
91 静态查找表
911 顺序表的查找
3 算法分析：包括时间复杂性、空间复杂性以及其它性能。
定义：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为算法在查找成功时的平均查找长度(Avrag Sarh Lngth, ASL)
4 线性链表的查找
见书本29页的算法28
912 有序表的查找
折半查找 d=[(lw+hgh)/2]
斐波那契查找
913 静态树表的查找 914 索引顺序表的查找
以上两小节只作简单介绍
92 动态查找表
921 二叉排序树和平衡二叉树
二、平衡二叉树(AVL树)
平衡二叉树(Baland Bnary Tr): 对二叉排序树的每棵子树，其左右子树的深度之差的绝对值不超过1。某结点的平衡因子=左子树的深度-右子树的深度对平衡二叉树的查找算法与二叉排序树的查找相同，其算法难度主要是插入和删除的实现，而且插入和删除算法所花的时间要大于二叉排序树的插入和删除算法所花的时间。
插入：插入->求平衡因子->旋转操作（P234-235）。
删除：
922 B-树和 B+树 一、B-树
定义：B-树
查找：结点内部二分查找，结点间树查找
插入：分裂
删除：合并
93 哈希(Hash)表
931 什么是哈希表
哈希函数：记录的关键字到它的存储地址的一个映射
冲突：两个不同的关键字得到相等的哈希函数值，这种现象称为冲突。
同义词：具有相同哈希函数值的两个关键字称为同义词。
哈希表：根据设定的Hash函数和处理冲突的方法将一组关键字映射到一个有限的地址集（区间）上，并以关键字在地址集的“像”作为记录在表中的存储位置，这种表称为Hash表。
932 哈希函数的构造方法
直接定址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法
933 处理冲突的方法
开放地址法
再哈希法
链地址法
建立一个公共溢出区
第10章 内部排序
排序(Srtng)是将一个数据元素(或记录)的任意序列, 重新排列成一个按关键字有序的序列。确切定义：(见书P263)
排序的稳定性：两个关键字相等的记录在排序完成后位次的大小没有发生改变，则称这个排序方法是稳定的；否则就是不稳定的。
排序方法的分类：内部排序和外部排序
内部排序算法的分类：
102 插入排序
1021 直接插入排序
算法思想：将一个记录插入到一个已经排好序的有序表中，得到一个新的、长度增加1的有序表。
1022 其他插入排序
折半插入排序
2-路插入排序
表插入排序：关键字的排序+记录的重排
1023 希尔排序(Shll's Srt )
希尔排序(Shll's Srt )又称“缩小增量排序”。首先给出一组数列(d1,d2,…,dn),满足d1>d2>…>dn=1它的基本思想是：在第步时，先按照下标差距为d将整个记录序列分割成若干子序列，然后分别对子序列进行直接插入排序。最后对全体记录进行一次直接插入排序。
103 快速排序
1、冒泡排序( Bbbl Srt )
Vd Bbbl_Srt(Sqlst &L);
{ h=Llngth; //h标记每趟结束后做最后一次交换的记录下标
whl(h>0){
=h-1; h=0;
r( =1;;++)
(Lr[]y >Lr[+1]y) {Lr[]Lr[+1]; h=;}
}
}
2、快速排序
104 选择排序
1041 简单选择排序
Vd SltSrt(Sqlst &L){
//对顺序表L作简单选择排序
r(=1;
n=Lr[]y; I=; // 4-6行是从到Llngth找关键 // 字最小的记录
r(j=+1; j<=Llngth; ++j)
(n>Lr[j]y){n=Lr[j]y; I=j;}
(I!=) Lr[]Lr[I];
} //r
}//SltSrt
1042 树形选择排序
堆的定义
如何从无序表来构造一个堆
如何调整堆
复 习 要 点
第2章：线性表的概念以及顺序和链式存储下查找、插入和删除算法和算法的时间复杂性。
第3章：1 概念: 栈、队列和循环队列; 2 栈和队列的初始化、插入和删除算法；3 栈、队列和循环队列的空、满条件。
第5章：数组、三元组和十字链表的定义
第6章：1 各种定义；2二叉树的链式存储结构和遍历(先序、中序、后序和层次)；3 树和森林的存储、遍历以及与二叉树的相互转换；4 Han树的构造。
第7章：1 图的存储(邻接矩阵、邻接表、邻接多重表)和遍历；2最小生成树、关键路径和最短路的算法实现。
第9章：折半查找、二叉排序树、平衡二叉树和B-树的算法实现。
第10章：1基本排序算法(冒泡、简单选择、直接插入)的编程；2其它排序(希尔、快速、2-路归并、堆、表插入)的算法实现；3 各种排序的稳定性。
如果你在阅读得很入味的时候,又正好有事离开,那请进行以下操作.