存储结构:

◆顺序存储:用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素物理上也相邻。

线性结构

◆线性结构:每个元素最多只有一个出度和一个入度,表现为一条线状。

线性表按存储方式分为顺序表和链表。

存储结构:

◆顺序存储:用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素物理上也相邻。

◆链式存储:存储各数据元素的结点的地址并不要求是连续的,数据元素逻辑上相邻,物理上分开。

性能类别具体项目顺序存储链式存储空间性能存储密度1更优1容量分配事先确定动态改变更优时间性能查找运算O(n/2)O(n/2)读运算O(1)更优O([n1]/2),最好情况为1最坏情况为n插入运算O(n/2)最好情况为0最坏情况为nO(1)更优删除运算O([n-1]/2)O(1)更优

◆在时间方面,当需要对元素进行破坏性操作(插入、删除)时,链表效率更高,因为其只需要修改指针指向即可,而顺序表因为地址是连续的,当删除或插入一个元素后,后面的其他节点位置都需要变动。

◆而当需要对元素进行不改变结构操作时(读取、查找),顺序表效率更高,因为其物理地址是连续的,如同数组一般,只需按索引号就可快速定位,而链表需要从头节点开始,一个个的查找下去。

◆栈和队列

队列、栈结构如下图,队列是先进先出,分队头和队尾;栈是先进后出,只有栈顶能进出。

◆循环队列

设循环队列Q的容量为MAXSIZE,初始时队列为空,且Q.rear和Q.front都等于0.

元素入队时修改队尾指针,即令Q.rear(Q.rear1)%MAXSIZE。

元素出队时修改队头指针,即令Q.front(Q.front1)%MAXSIZE。

根据队列操作的定义,当出队操作导致队列变为空时,有Q.rear

Q.front;

◆在队列空和队列满的情况下,循环队列的队头、队尾指针指向的位置是相同的,此时仅仅根据Q.rear和Q.front之间的关系无法断定队列的状态。

为了区别队空和队满的情况,可采用以下两种处理方式:其一是设置一个标志,以区别头、尾指针的值相同时队列是空还是满;其二是牺牲一个存储单元,约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满,而头、尾指针的值相同时表示队列为空。

◆空格串:由一个或多个空格组成的串,空格是空白字符,占一个字符长度。

◆子串:串中任意长度的连续字符构成的序列称为子串。

含有子串的串称为主串,空串是任意串的子串。

◆串的模式匹配:子串的定位操作,用于查找子串在主串中第一次出现的位置的算法。

模式匹配算法

◆朴素的模式匹配算法:也称为布鲁特一福斯算法,其基本思想是从主串的第1个字符起与模式串的第1个字符比较,若相等,则继续逐个字符进行后续的比较;否则从主串中的第2个字符起与模式串的第1个字符重新比较,直至模式串中每个字符依次和主串中的一个连续的字符序列相等时为止,此时称为匹配成功,否则称为匹配失败。

◆KMP算法:对基本模式匹配算法的改进,其改进之处在于:每当匹配过程中出现相比较的字符不相等时,不需要回溯主串的字符位置指针,而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离,再继续进行比较。

◆当模式串中的字符pj与主串中相应的字符Si不相等时,因其前j个字符(“p0

...

◆在KMP算法中,依据模式串的next函数值实现子串的滑动。

若令next[j]k,则next[j]表示当模式串中的pj与主串中相应字符不相等时,令模式串的next[j]与主串的相应字符进行比较。

◆数组是定长线性表在维度上的扩展,即线性表中的元素又是一个线性表。

N维数组是一种“同构”的数据结构,其每个数据元素类型相同、结构一致。

◆其可以表示为行向量形式或者列向量形式线性表,单个关系最多只有一个前驱和一个后继,本质还是线性的。

◆数组结构的特点:数据元素数目固定;数据元素类型相同;数据元素的下标关系具有上下界的约束且下标有序。

◆数组数据元素固定,一般不做插入和删除运算,适合于采用顺序结构,

◆数组存储地址的计算,特别是二维数组,要注意理解,假设每个数组元素占用存储长度为len,起始地址为a,存储地址计算如下(默认从0开始编号):

数组类型存储地址计算一维数组a[n]a[i]的存储地址为:ai*len二维数组a[m][n]a[i][j]的存储地址(按行存储)为:a(i\*nj)\*len

a[i][j]的存储地址(按列存储)为:a(j\*mi)\*len

◆特殊矩阵:矩阵中的元素(或非0元素)的分布有一定的规律。

常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。

◆稀疏矩阵:在一个矩阵中,若非零元素的个数远远少于零元素个数,且非零元素的分布没有规律。

广义表

◆广义表是线性表的推广,是由0个或多个单元素或子表组成的有限序列。

◆广义表与线性表的区别:线性表的元素都是结构上不可分的单元素,而广义表的元素既可以单元素,也可以是有结构的表。

◆广义表一般记为:LS(α1,α2,…,

其中LS是表名,ai是表元素,它可以是表(称为子表),也可以是数据元素(称为原子)。

其中n是广义表的长度(也就是最外层包含的元素个数),n0的广义表为空表;而递归定义的重数就是广义表的深度,即定义中所含括号的重数(单边括号的个数,原子的深度为0,空表的深度为1)。

◆head()和tail():取表头(广义表第一个表元素,可以是子表也可以是单元素)和取表尾(广义表中,除了第一个表元素之外的其他所有表元素构成的表,非空广义表的表尾必定是一个表,即使表尾是单元素)操作。

树与二叉树

◆树是n个节点的有限集合(n0),当n0时称为空树,在任一颗非空树中,有且仅有一个根节点。

其余结点可分为m(m20)个互不相交的有限子集T1,T2,.,Tm,其中,每个Ti又都是一棵树,并且称为根结点的子树。

(1)双亲、孩子和兄弟。

结点的子树的根称为该结点的孩子;相应地,该结点称为其子结点的双亲。

具有相同双亲的结点互为兄弟。

(2)结点的度。

一个结点的子树的个数记为该结点的度。

例如A的度为3,B的度为2,C的度为0,D的度为1。

(3)叶子结点。

叶子结点也称为终端结点,指度为0的结点。

例如,E、F、C、G都是叶子结点。

(4)内部结点。

度不为0的结点,也称为分支结点或非终端结点。

除根结点以外,分支结点也称为内部结点。

例如,B、D都是内部结点。

(5)结点的层次。

根为第一层,根的孩子为第二层,依此类推,若某结点在第i层,则其孩子结点在第i1层。

例如,A在第1层,B、C、D在第2层,E、F和G在第3层。

(6)树的高度。

一棵树的最大层数记为树的高度(或深度)。

例如,图中所示树的高度为3。

(7)有序(无序)树。

若将树中结点的各子树看成是从左到右具有次序的,即不能交换则称该树为有序树,否则称为无序树。

◆二叉树是n个节点的有限集合,它或者是空树,或者是由一个根节点及两颗互不相交的且分别称为左、右子树的二叉树所组成。

◆二叉树有一些性质如下,要求拿握,在买际考试中可以用特殊值法验证。

(3)对任何一棵二叉树,若其终端节点数为n0,度为2的节点数为n2,则

◆此公式可以画一个简单的二叉树使用特殊值法快速验证,也可以证明如下:

设一棵二叉树上叶结点数为n0,单分支结点数为n1,双分支结点数为n2,则总结点数n0n1n2。

在一棵二叉树中,所有结点的分支数(即度数)应等于单分支结点数加上双分支结点数的2倍,即总的分支数n12n2。

由于二叉树中除根结点以外,每个结点都有唯一的一个分支指向它,因此二叉树中:总的分支数总结点数-1。

◆顺序存储,就是用一组连续的存储单元存储二叉树中的节点,按照从上到下,从左到右的顺序依次存储每个节点。

◆对于深度为k的完全二叉树,除第k层外,其余每层中节点数都是上一层的两倍,由此,从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。

假设有编号为i的节点,则有:

若i1,则该节点为根节点,无双亲;若i1,则该节点的双亲节点为[i/2」。

◆显然,顺序存储结构对完全二叉树而言既简单又节省空间,而对于一般二叉树则不适用。

因为在顺序存储结构中,以节点在存储单元中的位置来表示节点之间的关系,那么对于一般的二叉树来说,也必须按照完全二叉树的形式存储,也就是要添上一些实际并不存在的“虚节点”,这将造成空间的浪费。

由于二叉树中节点包含有数据元素、左子树根、右子树根及双亲等信息,因此可以用三叉链表或二叉链表(即一个节点含有三个指针或两个指针)来存储二叉树,链表的头指针指向二叉树的根节点

◆如上一颗非空的二叉树由根节点、左子树、右子树三部分组成,遍历这三部分,也就遍历了整颗二叉树。

这三部分遍历的基本顺序是先左子树后右子树,但根节点顺序可变,以根节点访问的顺序为准有下列三种遍历方式:

示例:前序:12457836

仅仅有前序和后序是无法构造二叉树的,必须要是和中序遍历的集合才能反向构造出二叉树。

构造时,前序和后序遍历可以确定根节点,中序遍历用来确定根节点的左子树节点和右子树节点,而后按此方法进行递归,直至得出结果。

◆引入线索二叉树是为了保存二叉树遍历时某节点的前驱节点和后继节点的信息,二叉树的链式存储只能获取到某节点的左孩子和右孩子结点,无法获取其遍历时的前驱和后继节点,因此可以在链式存储中再增加两个指针域,使其分别指向前驱和后继节点,但这样太浪费存储空间,考虑下述实现方法:

◆若n个节点的二叉树使用二叉链表存储,则必然有n1个空指针域,利用这些空指针域来存放节点的前驱和后继节点信息,为此,需要增加两个标志,以区分指针域存放的到底是孩子结点还是遍历节点,如下:

◆若二叉树的二叉链表采用上述结构,则称为线索链表,其中指向前驱、后继节点的指针称为线索,加上线索的二叉树称为线索二叉树。

◆最优二叉树又称为哈夫曼树,是一类带权路径长度最短的树,相关概念如下:

◆结点的带权路径长度:该结点到根结点之间的路径长度乘以该节点的权值。

◆树的带权路径长度(树的代价):树的所有叶子节点的带权路径长度之和。

◆哈夫曼树的求法:给出一组权值,将其中两个最小的权值作为叶子节点,其和作为父节点,组成二叉树,而后删除这两个叶子节点权值,并将父节点的值添加到该组权值中。

重复进行上述步骤,直至所有权值都被使用完。

◆若需要构造哈夫曼编码(要保证左节点值小于右节点的值,才是标准的哈夫曼树),将标准哈夫曼树的左分支设为0,右分支设为1,写出每个叶节点的编码,会发现,哈夫曼编码前缀不同,因此不会混淆,同时也是最优编码。

◆查找二叉树上的每个节点都存储一个值,且每个节点的所有左孩子结点值都小于父节点值,而所有右孩子结点值都大于父节点值,是一个有规律排列的二叉树,这种数据结构可以方便查找、插入等数据操作。

◆二叉排序树的查找效率取决于二叉排序树的深度,对于结点个数相同的二叉排序树,平衡二叉树的深度最小,而单枝树的深度是最大的,故效率最差。

◆平衡二叉树又称为AVL树,它或者是一棵空树,或者是具有下列性质的二叉树。

它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差的绝对值不超过1。

若将二叉树结点的平衡因子(Balance

Factor,BF)定义为该结点左子树的高度减去其右子树的高度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。

只要树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。

◆有向图:图的结点之间连接线是箭头,区分A到B,和B到A是两条线。

◆完全图:无向完全图中,节点两两之间都有连线,n个结点的连线数为(n-1)(n-2)

1n*(n-1)/2;有向完全图中,节点两两之间都有互通的两个箭头,n个节点的连线数为n*(n-1).

◆度、出度和入度:顶点的度是关联与该顶点的边的数目。

在有向图中,顶点的度为出度和入度之和。

◆子图:有两个图G(V,E)和G’(V’,E’),如果VCV且EE,则称G为G的子图。

◆连通图和连通分量:针对无向图。

若从顶点v到顶点u之间是有路径的,则说明v和u之间是连通的,若无向图中任意两个顶点之间都是连通的,则称为连通图。

无向图G的极大连通子图称为其连通分量。

◆强连通图和强连通分量:针对有向图。

若有向图任意两个顶点间都互相存在路径,即存在v到u,也存在u到v的路径,则称为强连通图。

有向图中的极大连通子图称为其强连通分量。

邻接矩阵假设一个图中有n个节点则使用n阶矩阵来存储这个图中各节点的关系规则是若节点i到节点j有连线则矩阵Ri,j1,否则为0实例如下图所示

◆邻接链表:用到了两个数据结构,先用一个一维数组将图中所有顶点存储起来,而后,对此一维数组的每个顶点元素,使用链表挂上其出度到达的结点的编号和权值,示例如下图所示:

◆存储特点:图中的顶点数决定了邻接矩阵的阶和邻接表中的单链表数目,边数的多少决定了单链表中的结点数,而不影响邻接矩阵的规模,因此采用何种存储方式与有向图、无向图没有区别,要看图的边数和顶点数,完全图适合采用邻接矩阵存储。

◆图的遍历是指从图的任意节点出发,沿着某条搜索路径对图中所有节点进行访问且只访问一次,分为以下两种方式:

◆深度优先遍历:从任一顶点出发,遍历到底,直至返回,再选取任一其他节点出发,重复这个过程直至遍历完整个图;

◆广度优先遍历:先访问完一个顶点的所有邻接顶点,而后再依次访问其邻接顶点的所有邻接顶点,类似于层次遍历。

假设有n个节点,那么这个图的最小生成树有n-1条边(不会形成环路,是树非图),这n-1条边应该会将所有顶点都连接成一个树,并且这些边的权值之和最小,因此称为最小生成树。

共有下列两种算法:

◆普里姆算法:从任意顶点出发,找出与其邻接的边权值最小的,此时此边的另外一个顶点自动加入树集合中,而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的,同样此边的另外一个顶点加入树集合中,依次递

归,直至图中所有顶点都加入树集合中,此时此树就是该图的最小生成树。

普里姆算法的时间复杂度为O(n^2),与图中的边数无关,因此该算法适合于求边稠密的网的最小生成树。

◆克鲁斯卡尔算法(推荐):这个算法是从边出发的,因为本质是选取权值最小的n-1条边,因此,就将边按权值大小排序,依次选取权值最小的边,直至囊括所有节点,要注意,每次选边后要检查不能形成环路。

克鲁斯卡尔算法的时间复杂度为O(eloge),与图中的顶点数无关,因此该算法适合于求边稀疏的网的最小生成树。

◆拓扑序列

若图中一个节点入度为0,则应该最先执行此活动,而后删除掉此节点和其关联的有向边,再去找图中其他没有入度的结点,执行活动,依次进行,示例如下(有点类似于进程的前趋图原理):

顺序查找

◆顺序查找的思想:将待查找的关键字为key的元素从头到尾与表中元素进行比较,如果中间存在关键字为key的元素,则返回成功;否则,则查找失败。

◆平均查找长度为:

n]中,在表中元素已经按照关键字递增(或递减)方式排序的情况下,进行折半查找的方法是:

1、首先将待查元素的关键字(key)值与表r中间位置上(下标为mid)记录的关键字进行比较,若相等,则查找成功;

2、若keyr[mid].key,则说明待查记录只可能在后半个子表r[mid1

n]中,下一步应在后半个子表中查找;

3、若keyr[mid].key,说明待查记录只可能在前半个子表r[1

4、重复上述步骤,逐步缩小范围,直到查找成功或子表为空失败时为止。

要注意两点:中间值位置求出若为小数,应该向下取整,即4.54,非四舍五入;中间值已经比较过不相等,在划分下一次比较区间时,无需将中间值位置再纳入下一次比较区间。

哈希表

◆哈希表通过一个以记录的关键字为自变量的函数(称为哈希函数)得到该记录的存储地址,所以在哈希表中进行查找操作时,需要用同一哈希函数计算得到待查记录的存储地址,然后到相应的存储单元去获得有关信息再判定查找是否成功。

i1,

其中,H(key)为哈希函数;m为哈希表表长;di为增量序列。

常见的增量序列有以下3种。

(2)

di12,-12,22,-22,32,…,±k2(k≤),称为二次探测再散列。

2.链地址法。

它在查找表的每一个记录中增加一个链域,链域中存放下一个具有相同哈希函数值的记录的存储地址。

利用链域,就把若干个发生冲突的记录链接在一个链表内。

当链域的值为NULL时,表示已没有后继记录了。

因此,对于发生冲突时的查找和插入操作就跟线性表一样了。

3.再哈希法:在同义词发生地址冲突时计算另一个哈希函数地址,直到冲突不再发生。

这种方法不易产生聚集现象,但增加了计算时间。

4.建立一个公共溢出区。

无论由哈希函数得到的哈希地址是什么,一旦发生冲突,都填入到公共溢出区中。

直接插入排序

◆要注意的是,前提条件是前i-1个元素是有序的,第i个元素依次从第i-1个元素往前比较,直到找到一个比第i个元素值小的元素,而后插入,插入位置及其后的元素依次向后移动。

◆当给出一队无序的元素时,首先,应该将第1个元素看做是一个有序的队列,而后从第2个元素起,按插入排序规则,依次与前面的元素进行比较,直到找到一个小于他的值,才插入。

示例如下图所示:

希尔排序

◆希尔排序的基本思想是:先将整个待排记录序列分割成若干子序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。

◆具体做法是:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组,将所有距离为d1倍数的记录放在同一个组中,在各组内进行直接插入排序;然后取第二个增量d2(d2d1),重复上述分组和排序工作,依此类推,直至所取的增量di1(didi-1

◆按上述,希尔排序实际是为了解决大数据的排序问题,当待排序的数据很多时,使用直接插入排序效率很低,因此,采取分组的方法,使问题细化,可以提高效率,适用于多数据。

简单选择排序

◆n个记录进行简单选择排序的基本方法是:通过n-i(1in)次关键字之间的比较,从n-i1个记录中选出关键字最小的记录,并和第i个记录进行交换,当i等于n时所有记录有序排列。

◆按上述,本质就是每次选择出最小的元素进行交换,主要是选择比较过程,交换过程只有一次。

堆排序

对于n个元素的关键字序列{K1,K2,…,Kn},当且仅当满足下列关系时称其为堆,其中2i和2i1需不大于n。

堆排序的基本思想是:对一组待排序记录的关键字,首先按堆的定义排成一个序列(即建立初始堆),从而可以输出堆顶的最大关键字(对于大根堆而言),然后将剩余的关键字再调整成新堆,便得到次大的关键字,如此反复,直到全部关键字排成有序序列为止。

◆为序列(55,60,40,10,80,65,15,5,75)建立初始大根堆的过程如图所示:

◆由上图可知,首先将给出的数组按完全二叉树规则建立,而后,找到此完全二叉树的最后一个非叶子节点(也即最后一颗子树),比较此非叶子节点和其两个孩子结点的大小,若小,则与其孩子结点中最大的结点进行交换;依据此规则再去找倒数第二个非叶子节点;这是只有一层的情况,当涉及到多层次时,又打破了之前的堆,因此,又要进行变换。

◆建立初始堆后,开始排序,每次取走堆顶元素(必然是最大的),而后将堆中最后一个元素移入堆顶,而后按照初始建堆中的方法与其孩子结点比较大小,依次向下判断交换成为一个新的堆,再取走堆顶元素,重复此过程。

◆堆排序适用于在多个元素中找出前几名的方案设计,因为堆排序是选择排序,而且选择出前几名的效率很高。

冒泡排序

◆n个记录进行冒泡排序的方法是:首先将第一个记录的关键字和第二个记录的关键字进行比较,若为逆序,则交换这两个记录的值,然后比较第二个记录和第三个记录的关键字依此类推,直至第n一1个记录和第n个记录的关键字比较过为止。

上述过程称为一趟冒泡排序,其结果是关键字最大的记录被交换到第n个记录的位置上。

然后进行第二趟冒泡排序,对前n-1个记录进行同样的操作,其结果是关键字次大的记录被交换到第n-1个记录的位置上。

最多进行n-1趟,所有记录有序排列。

若在某趟冒泡排序过程没有进行相邻位置的元素交换处理,则可结束排序过程。

◆示例给的是从后往前排序,也是可以的,需要从最后两个元素开始进行比较,将较小的元素交换到前面去,依次进行比较交换。

比较是为了交换,交换次数很多。

区分冒泡排序和简单选择排序。

快速排序

◆快速排序是将n个记录分成两块,再递归,实际分成两块的方法如图所示:设定一个基准为57,设定两个指针high1,lown,从low指向的第n个元素开始,与基准值进行比较,若小于基准值,则与基准进行交换low

,此时,转而从high指向的第1个元素开始和基准值进行比较,若大于基准值,则和基准值进行交换,此时,又转而从low-指向的值和基准进行比较,重复上述过程。

◆要注意的是:每次都是和基准值进行比较,因此最终是以基准值为中间,将队列分成两块。

只有当和基准值发生了交换,才变换high和low指针的计数,否则会一直low–下去。

◆上图中,最终以57为界,左边都是小于57的元素,右边都是大于57的元素,完成一次快速排序,接着对两块再分别进行递归即可。

归并排序

◆所谓“归并”,是将两个或两个以上的有序文件合并成为一个新的有序文件。

归并排序的一种实现方法是把一个有n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件,然后进行两两归并,得到[n/2]个长度为2或1的有序文件,再两两归并,如此重复,直至最后形成包含n个记录的有序文件为止。

这种反复将两个有序文件归并成一个有序文件的排序方法称为两路归并排序。

◆要仔细理解上述过程,一般归并排序都是用来合并多个线性表的,对单列数据,二路归并排序可以对元素进行两两合并。

基数排序

◆基数排序是基于多个关键字来进行多轮排序的,本质也是将问题细分,如图例子,分别按个位、十位、百位的大小作为关键字进行了三轮排序,最终得出结果。

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。

基数排序不是基于关键字比较的排序方法,它适合于元素很多而关键字较少的序列。

基数的选择和关键字的分解是根据关键字的类型来决定的,例如关键字是十进制数,则按个位、十位来分解。

内部排序算法总结

(1)若待排序的记录数目n较小,可采用直接插入排序和简单选择排序。

由于直接插入排序所需的记录移动操作较简单选择排序多,因此当记录本身信息量较大时,用简单选择排序方法较好。

(2)若待排序记录按关键字基本有序,则宜采用直接插入排序或冒泡排序。

(4)若n较大,则应采用时间复杂度为O(nlogn)的排序方法,例如快速排序、堆排序或归并排序。

排序方法时间复杂度辅助空间稳定性直接插入O(n²)O(1)稳定简单选择O(n²)O(1)不稳定冒泡排序O(n²)O(1)稳定希尔排序O(n¹.³)O(1)不稳定快速排序O(n㏒n)O(n㏒n)不稳定堆排序O(n㏒n)O(1)不稳定归并排序O(n㏒n)O(n)稳定基数排序O(d(nrd))O(rd)稳定