1、渐近时间复杂度:就是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。评价一个算法的时间性能时,主要标准就就是算法的渐近时间复杂度。算法中语句的频度不仅与问题规模有关,还与输入实例中各元素的取值相关。时间复杂度按数量级递增排列依次为:常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O（n2）、立方阶O（n3）、k次方阶O（nk）、指数阶O（2n）。空间复杂度:就是某个算法的空间耗费,它就是该算法所求解问题规模n的函数。算法的时间复杂度与空间复杂度合称算法复杂度。第二章 线性表线性表就是由n0个数据元素组成的有限序列。n=0就是空表;非空表,只能有一
2、个开始结点,有且只能有一个终端结点。线性表上定义的基本运算:构造空表:Initlist（L）求表长:Listlength（L）取结点:GetNode（L,i）查找:LocateNode（L,x）插入:InsertList（L,x,i）删除:Delete（L,i）顺序表就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置与逻辑结构中各结点相邻关系就是一致的。地址计算:LOCa（i）=LOCa（1）+（i-1）*d;（首地址为1）在顺序表中实现的基本运算:平均移动结点次数为n/2;平均时间复杂度均为O（n）。 平均移动结点次数为（n-1）/2;线性表的链式存
3、储结构中结点的逻辑次序与物理次序不一定相同,为了能正确表示结点间的逻辑关系,在存储每个结点值的同时,还存储了其后继结点的地址信息（即指针或链）。这两部分信息组成链表中的结点结构。 一个单链表由头指针的名字来命名。单链表运算:建立单链表头插法:s-next=head;head=s;生成的顺序与输入顺序相反。尾插法:head=rear=null;if（head=null） head=s;else r-next=s;r=s; 平均时间复杂度均为O（n）加头结点的算法:对开始结点的操作无需特殊处理,统一了空表与非空表。查找按序号:与查找位置有关,平均时间复杂度均为O（n）。按值:与输入实例有关,平均时
4、间复杂度均为O（n）。插入运算:p=GetNode（L,i-1）;next=p-next;p-平均时间复杂度均为O（n）删除运算:r=p-next=r-free（r）;单循环链表就是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件就是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点就是查找头指针与尾指针的时间都就是O（1）,不用遍历整个链表。双链表就就是双向链表,就就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针head惟一确定。双链表也可以头尾相链接构成双（向）循环链表。双链表上的插入与
5、删除时间复杂度均为O （1）。顺序表与链表的比较:基于空间: 顺序表的存储空间就是静态分配,存储密度为1;适于线性表事先确定其大小时采用。链表的存储空间就是动态分配,存储密度1;适于线性表长度变化大时采用。基于时间:顺序表就是随机存储结构,当线性表的操作主要就是查找时,宜采用。以插入与删除操作为主的线性表宜采用链表做存储结构。若插入与删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。第三章 栈与队列栈（Stack）就是仅限制在表的一端进行插入与删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底。表中无元素时为空栈。栈的修改就是按后进先出的原则进行的,我们又称栈为LIFO表（L
6、ast In First Out）。通常栈有顺序栈与链栈两种存储结构。栈的基本运算有六种:构造空栈:InitStack（S）判栈空: StackEmpty（S）判栈满: StackFull（S）进栈: Push（S,x）退栈: Pop（S）取栈顶元素:StackTop（S）在顺序栈中有“上溢”与“下溢”的现象。“上溢”就是栈顶指针指出栈的外面就是出错状态。“下溢”可以表示栈为空栈,因此用来作为控制转移的条件。顺序栈中的基本操作有六种:构造空栈 判栈空 判栈满 进栈 退栈 取栈顶元素链栈则没有上溢的限制,因此进栈不要判栈满。链栈不需要在头部附加头结点,只要有链表的头指针就可以了。链栈中的基本操作
7、有五种:队列（Queue）就是一种运算受限的线性表,插入在表的一端进行,而删除在表的另一端进行,允许删除的一端称 为队头（front）,允许插入的一端称为队尾（rear） ,队列的操作原则就是先进先出的,又称作FIFO表（First In First Out） 、队列也有顺序存储与链式存储两种存储结构。队列的基本运算有六种:置空队:InitQueue（Q）判队空:QueueEmpty（Q）判队满:QueueFull（Q）入队:EnQueue（Q,x）出队:DeQueue（Q）取队头元素:QueueFront（Q）顺序队列的“假上溢”现象:由于头尾指针不断前移,超出向量空间。这时整个向量空间及队
8、列就是空的却产生了“上溢”现象。为了克服“假上溢”现象引入循环向量的概念,就是把向量空间形成一个头尾相接的环形,这时队列称循环队列。判定循环队列就是空还就是满,方法有三种:一种就是另设一个布尔变量来判断;第二种就是少用一个元素空间,入队时先测试（rear+1）%m = front）？ 满:空;第三种就就是用一个计数器记录队列中的元素的总数。队列的链式存储结构称为链队列,一个链队列就就是一个操作受限的单链表。为了便于在表尾进行插入（入队）的 操作,在表尾增加一个尾指针,一个链队列就由一个头指针与一个尾指针唯一地确定。链队列不存在队满与上溢的问题。在链队列的出队算法中,要注意当原队中只有一个结点时
9、,出队后要同进修改头尾指针并使队列变空。第四章 串串就是零个或多个字符组成的有限序列。空串:就是指长度为零的串,也就就是串中不包含任何字符（结点）。空白串:指串中包含一个或多个空格字符的串。在一个串中任意个连续字符组成的子序列称为该串的子串,包含子串的串就称为主串。子串在主串中的序号就就是指子串在主串中首次出现的位置。空串就是任意串的子串,任意串就是自身的子串。串分为两种:串常量在程序中只能引用不能改变;串变量的值可以改变。串的基本运算有:求串长strlen（char*s）串复制strcpy（char*to,char*from）串联接strcat（char*to,char*from）串比较ch
10、arcmp（char*s1,char*s2）字符定位strchr（char*s,charc）串就是特殊的线性表（结点就是字符）,所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串。顺序串又可按存储分配的不同分为:静态存储分配:直接用定长的字符数组来定义。优点就是涉及串长的操作速度 快,但不适合插入、链接操作。动态存储分配:就是在定义串时不分配存储空间,需要使用时按所需串的长度分配存储单元。串的链式存储就就是用单链表的方式存储串值,串的这种链式存储结构简称为链串。链串与单链表的差异只就是它的 结点数据域为单个字符。为了解决“存储密度”低的状况,可以让一个结点存储多个字符,即结点
11、的大小。顺序串上子串定位的运算:又称串的“模式匹配”或“串匹配”,就是在主串中查找出子串出现的位置。在串匹配中,将主串称为目标（串）,子串称为模式（串）。这就是比较容易理解的,串匹配问题就就是找出给定模式串P在给定目标串T中首次出现的有效位移或者就是全部有效位移。最坏的情况下时间复杂度就是O（n-m+1）m）,假如m与n同阶的话则它就是O（n2）。链串上的子串定位运算位移就是结点地址而不就是整数第五章 多维数组数组一般用顺序存储的方式表示。存储的方式有:行优先顺序,也就就是把数组逐行依次排列。PASCAL、C列优先顺序,就就是把数组逐列依次排列。FORTRAN地址的计算方法:按行优先顺序排列的
12、数组:LOCa（ij）=LOCa（11）+（i-1）*n+（j-1）*d、按列优先顺序排列的数组:LOCa（ij）=LOCa（11）+（j-1）*n+（i-1）*d、矩阵的压缩存储:为多个相同的非零元素分配一个存储空间;对零元素不分配空间。特殊矩阵的概念:所谓特殊矩阵就是指非零元素或零元素分布有一定规律的矩阵。稀疏矩阵的概念:一个矩阵中若其非零元素的个数远远小于零元素的个数,则该矩阵称为稀疏矩阵。 特殊矩阵的类型:对称矩阵:满足a（ij）=a（ji）。元素总数n（n+1）/2、I=max（i,j）,J=min（i,j）,LOCa（ij）=LOC（sa0）+（I*（I+1）/2+J）*d、三角矩
13、阵:上三角阵:k=i*（2n-i+1）/2+j-i,LOCa（ij）=LOC（sa0）+k*d、下三角阵:k=i*（i+1）/2+j,LOCa（ij）=LOC（sa0）+k*d、对角矩阵:k=2i+j,LOCa（ij）=LOC（sa0）+k*d、稀疏矩阵的压缩存储方式用三元组表把非零元素的值与它所在的行号列号做为一个结点存放在一起,用这些结点组成的一个线性表来表示。但这种压缩存储方式将失去随机存储功能。加入行表记录每行的非零元素在三元组表中的起始位置,即带行表的三元组表。第六章 树树就是n个结点的有限集合,非空时必须满足:只有一个称为根的结点;其余结点形成m个不相交的子集,并称根的子树。根就是
14、开始结点;结点的子树数称度;度为0的结点称叶子（终端结点）;度不为0的结点称分支结点（非终端结点）;除根外的分支结点称内部结点;有序树就是子树有左,右之分的树;无序树就是子树没有左,右之分的树;森林就是m个互不相交的树的集合;树的四种不同表示方法:树形表示法;嵌套集合表示法;凹入表示法广义表表示法。二叉树的定义:就是n0个结点的有限集,它就是空集（n=0）或由一个根结点及两棵互不相交的分别称作这个根的左子树与右子树的二叉树组成。二叉树不就是树的特殊情形,与度数为2的有序树不同。二叉树的4个重要性质:二叉树上第i层上的结点数目最多为2（i-1）（i1）。;深度为k的二叉树至多有（2k）-1个结点
15、（k1）;在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1;具有n个结点的完全二叉树的深度为int（log2n）+1、满二叉树就是一棵深度为k,结点数为（2k）-1的二叉树;完全二叉树就是满二叉树在最下层自右向左去处部分结点;二叉树的顺序存储结构就就是把二叉树的所有结点按照层次顺序存储到连续的存储单元中。（存储前先将其画成完全二叉树）树的存储结构多用的就是链式存储。BinTNode的结构为lchild|data|rchild,把所有BinTNode类型的结点,加上一个指向根结点的BinTree型头指针就构成了二叉树的链式存储结构,称为二叉链表。它就就是由根指针
16、root唯一确定的。共有2n个指针域,n+1个空指针。根据访问结点的次序不同可得三种遍历:先序遍历（前序遍历或先根遍历）,中序遍历（或中根遍历）、后序遍历（或后根遍历）。时间复杂度为O（n）。利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点与后继结点的指针,这些附加的指针就称为“线索”,加上线索的二叉链表就称为线索链表。线索使得查找中序前趋与中序后继变得简单有效,但对于查找指定结点的前序前趋与后序后继并没有什么作用。树与森林及二叉树的转换就是唯一对应的。转换方法:树变二叉树:兄弟相连,保留长子的连线。二叉树变树:结点的右孩子与其双亲连。森林变二叉树:树变二叉树,各个树的根相连
17、。树的存储结构:有双亲链表表示法:结点data | parent,对于求指定结点的双亲或祖先十分方便,但不适于求指定结点的孩子及后代。孩子链表表示法:为树中每个结点data | next设置一个孩子链表firstchild,并将data | firstchild存放在一个向量中。双亲孩子链表表示法:将双亲链表与孩子链表结合。孩子兄弟链表表示法:结点结构leftmostchild |data | rightsibing,附加两个分别指向该结点的最左孩子与右邻兄弟的指针域。树的前序遍历与相对应的二叉树的前序遍历一致;树的后序遍历与相对应的二叉树的中序遍历一致。树的带权路径长度就是树中所有叶结点的带
18、权路径长度之与。树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树）。在叶子的权值相同的二叉树中,完全二叉树的路径长度最短。哈夫曼树有n个叶结点,共有2n-1个结点,没有度为1的结点,这类树又称为严格二叉树。变长编码技术可以使频度高的字符编码短,而频度低的字符编码长,但就是变长编码可能使解码产生二义性。如00、01、0001这三个码无法在解码时确定就是哪一个,所以要求在字符编码时任一字符的编码都不就是其她字符编码的前缀,这种码称为前缀码（其实就是非前缀码）。哈夫曼树的应用最广泛地就是在编码技术上,它能够容易地求出给定字符集及其概率分布的最优前缀码。哈夫曼编码的构造很容易,只要画好了哈夫曼
19、树,按分支情况在左路径上写代码0,右路径上写代码1,然后从上到下到叶结点的相应路径上的代码的序列就就是该结点的最优前缀码。第七章 图图的逻辑结构特征就就是其结点（顶点）的前趋与后继的个数都就是没有限制的,即任意两个结点之间之间都可能相关。图GraphG=（V,E）,V就是顶点的有穷非空集合,E就是顶点偶对的有穷集。有向图Digraph:每条边有方向;无向图Undigraph:每条边没有方向。有向完全图:具有n*（n-1）条边的有向图;无向完全图:具有n*（n-1）/2条边的无向图;有根图:有一个顶点有路径到达其它顶点的有向图;简单路径:就是经过顶点不同的路径;简单回路就是开始与终端重的简单路径
20、;网络:就是带权的图。图的存储结构:邻接矩阵表示法:用一个n阶方阵来表示图的结构就是唯一的,适合稠密图。无向图:邻接矩阵就是对称的。有向图:行就是出度,列就是入度。建立邻接矩阵算法的时间就是O（n+n2+e）,其时间复杂度为O（n2）邻接表表示法:用顶点表与邻接表构成不就是唯一的,适合稀疏图。顶点表结构 vertex | firstedge,指针域存放邻接表头指针。邻接表:用头指针确定。无向图称边表;有向图又分出边表与逆邻接表;邻接表结点结构为 adjvex | next,时间复杂度为O（n+e）。,空间复杂度为O（n+e）。图的遍历:深度优先遍历:借助于邻接矩阵的列。使用栈保存已访问结点。广
21、度优先遍历:借助于邻接矩阵的行。使用队列保存已访问结点。生成树的定义:若从图的某个顶点出发,可以系统地访问到图中所有顶点,则遍历时经过的边与图的所有顶点构成的子图称作该图的生成树。最小生成树:图的生成树不唯一,从不同的顶点出发可得到不同的生成树,把权值最小的生成树称为最小生成树（MST）。构造最小生成树的算法:Prim算法的时间复杂度为O（n2）与边数无关适于稠密图。Kruskal算法的时间复杂度为O（lge）,主要取决于边数,较适合于稀疏图。最短路径的算法:Dijkstra算法,时间复杂度为O（n2）。类似于prim算法。拓扑排序:就是将有向无环图G中所有顶点排成一个线性序列,若E（G）,则
22、在线性序列u在v之前,这种线性序列称为拓扑序列。拓扑排序也有两种方法:无前趋的顶点优先,每次输出一个无前趋的结点并删去此结点及其出边,最后得到的序列即拓扑序列。无后继的结点优先:每次输出一个无后继的结点并删去此结点及其入边,最后得到的序列就是逆拓扑序列。第八章 排序记录中可用某一项来标识一个记录,则称为关键字项,该数据项的值称为关键字。排序就是使文件中的记录按关键字递增（或递减）次序排列起来。基本操作:比较关键字大小;改变指向记录的指针或移动记录。顺序结构、链表结构、索引结构。经过排序后这些具有相同关键字的记录之间的相对次序保持不变,则称这种排序方法就是稳定的,否则排序算法就是不稳定的。排序过
23、程中不涉及数据的内、外存交换则称之为“内部排序”（内排序）,反之,若存在数据的内外存交换,则称之为外排序。内部排序方法可分五类:插入排序、选择排序、交换排序、归并排序与分配排序。评价排序算法好坏的标准主要有两条:执行时间与所需的辅助空间,另外算法的复杂程序也就是要考虑的一个因素。插入排序:直接插入排序:逐个向前插入到合适位置。哨兵（监视哨）有两个作用:作为临变量存放Ri就是在查找循环中用来监视下标变量j就是否越界。直接插入排序就是就地的稳定排序。时间复杂度为O（n2）,比较次数为（n+2）（n-1）/2;移动次数为（n+4）（n-1）/2;希尔排序:等间隔的数据比较并按要求顺序排列,最后间隔为
24、1、希尔排序就是就地的不稳定排序。时间复杂度为O（n1、25）,比较次数为（n1、25）;移动次数为（1、6n1、25）;交换排序:冒泡排序:自下向上确定最轻的一个。自上向下确定最重的一个。自下向上确定最轻的一个,后自上向下确定最重的一个。冒泡排序就是就地的稳定排序。时间复杂度为O（n2）,比较次数为n（n-1）/2;移动次数为3n（n-1）/2;快速排序:以第一个元素为参考基准,设定、动两个指针,发生交换后指针交换位置,直到指针重合。重复直到排序完成。快速排序就是非就地的不稳定排序。时间复杂度为O（nlog2n）,比较次数为n（n-1）/2;选择排序:直接选择排序:选择最小的放在比较区前。直
25、接选择排序就地的不稳定排序。时间复杂度为O（n2）。比较次数为n（n-1）/2;堆排序建堆:按层次将数据填入完全二叉树,从int（n/2）处向前逐个调整位置。然后将树根与最后一个叶子交换值并断开与树的连接并重建堆,直到全断开。堆排序就是就地不稳定的排序,时间复杂度为O（nlog2n）,不适宜于记录数较少的文件。归并排序:先两个一组排序,形成（n+1）/2组,再将两组并一组,直到剩下一组为止。归并排序就是非就地稳定排序,时间复杂度就是O（nlog2n）,分配排序:箱排序:按关键字的取值范围确定箱子数,按关键字投入箱子,链接所有非空箱。箱排序的平均时间复杂度就是线性的O（n）。基数排序:从低位到高
26、位依次对关键字进行箱排序。基数排序就是非就稳定的排序,时间复杂度就是O（d*n+d*rd）。各种排序方法的比较与选择:待排序的记录数目n;n较大的要用时间复杂度为O（nlog2n）的排序方法;记录的大小（规模）;记录大最好用链表作为存储结构,而快速排序与堆排序在链表上难于实现;关键字的结构及其初始状态;对稳定性的要求;语言工具的条件;存储结构;时间与辅助空间复杂度。第九章 查找查找的同时对表做修改操作（如插入或删除）则相应的表称之为动态查找表,否则称之为静态查找表。衡量查找算法效率优劣的标准就是在查找过程中对关键字需要执行的平均比较次数（即平均查找长度ASL）。线性表查找的方法:顺序查找:逐个
27、查找,ASL=（n+1）/2;二分查找:取中点int（n/2）比较,若小就比左区间,大就比右区间。用二叉判定树表示。ASL=（每层结点数*层数）/N、分块查找。要求“分块有序”,将表分成若干块内部不一定有序,并抽取各块中的最大关键字及其位置建立有序索引表。二叉排序树（BST）定义就是:二叉排序树就是空树或者满足如下性质的二叉树:若它的左子树非空,则左子树上所有结点的值均小于根结点的值;若它的右子树非空,则右子树上所有结点的值均大于根结点的值;左、右子树本身又就是一棵二叉排序树。二叉排序树的插入、建立、删除的算法平均时间性能就是O（nlog2n）。二叉排序树的删除操作可分三种情况进行处理:*P就是叶子,则直接删除*P,即将*P的双亲*parent中指向*P的指针域置空即可。*P只有一个孩子*child,此时只需将*child与*p的双亲直接连接就可删去
