自考数据结构-串讲笔记

《自考数据结构-串讲笔记》由会员分享，可在线阅读，更多相关《自考数据结构-串讲笔记（210页珍藏版）》请在装配图网上搜索。

1、自考数据结构自考数据结构 串讲笔记串讲笔记自考乐园版自考乐园版 课程代号：课程代号：02331课程说明课程说明串讲目的串讲目的参考教材：参考教材：数据结构黄刘生主编经济科学出版社更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、数据：、数据：能输入计算机并能计算机程序处理的符号的总称。2 2、数据元素：、数据元素：数据的基本单位。可以进一步细分为若干数据项，数据项是最小单位，不能再细分。3 3、数据对象：、数据对象：具有相同性质的数据元素的集合，是数据的一个子集。4 4、（1 1）数据的逻辑结构：）数据的逻辑结构：数据之间的关系。数据之间的关系。A.A.集合（无顺序）：集合（无顺序

2、）：B.B.线性结构（一对一）：线性结构（一对一）：C.C.树形结构（一对多）：树形结构（一对多）：D.D.网状、图结构（多对多）：网状、图结构（多对多）：（）数据的存储结构（物理结构）（）数据的存储结构（物理结构）数据结构在计算机中的表示。（种）A.A.顺序表示顺序表示借助数据在连续连续的存储空间中的相对位置表示元素关系。B.B.链式表示链式表示借助数据元素的存储地址的指针指针表示元素关系。2.2.算法和算法分析算法和算法分析一、算法一、算法定义：定义：是对特定问题求解步骤的一种描述，是指令的有限序列。特点：特点：有穷性确定性可行性零个或多个输入一个或多个输出大大O O表示法表示法大O表示同

3、级别例：f(n)=n2,f(n)=1/2(n(n-1),f(n)=(n-1)(n+2)均表示为：O(n2)加法规则：若T1(n)=O(f1(n),T2(n)=O(f2(n)则两段程序连在一起的时间代价为:T(n)=T1(n)+T2(n)=O(max(f1(n),f2(n)例例:语句段语句段 频度频度f(n)f(n)时间复杂度时间复杂度T(n)T(n)x=x+11O(1)for(j=1;j=3n+5;j+)3n+5O(n)x=x+1;for(i=1;i=3n;i+)3n2O(n2)for(j=1;j=n;j+)x=x+1;i=0;n+1O(n)while(x!=ai&i=n)i=i+1;求时间复

4、杂度的原则求时间复杂度的原则当重复执行次数与输入有关时,计算平均值。平均复杂度不易求时,讨论最坏情况下的T(n)。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ n增大增大,T(n)T(n)增加快增加快,算法坏算法坏随问题规模随问题规模n n增大增大,T(n)T(n)趋缓趋缓,算法好算法好T(n)T(n)的增大趋势的增大趋势:O(1)O(log2n)O(n)O(nlog2n)O(n2)O(nk)O(2n)O(en)0时，线性表中各元素都有确定序号线性表中各元素除第一个元素没有前驱、最后一个元素没有后继外，均具有唯一的前驱、后继元素（a a1 1,a,a2 2,a,ai-1i-1,a,

5、ai i,a,ai+1i+1,a,an n)无前驱无前驱直接前驱直接前驱直接后继直接后继无后继无后继第二章线性表第二章线性表2.2.线性表的顺序存储结构线性表的顺序存储结构一、线性表的顺序存储一、线性表的顺序存储在计算机内开辟一片连续连续空间（存储单元）依次存放表中所有元素。设线性表为A（a1,a2,ai,an），表中的一个元素占用L个存储单元，第一个元素a1的起始地址是Loc(a1)，则第i个元素的起始地址为：Loc(ai)=Loc(a1)+(i-1)Loc(ai)=Loc(a1)+(i-1)*L La1 a2 ai an连续空间连续空间3.3.线性表的链式存储结构线性表的链式存储结构一、单

6、链表一、单链表定义定义：存储空间上一个结点对应线性表上一个元素，结点分为两个字段（或两个域）。一个字段存放元素的数据值；另一个字段存放指针，指向后继元素。结点：结点：DataPointer两个概念：两个概念：头指针头指针：指示链表中第一个结点。头结点头结点：在第一个结点之前附设的结点，其指针域指向链表中第一个结点。在链表中第i个结点前插入新结点b（前插）算法分析：算法分析：基本操作：查找第i-1个元素当1in 频度为：i-1当in(最坏，即i不合法)频度为：nT(n)=O(n)二、循环链表二、循环链表特点特点尾结点的next指针指向头结点，可以设头结点和尾结点指针。优点优点可迅速找到头、尾结点

7、。a1 an HeadHead空表空表三、双向链表和双向循环链表三、双向链表和双向循环链表特点：特点：在结点中增加一个指向前趋的指针域。优点：优点：可迅速找到结点前趋。缺点：缺点：增加存储空间。（每个结点增加了一个指针域）双向链表双向链表a1a2双向循环链表双向循环链表a2a12 2、基本操作、基本操作（1 1）插入）插入：在链表的x结点前插入元素e步骤：步骤：a.在链表中查找x结点b.申请结点空间s，s-data=ec.先做s-prior=p-prior;p-prior-next=s;d.后做s-next=p;p-prior=s;axpes（本章结束）（2 2）删除）删除：删除双向循环链表中

8、的结点x步骤：步骤：a.在链表中查找x结点b.删除：p-prior-next=p-next;p-next-prior=p-prior;c.free(p)axcp第第3 3章栈与队列章栈与队列1.1.栈栈一、栈的描述一、栈的描述1.1.栈的定义栈的定义2.2.栈的特点栈的特点：后进先出（后进先出（LIFOLIFO）1,2,3,41,2,3,4顺序进栈，有多少种出栈的情况？顺序进栈，有多少种出栈的情况？S Sn n=s=s0 0s sn-1n-1+s+s1 1S Sn-2n-2+s+sn-2n-2s s1 1+s+sn-1n-1s s0 0S S0 0=1,s=1,s1 1=1=1更多优质自考资料

9、尽在百度贴吧自考乐园俱乐部（http:/ 1、栈的顺序存储结构、栈的顺序存储结构顺序栈顺序栈顺序栈：顺序栈：开辟一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素。设top指针指示栈顶元素的当前位置。基本操作基本操作栈示意图栈示意图：CBAbasetop新元素入栈顶时：先入栈,再移指针top=top+1删除元素时：先移指针top=top-1,后删栈顶元素 栈的长度：top-base2 2、链栈、链栈定义：定义：采用链式存储结构的栈，并由其栈顶指针惟一确定。设ls为栈顶指针，栈=(a1,a2,an)，a1为栈底元素，an为栈顶元素。an a2 a1 ls最迟入栈元最早入栈元2.2.队列队列一

10、、队列描述一、队列描述1 1、队列定义、队列定义2 2、队列特点：、队列特点：先进先出（先进先出（FIFOFIFO）二、队列的顺序存储表示二、队列的顺序存储表示1 1、顺序队列、顺序队列用一组地址连续的存储单元依次存放从队头到队尾的元素。设队头指针为front，队尾指针为rear。约定：当front=rear=0，表示空队列；front指向队头元素；rear指向队尾元素的下一个位置。2 2、循环队列、循环队列假想：假想：将队列的头、尾相连形成一个环，构成循环队列。并引入数学中的模运算计算队头和队尾指针。frontrearMaxsize-10基本操作：基本操作：入队操作：入队操作：Q.baseQ

11、.rear=x;Q.rear=(Q.rear+1)%MAXQSIZE;出队操作：出队操作：x=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;问题：问题：循环队列的队空、队满条件？循环队列的队空、队满条件？举例说明：举例说明：矛盾：矛盾：对空：对空：front=rear队满：队满：front=rear解决方法：解决方法：少用一个存储空间矛盾三、链队列三、链队列定义：定义：用链表示的队列简称为链队列。设两个指针front、rear分别指示队头和队尾。为了链队列的操作方便，增加一个头结点，front指向头结点，rear指向队尾元素。如图所示：a1 an fro

12、nt队头元素队尾元素rear头结点3.3.递归算法设计递归算法设计一、递归算法设计一、递归算法设计递归过程：递归过程：一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程称为递归过程。直接递归调用间接递归调用1 1、递归算法的设计思想、递归算法的设计思想分治思想：分治思想：对一个较大问题可分解成属性相同、规模较小的问题，在小问题求解之后，通过组合，求得原来较大问题的解。递归定义：递归定义：基本项：基本项：描述递归过程的终结状态，即可直接求解状态。归纳项：归纳项：描述如何实现从当前状态到终结状态的转化，即子问题与原问题之间的转化。例例1 1：求：求n!n!用分治思想分析,得到递归定义:

13、基本项：基本项：当n=1时，f=1。（直接求解状态）归纳项：归纳项：如果能求得(n-1)!，原问题n!则迎刃而解。(n-1)!与n!问题的属性特征相同，只是规模小了。所以，归纳项是设法求(n-1)！。2 2、递归算法设计、递归算法设计在程序设计中，什么情况下使用递归算法进行程序设计呢？在程序设计中，什么情况下使用递归算法进行程序设计呢？考虑考虑以下三个方面的因素：以下三个方面的因素：当问题的定义是递归的解决问题的数据结构是递归的解决问题的过程是递归的（本章结束）更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、串定义、串定义：有零个或：有零个或n n个字符构成的有限序列。个字符构成

14、的有限序列。记为S=a1a2an(n=0);其中S是串名,a1a2.an是串值，ai(i=1)可以是字母、字符、数字，n是串长度，当n=0时为空串。2 2串的存储结构串的存储结构一、顺序存储结构一、顺序存储结构（或称静态存储结构：编译时进行空间分配）定义：定义：用一组地址连续地址连续的存储单元存储串的字符序列。两种编址形式：两种编址形式：字节编址：字节编址：一个字节字节存一个字符。(如早期的pc机)字编址：字编址：一个字字存一个字符。非紧缩格式：非紧缩格式：每个字存放一个字符。紧缩格式：紧缩格式：每个字节存放一个字符。C C语言仅有紧缩格式：语言仅有紧缩格式：char strmax;char

15、strmax;概念：存储密度概念：存储密度存储密度存储密度=串值所占的存储位实际分配的存储位顺序存储结构的特点顺序存储结构的特点预先分配串最大长度，有可能造成存储密度低。使串的某些操作受到很大限制。如置换、联接等操作。二、动态存储结构二、动态存储结构（在运行时进行存储空间的分配）定义：定义：用一组任意的存储单元（可以连续，可以不连续）存放串的字符序列。1 1、链式存储结构、链式存储结构每个结点存放一个字符。图示：图示：存储密度=1/(1+4)=20%(设指针占用4字节)特点：特点：密度低，存储空间利用率低，操作简单。每个结点存放多个字符块链结构。图示：图示：存储密度=4/(4+4)=50%(设

16、指针占用4字节)特点：特点：存储密度大，节省空间，操作复杂。链式结构的特点：结点的选择非常重要。a b c rear a b c d e f g h i#3 3串的模式匹配算法串的模式匹配算法模式匹配：模式匹配：子串的定位操作通常称为串的模式匹配，是各种串处理系统中重要的操作之一。Index(S,T,pos)其中S为主串，T被称为模式串。模式串。若T为S子串，则返回T在S中第pos个字符后首次出现的位置。若T不为S子串，则返回0。模式匹配模式匹配：子串在主串中的定位操作(mT0时说明匹配成功。匹配成功的返回值：T中第一个字符在S中的位置。（本章结束）第五章数组和广义表第五章数组和广义表1.1.

17、数组定义数组定义一、数组定义（一、数组定义（n n维数组）维数组）当n=1时，称为一维数组。当n2时，称为多维数组。一个n维数组是由若干个n-1维数组构成的。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ m*n na11 a12 a1na21 a22 a2n.am1 am2 amn可以看成由若干个一维数组组成，这些一维数组或按行或按列向量构成可以看成由若干个一维数组组成，这些一维数组或按行或按列向量构成Am*n=按列向量：按列向量：a11 a12 a1na21 a22 a2n.am1 am2 amnAm*n=n n个一维数组个一维数组按行向量：按行向量：a11 a12 a1n a2

18、1 a22 a2n .am1 am2 amnAm*n=(a11 a12a1n),(a21 a22a2n),(am1 am2 amn)Am*n=m m个一维数组个一维数组2.2.数组的顺序存储表示数组的顺序存储表示问题：问题：存储单元是一维的结构，而数组是多维结构，如何用一组连续存储空间存放数组的数据元素呢？解决方法：解决方法：存储映射策略；行优先存储；列优先存储。数组元素满足1=i=m,1=j=n设每个数据元素占L个存储单元，第一个元素a00存储地址是Loc(a00)，问aij在空间上的存储地址是什么？1 1、行优先存储、行优先存储 Loc(aij)=Loc(a00)+(i*n+j)*La00

19、a01a0n-1am-10am-1n-1nL假设：行、列的下界为假设：行、列的下界为0Loc(a00)2 2、列优先存储、列优先存储 Loc(aij)=Loc(a00)+(j*m+i)*La00a10am-10a0n-1am-1n-1mL假设：行、列的下界为假设：行、列的下界为0Loc(a00)3.3.矩阵的存储及运算矩阵的存储及运算一、一般矩阵的存储一、一般矩阵的存储通常用二维数组存储矩阵。特点：特点：矩阵中的每个元素占用二维数组中的相应位置。二、特殊矩阵的存储二、特殊矩阵的存储特殊矩阵：特殊矩阵：矩阵中相当一部分元素取值相同或都为0或元素在矩阵中分布有一定规律。特殊矩阵的存储方式：通常采用

20、压缩存储。压缩存储：压缩存储：为多个值相同的矩阵元只分配一个存储空间；对0元不分配空间。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 1、对称矩阵、对称矩阵定义：定义：对于一个n*n方阵，且aij=aji（1=i=n,1=j=j1/2j(j-1)+(i-1)i=j1/2n(n+1)i0时，1,2,n是满足线性有序关系的，且i可以是某一数据对象元素，也可以是一个表结构。前者称为原子原子，后者称为子表子表。（在表示习惯上，广义表名称用大写字母表示，原子用小写字母表示）特点：特点：广义表的结构是递归的。举例：举例：广义表广义表表长表长LS1=()n=0(空表)LS2=(a)n=1(只有原

21、子)LS3=(a,(b)n=2LS4=(a,b)n=2LS5=(a,(b,(c)n=2F=(a,F)n=2(递归表)广义表的术语：广义表的术语：当广义表非空时：(1)广义表的表头表头：表中第一个元素；(2)广义表的表尾表尾：除了表头之外，表中其余元素构成的子表。特点：特点：表头可以是原子或子表，而表尾一定是子表。举例：举例：LS=(a,b),c)Head:(a,b)Tail:(c)LS=(a)Head:aTail:()空表LS=(),(e),(a,(b,c,d)Head:()Tail:(e),(a,(b,c,d)广义表运算：设广义表LS=(1,2,n)取广义表表头Head(LS)=1取广义表表

22、尾Tail(LS)=(2,n)二、求广义表深度二、求广义表深度1 1、广义表深度定义：、广义表深度定义：广义表括号重数例：LS=()深度：1LS=()深度：2LS=(a)深度：1LS=(a,(b,c)深度：2例：求例：求E=(A,B,C)E=(A,B,C)的深度的深度其中：A=(),B=(e),C=(a,(b,c,d)解：Depth(E)=1+maxDepth(A),Depth(B),Depth(C)Depth(A)=1Depth(B)=1+maxDepth(e)=1Depth(C)=1+max(Depth(a),Depth(b,c,d)Depth(a)=0Depth(b,c,d)=1+max

23、Depth(b),Depth(C),Depth(d)=1Depth(C)=1+max0,1=2 Depth(E)=1+max1,1,2=3 3（本章结束）第六章树第六章树树的定义和术语树的定义和术语一、树的定义一、树的定义二、树的术语二、树的术语结点度、树的度、结点层次、树的深度、家族树、有序树。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 2二叉树二叉树一、二叉树的相关概念一、二叉树的相关概念1 1、二叉树定义、二叉树定义树中每个结点至多有两棵子树，且子树有序。（根据二叉树的定义，二叉树的结构是递归的）2 2、二叉树的基本形态、二叉树的基本形态二叉树有五种基本形态：二叉树的基本形

24、态：左子树右子树右子树左子树（1）空二叉树（2）只有一个根结点（3）有根结点和左子树（4）有根结点和右子树（5）有根结点和左，右子树二、二叉树的性质二、二叉树的性质1 1、二叉树、二叉树性质性质1 1：第i层上最多有2i-1个结点。性质性质2 2：深度为K的二叉树最多有2K-1个结点。性质性质3 3：设叶子（度为0）数为n0，度为2的结点数为n2，则n0=n2+1。2 2、满二叉树与完全二叉树、满二叉树与完全二叉树满二叉树：深度为k，且有2k-1个结点。（对满二叉树中的结点约定编号：自根起，从上到下，从左到右）完全二叉树：仅允许最下层右侧分支不满，若按从上到下，从左到右为树中结点编号，则与满二

25、叉树相同。关系：关系：满二叉树是完全二叉树。完全二叉树不一定是满二叉树。3 3、完全二叉树性质、完全二叉树性质性质性质4 4：n个结点，深度为K的完全二叉树，其K=log2n+1性质性质5 5：对一棵n个结点深度为K的完全二叉树上的结点按层次编码（从第一层到第K层，从左到右），则树中编号为i的结点(1=i1时，i的双亲是 i/2；c:当2in时，i是叶点（无左孩子）；当2in时，i结点无右孩子；当2i+1=n时，2i+1是i的右孩子。三、二叉树存储结构三、二叉树存储结构1 1、顺序存储结构、顺序存储结构用一维数组A作为二叉树的存储结构，Ai表示编号为i的结点。ABC125 A B C .012

26、34A特点：浪费存储空间特点：浪费存储空间特例：特例：123K深度为K，只有K个结点的单支树需要2K-1个存储单元。（由二叉树的性质2知，深度为K的二叉树至多有2K-1个结点）。而真正有用的只有K个空间，其它绝大多数空间是空闲的。造成了存储空间的极大浪费。顺序存储结构适用于完全二叉树：顺序存储结构适用于完全二叉树：特点：特点：即不浪费空间，又可以快速确定其结点的位置；对已知的结点i，其左孩子为2i，右孩子为2i+1，双亲为 i/2 。DBACEF123456 A B C D E F 012346A完全二叉树完全二叉树结点在存储空间中的相对位置恰好表现出了完全二叉树中结点之间的关系。2 2、链式

27、存储结构、链式存储结构二叉链表：二叉链表：链表中每个结点至少含有三个域：数据域、左指针域和右指针域。lchildDatarchild指向左孩子指向左孩子指向右孩子指向右孩子3 3二叉树的遍历二叉树的遍历一、遍历二叉树一、遍历二叉树遍历：遍历：按一定次序访问二叉树上每个结点恰一次；访问：访问：访问代表一次操作；访问次序：访问次序：先左后右。并以访问根的次序不同分为不同的三种方式：先序、中序、后序。先序：先序：先访问根结点，然后访问左子树，再访问右子树。中序：中序：先访问左子树，然后访问根结点，再访问右子树。后序：后序：先访问左子树，然后访问右子树，再访问根结点。例例1 1：KBDEHCGIJAF

28、先序：先序：A ABCDEFGBCDEFGHIJKHIJK中序：中序：CEDFBGCEDFBGA AIKJHIKJH后序：后序：EFDCGBEFDCGBKJIHKJIHA A例例2 2：已知先序、中序可以惟一确定一棵二叉树：已知先序、中序可以惟一确定一棵二叉树已知：中序：GDHBGDHBA AECIFECIF先序：A ABDGHBDGHCEFICEFIAIFECIFABCEGDHGDHBFABCEDGHI例例3 3：已知中序、后序可以惟一确定一棵二叉树：已知中序、后序可以惟一确定一棵二叉树已知：中序：DBGEDBGEA AHFICHFIC后序：DGEBDGEBHIFCHIFCA AAHIFCD

29、BGEHIFABCDGEFABCIDGEH例例4 4：已知先序、后序：已知先序、后序不能不能惟一确定一棵二叉树惟一确定一棵二叉树已知：先序：A B后序：B AABAB两棵不同的二叉树两棵不同的二叉树以中序为例讨论二叉树的递归遍历算法：以中序为例讨论二叉树的递归遍历算法：中序遍历二叉树的递归算法分析：中序：中序：访问左子树 访问根 访问右子树基值：基值：bt=NULL(bt为二叉树的根结点指针)。当二叉树为空时。归纳项：即是对子树（子树仍为二叉树）的遍历操作。算法思想：算法思想：若二叉树为空，则遍历结束；否则遍历左子树访问根结点遍历右子树中序递归算法执行过程的简化展开图：中序递归算法执行过程的简

30、化展开图：每深入一层代表一次调用；退上一层代表一次返回；从左子树返回仅一层；接着访问根结点；从右子树返回，表明当前层遍历结束，可以连续返回。ABFCDEGH二、线索二叉树二、线索二叉树1 1、什么是二叉树的线索化？、什么是二叉树的线索化？非线性结构的二叉树经过遍历（先序、中序、后序），结点排成线性有序（前趋、后继惟一）。但二叉树本身不具有这种信息，访问后即消失；为了保持在遍历过程中得到的前趋、后继信息，则需边遍历，边建立线索。线索：即是指向前趋、后继结点的指针。线索二叉树：加上线索的二叉树称为线索二叉树。线索化：对二叉树进行遍历使其成为线索二叉树的过程称为二叉树的线索化。更多优质自考资料尽在百

31、度贴吧自考乐园俱乐部（http:/ 2、怎样线索二叉树、怎样线索二叉树(1)(1)增加两个标志位增加两个标志位每个标志位仅占1个存储位(bit)结点结构：若LTag=0(Link),则lchild指向左孩子；RTag=0(Link),则rchild指向右孩子；若LTag=1(Thread),则lchild指向线索前趋；RTag=1(Thread),则rchild指向线索后继。lchildLTagdataRTagrchild带头结点的中序线索链表：带头结点的中序线索链表：10A00B01F01C00E11D11G11二叉树的头指针二叉树的头指针Head4 4树和森林的存储与运算树和森林的存储与运

32、算一、树的存储表示一、树的存储表示1 1、双亲表示法、双亲表示法（顺序存储结构）开辟一组连续空间存储树的结点，每个结点中附设一个指示双亲结点的双亲域。CBADEABCDE-1 0003Data:Parent:特点：找结点双亲容易，但找孩子不容易特点：找结点双亲容易，但找孩子不容易012 342 2、孩子表示法（、孩子表示法（链式存储结构）(1)按树的度设结点指针域特点：特点：每个结点的结构一致，操作简单，但浪费存储空间。CBADEAB C D E 树的度树的度=3=3(2)按结点的度设结点指针域特点：特点：每个结点的结构不一致，操作复杂，但节省存储空间。CBADEAB 0C 0D 13E 0(

33、3)按孩子结点排成线性表特点：特点：节省空间，操作也较容易；问题：问题：这种结构不能反映出树的层次性特征。ABCDECBADE2354每个结点的孩子链表每个结点的孩子链表123453 3、孩子兄弟表示法（二叉树表示法）、孩子兄弟表示法（二叉树表示法）在这种表示法中，树中每个结点有三个域：数据域：存放结点数据左指针域：指向该结点的第一个孩子结点右指针域：指向该结点的右兄弟结点datafchnsib特点：特点：便于实现树的各种操作，节省空间，并且能够描述树的层次结构。CBADEA B CD E 二、森林与二叉树的转换二、森林与二叉树的转换二叉树和树都可以用二叉链表作为其存储结构。因此，以二叉链表作

34、为中间媒介，可以导出树与二叉树之间存在对应关系。一棵树与惟一的一棵二叉树一一对应。一棵树与惟一的一棵二叉树一一对应。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ B CD E A B CD E CBADE树树二叉树二叉树二叉树表示法二叉树表示法二叉链表二叉链表1 1、树转换成二叉树、树转换成二叉树保持双亲和第一个孩子连线，其他连线去掉；兄弟之间连线；使右兄弟结点成为右孩子，使第一个孩子成为左孩子。2 2、森林转换为二叉树、森林转换为二叉树将每棵树转化为二叉树；将各棵二叉树的根相连；使二叉树的根成为右孩子。3 3、二叉树转换成森林、二叉树转换成森林若某结点是其父结点的左孩子，则把该结

35、点的右孩子、右孩子的右孩子、，都与该结点的父结点用线线连；去掉树中所有父结点到其右孩子的连线，生成森林。三、树与森林遍历三、树与森林遍历1 1、树的遍历、树的遍历遍历规则遍历规则：(1)(1)先根遍历：先根遍历：先访问树根，再依次先根遍历根的每棵子树。(2)(2)后根遍历：后根遍历：先依次后根遍历根的每棵子树，再访问树根。例：例：ABCDEF先根：先根：ABCEFDABCEFD后根：后根：BEFCDABEFCDA树 二叉树（续上例）ABCDEF先序：先序：ABCEFDABCEFD中序：中序：BEFCDABEFCDA结论结论：（续上例）树的先根先根遍历相当于其转化的二叉树的先序先序遍历；树的后根

36、后根遍历相当于其转化的二叉树的中序中序遍历；2 2、森林的遍历、森林的遍历(1)(1)先序先序(先根先根)遍历森林遍历森林A.访问第一棵树的树根；B.先序遍历第一棵树根的子树森林；C.先序遍历除第一棵树之后,剩余的树构成的森林。ABCDEF先序：先序：ABCDEFABCDEF(2)(2)中序中序(后根后根)遍历森林遍历森林A.中序遍历森林中第一棵树的根结点的子树森林；B.访问第一棵树的根结点；C.中序遍历除第一棵树之后剩余的树构成的森林。ABCDEF中序：中序：BCDAFEBCDAFE例例:CDEFHJ先根先根:ABCDEFGHJIK(ABCDEFGHJIK(二叉树的先序二叉树的先序)后根后根

37、:BADEFCJHKIG(BADEFCJHKIG(二叉树的中序二叉树的中序)ABIKG森林转化的二叉树森林转化的二叉树:CDEFHJABIKG5 5哈夫曼树及其应用哈夫曼树及其应用一、概念和术语一、概念和术语1、路径路径2、路径长度路径长度3、结点的权结点的权4、结点的带权路径长度结点的带权路径长度5、树的带权路径长度树的带权路径长度6、哈夫曼树哈夫曼树（续三）（续三）例：例：给定四个叶子结点a、b、c、d，分别带权0.1、0.1、0.4、0.4，由它们构成不同的带权二叉树，分别求WPL。0.1 0.1 0.4 0.4WPL=20.10.10.40.4WPL=1.80.10.10.40.4WP

38、L=2.1二、哈夫曼树的构造二、哈夫曼树的构造哈夫曼树构造算法:(P91)根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。例：给定权值7，5，2，4，构造哈夫曼树。前缀码前缀码给定一个码的集合序列，若没有一个序列是另一个序列的前缀，则称这个集合中的码为前缀码前缀码。例：例

39、：000，001，01，10，11 前缀码0，1，10，11 不是前缀码特点：特点：前缀码是码长不等的编码，既可以缩短报文的长度，又容易翻译。（本章结束）第七章图第七章图基本概念与术语基本概念与术语一、图的定义一、图的定义定义：定义：简单地说，图是由一些结点和连接两个结点之间的边组成。2 2图的存储表示和图的生成图的存储表示和图的生成一、图的存储表示一、图的存储表示1 1、邻接矩阵表示法、邻接矩阵表示法（数组表示法）用一维数组存储图中顶点的信息；用矩阵（二维数组）表示图中各顶点之间的相邻关系。图的顺序存储结构图的顺序存储结构(1)(1)邻接矩阵的定义邻接矩阵的定义图G=(V,E),n个顶点，邻

40、接矩阵用A1.n,1.n存放：Aij=1若或(vi,vj)E,ij 0 否则对带权的图：Aij=wij 若或(vi,vj)E,ij,且权为wij 0 否则(2)(2)对称性对称性无向图：无向图：邻接矩阵对称，只需存入下三角（或上三角）,所用空间为n(n+1)/2有向图：有向图：不一定对称，需n2个存储单元。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 2、图的邻接表（、图的邻接表（图的一种链式存储结构图的一种链式存储结构）(1)(1)无向图的邻接表无向图的邻接表vexdataFirstarc头结点：头结点：顶点顶点指向与该顶点指向与该顶点邻接的第一个邻接的第一个邻接点邻接点adjv

41、exnextarc表结点：表结点：邻接点在邻接点在图中的图中的位置位置指向下一个指向下一个邻接点邻接点构造方法：构造方法：与同一顶点邻接的所有邻接点构成一个单链表，用表结点描述；各链表设置表头结点，由头结点描述；各表头结点构成一个顺序表。(2)(2)有向图的邻接表及其逆邻接表有向图的邻接表及其逆邻接表邻接表（出度表）：邻接表（出度表）：结点结构同无向图。以vi为顶点的邻接点单链表上的结点都是以vi为弧尾弧尾的邻接点。顺序表部分定义同无向图的邻接表。逆邻接表（入度表）：逆邻接表（入度表）：结点结构同无向图。以vi为顶点的邻接点单链表上的结点都是以vi为弧头弧头的邻接点。顺序表部分定义同无向图的邻

42、接表。3 3图的遍历图的遍历遍历遍历：按一定次序，由图的某一顶点出发，沿着图的边访问所有顶点恰恰一次一次。设置访问标志数组设置访问标志数组：visitedi 1=i=n(n为图中顶点个数)False表示未被访问True表示已被访问一、深度优先搜索一、深度优先搜索（DFS）搜索策略：搜索策略：访问当前顶点vi，寻找与vi相邻且未被访问顶点vj，若存在，将其作为当前点，访问，并重复上述搜寻过程。否则（所有邻接点都被访问过），退回一步，寻找与前一个顶点相邻的未被访问顶点，访问，并重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。深度优先搜索是一种纵向搜索纵向搜索的过程。二、广

43、度优先搜索二、广度优先搜索（BFS）搜索策略：搜索策略：访问出发点v0，依次依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发重复上述过程。若上述过程无法访问图中的所有顶点，则另选一个新顶点重新开始。广度优先搜索是一种横向搜索横向搜索的过程。使用队列队列结构。算法思想算法思想从指定顶点出发，每访问一个顶点就把它排在队尾，然后从队头取出一个顶点，访问该顶点所有未被访问的邻接点，如此，直到队空。若图中仍有未被访问的顶点，则另选一个顶点为出发点，重复上述过程。4 4生成树生成树&最小生成树最小生成树一、生成树一、生成树1 1、定义：、定义：一个连通图连通图G的子图如果是一棵包含G的所有顶

44、点的树，则该子图称为G的生成树生成树。2 2、算法思想：、算法思想：DFS或BFS生成树。二、最小生成树二、最小生成树1 1、定义、定义连通网G=(V,E)，边是带权的，因而G的生成树的各边也是带权的。将生成树的各边的权值总和称为生成树的权，并把权最小权最小的生成树称为G的最小生成树最小生成树。例：例：用用PrimPrim算法求最小生成树算法求最小生成树连通图如下所示：21456361555366422145636155536642例：例：用克鲁斯卡尔算法求最小生成树用克鲁斯卡尔算法求最小生成树连通图如下所示：214563615553664212435612435612435612435612

45、43561243565 5最短路径最短路径一、单源最短路径问题一、单源最短路径问题单源最短路径问题单源最短路径问题给定带权有向图，求从指定源点到图中其余各点的最短路径。u0到其余各顶点的最短路径到其余各顶点的最短路径源点源点中间顶点中间顶点终点终点路径长度路径长度1 2101 4 30 1 4 3 50 1 4,3 5 60 12534101005030102060u06 6拓扑排序拓扑排序将集合中偏序关系变为全序关系称为拓扑排序。一、拓扑排序一、拓扑排序1 1、相关概念、相关概念AOV网网：顶点表示活动，弧表示活动间的优先关系的有向图。在无回路的AOV网中，所有的活动可以排成一个线性序列，使

46、得每个活动的所有前驱活动都排在该活动的前边，称此序列为拓扑序列拓扑序列，由AOV网构成拓扑序列的过程称为拓扑排序拓扑排序。拓扑排序算法思想：拓扑排序算法思想：选择有向图中入度为0的顶点输出，并从图中删去该点相邻弧；重复上述操作，直到图中全部顶点均被输出或图中已不存在入度为0的顶点（有回路）。更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 2排序概念排序概念趟（趟（PassPass）实现一个元素的有序性所完成的操作。稳定性稳定性若在排序前两个记录在序列中的关系为RiRj，且Ri与Rj的关键字相同Keyi=Keyj，排序后若RiRj称排序方法稳定，若RjRi称排序方法不稳定。内部排序的相

47、关概念内部排序的相关概念排序方法分类排序方法分类插入排序交换排序选择排序归并排序基数排序排序算法的关键操作排序算法的关键操作比较：比较两个关键字的大小。移动：将记录从一个位置移动至另一个位置。2 2插入排序插入排序一、直接（简单）插入排序一、直接（简单）插入排序基本思想：基本思想：每一趟都在已排好序的有序子表中插入一个元素，使有序子表不断扩大。趟：趟：在含有i-1个记录的有序子表中，插入第i个元素成为含有i个元素的有序子表的过程。算法实现：算法实现：引进监视哨的作用。算法分析算法分析空间：增加一个监视哨时间比较最好情况（正序）：n-1次最坏情况（逆序）：(n+2)(n-1)/2移动最好（正序）

48、：2(n-1)最坏（逆序）：(n+4)(n-1)/4平均时间复杂度：O(n2)稳定性稳定性：算法稳定二、希尔排序（二、希尔排序（ShellShell排序）排序）又称缩小增量排序，是直接插入排序的改进。基本思想基本思想将待排记录序列按增量dh值分成若干子表进行直接插入排序；然后缩小增量值，再分割，再排序，直至整个序列“基本有序”时，再对整个序列做一次直接插入排序。算法分析算法分析增量选取方法增量序列不同，时间复杂度不同稳定性：算法不稳定希尔排序的特点3 3交换排序交换排序一、起泡排序一、起泡排序基本思想基本思想相邻元素依次进行比较，小的前移，大的后移，第一趟结束后，最大元素放在了最后；再进行第二

49、趟，使次大元放在最大元素之前；继续，直到在一趟排序中没有交换发生，排序结束。算法分析算法分析最好情况（正序）比较次数：n-1移动次数：0最坏情况（逆序）比较次数：移动次数：n(n-1)时间复杂度：O(n2)稳定性：算法稳定23112/)1()(ninnin二、快速排序二、快速排序基本思想基本思想每趟让待排表中的第一元素作支点，排序后入终位k，将原表一分为二，使得r1rk-1中元素小于等于rk，而rk+1rn中元素都大于等于rk，递归进行，直到表长为1时，排序结束。一趟快速排序算法一趟快速排序算法支点放入x附设两个指针i和j：初始i指向第一元，j指向第n元从右向左，放过x.key元（比x大的元素

50、），j变化，当rj.keyx.key，放入j位置直到i=j，一趟结束，i为x终位 locating the pivot 4938659776132749 ij 273865977613 49ij 273865977613 49ij 2738 9776136549ij 2738139776 6549ij 273813 76976549 ij 2738134976976549 ijCS&T,BITIChapter 8算法分析时间效率最坏情况：当待排序的记录序列已经有序时，出现恶化趋势，Tworst(n)=O(n2)最好情况：每次划分的两个子表的长度大致相等，支点入“中值”位，Tbest(n)=O(

51、nlog2n)平均情况：数据去无序，T(n)=Tpass(n)+T(k-1)+T(n-k)=O(nlnn)空间效率稳定性：不稳定4 4选择排序选择排序一、简单选择排序一、简单选择排序基本思想基本思想每趟通过n-i次关键字之间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1in)个记录交换之。问题问题简单选择排序与起泡排序在排序过程都须经过比较、交换而实现的，二者的有何区别？算法分析算法分析时间效率比较次数：（无论正序、逆序、其他任意顺序）移动次数：最好情况(正序)：0次最坏情况(非逆序，但每趟排序过程中都有交换发生):3(n-1)平均时间复杂度：O(n2)空间效率：供交换用一个存

52、储单元的辅助空间稳定性：不稳定2/)1()(11nninni二、堆排序二、堆排序堆排序的算法思想堆排序的算法思想1、建堆将给定的原始待排序列建成一个初始堆。即先建成一棵完全二叉树，再从下往上筛选为堆。首先由序列的第 结点开始与其孩子比，大的上小的下（交换），下去后若有孩子再比较，直到叶子然后再由序列的第 结点起，重复上述过程，直到待排序列中的第一个结点。建成逆堆逆堆。得到待排序列中的最大元（根结点），并输出之。2、根结点与最后一片叶子交换。交换。3、若不是堆，则从根开始自上而下恢复成堆。4、重复2、3步，直到剩下一个结点为止，排序结束。12/n2/n5 5归并排序归并排序归并排序是另一类不同的

53、排序方法。“归并归并”的含义是将两个或两个以上的有序表合成一个新的有序表。实现算法即可采用顺序存储结构，也可采用链式存储结构。1 1、归并概念、归并概念将两个或两个以上的有序表合并成整体有序的大表。归并分类参加归并的有序表个数为2，称为2-路归并参加归并的有序表个数为3，称为3-路归并参加归并的有序表个数3，称为多路归并a、b、C均有序,且ai 若ai=bjbj 否则 Ck=a1.nb1.m C1.m+n归并归并2 2、2-2-路归并的基本思想路归并的基本思想基本思想基本思想对于n个元素的待排关键字序列，先分成长度为1的n个有序子表，两两归并，得到 个长度为2或1的有序子表；再对这 个有序子表

54、进行两两归并；如此重复，直至得到一个长度为n的有序表。2/n2/n更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 3、算法分析、算法分析时间效率时间=一趟归并时间*归并趟数=O(n)*log2n=O(n log2n)空间效率：使用了一个辅助数组 O(n)算法稳定性：稳定6 6基数排序基数排序基数排序借助多关键字排序的思想对单逻辑关键字进行排序，排序中不需要进行比较。一、多关键字排序一、多关键字排序设n个记录R1,R2,Rn，Ri的关键字为（K ,K ,K ），d个关键字对任意记录Ri和Rj，若他们的关键字满足（K ,K ,K ）ST.elemmid.key:则在右子表中继续找若key

55、ST.elemmid.key:则在左子表中继续找若key=ST.elemmid.key:已找到2 2、算法分析、算法分析判定树查找过程可以用一棵二叉树来描述，通常称此树为判定树。分析结论折半查找法在查找成功时，给定值Key与查找表中关键字进行比较的比较次数最多不超过与折半查找过程相对应的二叉判定树的树深。ASL=O(log2n)3 3、折半查找的特点、折半查找的特点只适用于有序表（构造有序表有一定的消耗）；只限于顺序存储结构，对线性链表不适用。三、索引顺序表的查找三、索引顺序表的查找分块查找分块查找静态查找表的组织方式：索引顺序表分块查找：又称索引顺序查找1 1、查找表的组织、查找表的组织查找

56、表中所有元素按关键字组成b块，每块s个元素；且块间元素有序，块内元素无序。建立索引表：由索引项构成，每项两个域。索引表按关键字有序。块内最大关键字块内最大关键字块所在地址块所在地址(表中表中)2 2、查找算法、查找算法查找过程分两步进行通过索引表确定待查记录所在块可用折半查找在块中查找所需记录可用顺序查找3 3动态查找表动态查找表静态查找表只能进行查找操作。若要在查找中不断地做插、删操作，应使用动态查找表。特点：特点：查找表结构本身是在查找过程中动态生成的。即对于给定值Key，若表中存在其关键字等于Key的记录，则查找成功，否则插入该记录。称此类查找表为动态查找表动态查找表。一、二叉排序树一、

57、二叉排序树（BST）1 1、定义、定义定义：定义：如果一棵二叉树中，每个结点的值都大于它的左子树上所有结点的值，而小于它的右子树上所有结点的值，则称此树为二叉排二叉排序树序树。2 2、二叉排序树的查找、二叉排序树的查找算法思想算法思想当二叉排序树不空时，首先将给定值key和根结点的关键字比较：若根结点=key，查找成功若根结点key，则用同样方法在根结点的左子树左子树上查找更多优质自考资料尽在百度贴吧自考乐园俱乐部（http:/ 3、二叉排序树的插入、二叉排序树的插入插入原则插入原则若二叉排序树为空，则将待插结点作为根结点插入到空树中。若二叉排序树非空，将待插结点的关键字与根结点的关键字比较：

58、若相等，则说明树中已有该结点，无须再插入；若待插结点的关键字根结点的关键字时，则将待插结点插入到根的右子树；在左子树、右子树中的插入过程与在树中的插入过程相同，如此下去，直到待插结点作为一个新的树叶新的树叶插入到二叉排序树，或发现树中已有该结点为止。4 4、二叉排序树的生成、二叉排序树的生成生成：对于给定的记录关键字序列，首先从空的二叉排序树开始，每输入一个关键字，就建立一个新的结点插入到当前已生成的二叉排序树中，插入规则同前。二叉排序树的重要特征：二叉排序树的重要特征：按中序遍历二叉排序树得到一个递增有序的序列按中序遍历二叉排序树得到一个递增有序的序列对于给定的记录关键字集合，不同的输入顺序

59、可以构造出不同形态的二叉排序树，共有：1n+1n2nC5 5、二叉排序树的删除、二叉排序树的删除分三种情况讨论：分三种情况讨论：设待删结点为P，其双亲为F，且P是F的左孩子若待删结点P是叶子结点,则直接删去此结点若待删结点P只有左子树无右子树,或只有右子树无左子树,则用其左子树的根或右子树的根代替被删结点P。若待删结点P既有左子树又有右子树，则不能简单处理，有以下处理方法：（设P的中序遍历的前驱前驱结点为S，S-rchild=NULL）用S替代P，S原来的左子树成为S双亲Q的右子树。6 6、二叉排序树查找效率分析、二叉排序树查找效率分析查找效率不仅与树中结点个数有关，还与树的形态有关最坏情况：

60、当关键字有序时，构成的二叉排序树蜕变为单枝树，树深为nASLss=(n+1)/2 (等概下)最好情况：二叉树的形态与折半查找的判定树相同ASLss=O(log2n)(等概下)二、二、B-B-树和树和B B+树树(一一)、B-B-树树定义：定义：一棵m阶的B-树，或为空树；若树不空，则为满足下列特性的m叉树：2根结点子树数m其他非叶子结点子树数m所有非终端结点结构：nA0K1A1K2A2KnAn其中：n为结点关键字个数，-1 n m-1A0An：指向子树根结点的指针K1Kn：结点关键字在同一结点上：KiKi+1,且同一结点上关键字有序对于“Ai-1KiAi”有：Ki大于Ai-1所指结点上的任一关

61、键字Ki小于Ai所指结点上的任一关键字所有叶子结点均在同一层上，且不带信息。2/m2/m2 2、B-B-树的运算树的运算(1)B-(1)B-树的查找运算树的查找运算在在B-B-树中查找给定的关键字的方法：树中查找给定的关键字的方法：首先从根结点开始，在根结点所包含的关键字中查找给定的关键字K（采用顺序查找或折半查找），直到Ki-1Kn。若找到等于给定值K的关键字K=Ki，则查找成功；否则，一定可以确定要查的关键字是在某个Ki-1和Ki之间（关键字有序），于是取Ai-1所指向的结点继续查找；如此重复下去，直到找到或指针Ai-1为空时（找到叶子），查找失败。查找成功：查找成功：可在根或非叶子结点。

62、查找失败查找失败：从根走到某一叶子结点。B-树查找效率分析：在B-树上进行查找包含两种基本操作。在B-树上找结点。在结点中找关键字。设m阶B-树中具有N个关键字，因此有N+1个树叶，所以2(m/2)l-1 N+1 l log m/2(N+1)/2)+1。O(log m/2 N)。B-树的查找效率是相当高的。(2)B-(2)B-树的插入运算树的插入运算B-B-树插入规则树插入规则:m阶B-树,若叶子结点处于第L+1层时,插入的关键字总是进入第L层的结点。若结点的关键字个数 m/2 -1，则直接删除。若结点的关键字个数=m/2 -1，则首先向兄弟结点借关键字：若允许，则删除完成。若借不到，则进行结

63、点合并。合并操作可能一直到根结点，使树的深度减少一层。4 4哈希表（哈希表（HashHash）哈希表采用的是直接存取技术哈希表采用的是直接存取技术一、哈希表查找的基本概念一、哈希表查找的基本概念1 1、基本思想、基本思想不直接比较，通过哈希函数建立关键字到哈希表的映射关系（可能多对一）。建立哈希表时。在哈希表中查找记录时。keyHash函数函数Hash地址二、解决冲突的方法二、解决冲突的方法1 1、开放定址法：、开放定址法：当冲突发生时，使用某种方法在Hash表中形成一个探查序列，然后沿着此探查序列逐个单元地查找，直到找到给定关键字或碰到一个开放的地址（即地址单元为空）为止。插入时：碰到开放的

64、地址，则将待查关键字插入。查找时：碰到开放的地址，则说明查找失败。(1)(1)、线性探测再散列、线性探测再散列di=(d+i)mod mi=1,2,m-1m为Hash表表长d为冲突产生时的Hash地址 通过 i 取值的线性变化构造探查序列特点：线性(2)(2)二次探测再散列二次探测再散列 d2i-1=(d+i2)mod md2i=(d-i2)mod m 1=i=(m-1)/2特点：特点：将同义词来回散列在第一次产生冲突时的Hash地址的两端探测序列是跳跃似的减少堆积（二次聚集）的发生缺点：不易探测到整个Hash表空间(3)(3)伪随机探测再散列伪随机探测再散列di=(d+Ri)mod mm为H

65、ash表长d为冲突产生时的Hash地址Ri：R1,R2,Rm-1是一个伪随机数序列2 2、再哈希法、再哈希法当冲突产生时，通过再计算另一个哈希函数地址解决冲突。即为构造不同的哈希函数。di=RHi(K)i=1,2,k其中：RHi(K)RHj(K),即RHi均是不同的Hash函数。优点：优点：不易产生堆积或聚集。缺点：缺点：计算量大。3 3、链地址法、链地址法将所有关键字为同义词的记录存储在同一单链表中。假设Hash函数产生的哈希地址在区间0m-1上，则将Hash表定义为一个由m个头指针组成的指针数组chainHashm，凡Hash地址为 i 的记录都插入到以数组元素chainHashi为头指针

66、的链表中，并保持同义词在同一线性链表中按关键字有序。优缺点优缺点优点：不会产生堆积；空间是动态申请的，适用于造表前无法确定表长的情况。缺点：空间开销大。三、哈希表的算法分析三、哈希表的算法分析哈希表的装填因子体现哈希表的装满程度哈希表的查找效率的决定因素哈希函数解决冲突的方法哈希表的装填因子表中填入的记录数 哈希表的长度=nm假设Hash函数均匀的前提下，不同的解决冲突的方法得到的Hash表的ASL不同，且不是表中关键字个数n的函数，而是装填因子的函数。如下表所示：解决冲突的方法解决冲突的方法平均查找长度平均查找长度ASL线性探测法二次探测、随机探测、再哈希法链地址法(1+1/(1-)/2(1+1/(1-)2)/2-ln(1-)/1/(1-)1+/2+exp(-)成功查找成功查找不成功查找不成功查找越小，发生冲突的可能性越小。越大，发生冲突的可能性越大。因此只要选择合适，不管n多大，哈希表的平均查找长度就会限定在一个范围之内。ASL链线性随机（本章结束）第十章文件第十章文件基本概念基本概念文件：是性质相同的记录的集合1.文件的逻辑结构及操作2.文件的存储结构：顺序文件、索引文件、散列文