《2022年数据结构C语言版复习攻略归类 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构C语言版复习攻略归类 .pdf（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章：绪论一、基础知识概念和术语 (黑体字部分 )。另外，注意：1、数据元素是数据的基本单位。 P4 2、数据项是数据不可分割的最小单位。 P5 3、数据结构及其形式定义。 P5 四种基本结构： 集合线性结构树形结构图（网）状结构4、数据结构的逻辑结构 （抽象的，与实现无关）物理结构 （存储结构）顺序映像（顺序存储结构 ）位置“相邻”非顺序映像 （链式存储结构 ）指针表示关系 P6 5、数据类型 P7 抽象数据类型 （ADT）P7 ADT= （数据对象，数据关系，基本操作）ADT 细分为原子类型，固定聚合，可变聚合类型。P8 6、算法的概念P13 7、算法的五个特征有穷性确定性 可行性 输入
2、（0 个或多个） 输出（ 1个或多个）8、算法设计的要求：正确性可读性健壮性效率与低存储量其中正确性的四个层次（通常要求达到C层） 。9、算法的时间复杂度P15 常见有：O(1)，O(n)，O(n2)，O(log2n)1，O(n log2n)，O(2n) 语句频度 ，用归纳法计算。10、算法的空间复杂度 P17 二、算法起泡排序。 P16 另一种形式void BubbleSort ( DataType a, intn ) for ( i=0; in-1; i+ ) for ( j=0; jaj+1 ) ajaj+1; 或void BubbleSort ( DataType a, intn )
3、for ( i=1; in; i+ ) for ( j=0; jaj+1 ) ajaj+1; 或void BubbleSort ( DataType a, intn ) for ( i=0; in-1; i+ ) change = fasle; for ( j=0; jaj+1 ) ajaj+1; change = true; if ( !change ) break; 说明：a) 考试中要求写算法时，可用类C，也可用 C程序。b) 尽量书写算法说明，言简意赅。c) 技巧：用“边界值验证法”检查下标越界错误。如上第一个：第二个循环条件若写作 jn-i ，则当 i=0 时 aj+1会越界。d)
4、时间复杂度为 O(n2)，第 3个在最好情况下（待排记录有序） ，时间复杂度为 O(n)。第二章、线性表一、基础知识和算法1、线性表及其特点线性表是 n 个数据元素的有限序列。线性结构的特点：“第一个”“最后一个”前驱 后继。22、顺序表线性表的顺序存储结构1分析算法的时间复杂度时，log2n 常简单记作 log n 。2这里太简炼了，只是为了便于记忆。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 48 页 - - - - - - - - - （1）特点： a) 逻辑上
5、相邻的元素在物理位置上相邻。b) 随机访问。（2）类型定义简而言之，“数组 +长度”3。constintMAXSIZ E = 线性表最大长度 ; typedefstructDataType elemMAXSIZE; int length; SqList; 注：a) SqList为类型名，可换用其他写法。b) DataType是数据元素的类型，根据需要确定。c) MAXSIZE 根据需要确定。如constintMAXSIZE=64; d) 课本上的 SqList 类型可在需要时增加存储空间，在上面这种定义下不可以e) 课本上的 SqList 类型定义中 listsize表示已经分配的空间大小 （
6、容纳数据元素的个数）。 当插入元素而遇到 L.length=L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而 realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。（3）基本形态1 . 顺序表空条件L.length=0 不允许删除操作2 . 顺序表满条件L.length=MAXSIZ E 不允许插入操作3 . 不空也不满可以插入，删除（4）基本算法遍历4 . 顺序访问所有元素 for ( i=0; iL.length; i+ )v isit ( L.elemi ); 5 查找元素 xfor ( i=0; iL.lengt
7、h; i+ ) if ( L.elemi=x ) break; if ( iL.length ) 找到; else未找到 ; (2) 插入算法 ListInsert(&L,i,x)1 . 前提：表不满2 . 合理的插入范围： 1iL.length+1 注：位序 i 在 C/C+中对应于下标 i-1。3 . 步骤第 i 至最后所有元素后移一个元素在第 i 个位置插入元素 x 表长增 1 4 . 算法bool4ListInsert ( SqList& L, int i, DataT ype x ) if ( L.length=MAXSIZE | iL.length+1 ) return false
8、; / 失败/ 元素后移for ( j=L. length-1; j=i-1; j- ) / 这里 j 为下标，从 L.length-1 到i-1 L.elemj+1 = L.elemj; / 若作为位序，有如何修改？3不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。4这里返回 true 表示正确插入，返回false 表示插入失败。以下常用来区分操作是否正确执行。0 1 MAXSIZE-1 . L.elem L.elem L.elem L.length=0 L.length=MAXSIZE 0L.lengthMAXSIZE 名师资料总结 - - -精品资料欢迎
9、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 48 页 - - - - - - - - - / 插入 x L.elemi-1 = x; / 表长增 1 L.length+; return true; / 插入成功(3) 删除算法 ListDelete(&L,i,&x)1 . 前提：表非空2 . 合理的删除范围： 1iL.length 3 . 步骤取出第 i个元素第 i 个元素之后的元素向前移动一个位置表长减 1 4 . 算法boolListDelete ( SqList& L, int i, DataT
10、ype& x ) if ( L.length=0 | iL.length ) return false ; / 失败x = L.elemi-1; for ( j=i; jnext = 0 2 . 单链表不空条件：L-next != 0 (5) 基本算法（遍历）1 . 顺序访问所有元素借助指针，“顺藤摸瓜” (沿着链表访问结点 )。p = L-next; / 注意起始位置的考虑while ( p!=NULL ) / 判表尾，另外(p!=0)或(p)均可visit( p-data ); / 访问:可以换成各种操作p = p-next; / 指针沿着链表向后移动 例：打印单链表中的数据。voidPr
11、intLinkList ( LinkList L ) p = L-next; while ( p!=NULL ) print ( p-data ); / 访问：打印数据域p = p-next; 2 . 查找元素 x/ 在单链表 L 中查找元素 x/ 若找到，返回指向该结点的指针；否则返回空指针LinkList Find ( LinkList L, DataType x ) p = L-next; while ( p!=NULL ) if ( p-data = x ) return p; / 找到 xp = p-next; return NULL; / 未找到 / 在单链表 L 中查找元素 x/
12、 若找到，返回该元素的位序；否则返回0 int Find ( LinkList L, DataT ype x ) 5不准确的说法，只为便于理解和记忆，不要在正式场合引用。/ an/ C a1L L . data next 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 48 页 - - - - - - - - - p = L-next; j = 1; while ( p!=NULL ) if ( p-data = x ) return j; / 找到 xp = p-nex
13、t; j+; / 计数器随指针改变 return 0; / 未找到 前一个算法的另一种写法：p = L-next; while ( p & p-data!=x ) p = p-next; if ( p & p-data=x ) return p; else return 0; 或者p = L-next; while ( p & p-data!=x ) p = p-next; returnp; / 为什么3 . 查找第 i 个元素LinkList Get ( LinkList L, inti ) p = L-next; j = 1; while ( p & jnext; j+; if ( p &
14、 j=i ) return p; elsereturn 0; 4 . 查找第 i-1 个元素p = L; j = 0; while ( p & jnext; j+; if ( p & j=i-1 ) return p; else return 0; (6) 插入算法ListInsert(&L,i,x) 技巧：画图辅助分析。思路：先查找第 i-1 个元素若找到，在其后插入新结点bool6ListInsert ( LinkList &L, int i, DataType x ) / 查找第 i-1 个元素 p p = L; j = 0; while ( p & jnext; j+; / 若找到，在
15、 p 后插入 xif ( p & j=i-1 ) s = (LinkList) malloc(sizeof(LNode); s-data = x; s-next = p-next; / p-next = s; / return true; / 插入成功 elsereturn false; / 插入失败 注意：a) 要让 p 指向第 i-1 个而不是第 i 个元素（否则，不容易找到前驱以便插入）。b) 能够插入的条件：p & j= i-1 。即使第 i 个元素不存在，只要存在第 i-1个元素，仍然可以插入第i 个元素。c) 新建结点时需要动态分配内存。6这里返回 true 表示正确插入，返回fa
16、lse 表示插入失败。ai-1- 插入前执行之后执行之后- p x s ai-1- - p x - s ai-1- - p x - s 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 48 页 - - - - - - - - - s = (LinkList) malloc(sizeof(LNode); 若检查是否分配成功，可用if ( s=NULL ) exit(1); / 分配失败则终止程序d) 完成插入的步骤：。技巧：先修改新结点的指针域。(7) 删除算法ListDe
17、lete(&L,i,&x) 思路：先查找第 i-1 个元素若找到且其后存在第 i 个元素，则用 x 返回数据，并删除之boolListDelete ( LinkList &L, int i, int &x ) / 查找第 i-1 个元素 p p = L; j = 0; while ( p & jnext; j+; /若存在第 i 个元素，则用 x 返回数据，并删除之if ( p & j= i-1 & p-next ) / 可以删除s = p-next; / p-next = s-next; / x = s-data; free (s); return true; elsereturn fals
18、e; 注意：a) 要求 p 找到第 i-1 个而非第 i 个元素。为什么？b) 能够进行删除的条件：p & j= i-1 & p-next 。条件中的 p-next 就是要保证第 i个元素存在，否则无法删除。若写成p-next & j=i-1 也不妥，因为此时(循环结束时 )可能有 p=NULL ，所以必须先确定 p 不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p-next & p & j= i-1，因为先有 p!=0 才有 p-next，上式颠倒了这一关系。c) 释放结点的方法。free(s); d) 完成删除的步骤：。(8) 建立链表的两种方法思路：建立空表（头结点）；依次
19、插入数据结点（每次插入表尾得(a1,a2,an)，每次插入表头得 (an,a2,a1)） 。1 . 顺序建表void CreateLinkList ( LinkList &L, int n) / 建立空表L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表p = L; / 用 p 指向表尾/ 插入元素for ( i=0; idata = x; / 插入表尾s-next = p-next; p-next = s; p = s; / 新的表尾 2 . 逆序建表void CreateLinkList ( LinkList &L, int n
20、) / 建立空表L = (LinkList) malloc(sizeof(LNode); L-next = NULL; / 空表/ 插入元素ai-1- 删除前ai- p - s ai-1- 执行之后ai- p - s ai-1- 执行之后ai- p - 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 48 页 - - - - - - - - - for ( i=0; idata = x; / 插入表头s-next = L-next; L-next = s; 3. 循环链表
21、(1) 特点最后一个结点的指针指向头结点。(2) 类型定义同单链表。(3) 基本形态空表：L-next = L。非空表。(4) 与单链表的联系判断表尾的方法不同：单链表用p=NULL；循环链表用p=L。其余操作相同。4. 双向循环链表(1) 特点一个结点包含指向后继 (next)和指向前驱 (prior)两个指针，两个方向又分别构成循环链表。(2) 类型定义typedefstruct DuLNode DataType data; struct DuLNode *prior, *next; / 两个指针 DuLNode, *DuLinkList; (3) 基本形态空表：用后向指针判断 L- ne
22、xt = L，或者用前向指针判断 L-prior = L 。非空表。(4) 与单链表和循环链表的联系最大不同：前驱容易求得，可以向前遍历。判断表尾的方法与循环链表相同： p=L。插入和删除时需要修改两个方向的指针。(5) 插入和删除需要修改两个方向的指针。例如：(见下表) 表 0.2 双向循环链表的插入和删除p 之后插入 s p 之前插入 s 删除 p 之后继 s 删除 p s-next = p-nex t; p-next = s; s-prior = p; s-next-prior = s; s-prior = p-prior; p-prior = s; s-next = p; s-prio
23、r-next = s; s = p-next; p-next = s-nex t; p-next-prior = p; p-prior-next = p-next; p-next-prior = p-prior; a1a2anL L . . anC a1L . L data prior next 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 48 页 - - - - - - - - - 5. 顺序表与单链表的比较表 0.3 顺序表和单链表的比较顺序表单链表以地址相邻表示
24、关系用指针表示关系随机访问，取元素 O(1) 顺序访问，取元素 O(n) 插入、删除需要移动元素O(n) 插入、删除不用移动元素O(n)(用于查找位置 ) 总结：需要反复插入、删除，宜采用链表；反复提取，很少插入、删除，宜采用顺序表。第三章、栈和队列6. 栈栈，栈顶，栈底，空栈，后进先出 (LIFO)，入栈(Push) ，出栈(Pop)。顺序栈：栈的顺序存储结构； 链栈 ：栈的链式存储结构。7. 链栈(1) 存储结构用不带头结点的单链表实现。(2) 类型定义同单链表。(3) 基本形态1 . 栈空条件: S = NULL 2 . 栈非空3 . 栈满（一般不出现）(4) 基本算法1 . 入栈 Pu
25、sh (&s, x) boolPush ( LinkList &s, DataType x ) / 新建结点p = (LinkList) malloc (sizeof(LNode); if ( !p ) return false ; / 失败p-data = x; / 插入栈顶p-next = s; s = p; return true; 2 . 出栈 Pop (&s, &x)前提：栈非空。boolPop ( LinkList &s, DataType &x ) if ( s=NULL ) return false ; / 栈空/ 删除栈顶元素p = s; s = s-next; x = p-
26、data; free ( p ); return true; a1/ anS . an-1S / a1/ anS . an-1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 48 页 - - - - - - - - - 3 . 栈顶元素前提：栈非空。bool Top ( LinkList &s, DataT ype &x ) if ( s=NULL ) return false ; / 栈空x = s-data; return true; 8. 顺序栈(1) 存储结构类似
27、于顺序表，插入和删除操作固定于表尾。(2) 类型定义简单说，“数组 + 长度”7。constintMAXSIZ E = 栈的最大容量；typedefstruct DataType elemMAXSIZE; int top; SqStack; (3) 基本形态1 . 栈空条件s.top = 0; 2 . 栈满条件s.top = MAXSIZ E 3 . 栈不空、不满(4) 基本算法1 . 入栈Push (&s, x) 前提：栈不满boolPush ( SqStack& s, DataT ype x ) if ( s. top = MAXSIZ E ) return false; / 栈满s.el
28、emtop = x; / 或者 s.elemtop+ = x; top+; / 代替这两行return true; 2 . 出栈Pop (&s, &x) 前提：栈非空boolPop ( SqStack &s, DataT ype &x ) if ( s. top=0 ) return false ; top-; / 可用 x=s.elem-top; x = s.elemtop; / 代替这两行return true; 7不准确的说法，只为便于理解和记忆，不要在正式场合引用。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心
29、整理 - - - - - - - 第 9 页，共 48 页 - - - - - - - - - 3 . 栈顶元素前提：栈非空s.elemtop-1 即是。9. 队列队列，队头，队尾，空队列，先进先出 (FIFO)。链队列：队列的链式存储结构。循环队列：队列的顺序存储结构之一。10. 链队列(1) 存储结构简而言之，“单链表+ 尾指针”8。(2) 类型定义课本 P61。typedefstruct LinkList front; LinkList rear; LinkQueue; (3) 基本形态队列空： Q.front=Q.rear。非空队列。(4) 基本算法1 . 入队列课本 P62。插入队尾
30、，注意保持 Q.rear 指向队尾。2 . 出队列课本 P62。删除队头元素，特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。11. 循环队列(1) 存储结构简单说，“数组 + 头、尾位置”9。(2) 类型定义constintMAXSIZ E = 队列最大容量; typedefstruct DataType elemMAXSIZE; int front, rear; / 队头、队尾位置 SqQueue; (3) 基本形态通常少用一个元素区分队列空和队列满， 也可以加一标志。约定 front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 fr
31、ont,rear)。8不准确的说法，只为便于理解和记忆，不要在正式场合引用。9不准确的说法，只为便于理解和记忆，不要在正式场合引用。/ - a1- a2- an/ . Q.front Q.rear Q.front Q.rear 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 48 页 - - - - - - - - - 1 . 队列空条件：Q.front = Q.rear。不能出队列。2 . 队列满条件： (Q.rear+1)%MAXSIZE = Q.front （少用
32、一个元素时）。不能入队列。3 . 队列不空也不满4 . 加一标志区分队列空和队列满的情况可以用满所有空间。队列空和队列满时都有Q.front=Q.rear，再用标志区分。队列空： Q.front=Q.rear andQ.tag=0；队列满： Q.front=Q.rear and Q.tag=1。(4) 基本算法1 . 入队列前提：队列不满。boolEnQueue ( SqQueue &Q, DataT ype x ) if ( (Q.rear+1)%MAXSIZE=Q.front ) return false ; / 队列满/ 入队列Q.elem Q.rear = x; Q.rear = (Q
33、.rear+1)%MAXSIZE; return true; 2 . 出队列前提：队列非空。boolDeQueue ( SqQueue &Q, DataT ype &x ) if ( Q.front=Q.rear ) return false ; / 队列空/ 出队列x = Q.elem Q.front; Q.front = (Q.front+1)%MAXSIZ E; return true; 3 . 队列中元素个数结论： (Q.rear-Q.front+ MAXSIZ E)%MAXSIZE 。注：Q.rear-Q.front可能小于 0，需要加上 MAXSIZE 。int QueueLeng
34、th ( SqQueue Q ) return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; 4 . 用标志区分队列空和满用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下：front rear a1rear front a3a2a4a1rear front a3a2front rear tag:0 front rear a3a4a1a2front rear tag:1 a3a4a5a1a2名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11
35、 页，共 48 页 - - - - - - - - - void InitQueue ( SqQueue &Q ) Q.front = Q.rear = 0; Q.tag = 0; boolEnQueue ( SqQueue &Q, DataT ype x ) if ( Q.front=Q.rear and Q.tag=1 ) returnfalse; Q.elem Q.rear = x; Q.rear = (Q.rear+1)%MAXSIZE; if ( Q.tag= 0 ) Q.tag = 1; / 队列非空return true; boolDeQueue ( SqQueue &Q, Da
36、taT ype &x ) if ( Q.front=Q.rear and Q.tag=0 ) returnfalse; x = Q.elem Q.front ; Q.front = (Q.front+1)%MAXSIZ E; if ( Q.front=Q.rear ) Q.tag = 0; / 队列空return true; int QueueLength ( SqQueue Q ) if ( Q.front=Q.rear and Q.tag=1 ) return MAXSIZE; / 队列满elsereturn (Q.rear-Q.front+MAXSIZE)%MAXSIZ E; / 队列不
37、满(包含队列空的情况 ) 12. 栈和队列比较都是线形结构，栈的操作LIFO（后进先出），队列操作 FIFO（先进先出）。13. 简化的栈和队列结构在算法中使用栈和队列时可以采用简化的形式。表 0.4 简化的栈和队列结构简化栈简化队列结构“s + top”结构“q + front + rear”初始化top = 0; 初始化front=rear=0; 入栈stop+ = x; 入队列qrear = x; rear = (rear+1)%MAXSIZE; 出栈x = s-top; 出队列x = qfront; front = (front+1)%MAXSIZE; 栈顶stop-1 队列头qfro
38、nt 栈空top = 0 队列空front = rear 说明：只要栈 (队列)的容量足够大，算法中可以省去检查栈 (队列)满的情况。14. 栈和队列的应用1 . 表达式求值参见课本 P53。2 . 括号匹配例：检查表达式中的括号是否正确匹配。如 ( ) 正确，( ) 则错误。分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误。/ 检查输入的表达式中括号是否匹配bool MatchBrackets () constint M
39、AXSIZE = 1024; / 栈的最大容量char s MAXSIZE; / 简化的栈结构int top; / 栈顶/ 栈初始化top = 0; / 检查括号是否匹配ch = getchar(); while ( ch!=EOF ) switch ( ch ) case ?(?, ? , ? : 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 48 页 - - - - - - - - - s top+ = ch; / 所有左括号入栈break; case ?) :
40、if ( top=0 or s -top!= ( ) returnfalse; / 栈空或右括号与栈顶左括号失配case ? : if ( top=0 or s -top!= ) returnfalse; case ? : if ( top=0 or s -top!= ) return false ; ch = getchar(); / 取下一个字符 if ( top=0 ) return true; / 正好匹配elsereturn false ; / 栈中尚有未匹配的左括号 3 . 递归程序的非递归化将递归程序转化为非递归程序时常使用栈来实现。4 . 作业排队如操作系统中的作业调度中的作业
41、排队，打印机的打印作业也排成队列。5 . 按层次遍历二叉树voidLevelOrder ( BinTree bt, V isitFunc visit ) constint MAXSIZE = 1024; / 队列容量 (足够大即可 ) BinTree q MAXSIZE; / 简化的队列结构int front, rear; / 队头、队尾if ( ! bt ) return ; / 初始化队列，根结点入队列front = rear = 0; q rear = bt; rear = (rear+1)%MAXSIZE; / 队列不空，则取出队头访问并将其左右孩子入队列while ( front!=
42、rear ) p = q front; front = (front+1)%MAXSIZE; if ( p ) visit ( p-data ); / 访问结点q rear = p-lchild; rear = (rear+1)%MAXSIZE; q rear = p-rchild; rear = (rear+1)%MAXSIZE; 第四章串二、基础知识和算法1. 概念串，空串，空格串，串的长度；子串，子串在主串中的位置 ，主串；串相等。2. 串的基本操作表 0.1 串的基本操作Assign (s, t), Create (s, cs) Assign(s,t) 将变量 t 赋值给 s，Crea
43、te(s,cs) 根据字串创建变量 s。Equal (s, t), Length (s) 判断串相等，求串长度。如Length()=0。Concat (s, t) 串连接。如 Concat( ab , cd )= abcd 。Substr (s, pos, len) 取子串，pos 为开始位置，len 为子串长度。Index (s, t) 求子串 t 在主串 s中的位置。如 Index( abc , ab )=1，Index( a bc , bc )=3。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
44、- - - - 第 13 页，共 48 页 - - - - - - - - - Replace (s, t, v) 把串 s 中的字串 t 替换成 v。如 Replace( aaa , aa , a )= aa 。Delete (s, pos, len) 删除串 s的一部分。注：完成习题集 4.14.6。3. 串的存储结构表 0.2 串的存储结构定长顺序串最大长度固定，超过最大长度则作截断处理堆分配存储表示串的长度几乎没有限制块链存储表示块内存储空间连续，块间不连续第1章 树和二叉树一、基础知识和算法1. 树及有关概念树，根，子树；结点，结点的度 ，叶子（终端结点） ，分支结点（非终端结点）
45、，内部结点，树的度 ；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次 （根所在层为第 1层） ，深度，高度；有序树，无序树，二叉树是有序树； 森林。2. 二叉树二叉树（二叉树与度为 2 的树不同，二叉树的度可能是0，1，2） ；左孩子，右孩子。二叉树的五种基本形态。3. 二叉树的性质1 . 二叉树的第 i层10上至多有 2i-1个结点。2 . 深度为 k 的二叉树至多有 2k-1 个结点。满二叉树 ：深度为 k，有 2k-1 个结点。完全二叉树 ：给满二叉树的结点编号，从上至下，从左至右，n 个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1 到n。3 . 叶子结点 n0，度为 2 的结点为
46、 n2，则 n0= n2+1 。考虑结点个数： n = n0 + n1 + n2考虑分支个数： n-1 = 2n2 + n1可得 n0 = n2+1 例：1) 二叉树有 n 个叶子，没有度为 1 的结点，共有个结点。2) 完全二叉树的第 3层有 2个叶子，则共有个结点。分析：1) 度为 2 的结点有 n-1个，所以共 2n-1 个结点。 2) 注意考虑到符合条件的二叉树的深度可能是3或 4，所以有 5、10或11 个结点。4 . n 个结点的完全二叉树深度为1log n。5 . n 个结点的完全二叉树，结点按层次编号有：i 的双亲是2/n，如果 i = 1 时为根（无双亲）；i 的左孩子是 2
47、i ，如果2in，则无左孩子；i 的右孩子是 2i + 1，如果 2i + 1n 则无右孩子。10本书中约定根结点在第1 层，也有约定根在第0 层的，则计算公式会有所不同。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 48 页 - - - - - - - - - 4. 二叉树的存储结构1 . 顺序存储结构用数组、编号 i的结点存放在 i-1 处。适合于存储完全二叉树。2 . 链式存储结构二叉链表：typedefstruct BTNode DataType data;
48、struct BTNode *lchild, *rchild; BTNode, *BinTree; 三叉链表：typedefstruct BTNode DataType data; struct BTNode *lchild, *rchild, *parent; BTNode, *BinTree; 例：用二叉链表存储n个结点的二叉树 (n0)，共有(_a_)个空指针域；采用三叉链表存储，共有 (_b_)个空指针域。115. 二叉树的五种基本形态空树： bt=NULL 左右子树均空： bt-lchild=NULL and bt-rchild=NULL 右子树为空： bt-rchild=NULL
49、左子树为空： bt-lchild=NULL 左右子树均非空。前两种常作为递归结束条件，后三者常需要递归。6. 遍历二叉树1 . 常见有四种遍历方式按层次遍历，先序遍历，中序遍历，后序遍历。按层次遍历：“从上至下，从左至右”，利用队列。先序遍历：DLR；中序遍历 ：LDR ；后序遍历 LRD。例：写出 a+b*(c-d)-e/f的前缀、中缀和后缀表达式。画出二叉树，分别进行前序、中序、后序遍历即可得到。前缀表达式 ： - + a * b - c d / e f 中缀表达式 ： a + b * c - d - e / f 后缀表达式 ： a b c d - * + e f / - 2 . 先序遍历
50、算法voidPreorder ( BinTree bt ) if ( bt ) visit ( bt- data ); Preorder ( bt-lchild ); Preorder ( bt-rchild ); 11答案： (a) n+1 (b) n+2。提示：只有根结点没有双亲。data parent lchild rchild data rchild lchild - + / a * b - c d e f 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 48