数据结构知识点总结

1、计算机系列课程之间的联系,数据结构涵盖的内容,二.基本概念和术语,1.数据 数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中的并由计算机程序加以处理的符号的集合。其范围随着计算机技术的发展而不断发展。 2.数据元素 数据的基本单位是数据元素，在计算机程序中通常作为一个整体进行考虑和处理。 3.数据项 是数据的不可分割的最小单位，一个数据元素可由若干个数据项组成。 4.数据对象 性质相同的元素的集合叫做数据对象,5.结点 数据元素在机内的位串表示，即数据元素在计算机内的映象。 6.域/字段 当数据元素由若干个数据项组成时，位串中对应于各个数据项的子串称为域/字段，是数据元素中数据项

2、在计算机中的映象。 7.信息表 计算机程序所作用的一组数据通常称为信息表，是数据对象在计算机中的映象,8.数据结构 数据结构指的是数据元素之间的相互关系，这种关系是抽象的，即并不涉及数据元素的具体内容。是数据元素及其相互间的关系的数学描述。 9.逻辑结构和存储结构 (1)逻辑结构 数据结构中描述的是数据元素之间的抽象关系(逻辑关系)，称为逻辑结构。 (2)存储结构/物理结构 数据结构在计算机中的表示（映象）称为存储结构/物理结构,1.1.1基本概念和术语,3)数据元素之间的关系（逻辑结构）在计算机中有两种表示方法：顺序映象(表示)和非顺序映象(表示)，从而导致两种不同的存储结构：顺序结构和链式

3、结构。 顺序映象（表示）的特点是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 非顺序映象（表示）的特点是借助指示数据元素存储地址的指针来表示数据元素之间的逻辑关系,1.1.1基本概念和术语,返回,1.1.2四种基本的数据结构,1.集合结构,结构中的数据元素之间除了“属于同一个集合”的关系之外，别无其他关系。关系比较松散，可用其他结构来表示,结构中的数据元素之间存在一个对一个的关系，即线性关系，每个元素至多有一个直接前导和后继,2.线性结构,3.树型结构,结构中的数据元素之间存在一个对多个的关系，即层次关系，即每一层上的元素可能与下层的多个元素相关，而至多与上层的一个元素相关,

4、结构中的数据元素之间存在多个对多个的关系，即任意关系，任何元素之间都可能有关系,4.网状/图型结构,返回,1.1.3数据结构的研究对象,数据结构的研究对象(研究内容,1.数据对象的结构形式,各种数据结构的性质 (逻辑结构); 2.数据对象和”关系”在计算机中的表示 (物理结构/存储结构); 3.数据结构上定义的基本操作(算法); 4.算法的效率; 5.数据结构的应用,如数据分类,检索,返回,数据结构的作用图,数据 结构,数据关系,数 据 表 示,数 据 类 型,数学 离散数学 应用数学,硬件 存储设备 总体结构,软件 系统软件 应用软件,算法 设计 数据 运算,编码 理论 数据 组合,系统设计

5、 数据存取,2.1 算法及其性能评价准则,算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令（规则）的有限序列，其中每一条指令表示一个或多个操作,算法的特征： 有穷性、确定性、 能行性、输入、 输出,算法描述： 自然语言；程序设计语言；类语言,一、算法、算法的特征和算法描述,常用的算法设计方法： 递归法（Recursion）、分治法(Divide-and Conquer)、 贪心法(Greedy)、动态规划(Dynamic Programming)、 搜索与遍历、回溯（Backtracking）、解空间局部搜索 近似算法(Approximation)、在线算法（On-Line

6、）等,2.2 算法时间复杂性分析方法,定理2.1 若 A（n）=amnm+a1n+a0 是关于n的m次多项式，则 A（n）=（nm） *此定理说明，时间复杂性仅取决于多项式的最高次幂，而与最高次幂的系数和其他低次项无关 （1）表示实践复杂性为常数 常见的时间复杂性及其比较 （1） （n） （n） （n） （nn） （n2） （n3） （2n,设T1(n)=O( f(n) )，T2(n)=O( g(n) )，则 加法规则：T1(n)+T2(n) = O( max f(n), g(n) ) 乘法规则：T1(n)*T2(n) = O( f(n)* g(n) ) 1. 表达式和赋值语句:O(1,2.

7、语句序列:用加法规则,取耗时最多语句. 3. 条件语句:O(1) 4. FOR语句:O(N*M)N为循环次数,M为体内时间最多的语句 5. WHILE语句:找出与循环次数有关的变量,通过计算找出上下限,例: x=n; y=0; while (x=(y+1)(y+1) y=y+1; 时间复杂性为O,s = 0 ; f(n) = 1; T2(n) = O(f(n) = O(1)常量阶,for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j ) +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n) = O(n2) 平方阶,for (

8、i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ; k = n; +k ) cij += aik * bkj ; f(n) = 2n3+3n2+2n+1; T4(n) = O(f(n) = O(n3) 立方阶,for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T1(n) = O(f(n) = O(n) 线形阶,第三章 线性表（Liner List,知识点： 线性表的逻辑结构和各种存储表示方法 定义在逻辑结构上的各种基本运算（操作） 在各种存储结构上如何实现这些基本运算 各种基

9、本运算的时间复杂性,重点： 熟练掌握顺序表和单链表上实现的各种算法及相关的时间复杂性分析,难点： 使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题,3.1 抽象数据型线性表,定义 线性表是由n(n0)个相同类型的元素组成的有序集合。 记为： ( a1,a2,a3,ai-1,ai,ai+1, an,其中： n为线性表中元素个数，称为线性表的长度； 当n=0时，为空表，记为（ ）。 ai为线性表中的元素，类型定义为elementtype a1为表中第1个元素，无前驱元素；an为表中最后一个 元素，无后继元素；对于ai-1,ai,ai+1(1in)，称ai-1 为ai的直接前驱，ai+1

10、为ai的直接后继。(位置概念！） 线性表是有限的，也是有序的,3.1 抽象数据型线性表,线性表 LIST = ( D , R) D = ai | ai Elementset , i = 1, 2, , n, n 0 R = H H = | ai-1, ai D , i = 2 , , n,操作：设L的型为LIST线性表实例，x 的型为elementtype的元素 实例，p 为位置变量。所有操作描述为： Insert(x, p, L) Locate(x, L) Retrieve(p, L) Delete(p, L) Previous(p, L), Next(p, L) MakeNull( L)

11、First( L) End(L,数学模型,3.1 抽象数据型线性表,举例：设计函数 Deleval（LIST,3.2 线性表的实现,问题：确定数据结构（存储结构）实现型LIST，并在此基础上 实现各个基本操作,存储结构的三种方式： 连续的存储空间（数组） 静态存储 非连续存储空间指针（链表） 动态存储 游标（连续存储空间+动态管理思想） 静态链表,3.2.1 指针和游标,指针：地址量，其值为另一存储空间的地址； 游标：整型指示量，其值为数组的下标，用以表示指定元素 的“地址” 或 “位置”（所在的数组下标,3.2.2 线性表的数组实现,顺序表： 把线性表的元素逻辑顺序依次存放在数组的连续单元内

12、，再用一个整型量表示最后一个元素所在单元的下标,特点： 元素之间的逻辑关系（相继/相邻关系）用物理上的相邻关系来表示（用物理上的连续性刻画逻辑上的相继性）； 是一种随机存储结构，也就是可以随机存取表中的任意元素，其存储位置可由一个简单直观的公式来表示,3.2.2 线性表的数组实现,类型定义： # define maxlength 100 struct LIST elementtype elements maxlength; int last; ; 位置类型： typedef int position; 线性表 L: LIST L; 表示： L.elementsp / L的第p个元素 L.las

13、t L的长度，最后元素的位置,3.2.2 线性表的数组实现,操作,void Insert ( elementtype x, position p, LIST /时间复杂性：O(n,position Locate ( elementtype x , LIST L ) position q ; for ( q = 1; q = L.last ; q+ ) if ( L.elements q = x ) return ( q ) ; return ( L.last + 1 ); /时间复杂性：O(n,3.2.2 线性表的数组实现,elementtype Retrieve ( position p ,

14、 LIST L ) if ( p L.last ) error( “指定元素不存在” ) ; else return ( L.elements p ) ; /时间复杂性：O(1,void Delete( position p , LIST /时间复杂性：O(n,3.2.2 线性表的数组实现,position Previous( position p , LIST L ) if ( ( p L.last ) ) error ( “前驱元素不存在” ) ; else return ( p 1 ); /时间复杂性：O(1,position End( LIST L ) return( L.last +

15、 1 ); / O(1,position First( LIST L ) return ( 1 ); /复杂性：O(1,position Next( position p , LIST L ) if ( ( p = L.last ) ) error ( “前驱元素不存在” ) ; else return ( p + 1 ); /时间复杂性：O(1,position MakeNull( LIST /时间复杂性：O(1,3.2.2 线性表的数组实现,3.2.3 线性表的指针实现,单链表：一个线性表由若干个结点组成，每个结点均含有两个域： 存放元素的信息域和存放其后继结点的指针域，这样就形成一个 单

16、向链接式存储结构，简称单向链表或单向线性链表,结构特点： 逻辑次序和物理次序不一定相同； 元素之间的逻辑关系用指针表示； 需要额外空间存储元素之间的关 系； 非随机存储结构,3.2.3 线性表的指针实现,操作讨论,3.2.3 线性表的指针实现,插入元素,p,a) 表头插入元素,b) 中间插入元素,c) 表尾插入元素,q = new celltype ; qelement = x ; qnext = pnext ; pnext = q,或: temp = pnext ; pnext = new celltype ; pnextelement = x ; pnextnext = temp,讨论表头

17、结点的作用,操作讨论,3.2.3 线性表的指针实现,删除元素,q = pnext ; pnext = qnext ; delete q,或： q = pnext ; pnext = pnextnext ; delete q,讨论结点 ai 的位置 p,操作,3.2.3 线性表的指针实现,position End ( LIST L) position q ; q = L ; while ( qnext != NULL ) q = qnext ; return ( q ) ; /时间复杂性：O(n,void Insert ( elementtype x, position p) position

18、q ; q = new celltype ; q element = x ; q next = p next ; p next = q ; /时间复杂性：O(1,操作,3.2.3 线性表的指针实现,position Locate ( elementtype x, LIST L ) position p ; p = L ; while ( pnext != NULL ) if ( pnextelement = x ) return p ; else p = pnext ; return p ; /时间复杂性：O(n,elementtype Retrieve ( position p) retur

19、n ( p next element ); /时间复杂性：O(1,操作,3.2.3 线性表的指针实现,void Delete( position p) position q ; if ( pnext != NULL ) q = p next ; p next = q next ; delete q ; /时间复杂性：O(1,position Previous ( position p) position q ; if ( p = Lnext ) error ( “不存在前驱元素” ) ； else q = L ; while ( qnext != p ) q = qnext ; return

20、q ; /时间复杂性：O(n,操作,3.2.3 线性表的指针实现,position Next ( position p) position q ; if ( pnext = NULL ) error ( “不存在后继元素” ) ； else q = pnext; return q ; /时间复杂性：O(1,position MakeNull ( LIST /时间复杂性：O(1,操作,3.2.3 线性表的指针实现,position First ( LIST L ) return L; /时间复杂性：O(1,静态链表 与 动态链表的 比较,比较参数 表的容量 存取操作 时间 空间,链式存储 灵活，

21、易扩充 顺序存取 访问元素费时间 实际长度，节省空间,顺序存储 固定，不易扩充 随机存取 插入删除费时间 估算表长度，浪费空间,举例：遍历线性链表，按照线性表中 元素的顺序，依次访问表中的 每一个元素，每个元素只能被 访问一次,void Travel( LIST L ) position p ; p = Lnext ; while ( p != NULL) cout pelement ; p = pnext ;,单链表逆置问题: 方法一: 设表头为L,算法如下: p=L-next-next; q=p-next; L-next-next=NULL; while(p!=null) p-next=L

22、-next; L-next=p; p=q; q=q-next;,方法二:线性表由q来 表示 p=null; w=q; while(w!=null) w=w-next; q-next=p; p=q; q=w;,3.2.5 双向链表,双向连表：在单向链表中，对每个结点增加一个域，用一指向该结点的前驱结点。线性表的这种存储结构称为 双向链表,优点： 实现双向查找（单链表不易做到） 表中的位置i 可以用指示含有第i 个结点的指针表示。 缺点：空间开销大,3.2.5 双向链表,操作,删除位置p的元素： void Delete( position p, DLIST,void Insert( element

23、type x, position p, DLIST,3.2.6 环形链表,对线性链表的改进，解决“单向操作”的问题；改进后的链表，能够从任意位置元素开始，访问表中的每一个元素,单向环形链表：在(不带表头结点)的单向链表中，使末尾结点的指 针域指向头结点，得到一个环形结构；用指向末尾结点的指针标识 这个表,存储结构:与单向链表相同(略,操作：在表左端插入结点Insert(x,FIRST(R),R); LInsert(x,R) void LInsert( elementtype x , LIST,3.2.6 环形链表,在表右端插入结点Insert(x,END(R),R); RInsert(x,R)

24、 void RInsert( elementtype x , LIST R ) LInsert ( x , R ) ; R = Rnext ;,操作：从表左端删除结点Delete(First(R),R); LDelete(R) void LDelete( LIST,3.2.6 环形链表,3.2.6 环形链表,双向环形链表的结构与双向连表结构相同，只是将表头元素 的空previous域指向表尾，同时将表尾的空next域指向表头结点， 从而形成向前和向后的两个环形链表，对链表的操作变得更加灵 活,举例：设计算法，将一个单向环形链表反向。头元素变成尾 元素，尾元素变成新的头元素，依次类推,3.2.6

25、 环形链表,3.3 栈（Stack,栈是线性表的一种特殊形式，是一种限定性数据结构，也就是在对线性表的操作加以限制后，形成的一种新的数据结构,定义：是限定只在表尾进行 插入和删除操作的线性表。 栈又称为后进先出 (Last In First Out )的线性表。 简称LIFO结构,栈举例,3.3 栈,栈的基本 MakeNull ( S ) 操作 Top ( S ) Pop ( S ) Push ( x , S ) Empty ( S,举例：利用栈实现行编辑处理。 设定符号“#”为擦讫符，用以删 除“#”前的字符；符号“”为删 行符，用以删除当前编辑行。 原理： 一般字符进栈； 读字符 擦讫符退

26、栈； 删行符则清栈,3.3.1 栈的实现,3.3 栈,1、顺序存储,顺序栈示意图,top,类型定义： enum BoolenTRUE,FALSE typedef struct elementtype elementsmaxlength; int top ; STACK ; STACK S,栈的容量：maxlength 1 ; 栈空：S.top = 0 ; 栈满：S.top = maxlength 1 ; 栈顶元素：S.elements S.top,3.3.1 栈的实现,1、顺序存储,操作,void MakeNull( STACK,Boolean Empty( STACK S ) if ( S.

27、top 1 ) return TRUE else return FALSE ;,elementtype Top( STACK S ) if Empty( S ) return NULL; else return ( S.elements S.top );,3.3.1 栈的实现,1、顺序存储,操作,void Pop( STACK,void Push ( elementtype x, STACK,3.3.1 栈的实现,2、链式存储,采用由指针形成的线性链表来实现栈 的存储,要考虑链表的哪一端实现元素的插 入和删除比较方便。 实现的方式如右图所示，其操作与线 性链表的表头插入和删除元素相同,stru

28、ct node Elementtype val; node * next; ; typedef node * STACK,void MakeNull (STACK,void Pop ( STACK,boolean Empty(STACK S) if (S-next) return FALSE; else return TRUE;,多个栈共用一个存储空间的讨论,3.4 排队或队列（Queue,队列是对线性表的插入和删除操作加以限定的另一种限 定性数据结构。 定义 将线性表的插入和删除操作分别限制在表的两端进行， 和栈相反，队列是一种先进先出（First In First Out，简称 FIFO

29、结构）的线性表,操作：MakeNull(Q)、Front(Q)、EnQueue(x, Q)、DeQueue(Q)、Empty(Q,3.4 队列（Queue,3.4.1 队列的指针实现,元素的“型”： struct celltype elementtype element ； celltype *next ；,队列的 “型”： struct QUEUE celltype *front ； celltype *rear ；,3.4.1 队列的指针实现,操作： void MakeNull( QUEUE,Boolean Empty( Q ) QUEUE,elementtype Front ( Q )

30、QUEUE Q ; return Q.frontnextelement ;,3.4.1 队列的指针实现,void EnQueue ( elementtype x, QUEUE,void Delete ( QUEUE,3.4.2 队列的数组实现,队列的 “型”： struct QUEUE elementtype element maxlength ; int front ； int rear ；,随着不断有元素出队和进队 （插入和删除），队列的状 态由1变成2；此时an占据队 列的最后一个位置；第n+1 个元素无法进队,但实际上， 前面部分位置空闲,3.4.2 队列的数组实现,解决假溢出的方法有

31、多种；一是通过不断移动元素位置， 每当有元素出队列时，后面的元素前移一个位置，使队头元 素始终占据队列的第一个位置。 第二种方法是采用循环队列,插入元素： Q.rear = (Q.rear + 1） % maxlength 删除元素： Q.front = (Q.front + 1） % maxlength,队空： (Q.rear + 1）% maxlength = Q.front 队满： (Q.rear + 1 ) % maxlength = Q.front,3.4.2 队列的数组实现,问题：如何解决循环队列中队空与队满状态相同,方法一：约定队列头指针在队列尾指针的下一位置上； 方法二：另设一

32、个标志位用以区别队空与队满两种状态,结论：两种方法的代价是相同的,操作： int addone( int i ) return ( ( i + 1）% maxlength ) ; void MakeNull ( QUEUE,boolean Empty( Q ) QUEUE Q ; if ( addone(Q.rear) = Q.front ) return TRUE ; else return FALSE ;,3.4.2 队列的数组实现,操作： elementtype Front( QUEUE Q ) if ( Empty( Q ) ) return NULL ; else return (Q

33、.elements Q. front ); void EnQueue ( elementtype x, QUEUE Q ) if ( addone ( addone( Q.rear ) ) =Q.front ) error ( “队列满” ) ; else Q.rear = addone ( Q.rear ) ; Q.elements Q.rear = x ;,3.4.2 队列的数组实现,void DeQueue ( QUEUE Q ) ; if ( Empty ( Q ) ) error ( “空队列” ) ; else Q.front = addone ( Q.front ) ;,3.6

34、串( String,串是线性表的一种特殊形式，表中每个元素的类型为字符型，是一个有限的字符序列。 串的基本形式可表示成：S = a1a2a3an ； 其中：char ai ； 0 i n ；n 0 ； 当 n = 0 时，为空串。 n 为串的长度,C 语言中串有两种实现方法： 1、字符数组，如：char str110 ； 2、字符指针，如：char *str2,3.6.1 抽象数据型串,3.6.2 串的实现,1、串的顺序存储 采用连续的存储空间（数组），自第一个元素开始，依次 存储字符串中的每一个字符。 char str 10 =“China,操作：NULL，ISNULL，IN，LEN，CON

35、CAT，SUBSTR，INDEX,2、串的链式存储 构造线性链表，element类型为char，自第一个元素开始，依 次存储字符串中的每一个字符,3.7 数组( ARRAY,3.7.1 抽象数据型数组,数组是由下标（index）和值（value）组成的序对 （index，value）的集合。 也可以定义为是由相同类型的数据元素组成有限序列。 数组在内存中是采用一组连续的地址空间存储的，正是 由于此种原因，才可以实现下标运算。 所有数组都是一个一维向量,数组1：( a1, a2, a3, , ai , , an ),数组2：( a11, , a1n, a21, , a2n, , aij , ,

36、am1, , amn ) ; 1im, 1jn,数组3: ( a111, , a11n, a121, , a12n, , aijk , , amn1, , amnp ) ; 1 i m, 1 j n , 1 k p,3.7.2 数组的实现,1、数组的顺序存储,数组的顺序表示，指的是在计算机中，用一组连续的存 储单元来实现数组的存储。目前的高级程序设计语言都是这 样实现的。 两种存储方式： 一是按行存储（C语言、PASCAL等） 二是按列存储（FORTRAN等,elementtype A23,1、数组的顺序存储,对二维数组有： LOC（Aij ）= LOC（A00）+ n i + j ， 0 i

37、 m-1，0 j n-1 对三维数组有： LOC（Ai1i2i3 ）= LOC（A000）+ d2d3 i1 + d3i2 + i3， 0 i1 d1-1，0 i2 d2-1，0 i3 d3-1,2、数组的压缩存储,特殊矩阵 若n 阶矩阵 A 中的元素满足下述性质 aij = aji 1 i, j n 则称 n 阶对称阵。 对于对称矩阵, 为实现节约存储空间, 我们可以为每一对对称 元素分配一个存储空间, 这样, 原来需要的 n2 个元素压缩存 储到 n(n+1)/2 个元素空间,对称关系： 设sa 0 . . n(n+1)/2 做为 n 阶对称阵 A 的存储结构, 则 Sa k 和 aij

38、的一一对应关系为: i ( i + 1 ) / 2 + j 当 i j k = j ( j + 1 ) / 2 + i 当 i j,2） 稀疏矩阵,稀疏矩阵中，零元素的个数远远多于非零元素的个数。为 实现压缩存储，仍考虑只存储非零元素,第4章 树,1、一个结点 x 组成的集 x 是一株树，这个结点 x 也是这株树的根。 2、假设 x 是一个结点，T1，T2，Tk是 k 株互不相交的树，我们可以构造一株新树：令 x 为根，并有 k 条边由 x 指向树T1，T2，Tk。这些边也叫做分支， T1，T2，Tk称作根 x 的树之子树（SubTree,树的构造性递归定义,递归定义，但不会产生循环定义,一株

39、树的每个结点都是这株树的某株子树的根,注意,树的逻辑结构特点,除根结点之外，每株子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。即一对多的关系，反映了结点之间的层次关系,结点的度(元结点的度(元）和树的度 叶结点（终端结点） 非终端结点（分支结点） 子结点（儿子、子女） 父结点（双亲） 兄弟（结点） ）和树的高,路（径）长 祖先（结点） 后代（子孙） 结点层、结点的高 路（路径,有序树 无序树 森林,森林forest： 是 n 0 株互不相交的树的集合,二叉树: 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点和两棵分别称为左子树和右子树的、互不相交的二叉树组成

40、,结构特点: 每个结点最多只有两个孩子结点，即结点的度不大于2 ,子树有左右之别，子树的次序（位置）不能颠倒,基本形态,4.2.1 二叉树的定义及遍历,高度为K且有2K-1个结点的二叉树称为满二叉树,设二叉树高度为K，称满足下列性质的二叉树为完全二叉树 （1）所有的叶都出现在K或K-1层； （2）K-1层的所有叶都在非终结结点的右边； （3）除了K-1层的最右非终结结点可能有一个（只能是左分支）或两个分支之外，其余非终结结点都有两个分支,二叉树的遍历,根据某种策略，按照一定的顺序访问二叉树中的每一个结点，使每个结点被访问一次且只被访问一次。结果得到二叉树结点的线性序列,根（D）、左孩子（L）和

41、右孩子（R）三个结点可能出现 的顺序有： DLR LDR LRD DRL RDL RLD,要讨论的三种操作分别为,先根顺序DLR， 中根顺序LDR， 后根顺序LRD,策略：左孩子结点一定要在右孩子结点之前访问,先根顺序遍历二叉树： 若二叉树非空则： 访问根结点； 先根顺序遍历左子树； 先根顺序遍历右子树；,中根顺序遍历二叉树： 若二叉树非空则： 中根顺序遍历左子树； 访问根结点； 中根顺序遍历右子树；,后根顺序遍历二叉树： 若二叉树非空则： 后根顺序遍历左子树； 后根顺序遍历右子树； 访问根结点；,所得到的线性序列分别称为先根（序）、中根（序）和后根（序）序列,如图所示的二叉树，对其进行先序、

42、中序和后序遍历都是从根结点A开始的，且在遍历过程中经过结点的路线是一样的，只是访问的时机不同而已,性质1 二叉树的第 i 层最多有 2i-1 个结点。(i 1) 证明用数学归纳法 性质2 高度为 K 的二叉树最多有 2K - 1个结点。(K 1) 证明用求等比级数前 K 项和的公式 20 + 21 + 22 + + 2K = 2K - 1 性质3 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2 的非叶结点有 n2 个, 则有 n0 n2 1 证明：若设度为1的结点有 n1 个，结点总数为 n，分支总 数为 B，则根据二叉树的定义， n = n0 + n1 + n2 B = 2n2 +

43、n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1,4.2.2 二叉树的性质,性质4 具有 n (n 0) 个结点的完全二叉树的高度为 log2(n + 1) 或 log2 n + 1 证明：设完全二叉树的高度为 K，则有 2K-1 - 1 n 2K - 1 变形 2K-1 n + 1 2K 2K-1 n 2K 取对数 K-1 log2(n+1) K K-1 log2 n K 因此有 log2(n+1) = K K = log2 n + 1,性质5 完全（或满）二叉树的顺序存储结构及其性质 如果将一棵有n个结点

44、的完全二叉树自顶向下，同一层自左向右连续给结点编号, 1, 2,n，且使该编号对应于数组的下标，则有以下关系： 若i = 1, 则 i 是根结点，无父结点 若i 1, 则 i 的父结点为i/2 若 2*i n, 则 i 有左儿子且为 2*i；否则，i 无左儿子。 若2*i+1 n, 则 i 有右儿子且为2*i+1；否则，i 无右儿子。 若 i 为偶数, 且 i n , 则有右兄弟，且为 i + 1。 若 i 为奇数, 且 i n if ( ! IsEmpty ( BT ) ) visit ( DATA ( BT ) ) ; Preorder ( LCHILD ( BT ) ) ; Preord

45、er ( RCHILD ( BT ) ) ;,例1-1：写一个递归函数，按先根顺序列出二叉树 中每个结点的DATA 域之值,例1-2：写一个递归函数，按 中根顺序列出二叉树 中每个结点的DATA 域之值,void Inorder ( BT ) BTREE BT ; if ( ! IsEmpty ( BT ) ) Inorder ( LCHILD ( BT ) ) ; visit ( DATA ( BT ) ) ; Inorder ( RCHILD ( BT ) ) ;,例1-3：写一个递归函数，按后根顺序列出二叉树中每个结点的DATA域之值,void Postorder ( BT ) BTRE

46、E BT ; if ( ! IsEmpty ( BT ) ) Postorder ( LCHILD ( BT ) ) ; Postorder ( RCHILD ( BT ) ) ; visit ( DATA ( BT ) ) ;,二元树的遍历的 非递归过程,void NInorder( BT ) BTREE BT; STACK S ; BTREE T ; MakeNull( S ) ; T = BT ; while ( !IsEmpty( T ) | Empty ( S ) ) if ( !IsEmpty ( T ) ) Push( T ,S ); T = T LCHILD ( T ) ; e

47、lse T = Top ( S ) ; Pop ( S ) ; visit( DATA( T ) ) ; T = T RCHILD ( T ) ;,进栈; 左走一步,退栈; 右走一步,一、顺序表示 1、完全（或满）二叉树,根据性质5，如已知某结点的层序编号i,则可求得该结点的 双亲结点、左孩子结点和右孩子结点,采用一维数组，按层序顺序依次存储二叉树 的每一个结点。如下图所示,4.2.4 二叉树的表示,二、左右链表示,struct node struct node *lchild ; struct node *rchild ; datatype data ; ; typedef struct n

48、ode * BTREE,三、二叉树的线索表示线索二叉树,若结点p有左孩子，则p-lchild指向其左孩子结点，否则令其指向其（先序、中序、后序）前驱； 若结点p有右孩子，则p-rchild指向其右孩子结点，否则令其指向其（先序、中序、后序）后继； 同时在每个结点中增加两个标志位，以区分该结点的的两个链域是指向其左/右孩子还是指向某种遍历的前驱/后继,struct node datatype data ; struct node *lchild , *rchild ; enum bool lchild , rchild ;,typdef struct node * THTREE,p-ltag,T

49、RUE p-lchild 指向左孩子 FALSE p-lchild 指向（中序）前驱,算法：求$p（中序前驱,分析：(1) 当p-ltag=FALSE时，p-lchild 即为所求（线索）。 (2) 当p-ltag=TRUE时，$p为p 的左子树的最右结点,THTREE InPre( THTREE p) THTREE Q ; Q=p-lchild ; if (p-ltag = = TRUE ) while(Q-rtag = = TRUE) Q = Q-rchild ; return ( Q ) ;,void PreOrder( BTREE T ) STACK S; Makenull(S); /

50、递归工作栈 struct node * p = T; while ( p != NULL ) cout data rchild != NULL ) Push (S, p-rchild ); if ( p-lchild != NULL ) p = p-lchild; /进左子树 else p=Top(S); Pop(S); /左子树空, 访问右子树,例 先序遍历的非递归算法栈顶保存当前结点的右子树,void Preorder(BTREE bt) STACK S; BTREE t; t=bt ; Makenull(S); while(t != null| !Empty(S) whlie (t !=

51、 null) visit(t-data); push(t ,S); t=t-lc; if (!Empty(S) t=top (S) ; pop (S) ; t= t - rc;,例先序遍历的非递归算法栈顶保存当前结点的左子树,4.3.1 树的三种遍历,先根顺序 访问根结点 ； 先根顺序遍历T1 ; 先根顺序遍历T2 ; 先根顺序遍历Tk,中根顺序 中根顺序遍历T1 ; 访问根结点 ； 中根顺序遍历T2 ; 中根顺序遍历Tk,后根顺序 后根顺序遍历T1 ; 后根顺序遍历T2 ; 后根顺序遍历Tk ; 访问根结点,先根遍历序列:RADEBCFGHK 中根遍历序列:DAERBGFHKC 后根遍历序列

52、:DEABGHKFCR,D,A,E,R,B,C,F,G,H,K,4.3.2 树的存储结构,1、树的数组表示法（双亲表示、父链表示、单链表示,首先，对树T的结点按下列规则依次编号： 根结点编号为1； 对于T中的每一个已编号的结点k ，按从左到右的顺序对k 的儿子结点编号。 然后，令树T 的结点编号与一个结构体数组的下标对应，结 构体数组的每个单元包括两个域：parent和data域，且规定,Ai.data=结点i 的数据域的值,父链表示,struct node int parent ; char data ;,typedef node TREE11; TREE T,存储结构,基本操作的实现,结构

53、特点： 每个结点均保存父结点所在的数组单元下标 兄弟结点的编号连续,易求父结点、祖先结点： 如i 的父结点的父结点TTi.parent.parent 易求结点数据域的值：Ti.data 不便于CREATEk操作,2、树的邻接表表示法（孩子表示法、孩子链表表示法,typedef struct CTNode int child ; struct CTNode *next ; *ChildPtr ; typedef struct Telementtype data ; ChildPtr firstchild ; CTBox ; typedef struct CTBox nodesMAX_TREE_S

54、IZE ; int n , r ; Ctree,1、结点结构,2、存贮示例,因每个结点有且仅有两个指针域，所以也称为二叉树表示方法,3、树的（左）孩子（右）兄弟表示法（二叉树表示法,类型：typedef struct CSNode /动态存储结构 ElemType data; struct CSNode *firstchild , *nextsibling ; ; typedef struct CSNode *TREE,森林（树）转换为二元树,连线：把每株树的各兄弟结点连起来； 把各株树的根结点连起来（视为兄弟） 抹线：对于每个结点，只保留与其最左儿子的连线，抹去该结 点 与其它结点之间的连线

55、 旋转：按顺时针旋转45度角（左链竖画，右链横画,4.5 树的应用,没有度数为1的结点 外结点数 =内结点数 + 1(为什么?) 有 n 个外结点的扩充二元树共有 2n-1 个结点,4.5.3 哈夫曼（Huffman）树及其应用,在二叉树中，对于每个结点，若出现空（左/右）子树，则 为其加上一个特殊的结点（称为外结点），由此得到的新二叉 树称为原二叉树的扩充二叉树。而原二叉树的结点称为内结点,一、哈夫曼树的由来及其构造,内路径长 I = 21+32+13 = 11 外路径长 E = 12+53+24 = 25,2. 扩充二元树的外路径长、内路径长及相互关系,外路径长E：从根结点到每个外结点的路

56、径长之和，E=l j 内路径长 I：从根结点到每个内结点的路径长之和 关系： E = I2n (n为内结点的个数,4.5.3 哈夫曼（Huffman）树及其应用,设： w i = 2 , 3 , 4 , 11,求：wj l j（加权路长,a）111422333=34 （b）213243113=53 （c）221123242=40,3. 扩充二元树的加权路径长,外结点的加权路径长： 设每个外结点 j 对应一个实数w j （称为外结点的权值）， l j 是从根到外结点 j 的路长，则 wj l j个称为外结点 j 的加权路长。 扩充二元树的加权路长: WPL = wj l j称为扩充二元树的加权路

57、长,4.5.3 哈夫曼（Huffman）树及其应用,哈夫曼树定义: 在给定权值为w 1 ， w 2 w n的 n 个叶结点所构成的所有扩 充二叉树中，WPL = wj l j最小的称为huffman树。 在哈夫曼树中，权值越小，离根越远；权值大的结点离根最近,构造算法: (1) 由给定的 n 个权值 w0, w1, w2, , wn-1，构造具有 n 棵扩充二叉树的森林 F = T0, T1, T2, , Tn-1 ，其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。 (2) 重复以下步骤, 直到 F 中仅剩下一棵二叉树为止： 在 F 中选取两棵根结点的权值最小

58、的扩充二叉树, 做为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F,哈夫曼树（最优二叉树,F : 7 5 2 4,F : 7 5 6,7,5,2,4,0-初始,1-合并2 4,F : 7 11,7,5,2,4,7,5,2,4,6,6,11,2-合并5 6,F : 18,5,3-合并7 11,2,7,4,6,11,18,举例,编码和译码,哈夫曼（Huffman）树及其应用,是指将文件（字符集）中的每个字符转换为一个唯一的二进制串,编码,解码）是指将二进制串转换为对应的字符,译码,对于给定的字符集，可

59、能存在多种编码方案，但应选择最优的,3.编码的前缀性,对字符集进行编码时，如果任意一个字符的编码都不是其它任何字符编码的前缀，则称这种编码具有前缀性或前缀编码,前缀 编码,注意,等长编码具有前缀性； 变长编码可能使译码产生二义性，即不具有前缀性。 如, E(00), T(01), W(0001), 则译码时无法确定信息串是ET还是W,最优编码（Huffman编码,Huffman编码问题和编码算法,对于给定的字符集以及每个字符出现的概率（使用频度），求字符集的最优的前缀性编码Huffman编码问题,用huffman算法求字符集最优编码的算法,使字符集中的每个字符对应一株只有叶结点的二叉树，叶的权值为对应字符的使用频率； 利用huffman算法来构造一株huffman树； 对huffman树上的每个结点，左支附以0，右支附以1（或者相反），则从根到叶的路上的0、1序列就是相应字符的编码,Huffman编码问题和编码算法,哈夫曼（Huffman）树及其应用,举例,第5章图及其相关算法,图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷非空集合； E = (x, y) | x, y V 或 E = | x, y V是顶