导图社区 数据结构导论
- 5.1k
- 533
- 141
- 举报
数据结构导论
一张思维导图带你学懂计算机专业重要的专业基础课-数据结构导论知识点汇总。该导图详细著明了数据结构的基本概念，线性表、栈、串、队列和数组、树结构和图结构，以及查找和排序等基本运算。如果有帮到你，不妨动动手指帮我点赞呀！
提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。
- 相似推荐
- 大纲
数据结构导论
一 概论
1.1 数据结构（Data structure）
数据结构主要研究
数据（计算机加工对象）的逻辑结构
实现各种基本操作的算法
学习数据结构的目的
➢掌握常用的数据结构及其应用
➢学会合理地组织数据， 有效地表示数据和处理数据
➢掌握算法设计技术和分析技术
➢掌握使用计算机解决问题的方法和技能，提高程序设计水平
数据结构定义
是计算机组织数据和存储数据的方式
是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的存储方式，以及定义在该组数据上的一组操作
数据的逻辑结构：是指数据及数据的组织方式
数据结构、算法 和 程序 的关系
算法 + 数据结构 = 程序
(1976年瑞士计算机科学家尼克劳斯·维尔特[Niklaus Wirth]提出)
计算机解决问题的步骤
1.2 基本概念和术语
数据（Data)
所有能被计算机处理的符号的集合
数据元素（Data Element）
是数据这个集合中的一个个体即数据的基本单位
数据项（Data Item）
数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位
数据库中，数据项又称为字段 / 域。它是数据的不可分割的最小标识单位。
实际问题中的数据称为原始数据
逻辑结构（Logical Structure）
指数据元素之间的结构关系
数据的逻辑结构(D, {R}) 可分为下列几种: D = {d1,d2, …, dn}
集合
数据元素同“属于一个集合”。R = { }。
任意两个结点之间都没有邻接关系，组织形式松散
线性结构
R= {(d1, d2), (d2, d3), …, (dn-1, dn)}，即除起始节点和终端结点d1、dn外，每个节点有一个前驱和一个后继
结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接
树形结构
(D, {R}) 构成树，即每个元素最多有一个前驱，可以有多个后继
具有分支、层次特性，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接
图结构
(D, {R})构成一个图
最复杂，任何两个结点都可以相邻接
物理结构（Physical Structure）/存储结构
指数据结构在机内的表示，数据的逻辑结构在计算机中的实现
数据的存储结构
存储结构的主要部分
存储结点（每个存储结点存放一个数据元素）数据元素之间关联方式的表示
数据结构的存储=数据元素的存储+元素逻辑关系的存储
顺序结构
借助数据元素的相对存储位置来表示数据的逻辑结构
线性表的顺序存储方法
将表中的结点一次存放在计算机内存中一组连续的存储单元中
顺序的方法
将元素存储到一片连续的存储区
特点
预先分配好长度，需要预估存储数据需要的存储量
插入和删除需要移动其他元素
存取快捷，是随机存取结构
链式结构
链式存储方式
借助数据元素地址的指针表示数据的逻辑结构
这种结构是给结点附加一个指针字段，指出其后继节点的位置，即存放结点的存储单元分为两部分
特点
动态分配，不需要预先确定内存分配
插入和删除不需要移动其他元素
非随机存取结构
索引存储方式
借助索引表中的索引指示各存储节点的存储位置
散列存储方式
用散列函数指示各节点的存储位置
数据组织的3个层次
1.3 算法及描述
算法
算法规定了求解给定类型问题所需的所有“处理步骤”及执行顺序，使给定类型问题能在有限时间内被机械的求解
一个算法是对特定问题求解步骤的一种描述，它是指令的有穷序列
特性
有穷性: 一个算法总是在执行有穷步后结束
确定性: 算法的每一步都必须是明确地定义的
可行性: 算法中的每一步都是可以通过已经实现的操作来完成的
输入: 一个算法有零个或者多个输入，这些输入取自于特定的对象集合
输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量
算法必须使用某种语言描述
程序
介于自然语言和程序设计语言的伪代码
非形式算法（自然语言）
框图(N-S图)
类C语言描述算法
1.4 算法分析
算法的设计应满足
正确性
对于合法的输入产生符合要求的输出
易读性
算法应该易读、便于交流， 这也是保证算法正确性的前提；添加注释也是一种增加可读性的办法
健壮性
当输入非法数据时， 算法还能做出适当的反应而不会崩溃， 如输出错误信息；算法中应该考虑适当的错误处理
时空性
指算法的时间复杂度和空间复杂度，算法分析主要分析算法的时间复杂度和空间复杂度，目的是提高算法的效率
选择最优算法的2个度量
时间复杂度
算法运行时需要的总步数，通常是问题规模的函数
空间复杂度
算法执行时所占用的存储空间，通常是问题规模的函数
确定算法的计算量
合理地选择一种或几种操作作为“标准操作”，无特殊说明，默认以赋值语句作为标准操作
确定每个算法共执行多少次标准操作，并将此次数规定为该算法的计算量
时间复杂度
最坏情况时间复杂度和平均情况时间复杂度统称为时间复杂度
算法的最坏情况时间复杂度：以算法在所有输入下的计算量的最大值作为算法的计算量
算法的平均情况时间复杂度：以算法在所有输入下的计算量的加权平均值作为算法的计算量
例：设变量a、b、c、d中各含一个整数，求a、b、c中的最大值与d的乘积：算法max1的最坏情况时间复杂度为5；算法max2的最坏情况时间复杂度为3
/*编制函数求1！+2！+ ... + n！算法一*/ int fact1(int n) { int i,j,temp,s; s = 0; for (i = 1; i <= n; i++) { temp = 1; for (j = 1; j <= i; j++) temp = temp*j; s = s + temp; } return s; }// 2重循环，时间复杂度O(n^2)
/*编制函数求1！+2！+ ... + n！算法二*/ int fact2(int n) { int i,temp,s; s = 0; temp = 1; for (i = 1; i <= n; i++) { temp = temp*i; s = s + temp; //存储每次阶乘和值 } return s; }// 时间复杂度O(n)
常见的时间复杂度按数量级递增排列依次为
各种时间复杂度与时间的关系
空间复杂度
是对一个算法在运行过程中临时占用存储空间大小的量度
一个算法在执行期间所需要的存储空间量包括
程序代码所占用的空间
输入数据所占用的空间
辅助变量所占用的空间
估算算法空间复杂度时，一般只分析辅助变量所占用的空间
【例】读入n=100个整数到一个数组中，写出实现将该组数进行逆置的算法，并分析算法的空间复杂度。 下面的空间复杂度（辅助变量占用的空间量）：O(1) void f1(int a[],int n) { int i,temp; for (i=0;i<=n/2-1;i++) { temp=a[i] a[i]=a[n-1-i]; //当i=0时，首地址为：a[0]；尾地址为：a[n-1] a[n-1-i]=temp; //共用temp一个空间，就一个 } }
空间占用大O(n)
二 线性表
2.1 线性表的基本概念
字母表(A,B,C,D….Z)
数字表(0,1,2,3,4,5,6,7,8,9)
学生名单
线性表的逻辑结构
线性表是一种最简单、最常见的数据结构
线性表是由n（n≥0）个数据元素（结点）a1，a2，a3，……an组成的有限序列。 数据元素的个数n定义为表的长度。 当n=0时，称为空表
例： 线性表：1，2，3，4，5，6，7，8，9，10。 表的长度：10。
将非空的线性表（n＞0）记作：L=（a1，a2，a3，……，an）
a1：起始结点，an：终端结点。 a1称为a2的直接前驱，a3称为a2的直接后继……
例： 线性表：L=（1，2，3，4，5，6，7，8，9，10） 起始结点：1，终端结点：10。 2是3的直接前驱，4是3的直接后继……
线性表L=（1，2，3，4，5，6，7，8，9，10）
线性表中只有1个起始结点，1个终端结点， 起始结点没有直接前驱，有1个直接后继。 终端结点有1个直接前驱，没有直接后继。 除这2个结点外，每个结点都有且只有1个直接前驱和1个直接后继
2.2 线性表顺序存储的方法
将表中的结点依次存放在计算机内存中一组连续的存储单元中
数据元素在线性表中的邻接关系决定其在存储空间中的存储位置
即逻辑结构中相邻的结点，其存储位置也相邻
用顺序存储实现的线性表称为顺序表
例：假定有一组数据，数据间有顺序： 12，10，5，78，56，45，32，88，71，11
此处，数据间的顺序，表示数据间的逻辑关系即线性关系，这一组数据为线性表
线性表的顺序存储结构
12 10 5 78 56 45 32 88 71 11 0 1 2 3 4 5 6 7 8 9
顺序表的结构体定义
Const int Maxsize = 100; typedef struct { DataType data[Maxsize]; int length; } Seqlist; Seqlist L ;
【例】
结构体
➢ 结构体是一种构造数据类型 ➢ 用途：把不同类型的数据组合成一个整体-------自定义数据类型 ➢ 引入结构体的好处：加强数据项之间的联系 如学生的基本信息，包括学号、姓名、性别、年龄、班级、成绩等数据项。这些数据项描述了一个学生的几个不同侧面。
顺序表上的基本运算
插入（Insert）、删除（Delete）、定位（Locate）
插入 InsertSqlist(L, x, i)
线性表的插入运算是指在表的第 i 个位置上，插入一个新结点 x，使长度为 n 的线性表（a1，a2，……，ai，……，an）变为长度为 n+1 的线性表（a1，……，x，……，an+1）
注意！ 当表空间已满，不可再做插入操作。 当插入位置是非法位置，不可做正常的插入操作
顺序表插入操作过程
将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第 i 个位置。
在第i个位置上插入新结点x。
（当插入位置i=n+1时，无须移动结点，直接将x插入表的末尾）该顺序表长度加1
例：在位置3插入新结点x=66
在第3个位置插入新结点时，要移动（10-3+1）=8个数据
算法
void InsertSeqlist(SeqList L, DataType x, int i) //⭐⭐⭐算法要会 5步 { //将元素 x 插入到顺序表 L 的第 i 个数据元素之前,两个判断 if (L. length == Maxsize) exit(“表已满”); //Maxsize，表的存储空间 if (i < 1 || i > L. length+1) exit(“位置错”)； //检查插入位置是否合法 for(j = L.length; j >= i; j--) //初始 i=L.length L.data[j] = L.data[j-1]; //依次后移,直到第 i 个位置（包括 i） L.data[i-1] = x; //元素 x 置入到下标为 i-1 的位置(数组下标从0开始，序号-1,即第i个位置) L.length++; //表长度加 1 }
需要判定顺序表是否为满
插入算法的分析
假设线性表中含有 n 个数据元素，在进行插入操作时，有 n+1 个位置可插入;在第 i 个位置插入时，要移动 n-i+1 个数据
删除 DeleteSeqList( L, i )
线性表的删除运算是指将表的第i个结点删去，使长度为n的线性表（a1，a2，……，ai，……，an）变成长度为n-1的线性表（a1，a2，……，ai-1，ai+1，……，an-1）
注意！ 当要删除元素的位置 i 不在表长范围内时，为非法位置，不能做正常的删除操作
顺序表删除操作过程
若 i = n，则只要删除终端结点，无须移动结点；
若 1 ≤ i ≤ n-1，则必须将表中位置 i+1，i+2，……，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。 （仅当删除位置 i=n 时， 才无须移动结点，直接令表长度length-1即可）
该表长度减1
例：在位置3删除结点75
在第3个位置删除结点时，要移动（10-3）= 7 个数据
例：设顺序表A长度为100，若下标从1开始计数，则删除元素A[10]需要移动__90__个元素
例：在表长为n的顺序表上做删除运算，其平均时间复杂度为（O(n) ）
删除算法的分析
假设线性表中含有 n 个数据元素，在进行删除操作时，有 n 个位置可删除，在第i个位置删除时，要移动 n-i 个数据
算法
void DeleteSeqList( SeqList L, int i ) { //3步 //删除线性表 L 中的第 i 个数据结点 if(i < 1 || i > L.length) //检查位置是否合法 exit(“非法位置”); for(j = i; j < L.length; j ++) //从第 i 个元素开始，对第 i 个元素后面的元素做前移（包括 i） L.data[j-1] = L.data[j]; //依次左移 L.length--; //表长度减 1 }
定位 LocateSeqlist(L,X)
定位运算LocateSeqlist(L,X)的功能是求 L 中值等于 X 的结点序号的最小值，当不存在这种结点时结果为0。 从第一个元素a1起，依次和 x 比较， 直到找到一个与 x 相等的数据元素，则返回它在顺序表中的存储下标或序号；当查遍整个表都没找到与x相等的元素，返回0
例：查找值为75的元素
例：顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为（O(n)）
定位算法的分析
定位运算的功能是查找出线性表 L 中值等于 x 的结点序号的最小值，当不存在这种结点时，结果为 0
i从0开始，作为扫描顺序表时的下标
最好情况下，第1个元素就是x值，此时查找比较次数为 1 。 最坏情况下，最后1个元素是x值，此时查找比较次数为 n 。 故平均查找长度为（n+1）/2
算法
int LocateSeqlist(SeqList L, DataType x) { int i = 0; while ((i < L. length) && (L.data[i] != x) ) //在顺序表中查找值为 x 的结点 i++; if(i < L.length) return i+1; //若找到值为 x 的元素，返回元素的序号 else return 0; //未查找到值为 x 的元素，返回 0 } //顺序表的求表长操作，直接输出 L.length 即可
结论：顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要考虑
2.3 线性表的链接存储
链式存储方式（运算实现）
链表（Link List）
链接方式存储的线性表
具体存储
用一组任意的存储单元来存放
链表中结点的逻辑次序和物理次序不一定相同，还必须存储指示其后继结点的地址信息
线性表中数据为（11，12，22，34，45）：用一组地址任意的存储单元存放线性表中的数据元素
单链表的一般图示法
由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针
单链表特点
链表由头指针唯一确定，单链表可以用头指针的名字来命名。头指针名是head3的链表可称为表head3
起始节点又称为首结点，无直接前驱，故在无头结点时，设头指针head指向首结点
终端结点又称尾结点，无直接后继，故终端结点的指针域为空，即NULL
除头结点之外的结点为表结点，为运算操作方便，头结点中不存数据
单链表的组成
注意
单链表各个结点在内存中的存储位置并__不一定__连续
单链表与顺序表相比，其特点是（不需要预先分配存储空间）
在一个长度为n(n>1)的单链表上，设有头和尾两个指针，下列操作与链表长度有关的是（删除单链表中的最后一个元素）
结点结构
data域——存放结点值的数据域
next域——存放结点的直接后继的地址（位置）的指针域（链域）
单链表的每个结点包括___数据域___和指针域
NULL
空指针
Head
头指针
尾指针
指向最后一个元素（尾结点）的指针
头结点
一般不存数据，利用Head存放该结点地址
第一个结点之前增设一个类型相同的结点为了便于运算的实现,在单链表的，称之为_头结点_。
所有结点通过指针链接而组成
1.单链表初始化
建立一个空的单链表L，InitiateLinkList（L）
keep trying(-20%)--->getting there...(30%)--->Nice going...(85%)
一个空的单链表是一个头指针和一个头结点构成的
初始化的算法
单链表的类型定义
// 单链表类型定义 typedef struct node { DataType data; //数据域 struct node * next; //指针域：存放该结点的直接后继结点的地址;此处嵌套定义 } Node , *LinkList ;
空表初始化算法
// 单链表空表初始化 LinkList InitiateLinkList() //建立一个空的单链表 { LinkList head; //头指针，以head命名 head = malloc(sizeof(Node)); //动态构建一结点，它是头结点 head -> next = NULL; return head; }
/* malloc函数用法 malloc函数：产生头结点。开辟新空间，如Java中的 new ... malloc函数的使用格式及作用：前面可带类型强转语句 （数据类型*）malloc（sizeof(数据类型)）sizeof()：度量大小 如：int p ; p = (int *) malloc(sizeof(int)) */
在算法中，变量head是链表的头指针，它指向新创建的结点，即头结点。一个空单链表仅有一个头结点，它的指针域为NULL
例：在表达式中，符号p->next表示（p所指的链结点的下一个链结点的地址 ）。
2.求表长LengthLinkList
在单链表存储结构中，表长等于单链表所含结点的个数（不含头结点）
设置一个工作指针p，初始时，p指向头结点，并设置一个计数器cnt，初值设置为0。然后，让工作指针p通过指针域逐个结点向尾结点移动，工作指针每向尾部移动一个结点，让计数器加1。直到工作指针p->next为NULL时，说明已经直到了表的尾部，这时已完成对所有结点的访问，计数器cnt的值即是表的长度。
步骤(走指针，计数)
1，令计数器 j 为 0 2，令 p 指向头结点 3，当下一个结点不空时/while ( p->next != NULL )，j 加 1，p 指向下一个结点 4，j 的值即为链表中结点个数，即表长度
算法
int lengthLinklist ( LinkList head ) { Node *P ; p = head; j = 0; while ( p->next != NULL ) //指针p所指的结点为最后一个结点 { p = p->next ; //指针p指向后继结点 j++; } return( j ); }
特别注意：p = p->next的作用
3.读表元GetLinkList
步骤
1、令计数器 j 为 0 2、令p指向头结点 3、当下一个结点不空时，并且 j<i 时/while (( j < i ) && ( p != NULL) )， j 加 1，p 指向下一个结点 4、如果 j 等于 i，则p所指结点为要找的第i结点， 否则，链表中无第 i 结点
Node * GetLinkList( LinkList head, int i ) { Node *p; p = head->next ; int j = 1; while (( j < i ) && ( p != NULL) ) { p = p->next; j++; } if ( i == j ) return( p ); else return (NULL); }
例：已知指针p指向单链表中某个结点，则语句p ->next=p ->next->next的作用是___删除p的直接后继结点_____。
4.定位LocateLinkList
定位运算是对给定表元素的值，找出这个元素的位置。对于单链表，给定一个结点的值，找出这个结点是单链表的第几个结点。定位运算又称为按值查找
具体步骤
1、令 p 指向头结点
2、令 i = 0
3、当下一个结点不空时，p 指向下一个结点，同时 i 的值加 1
4、直到 p 指向的结点的值为 x，返回 i+1 的值。
5、如果找不到结点值为 x 的话，返回值为 0
定位运算算法描述
int LocateLinkList(LinkList head, DataType x) //求表head中第一个值等于x的结点的序号，若不存在这种结点，返回结果为0 { Node *p = head; //p是工作指针 p = p->next; //初始时p指向首结点 int i = 0; //i代表结点的序号，这里置初值为0 while (p != NULL && p->data != x) //访问链表 { i++; p=p->next; } if (p!=NULL) return i+1; else return 0; }
5.插入
有头插入法和尾插入法两种，头插入法把顺序逆置了
具体步骤
1）找到 ai-1 存储位置q （一定要先找到 ai-1 的指针 q，这也是链表设立头结点的原因，方便运算的实现）
2）生成一个数据域为x的新结点*p
3）新结点的指针域指向结点ai
4）令结点*q的指针域指向新结点
程序实现
void InsertLinklist (LinkList head, DataType x, int i) //在表head的第 i 个数据元素结点之前插入一个以 x 为值的新结点 { Node *p,*q; if (i==1) q = head; else q = GetLinklist (head, i-1); //找第 i-1个数据元素结点 if (q==NULL) //第i-1个结点不存在 exit(“找不到插入的位置”); else { p=malloc(sizeof (Node) );p->data=x; //生成新结点并赋值 p->next = q->next; //新结点链域指向*q的后继结点 q->next = p; //修改*q的链域 } }
在q所指结点后插入p所指结点
注意：链接操作p->next=q->next和q->next=p两条语句的执行顺序不能颠倒，否则结点*q的链域值（即指向原表第i个结点的指针）将丢失
例：已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ s->next = p->next ; p->next = s ;
例：在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是________和________。 s->next->next=p->next; p->next=s;
例：若频繁地对线性表进行插入和删除操作，该线性表应该采用（链式 ）存储结构
6.删除
算法思路（此算法描述删除第i个结点）
找到第 i-1 个结点；若存在继续，否则结束
删除第 i 个结点，并释放对应的内存，结束
算法步骤
删除运算是将表的第 i 个结点删去
1）找到 ai-1 的存储位置 q
2）令p-＞next指向ai 的直接后继结点
3）释放（free）结点ai 的空间，将其归还给"存储池"
在单链表中删除第 i 个结点的基本操作为:找到线性表中第 i-1 个结点，修改其指向后继的指针
p = q->next ; q->next = p->next ; free(p);
程序实现
void DeleteLinklist(LinkList head, int i) //删除表head的第i个结点 { Node *q; if(i==1) q = head; else q=GetLinklist(head, i-1); //先找待删结点的直接前驱 if(q !== NULL && q->next != NULL) //若直接前驱存在且待删结点存在 { p = q->next; //p指向待删结点 q->next = p->next; //移出待删结点 free(p); //释放已移出结点p的空间 } else exit (“找不到要删除的结点”); //结点不存在 }
注意：free(p)是必不可少的，因为当一个结点从链表移出后，如果不释放它的空间，它将变成一个无用的结点，它会一直占用着系统内存空间，其他程序将无法使用这块空间
2.4.其他运算在单链表上的实现（建表）
这个过程分为三步
首先建立带头结点的空表
其次建立一个新结点，然后将新结点链接到头结点之后，这个结点为尾结点（也是首结点）
复建立新结点和将新结点链接到表尾这两个步骤，直到线性表中所有元素链接到单链表中。这里用int代替DataType
方法一
通过已实现的插入算法InsertLinkList ( LinkList head,int x,int i )来实现，依次增大插入位置 i，使新的结点链入到链表中
LinkList CreateLinkList1() // 通过调用 InitiateLinkList 和 InsertLinkList 实现建表算法。假定0是输入结束标志 ｛LinkList head; int x,i; head = InitateLinkList(); //建立空表，此处调用了建表函数 i = 1; //置插入位置初值，表头为0 scanf("%d",&x); //读入第一个数据元素，x为整型 while(x != 0); //输入的不是结束标志时继续插入，用循环实现 { InsertLinkList(head , x , i); //将输入插入到head表尾，调用链表插入函数 i++; //修改插入位置 scanf("%d",&x); //读下一元素 } return head; }
方法二（尾插法）
上面的算法由于每次插入都从表头开始查找，比较浪费时间。因为每次都是把新的结点链接到表尾，我们可以用一个指针指向尾结点，这样就为下一个新结点指明了插入位置
LinkList CreateLinkList2() // q是一个LinkList类型的变量，用来指示链入位置 { LinkList head; //建链式结构表，以head命名 Node *q,*t; int x; head = malloc(sizeof(Node)); //生成头结点，开辟空间 q = head; //尾指针置初值 scanf("%d",&x); //读入每一个元素 while(x != 0) //输入的不是结束标志时继续链入 { t = malloc(sizeof(Node));t->data = x; //生成一个新结点并赋值 q->next = t; //将新结点 t 链入 q = t; //修改尾指针q,指向新的尾结点 scanf("%d",&x); //读入下一个元素 } q->next = NULL; return head; //q指向尾结点，置尾结点标志 }
时间复杂度O(n)
方法三（头插法）(类顺序栈)
LinkList CreateLinkList3() { LinkList head; Node *p; int x; head = malloc(sizeof(Node));//生成头结点 head->next = NULL; scandf("%d",&x); while(x) //x = 0 时结束输入 { p = malloc(sizeof(Node)); p->data = x; p->next = head->next; //前插：插入到链表的第一个结点处 head->next = p; scanf("%d",&x); } return head; } //最终形成的链表的数据顺序与输入顺序正好相反，时间复杂度也是O(n)
1.清除单链表中值为 x 的重复结点
步骤
1）找到值为 x 的第一个结点位置，p 指向该结点 2）从 p 所指结点开始向后查找， 若存在值为 x 的结点，令q指向x结点前一个 执行删除操作 继续查找直到链表末尾
2. 清除单链表中所有重复结点
逐步求精法分析：
整体步骤
i=1 While（ ai 不是终端结点 ） { 删除ai+1 到an 结点中值为ai 的结点 i++ }
当未到达链表末尾时（ai 不是终端结点时）
删除ai+1 到an 结点中值为ai 的结点 i++
进一步细化步骤：
当未到达链表末尾时（ai 不是终端结点时） 删除ai+1 到an 结点中值为ai 的结点 j=i while （j<n） { if( aj ==ai ) 删除aj j++ } i++ }
删除重复结点
void PurgeLinklist( LinkList head ) //删除表head中多余的重复结点 { Node *p, *q, *r; q = head->next; //q指示当前检查结点的位置，置其初值指向首结点 while(q != NULL) //当前检查结点*q不是尾结点时，寻找并删除它的重复结点 { p = q; //工作指针p指向*q while(p->next != NULL) //当*p的后继结点存在时,将其数据域与*q数据域比较 { if (p->next->data == q->data) //若*(p->next)是*q的重复结点 { r = p->next; //r指向待删结点 p->next = r->next; //移出结点* (p->next)，p->next指向原来* (p->next)的后继结点 free (r); } else p = p->next; //否则，让p指向下一个结点 } q=q->next; //更新检查结点 } }
2.5循环链表
普通循环链表
普通链表的终端结点的next值为NULL 循环链表的终端结点的next指向头结点 在循环链表中，从任一结点出发能够扫描整个链表 一般频繁做插入删除操作应采用链式存储结构
如何找到普通链表的尾结点
在循环链表中附设一个rear指针指向尾结点适用于经常适用头尾结点的链表操作中
例：若p为指向循环链表中某链结点的指针变量，判断循环链表是否只有一个结点的标志是______。 p->next=p
例：非空的循环单链表head的尾结点（由p所指向）满足： p->next == head;
循环链表判空
带有头结点的循环链表 head -> next == head
设有尾结点的循环链表 rear ->next == rear
双向循环链表
在链表中设置两个指针域， 一个指向后继结点 一个指向前驱结点 这样的链表叫做双向链表
prior data next 双向链表的结点
struct dbnode //double node { DataType data; struct dbnode *prior, *next; }; typedef struct dbnode *dbpointer; typedef dbpointer DLinkList; //以上两行语句有些啰嗦，可以简化为 typedef struct dbnode *DLinkList; 假设双向链表中p指向某节点 则有 p->prior->next 与p->next->prior相等
双向循环链表适合应用在需要经常 查找结点的前驱和后继的场合。找 前驱和后继的复杂度均为：O(1)。
双向链表中结点的删除
设p指向待删结点，删除*p
(1) p->prior->next = p->next; // p 前驱结点的后链指向p的后继结点 (2) p->next->prior = p->prior; // p 后继结点的前链指向p的前驱结点 (3) free(p); //释放*p的空间 （1）、（2）这两个语句的执行顺序可以颠倒
双向链表中结点的*p后插入
在p所指结点的后面插入一个新结点*t，需要修改四个指针:（先搭上，再修改指针） (1) t->prior = p; (2) t->next = p->next; (3) p->next->prior = t; (4) p->next = t; 注意：（1）（2）可颠倒，（3）（4）不可颠倒，（12）和（34）不能颠倒
双向链表中结点的*q前插入*p
在非空双向循环链表中由q所指的那个链结点前面插入一个p所指的链结点的动作对应的语句依次为：p->next=q；p->prior=q->prior；q->prior=p；p->prior->next=p；
2.6 顺序实现与链式实现的比较
线性表与链表的优缺点
(1)单链表的每个结点包括数据域与指针域，指针域需要占用额外空间。 (2)从整体考虑，顺序表要预分配存储空间，如果预先分配得过大，将造成 浪费，若分配得过小，又将发生上溢；单链表不需要预先分配空间，只 要内存空间没有耗尽，单链表中的结点个数就没有限制。
时间性能的比较
顺序表
读表元素 O（1） 定位（找x） O（n） 插入 O（n） 删除 O（n）
链表
读表元素 O（n） 定位（找x） O（n） 插入 O（n） 删除 O（n）
三 栈、队列和数组
3.1 栈
栈的基本概念
栈是只能在表的一端（表尾）进行插入和删除的线性表； 其中：. 允许插入及删除的一端（表尾）称为栈顶(Top)； . 另一端（表头）称为栈底(Bottom)。 . 当表中没有元素时称为空栈。 S =（a1 ，a2 ，a3 ，…, an ） a1: 栈底元素 an: 栈顶元素 . 进栈——在栈顶插入一元素； . 出栈——在栈顶删除一元素。
例：一叠书或一叠盘子
栈的特点——后进先出 栈中元素按a ，a ，a ，…a 的次序进栈，出栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。 因此，栈称为后进先出线性表（LIFO）。
栈的基本操作
栈的用途——常用于暂时保存有待处理的数据 /*比如Seqstack.h头文件，C语言就有。再如请求CPU的执行权，运用栈队列的形式来保护程序现场*/
栈的基本运算
（1）初始化栈：InitStack(S); （2）判栈空： EmptyStack (S); （3）进栈： Push (S,x); （4）出栈： Pop (S); （5）取栈顶： GetTop(S);
栈的顺序实现——顺序栈
顺序栈及常用名词
顺序栈—— 即栈的顺序实现； 栈容量——栈中可存放的最大元素个数； ● 栈顶指针top——指示当前栈顶元素在栈中的位置； ● 栈空——栈中无元素时，表示栈空； ● 栈满——数组空间已被占满时，称栈满； ● 下溢——当栈空时，再要求作出栈运算，则称“下溢”； ● 上溢——当栈满时，再要求作进栈运算，则称“上溢”。
注意：出栈的时候，不管是顺序栈还是链栈，都要先判空[顺序栈Seqstk->top == 0],[链栈LkStk->next == NULL]；进栈时，顺序栈需要判满[Seqstk->top == maxsize -1]，而链栈则不需要判满，因为链式存储是来一个开辟一个空间的形式
栈的顺序实现
顺序栈的类型定义
const int maxsize=6; typedef struct seqstack { DataType data[maxsize]; int top; }SeqStk; <-- 顺序栈类型
SeqStk *s ; /*定义一顺序栈s*/ 约定栈的第1个元素存在data[1]中,则： s->top==0 代表顺序栈s为空； s->top==maxsize -1 代表顺序栈s为满；
顺序栈的运算
➢初始化
1）初始化 int Initstack(SeqStk *stk) { stk->top = 0; return 1; }
➢判栈空
2) 判栈空 int EmptyStack(SeqStk *stk) { if(stk->top= =0) return 1; else return 0;} 栈空时返回值为1，否则返回值为0。
➢进栈
3) 进栈 int Push( SeqStk *stk, DataType x ){ /*数据元素x进顺序栈sq*/ if（stk->top==maxsize -1) /*判是否上溢*/ { error(“栈满”);return 0;} /*上溢*/ else { stk->top++；/*修改栈顶指针，指向新栈顶*/ stk->data[stk->top]=x; /*元素x插入新栈顶中*/ return 1; } }
➢出栈
4)出栈 int Pop( SeqStk *stk ){ /*顺序栈sq的栈顶元素退栈*/ if（stk->top == 0） /*判栈空，是否下溢*/ { error(“栈空”);return 0;} /*下溢*/ else { stk->top-- ； /*修改栈顶指针，指向新栈顶*/ return 1; } }/*Pop*/
➢取栈顶元素
5) 取栈顶元素(引用型操作，读取一下，不改变栈元素) DataType GetTop( SeqStk *stk ) { if(EmptyStack(stk)) return NULLData; else return stk->data[stk->top]; }
例：在某些应用中，为了节省空间，让两个数据元素类型一致的栈共享一维数组空间data[max]，成为双栈，两个栈的栈底分别设在数组两端，让两个栈彼此迎面“增长”，两个栈的栈顶变量分别为top1、top2（top2 >top1），仅当两个栈的栈顶位置在中间相遇时（top1+1=top2）才发生“上溢”。
栈的链接实现-链栈
链栈的定义
栈的链式存储结构称为链栈，它是运算的受限单链表，插入和删除操作仅限制在表头位置上进行。栈顶指针就是链表的头指针
链式栈的类型说明如下： typedef struct node{ DataType data; //下溢条件：LS->next==NULL struct node *next //上溢：不考虑栈满现象 } LkStk; //<-- 链栈类型
链栈的基本运算
➢ 1)初始化 void InitStack(LkStk *LS) { LS=(LkStk *)malloc(sizeof(LkStk)); LS->next=NULL; }
➢ 2）判栈空 int EmptyStack(LkStk *LS) { if(LS->next= =NULL) return 1; else return 0; }
➢3）进栈——在栈顶插入一元素x //不需要判栈满 ● 生成新结点（链栈不会有上溢情况发生，来一个malloc一下...） ● 将新结点插入链栈中并使之成为新的栈顶结点 void Push ( LkStk *LS, DataType x ) { LkStk *temp; //定义指针变量 temp temp = (LkStk *) malloc (sizeof (LkStk)); //给 temp 所指结点开空间 temp->data = x; //赋值给 temp 结点的数据域 temp->next = LS->next; //头插法进栈 LS->next = temp; }
进栈
➢4）出栈——在栈顶删除一元素，并返回 ● 考虑下溢问题,不需考滤上溢 ● 不下溢，则取出栈顶元素，从链栈中删除栈顶结点并将结点回归系统。 int Pop ( LkStk *LS ) { LkStk *temp; //定义指针变量 temp if ( ! EmptyStack (LS)) //判栈空 { temp = LS->next;//把 temp 指针指向首结点，相当于复制了此栈（首结点除外） LS->next = temp->next; //修改指针，可写成LS->next = LS->next->next free( temp ); //删除 temp 所指结点，即出栈 return 1; } else return 0; }
出栈
➢ 5）取栈顶元素 DataType GetTop( LkStk *LS ) { if ( !EmptyStack(LS) ) return LS->next->data; else return NULLData; }
栈的应用举例
设栈的输入序列依次为1,2,3,4，则所得的输出序列不可能是____b____ 。 a 1,2,3,4 b 4,2,3,1 c 1,3,2,4 d 3,4,2,1
设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列，即输出出栈操作得到的数据元素的排列
分析：共有五种可能的输出序列
输出ABC，A进，A出，B进，B出，C进，C出；
输出BCA，A进，B进，B出，C进，C出，A出；
输出BAC，A进，B进，B出，A出，C进，C出；
输出CBA，A进，B进，C进，C出，B出，A出；
输出ACB，A进，A出，B进，C进，C出，B出。
写一个算法，借助栈将下图所示的带头结点的单链表逆置
void ReverseList(LkStk *head) { LkStk *S; DataType x; InitStack(S); // 初始化链栈 p = head->next; while(p != NULL) // 扫描链表 { Push(S,p->data); // 元素进栈 p = p->next; } p = head->next; while (!EmptyStack(S)) //栈不为空时 { p->data = Gettop(S); // 元素填入单链表中 Pop(S); // 出栈 p = p->next; } }
【例】阅读程序片段，写出运行结果
const int maxsize = 50; typedef struct seqstack { char data[maxsize]; int top; }SeqStk; main() { SeqStk stk; int i; char ch; InitStack(&stk); for(ch = 'A';ch <= 'A'+10;ch++) { Push(&stk,ch); printf("%c",ch); } printf("\n"); while(!EmptyStach(&stk)) { ch = GetTop(&stk); pop(&stk); printf("%c",ch); } printf("\n"); }
运行结果
ABCDEFGHIJK
KJIHGFEDCBA
递归与递归的阅读
递归的定义
如果一个函数在完成之前又调用自身，则称之为递归函数
求整数n的阶乘函数 n!
n*(n-1)! 当n>1时
1 当n=1时
程序实现
int f (int n) { if(n==0) return(1); else return n*f (n-1); }
递归的一般形式
void fname(参数表) { if( 数据作为递归出口 ) 简单操作; else { 简单操作; fname( 参数表 );简单操作; [fname( 参数表 );简单操作;] //可能有多次调用 } }
3.2 队列
队列的基本概念
队列( Queue )也是一种运算受限的线性表。 ▲队列——是只允许在表的一端（rear）进行插入，而在另一端（front）进行删除的线性表。 其中：允许删除的一端称为队头(front)，允许插入的另一端称为队尾(rear)。 队列 Q=(a1 ，a2 ，a3 ，…an ) 例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开 队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1 ,a2 ,…a n之后，a 是队头元素，a 是队尾元素。显然退出队列的次序也只能是 a1 ,a2 ,…an ，也就是说队列的修改是依先进先出的原则进行的。 ▲队列特点：先进先出（FIFO） 队列的用途——常用于暂时保存有待处理的数据。
▲示意图
▲队列的基本操作
➢ 队列初始化 InitQueue(Q): 设置一个空队列Q； ➢ 判队列空 EmptyQueue(Q): 若队列Q为空，则返回值为1，否则返回值为0； ➢ 入队列 EnQueue(Q , x): 将数据元素x从队尾一端插入队列，使其成为队列的新 尾元素； ➢ 出队列 OutQueue(Q): 删除队列首元素； ➢ 取队列首元素GetHead(Q): 返回队列首元素的值。
队列的顺序实现
用一维数组作为队列的存储结构 队列容量—队列中可存放的最大元素个数 约定： 初始： front=rear=0 进队：rear增1，元素插入尾指针所指位置 出队：front增1，取头指针所指位置元素 队头指针front—— 始终指向实际队头元素的前一位置 队尾指针rear —— 始终指向实际队尾元素 const int maxsize=20; typedef struct seqqueue { DataType data[maxsize]; int front, rear ; }SeqQue; SeqQue sq; ➢入队列操作：Sq.rear=Sq.rear+1; Sq.data[Sq.rear]=x; ➢出队列操作：Sq.front=Sq.front+1; 图a为空队列，sq.rear=0,sq.front=0。 图b为20入队列后，sq.rear=1,sq.front=0。 图c为30,40,50依次入队列后，sq.rear=4,sq.front=0。 图d为20,30,40,50依次出队列后，sq.rear=4,sq.front=4。 图e为60入队列后，sq.rear=5,sq.front=4。
顺序队列
——只能从数组的一头插入、另一头删除。 SeqQue sq ； ●上溢条件：sq.rear = = maxsize-1 ( 队满 ) ●下溢条件：sq.rear = = sq.front ( 队列空 ) ● 假溢出：sq.rear == maxsize-1，但队列中实际容量并未达到最大容量的现象。 极端现象：队列中的项不多于1,也导致“上溢” ; 浪费空间 为克服“假溢出”引入了循环队列
循环队列
循环队列注意点
（1） 定义——为队列分配一块存储空间(数组表示)，并将 这一块存储空间看成头尾相连接的。 ● 头指针front——顺时针方向落后于实际队头元素一个位置 ● 尾指针rear ——指向实际队尾元素 ● 循环的实现 ▲ 对插入即入队：队尾指针增1 SQ.rear=(SQ.rear+1)%maxsize；//然后再赋值如下 SQ.data[SQ.rear] = x ▲ 对删除即出队：队头指针增1 SQ.front=(SQ.front+1)%maxsize ● 循环队列类型定义： typedef struct Cycqueue { DataType data[maxsize]; int front,rear; } CycQue; CycQue CQ; ★ 规定：循环队列CQ 下溢条件即队列空： CQ.front==CQ.rear 上溢条件即队列满： 尾指针从后面追上头指针 即：(CQ.rear+1)%maxsize==CQ.front （尾赶头） （浪费一个空间，队满时实际队容量=maxsize-1） （2）循环队列运算 ▲ 入队——在队尾插入一新元素x ● 判上溢否？是，则上溢返回； ● 否则修改队尾指针（增1），新元素x插入队尾。 ▲ 出队——删除队头元素，并返回 ● 判下溢否？是，则下溢返回； ● 不下溢，则修改队头指针，取队头元素。
示意图
循环队列示意图
上溢、下溢条件图解
循环队列的基本运算
➢ 1.队列的初始化 void InitQueue(CycQue CQ) { CQ.front=0; CQ.rear=0;} ➢ 2.判队列空 int EmptyQueue(CycQue CQ) { if (CQ.rear==CQ.front) return 1; else return 0;} ➢ 3.入队列 int EnQueue(CycQue CQ,DataType x) {if ((CQ.rear+1) % maxsize == CQ.front) //判满条件 { error(“队列满”);return 0;} else { CQ.rear = (CQ.rear+1) % maxsize; //队尾+1 CQ.data[CQ.rear] = x; //赋值 return 1;} } /* 队列满条件为：((CQ.rear+1) % maxsize==CQ.front)成立 队列空条件为：(CQ.rear==CQ.front)成立 */ ➢ 4.出队列 int OutQueue(CycQue CQ) {if (EmptyQueue(CQ)) { error(“队列空”)；return 0；} else { CQ.front = (CQ.front+1) % maxsize; return 1；} } ➢ 5.取队列首元素 DataType GetHead(CycQue CQ) { if (EmptyQueue(CQ)) return NULLData； else return CQ.data[(CQ.front+1) % maxsize]; }
【例】
设循环队列的元素存放在一维数组Q[30]中，队列非空时，front指示队列首结点的前一个位置，rear指示队列尾结点。如果队列中元素的个数为10,front的值为25，则rear应指向的元素是（B）。//有多少个元素，就是直接加队首的值如：(25+10)%30 = 5 A、Q[4] B、Q[5] C、Q[14] D、Q[15]
解析
队列的链式实现—链队列
链式队列的定义
链式队列的定义 ▲链式队列——用链表表示的队列，即它是限制仅 在表头删除和表尾插入的单链表。 附设两指针： 头指针front——指向表头结点；队头元素结点为front->next 尾指针rear——指向链表的最后一个结点（即队尾结点） ▲链队列类型说明： 可将队头和队尾这两个指针封装在一起，将链队列的类型定义为一个结构 类型： typedef struct LinkQueueNode { DataType data; struct LinkQueueNode *next; } LkQueNode； typedef struct LkQueue { LkQueue *front ,*rear; } LkQue; LkQue LQ ; LQ.front—链式队的队头指针 LQ.rear — 链式队的队尾指针 ▲链式队的上溢：可不考虑；（因动态申请空间） ▲链式队的下溢：即链式队为空时，还要求出队； 此时链表中无实在结点： LQ.front->next==NULL LQ.front== LQ.rear 规定：链队列空时，令rear指针也指向表头结点。 链队列下溢条件： LQ.front->next == NULL 或 LQ. front == LQ. rear；
显然仅有单链表的头指针不便于在表尾做插入操作，为此再 增加一个尾指针，指向链表的最后一个结点。
链式队的下溢：即链式队为空时，还要求出队
【例】
1. 在实现队列的链表结构中， 其时间复杂度最优的是（B） A、仅设置头指针的单循环链表 B、仅设置尾指针的单循环链表（解析：入队：(rear+1)%maxsize; 出队：[(rear->next)+1]%maxsize; 即(front+1)%maxsize） C、仅设置头指针的双向链表 D、仅设置尾指针的双向链表
2. 关于栈和队列,下面叙述正确的是（D） A、函数的嵌套调用用队列来实现（解析：用递归实现） B、操作系统中进程调用用栈来实现（解析：用队列来实现） C、程序递归的处理用队列来实现（解析：用栈来实现） D、栈和队列是运算受限的线性表
链队列的基本运算
➢ 队列的初始化
➢ 队列的初始化 void initQueue(LkQue *LQ) { LkQueNode *temp; temp = (LkQueNode *)malloc(sizeof(LkQueNode)); LQ->front = temp; LQ->rear = temp; (LQ->front)->next = NULL; }
➢ 判队列空
➢ 判队列空 Int EmptyQueue(LkQue LQ) { if (LQ.rear==LQ.front) return 1; else return 0; }
➢ 入队列
➢ 入队列 入队——在队尾即链表尾部插入一元素x ● 生成新结点p（其数据域置x，链域置NULL） ● 将新结点p插入到表尾，并变成新的队尾结点 Void EnQueue(LkQue *LQ; DataType x) { LkQueNode *temp; temp=(LkQueNode *)malloc(sizeof(LkQueNode)); temp->data = x; temp->next = NULL; (LQ->rear)->next = temp; //新结点插入队尾 LQ->rear = temp; //修改尾结点指针 }
入队列
➢ 出队列
➢ 出队列 出队——在链式队中删除队头元素，并送至x中 ● 考虑下溢否 ● 不下溢，则 ① 取队头结点temp； ② 送队头元素至x； ③ 从链式队中删除队头结点； ④ 若链式队中原只有一个元素，则删除后队列为空，应修改队尾指针； ⑤ 结点temp回归系统。 OutQueue(LkQue *LQ) { LkQueNode *temp; if (EmptyQueue(LQ)) {error(“队空”)；return 0；} else { temp = (LQ->front)->next; (LQ->front)->next = temp->next; if (temp->next == NULL) LQ->rear = LQ->front; free(temp); return 1; } }
出队列
➢ 取队列首元素
➢ 取队列首元素 DataType GetHead (LkQue LQ) //此处不加 *,则下面可写成LQ.front { LkQueNode *temp; if (EmptyQueue(LQ)) return NULLData; else { temp=LQ.front->next; return temp->data; } }
描述栈和队列实现的头文件
Seqstack.h：顺序栈的定义及其实现
Lkstack.h：链栈的定义及其实现
Sequeue.h：顺序队列定义及其实现
Lkqueue.h：链队列的定义及其实现
3.3 数 组
数组可看成是一种特殊的线性表，其特殊在于，表中的数组元素本身也是一种线性表。
§3.3.1 数组的逻辑结构和运算
数组——是线性表的推广，其每个元素由一个值和一组下标组成，其中下标个数称为数组的维数。 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是线性表的推广。
例如：二维数组
二维数组Amn可以看成是由m个行向量组成的向量， 也可以看成是n个列向量组成的向量。 数组一旦被定义，它的维数和维界就不再改变。因 此，除了结构的初始化和销毁之外，数组通常只有两 种基本运算： ①读——给定一组下标，读取相应的数据元素； ②写——给定一组下标，修改相应的数据元素；
§3.3.2 数组的存储结构
1. 存储结构——顺序存储结构
由于计算机的内存结构是一维的，因此用一维内存来表示多维数组， 就必须按某种次序将数组元素排成一列序列，然后将这个线性序列存放 在存储器中。 又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立， 结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采 用顺序存储的方法来表示数组。
2. 寻址公式（以行为主存放）
例如，二维数组A 按“行优先顺序”存储在内存中，假设每个元素占用k个存储单元。 元素aij 的存储地址应是数组的基地址加上排在 aij 前面的元素所占用的单元数。因为 aij 位于第 i 行、第 j 列，前面 i 行一共有i×n个元素，第 i 行上aij 前面又有 j 个元素，故它前面一共有i×n+j个元素，因此，aij 的地址计算函数为： LOC(aij ) = LOC(a00) + ( i*n + j )*k //i*n 即第 i 行前面的元素个数，j 即第 j 列前的素数个数
3.3.3 矩阵的压缩存储
为了节省存储空间， 我们可以对这类矩阵进行压缩存储：即为多个相同的 非零元素只分配一个存储空间；对零元素不分配空间。
特殊矩阵
即指非零元素或零元素的分布有一定规律的矩阵。下面我们讨论几种特殊矩阵的压缩存储。
对称矩阵
1.定义：在一个n阶方阵A中，若元素满足下述性质： aij =aji 0≤i, j≤n-1
物理存储
对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素 在这个下三角矩阵中，第i行恰有i个元素，元素总数为：（等差数列） ∑(i)=n(n+1)/2 因此，我们可以按图中箭头所指的次序将这些元素存放在一个一维数组S[1..n(n+1)/2]中。为了便于访问对称矩阵A中的元素，我们必须在a 和S[k]之间找一个对应关系。
★下标变换公式：（以下三角表示） (1) 若i≥j，则aij 在下三角形中。aij 之前的i行（从第0行到第i-1行）一共有1+2+…+i=i(i+1)/2个元素，在第i行上，aij 之前恰有j个元素（即ai0 ,ai1 ,ai2 ,ai3 ,…,ai(j-1) ）， 因此有：
(2) 若i<j，则a 是在上三角矩阵中。因为a =a ，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0≤k＜n(n+1)/2 -1 令I=max(i,j)，J=min(i,j)，则k和i, j的对应关系 可统一为： k = i*(i-1)/2+j 0≤k＜n(n+1)/2 -1
有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在S[k]中找到矩阵元素aij ，反之，对所有的k=0,1,2,3,…n(n+1)/2-1，都能确定S[k]中的元素在矩阵中的 位置(i,j)。由此，称S[n(n+1)/2]为对称矩阵A的压缩存储，见右图： 例如a31 和a13 均存储在sa[4]中，这是因为： k = i*(i-1)/2+j=3*(3-1)/2+1=4
对称矩阵转置算法( 行 和 列 转置 )
void MM( int A[n][n] ) { int i, j, temp; for(i = 0; i < n; i++) for(j = 0; j < i; j++) //行号大于列号的部份不用重复转 { temp = A[i][j]; A[i][j] = A[j][i]; A[j][i] = temp; } }
三角矩阵
以主对角线划分，三角矩阵有上三角和下三角两种。 上三角矩阵如图所示，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵正好相反，它的主对角线上方均为常数，如图所示。在大多数情况下，三角矩阵常数为零。 三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n(n+1)/2个，因此，三角矩阵可压缩存储到向量s[0..n(n+1)/2]中，其中c存放在向量的最后一个分量中。 上三角矩阵中，主对角线之上的第p行(0≤p<n)恰有n-p个元素，按行优先顺序存放上三角矩阵中的元素aij 时，aij 之前的i行一共有 (n-p)=i(2n-i+1)/2个元素，在第i行上，aij 前恰好有j-i个元素：aij ,aij+1 ,…aij-1 。因此，s[k]和aij 的对应关系是： k = i(2n-i+1)/2+j-i 当i≤j k = n(n+1)/2 当i>j 下三角矩阵的存储和对称矩阵类似，s[k]和aj 对应关系是： k = i(i+1)/2+j i≥j k = j( j+1)/2+i i＜j
稀疏矩阵的压缩存储
什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。 稀疏矩阵的压缩存储——即只存储稀疏矩阵中的非零元素。 由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。反之，一个三元组(i,j,a )唯一确定了矩阵A的一个非零元。因此，稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。 例如，下列三元组表(i, j, v) ( (0,1,12)，(0,2,9)，(2,0,- 3)，(2,5,14)，(3,2,24), (4,1,18)，(5,0,15)，(5,3,-7) ) 加上(5,6)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。 1、三元组顺序表 稀疏矩阵的三元组顺序表表示法——将矩阵中的非零元素化成三元组形式并按行的不减次序（同行按列的递增次序）存放在内存中。 1).三元组表结构： 假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法——三元组顺序表。 const int maxnum=10； typedef struct node { int i, j; /*非零元的行下标和列下标*/ DataType v; /*非零元素的值*/ } NODE;——三元组 typedef struct spmatrix{ NODE data[maxnum]; /*非零元三元组表*/ int mu,nu,tu; /*矩阵的行数、列数和非零元个数*/ } SpMtx;——稀疏矩阵三元组表存储类型 设:SpMtrx M ; 则右图中（三元组表）所示的稀疏矩阵的三元组的表示如右： （i, j, v）即：(行下标，列下标，对应的值)
栈、队列和数组小结
● 掌握栈和队列的特点，并能在相应的应用问题中正确选用它们； ● 掌握栈的顺序存储结构的描述方法，栈空、栈满条件及入栈、出栈算法 ； ● 掌握循环队列和链式队列两种存储结构的描述方法、上下溢条件以及出队、入队算法。 ★ 重点：栈、队列的操作原则与基本操作算法。 ▲二维数组以行为主存储时的寻址公式； ▲特殊矩阵、稀疏矩阵的定义； ▲对称矩阵压缩存储时的下标变换公式； ▲稀疏矩阵的三元组顺序表的表示
四 树和二叉树
4.1 树的基本概念
树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。 树在计算机领域中也有着广泛的应用，例如： 在编译程序中，用树来表示源程序的语法结构； 在数据库系统中，可用树来组织信息； 在分析算法的行为时，可用树来描述其执行过程等等。 递归是树的固有特性
树的定义
树——是n(n>=0)个结点的有限集T，满足： (1)当n=0时，称为空树； (2)当n>0时，有且仅有一个特定的称为根的结点；其余的结点可分为m(m>=0)个互不相交的子集T1 ,T2 ,T3 …Tm ，其中每个子集T 又是一棵树，并称其为子树。
树的逻辑表示
▲一般表示法(直观表示法)：
▲另三种表示法
a、文氏图法
b、嵌套括号法
(根(子树,子树…子树)) ( A ( B ( E, F ), C , D ( G ) )
c、凹入法表示
树的相关术语
树的相关术语 ● 结点—由一个数据元素及若干指向其它结点的分支所组成。 ● 度——结点的度：该结点的子树数（即分支数）。 树的度：树中结点的度最大值。 ● 叶子（终端结点）——度为零的结点。 ● 非终端结点——度不为零的结点。 ● 孩子（子结点）——结点的子树的根称为该结点的孩子。 ● 双亲（父结点）——一个结点称为该结点所有子树根的双亲。 ● 祖先——结点祖先指根到此结点的一条路径上的所有结点。 ● 子孙——从某结点到叶结点的分支上的所有结点称为该结点的子孙。 ● 兄弟——同一双亲的孩子之间互称兄弟。 ● 结点的层次——从根算起，根为第一层，其孩子在第二层,….， L层上任何结点的孩子都在L+1层上。 ● 堂兄弟——其双亲在同一层的结点。 ● 树的深度——树中结点的最大层次。 ● 有序树——若树中各结点的子树从左到右是有次序的，不能互换，称为有序树。 ● 无序树——若树中各结点的子树是无次序的，可以互换，则成为无序树。 ● 森林——是m（≥0）棵树的集合。
树的基本运算
➢ 求根Root(T):求树T的根结点； ➢ 求双亲Parent(T,X):求结点X在树T上的双亲；若X是树T的根或X不在T上，则结果为一特殊标志； ➢ 求孩子Child(T,X,i):求树T上结点X的第i个孩子结点；若X不在T上或X没有第i个孩子，则结果为一特殊标志； ➢ 建树Create(X,T ,…,T ),k>1:建立一棵以X为根，以T ,…,T 为第1,…,k棵子树的树； ➢ 剪枝Delete(T,X,i):删除树T上结点X的第i棵子树；若T无第i棵子树，则为空操作； ➢ 遍历TraverseTree(T):遍历树，即访问树中每个结点，且每个结点仅被访问一次。
4.2 二叉树
二叉树的基本概念
二叉树在树结构的应用中起着非常重要的作用，因为二叉树有许多良好的性质和简单的物理表示，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。
定义
二叉树是n(n>=0)个结点的有限集合，它或为空(n=0)，或是由一个根及两棵互不相交的左子树和右子树组成，且中左子树和右子树也均为二叉树。
这是一个递归定义。 二叉树可以是空集合，根可以有空的左子树或空的右子树。
特点
① 二叉树可以是空的，称空二叉树； ② 每个结点最多只能有两个孩子； ③ 子树有左、右之分且次序不能颠倒。
二叉树与树的比较
二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。
二叉树的五种基本形态
二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。下图列出二叉树的5种基本形态，图(C) 和（d）是不同的两棵二叉树。
空O左右格
二叉树的基本运算
➢ 初始化Initiate(BT)：建立一棵空二叉树，BT=∅。 ➢ 求双亲Parent(BT,X)：求出二叉树BT上结点X的双亲结点，若X是BT的根或X根本不是BT上的结点，运算结果为NULL。 ➢ 求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分别求出二叉树BT上结点X的左、右孩子；若X为BT的叶子或X补在BT上，运算结果为NULL。 ➢ 建二叉树Create(BT)：建立一棵二叉树BT。 ➢ 先序遍历PreOrder(BT)：按先序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。 ➢ 中序遍历InOrder(BT)：按中序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。 ➢ 后序遍历PostOrder(BT)：按后序对二叉树BT进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。 ➢ 层次遍历LevelOrder(BT)：按层从上往下，同一层中结点按从左往右的顺序，对二叉树进行遍历，每个结点被访问一次且仅被访问一次，若BT为空，则运算为空操作。
二叉树的性质
性质1： 在二叉树的第 i (i>=1)层上至多有2^(i-1)个结点。 性质2：深度为 k (k>=1)的二叉树至多有2^k－1个结点。（等比数列演化） 性质3：对任何一棵二叉树，如果其终端结点数为n0 ，度为2的结点数为n2 ，则n0 ＝n2 ＋1。即：叶结点数n0 =度为2的结点数n2 +1 ▲ 满二叉树——深度为 k (k>=1)且有2^k-1个结点的二叉树；是完全二叉树的一种特例。 ▲ 满二叉树中结点顺序编号：即从第一层结点开始自上而下，从左到右进行连续编号。 ▲ 完全二叉树——深度为K的二叉树中，K-1层结点数是满的(2k- 2 )，K层结点是左连续的(即结点编号是连续的)；剪枝从右往左剪。 性质4：具有n个结点的完全二叉树的深度为：⌊log2 n⌋+1；如：⌊log2 7⌋+1=2+1=3；与求最多结点数互逆。 假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2^(k-1)－1< n <= 2^k-1 或 2^(k-1) <= n < 2^k 取对数得到：k－1<log2 n<k 因为k是整数。所以有⌊log2 n⌋+1 性质5： 对有n个结点的完全二叉树的结点按层编号（从第1层到第[log2 n]+1层，每层从左到右),则对任一结点i（1≤i≤n),有： （1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则i的双亲Parent(A)是结点⌊i/2⌋； （2）如果2*i ≤ n，则其左孩子是结点 2*i，否则，结点i无左孩子且为叶子结点； （3）如果2*i＋1 ≤ n，则其右孩子是结点 2*i＋1，否则，结点i无右孩子。 注：⌊...⌋下取整，把小数部分砍掉
⌊log2 7⌋+1=2+1=3层
具有n个结点的完全二叉树的深度；⌊x⌋表示不大于 x 的最大整数；即下取整
思考
满二叉树（结点数=2^3-1=7）//深度为3，性质2
▲深度为5的二叉树
结点数最少 （5）个
结点数最多（31） 个，2^5-1
▲深度为5的完全二叉树
结点数最少（16）个，2^(5-1) =16
结点数最多（31）个
▲一棵完全二叉树,结点总数n=980,问
该二叉树的深度=? ——性质4：⌊log2 980⌋+1 = 10 最下层结点个数=? ——性质2： 980 - [ 2^9 -1] = 369 度为1的结点个数： n1 =0 或 1 ——完全二叉树定义 叶结点个数：n0 = n2 +1 ——性质3：2n2+1+n1=980
如果需要顺序存储的非完全二叉树，首先必须用某种方法将其转化为完全二叉树，为此，可以增设若干个虚拟结点。（如图）这样可以用与处理完全二叉树相同的方法实现二叉树的基本运算，但这种方法的缺点是造成了空间的浪费
4.3 二叉树的存储结构
顺序存储结构
完全二叉树存到二维数组当中，0 空着
一般二叉树,造成空间的浪费
链式存储结构
二叉链表
▲二叉链表类型定义 typedef struct btnode { DataType data; struct btnode *lchild,*rchild; } *BinTree;;——二叉链表类型
5个节点，共10个指针，这里n为5，n+1=6个空指针，n-1=4条边
注：在含n个结点的二叉链表中有 2n 个指针域，其中 n-1 个用来指向结点的左右孩子，其余 n+1 个空链域.
三叉链表
三叉链表
4.4 二叉树的遍历
遍历含义
一、遍历含义 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题。 遍历二叉树——是指按某种次序访问二叉树上的所有结点，使每个结点被访问一次且仅被访问一次。 二、遍历规则 由二叉树的递归定义知，二叉树的三个基本组成单元是：根结点、左子树和右子树。以下均指根节点的访问次序。 令：L —— 遍历左子树 D —— 访问根结点 R —— 遍历右子树 DLR——先（根）序遍历， LDR——中（根）序遍历，（中序遍历一棵二叉树，得到的的结果刚好是排序递增的顺序，即满足二叉排序树） LRD——后（根）序遍历。 1、先序遍历DLR ——首先访问根结点，其次遍历根的左子树，最后遍历根右子树，对每棵子树同样按这三步（先根、后左、再右）进行。 2、中序遍历LDR ——首先遍历根的左子树，其次访问根结点，最后遍历根右子树，对每棵子树同样按这三步（先左、后根、再右）进行。 3、后序遍历LRD ——首先遍历根的左子树，其次遍历根的右子树，最后访问根结点，对每棵子树同样按这三步（先左、后右、最后根）进行。
遍历算法
先序遍历（递归算法）
▲步骤：若二叉树为空，执行空操作； 否则: （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。
▲ 算法： void preorder ( Bintree bt ) { /*先序遍历以bt为根的二叉树*/ if (bt！=NULL){ visit(bt); /*访问根结点*/ preorder ( bt->lchild ) ；//递归方式遍历 preorder ( bt->rchild ) ;}//递归方式遍历 }
遍历实现
中序遍历运算（递归算法）
▲步骤：若二叉树为空，执行空操作； 否则: （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。
▲ 算法： void inorder (Bintree bt ) { /*中序遍历以bt为根的二叉树*/ if (bt！=NULL){ inorder ( bt->lchild ) ； visit(bt); /*访问根结点*/ inorder (bt->rchild ) ; } }
后序遍历运算（递归算法）
▲步骤：若二叉树为空，则退出； 否则: （1）后序遍历根的左子树； （2）后序遍历根的右子树。 （3）访问根结点；
▲ 算法： void postorder (Bintree bt ) { /*后序遍历以bt为根的二叉树*/ if (bt！=NULL){ postorder ( bt->lchild ) ； /*后序遍历以 l 的左孩子为根的左子树*/ postorder ( bt->rchild ) ； visit(bt);} /*访问根结点*/ }
二叉树的层次遍历
从二叉树的根结点的这一层开始，逐层向下遍历，在每一层上按从左到右的顺序对结点逐个访问。 设立一个队列Q，用于存放结点，以保证二叉树结点 按照层次顺序从左往右进入队列。若二叉树bt非空： ✓ 将根结点插入队列； ✓ 从队列中删除一个结点，访问该结点，并将该结点 的孩子（若有的话）插入队列。 ✓ 若此时队列非空，再从队列中删除一个结点，访问 该结点，并将它的孩子结点插入队列。依次重复进行， 直到队列为空。
void levelorder( BinTree bt ) { LkQue Q; InitQueue( &Q ); if ( bt != NULL ) { EnQueue( &Q ,bt ); while ( ! EmptyQueue ( Q ) ) { p=Gethead( &Q ); outQueue( &Q ); visit( p ); if (p->lchild ! NULL) EnQueue(&Q , p->lchild); if (p->rchild ! NULL) EnQueue(&Q , p->rchild); } } }
遍历实例
先序遍历：A、B、D、F、G、C、E、H 。 中序遍历：B、F、D、G、A、C、E、H 。 后序遍历：F、G、D、B、H、E、C、A 。
先序遍历：根->左->右 A、B、D、G、H、E、C、K、F、I、J
中序遍历：左->根->右 G、D、H、B、E、A、K、C、I、J、F
后序遍历：左->右->根 G、H、D、E、B、K、J、I、F、C、A
按层遍历：从上到下，从左到右 A、B、C、D、E、K、F、G、H、I、J
任意一棵二叉树的前序和后序遍历的结果序列中， 各叶子结点之间的相对次序关系都相同
遍历二叉树的应用
▲注：“遍历”是二叉树各种操作的基础，可以在遍历 过程中对结点进行各种操作，如：对于一棵已知二叉树 ① 求二叉树中结点的个数； ② 求二叉树中叶子结点的个数； ③ 求二叉树中度为1的结点个数； ④ 求二叉树中度为2的结点个数； ⑤ 求二叉树中非终端结点个数； ⑥ 交换结点左右孩子； ⑦ 判定结点所在层次；
例1：编写求二叉树中叶结点个数的算法(设二叉树的二叉链表的根指针为bt)。
int leafcount (Bintree bt ) { /*求二叉树bt中叶结点的数目*/ if ( bt == NULL ) return (0) ; else if ( bt->lchild == NULL && bt->rchild == NULL ) return (1) ; else { n = leafcount( bt->lchild ) ; /* 求左子树的叶子数目*/ m = leafcount(bt->rchild) ; /* 求右子树的叶子数目*/ return (m+n) ; } }
以二叉链表作存储结构，试编写求二叉树叶子结点个数的算法
typedef struct btnode { DataType data ; struct btnode *lchild, *rchild ; //指向左右孩子的指针 } *BinTree ; int leafnode_num (Bintree bt ) { if ( bt == NULL ) return 0 ; else if ( bt->lchild == NULL && bt->rchild == NULL ) return 1 ; else { n = leafnode_num ( bt->lchild ) ; /* 求左子树的叶子数目*/ m = leafnode_num (bt->rchild) ; /* 求右子树的叶子数目*/ return (m+n) ; } }
设计算法按先序次序打印二叉树T中叶子结点的值
//设计算法按先序次序打印二叉树T中叶子结点的值 typedef struct btnode { int data; struct btnode *lchild,*rchild; //指向左右孩子的指针 } *BinTree; void preorder (BinTree bt) { if (bt != NULL) { if ((bt->lchild == NULL) && (bt->rchile == NULL)) printf("%d",bt->data); preorder(bt->lchild); preorder(bt->rchild); } }
例2：编写输出二叉树中所有度为1的结点的数据域的值，并统计其数目的算法(设二叉树的二叉链表的根指针为t)。
int onesoncount(Bintree t) /*输出二叉树t中度为1的结点值，并求其个数*/ { if (t==NULL) return(0); else if ((t->lchild==NULL && t->rchild != NULL) || (t->lchild != NULL && t->rchild==NULL)) { printf(t->data); return(onesoncount(t->lchild)+onesoncount(t->rchild)+1); } else return(onesoncount(t->lchild)+onesoncount(t->rchild)); }
例3：编写输出二叉树中所有度为2的结点的数据域的值，并统计其数目的算法(设二叉树的二叉链表的根指针为BT)。
int twoson(Bintree BT) /*输出二叉树BT中所有度为2的结点的数据域值，并统计其数目*/ { if (BT==NULL) return(0); else if (BT->lchild==NULL || BT->rchild==NULL) return(twoson(BT->lchild) + twoson (BT->rchild)); else if (BT->lchild != NULL && BT->rchild != NULL) { printf(BT->data); return(twoson(BT->lchild) + twoson(BT->rchild)+1); } }
例4：编写一算法，打印出一棵二叉树中所有非终端结点的值，并统计非终端结点的个数。(二叉树以二叉链表存储，根指针为bt)
int notleafcount (Bintree bt ) /*求二叉树bt中非叶结点的数目*/ { if ( bt = = NULL ) return (0) ; else if ( bt->lchild = = NULL && bt->rchild = = NULL ) return (0) ; /*无左右子树*/ else { printf(bt->data); /* 输出非终端结点值*/ n = notleafcount( bt->lchild ) ; /* 求左子树的非终端结点数目*/ m = notleafcount(bt->rchild) ; return (m+n+1) ; /* 返回总的非终端结点数*/ } }
例5： 编写一算法，打印出一棵二叉树中所有结点的值，并统计结点的个数。(二叉树以二叉链表存储，根指针为bt)
int f5 (Bintree bt ) /* 打印出二叉树t中所有结点的值，并统计结点的个数 */ { if ( bt == NULL ) return (0) ; else { printf(bt->data); /* 输出结点值*/ n = f5( bt->lchild); /* 求左子树的结点数目*/ m = f5( bt->rchild); /* 求右子树的结点数目*/ return (m+n+1) ; /* 返回总的结点数*/ } }
设计算法求二叉树的结点个数
//设计算法求二叉树的结点的个数 typedef struct btnode { DataType data; struct btnode *lchild,*rchild; //指向左右孩子的指针 } *BinTree; int node_num(BinTree bt) { if (bt == NULL) return 0; else return node_num(bt->lchild)+node_num(bt->rchild)+1; // 左子树结点数 + 右子树结点数 + 1 个根结点 }
例6：设二叉树存储结构采用二叉链表表示，每个结点的数据域中存放一个整数。试编写一个算法，求此二叉树上数据域的值为８的结点个数。
int f6 (Bintree bt ) /*求二叉树bt结点数据域值为８的结点的数目*/ { if ( bt == NULL ) return (0) ; else if (bt->data=８) return(f6(bt->lchild)+f6(bt->rchild)+1); else return(f6(bt->lchild)+f6(bt->rchild)); }
4.5 树和森林
树的存储结构（三种）
双亲表示法
以一组连续空间存储树的结点，即一个一维数组构成，数组每个分量包含两个域：数据域和双亲域。数据域用于存储树上一个结点的数据元素值，双亲域用于存储本结点的双亲结点在数组中的序号（下标值）。 每个数组元素含两个成员，即：（结点值和其双亲在表中的位置） ➢ 根结点没有双亲，双亲域的值为-1。双亲链表的类型 定义如下： #define size 10 typedef struct { datatype data; int parent; } Node; Node slist[size];
孩子链表表示法
树中每个结点的孩子串成一单链表——孩子链表：n个结点——n个孩子链表 n个头指针用顺序表存储——表头数组：数组元素存储结点本身的信息和该结点的孩子链表的头指针。 child next child：存放孩子结点在表头数组中的序号 next：指向下一个孩子结点 ➢ 孩子链表表示法的类型定义： # define MAXND 20 typedef struct bnode { int child; struct bnode *next; } node,*childlink; Typedef struct { DataType data; childlink hp; } headnode; Headnode ；link[MAXND]； 注:在孩子链表表示中，找孩子方便，但 求结点的双亲困难，因此可在顺序表中再增加 一个域，用于指明每个结点的双亲在表中位置，即将双亲表示法和孩子链表表示法结合 起来。
双亲孩子表示法
树中每个结点的孩子串成一单链表——孩子链表 n个结点——n个孩子链表 同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子链表的头指针之外，还增设一个域，用来存储结点双亲结点在数组中的序号。 # define MAXND 20 typedef struct bnode { int child; struct bnode *next; } node,*childlink; Typedef struct { DataType data; int parent ; childlink hp; } headnode; Headnode ；link[MAXND]；
孩子兄弟链表表示法（二叉链表表示）
孩子兄弟链表的结构形式与二叉链表完全相同，但结点中指针的含义不同。
孩子兄弟链表表示法类型定义： Typedef struct tnode { DataType data; struct tnode *son,*brother; } *Tree;
树、森林与二叉树的关系
一般树->二叉树
▲方法： ⑴ 各兄弟之间加连线； ⑵ 对任一结点，除最左孩子外，抹掉该结点与其余孩子的各枝； ⑶ 以根为轴心，将连线顺时针转45度。
森林->二叉树
⚫（1）将每棵树转换成相应的二叉树； ⚫（2）将（1）中得到的各棵二叉树的根结点看做是兄弟连接起来。
二叉树->一般树（还原）
▲方法： ⑴ 从根结点起； ⑵ 该结点左孩和左孩右枝上的结点依次作为该结点孩子； ⑶ 重复⑴ 。
树和森林的遍历
树的遍历
●先序遍历：先访问根结点，然后依次先序遍历根的每棵子树； ●后序遍历：先依次后序遍历每棵子树，最后访问根结点。 ●层次遍历
先序遍历次序：？ ABCDE 后序遍历次序：？ BDCEA 层次遍历次序：？ ABCED
森林的遍历（只有两种）
⚫ 先序遍历森林：访问森林中每棵树的根结点；先序遍历森林中第一棵树的根结点的子树组成的森林；先序遍历除去第一棵树之外其余的树组成的森林。 对右图中森林进行先序遍历的序列为：（根左右） ABCDEFGHJI ⚫ 中序遍历森林：中序访问森林中第一棵树的根结点的子树组成的森林；访问第一棵树的根结点；中序遍历除去第一棵树之外其余的树组成的森林； 对右图中森林进行先序遍历的序列为：（左右根）（类似二叉树的后根遍历） BCDAFEJHIG
4.6 判定树和哈夫曼树
分类与判定树
◆问题：n个学生成绩 a1 ，a2 ，…,an （百分制），现要转换成五分制。即 a ，a ，…,a 分五类： 一类：< 60 不及格 二类：[ 60， 70 ） 及格 三类：[ 70， 80 ） 中等 四类：[ 80， 90 ） 良好 五类：≥ 90 优秀 每类出现的概率： 分数 0～59 60～69 70～79 80～89 90以上 概率 5% 15% 40% 30% 10%
◆若按顺序判，得下列判断过程： 判定树——用于描述分类过程的二叉树，其中：每个非终端结点包含一个条件，对应一次比较；每个终端结点包含一个种类标记，对应于一种分类结果。 对n个数分类花费时间较多。因为大多数元素属于中和良，这样大多数数据都得通过3至4次判断，这样总的判断次数就多。 改进后：总的判断次数最少。因为属于中、良的数最多， 而检验它们的判断少，因此总的判断次数少。 如何构造时间性能最高的判定树？ 哈夫曼树
改进后
哈夫曼树与哈夫曼算法
路径长度
◆叶结点带权的二叉树： 一组实数{ p1 ，p2 ，…,pk } ➔ 每个叶子{ n1 ，n2 ，…,nk } 例：pi 表示输入最终落入ni 的概率 ◆结点ni 的带权路径长度： 为结点ni 到树根的路径长度(ni 的祖先的个数li )×结点ni 所带的权（pi ） a 的路径长度=？ 2×7=14
◆叶结点带权的二叉树路径长度WPL
其中：n——叶子数 pk ——第 k 个叶子的权 lk ——从根到第 k 个叶子的路径长度（分支数） d的路径长度=？8 WPL=？36
哈夫曼树
例：二叉树有4个叶子，权分别为7，5，2，4 ◆结论： 带权路径长最小的二叉树 其特征是 权大的叶子离根近 权小的叶子离根远 哈夫曼树（最优二叉树）
WPL=36
WPL=46
WPL=35
哈夫曼算法
◆方法： 给定n个权值{ p1 ，p2 ，…, pn }{n个叶子带的权} 森林F' ={ T'1 ，T'2 ，…,T'n }——{ T'i 只有一个带权pi 排 的根结点，左、右子树为空 } F = { T1 ，T2 ，…,Tn }—{T1 ，T2 ，…,Tn 权从小到大排列 } ⑴ 取F中T1 和T2 (权最小的二棵)生成一棵二叉树T， T为根， T1 、T2 分别为T的左、右子树， T的权=T1 的权+T2 的权； ⑵ T插入到F的余下森林中（按序）； 重复⑴、⑵，直至F = { T }为一棵二叉树。 此二叉树T即为哈夫曼树
初始森林共有n棵二叉树，每棵树中都仅有一个孤立的结点，要进行n-1次合并才能得到哈夫曼树，每次合并产生一个新结点。 最终有2n-1个结点。
采用顺序存储，设置大小为2n-1的数组，每个数组元素由4个域组成： 存储权值、双亲指针、左孩子指针和右孩子指针。类型定义如下： const int n=10; typedef struct { float w; //w为结点的权值 int parent, lchild,rchild; //父结点和左、右孩子所在数组的下标 } node; typedef node hftree[2*n-1]； 哈夫曼算法： 1.将表示哈夫曼树的数组T中的2n-1结点初始化； 2.读入n个权值到数组T的前n个分量中，它们是初始森林中的n个孤立的根结点的权值； 3.对森林中的树进行n-1次合并，共产生n-1个新结点，依次放入数组T的第i个 分量重(n<=i<2*n-1)。每次合并的步骤如下： •从当前森林的所有结点T[j](0<=j<=i-1)中选取具有最小权值和次小权值的两个根结点，分别用x和y记住这两个根结点在数组T中的下标。 •将根为T[x]和T[y]的两棵树合并，使它们分别成为新结点T[i]的左右孩子，得到一棵以新结点T[i]为根的二叉树。同时修改T[x]和T[y]的双亲域parent，使其指向新结点T[i],将T[x]和T[y]的权值相加后作为新结点T[i]的权值。类C语言描述的算法见P122。
哈夫曼编码
可利用哈夫曼树构造用于通信的二进制编码称为哈夫曼编码。 树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。 ◆ 每个字符在电文中出现的次数为w ，其编 码长为m ，电文有n种字符，则电文总长=? ◆ 什么是哈夫曼编码？如何设计？ ◆ 求哈夫曼编码的算法。 分二步： 1）以n个字符的权值，构造哈夫曼树； 2）求n个字符的哈夫曼编码。
◆ 哈夫曼编码的应用 例电文：“CAST└┘TAT└┘A└┘SA”。 其中：C出现1次，A出现4次，S出现2次，T出现3次，└┘出现3次。 哈夫曼编码： C：100 S：101 └┘：01 A：11 T：00
例：设某通信系统中一个待传输的文本有6个不同字符，它们的出现频率分别是：0.5，0.8，1.4，2.2，2.3，2.8，试设计哈夫曼编码。 【分析】由题意，共有n=6个不同的字符，字符的频率序列为p=｛0.5，0.8，1.4，2.2，2.3，2.8｝，以这些频率作为权值，构造一棵哈夫曼树，并对其进行哈夫曼编码。
树和二叉树小结
了解树的定义及基本术语；掌握二叉树的定义、性质及满二叉树、完 全二叉树的定义；熟练掌握二叉树的二叉链表表示；熟练掌握二叉树的 三种遍历（先序、中序、后序）过程和算法，并能运用遍历算法实现二 叉树的其它一些操作；熟悉树的各种存储表示及特点，熟练掌握树与二 叉树的转换方法；熟练掌握建立哈夫曼树的方法；理解由二叉树先序序 列、中序序列及后序序列和中序序列可唯一的确定一棵二叉树的道理， 掌握由此建立二叉树的方法。 ★重点：二叉树遍历过程及算法、哈夫曼树的构造。
五 图
图的基本概念
图的定义 图G —— 是由集合V和E组成，记成G=（V，E） 其中： V — 顶点集（非空）； E — 边集（可空）。 边是顶点的有序对或无序对。 （边反映了两顶点之间的关系） ●有向图：边是顶点的有序对的图。 （图中每条边都用箭头指明了方向） ●无向图：边是顶点的无序对的图。 注： 1）边集可空； 2）边集中不允许出现相同的边。
无向图
V(G1)={ 1，2，3，4 } E(G1)={ (1,2)，(1,3)，(1,4)，(2,3)， (2,4)，(3,4) } //不允许重复，（1，3）与（3，1）一回事，相同的
V(G2)={ 1，2，3，4 ，5，6，7 } E(G2)={ (1,2)，(1,3)，(2,4)，(2,5)， (3,6)，(3,7) }
有向图
V(G3)={ 1，2，3 } E(G3)={ <1,2>，<2,1>，<2,3> } //尖括号表示有向
图的基本术语
● 顶点(Vertex)——图中的数据元素； ● <Vi ,Vj >——有向图中,顶点Vi 到 顶点Vj 的边,也称弧； Vi 弧 头（终端点）：箭头端；Vj 弧 尾（初始点）：无箭头端； ● 完全图： 无向完全图：边数= n*(n-1)/2 的无向图； 有向完全图：边数= n*(n-1) 的有向图； ● 权 ——与图中的边相关的数； ● 子图——图G和G′,若有V(G′) ∈ V(G) 和 E(G′) ∈ E(G),则称 G′为图G的子图。 ● 邻接——若(Vi ,Vj ) ∈ E(G)，则称Vi 和Vj 互为邻接点; ● 关联——若(Vi ,Vj ) ∈ E(G)，则称边(Vi ,Vj )关联于顶点Vi 和Vj ; 注： 1）邻接是指顶点之间的关系，而关联是指边与顶点间的关系。 2）若弧<Vi ,Vj > ∈ E(G)，则称Vj 是Vi 的邻接点 ● 度 无向图：顶点Vi 的度为与Vi 相关联的边的个数；D(Vi) 有向图： 出度：顶点Vi 的出度为以Vi 为尾的出边数；OD( Vi ) 入度：顶点Vi 的入度为以Vi 为头的入边数；ID( Vi ) 度：有向图的度 = 入度+出度；D( Vi ) = OD( Vi ) + ID( Vi ) ● 路径——图中，顶点Vp至顶点Vq的路径是顶点序列 { Vp,Vi1 ,Vi2 ,…,Vin ,Vq } 且 对无向图，边(Vp,Vi1 ),(Vi1 ,Vi2 ),…,(Vin ,Vq) ∈ VR(G); 对有向图，弧<Vp,Vi1 >,<Vi1 ,Vi2 >,…,<Vin ,Vq> ∈ VR(G); ● 路径长度——路径上边或弧的数目； ● 简单路径——除第一个和最后一个外，其余各顶点均不相同的路径； ● 回路—第一个和最后一个顶点相同的路径，也称环； ● 简单回路—第一个和最后一个顶点相同的简单路径； 注：回路中可以有多个圈，而简单回路只能有一个圈。 ● 连通——无向图中，若从顶点Vi 到Vj 顶点有路径，则称Vi 和Vj 是连通的。 ● 连通图和连通分量： 针对无向图而言 ⚫ 生成树——含有该连通图的全部顶点的一个极小连通子图。（只要连通就行，即可生成树） 若连通图G的顶点个数为n，则G的生成树的边数为n-1。 G的子图G’边数大于n-1,则G’中一定有环。 G的子图G’边数小于n-1,则G’中一定不连通。 ⚫ 生成森林——在非连通图中，每个连通分量都可得到一个极小连通子图，也就是生成树。这些生成树就组成了一个非连通图的生成森林。
子图
注：图中边数e与顶点的度的关系 （一边带二度，两度组成一边）
连通图，强连通图；连通分量；强连通分量
图的基本运算
➢ 建立图 GreateGraph(G,V,E) ➢ 取顶点信息 GetVex(G,u) ➢ 取边信息 Getarc(G,u,v) ➢ 查询第一个邻接点 FirstVex(G,u) ➢ 查询下一个邻接点 NextVex(G,u,v) ➢ 插入顶点 InsertVex(G,v) ➢ 删除顶点 DeleteVex(G,v) ➢ 插入边 InsertArc(G,v,w) ➢ 删除边 DeleteArc(G,v,w) ➢ 遍历图 Travers(G,tag)
图的存储结构
邻接矩阵
1、图的邻接矩阵——表示图的各顶点之间关系的矩阵。 ▲定义—— 设G=(V,E)是n个顶点的图，则G的邻接矩阵为下列n阶方阵： A[i][j] = 1； 若 (Vi ,Vj )或< Vi ,Vj >∈E(G) && 否则 A[i][j]= 0； ▲结论： （1）无向图的邻接矩阵是对称的； （∵ (Vi ,Vj )∈E(G)，则(Vj ,Vi )∈E(G) ） （2）从邻接矩阵容易判断任意两顶点间是否有边相联； 容易求出各顶点的度； 无向图：顶点Vi 的度D(Vi )=矩阵中第 i 行或第 j 列元素之和 有向图：OD(Vi) = 矩阵中第 i 行元素之和 ID(Vi) =矩阵中第 i 列元素之和 2、 带权图(网)的邻接矩阵 A[i][j]= Wij 若 (Vi ,Vj )或< Vi ,Vj >∈E(G) //（Wij 为边或弧的权） A[i][j]= ∞ Vi 、Vj 间无边或弧 3、邻接矩阵的类型定义 const int vnum=20; typedef struct gp { VertexType vexs[vnum]; //顶点信息 WeightType arcs[vnum][vnum]; //邻接矩阵 int vexnum,arcnum; //顶点数，边数 } WGraph; 4、建立无向带权邻接矩阵： ➢ 将矩阵A的每个元素都初始化为最大值。 ➢ 然后读入边和权值（i，j，Wij ），将A的相应 元素设为Wij 。
//建立无向带权邻接矩阵 Void CreatGraph(Graph *g) { int i, j, n, e, w; char ch; scanf(“%d %d”,&n, &e); //输入顶点数和边数 g->vexnum = n; //顶点数 g->arcnum = e; //边数 for (i=0; i < g->vexnum; i++) { scanf(“%c”,&ch); g->vexs[i] = ch; } for (i=0; i < g->vexnum; i++) for (j=0; j < g->vexnum; j++) g->arcs[i][j]=MAX_INT; for (k=0; k < g->arcnum; k++) { scanf(“%d %d %d”,&i, &j, &w); g->arcs[i][j]= w; g->arcs[j][i]= w; } }
【例题】
邻接表
定义：对图G中每个顶点都建立一个单链表，第 i 个 单链表（称边表）链接图中与顶点Vi 相邻接的所有顶点。 ▲每个链表均设一表头结点（以向量存储，称顶点表） V[i]—第 i 个链表的表头结点； V[i].vertex — 存放顶点Vi 的信息； V[i].firstarc — 指向Vi 的邻接链表的第一个结点。 结论： 1）n个顶点、e条边的无向图，则其邻接表的表头结点数为n， 链表结点总数为2e； 2）对于无向图，第i个链表的结点数为顶点V 的度； 对于有向图，第i个链表的结点数为顶点V 的出度； 3）在边稀疏时，邻接表比邻接矩阵省单元； 4）邻接表表示在检测边数方面比邻接矩阵表示效率要高。
边表
表头结点
邻接表
b）无向图
a）有向图
【例题】
【例】
邻接表的类型定义
#define vnum 20 Typedef struct arcnode { int adjvex; //下一条边的顶点编号 WeightType weight; //带权图的权值域 struct arcnode *nextarc；//指向下一条边的指针 } ArcNode; Typedef struct vexnode { int vertex; //顶点编号 ArcNode *firstarc; //指向第一条边的指针 } AdjList[vnum]; Typedef struct gp { AdjList adjlist; int vexnum,arcnum; //顶点和边的个数 } Graph;
计算图的度
➢ 对于无向图，第 i 个链表的结点数为顶点Vi 的度； ➢ 对于有向图，第 i 个链表的结点数只为顶点Vi 的出度；若要求入度， 必须遍历整个邻接表。在单链表中，其邻接点域的值为i的结点个数是顶点Vi 的入度。 ➢ 对于有向图，有时候就要建立一个你邻接表。即队每个顶点Vi 建立 一个以Vi 为弧头的邻接点的链表。这样，逆邻接表第 i 个单链表中的结点个数就是Vi 的入度。
带权图邻接表
结点形式
无向带权图的邻接表
有向带权图的邻接表、逆邻接表
图的遍历
▲ 遍历的含义及方法： ● 图的遍历——从图G中某一顶点v出发，顺序访问各顶点一次。 ● 方法： 为克服顶点的重复访问，设立辅助数组visited[n]。 visited[i] = 1 顶点 i 已被访问过 visited[i] = 0 顶点 i 未被访问过 遍历方法 深度优先搜索法 （纵向搜索：类二叉树的先序遍历） 广度优先搜索法 （横向搜索：类二叉树的层次遍历）
连通图的深度优先搜索（DFS）
一、过程 从图G(V,E)中任一顶点Vi 开始，首先访问Vi ，然后访问Vi 的任 一未访问过的邻接点Vj ，再以Vj 为新的出发点继续进行深度优先 搜索，直到所有顶点都被访问过。 二、算法： ▲分析： a、为克服顶点的重复访问，设立一标志向量visited [n]; b、图可用邻接矩阵或邻接表表示； c、DFS规则具有递归性，故需用到栈。 注意： ➢ 搜索到达某个顶点时(图中仍有顶点未被访问)，如果这个顶点的所有邻接点都被访问过，那么搜索就要回到前一个被访问过的顶点，再从该顶点的下一未被访问的邻接点开始深度优先搜索。 ➢ 深度搜索的顶点的访问序列不是唯一的。
连通图的深度优先搜索的算法
Dfs (Graph g, int v) { 访问 v； visited[v]=1; // visited[v]初值都为0，顶点v已被访问，就置为1 //找出g中v的第一个邻接点w； while (w存在) { if w 未被访问Dfs(g,w); w=g中v的下一个邻接点；} }
对图按深度优先遍历的递归算法（邻接表）：O(n+e)
int visited[N] = 0 ; /*对访问标记visited数组初始化*/ void Dfs ( Graph g , int v ) { //从第v个顶点出发递归地深度优先遍历图g，图以邻接表作为存储结构 ArcNode *p ; printf ( “%d”,v ) ; /* 访问起始顶点v*/ visited [v] = 1; /* 置“已访问”标记*/ p = g.adjlist[v].firstarc ; /* 取顶点表中v的边表头指针*/ while ( p != NULL ) /* 依次搜索v的邻接点*/ { if ( ! visited[p->adjvex] ) /*v的一个邻接点未被访问*/ Dfs ( g,p->adjvex ) ; /*沿此邻接点出发继续DFS*/ p = p->nextarc ; /* 取v的下一个邻接点*/ } }
对图按深度优先遍历的递归算法（邻接矩阵）O(n^2)
int visited[N]=0 ; /*对访问标记visited数组初始化*/ void Dfs ( Graph g , int v ) { //从第v个顶点出发递归地深度优先遍历图g，图以邻接矩阵作为存储结构 int j ; printf ( “%d”,v ) ; /* 访问起始顶点v*/ visited [v] = 1; /* 置“已访问”标记*/ for (j=0;j<n;j++) /* n为顶点数，j为顶点编号*/ { m=g->arcs[v][j]; /*顺序访问矩阵的第v行结点*/ if （m&&!visited[j]） /*如果v与j邻接，且 j 未被访问*/ Dfs ( g,j ) ; /*递归访问j*/ } }
连通图的广度优先搜索法（BFS）
一、过程 从图G(V,E)中某一点Vi 出发，首先访问Vi 的所有邻接点（W1 ，W2 ，…，Wt ），然后再顺序访问W1 ，W2 ，…，Wt 的 所有未被访问过的邻接点…., 此过程直到所有顶点都被访问过。 三、算法： ▲分析： a、为克服顶点的重复访问，设立一标志向量 visited [n]; b、图可用邻接矩阵或邻接表表示； c、顶点的处理次序——先进先出，故需用到一队列 ▲广度优先遍历算法基本思想： 1. 所有结点标记置为“未被访问”标志； 2. 访问起始顶点，同时置起始顶点“已访问”标记; 3. 将起始顶点进队列； 4. 当队列不为空时重复执行以下步骤； 1）取当前队头顶点； 2）对与队头顶点相邻接的所有未被访问过的顶点依次做： (a)访问该顶点； (b)置该顶点为“已访问”标记,并将它进队列； 3）当前队头元素顶点出队； 4）重复进行，直到队空时结束。
广度优先遍历算法
int visited[N] = 0 ; /*对访问标记visited数组初始化*/ int queue[N] ; /*队列queue存放已访问过的顶点*/ void bfs (Graph g , int v ) { // 从顶点v出发，按广度优先遍历图g，图用邻接表表示 printf(“%d”,v ); visited [v] = 1; /*访问初始顶点v */ rear = 1; front = 0; queue[rear] = v ; /* 起始顶点（序号）入队*/ while ( front != rear ) /*队列不空，则循环*/ { front = (front+1)%N ; /*置队头*/ v = queue[front]; /* 队头元素出队*/ p = g.adjlist[v].firstarc; /*取刚出队顶点v的边表的头指针*/ while ( p != NULL ) { /* 依次搜索v的邻接点*/ { if ( ! visited[p->adjvex]) /*v的一个邻接点未被访问*/ { printf (“%d”,p->adjvex) /*访问此邻接点*/ visited[p->adjvex] = 1 ; rear = (rear+1)%N ; /*队尾指针增1*/ queue[rear] = p->adjvex; /*访问过的顶点入队*/ } p = p->nextarc; } /* 找v的下一个邻接点*/ } ｝ } /*bfs*/
Bfs (Graph g, int v) { LkQue Q; //Q为链队列 int j; InitQueue(&Q); printf(“%d”,v); //v为访问的起始结点 visited[v] = 1; //访问过的标志 EnQueue(&Q, v); while ( ! EmptyQueue(Q)) //判队列是否为空 { v = Gethead(&Q); OutQueue(&Q); //出队列 for (j = 0; j < n; j++) //n为顶点数，变化j依次尝试v的可能邻接点 { m = g->arcs[v][j]; if (m && !visited[j]) //判断是否邻接点，且未被访问 { printf(“%d”,j); visited[j] = 1; //置被访问标志 EnQueue(&Q ,j); //邻接点入队列 } } } }
应用举例--求图的连通分量
1、判断图的连通性 对图G调用一次DFS或BFS，得到一顶点集合，然后将 之与V(G)比较，若两集合相等，则图G是连通图，否则就 说明有未访问过的顶点，因此图不连通。 2、求图的连通分量 从无向图的每个连通分量的一个顶点出发遍历， 则可求得无向图的所有连通分量。 算法： void trace( Graph G ) { /*G为用邻接矩阵或邻接表表示的有n个顶点的无向图，求 该图的连通分量*/ int i; for ( i=0; i<N; ++i ) if (!flag[i]) { dfs(i); /*调用DFS算法的次数仅决定于连通分量个数*/ OUTPUT ；/*输出访问到的顶点和依附于这*/ /*些顶点的边，就得到一个连通分量*/ } } /*trace*/
图的应用
一、生成树 1、生成树定义：连通图G=(V,E)，从任一顶点遍历，则图中边分成两部分： E(G) = T(G)+ B(G) ：遍历通过的边 + 剩下的边(即遍历时未通过的边） 则G’(V，T)为G的子图，称之为G的一棵生成树。 ● 深度优先生成树：按深度优先遍历而得的生成树 ● 广度优先生成树：按广度优先遍历而得的生成树 注：● 生成树G’是图G的极小连通子图。 即V(G)=V(G’)，G’是连通的，且在G的所有连通子图中边数最少（n个顶点，n-1条边）。 ● 图的生成树不是唯一的。 二、最小生成树★ 1、问题的提出： ● 通讯网： 网中n个顶点——n个城市 两顶点间的边——两城市间线路 边的权——架设相应线路的费用 ● 问题1：n个城市间的通讯网，至少要多少条线路？（n-1） n个城市间最少的可行的通讯线路就是一棵生成树 ● 问题2：选择怎样的n-1条线路，使总费用最少？ 网上问题：取n-1条边，并使边权总和为最少。 最小生成树问题 2、最小生成树定义 给定一个带权图，构造带权图的一棵生成树， 使树中所有边的权总和为最小。 3、最小生成树的构造算法 Prim算法和kruskal算法 三、最小生成树的构造方法（Prim法） 基本思想： 假设G=(V,E)是一个无向带权图，生成的最小生成树为MinT=(V,T),其中V为顶点的集合，T为边的集合。求T的步骤如下： 1. 初始化U={u0 }，T={ }；其中U为一个新设置的顶点的集合，初始U中只含有顶点u0，这里假设在构造最小生成树时，从顶点u0出发； 2. 对所有u∈U，v∈V-U(其中u，v表示顶点)的边(u,v)中，找一条权最小的边(u’,v’)，将这条边加入到集合T中，将顶点v’加入到集合U中； 3. 如果U=V，则算法结束；否则重复2、3步。 最后得到最小生成树MinT=<V,T>,其中T为最小生成树的边的集合 步骤： 已选顶点集U； 剩余顶点集V-U ； 已选集TE 四、最小生成树的构造方法 （ Kruskal克鲁斯卡尔法 ） 基本思想： 1.设G=(V,E),令最小生成树初始状态为只有n个顶点而无边的非联通图T=（V，{ }），每个顶点自成一个连通分量； 2.在E中选取权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T 中，否则，舍去此边，选取下一条权值最小的边； 3.以此类推，重复2，直至T中所有顶点都在同一连通分量上为止。 步骤 最小权边及权 动作 最小生成树
Prim法构造最小生成树
最小生成树的构造方法（Prim法） 适合于求边稠密的带权图的最小生成树。 设G=（V，E）是个无向带权图，U是最小生成树的顶点集合，T是最小生成 树的边集合，则Prim算法描述如下： Prim ( Graph G ) { /*构造图G的最小生成树*/ 从G中任选一顶点p∈V ； U={ p }； T={ }； while ( U≠V ） { 在p∈U，q∈V-U中找一条权最小的边（p,q）； U=U+{ q } ; T=T+{（p,q）}; } }/*Prim*/
Kruskal克鲁斯卡尔法
最小生成树的构造方法（Kruskal法） 适合于求边稀疏的网的最小生成树。 ◆原则：按权值递增次序构造Tmin ； 即每次选权最小且不构成回路的边,直至n-1条。 ◆Kruskal方法形式描述： Kruskal （ Graph G ) { /*构造图G的最小生成树*/ n=G的顶点数 ; V(T)=V(G); E(T)={ };/*T初始化为n个顶点而无边的图*/ while ( E(T)中边数 < n-1 ） { 从E(G)中选择最小权的边（v,w）； 从E(G)中删去边（v,w）； if（（v,w）加到T中不形成回路 ） 则将边（v,w）加入T中； } }/*Kruskal*/ 算法时间复杂度：O(eloge)
拓扑排序
●定义:若有向图G中，顶点表示活动或任务，边表示活动或任务之间的优先关系， 则称G为AOV网络，即顶点表示活动的网络(Activity on vertex network)。 ●定义：在一个AOV网中， 称i为j的前趋当且仅当i到j有一条有向路径 称i为j的直接前趋当且仅当有边<i,j> AOV网不能出现回路(否则自己以自己为前提，不合理) 如何检测AOV网中有无回路？ 拓扑排序 二、什么叫拓扑排序？ ● 定义：对AOV网构造顶点线性序列（…i,…,k ,…j,…） i 是 j 的前趋，则 i 在 j 之前，若 i、k 间无路径，则或 i 在 k 前，或 k 在i前。这样的线性序列称为拓扑有序序列。 ● 定义：拓扑有序序列的构造过程称为拓扑排序。 三、拓扑排序方法 ● 过程： (1) 在AOV网中选一个无前趋的顶点并输出之； (2) 从AOV网中删去该顶点及以它为尾的所有弧。 重复(1)、(2)直至没有无前趋的顶点为止。 结果： .n个顶点全部输出，则此图中无回路，且得到拓扑序列； .＜n个顶点被输出，则说明图中有回路。 （工程不可行） 四、拓扑排序算法 ● AOV网的物理表示：AOV网用邻接表表示，且在顶点表中为每个顶 点增加一个存放顶点入度的域in，以指示各顶点当前的入度值，即： vertex in firstarc ● 拓扑排序算法的基本思想： 为避免重复查找，可将入度为0的顶点入度域串链成一个链式栈。 （1）将全体入度为0 的顶点入栈； （2）链栈非空时，反复执行： ● 弹出栈顶元素Vj 并将其输出； ● 检查V 的出边表，将每条出边（Vj ，Vk ）的终点Vk 的入度域减1； ● 若Vk 的入度为0，则Vk 入栈。 （3）若输出的顶点数小于N，则输出有回路；否则，拓扑排序结束。 拓扑排序算法的时间复杂度为O(n+e)，n 是图的顶点个数，e 是图的弧的数目。
六 查找表
基本概念
▲查找表——由同一类型的数据元素（或记录）构成的集合。 ▲关键字（键）——用来标识数据元素的数据项称为关键字，简称键；其值称为键值。 ▲主关键字——可唯一标识各个数据元素的关键字 ▲查找——根据给定的某个k值，在查找表寻找一个其键值等于k的数据元素。 ▲静态查找表—进行的是引用型运算 ▲动态查找表—进行的是加工型运算
静态查找表
查找表用顺序表表示
const int maxsize=20 //静态查找表的表长 typedef struct { TableElem elem[maxsize+1]；/*一维数组，0号单元留空*/ int n； /*最后一个元素的下标，也即表长*/ }SqTable ;
typedef struct { keytype key ; /*关键字域 */ … /*其它域*/ } TableElem ;
顺序表上的查找——顺序查找
一、过程 从表中最后一个记录开始顺序进行查找，若当前记录的关键字=给定值，则查找成功；否则，继续查上一记录…；若直至第一个记录尚未找到需要的记录，则查找失败。 二、算法 方法一：使用一种设计技巧：设立岗哨 int SearchSqtable(Sqtable T, KeyType key） { /*在顺序表R中顺序查找其关键字等于key的元素。若找到，则函数值为该元素在表中的位置，否则为0*/ T.elem[0].key = key; i=T.n; while ( T.elem[i].key != key ) i- - ; return i ; }
三、算法分析
不成功查找：ASL=n+1 ▲顺序查找优点：简单，对表无要求； ▲顺序查找缺点：比较次数多。
有序表上的查找——二分查找★
1、二分查找思想： 每次找中项： ▲中项是，则找到； ▲否则，根据此中项的关键字与给定关键字的关系，决定在表的前或后半部继续找。 关键点。可使下次查找范围缩小一半。 二分查找基本思想：每次将处于查找区间中间位置上的数据元素与给定值K比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为0（查找不成功）为止。 2、二分查找过程：表头指针low=1 表尾指针high=n (1)求中间点 mid=⌊(low+high)/2⌋ { item[1],…, item[mid-1], item[mid], item[mid+1],…, item[n] } (2)给定关键字k与中项记录关键字比较 ① K＜item [mid].key，则所查记录落在表的前半部； 继续在前半部找，此时low不变，high=mid-1 ② K＝item [mid].key，则查找成功，中项即是，结束； ③ K＞item [mid].key，则所查记录落在表的后半部； 继续在后半部找，此时low=mid+1，high不变 (3)若low≤high，则转(1)，否则查找不成功。
二分查找算法
int SearchBin ( SqTable T, KeyType key ) { /*在有序表R中二分查找其关键字等于K的数据元素；若找到，则返回该元素在表中的位置，否则返回0 */ int low,high; low = 1 ; high = T.n ; while ( low <= high ) { mid = (low+high)/2 ; if (key==T.elem[mid].key) return mid; else if (key＜T.elem[mid].key ) high = mid-1 ; else low = mid+1 ; } return (0) ; }
算法分析
查找成功时：比较次数最多为 ：⌊log2 n⌋+1 查找不成功时：比较次数最多也为：⌊log2 n⌋+1 二分查找算法每进行一次键值与给定值的比较，查找区间的长度至少减小为原来二分之一，“二分查找”由此得名。由此易推算出二分查找的查找长度不超过⌊log2 n⌋+1。 二分查找的平均查找长度为：ASLb =[(n+1)/n]*(log2(n+1)-1) 当n较大时可得：ASLb 约等于 log2(n+1)-1 由此可见，二分查找 的时间性能比顺序查找好。而相比顺序查找而言，二分查找要求表元素是排好序的。当采用的存储结构不是顺序表，或者顺序表中元素未按键值的次序（递增或递减）排列时，则不能进行二分查找。
索引顺序表的查找——分块查找
查找过程： 1.先建立最大（或小）关键字表——索引表（有序） 即将每块中最大（或最小）关键字及指示块首记录在表中位置的指针依次存入一张表中，此表称为索引表； 2.查找索引表，以确定所查元素所在块号； 将查找关键字k与索引表中每一元素（即各块中最大关键字）进行比较，以确定所查元素所在块号； 3.在相应块中按顺序查找关键字为k的记录。
算法分析 分块查找的平均查找长度等于两阶段各自的查找长度之和。若每块含S个元素，且第一阶段采用顺序查找，则在等概率假定下，分块查找的平均长度为： ASLbs = (1/2)*[(n/s)+s] +1 其中，n为顺序表中的数据元素数目。当 s 取 根号n 时，ASLbs达到最小值 根号n +1 静态查找表的上述三种不同实现各有优缺点。其中， 顺序查找效率最低但限制最少。 二分查找效率最高，但限制最强。 而分块查找则介于上述二者之间。在实际应用中应根据需要加以选择。
二叉排序树
表结构是在查找过程中动态生成的；对于给定值k，若表中存在其关键 字等于k的记录，则查找成功返回，否则在表中插入关键字等于k的记录。 ●什么是二叉排序树？ 一棵二叉排序树(Binary Sort Tree)(又称二叉查找树)或者是一棵空二叉树，或者 是具有下列性质的二叉树： ① 若它的左子树不空，则左子树上所有结点的键值均小于它的根结点键值； ② 若它的右子树不空，则右子树上所有结点的键值均大于它的根结点键值； ③ 根的左、右子树也分别为二叉排序树。 ●性质： 中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列。 二叉排序树上的查找： 1、过程： 当二叉排序树不空时，首先将给定值和根结点的关键字 比较,若相等,则查找成功；否则根据给定值与根结点关键字 间的大小关系，分别在左子树或右子树上继续进行查找。 2、二叉排序树查找算法 注： (1)二叉排序树，对每个结点，均有： 左子树上的所有结点键值都比根的小； 右子树上的所有结点键值都比根的大。 (2)构造二叉排序树的同时也对序列排序了。
算法
BinTree SearchBST(BinTree bst ,KeyType key) /*在根指针bst所指的二叉排序树上递归地查找键值等于key的结点。若成功，则返回指向该结点的指针，否则返回空指针*/ { if (bst == NULL) return NULL; //不成功时返回 NULL 作为标记 else if (key == bst->key) return bst; //成功时返回结点地址 else if ( key < bst->key) return SearchBST (bst->lchild, key); //继续在左子树中查找 else return SearchBST (bst->rchild, key); //继续在右子树中查找 }
由上面的查找过程可知：在二叉排序树上进行查找，若查找成功，则是从根结点出发走 了一条从根结点到待查结点的路径；若查找不成功，则是从根结点出发走了一条从根到 某个叶子的路径。因此与二分查找类似，关键字比较的次数不超过二叉树的深度。
二叉排序树的插入和生成★
对序列R={k1 ，k2 ，…，kn }， k1 ～ kn 均为关键字值，则 按下列原则可构造二叉排序树： (1)令k1 为根； (2)若k1 ＜k2 ，则令k2 为k1 的右孩，否则为左孩； (3) k3 ，k4 ，…，kn 递归重复（2）
【例题】查找键值序列为{50, 48, 24，55，53，50, 90}，则生成的二叉排序树如图6-6所示。 中序遍历结果正好是键值有序的
二叉排序树的查找分析
二叉排序树上的平均查找长度是介于O(n)和O(log2 n)之间的，其查找效率与树的形态有关。
【例题】假设5个元素的查找概率相等均为1/5，则图6-7a的平均查找长度为 ASL(a) = (1+2+2+3+3)/5 = 11/5 需要在二叉排序树的动态变化过程中随时调整其形态，使之保持“平衡”。二叉排序树的平均查找长度ASL ≤ 1+log2 n。
O(log2n)~O(n)之间
散列表（哈希表）
◆散列函数（哈希函数）——设记录表A，长为n，ai（1≤i≤n）为表中某一元素，ki 为其关键字，则关键字ki 和元素ai 在表中的地址之间有一函数关系，即： ◆散列地址——由散列函数决定数据元素的存储位置，该位置称为散列地址。 ◆散列表——通过散列法建立的表称为散列表。 ◆冲突： k1 ≠ k2 但 H（k1 ）= H（k2 ）的现象称为冲突。 即：不同的关键字映射到同一存储单元。 并称k1 和k2 是同义词。
常用散列法
1、数字分析法（见P173） 2、除留余数法 ▲散列函数：取关键字被某个不大于散列表长m的数p除后所得余数作为散列地址。 即： H(key)= key mod p （p≤n ） ▲例： 一组关键字从000,001 ～ 859,999 散列地址为：0 ～ 5999 即 m=6000 取 p=5999 ——余数r在0～5999范围内 H=k mod 5999 设：k=172,148 则：H=k mod p = 172148 mod 5999 = 4176 方法关键——如何取p ？ ★结论：①p不取偶数 ②p不取关键字字符基的n倍 ③一般选p为质数且最接近表长m的质数 3、平方取中法（见P174） 平方取中法以键值平方的中间几位作为散列地址。这一方法计算简单，是一种较常用的构造散 列函数的方法，通常在选定散列函数时不一定能知道键值的分布情况。取其中哪几位也不一定 合适，而一个数平方的中间几位与这个数的每一位都有关，所得散列地址比较均匀。 4、基数转换法（见P174）
数字分析法
基数转换法
散列表的实现
线性探测法
用“线性探测法”处理冲突构造散列表 ●思想：计算出的散列地址已被占用，则按顺序找“下一个”空位。 ●过程：设有散列表HT（向量），对给定记录R，其关键字k，对应哈希地址H(k)=>j ★要点： ①HT[ j]空，则R填入； ②HT[ j].key=k，则输出； ③否则，按顺序一步步找“下一个”空位，将R填入。 ●例：已知一组关键字为（13，41，15，44，06，68，25，12，38，64，19，49），按散列函数H(key)=key mod 13 和线性探测法处理冲突构造散列表。 ●散列法的优缺点： 优点：直接由关键字通过哈希函数计算出哈希地址，查找效率高； 缺点：常发生冲突，影响查找效率。
二次探测法
二次探测法的基本思想：生成的后继散列地址不是连续的，而是跳跃式的，以便为 后续数据元素留下空间从而减少堆积。按照二次探测法，键值key的散列地址序列为 d0 =H(key) dj = (d0 +i) mod m
【例】
1. 已知散列表的地址空间为0~10，散列函数为H(key) = key mod 11 (mod 表示求余运算)，采用二次探测法解决冲突，试用键值序列 20，38，16，27，5，23，56，29 建立散列表，并计算出等概率情况下查找成功的平均查找长度。
2. 如图6-9所示长度为13的散列表中，用二次探测法插入键值为29的元素。
二次探测法的缺点是不易探测到整个散列表的所有空间，也就是说，上述后继散列地址可能难以包括散列表的所有存储位置。
链地址法
即用“链地址法”处理冲突 ●思想：将散列地址相同记录存储在同一单链表中（称同义词表），同时按散列地址设立一个表头指针向量。【HP】 ●例：已知一组关键字为（13，41，15，44，06，68，25，12，38，64，19，49），按散列函数H(key)=key mod 13 和链地址法处理冲突构造散列表。
链地址是对每一个同义词都建一个单链表来解决冲突，其组织方式如下： 设选定的散列函数为H, H的值域(即散列地址的范围)为0〜(n-1)。设置一个“指针向量”Pointer HP [n]，其中的每个指针HP[i]指向一个单链表，该单链表用于存储所有散列地址为i的数据元素。每一个这样的单链表称为一个同义词子表。 例如，若选定的散列函数为H(key)=key mod 13,已存入键值为26，41，25，05, 07，15，12, 49, 51, 31,62的散列表，如图6-10所示。
多重散列法
此法要求设立多个散列函数Hi ，i=1，…，k。当给定值key与散列表中的某个键值是相对于某个散列函数氏的同义词而发生冲突时，继续计算这个给定值key在下一个散列函数Hi+1 下的散列地址，直到不再产生冲突为止。这种方法的优点是不易产生“堆积”，缺点是计算量较大。
公共溢出区法
按这种方法，散列表由两个一维数组组成。一个称为基本表，它实际上就是 上面所说的散列表，另一个称为溢出表。插入首先在基本表上进行，假如发 生冲突，则将同义词存入溢出表。这样，基本表不可能发生“堆积”。
查 找 小 结
▲熟练掌握顺序表和有序表的查找方法和算法； ▲掌握二叉排序树的定义、构建方法和查找方法； ▲什么是散列方法、什么是冲突？ ▲熟练掌握散列表的构造和查找及冲突的处理； ▲按定义计算各种查找方法在等概率情况下查找成功的平均查找长度。
七 排序
概述
▲数据排序——将一个文件的记录按关键字不减（或不增）次序排列，使文件成为有序文件，此过程称为排序。 ▲稳定排序——若排序后，相同关键字的记录保持它们原来的相对次序，则此排序方法称为～。 ▲不稳定排序—— ▲排序类型—— 内部排序：全部数据存于内存； 外部排序：需要对外存进行访问的排序过程 内部排序 按方法分 插入排序、交换排序、选择排序、归并排序 ▲排序文件的物理表示：数组表示 ▲排序指标（排序算法分析）： 存储空间 比较次数
数组表示
typedef struct { int key; /*关键字项*/ ItemType otheritem ; /*其他数据项*/ }RecordType; typedef RecordType list[n+1];
list R; R[0] R[1] R[2]….R[n] R[i].key——第i个记录的关键字
插入排序（通过比较插入实现排序）
▲直接插入排序 1.过程： 对R1 ，…，Ri-1 已排好序，有K1 ≤K2 ≤….≤Ki-1 ， 现将Ki 依次与Ki-1 ，Ki-2 ，…进行比较，并移动元素， 直到发现Ri 应插在Rj 与Rj+1 之间(即有Kj ≤Ki ＜Kj+1 )， 则将R 插到j+1号位置上，形成i个有序序列。 （i从2～n） 4.算法分析： ● 存储空间 n+1；（1为附加空间） ● 时间复杂度 O(n2) ● 稳定性：稳定排序；
▲直接插入排序算法
void StraightInsertSort( list R,int n) { /*用直接插入排序法对R进行排序*/ for( i=2; i<=n; i++ ) { R[0]=R[i]; j=i-1; while ( R[0].key<R[ j].key ) { R[ j+1]= R[ j]; /*记录后移*/ j--; } R[ j+1]=R[0] ; /*插入*/ } }
记录R[0]有两个作用，其一是进入查找循环之前，它保存了R[i]的值，使得不致于因记录的后移而丢失R[i]中的内容；其二是起岗哨作用，在while循环中“监视”数组下标变量j是否越界，一旦越界(即j<1), R[0]自动控制while循环的结束，从而避免了在while循环中每一次都要检测j是否越界。这一技巧的应用，使得测试循环条件的时间大约减少一半。
交换排序（通过比较交换实现排序）
冒泡排序
基本思想
通过多次重复比较、交换相邻记录而实现排序；每一趟的效果都是将当前键值最大的记录换到最后。
试对下列待排序序列用冒泡排序法进行排序,给出每趟结果: { 49，38，65，97，76，134，27，49 } 第一趟： 38 49 65 76 97 27 49 [ 134 ] 第二趟： 38 49 65 76 27 49 [ 97 134 ] 第三趟： 38 49 65 27 49 [ 76 97 134 ] 第四趟： 38 49 27 49 [ 65 76 97 134 ] 第五趟： 38 27 49 [ 49 65 76 97 134 ] 第六趟： 27 38 [ 49 49 65 76 97 134 ] 第七趟： 27 [ 38 49 49 65 76 97 134 ]
冒泡排序算法
void BubbleSort( List R,int n) { /*用冒泡排序法对R[1]…R[n]进行排序*/ /*endsort:标志文件是否已排好序*/ for( i=1; i<=n-1; i++ ) { endsort=0; /*若循环中记录未作交换,则说明序列已有序*/ for( j=1; j<=n-i-1; j++ ){ if( R[ j].key > R[ j+1].key ) { temp=R[ j]; R[ j]=R[ j+1]; R[ j+1]=temp; endsort=1； } } if(endsort==0) break; } }
算法分析
●时间复杂度：外循环最多n-1次（最少1次），第i次外循环时，内循环n-i次比较，
●稳定性：稳定排序。
快速排序★
基本思想
通过分部排序完成整个表的排序； 首先取第一个记录，将之与表中其余记录比较并交换，从而将它放到记录的正确的最终位置，使记录表分成两部分 其一（左边的）诸记录的关键字均小于它； 其二（右边的）诸记录的关键字均大于它； 然后对这两部分重新执行上述过程，依此类推，直至排序完毕。
过程
记录序列{ r[h],r[low+1],…,r[p] } 设：左指针i，右指针j; 初值：i=h； j=p; 处理元素=>x ; (1) j 指针逐步左移，即： 将r[ j]与x比较，j不断减1，直到发现某个 r[ j].key<x.key时，则： r[ j]=>i位置上（开始时i=1）；i+1=>i; 转(2) (1)j指针逐步左移，即： 将r[ j]与x比较，j不断减1，直到发现某个 r[ j].key<x.key时，则： r[ j]=>i位置上（开始时i=1）；i+1=>i; 转(2) (2) i 指针逐步右移，即： 将r[i]与x比较，i不断增1，直到发现某个 r[i].key＞x.key时，则： r[i]=>j位置上； j-1 => j; 转(1); 此过程直到(1)或(2)中i=j时停止，此时将处理元素x 送到i或j位置上，它将原序列分成左、右两个子序列，对 它们分别进行上述过程，直至分裂后的子序列都只有一 个元素为止。
快速排序的第一趟
快速排序的完整过程
算法分析
快速排序算法
void quickpass (list r, int h , int p ) { /*对顺序表r中的子序列r[h]至r[p]进行快速排序*/ i=h; j=p ; /*左右指针置初值*/ x=r[h] ; /*取处理元素（即作为枢轴记录）*/ while ( i ＜ j ) /*左右指针未碰头则反复做：*/ { while ( r[j].key > x.key && i < j ) --j ; /*右边未找到小关键字，则右指针j继续左移*/ if ( i < j ) /*右边找到比枢轴记录小的记录，则将其送到左边*/ { r[i]=r[j] ; ++ i ; } while ( r[i].key <= x.key && i < j ) ++i; /*边未找到大关键字，则左指针i继续右移*/ if ( i < j ) /*左边找到比枢轴记录大的记录，则将其送到右边*/ { r[j]=r[i] ; - - j ; } } r[i]=x ; /*枢轴记录定位*/ if ( h < i-1 ) quickpass( r, h, i-1 ) ; /*对左子序列进行快速排序*/ if (j+1 < high) quickpass ( r, j+1, p) ; /*对右子序列进行快速排序*/ }
选择排序（以重复选择的思想为基础进行排序）
直接选择排序
过程
设记录R1 ，R2 …，Rn ，对i=1，2，…，n-1，重复下列工作： (1) 在Ri ，…，Rn 中选最小(或最大)关键字记录Rj ； (2) 将Rj 与第i个记录交换位置，即将选到的第 i 小的记录换到第i号位置上。
算法
▲直接选择排序算法： void SelectSort( List R, int n ) { for ( i=1 ; i < =n-1 ; i++ ) { min=i ; /*选择第i小的记录，并交换位*/ for ( j=i+1; j<=n; j++ ) if ( R[j].key < R[min].key ) /*在R[i]…R[n]中找最小者*/ min=j ; if ( min!=i ) /*交换记录*/ { temp=R[i] ; R[i]=R[min] ; R[min]=temp ; } } }
不稳定性
算法分析
●空间：n+1； （1为附加空间） ●稳定性：不稳定排序
堆排序
堆
堆： 集合{ K1 , K2 , …., Kn }， 对所有 i =1,2,…,n/2 有： Ki ≤K2i 且 Ki ≤K2i+1， 则此集合称为堆（最小堆）; （或Ki ≥K2i 且Ki ≥K2i+1 最大堆） 例： ｛13,40,27,88,55,34,65,92｝(最小堆) ｛92,65,88,40,55,34,13,27｝(最大堆) 下标： 1 2 3 4 5 6 7 8 对应的完全二叉树
建堆（筛选法）：
▲方法： 设记录{ R1 , R2 , …., Rn } (1) 顺序输入成完全二叉树（以数组存储） (2) 从最后一个双亲开始，如果有较小的孩子，则将其沿左或右孩中小的那个方向筛下，一直到不能再筛； (3) 逐次处理完每个双亲。 ▲算法：下筛一个结点算法 (见P195) 建堆：对k=n/2,…,1依次调用sift。
其中n=8，n/2=4，所以 从k4 =34开始执行。
例：判别下列序列是否为堆，如果不是则将之调整为堆。 ｛12,70,53,65,24,56,48,92,86,33｝
堆排序
1）过程： ①从i=int(n/2）→ 1 调用sift(r,i,n)建初始堆 对i=n,n-1,n-2,….,2重复②、③ ②输出r[1],即：r[1] > r[i] ③调用sift(r,1,i-1),重新建堆
算法分析
算法分析： ●空间：n+1； （仅需一个记录大小的供交换用的辅助存储空间。） ●时间：O(nlog2 n) ●稳定性：不稳定排序
归并排序
有序序列的合并(两个有序表归并成一个有序表)
思想
比较各个子序列的第一个记录的键值，最小的一个就是排序后序列的第一个记录。取出这个记录，继续比较各子序列现有的第一个记录的键值，便可找出排序后的第二个记录。如此继续下去，最终可以得到排序结果。
二路归并排序
思想
① n个记录的表看成n个，长度为1的有序表 ② 两两归并成 n/2 个，长度为2的有序表（n为奇数，则还有1个长为1的表） ③再两两归并为 (n/2)/2 个，长度为4的有序表 再两两归并直至只剩1个，长度为n的有序表； 共log2 n趟
试对下列待排序序列用归并排序法进行排序,给出每趟结果: { 475，137，481，219，382，674，350，326，815，506 } 第一趟：[137 475] [219 481] [382 674] [326 350] [506 815] 第二趟：[137 219 475 481] [326 350 382 674] [506 815] 第三趟：[137 219 326 350 382 475 481 674] [506 815] 第四趟：[137 219 326 350 382 475 481 506 674 815]
算法分析
●空间：n+n； （需n个附加空间） ●时间：O(nlog2 n) ●稳定性：稳定排序
算法
void Merge(List a,List R, int h,int m,int n){ //将ah ,…，am 和am+1 ,…，an 两个有序序列合并成一个有序序列R , …,Rn k=h; j=m+1; //k,j置成文件的起始位置 while ((h<=m) && ( j<=n)){ //将a中记录从小到大合并入R if (a[h].key <= a[j].key){ //a[h]键值小，送入R[k]并修改h值 R[k]=a[h]; h++; } else { //a [ j ]键值小，送入R[k]并修改j值 R[k]=a[j]; j++; } k++; } while (h<=m) {R[k] =a[h];h++; k++;} // j >n,将ah,…,am剩余部分插入R的末尾 while ( j<=n) {R[k] =a[j]; j++;k++;} //h>m,将am+1,…,an剩余部分插入R的末尾 }
小结
各种排序方法的比较
直接快堆不稳定
排序小结
掌握各种排序算法思想、排序过程、稳定性及算法的时间复杂性。 重点：各种排序方法的过程及冒泡排序、快速排序等算法。
浮动主题