2021年自学考试数据结构重点总结02331整理

1、自考数据构造重点整顿第一章概论1,瑞I:计算机科学家沃思提出：算法 +数据构造二程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数拯构造。2 .数据是信息载体c数据元素是数据根本单位。一种数据元素可以由假设干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。3 .数据构造指是数据元素之间互有关系，即数据组织形式。数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 数据逻借构造是从逻辑关系上描述数据，与数据元素存储构造无关

2、，是独立于汁算机。数据逻辑构造分类：线性构适和非线性构造 数据元素及其关系在讣算机内存储方式，称为数据存储构造物理构造。数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 数据运算最惯用检索、插入、删除、更新、排序等。4?数据四种根本存储方法：顺序 存储、链接存储、索引存储、散列存储1顺序存储：普通借助程序设计语言数组描述。2链接存储：普通借助于程序语言指针来描述。3 索引存储：索引表由假设干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。4散列存储：该方法根本思想是：依照元素核心字直接il?算出该元素存储地址。5 .算法必要满足5个准那么：输入，0个或各种数据作为输入：

3、输出，产生一种或各种输出：有穷性，算法执行有限步后结束：拟定性，每一条指令含义都明确：可行性，算法是可行。算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、il?算机程序语言、数学语言或商 宦符号语言来描述。当前惯用描述算法语言有两类：类 Pascal和类Co6 .评价算法优劣：算法"对的性"是一方而要考虑。止匕外，重要考虑如下三点： 执行算法所消耗时间，即时间复杂性： 执行算法所消耗存储空间，重要是辅助空间，即空间复杂性； 算法应易于理解、易于编程，易于调试等，即可读性和可操作性。以上几点最重要是时间复杂性，时间复杂度惯用渐进时间复杂度表达。7 .算法

4、求解问题输入量称为问题规模，用一种正整数 n表达。8 .常用时间复杂度按数量级递增排列依次为：常数阶 0(1)、对数阶0(logcn).线性阶0(n)、线性对数阶0(nlog=n).平方阶0(多立方阶 0(n')、k次方阶0亦)、指数阶0(2=)和阶乘阶0 (n!)o9 . 一种算法空间复杂度 S(n)泄义为该算法所消耗存储空间，它是问题规模n函数，它涉及存储算法自身所占存储空间、算法输入输出数据所占存储空间和算法在运营过程中暂时占用存储空间。第二章线性表1 .数据运算是左义在逻辑构造上，而运算详细实现是在存储构造上进行。2 .只要拟定了线性表存储起始位卷，线性表中任意一种元素都可随机

5、存取，因此顺序表是一种随机存取构造。3 .常用线性表根本运算：(1)宜空表INtList (L)构造一种空线性表 L。(2)求表长ListLength (L)求线性表L中结点个数，即求表长。(3) GetNode (L, i)取线性表L中第i个元素。(4) LocateNode (L, x)在L中查找第一种值为x元素，并返回该元素在 L中位置。假设L中没有元素值为x ,那么返 回0值。(5) InsertList (L, i, x)在线性表L第i个元素之前插入一种值为 x新元素，表L长度加1。(6) DeleteList (L, i)删除线性表L第i个元素，删除后表L长度减1。4 .顺序存储方

6、法：把线性表数据元素按逻辑顺序依次存储在一组地址持续存储单元里方法。顺序表(Sequential List):用顺序存储方法存储线性表称为顺序表。顺序表是一种随机存取构造，顺序表特点是逻辑上相邻结点苴物理位置亦相邻。5 .顺序表上实现根本运算：(1)插入：该算法平均时间复杂度是0(n),即在顺序表上进行插入运算，平均要移动一半结点(n/2)。(2)删除：顺序表上做删除运算，平均要移动表中约一半结点(n-l)/2,平均时间复杂度也是 0(n)。6 .采用链式存储构造可以防止频繁移动大量元素。一种单链表可由头指针唯一拟定，因而单链表可以用头指针名字来命夕I。生成结点变量原那么函数p=( ListN

7、ode *)malloc (sizeof (ListNode) : /函数malloc分派一种类型为ListNode结点变量空间，并将苴首地址放入指针变量p中释放结点变量空间原那么函数free (p): 释放P所指结点变量空间结点分量访问 方法二:p- > data和p->next 指针变量P和结点变量*P关系：指针变量P值一一结点地址，结点变虽和值一一结点内容7.建立单链表:(1)头插法建表：算法：p= (ListNode *)malloc (sizeof (ListNode): 生成新结点p->data二ch; 将读入数据放入新结点数据域中p->next=head;

8、head=p;I TH l 幡+T r 瓜* t " A匕 ,/:、一 >d 一一* 将绡点邯插到单链表 head的头1.(2)尾插法建表：算法：p= (ListNode *)malloc (sizeof (ListNode): 生成新结点p->data=ch;将读入数据放入新结点数据域中i±(head二二 NULL)head=p;新结点插入空表elserear->next=p;将新结点插到缸之后rear=p; 尾指针指向新表尾将新姑点*s插列单燧农hsd的甩h(3)尾插法建带头结点单链表：头结点及作用：头结点是在链表开始结点之前附加一种结点。它具备两个长

9、处：1?由于开始结点位置被存储在头结点指针域中，因此在链表第一种位置上操作就和在表其他位置上操作一致，不必进行特殊解决；2.无论链表与否为空，其头指针都是指向头结点非空指针(空表中头结点指针域空)，因而空表和非空表解 决也就统一了。head头笫点 开始结点终端绪点匚 3 4 出 I> 1 <<, | /J头结点数据域阴影表达该某些不存储信息。在有应用中可用于存储表长等附加信息。<A)堆空衣1A|详细算法：r=head;/尾指针初值也指向头结点while(ch=getchar 0)!二n )s= (ListNode *)malloc (sizeof (ListNode)

10、;/ 生成新结点s->data 二 ch;/将读入数据放入新结点数摒域中r->next=s;r 二 s;)r->next二NULL;/终端结点指针域置空，或空表头结点指针域置空以上三个算法时间复杂度均为 0(n)。8,单链表上查找：(带头结点)(1)按结点序号查找：序号为 0是头结点。算法：p二head;j二0;/从头结点开始扫描while (p->next&&j<i) / 顺指针向后扫描，直到 p->next 为 NULL 或 i 二 j 为止 p=p->next;j+ ；)i±(i 二二 j)return p;找到了第i个

11、结点else return NULL;/当i<0或i>0时，找不到第i个结点时间复杂度：在等概率假设下，平均时间复杂度为：为 n/2=0(n)(2)按结点值查找：详细算法：ListNode *p=head->next;/从开始结点比拟。表非空，p初始值指向开始结点 wh订e (p&&p->data! =key) /直到p为NULL或p->data为key为I上p=p->next;扫描下一结点return p;假设p二NULL,那么查找失败，否那么 p指向值为key结点时间复杂度为：0( n)9 .插入运算：插入运算是将值为x新结点插入到表第i

12、个结点位置上，即插入到亦与 a'之间。riA,单琏表上插入余肖点示怠图s=(ListNode *)malloc(sizeof(ListNode); s->data=x; (3)s->next=p->next(4) ; p->next=s; 算法时间重要消耗在查找结点上，故时间复杂度亦为0(n) 010 .删除运算head任单链未上剧除结点示：e图r=p->next;使r指向被删除结点a: p->next=r->next;将弘从链上摘卜free (r):释放结点a'空间给存储池 算法时间复杂度也是0 (n)0 p指向被删除前一种结点。链表

13、上实现插入和删除运算，不必移动结点，仅需修改指针。11?单循环链表一在单链表中，将终端结点指针域 NULL改为指向表头结点或开始结点即可。判断空链表条件是 next;headhead-12.仅设尾指针单循环链表：用尾指针rear表达单循环链表对开始结点a,和终端结点加查找时间都是0(1)。而表操作经常是在表首尾位宜上进行，因而，实用中多采用尾指针表达单循环链表。判断空链表条件为rear=rear->next;?renr*rpar->noxt仅的单循环链表13?循环链表：循环链表特点是不必增长存储疑，仅对表链接方式稍作变化,即可使得表解决更加以便灵活。假设在尾指针表达单循环链表上实现

14、，那么只需修改指针，不必遍历，其执行时间是0(1)，十一)石详细算法:LinkList Connect (LinkList A, LinkList B)/假设A, B为非空循环链表尾指针LinkList p=A->next;/(D 保存A表头结点位置A->next=B->next->next ;/ （2jB表开始结点链接到 A表尾free（B->next） ;/释放B表头结点B->next 二 p;return B;/返回新循环链表尾指针循环链表中没有NULL指针。涉及飒历操作时，英终结条件就不再是像非循环链表那样鉴别p或p->next与否 为空，而是

15、鉴别它们与否等于某一指压指针，如头指针或尾指针等。在单链表中，从一结点出发，只能访问到该结点及苴后续结点.无法找到该结点之前其他结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一长处使某些运算在单循环链表上易于实现。14?双向链表：双（向）链表中有两条方向不同链，即每个结点中除next域存储后继结点地址外，还增长一种指向其直接前趋指针域prioriprior datn r>oxt 双链表由头指针head惟一拟左。 head 带头结点双链表某些运算变得以便。工 将头结点和尾结点链接起来，为双（向）循环链表。15 .双向链表前插和删除本结点操作双链表前插操作s-4?的前捕按作

16、void DInsertBefore(DListNode *p, DataType x) / 在带头结点双链表中，将值为 x新结点插入*p之前，设pHNULLDListNode *s=malloc(sizeof(DListNode);/(!) s->data=x;/(2)s->pr i or 二 p- >prior ;/(3)s-next 二 p;/ p->prior->next=s;/ p->pr i or=s ;/双链表上删除结点*P自身操作/在带头结点双链表中，删除结点和，设*声为非终端结点p->prior->next=p->next

17、;/ p->next->prior=p->prior;/ free (p); )与单链表上插入和删除操作不同是，在双链表中插入和删除必要同步修改两个方向上指针。上述两个算法时间复杂度均为0(1)。16 .顺序表和链表比拟时间性能：a、线性表：经常性查找；b、链式存储构造：经常插入删除操作：空间性能：a、对数据量大小事先可以懂得用线性表；b、数据量变化较大用链式存储构造。存储密度越大，存储空间运用率越高。显然，顺序表存储密度是1,链表存储密度必左不大于 1。第三章栈和队列1. 栈称为后进先出(Last In First Out)线性表，简称为LIFO表"栈是运算受限线

18、性表，顺序栈也是用数组表达。进栈操作：进栈时，需要将S->top加1. (DS->top=StackSize-l表达栈满上溢现彖一当栈满时，再做进栈运算产生空间溢浮现彖。退栈操作：退栈时，需将S->top减1.S->top<0表达空栈下溢现彖一当栈空时，做退栈运算产生溢浮现象。下溢是正常现象，惯用作程序控制转移条件。空栈时栈顶指针不能是 0,只能是-1当程序中同步使用两个栈时，可以将两个栈栈底分Stall IKHX r2kl中有ITU- Hr校空间满“F 同 ld| E b |以1 _ 1 耳 I _fl!良I 11pimh |M>别设在顺序存储空间两端，让

19、两个栈顶各自向中间延伸。当一种栈中元素较多而栈使用空间超过共享空间一半时 只要另一种栈元素不多，那么前者就可以占用后者某些存储空间。当Topl=Top2-l时，栈满data next2. 为了克服顺序存储分派固泄空间所产生溢出和空间挥霍问题。可采用链式存储构造来存储栈。链栈是没有附加头结点运算受限单链表。栈顶指针就是链表头指针。0链栈frontrenr认列初始为空栈front中结点是动态分派，因此可以不考虑上溢，不必泄义StackFull运算rear(b)A, B、C 入阻种重要应用是实现递归，直接调用自己或间接调用自己函数。oIB Cfrontrear3.容许删除一端称为队头(Front),

20、容许插入一端称为队尾(Rear),当队列中没A : hRK顺序陆宛T妻估示玄阁(d)H> C ； lltronxrenr有元素时称为空队列，队列亦称作先进先出(First In First Out)线性表，简称为表。FIFO队列顺序存储构造称为顺序队列，顺序队列事实上是一种受限线性表。顺序队列根本操作 入队时：将新元素插入 rear所指位苣，然后将rear加1。 出队时：删去front所指元素，然后将front加1并返回被删元素。当头尾指针相等时，队列为空。在非空队列里，头指针始终指向队头元素，而队尾指针始终指向队尾元素下一位置。而栈顶指针指向栈顶元素。循环队列。4. 循环队列：为充分运

21、用数组空间，克服上溢，可将数组空间想象为一种环状空间，并称这种环状数组表达队列为循环队列中进行出队、入队操作时，头尾指针仍要加1,朝前移动。只但是当头尾指针指向向量上界(QueueSize-1)时，英加1操作成果是指向向量下界0。这种循环意义下加1操作可以描述为:if (i+l=QueueSize) /i 表达 front 或：reari=0elsei十方法二一运用"模运算"i=(i+l)%QueueSize :循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，导致队空和队满时头尾指针均相等。因而，无法通过条件 Q. front二二Q. r亡ar来鉴别

22、队列是"空"还是"满"。解决这个问题方法至少有三种： 期设一种标志位以区别队列是空还是满： 设立一种计数器记录队列中元素总数 (即队列长度)。少用一种元素空间。商立入队前 ，测试尾指针在循环意义下加 1后与否等于头指针，假设相等那么以为队列满即尾指针Q? rear所指单元始终为空。boho循环队列操作演示当前耿弭中兀素总散g D _一入队元素出队元索儿索入U禅作刘行冲？ 一个儿盔入跟麻？秫亍环队列 的压抢them轴佶向卜个存储廉凡。?入耿。电新开始Otl:认5. 循环队列根本运算：置队空：Q->front=Q->rear=0; 判队空：ret

23、urn Q->rea:r=Q->front; 判队满：return (Q->rear-l) %QueueSize=Q->front; 入队Q->data Q->rear =x;/新元素插入队尾Q->rear= (Q->rear+l)%QueueSize;出队 temp=Q->dataEQ>front;Q->f ront= (Q->front+l) %QueueSize; / 循环意义卜头指针加 1 return temp;取队头元素 return Q->dataQ->front;6. 队列链式存储构适简称为链队

24、列。它是限制仅在表头删除和表尾插入单链表。*Q 认头结点,飘足结点(6)1空乳列为了简化解决，在队头结点之前附加一种头结点，并设队头指针指向此结点。Qf front Qf链队列根本运算：带头结点(1) 构造空队：Q->rear=Q->front: Q->rear->next=NULL:(2)判队空：return Q->rear=Q->front;(3) 入队：QueueNode *p= (QueueNode *)malloc(sizeof (QueueNode);/ 申请新结点p->data=x; p->next=NULL;Q->rear-

25、>next=p; *p链到原队尾结点后Q->rear=p;队尾指针指向新尾(4) 出队：当队列长度不不大于 1时，只需修改头结点指针，尾指针不变s=Q->front->next ; Q->front->next=s->next:x=s->data: free (s): return x :当队列长度等于1时，不但要修改头结点指针，还要修改尾指针s=Q>front->next: Q->front->next=NULL : Q->rear=Q->front; x=s->data ; free(s): retu

26、rn x;(5) 取队头元素：return Q->front->next->data :由于有头结点，因此用了next 和链栈类似，不必考虑判队满运算及上溢。 在出队算法中，普通只需修改队头指针。但当原队中只有一种结点时，该结点既是队头也是队尾，故删去此结点 时亦需修改尾指针，且删去此结点后队列变空。7?用计算机来解决计算算术表达式问题，一方而要解决问题是如何将人们习惯书写中缀表达式转换成后缀表达式。第四章多维数组和广义表1.数组顺序存储方式：普通采用顺序存储方法表达数组。1行优先顺序 a-： ,，2, ?, a, aci, ax, ?, aR, , a叭吐九2列优先顺序a:

27、1, a21, ?, a, a-, a: : , ?, hr, a： r, ?年口Pascal和C语言是按行优先顺序存储，而Fortran语言是按列优先顺序存储 2?为了右约存储空间，可以对矩阵中有许多值相似或值为零元素矩阵，采用压缩存储特殊矩阵是指相似值元素或零元素在矩阵中分布有一左规律。常用有对称矩阵、三角矩阵。(1)对称矩阵在一种n阶方阵A中，假设元素满足下述性质：a沪"0知jWn-1元素共享一种存储空称为n阶对称矩阵，它元素是关于主对角线对称，因此只需要存储矩阵上三角或下三角元素即可，让两个对称 lo矩阵元素汕和数组元素 sa k之间关系是k=iX(i+l)/2+j iMj

28、0Ak<n(n+l)/2-lk=jX(j+l)/2+i i<j 0Wk<n(n+l)/2-l(2)三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指它下三角(不涉及主角线)中元 素均为常数c或零;下三角矩阵主对角线上方均为常数c或零。普通状况，三角矩阵常数 c均为零。三角矩阵压缩 存储：三角矩阵中重复元素 c可共享一种存储空间，别的元素正好有 nX(n+l)/2个，因而，三角矩 阵可压缩存储在一维数组san(n+l)/2+l中，其中c存储在数组最后一种元素中。三角矩阵压缩存储构造是随机存取构造。3, 稀疏矩阵：设矩阵篇中有s个非零元素，假设s远远不大于矩阵

29、元素总数，那么称 A为稀疏矩阵。为了节约存储单元，可用压缩存储零元素所在行、列位置，因此可用三方法只存储非零元素。由于非零元素分布普通是没有规律，因而在存储非零元素同步，还必要存储非 元组(i, j, aj来拟泄非零元素稀疏矩阵进行压缩存储普通有两类方法：顺序存储(三元组表)和链式存储(十字链表)。稀疏矩阵压缩存储会失去随 机存取功能 oAIX5= 0-65 0 032 00 00800000 0.MaxSize015048101123212306(b)a-*data稀疏矩阵A和它的三元组?要相4, 广义表是线性表推广，又称列表。广义表是n(n>0)个元素a a，a,，比有限序列。其中

30、a'或者是原子或者是一种广义表 广义表通惯用圆括号括起来，用逗号分隔其中元素。 为了区别原子和广义表，书写时用大写字母表达广义表，用小写字母表达原子。假设广义表Ls非空(nAl),那么/是LS表头，别的元素构成表(5右 ，/)称为Ls表尾广义表具备递归和共享性质广义表深度：一种表展开后所含括号层数称为广义表深度。19.广义表是一种多层次线性构造，事实上这就是一种树形构造。任何一种非空广义表表头可以是原子，也可以是子表，而英表尾必然是子表。head=(a, b)=a, tail (a? b) = (b)对非空表A和(y),也可继续分解。注惫：广义表0和(0)不同。前者是长度为o空表，对英

31、不能做求表头和表尾运算：而后者是长度为1由空表作 元素广义表，可以分解得到表头和表屋均是空表0o广义表是一种有层次非线性构造，普通采用链式存储构造，每个元素用一种结点表达，结点由 3个域构成，英中一种是tag标志位，用来区别结点是原子还是子表，当tag为零时结点是子表，第二个域为slink,用以存储子表 地址：当tag为1时结点是原子，第二个域为data,用以存储元素值。第五章树和二叉树1?树表达法：最惯用是树形图表达法；尚有 3种嵌套集合、凹形、广义表。树构造根本术语(1)结点度(Degree)树中一种结点拥有子树数称为该结点度(Degree)。一棵树度是指该树中结点最大度数。度为零结点称为

32、叶子(Leaf)或终端结点。度不为零结点称分支结点或非终端结点。除根结点之外分支结点统称为内部结点。根结点又称为开始结点。(2)途径(path)假设树中存在一种结点序列 4, k：,，k:，使得k:是双亲(lWi<j),那么称该结点序列是从 ki到 一条途径(Path)。一种结点祖先是从根结点到该结点途径上所通过所有结点，而一种结点子孙那么是以该结点为根子树中所有结点。结点层数(Level)从根起算：根层数为1,别的结点层数等于其双亲结点层数加1。双亲在同一层结点互为堂兄弟。树中结点最大层数称为树高度(Height)或深度(Depth)。假设将树中每个结点各子树当作是从左到右有顺序(即不

33、能互换)，那么称该树为有序树(OrderedTree):否那么称 为无序树(UnoderedTree) o假设不特别指明，普通讨论树都是有序树。加上一种结点作树根,森林(Forest)是m(m20)棵互不相交树集合。树和森林概念相近。删去一棵树根，就得到一种森林：反乙 森林就变为一棵树。3. 二叉树与度数为2有序树不同：在有序树中，虽然一种结点孩子之间是有左右顺序，但是假设该结点只有一种孩子，就不必区别其左右顺序。而在二叉树中，虽然是一种孩子也有左右之分。二叉树性质：性质1二叉树第i层上结点数目最多为 21'1(i>l)。例如5层二叉树，第5层上结点数目最多为2*=16性质2深度

34、为k二叉树至多有 才-1个结点(k>l)o例如深度为5二叉树，至多有25-1=31个结点性质3在任意-棵二叉树中，假设终端结点个数为no,度为2结点数为n 那么m二氐+1。例如一棵深度为4二叉树(a),其终端结点数 m为8,度为2结点树为7,那么8=7+1, n,=n=+l成立(b)其终端结点数n°为6,度为2结点树为5,那么6二5+1, ru=n=+l成立3满：叉超满二叉树：一棵深度为 k且有2-1个结点二又树称为满二叉树。满二叉树特点:(1)每一层上结点数都到达最大值。即对给定高度，它是具备最多结点数二叉树。(2)满二叉树中不存在度数为 1结点，每个分支结点均有两棵高度相似

35、子树，且树叶都在最下一层上。完全二叉树：假设一棵深度为 k二叉树，英前k-1层是一棵满二叉树，而最下而一层上结点都集中在该层最左边假设干位置上，那么此二叉树称为完全二叉树。特点：(1) 满二叉树是完全二叉树,完全二叉树不一泄是满二叉树。(2) 在满二叉树最下一层上，从最右边开始持续删去假设干结点后得到二叉树依然是一棵完全二叉树。(3) 在完全二叉树中，假设某个结点没有左孩子，那么它一左没有右孩子，即该结点必是叶结点。性质4具备n个结点完全二叉树深度为。LlognJ+1或log(n+l) l例，具备 100 个结点完全二叉树深度为：Llgl00j+l=7, 2*=64 2 :二 128 因此 L

36、lgl00j=6jlg(100+l)l=74 .完全二叉树编号特点：完全二叉树中除最下而一层外，各层都布满了结点。每一层结点个数正好是上一层结点个数2倍。从一种结点编号就可推得英双亲，左、右孩子等结点编号。编号从 0开始 假设匚0,那么q,为根结点，无双亲；否那么，q'双亲编号为LG-1)/2。 假设2i+l<n,那么q：左孩子编号是21+1;否那么，Q无左孩子，即q,必然是叶子。 假设2i+2<n,那么q：右孩子编号是21+2;否那么，q：无右孩子。对于完全二叉树而言，使用顺序存储构造既简朴又节约存储空间。但对于普通二叉树来说，采用顺序存储时，为了使用结点在数组中相对位置

37、来表达结点之间逻借关系，就必要增长某些虚结点使其成为完全二叉树形式。还应设立两个指针5 . 链式存储构造：二叉树每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点自身数据外域Ichild和rchild,分别指向该结点左孩子和右孩子。结点构造为：叵回 WI巨刁二叉链表是一种惯用二叉树存储构造建立二叉链表方法：a.按广义表方法，接近左括号结点是在左子树上，而逗号右边结点是在右子树上。b、按完全二叉树层次顺序建立结点。具备n个结点二叉链表中，共有 2n个指针域。其中有n-l个用来批示结点左、右孩子，别的 n+1个为空二叉树遍历算法中递归终结条件是二叉树为空。递归工作栈中涉及两项：一

38、项为哪一项递归调用语句编号，另一项那么是指向根结点指针一棵二叉树前序和中序遍历序列或中序和后序遍历序列，可唯一拟定一棵二叉树。详细方法如下:一方而依照前序或后序遍历序列拟任二叉树各子树根，然后依照中序遍历序列拟左各子树根左右子树。6?线索二叉树：n个结点二叉链表必然存在 n+1个空指针域，可以运用这些空指针域，存储指向结点在某种遍历顺序下前趋和后继结点指针，这种指向前驱和后继结点指针称为刃线索，这种加上线索二叉链表称为线索链表，相应二叉树称为线索二叉树（ThreadedBinaryTree)。线索链表结点构造役次检中的结点垮耳为lchildItagdatartagrchiId其中：ltag和说

39、递是增长两个标志威，用来区别结点左、右指针域是指针，还是指向其前趋或后继线索。指向其左、右孩子右标志 rfag = <图中实线表达指针，虚线表达线索。线索二叉树中，一种结点是叶结点充要条件为：左、右标志均是7?二叉树线索化：把对一棵二叉线索链表构造中所有结点空指针域按照某种遍历顺序加线索过程称为线索化和中序遍历算法同样，递归过程中对每结点仅做一次访问。因而对于n个结点二叉树，线索化算法时间复杂度为0(n)一棵二叉府(b)二叉线索树bt1 二1限1r JCO二叉线，表8?树、森林到二叉树转换：树中每个结点最多只有一种最左边孩子长子和一种右邻兄弟将树转换成二叉树：在所有兄弟结点之间加一道连线

40、：对每个结点，除了保存与英长子连线外，去掉该结点与其他孩子连线。由于树根没有兄弟，故树转化为二叉树后，二叉树根结点右子树必为空树到二叉树的转换吹树到二叉树的转换2第一步：在树中所有兄弟结点Z间加i连线第二步：对何个结点，除了保 留与梵的长子的连线外， 去掉该条吉点与其他孩子的 连线树到二叉树的转换Z将一种森林转换为二叉树将森林中每棵树转化成二叉树，然后再将二叉树根肖点看做兄弟连在一起，形成一棵二叉树森林转化为二义树森林转化为二义树第一步：先将森林中的每棵树变为一义树森林转化为二叉树品第二步：将各叉树的根结点视为兄弟从左至右连在一 起.就形成一棵二义 树9.二叉树到树.森林车t换:方式是：假设二

41、叉树中结点x是双亲y左孩子，那么把x右孩子,右孩子右孩子，都与 y用连线连起来最后去掉所有双亲到右孩子连线匚10 ?树存储构造：1. 双亲表达法：双亲链表表达法运用树中每个结点双亲唯一性，在 存储结点信息同步，为每个结点附设一种指向其双亲指针parent,惟一地表达任何-棵树。1双亲链表表达法实现分析：E和F所在结点双亲域是1,它们双亲结点在向量中位置是b即B是它们双杀0注意： 根无双亲，其parent域为-1。下标 0 I 2 31 5 6 7 8 9MaxTreeSize-lIdatajmrent-1 0 0 0 1 1G_L_LJ_2 3 3 3?图6. 17树转化为 叉树S断小 叉树的

42、女*链 农双亲链表表达法中指针 parent向上链接，适合求指左结点双亲或祖先涉及根；求指定结点孩子或英他后裔时，也许要遍历整个数组2?孩子钱表法：孩子链表表达法是为树中每个结点设立一种孩子链表，并将这些结点及相应孩子链表头指针存储在一种向量中。注意：孩子结点数据域仅存储了它们在向量空间序号datA lintchildI细.l嗣转化为 叉树?1咽的孩了低衣农示法ffi 6? I7MH化为XHai|?K的挟J?兄弟锻衣3?孩子兄弟表达法：在存储结点信息同步，附加两个分这种存储构造最大长处是：它和二叉树二叉链表表达完全同样。可运用二叉树算法来实现对树操作。R前序遍历森林等同于前序遍历该森林相应二叉

43、树与双亲链表表达法相反，孩子链表表达便于实现涉及孩子及其子孙运算，但不便于实现与双亲关于运算。将双亲链表表达法和孩子链表表达法结合起来，可形成双亲孩子链表表达法。别指向该结点最左孩子和右邻兄弟指针域，即可得树孩子兄弟链表表达注意：11 ?树遍历： 普通都只给出两种顺序遍历树方法：前序先根顺序遍历和后序后根顺序遍历前序遍历一棵树等价于前序遍历该树相应二叉树 后序遍历一棵树等价于中序遍历该树相应二叉树。对下面a图中所示森林进行前序飒历和后序遍历，那么得到该森林前序序列和后序序列分别为ABCDEFIGJH和BDCAIFJGHEc而b图所示二叉树前序序列和中序序列也分别为ABCDEFIGJH和BDCA

44、IFJGHE。后序遍历森林等同于中序遍历该森林相应二叉树12 .从根结点到某结点之间途径长度与该结点上权乘积称为该结点带权途径长度，树种所有叶子结点带权途径长度之和称为树带权途径长度。带权途径长度 WPL最小二叉树称为哈夫曼树或最优二叉树。哈夫曼树不一定是二叉树。哈夫曼树又称为最优树，是一类 带权途径长度最熟 完全二叉树就是这种越径长度最短二叉树。只有叶结点上权值均相似时，完全二叉树一定是最优二叉树，否那么完全二叉树不一定是最优二叉树。最优二叉树中，权越大叶子离根越近。最优二叉树形态不唯一， WPL最小13 .哈夫曼算法:注总：初始森林中n棵二叉树，每棵树有一种孤立结点，它们既是根，又是叶子n

45、个叶子哈夫曼树要通过 n-l次合并，产生n-1个新结点。最后求得哈夫曼树中共有2n-l个结点哈夫曼树是严格二叉树,没有度数为1分支结点.© © © (a)初始森林图5.27哈夫曼树的构造过程示例数据压缩过程称为编码，反之，解压缩过程称为解码 设讣一种长短不等编码，那么必要保证任一字符编码都不是列一种字符编码前缀，这种编码称为前缀编码。可以运用二叉树来设计二进制前缀编码，其左分支表达字符0,右分支表达字符1,那么以根结点到叶结点途径上分支字符构成串作为该叶节 点字符编码码就是哈夫曼编码。因而设计电文总长最短二进制前缀编码，就是以n种字符浮现频率作为权构造一棵哈夫曼树

46、，由哈夫曼树求得编译码过程是从树根结点出发，逐个读入电文中二进制码第六章1?图G由两个集合构成，顶点集合和边集合，也可以图G只有顶点而没有边。用尖括号表达图有向边V V1, v;，有向边又称为弧，起点称为弧尾，终点称为弧头。无向图顶点对用圆括号表达(v ' ,v )。在无向图中，称v:和匕相邻接，在有向图中称顶点V'邻接到V 顶点V,邻接于V,条边无向图称为无向完全图。在无向图中，n取值范畴是0-n(n-l)/2,将具备n(n-l)/2 在有向图中，n取值范畴是0-n(n-l),将具备n(n-l)条边有向图称为有向完全图。无向图中，顶点度定义为以该顶点为一种端点边数目，有向图度

47、等于出度和入度之和。在无向图中，任意两顶点均有途径，那么称两顶点连通。假设图G中任意两个顶点都连通，称 G为连通图。无向图极 大连通子图称为连通分量，显然，任何连通图连通分量只有一种，即其自身，而非连通无向图有各种连通分量。在有向图中，图 G中任意两顶点连通，称为强连通图，极大连通子图称为强连通分呈假设在一种图每条边上标上某种数值，该数值称为该边权。边上带权图称为带权图，带权连通图称为网络2 .图存储构造：邻接矩阵和邻接表表达法。图顶点编号从 0开始。邻接矩阵表达法： vv：, Vj 或（jvJ是边，那么值为1,不是边那么值为0。无向图邻接矩阵是按主对角线对称。假设G是带权图，只要把1换成相应

48、边上权值即可，0位苣上可以不动或将其换图邻接矩阵表达法可以仅存储主对角线如下元素，时间复杂度为O（n：）邻接表表达法：邻接表是图一种链式存储构造。将无向图邻接表称为边表，将有向图邻接表称为出边表，将邻接表。假设无向图有n个顶点和亡条边，那么它邻接表共有n个头结点和2e个表结点。建立邻接表时间复杂度是 0（n+e）。图邻接表表达不是唯一，这是由于在每个顶点邻接表中，各边结点链接顺序可接顺序与边输入顺序和生成算法关于。3 .图遍历：遍历图算法是求解图连通性、图拓扑排序等算法根本。图遍历惯用是深度优先搜索遍历和广度优先搜索遍历两种方法。共需要搜索£个矩阵元素，时间复杂度为邻接矩阵0（Y）或

49、邻接表0（n+e）广度优先搜索遍历（BFS）类似于树按层次遍历，先被访问顶点，其邻接点也先被访问，就是先进先出。时间复杂度为邻接矩阵 0（外或邻接表0何十日,空间复杂度都是 O（n）。成无穷大表达。无向表表头向量称为顶点以是任意，英详细链简称为DFS序列。深度优先搜索遍历（DFS）类似于前序（先根）遍历。按访问顶点先后顺序得到顶点序列称为图深度优先遍历序列，或4 .生成树是连通图包括图中所有顶点一种极小连通子图，一种图极小连通子图恰为一种无回路连通图，也就是说 假设图中任意添加一条边，就会浮现回路，假设去掉任意一条边，都会使之成为非连通图。因而，一种具备n个顶点生成树有且仅有 n-1条边，但有

50、n-1条边图不一左是生成树，同一种图可以有不同生成树。生成树左义为：假设从图某顶点出发，可以系统访问到图所有顶点，那么遍历时通过边和图所有顶点所构成子图，称为该图生成树。最小生成树：图生成树不唯一，把权值最小生成树称为最小生成树(MST)。构造最小生成树算法：普里姆 Prim算法时间复杂度为0 (跖网中边数无关适于稠密图。克鲁斯卡尔Kruskal算法时间复杂度为0 (eloge),重要取决于边数，较适合于稀疏图。【例6.3】利用普里姆算法，给出求图6.17(a)所示的无向网络的最小生成树的过程。,用、，平、 用(p中"沁)0二6 '0：-忐© 配由O Q-5-

51、69; ©. /产、,/Q /3/23 © of3-初2或忠2金梦S16-18克鲁斯卡尔最小生成树的生成过程5?最短途径：Dijkstra迪杰斯特拉算法，提出了按途径长度递增顺序产生诸顶点最短途径算法。拓扑排序：子工程称为活动，顶点代表活动，有向边代表活动先后关系。这样有向无环图 DAG称为顶点活动网，简称为A0V网。将有向无环图G中所有顶点排成一种线性序列，假设 Cu, v>GE (G),那么在线性序列u任v之前,这种线性序列称为拓扑序列。由 A0V网构造拓扑序列过程称为拓扑排序。检测方法是：对有向图构造其顶点拓扑序列，假设网中所有顶点都在她拓扑序列中，那么 A0V

52、网必然不存在环。A0V网拓扑序列不是唯一。拓扑排序描述思想：a、在有向图中选一种没有前趋(入度为零)顶点，且输出之。b、从有向图中删除该顶点及英与该顶点关于所有边。c、重复上述环节，直到所有顶点都已输出或图中剩余顶点中没有前趋顶点为止。d、输出剩余无前趋结点。拓扑排序事实上是对邻接表表达图G进行遍历过程。时间复杂度是 0(n+e)第七章排序1 .如果待排序文献中存在各种核心字相似记录，通过排序后，这些具备相似核心字记录之间相对顺序保持不变，该排序方法是稳世；反之，那么是不稳左。排序在内存中解决，不涉及数据内外存互换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、选取、互换、归并和分派

53、排序。在排序过程中需进行两种操作：比拟两个核心字大小、变化指向记录指针或移动记录自身，而待排序记录存储形式普通有三种：顺序构造、链式构造和辅助表。评价排序算法原那么：执行算法需要时间，以及算法所需要附加空间。尚有算法自身复杂度。排序时间开销，普通状况下可用算法中核心字比拟次数和记录移动次数来衡量。2 .插入排序：每次将一种待排序记录按其核心字大小插入到前面已排好序文献中恰当位置。直接插入排序：每次从无序区取出第一种元素把它插入到有序区恰当位宜，使之成为新有序区，通过n-1次插入 后完毕。算法中R0作用：保存Ri副本，监视数组下标变戢j与否越界。因此 R0称为哨兵。每次比拟是从后 往前比拟-时间

54、复杂度最正确是 0(n),最坏是0( 4因此是0(n:)o空间复杂度0(1)，因此是就地排序。是稳泄算法。初始状况是有序区中只有一种元素RE11,无序区中R2. n on越大越明显。希尔排序时希尔排序(缩小增量排序广算法不稳立。记录总比拟次数和总移动次数都要比直接插入排序少得多，特别是当 间依赖于增量序列，最后一种增量必要是1,尽量防止增图互为倍数状况。下标初始关键字12345678936254827652543581761032452525482732364358二76651d=31252512736483243657658d=l25252732364348586576?1耳侍尔才尺例,直到没有反序位置。3?互换排序：两两比拟待排序记录核心字，如果发现两个记录顺序相反时即进行互换冒泡排序(起泡排序)：通过相邻元素之间比拟和互换，使较小移向顶部，从后往前两两比拟。时