第三章算法基础 算法算法的特性有穷性：执行有穷步之后结束，且每一步都可在有穷时间内完成。确定性（无二义性）：算法中每一条指令都必须有确切的含义，不能含糊不清。输入(>=0)即可以没有输入。输出(>=1)即必须有输出。有效性(可行性)：算法的每个步骤都能有效执行并能在执行有限次后得到确定的结果。例如a=0，b/a就无效。时间复杂度与空间复杂度时间复杂度    时间复杂度是指程序运行从开始到结束所需要的时间。    通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下：    如果存在两个常数c和m，对于所有的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3n3+2n2+n，则T(n)=o(n3)    常见的对算法执行所需时间的度量:O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < 0(n3) < 0(2n)空间复杂度    空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。时间复杂度O(1)单条语句k = 1;整个程序都没有循环语句，或复杂函数的调用void main(){ char *x = "ABCADAB"; int m = strlen(x); printf("len:%d\n",m);时间复杂度O(n)单层循环void main() { int i,j; k = 0; for(i = 0;i < n; i++){ b[i]=0; } }时间复杂度O(n2)双层循环void main() { int i,s = 0, n = 1000; for(i = 1;i < n; i++){ for(j = 1;j < n; j++) s+=j printf("结果为:%d",s); }由此可知时间复杂度O(n3)则为三层循环时间复杂度O(log2n)常为二分、二叉树等int search (int array[], int n, int v) int left, right, middle; left=0,right=n - 1; while(left <= right ){ middle=(left + right) / 2; if(array[middle] > v){ right=middle-1; } else if (array[middle] < v){ left=middle+1; } else{ return middle ; } } return-1; }时间复杂度O(nlog2n)典型代表：堆排序，每次重建堆的时间复杂度是log2n，n个元素基本上就是nlog2n。时间复杂度O(2n)典型代表：LCS最长公共子序列、钢管切割问题，动态规划法自顶向下，时间复杂度为O(2n)。常见算法策略算法策略概述一、分治法特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜素、大整数乘法、汉诺塔二、贪心法（一般用于求满意解）特征：局部最优，但整体不见得最优。每步有明确的，既定的策略。经典问题：背包问题（如装箱）、多机调度、找零钱问题三、动态规划法（用于求最优解）--“最优子结构”和递归式特征：划分子问题，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。（一般自顶向下时间复杂度为O(2n),自底向上时间复杂度为O(n2)效率更高）经典问题：斐波那契数列、矩阵乘法、背包问题、LCS最长公共子序列四、回溯法特征：系统的搜索一个问题的所有解或任一解。经典问题：N皇后问题、迷宫、背包问题常见算法总结算法名称关键点特征典型问题分治法递归技术把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。归并排序、快速排序、二分搜素贪心法一般用于求满意解，特殊情况可求最优解（部分背包）局部最优，但整体不见得最优。每步有明确的，既定的策略。背包问题（如装箱）、多机调度、找零钱问题动态规划法最优子结构和递归式、中间解数组划分子问题（最优子结构），并把子问题结果使用数组存储，利用查询子问题结果构造最终问题结果。矩阵乘法、背包问题、LCS最长公共子序列回溯法探索和回退系统的搜索一个问题的所有解或任一解。有试探和回退的过程。N皇后问题、迷宫、背包问题算法策略判断：回溯，大家比较熟悉，有尝试探索和回退的过程。这个比较好识别。分治，分治与动态规划法其实最难区分，分治不好解决问题，从而记录中间解、解决问题，有了动态规划法，但是在软设考试中，分治目前只有二分的思想，二分以外的思想都用动态规划法解决了。二分的时间复杂度，与O(nlog2n)相关，注意有没有外层嵌套循环。（结合归并排序、快速排序的过程，也是二分的）动态规划法，有递归式，经常考查递归式，此时自底向上实现时，中间解基本上是查表可得的，所以时间复杂度一般是O(n^k),具体k是多少，根据for循环的嵌套。此时循环变量能够看到，是从0或1开始，到n结束，这种情况就是从小规模到大规模，自底向上的。如果用到自顶向下，其实跟分治的实现就差不多了，查表的意义基本上可以忽略不计了，时间复杂度为O(2^n),递归的变量一般由开始，向1缩小，所以是大规模到小规模，也就是自顶向下的。（一般动态规划法涉及递归式，递归式还会经常用在代码填空中让大家补充缺失的填空，然后会有“最优子结构”的描述，会有表（数组）记录中间解。）贪心法，有时候也会出现“最优子结构”的描述，但是没有递归式。考虑的当前最优，求得的是满意解。（特殊情况下，贪心法有时候得到的也可以是最优解，比如部分背包问题）分治法    对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。递归// 斐波拉契数列 int F(int n) { if(n==0)return 1; if(n==1)return 1; if(n>1) return F(n-1)+F(n-2); }二分function Binary_Search(L,a,b,x){ if(a>b) return(-1); else{ m=(a+b)/2; if(x==L[m]) return(m); else if(x>L[m]) return(Binary_Search(L,m+1,b,x); else return(Binary_Search(L,a,m-1,x)); } }贪心法    总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但可能得不到最优解。【贪心法解决部分背包问题可得最优解】动态规划法    在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。（问题中如果出现“最优子结构”这类描述，并且结果用递归式表示，一般为动态规划法）回溯法    回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。试探部分：满足除规模之外的所有条件，则扩大规模。（扩大规模）回溯部分：（缩小规模）当前规模解不是合法解时回溯（不满足约束条件D）。求完一个解，要求下一个解时，也要回溯。查找算法顺序查找    顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。查找成功时，顺序查找的平均查找长度为（等概率情况下）：二分查找二分法查找的基本思想是：(设R[low,...,high]是当前的查找区)(1) 确定该区间的中点位置：mid=[(low+thigh)/2]；(2) 将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下：若R[mid].key>k，则由表的有序性可知R[mid,…,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low,…,mid-1]中。因此，新的查找区间是左子表R[low,…, high]，其中high=mid-1。若R[mid].key<k，则要查找的k必在mid的右子表R[mid+1,…,high]中，即新的查找区间是右子表R[low,…,high]，其中low=mid+1。若R[mid].key=k，则查找成功，算法结束。(3) 下一次查找是针对新的查找区间进行，重复步骤(1)和(2)。(4) 在查找过程中，low逐步增加，而high逐步减少。如果 high<low，则查找失败，算法结束。折半查找在查找成功时关键字的比较次数最多为log2n+1次。折半查找的时间复杂度为O(log2n)次。折半查找的前提：有序顺序存储。哈希散列表    散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0...n-1]（n<<m）中，这个区间就称为散列表，散列查找中使用的转换函数称为散列函数。例:记录关键码为(3,8,12,17,9)，取m=10(存储空间为10)，p=5，散列函数h=key%p。    开放定址法是指当构造散列表发生冲突时，使用某种探测手段，产生一个探测的散列地址序列，并且逐个查找此地址中是否存储了数据元素，如果没有，则称该散列地址开放，并将关键字存入，否则继续查找下一个地址。只要散列表足够大，总能找到空的散列地址将数据元素存入。排序算法插入类排序直接插入排序    即当插入第i个记录时，R1，R2，…，R1均已排好序，因此，将第个记录R依次与R1，…，R2，R1进行比较，找到合适的位置插入。它简单明了，但速度很慢。    直接插入排序是一种稳定的排序方法，时间复杂度为O(n2)。在排序过程中仅需要一个元素的辅助空间，空间复杂度为O(1)。    适用于基本有序的情况，此时时间复杂度近乎线性，即O(n)。希尔排序    先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 < d1重复上述的分组和排序，直至所取的增量d1=1(dt < dt-1 < O <> d2 < d1 )，即所有记录放在同组中进行直接插入排序为止。该方法实质上是一种分组插入方法。    希尔排序是一种不稳定的排序方法，据统计分析其时间复杂度约为O(n1.3)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(1)。选择类排序直接选择排序    直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依次类推，直到所有记录排完为止。    直接选择排序是一种不稳定的排序方法，其时间复杂度约为O(n2)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(1)。堆排序    堆排序的基本思想为：先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依此类推，直到所有元素均输出为止，此时元素输出的序列就是一个有序序列。    对于大量的记录来说，堆排序是很有效的。    堆排序的算法步骤如下（以大顶堆为例）:初始时将顺序表R[1...n]中元素建立为一个大顶堆，堆顶位于R[1],待序区为R[1...n]。循环执行步骤3~步骤4，共n-1次。假设为第i运行，则待序区为R[1..n-i+1]，将堆顶元素R[1]与待序区尾元素R[n-i+1]交换，此时顶点元素被输出，新的待序区为R[1...n-i]。待序区对应的堆已经被破坏，将之重新调整为大顶堆。    堆排序的时间复杂度为O(nlog2n)，空间复杂度为O(1)。交换类排序冒泡排序    冒泡排序的基本思想是，通过相邻元素之间的比较和交换，将排 序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底 下的气泡一样逐渐向上冒，因此称为冒泡算法。    冒泡排序是一种稳定的排序方法，其时间复杂度约为O(n2)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(1)。快速排序    快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组合成原问题的解。    在 O(nlog2n) 时间量级上，平均性能最好。    快速排序通常包括两个步骤：    第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。    第二步，采用相同的方法对左、右两组分别进行排序，直到所有记录都排到相应的位置为止。    快速排序的基准元素：一般是第一个元素，也可以设置中位数。    快速排序是一种不稳定的排序方法，平均和最优情况下时间复杂度约为O(log2n)。快速排序的最差情况-基本有序以第一个元素为基准元素，此时时间复杂度为O(n2)。以中位数为基准元素，此时时间复杂度为O(log2n)。辅助空间(1)需要辅助空间存储左侧数组和右侧数组时，空间复杂度为O(n)。(2)需要记录所有基准元素时，空间复杂度度为O(log2n)。归并排序    归并也称为合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。合并的过程是：比较A[i]和A[j]的排序码大小，若A[i]的排序码小于等于A[j]的排序码，则将第一个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到其中一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。    归并排序是一种稳定的排序方法，其时间复杂度约为O(nlog2n)。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(n)。基数排序    基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。    基数排序是一种稳定的排序方法，其时间复杂度约为O(d(n+rd))。在排序过程中仅需要一个元素的辅助空间用于数组元素的交互，空间复杂度为O(rd)。排序算法对比 类别 排序方法 时间复杂度 空间复杂度 稳定性 平均情况 特殊情况 辅助存储 插入排序 直接插入 O(n2) 基本有序最优O(n) O(1) 稳定 Shell排序 O(n1.3) - O(1) 不稳定 选择排序 直接选择 O(n2) - O(1) 不稳定 堆排序 O(nlog2n) - O(1) 不稳定 交换排序 冒泡排序 O(n2) - O(1) 稳定 快速排序 O(nlog2n) 基本有序最差O(n2) O(log2n) 不稳定 归并排序 O(nlog2n) - O(n) 稳定 基数排序 O(d(n+rd)) - O(rd) 稳定     在选取排序方法时需要考虑的因素有待排序的记录个数n、记录本身的大小、关键字的分布情况、对排序稳定性的要求、语言工具的条件和辅助空间的大小。据这些因素，可以得到以下几点结论：若待排序列的记录数目n较小，可采用直接插入排序和简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多，因而当记录本身信息量大时用简单选择排序方法较好。若待排记录按关键字基本有序，宜采用直接插入排序或冒泡排序。当n很大且关键字位数较少时，采用基数排序较好。若n很大，则应采用时间复杂度为0(nlog2n)的排序方法，例如快速排序、堆排序或归并排序：(1)快速排序目前被认为是内部排序中最好的方法，当待排序的关键字为随机分布时，快速排序的平均运行时间最短；(2)堆排序只需要一个辅助空间，并且不会出现在快速排序中可能出现的最快情况。(3)快速排序和堆排序都是不稳定的排序方法，若要求排序稳定，可选择归并排序。

第二章程序设计语言与数据结构 程序设计语言概述编译程序与解释程序编译与解释区别 编译型语言解释型语言 共同点高级程序语言 有词法分析、语法分析、语义分析过程 不同点翻译程序编译器解释器 翻译程序编译器解释器 是否生成目标代码生成目标代码不会生成目标代码 目标程序能够直接执行目标程序直接执行边解释边执行 翻译程序是否参与执行编译器不参与执行解释器参与执行 执行效率执行效率高执行效率低 灵活性与可移植性灵活性差，可移植性差灵活性好，可移植性强 编译器与解释器多种程序设计语言特点1. Fortran语言(科学计算，执行效率高) 2. Pasca语言(为教学而开发的，表达能力强，Delph) 3. C语言(指针操作能力强，高效) 4. Lisp语言(函数式程序语言，符号处理，人工智能) 5. C++语言(面向对象，高效) 6. Java语言(面向对象，中间代码，跨平台) 7. C#语言(面向对象，中间代码，Ne) 8. Prolog语言(逻辑推理，简洁性，表达能力，数据库和专家系统) 9. Python语言(解释型，面向对象，胶水语言)程序设计语言的基本成分常见数据类型数字数据类型布尔类型字符类型枚举类型指针类型程序控制结构顺序结构、选择结构、循环结构函数调用方式传值与传址传递方式主要特点传值调用形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变传址调用（引用调用）形参取的是实参的地址，即相当于实参存储单元的地址引用因此其值的改变同时就改变了实参的值函数调用传值调用： void swap(int x, int y) { int t; t = x; x = y; y = t; printf("%d %d,", x, y); } main() { int a = 3, b = 4; swap(a, b); printf("%d %d", x, y); } // 输出结果：4 3, 3 4传址调用： void swap(int *x, int *y) { int *t; *t = *x; *x = *y; *y = *t; printf("%d %d,", *x, *y); } main() { int a = 3, b = 4; swap(&a, &b); printf("%d %d", x, y); } // 输出结果：4 3, 4 3编译程序基本原理编译过程概述词法分析词法分析：从左到右逐个扫描源程序中的字符，识别其中如关键字(或保留字)、标识符、常数、运算符以及分隔符(标点符号和括号)等语法分析语法分析：根据语法规则将单词符号分解成各类语法单位，并分析源程序是否存在语法上的错误。包括:语言结构出错、if···end if不匹配，缺少分号、括号不匹配、表达式缺少操作数等自顶向下（或自上而下）分析法自底向上语法分析法（移进-归约分析法）语义分析语义分析：进行类型分析和检查，主要检测源程序是否存在静态语义错误。包括：运算符和运算类型不符合，如取余时用浮点数。错误管理动态错误发生在程序运行时也叫动态语义错误陷入死循环、变量取零时做除数、引用数组元素下标越界等错误静态错误编译时所发现的程序错误分为语法错误和静态语义错误语法错误包含：单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误静态语义分析：运算符与运算对象类型不合法等错误文法文法定义一个形式文法是一个有序四元组G=(V,T,S,P)，其中：1) V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符 2) T：终结符。是语言的组成部分，是最终结果。V∩T=ø 3) S：起始符。是语言的开始符号 4) P：产生式。用终结符替代非终结符的规则。形如α→β正则闭包:A+=A1∪A2∪A3∪…∪An∪···（也就是所有幂的组合）。闭包:A*=A0∪A+（在正则闭包的基础上，加上A0={ε}）例如a*={a,aa,a,···,ε}，而(ab)*={ab,abab,ababab,···,ε}类型别称说明对应自动机0型短语文法G的每条产生式α→β满足α属于V'的正则闭包，且至少含有一个非终结符，而β属于V'的闭包图灵机1型上下文有关文法G的任何产生式α→β满足|α|=|β|，仅仅S→ε例外，但S不得出现在任何产生式右部线性界线自动机2型上下文无关文法G的任何产生式为A→β，A为非终结符，β为V'的闭包非确定的下推自动机3型正规文法G的任何产生式为A→αB或A→α，a属于非终结符的闭包，A、B都属于非终结符有限自动机语法推导树正规式与正规集正规式正规式是描述程序语言单词的表达式，对于字母∑，其上的正规式及其表示的正规集可以递归定义如下①ε是一个正规式，它表示集合L(ε)={ε}②若a是Σ上的字符，则a是一个正则式，它所表示的正规L(a)={a}③若正规式r和s分别表示正规集L(r)=L(s)，则(a)r|s是正规式，表示集合L)UL(s)(b)r·s是正规式，表示集合L(r儿L(s);(c)r*是正规式，表示集合(L(r))*;(d)(r)是正规式，表示集合L(r)仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。由此可见，正规式要么为空，要么由字母、或、连接、闭包运算符组成。其中闭包运算符“*”具有最高的优先级，连接运算具有次高优先级，或运算符“|”具有最低优先级正规式正规集举例ab字符串ab构成的集合{ab}a|b字符串a、b构成的集合{a,b}a*由0或多个a构成的字符串集合{空,a,aa,aaa,a···a(n个a)}(a|b)*所有字符a和b构成的串的集合{空,a,b,ab,aab,abb,baa,aba,···}a(a|b)*以a为首字符的a、b字符串的集合{a,aa,ab,aab,aba,aaab,aaba,···}(a|b)*abb以ab结尾的a、b字符串的集合{abb,aabb, babb,abaabb,abaabb,···}有限自动机后缀表达式线性结构顺序表与链表线性表顺序存储方式数组的内存是连续分配的并且是静态分配的，即在使用数组之前需要分配固定大小的空间。链表(inked-list)存储方式链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的所有元素串起来。尾结点：最后一个有效结点首结点：第一个有效结点头结点：第一个有效结点之前的那个结点，存放链表首地址头指针：指向头结点的指针变量尾指针：指向尾结点的指针变量特点：①n个结点离散分布，彼此通过指针相联系②除头结点和尾结点外，每个结点只有一个前驱结点和一个后续结点。头结点没有前驱结点，尾结点没有后继结点③头结点并不存放有效数据，只存放链表首地址。其头结点的数据类型和首结点类型一样④加头结点的目的是方便对链表的操作，比如在链表头部进行结点的删除、插入链表的每个结点实际上是一个结构体变量,它有若干成员组成,包括数据部分和指针变量。链表单链表设单链表结点类型定义为：typede struct node{ int data; /*数据域*/ struct node *link; /*指针域*/ }NODE,*LinkList;在单链表p所指结点后插入新元素结点（s所指结点）①s>ink=p->link;②pnk=s;在单链表中删除p所指结点的后继结点①q=p->link;②p->link=p->link->link;③free(q);在单链表中删除p所指结点①p->data=p->link->data;②q=p->link;③p-link=p->link->link④free(a);双链表双向链表插入q所指向的结点①q->front=p;②q->next=p->next;③p->next->front=q;④p->next=q;双向链表删除结点p所指向的结点①p->front->next=p->next;②p->next->front=p->front;③free(p);顺序存储与链式存储对比性能类别具体项目顺序存储链式存储空间性能存储密度=1，更优<1空间性能容量分配事先确定动态改变，更优时间性能查找运算O(n)O(n)时间性能读运算O(1)，更优O(n)，最好情况为1，最坏情况n时间性能插入运算O(n)，最好情况为0，最坏情况nO(1)，更优时间性能删除运算O(n)O(1)，更优队列与栈习题：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。abc acb bac bca cba循环队列队空条件：head=tall队满条件：(tail+1)%size=head队列长度：(tail-head+size)%size循环队列（通过整数取余运算实现）串串的定义串是仅由字符构成的有限序列，是一种线性表。一般记为S="a1a2a3···an"，其中，S是串名，单引号括起来的字符序列是串值基本概念(1) 空串与空格串空串：长度为零，不包含任何字符。空格串：由一个或多个空格组成的串。虽然空格是一个空白字符，但它也是一个字符，在计算串长度时要将其计算在内。(2) 子串与子序列子串：由串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串。子串在主串中的位置是指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。子序列：一个串的“子序列”(subsequence)是将这个串中的一些字符提取出来得到一个新串并且不改变它们的相对位置关系。(3) 串比较与串相等串比较：两个串比较大小时以字符的ASCII码值(或其他字符编码集合)作为依据。实质上，比较操作从两个的第一个字符开始进行，字符的码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。串相等：指两个串长度相等且对应序号的字符也相同。基本操作(1)赋值操作 StrAssign(s,t)将串s的值赋给串t。(2)连接操作 Concat(s,t)将串接续在串s的尾部，形成一个新的串。(3)求串长 StrLength(s)返回串s的长度。(4)串比较 StrCompare(s,t)比较两个串的大小。返回值1、0和1分别表示s<t、s=t和s>t三种情况。(5)求子串 SubString(s,star,len)返回串S中从 start开始的、长度为len的字符序列。存储(1)顺序存储(2)链式存储模式匹配模式匹配：子串的定位操作通常称为串的模式匹配。(串也称为模式串)朴素的模式匹配算法(布鲁特福斯算法)其基本思想是从主串的第一个字符起与模式串的第一个字符比较，若相等，则继续逐一对字符迸行后续的比较，否则从主串第二个字符起与模式串的第一个字符重新比较，直到模式串中每个字符依次与主串中一个连续的字符序列相等时为止，此时称为匹配成功。如果不能在主串中找到与模式串相同的子串，则匹配失败。改进的模式匹配算法(KMP算法)其改进之处在于每当匹配过程中出现相比较的字符不相等时，不需要回退到主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。在KMP算法中，依据模式串的next函数值实现子串的滑动。若令next[j]=k，则next[j]表示当模式串中的p与主串中相应字符不相等时，令模式串的pnext[j]与主串的相应字符进行比较。（j=next[j]）next函数的定义如下：数组与矩阵数组数组类型存储地址计算一维数组a[n]a[i]的存储地址为：a+i*len二维数组amai的储存地址（按行存储）为：a+(i*n+j)*lenai的储存地址（按列存储）为：a+(j*m+i)*len矩阵稀疏矩阵示意图要点上三角矩阵在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为：(2n-i+1)×i/2+j下三角矩阵在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为：(i+1)×i/2+j对角矩阵矩阵中的非零元素都集中在以主对角线为中心的带状区域中。树树与二叉树的特性数转二叉树常见二叉树二叉树的重要特性在二叉树的第i层上最多有2i-1个结点(i≥1)；深度为k的二叉树最多有2k-1个结点(k≥1)；对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。如果对一棵有n个结点的完全二又树的结点按层序编号(从第1层到「Log2n」+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：如果i=1，则结点无父结点，是二叉树的根；如果i>1，则父结点是「i2」；如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；如果2i+1>n，则结点i无右子叶点，否则，其右子结点是结点2i+1。二叉树的遍历前序遍历：根-左-右中序遍历：左-根-右后序遍历：左-右-根层次遍历：按层次从左至右遍历图中的前序遍历、中序遍历、后序遍历、层次遍历前序：1-2-4-5-7-8-3-6中序：4-2-7-8-5-1-3-6后序：4-8-7-5-2-6-3-1层次：1-2-3-4-5-6-7-8二叉排序树也叫查找二叉树，二叉排序树要么是空二叉树，要么具有如下特点：二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；二叉排序树的左右子树也要求都是二叉排序树；如图为一个二叉排序树时间复杂度：最优时，即为完全二叉树或者满二叉树的时候，时间复杂度为O((log2n)+1)；最差的时候（但分支结构），时间复杂度为O(n)最优二叉树（哈夫曼树）路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径路径长度：在一条路径中，每经过一个结点，路径长度都要加 1结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积树的带权路径长度：树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 如图中所示的这颗树的带权路径长度为：WPL = 7 1 + 5 2 + 2 3 + 4 3哈夫曼树：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。例子：假设一个文本文件TFile中只包含7个字符{A，B，C，D，E，F，G}，这7个字符在文本中出现的次数为{5，24，7，17，34，5，13}，利用哈夫曼树可以为文件TFile构造出符合前缀编码要求的不等长编码图图的定义与存储图的基本概念完全图在无向图中，若每对顶点之间都有一条边相连,则称该图为完全图(complete graph)。在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图。连通图连通图：指任意两个顶点之间都有一个路径相连。图的存储-邻接矩阵用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素R定义为：图的存储-邻接表首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。图的遍历 遍历方法说明示例图例 深度优先1.首先访问出发顶点V2.依次从V出发搜索V的任意一个邻接点W;3.若W未访问过,则从该点出发继续深度优先遍历它类似于树的前序遍历。V1，V2，V4，V8，V5，V3，V6，V7  广度优先1.首先访问出发顶点V2.然后访问与顶点V邻接的全部未访问顶点W、XY…3.然后再依次访问W、X、Y…邻接的未访问的顶点;V1，V2，V3，V4，V5，V6，V7，V8 邻接表的方式拓扑排序我们把用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称AOV网络。上图的拓朴序列有:02143567,01243657,02143657,01243567最小生成树与最短路径问题（软考涉及少）最小生成树：对无向连通图的生成树，各边的权值总和称为生成树的权，权最小的生成树称为最小生成树。构成生成树的准则有三条：必须只使用该网络中的边来构造最小生成树。必须使用且仅使用n-1条边来连接网络中的n个顶点不能使用产生回路的边。克鲁斯卡尔算法：在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用（所选的边不能构成回路）的最小权植边。普里姆算法：普里姆算法是以其中某一顶点为起点，逐步寻找各个顶点上最小权值的边来构建最小生成树。其中运用到了回溯，贪心的思想。最短路径一批货物要从城市s发送到城市t，线条上的数字代表通过这条路的费用(单位为万元)。那么，运送这批货物，至少需要花费多少元？迪杰斯拉算法：是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。都用到了贪心算法策略

第一章计算机组成与体系结构 数据的表示码制原码：最高位是符号位，其余低位表示数值的绝对值反码：整数的反码与原码相同，负数的反码是其绝对值按位取反补码：正数的补码与原码相同，负数的补码是其反码末位加1（符号位不变）移码：补码的符号位按位取反码制定点整数定点小数数码个数原码-(2n-1-1)~+(2n-1-1)-(1-2-(n-1))~+(1-2-(n-1))2n-1反码-(2n-1-1)~+(2n-1-1)-(1-2-(n-1))~+(1-2-(n-1))2n-1补码-2n-1~+(2n-1-1)-1~(1-2-(n-1))2n移码-2n-1~+(2n-1-1)-1~(1-2-(n-1))2n注意人为规定浮点数表示：N = 尾数 * 基数 指数 （指数也叫阶码）运算过程：对阶 > 尾数计算 > 结果格式化特点：一般尾数用补码，阶码用移码阶码的尾数决定书的表示范围，尾数越多范围越大位数的位数决定数的有效精度，尾数越多精度越高对阶时，小数向大数看齐对阶是通过较小的尾数右移实现的逻辑运算关系运算符优先级相同（高）：<、<=、>、>=优先级相同（低）：==、!=说明：关系运算符的优先级低于算术运算符关系运算符的优先级高于赋值运算符逻辑运算逻辑或（||、+、∪、∨、OR）：连接的两个逻辑值全0时才取0 遇真则真逻辑与（&&、*、·、∧、AND）：连接的两个逻辑值全1时才1 遇假则假逻辑异或（⊕、XOR）：连接的两个逻辑值不相同时取1，相同取0逻辑非（!、¬、~、NOT、ˉ）：将原逻辑取反ABA+BA*BA⊕B!A000001011011100100110110逻辑运算符&& (逻辑与) 相当于其他语言中的AND|| (逻辑或) 相当于其他语言中的OR! (逻辑非) 相当于其他语言中的NOT运算符的优先顺序：!>算术运算符>关系运算符>&&>!!>赋值运算符短路原则在逻辑表达式的求解中，并不是所有的逻辑运算符都要被执行。(1) a&&b&&c 只有a为真时，才需要判断b的值，只有a和b都为真时，才需要判断c的值(2) a||b||c 只要a为真，就不必判断b和c的值，只有a为假，才判断b，a和b都为假才判断c校验码奇偶校验码码距任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。奇偶校验奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制（校验位）组成校验码。奇校验：整个校验码（有效信息位和校验位）中"1"的个数为奇数。偶校验：整个校验码（有效信息位和校验位）中"1"的个数为偶数。特点：可检错不可纠错循环校验码CRCCRC的编码方法:在k位信息码之后拼接r位校验码。应用CRC码的关键是如何从k位信息位简便地得到r位校验位(编码)，以及如何从k+r位信息码判断是否出错。特点：可检错不可纠错把接收到的CRC码用约定的生成多项式G(X)去除(模二除法)，如果正确，则余数为0如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有惟一的对应关系。海明校验码海明校验码的原理在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据特点：可检错也可纠错校验码比较 校验码位数校验码位置检错纠错校验方式奇偶校验1一般拼接在头部可检奇数位错不可纠错奇校验：最终1的个数是奇数个；偶校验：最终1的个数是偶数个；CRC循环冗余检验生成多项式最高次幂决定拼接在信息位尾部可检错不可纠错模二除法求余数，拼接作为校验位海明校验2r-1>=m+r插入在信息位中间可检错可纠错分组奇偶校验CPU组成（运算器与控制器）运算器算术逻辑单元ALU：数据的算术运算和逻辑运算累加寄存器AC：通用寄存器，为ALU提供一个工作区，用在暂存数据数据缓冲寄存器DR：写内存时，暂存指令或数据状态条件寄存器PSW：存状态标志与控制标志(争议：也有将其归为控制器的)控制器程序计数器PC：存储下一条要执行指令的地址指令寄存器|R：存储即将执行的指令指令译码器ID：对指令中的操作码字段进行分析解释时序部件：提供时序控制信号寻址方式立即寻址方式：操作数直接在指令中，速度快，灵活性差直接寻址方式：指令中存放的是操作数的地址间接寻址方式：指令中存放了一个地址，这个地址对应的内容是操作数的地址寄存器寻址方式：寄存器存放操作数寄存器间接寻址方式：寄存器内存放的是操作数的地址CISC与RISC指令系统类型指令寻址方式实现方式其他CISC（复杂）数量多，使用频率差别大，可变长格式支持多种微程序控制技术（微码）研制周期长RISC（简单）数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/ Store操作内存支持方式少增加了通用寄存器；硬布线逗辑控制为主；适合采用流水线优化编译，有效支持高级语言比较CISC：复杂，指令数量多，频率差别大，多寻址RISC：精简，指令数量少，操作寄存器，单周期，少寻址，多通用寄存器，流水线流水线技术概念流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度流水线计算流水线周期为执行时间最长的一段第一条指令执行时间也是流水线建立时间公式：1条指令执行时间 + (指令条数 - 1) * 流水行周期理论公式：(t1 + t2 +···+ tk) + (n-1) * t实践公式：k t + (n - 1) t注意：优先用理论公式进行计算，若选项中没有理论公式计算答案则用实践公式进行计算示例：一条指令的执行过程可以分解为取指、分析和执行三步，在取指时间t=3△t、分析时间t分=2△t、执行时间轨执行4△t的情况下，若串行方式执行，则10条指令全部执行完需要(90)△t;若按流水线的方式执行，流水线周期为(4)△t，则10条指令全部执行完需要(45)△t。流水线吞吐率计算流水线的吞吐率（Thouph Putrate，TP）是指在单位时间内流水线所完成的任务数量或输出的结果数量。基本公式:$$TP = \frac{指令条数}{流水线执行时间}$$流水线最大吞吐率：$$TP_{max} = \lim_{n\to ∞}\frac{n}{(k+n-1)t} = \frac{1}{t}$$存储系统层次化存储结构三层存储结构是高速缓存(ache)、主存储器(MM)和辅助存储器(外存储器)。若将CPU内部寄存器也看作是存储器的一个层次，那么存储器的层次分为四层。若有些计算机没有高速缓存，那么存储器的层次分为两层，即只有主存和辅存。局部性原理是层次化存储结构的支撑时间局部性：刚被访问过的内容，立即又被访问空间局部性：刚被访问过的内容，邻近的空间很快被访问层次化存储结构-分类存储器位置内存&外存存取方式(1) 按内容存取：相联存储器（如Cache）(2)按地址存取：随机存取存储器（如内存）顺序存取存储器（如磁带）直接存取存储器（如磁盘）工作方式随机存取存储器RAM（如内存DRAM）只读存储器ROM（如BIOS）DRAM：动态随机存取存储器SRAM：静态随机存取存储器Cache：高速缓存EEPROM：电可擦可编程只读存储器Cache概念在计算机的储存系统体系中，Cache是访问速度最快的层次（若有存储器，则存储器最快）。使用Cache改善系统性能的依据是程序的局部性原理。如果以h代表对Cache的访问命中率，t1表示Cache的周期时间，t2表示主存储器周期时间，以读操作为例，使用“Cache+主存储器”的系统的平均周期为t3，则:$$ t_3 = h×t_1 + (1-h) x t_2 $$其中，(1-h)又称为失效率(未命中率)。地址映像方式直接相联映像：硬路电路较简单，但冲突率很高。全相联映像：电路难于设计和实现，只适用于小容量的 cache，冲突率较低。组相联映像：直接相联与全相联的折中注：主存与Cache之间的地址映射由硬件直接完成地址映像是将主存与Cache的存储空间划分为若干大小相同的页(或称为块) 冲突率电路复杂度直接相联映像高简单全相联映像低复杂组相联映像中折中主存编址计算存储单元：存储单元个数 = 最大地址 - 最小地址 + 1编址内容按字编址：存储体的存储单元是字存储单元，即最小寻址单位是一个字按字节编址：存储体的存储单元是字节存储单元，即最小寻址单位是个字节总容量 = 存储单元个数 * 编址内容根据存储器所要求的容量和选定的存储芯片的容量，就可以计算出所需芯片的总数，即总片数 = 总容量 / 每片的容量输入输出技术数据传输控制方式程序控制（查询）方式：分为无条件传送和程序查询方式两种。方法简单，硬件开销小，但I/O能力不高，严重影响CPU的利用率。程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。DMA方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效。(DMAC向总线裁决逻辑提出总线请求；CPU执行完当前总线周期即可释放总线控制权。此时DMA响应，通过DMAC通知I/O接口开始DMA传输。)通道方式I/O处理机中断处理过程：CPU无需等待也不必查询O状态当I/O系统准备好以后,发出中断请求信号通知CPUCPU接到中断请求后,保存正在执行程序的现场(保存现场)打断的程序当前位置即为断点(通过中断向量表)转入I/O中的服务程序的执行,完成系统的数据交换;返回被打断的程序继续执行(恢复现场)。总线一条总线同一时刻仅允许一个设备发送，但允许多个设备接收总线的分类：数据总线( Data Bus)：在CPU与RAM之间来回传送需要处理或是需要储存的数据地址总线( Address Bus)：用来指定在RAM( Random AccessMemory)之中储存的数据的地址。控制总线( Control Bus)：将微处理器控制单元( Control Unit)的信号，传送到周边设备。可靠性系统可靠性分析 - 可靠性指标平均无故障时间 → (MTTF)MITF = 1 / λ，λ为失效率平均故障修复时间 → (MTTR)MTTR = 1/μ，μ为修复率平均故障问隔时间 → (MTBF)MTBF = MTTR + MTTF系统可用性 → MTTF / (MTTR + MTTF) × 100%在实际应用中，一般MTTR很小，所以通常认为MTBF ≈ MTTF可靠性可以用可以用MTTF/(1+MTF)来度量如果用M表示可维护性指标，那么M=1/(1+MTTR)串联系统与并联系统N模混合系统性能指标平均每条指令的平均时钟周期个数(CPl, clock per instruction)每(时钟)周期运行指令条数(IPC, instruction per clock)百万条指令每秒(MIPSS, Million Instructions Per Second)每秒百万个浮点操作( MFLOPS, Million Floating-point Operations per Second)响应时间(RT, Response Time)