二叉树

Binary Tree,第i(i>=1)层上结点数最大值:2i-1。即1、2、4、8、16…。
深度为i的树的结点数最大值,或从第i(i>=1)到1层所有结点数最大值:2i-1。即1、3、7、15、31。这称为满二叉树。满二叉树的结点数为2k-1,只有度为0和2的结点,并且叶结点都处在最下层。
结点总数n=n2+n1+n0,度为0的结点数n0=n2+1,即叶结点数比双分支的结点数多1个。
二叉树中序号大于n/2的结点没有孩子结点。
完全二叉树中度为1的结点数是0或1。
完全二叉树,n个结点,深度=⌊log2n⌋+1。
完全二叉树,若深度k>1,则 2k-1>=叶子结点数>=2k-2,结点数>=2k-1
深度为k的二叉树,结点数最多为2k-1,最少为k。
深度为k的二叉树,若只有度为0、2的结点,结点数最少为2k-1。
第i个结点的父结点编号为⌊i/2⌋,左孩子编号为2*i,右孩子编号为2*i+1。
n个结点的二叉树的二叉链表中,有2n个指针域,n-1个指针域不为空,n+1个指针域为空,结果发现2n没有被平分,而是多出了一个空指针域是因为根结点没有被指向。
n个结点的二叉树的三叉链表中,除了具有二叉链表的统计结果,然后所有parent指针中只有根结点的parent指针为空。

结点的度:结点的子树的数目。
树的度:树中最大的结点度。
树的高度:也叫深度,即从1开始的最大层次数。
树的出度:树中结点度为D(D>=0)的结点的个数与D的乘积。
树的结点数=各个度(0到树的度)的结点的个数之和=各个结点的度之和再加一。

存储

完全二叉树的顺序存储结构中,编号为i的结点的层次为⌈log2(i+1)⌉ 。

二叉树的链式存储结构中,三叉链表比二叉链表的结点中多了一个parent指针域。

遍历

PreOrder、InOrder、PostOrder、LevelOrder。
先序序列的第一个结点是根结点,后序序列的最后一个结点是根结点,中序序列中由根结点将序列分为为两部分。

先序序列和中序序列相反,则二叉树每个结点只有左子树,左单极树。
先序序列和中序序列相同,则二叉树每个结点只有右子树。
先序序列和后序序列相反,则二叉树高度和结点数相同即可。
先序序列和后序序列相同,则二叉树只有一个根结点。
从一个遍历序列推导出不同形状的二叉树,首先宽二叉树,然后是多种每层单节点二叉树。

中序序列中前后结点在二叉树中的关系是,前面的结点在后面的结点的左边,左边是指左子或其所在分支的父。
交换所有分支左右子树的位置,利用前序遍历方法最合适。
一棵二叉树的前序序列和中序序列,或后序和中序序列可唯一确定这棵二叉树。在先序中第一个字符是根结点,而在后序中最后一个字符是根结点。在中序中,根结点前后分别是其左右子树。按照这个思想递归可推导出二叉树。
方法一:以中序为主线,在前序中找中序的根:
1.在中序中,由树的根分左序L,右序R。在先序中找到排在根后面的第一个L中的值,即为根的左结点。同样地,在先序中找到排在根后面的第一个R中的值,即为根的右结点。在中序中标记根值为墙表示它是已处理完毕的界线,在树中对字符画圈也表示它已处理完毕。
2.再把左右两个结点分别视为根,依次进行步骤1。
当是在后序序列中辅助查找时,方向是从后向前。

遍历实现

1.二叉链表上遍历的递归实现。还可以利用递归遍历求得二叉树的高度为较高的子树的高度加1。
2.二叉树的层次遍历可以借助队列来实现。将根结点入队列,从队列中出一个结点,将该结点的左右孩子结点入队列。如此出入直至队列为空。则入队列或出队列的顺序即为层次遍历的序列。
3.二叉树顺序存储或链式存储上的非递归实现可以借助栈来实现。

算法:输出二叉树各结点的值

//中序遍历
void printtree (BiTree BT)
{
  BiTnode* p=BT;
  InitStruct(s); //构造一个数组结构s
  s.top=0;
  
  while (p || s.top!=0)
  { 
    //把p、左子、左子的左子...,存入eles。
    while (p)
    { 
      s.eles[s.top++]=p;
      p=p->lchild ;
    }
    
    if (s.top>0)
    { 
      //输出eles中最后一个元素。
      p=s.eles[s.top--];
      cout < < p->data;//int pos=s.top,输出的元素将不在eles中继续保存。
      //遍历p的右子树
      p=p->rchild; //在下一次进入循环时,eles[pos]会被替换为p,即原p的右子结点。
    }
  }
}

树和二叉树的转换

树转二叉树:
1.将所有兄弟连接起来;
2.保留兄弟中的第一个结点与父结点的连接,断开其它的父连接;
3.结果即是使这条兄弟链变成以兄长为根的子树,新枝都变为右枝,旧枝变为左枝;
转换后得到的二叉树的根结点的右子树总是空的。

森林转二叉树:
1.将森林中的每棵树转为二叉树;
2.将每棵树对应的二叉树的根作为兄弟结点连接起来;
3.同样遵循子树外部左排列、子树内部右排列的规则;
森林中有m个非终端结点,则其对应的二叉树中有m+1个右指针域为空的结点。右指针为空,即没有右孩子。因为每个非终端结点转换成二叉树后都对应(本身是,或者它的右孩子…是)一个无右孩子的结点,另外最后一棵树的根结点转换后也没有右孩子。
转换后得到的二叉树的根结点和其左子对对应森林中的第一棵树,右子树对应森林中的所有其它树。

二叉树转森林:
1.将根结点与其右子树连线断开,继续对新生的二叉树断开其根结点和其右子树的连接,得到多棵无右子树的二叉树。
2.把每个二叉树中的所有右支中的各结点依次断开连接并连接到支的父结点;最终得到多棵只根其结点多枝,其它结点都单枝的树。

树的遍历

树的先序遍历,与其对应的二叉树的先序遍历,结果相同。
树的中序遍历,与其对应的二叉树的中序遍历,结果相同。

树存储结构:孩子链表表示法、孩子兄弟链表表示法、双亲表示法。

按层遍历孩子兄弟链表结点,采用队列辅助,在访问某个结点后,立即把它的孩子和兄弟都加入队列。
1.根结点入队列
2.判断队列不为空时,出列一个元素,并访问这个元素的数据
3.将上一步访问的元素的孩子及其兄弟、兄弟的兄弟…,入队列。
4.循环步骤2、3。

哈夫曼(Huffman)树

树的应用之一是可以描述分类过程,按标准将数据划分为不同的种类。

判定树:描述分类过程的二叉树。分类问题中的因素有总数N,某个类别的属性有名称、条件、占比(权重)。二叉树中分叉结点表示判断条件,叶子结点表示值。判断树中的问题在于,同一个分类问题有不同的分类算法,会产生不同的判定树。它们从表面上看有纵深形状或水平形状,那么它们的总加权遍历查找的计算量也不同。则判定树中要研究的课题是要使平均比较次数计算量最小,使权重大的类别的比较次数尽量少。

哈夫曼算法和哈夫曼树,是从序列生成树的过程:
1.给定一组类别,{p1,p2,…,pk},其初始对应为单根树的森林{T1,T2…Tk}。
2.从森林中选两个根结点权(即占比)最小的树合并,它们分别为新树的左右子树,整齐起见可以按左小右大排列,新树的根结点权为左右子结点权之和。
3.直到森林中只剩一棵最小带权路径长度的二叉树,即哈夫曼树。
哈夫曼树也是满二叉树,其中共有2n0-1个结点,n0个叶结点是初始森林中的结点数。
WPL(Weight Path Length Of Node 带权路径长度)= 权与比较次数的乘积之和。

哈夫曼树的树形不一定唯一,但其WPL值最小且相等
哈夫曼字符编码不一定唯一,但总码长最短
哈夫曼树没有严格要求区别左右子树权重次序

哈夫曼编码:
在通信领域,希望字符在传输中总编码长度最短。
给出所有不同的字符,根据其出现次数比重构造哈夫曼树,然后将每个结点的左分支路径标记为0,右分支路径标记为1,每个叶结点都有一个从根结点开始的唯一的0、1序列,这个序列即是这个字符的编码,即哈夫曼编码。

排序思想

直接插入排序

将后面的无序区中的元素挨个向前面的有序区中插入。直接插入排序过程中一边比较一边后覆盖移动数据。
1.将顺序表中R[0]用作哨兵,按索引i=2…n的次序,将R[i]向有序区R[1…i-1]中执行插入操作。
2.插入操作可采取在有序区中从后向前的查找比较和移动的方法。
3.此操作中比较的次数与原序列的排列状态有关:
当原序列为正序时,在插入操作中插入位置为尾部即只需要比较一次,排序中比较的总次数为n-1,效率很高;
当原序列为反序时,插入位置为头部则需要和有序序列中的每个元素比较一次,效率很低。

时间复杂度:正序时O(n),反序时 O(n²),平均时间复杂度 O(n²)
空间复杂度:O(1),就地排序
直接插入排序是稳定的。

希尔排序(分组插入排序)

1.把序列分为d个组,分组方法为所有距离为d的元素划到一个组内。
2.各组内进行直接插入排序。
3.按照避免增量序列中的值互为倍数,及最后一个增量必须为1的原则,设定增量序列d。

希尔排序是不稳定的。

冒泡(交换)排序

1.从下面无序区的最底部元素开始向上两两比较,最小者交换到无序区的最顶部,它同时也处了在有序区的最底部。
2.当某一趟扫描中的两两比较未出现交换,则说明无序区已全部有序,排序结束。
在n-1趟起泡中,总的比较次数=(n-1)+(n-2)+…+1=(n-1)n/2。
新教材中是值大的从序列左边交换到最右边,右边为有序区。

时间复杂度:正序时O(n),反序时 O(n²),平均时间复杂度 O(n²)
空间复杂度:属于就地排序
冒泡排序是稳定的。性能低于直接插入排序。

(两端)快速(交换)排序(基准分冶)

1.确定基准
在区间R中可随机选择一个元素作为基准,和R[0]交换位置,则R[0]变为基准,通常直接取R[0]作为基准。
2.对比划分
以R[0]作为基准做一趟划分操作:从区间右端和左端向中间依次交替与基准比较大,根据小在左侧、大在右侧的规则与基准交换位置,最终生成比基准值小和大的左右两个无序的子区间。在一趟划分过程中区间元素逐渐变少,不包括已比较过的元素,左右交替要在成功交换后。
或者是把基准存放到一个临时变量中,在交换位置时是右左两端的当前值腾挪。
3.递归
对每个子区间递归定基准-划分过程。

划分操作结果中有一个子区间为空,及两个子区间都不为空,这两种情况比较,前者整体排序中做的比较次数更多。

时间复杂度:最好 O(nlgn),对有序序列最坏 O(n²),平均 O(nlgn)
空间复杂度:O(lgn)
快速排序是不稳定的。

直接选择排序

1.从后面的无序区中选择最小的元素,与无序区头部元素交换,则有序区末尾增加一个元素,无序区头部减少一个元素。
此步中的交换操作优于元素整体后移操作。
2.对新的有序区和无序区执行上一步操作。
对链表结构的数据做直接选择排序,可以只交换结点的数据,而不移动结点。
时间复杂度:O(n²),其键值比较的次数与初始序列的排列顺序无关。
空间复杂度:O(1),就地排序
直接选择排序是不稳定的,不稳定的原因在于步骤中的元素交换。

插入排序是先在指定位置取元素,然后再找合适的位置插入,重心在第二步的插入。
选择排序是先找最小的元素,然后交换到指定位置,重心在第一步的选择。

堆排序(树形选择排序)

相对于直接选择排序,堆排序是保存利用前n-1次比较所得的信息,来减少各次选择中比较的次数。
大根堆的排序结果为升序列。
首先定义调整堆(筛选):判断调整根子树,将根与两个孩子中较大者(大根堆)交换,继而判断调整有变动的子子树。
1.从序列建二叉树
将初始关键字序列转换为完全二叉树结构。
2.构造堆
在树中从下往上依次对位置编号为⌊n/2⌋…1为根的子树做调整堆操作。结果构造出堆,但并不有序。
3.将堆根元素交换到无序区尾部,即有序区首部。
令i为本次调整的序号,将堆顶元素R[1]和最后一个元素R[n-i+1]交换,则新的无序区变为R[1…n-i],有序区为R[n-i+1,n]。即输出堆顶元素,并且把最后一个元素换到堆顶。
4.判断调整重建堆
同步骤2。
5.对新的无序区重复3、4步骤共n-1次。

时间复杂度:平均和最坏都是 O(nlgn)
空间复杂度:O(1),就地排序
堆排序是不稳定的。

(两两)归并排序(二路归并排序)

1.将区间内的元素两两做二路归并。
2.将上一步形成的各个有序组两两做二路归并。
3.直至全部元素进入同一个有序组。
4.二路归并需要同等的辅助空间。

时间复杂度:O(nlgn)
空间复杂度:O(n),
归并排序是稳定的。

以上基于关键字比较的排序时间下限是O(nlgn),而分配排序无须比较关键字,通过分配和收集过来实现排序,它们的时间复杂度可以下破到线性阶O(n)。

箱排序(桶排序)

分配排序不基于关键字比较,而是通过分配和收集过程实现排序。时间复杂度可达线性阶。
第一种箱排序是设置箱子个数和关键字的种类的个数相同;
第二种桶排序是关键字映射到某个桶中,桶中的所有元素再单独做关键字比较排序

基数排序

基数排序要求分析关键字的结构,分为多关键字和单关键字,每个关键字又由多个位组成。
单关键字的每位即每个分量可能取值个数称为基数,
基数排序是按基数的个数次数从低位到高位对序列元素进行箱排序,每箱排序的结果作为下一趟排序的输入。

基数排序是稳定的。

查找思想

查找表的逻辑结构是集合。
静态查找表:只进行查找、读取元素的操作的查找表。我们不关心查找表的创建。
动态查找表:在查找前,我们要先根据原有集合创建这个查找表,并且在创建过程中需要查找,当查找不到元素时插入。

查找长度即是比较次数,平均查找长度ASL,是每个元素查找需要的比较次数*其查找概率,之和。每个元素查找概率相等即1/n。

线性表查找

1.顺序查找,ASL=(1+…+n)/n=(n(n+1)/2)/n=(n+1)/2。
平均时间复杂度 O(n)。
岗哨的位置在要查找的元素外,所以在查找不成功时,与关键字的比较次数是n+1。
2.二分查找,也称折半查找,要求线性表是按关键字有序顺序表,只适用于静态查找表。
中间点位置=⌊(low+high)/2⌋,在和中间点位置值比较后,得出的左右两段都不再包含此中间点位置。
二分查找过程用二叉树来描述,称为描述二分查找的判定树,或比较树。
ASL=((n+1)/n)*lg(n+1)-1≈lg(n+1)-1。
树深度=⌈lg(n+1)⌉。
平均时间复杂度 O(lgn)。
3.分块查找,又称索引顺序查找,性能介于顺序和二分查找之间。安要求线性表分块有序。
它的索引表是由各块中的最大关键字及块起始位置组成的有序表。
先查找索引表,确定块,再在块内顺序查找。

树表之二叉排序树

二叉排序树,又称二叉查找树。中序遍历一棵二叉排序树可得到键值的升序序列。ASL介于O(lgn)和O(n)。
从键值序列生成二叉排序树:挨个把序列中的元素接入树中的左小右大的适当位置,每次增加的新结点都是树上的新的叶子结点。
从整体看,排序树只是用来排序,它的状态不一定有序。
运算:插入、生成、删除、查找。
平衡二叉树是指任一结点的左右子树的高度大致相同。
同一些关键字的不同序列,可能会得到相同的二叉排序树。这些序列的基本特征是开头字符相同,然后接着是全部右枝中的点或全部左枝中的点。
二叉排序树与二分查找类似,关键字比较的次数不超过二叉树的深度。

B-树

读作B树,即Balance Tree,多路平衡查找树。度为m的B树称为m阶B树。度数大则高度小,较大的度数使结点中的关键字较多,相比减小了磁盘访问次数。
一般地,文件中查找性能,受到的磁盘IO的次数的影响,远大于内存中比较的次数的影响。B树用于对较大的,存放在外部存储器上的文件内查找,是一种尽可能降低磁盘IO次数的文件组织方式。Mysql的数据索引存储即是基于Hash表或者B+树。
非根结点关键字数j:⌈m/2⌉-1<=j<m-1。

https://www.sohu.com/a/154640931_478315

散列(Hash)技术

和排序类似,要突破lgn的下界,就不能只依赖比较。
将结点按关键字的散列地址,存储到散列表中的过程,称为散列。
散列函数的作用是压缩待处理的下标范围|U|到m=O(|K|),即|K|的线性阶数量级,|K|<= m <|U|,所以从所有情况来看,冲突总会出现。
散列函数的标准是简单和均匀。有平方取中法、除余法、相乘取整法、随机数法。
处理冲突的方法:开放定址法(线性探查法、二次探查法、双重散列法)、拉链法。
地址单元为空的地址称为开放地址。
开放定址是当冲突发生时,用某种探查法在散列表中找到一个地址来放置这个冲突的结点。
散列表上的查找:
1.在散列表中查找散列地址h(K),若其单元为空,则查找失败。
2.比较其单元和K值是否相等,若相等则查找成功。
3.按冲突处理方法计算下一个散列地址h(K)。
堆积:是非同义词之间对一个散列地址的争夺现象,我理解为二次冲突、后继冲突,即解决冲突而给出的地址仍然已被占用了。

文件

文件是性质相同的记录的集合。
记录是文件中存取的基本单位,数据项是文件可使用的最小单位。
操作系统研究的文件是一维的无结构连续字符序列,数据库中研究的文件是带有结构的记录集合。

文件在外存上的4种基本组织方式:顺序、索引、散列、链(多关键字)。
磁带和磁盘分别是顺序存取设备和直接存取设备。

顺序文件

顺序文件按记录进入文件的顺序存储。
顺序有序文件和顺序无序文件。
顺序文件多用在磁带上。

索引文件

索引表指明逻辑记录和物理记录的对应关系,索引表和主文件一起构成索引文件,在存储器上分为索引区和数据区。
主文件分为索引顺序文件和索引非顺序文件,索引非顺序文件适合随机存取,索引顺序文件适合于顺序存取。
索引表分为稠密索引和稀疏索引。
还可以对索引表建立索引,称为查找表。查找表可以有多级。
这种多级顺序表索引是一种静态索引。而动态索引采用二叉排序树、AVL树、B-树等树表结构,插入和删除方便。

索引顺序文件

两种常用的索引顺序文件:ISAM文件和VASM文件。
ISAM:索引顺序存取方法,为磁盘存取设计,采用静态索引结构。ISAM文件由多级主索引、柱面索引、磁道索引、主文件组成。
VSAM:虚拟存储存取方法,采用B+树作为动态索引结构。VSAM文件由索引集、顺序集、数据集组成。

散列文件

也称为直接存取文件,散列文件主要采用拉链法处理冲突。
散列文件只能按关键字随机存取,不能顺序存取。

多关键字文件

多重表文件,对每个次关键字也建立一个索引,并且将具有相同次关键字的记录的物理地址链接起来,次关键字索引表的一条记录包括次关键字、链表的头指针、链表长度。
倒排文件,与多重表文件相比,倒排文件把链表的物理地址放在了次关键字索引表中了。
与单关键字索引文件相比,倒排文件是按给定次关键字查找记录,而不是在已查找记录中找次关键字。

概论

1946年首台计算机ENIAC问世。
计算机软件相对硬件发展缓慢。软件的核心是算法,算法是加工数据的过程。
数据的存储结构是逻辑结构用计算机语言的实现。本课程数据结构主要是讨论存储结构,并且我们只在高级语言的层次上讨论存储结构。

时间复杂度

时间复杂度是省去了系数的,平均查找长度则是有系数的。
n!的算法的时间复杂度是O(n)。
{i=s=0;while(s<=n){i++;s+=i;}}时间复杂度O(n1/2)

线性表

Linear List,运算受限的线性表
Sequential List
Link List

在表长为n的顺序表中插入一个数据元素,平均需要移动约n/2个数据元素。这句话是指顺序表中低地址区已经连续存在了n个元素了,并且其空间可以无限增大。插入元素的位置可以是n个元素现有的位置及其右侧的一个位置,则可选插入位置数是n+1。对于删除操作,可选删除位置数是n。

出栈和取栈顶元素操作是分开的。
顺序表实现的栈,元素出栈后不用free。
顺序表的岗哨是在n个元素之外的位置上。

数组

数组是线性表的一种推广。
二维数组a[m][n],每个元素占k个存储单元,以行序为主序的存储中,a[i][j]的位置索引L=i*n+j,存储地址loc[i,j]=loc[0,0]+L*k。

矩阵的压缩存储

对称矩阵:满足n阶方阵中a[i,j]=a[j,i],以行为主序存储下三角中的元素,a[i,j]的位置K:
当i>=j,即下三角中的元素,k=i(i+1)/2+j;
当i<j,即上三角中的元素,k=j(j+1)/2+i;

三角矩阵:上(下)三角矩阵的下(上)三角全为固定值。
上三角矩阵中前i行的元素个数=i(2n-i+1)/2。a[i,j]的位置K:
当i<=j,即上三角中的元素,k=i(2n-i+1)/2+j-i;
当i>j,即下三角中的元素,k=n(n+1)/2;
下三角矩阵中a[i,j]的位置K:
当i>=j,即下三角中的元素,k=i(i+1)/2+j;
当i<j,即上三角中的元素,k=n(n+1)/2;

顺序栈初始top=0,此时栈空。用了一个元素空间来表示栈底,实现数组的空间MaxSize值比栈空间大小多一个。

已知栈的输入顺序,判断给出的输出顺序的可能性,快速方法是:把输入序列和输出序列做一段消除,若消除后的结果相同,则有可能为真。消除的这一段序列是在输出序列中头部或尾部的一段,在输入序列中是正序连续或逆序连续的子序列。消除后的结果不能是输入顺序的右边部分。

队列

非循环顺序队列,为记忆数组索引关系,可以理解为队头出口开在了顺序栈的底部。并且也用了一个元素空间来指示队首。
链队列头指针头结点指向队列首元素。
循环队列长度=(rear-front+Max) % Max;

信息系统开发与管理

题型要点

1.数据流图题型要点
把流程描述中的动词转为加工处理。
处理和存储分别标上Pn和Dn。
系统内的参与者根据其是否有承接的处理操作来决定其是否需要出现在图中,或出现其处理操作。
数据流不能是生产实物,一般是单据等。
加工处理生成的信息如果主动传递到其它环节,而是由其它环节主动使用,则将此生成信息归档。例如:制作的记账凭证、登记的会计账簿。
除了开头和结尾的数据源点和终点,流程中间可能也会出现外部实体,也可能会没有终点的外部实体。例如:申请采购流程中间的供应商发货,输出发货单…
外部实体也可能出现在加工处理环节和文件节点之间。即加工处理依据的数据也可能来自外部实体。
2.模块结构图题型要点
题图的含义是,上方的主模块调用下方的各个子模块,来实现功能。明确了调用方向,就明确了数据方向。
多个数据同时传递时,注意它们可能有顺序要求。
模块结构图中主模块对子模块的调用是从左到右的顺序。
3.实体关系图和数据库逻辑模式题型要点
实体关系图中在实体间写上关系的名称,根据要求看是否要在实体上加上其各个属性。
对于多对多的关系,要设计其数据库逻辑模式,其主键是组合字段,它可能也有自己的属性。
数据库逻辑模式中主键要加上下划线。
4.数据流图->变换分析->简单模块结构图
主模块的三个从属模块,从左到各分别是:输入模块、变换模块、输出模块。

软件开发工具题型要点

1.应用题题型要点
应用题中如果函数需要在其实现之前调用,则需要在调用有对其声明。
2.年代题题型要点
60年代初,高级程序设计语言成熟和普及,计算机走出难以应用的困窘局面;此阶段也称为程序设计自动化;
60年代末,非过程化语言思想出现;结构化程序设计思想产生;人们认识到“软件危机”问题;
70年代,Smalltalk语言出现;
70年代末,利用通用软件作为辅助工具的阶段开始
80年代以来,专用软件开发工具陆续问世;时序网络得到了广泛应用;软件工具(软件工程)的思想与方法广泛宣传;
80年代初期,宁波软件学术会议
80年代中期,软件开发工具兴起,专项的、支持某一工作环节的专用工具大量涌现;
80年代末,人们发现了专用开发工具的弱点,提出了一体化的要求,一体化的趋势明显;1989年IBM的AD/Cycle理论框架标志着进入集成软件开发环境阶段。
90年代,软件开发进入了大量应用软件开发工具的阶段
90年代,1992年已有30余种一体化开发工具产品推向市场;1994年IBM停止了AD/Cycle计划;1994年UML工作在Rational公司开始,1997年Rational提出了UML。
21世纪以来,软件开发工具发展到了互联网阶段;软件开发进入了规模更大、应用更广的阶段;
21世纪,2008年美国电气与电子协会发现以“软件开发工具”为题的一期专刊;2002年Rational初IMB收购。
3.近义混淆词
速度和效率
错误视图和断点视图
表示层和用户接口层

图结构中,圆圈称为顶点,连线称为边,有向图的边称为弧。
有序偶对用尖括号,无序偶对用圆括号。
简单路径:序列中顶点不重复出现的路径。
n个顶点的无向完全图的边数=n(n-1)/2,n个顶点的有向完全图的边数=n(n-1)。

图的存储结构

邻接矩阵:图的n的顶点的相邻关系用n阶方阵来表示,其中用1表示顶点间存在的边或弧,用0表示顶点间不存在边。
除了用0、1表示是否有边外,对于带权图,还可以用边的权值来替代1,用无穷替代0。
还需要另一个数组来存储n个顶点的附带信息。
对于有向图,矩阵中行表示出度,列表示入度。
无向图的邻接矩阵是一个对称矩阵。
无向图的边数=值为1的个数/2,有向图边数=值为1的个数。
无向图某顶点的度数=邻接矩阵中对应行或列的值之和。

邻接表:
对每个顶点建立一个单链表,这个单链表称为顶点v的邻接表。再用一个数组存储所有的单链表的头结点。
对于无向图,单链表中的每个结点都和顶点v之间存在边。
对于有向图,单链表中的每个结点都和顶点v之间存在边,且是这条边的终点。
对于有向图,有时还需要建立逆邻接表,它较容易求出顶点v的入度。

遍历和搜索

图的遍历是从某个顶点出发,访问图的每个顶点一次。
图的搜索是从某个顶点出发,访问能访问到的每个顶点一次。
遍历图的两种基本方法:深度优先搜索和广度优先搜索。
由于顶点间都可能相邻接,在遍历的过程中,需要增设一个辅助数组,标记各顶点是否被访问过。

连通图的深度优先搜索:
类似于树的先序遍历,可以看成一个递归过程。
当某个顶点的所有邻接点都被访问过时,搜索过程要加到前一个顶点寻找未被访问的顶点。
深度搜索的顶点访问序列不是唯一的。
以邻接表为存储结构,时间复杂度为O(n+e)。
以邻接矩阵为存储结构,时间复杂度为O(n2)。

连通图的广度优先搜索:在访问完所有邻接点后,要依次从这些邻接点出发继续广度搜索。
类似于树的按层次遍历。
广度优先搜索具有先进先出的特征,可以用队列暂存访问过的顶点。

最小生成树(最小遍历树)

连通图的一次遍历所经过的顶点和边就构成了图的一棵生成树。连通图的遍历序列不是唯一的,其中权总和最小的生成树叫做最小生成树。
生成树是连通图的极小连通无环子图,不是连通分量。
n个顶点的无向图,所有生成树中都有n-1条边。构建最小生成树的过程,即找到这n-1条权总和最小的边。

构造最小生成树的Prim(普里姆)算法:原状列出带权图的各顶点,从顶点v0出发,在已通路径的任意点中向外连接上新的最小权边,最终得到图的最小生成树。
树造最小生成树的Kruskal(克鲁斯卡尔)算法:原状列出带权图的各顶点,在所有连通分量(顶点)间按权从小到大找边并连接,最终得到图的最小生成树。
单源最短路径Dijkstra(迪杰斯特拉)算法:从只包含最初源顶点的源集出发,每趟把上一趟列出的权值最小路径点加入到源集中,接着列出源集到除了最初源点的各点的最小权值。最终得到最短路径序列。

拓扑

AOV网:用图中的顶点表示活动,有向边表示活动之间的优先关系,这种表示活动关系的有向图称为AOV网。
拓扑排序,即输出有向图顶点的拓扑序列:
1.在无环有向图中选择一个入度为0的顶点,输出该顶点,然后在图中删除该顶点及和其关系的弧。
2.重复上一条直到图中只剩最后一个顶点。这样的顶点输出序列即为拓扑序列。
邻接表拓扑排序算法的时间复杂度为O(n+e)。

拓扑序列: