《数据结构与算法》PPT课堂课件-第8章-集合

1、1第9章 集合 学习要点:9.1 以集合为基础的抽象数据类型 理解集合的概念。 理解以集合为基础的抽象数据类型。 掌握用位向量实现集合的方法。 掌握用链表实现集合的方法。29.2 符号表 理解抽象数据类型符号表的概念。 掌握数组实现符号表的方法。 理解开散列和闭散列的概念。 掌握用开散列表实现符号表的方法。 掌握除余法、数乘法、平方取中法、基数转换法和随机数法等散列函数构造方法。 掌握采用线性重新散列技术的闭散列表实现符号表的方法。39.3 字典 理解以有序集为基础的抽象数据类型字典。 理解用数组实现字典的方法。 理解二叉搜索树的概念和实现方法。 掌握用二叉搜索树实现字典的方法。 理解AVL树

2、的定义和性质。 掌握二叉搜索树的结点旋转变换及实现方法。 掌握AVL树的插入重新平衡运算及实现方法。 掌握AVL树的删除重新平衡运算及实现方法。49.4 优先队列 理解以集合为基础的抽象数据类型优先队列。 理解用有序字典实现优先队列的方法。 理解优先级树和堆的概念。 掌握用数组实现堆的方法。 理解以集合为基础的抽象数据类型可并优先队列。 理解左偏树的定义和概念。 掌握用左偏树实现可并优先队列的方法。 掌握堆排序算法。59. 5 并查集 理解以不相交的集合为基础的抽象数据类型并查集。 掌握用数组实现并查集的方法。 掌握用树结构实现并查集的方法。 理解将小树合并到大树的合并策略及其实现。 掌握路径

3、压缩技术及其实现方法。69.0 引言9.0.1 集合的概念的原形 银行中所有储户帐号的集合；图书馆中 所有藏书的集合；一个程序中所有标识 符的集合；2003级34班全体同学的集合等 79.0 引言9.0.2 集合的概念与术语 集合：集合是由元素(成员)组成的一个类。 原子：不可再分的元素。 多重集合：允许同一元素在集合中多次出 现的集合称为多重集合。有序集：当由原子组成的集合具有线性序关 系“”时，称该集合为有序集。“”是集合的 一个线性序，它满足： (1)若a、b是集合中任意2个原子,则ab,a=b和 ba三者必居其一；(2)a，b和c是集合中的原 子，且ab，bc则asetsize=siz

4、e; S-arraysize=(size+15)4; S-v=malloc(size*sizeof(unsigned short); for (i=0; ivi=0; return S; 15void SetAssign(Set A, Set B) int i; if (A-setsize !=B-setsize) Error(“Sets are not the same size”); for(i=0; iarraysize; i+) A-vi=B-vi; 16int SetMemeber(int x, Set S) if (x=S-setsize) Error(“Invalid membe

5、r reference”); return S-vArrayIndex() & BitMask(x); 17int ArrayIndex(int x) return x4; unsigned short BitMask(int x) return 1setsize !=B-setsize) Error(“.”); for(i=0; iarraysize; i+) if(A-vi !=B-vi) retval=0; break; return retval; 19Set SetUnion(Set A, Set B) int i; Set tmp=SetInit(A-setsize); for(i

6、=0; iarraysize; i+) tmp-vi=A-vi | B-vi; return tmp; 20Set SetIntersection(Set A, Set B) int i; Set tmp=SetInit(A-setsize); for(i=0; iarraysize; i+) tmp-vi=A-vi & B-vi; return tmp; 21Set SetDifference(Set A, Set B) int i; Set tmp=SetInit(A-setsize); for(i=0; iarraysize; i+) tmp-vi=A-vi (B-vi & A-vi);

7、 return tmp; 22void SetInsert(int x, Set S) if (x=S-setsize) Error(“.”); S-vArrayIndex(x) |=BitMask(x); 23void SetDelete(int x, Set S) if (x=S-setsize) Error(“.”); S-vArrayIndex(x) &=BitMask(x); 249.1 以集合为基础的抽象数据类型9.1.3 ADT集合的简单实现用有序链表实现9.1.3.0 LinkedSet的有序链表结点类型Node的定义Typedef struct node *linkstruc

8、t node ListItem element; link next; Node;259.1 以集合为基础的抽象数据类型9.1.3 ADT集合的简单实现用有序链表实现 9.1.3.1有序链表实现的集合Set的定义Typedef struct list *SetTypedef struct list link first;26Set SetInit( ) Set S=malloc(sizeof *S); S-first=0; return S; 27int SetEmpty(Set S) return S-first=0; 28int SetSize(Set S) int len; link c

9、urrent; current=S-first; len=0; while (current) len+; current=current-next; return len; 29void SetAssign(Set A, Set B) link a,b,c; b=B-first; A-first=0; if (b) A-first=NewNode( ); a=A-first; a-element=b-element; a-next=0; b=b-next; while(b) c=NewNode( ); c-element=b-element; c-next=0; b=b-next; a-ne

10、xt=c; a=c; 30Set SetIntersection(Set A, Set B) link a,b,p,q,r; Set tmp=SetInit( ); a=A-first; b=B-first; p=NewNode( ); q=p; while(a & & b) if(a-element =b-element) r=NewNode( ); r-element=a-element; r-next=0; p-next=r; p=r; a=a-next; b=b-next; else if(a-element element) a=a-next; else b=b-next; if(p

11、!=q) tmp-first=q-next; free(q); return tmp; 31void SetIntsert(ListItem x, Set S) link p,q,r; p = S-first; q = p; while ( p & p-element next; if (p & p-element = x) return; r = NewNode(); r -element =x; r-next = p; if (p = q) S-first = r; else q-next =r; 329.2 符号表9.2.0 引言 ADT符号表的概念 以集合为基础，并支持Member、I

12、nsert和Delete三种运算的抽象数据类型叫做符号表。 ADT符号表的应用 公司的客户字典 一个地区的固定/移动电话号码字典 软件开发中的数据字典 网上的在线字典 互联网/企业网/局域网网管中的IP地址字典等等 339.2符号表9.2.1 实现符号表的简单方法用固定数组typedef struct atab *Table;typedef struct atab int arraysize; int last; SetItem*data;Atab;34Table TableInit(int size) Table T=malloc(sizeof *T); T-arraysize=size;

13、T-last=0; T-data=malloc(size*sizeof(SetItem); return T;35int TableMember(SetItem x,Table T) int I; for(i=0;ilast;i+) if(T-datai=x) return 1;return 0;36void TableInsert(SetItem x,Table T) if(! TableMember(x,T) & T-lastarraysize) T-dataT-last+=x;37void TableDelete(SetItem x,Table T) int i=0; if (T-las

14、t0) while(Y-datai!=x & ilast) i+; if(ilast & T-datai=x) T-datai=T-data-T-last;389.2符号表9.2.1 实现符号表的简单方法用固定数组9.2.1.3 优缺点优点：结构简单，实现操作的逻辑简单。缺点： 所表示的集合的大小受到数组大小的限制。 三个基本操作在最坏情况下都需要O(n)。 通常集合元素并不占满整个数组，因此， 空间没有得到充分利用。399.2符号表9.2.2 实现符号表的简单方法开散列9.2.2.1 基本设想 把符号表中的所有元素散列(hashing)即映射到一 个桶数组(散列表)的桶中。当有多个不同元素被

15、 散列到同一个桶时，这些元素用链在一个表里。 期望散列能均匀，使得当桶数组的规模与字典 的规模同阶时，桶数组的每一个桶中大致有常 数个元素，从而对字典的三个基本操作都只需 要常数时间。 这里的问题是如何散列即如何构造散列(映射)函 数去达到设想的期望？409.2符号表9.2.2 实现符号表的简单方法开散列9.2.2.2 开散列的数据要素 按照设想，开散列首先需要拥有一个桶数组， 桶数组的规模与符号表的规模同阶，桶数组中的 每一个桶有一个指针各指向一个链表。 其次需要拥有一个散列(映射)函数，它把字典 中的元素分别散列(映射，分散)到各桶所对应 的链表中。419.2符号表9.2.2 实现符号表的

16、简单方法开散列9.2.2.3 散列函数的例子 假设符号表的元素是字符串x，桶数组的规模为 101，那么，下面是散列函数的一个具体例子int hash1(char* x) int len=strlen(x), hashval = 0; for(int i=0;isize=nbuckets; H-hf=hashf; H-ht=malloc(H-size*sizeof(List); for(i=0;isize;i+) H-hti=ListInit() return H;45int HTMember(SetItem x,OpenHashTable H) int i=(*h-HF)(x) % H-siz

17、e; return (ListLocate(x,H-hti)0);46void HTInsert(SetItem x,OpenHashTable H) int i; if (HTMember(x,H) Error(“Bad Input”); i=(*h-hf)(x) % H-size; ListInsert(0,x,H-hti);47void HTDelete(SetItem x,OpenHashTable H) int i; i=(*h-hf)(x) % H-size; if (k=ListLocate(x,H-hti) ListDelete(k,H-hti);489.2符号表9.2.3 实

18、现符号表的简单方法闭散列9.2.3.1 与开散列的相同点和区别相同点：把字典中的所有元素散列(hashing)即 映射到一个桶数组(散列表)的桶中。区别：桶数组(散列表)的桶直接用来存放字典 元素，而且一个桶只存放一个元素。出现多个 元素散列到同一个桶时(这叫冲突)，需要按照 确定的规则在桶数组中进行探测，找还没有存 放元素的桶(这叫空桶)，然后将发生冲突的后 到元素放入空桶，解决冲突，实现散列。 499.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.2 闭散列引发的问题(1)需要一个探测函数c(i),i=0,1,2,size-1： c(0)=0,而且对于任意的0jsize-1 (

19、j+c(0)mod size, (j+c(1)mod size, ,(j+c(size-1)mod size是 0,1,2,size-1 的重排,保证不会漏测。(2)需要对ht 的每一个桶的状态加以标记： statek=0表示htk桶存放着元素。 statek=1表示htk桶一直是空桶。 statek=2表示htk桶现在是空桶但曾经存放过元素509.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.3 闭散列的数据要素(1)桶数组的规模size；(2)桶数组ht ；(3)散列函数指针 int (*hf) (T x)；(4)探测函数c(i),i=0,1,2,size-1；(5)桶状态标记

20、数组state ；519.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.4 闭散列表实现的的定义typedef struct hashtable *HashTable;typedef struct hashtableint size;int (*hf)(SetItem x);SetItem *ht;int *state;Hashtable;52HashTable HTInit(int divisor, int (*hashf)(SetItem x)int i;HashTable H=malloc(sizeof *H);H-size=divisor;H-hf = hashf;H-ht

21、=malloc(H-size*sizeof(int);for (i=0;isize;i+)H-statei=1;return H;53int FindMatch(SetItem x,HashTable H)int I,j,k;j=(*H-hf)(x);for (i=0;isize;i+)k=(j+HashProb(i)%H-size;if (H-statek=1) break;if(!H-statek & H-htk=x) return k;return H-size;int HashProb(int i)return i;54int Unoccupied(SetItem x,HashTabl

22、e H)int I,j,k;j=(*H-hf)(x);for (i=0;isize;i+)k=(j+HashProb(i)%H-size;if (H-statek) return k;return H-size;55int HTMember(SetItem x,HashTable H)int i=FindMatch(x,H);if (isize & H-hti=x) return 1;return 0;56int HTInsert(SetItem x,HashTable H)int I;if(HTMember(x,H) Error(“Bad Input”);i=Unoccupied(x,H);

23、if(isize) H-statei=0; H-hti=x; else Error(“table full”);57int HTDelete(SetItem x,HashTable H)int i=FindMatch(x,H);if (isize & H-hti=x) H-statei=2;589.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.5 HashTable的定义中未实现的函数(续)函数HTDelete的缺点： 在执行了大量元素删除运算后，大量的桶的状态 标记为 2 即大量的桶的状态标记既非 1 也非 0 使 得运算FindMatch 中的循环次数大大增加，从而 使得运算F

24、indMatch的速度大大减慢。 因此人们提出HTDelete的一种改进版本HTDelete1599.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.5 HashTable的定义中未实现的函数(续)改进HTDelete的基本思想： 动机是希望腾出的空桶(记为hti)不仅仅可供新元素插入 ，而且能为提高还在桶数组中的元素(比如y= htj)的查 找速度作出贡献：减少查找y的探测次数。 容易理解，如果不作任何改进，查找y的探测次数会等于 插入y时的探测次数。如果插入y时x已在桶hti中且与x发 生冲突而增加了插入的探测次数，那么，现在x不存在了， 只要将x腾出的桶hti让y顶替，就可以使

25、得将来查找y时 减少探测次数。因此改进HTDelete的途径是在当前的桶数 组中找能顶替x的y。如果找不到，就按HTDelete的原版处 理；如果找得到，在用y顶替x之后还可以引起连锁反应。 609.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.5 HashTable的定义中未实现的函数(续)改进HTDelete的细节找能顶替x的y 假设被删除元素x位于桶单元hti。现考察一个非空单元htj 中的元素y，其散列函数值设为h=hf(y)，则按从h出发的线性 探测，只要i比j离h近即可使得在顶替后找y的探测次数减少。 当ij时，若ihj，则不可用元素htj顶替hti；若hij或ijh，

26、则可用元素htj顶替hti。如下图(a)。 当ji时，若jhI，则可用元素htj顶替hti，如下图 (b)；否则不可。 这里以线性探测为前题，以顶替后减少探测次数为目标。619.2符号表9.2.3 实现符号表的简单方法闭散列9.2.3.5 HashTable的定义中未实现的函数(续)(8) 改进HTDelete的函数HTDelete1Void HTDelete1SetItem x,HashTable H) int i=FindMatch(x); if (isize) / &H-hti=x可以去掉 for (;) /找hti的顶替元素 H-statei=2; /先按无顶替元素处理 int j;

27、/从(i+1)%size开始线性搜索可顶替元素 for (j=(i+1)%H-size; !statej; j=(j+1)%H-size) 629.2符号表 int h=(*H-hf) (H-htj);if (h=i&ij)|(ij&jh)|(jh&hstatej) break; /跳出外for循环 H- hti=htj; H-statei=statej; /做顶替工作i=j; /为构成循环找htj的顶替元素 639.2符号表9.2.4 开散列的效率若能选择一个好的散列函数，将集合中的N个元素均匀地散列到B个桶中，那么，每个桶中平均有N/B个元素，使得在开散列表中，Insert，Delete和

28、Member运算都只要O(N/B)的平均时间。进而当N/B为一常数时，字典的每一个运算都可在常数时间内完成。因此：对于开散列表，关键在于选择一个好的散列函数649.2符号表9.2.5 散列函数举例(1)除余法：h(k)=k %m。(2)数乘法：h(k)= 。(3)平方取中法：h(k)= %B。(4)基数转换法 ：(5)随机数法 ：h(k)=random(k)。659.2符号表9.2.6 闭散列的重新散列技术 (1)二次重新散列技术 它选取的探查桶序列为：h(x),h1(x) ,h2(x) ,h2i(x) ,h2i+1(x) , 其中， ， 。 (2)随机重新散列技术 它选取的探查桶序列为： ,

29、i=1，2，B-1。 其中， 是1，2，B-1的一个随机排列。 (3)双重散列技术 这种方法使用2个散列函数h和h来产生探索序列： 其中 i=1，2，B-1。要求h(x)的值和B互素 。669.3.1 字典的定义 字典是以有序集为基础的抽象数据类型。 它支持以下运算： (1)Member(x)，成员运算。 (2)Insert(x)，插入运算：将元素x插入集合。 (3)Delete(x)，删除运算：将元素x从当前集合中删去。 (4)Predecessor(x)，前驱运算：返回集合中小于x的最大元素。 (5)Successor(x)，后继运算：返回集合中大于x的最小元素。 (6)Range(x，y

30、)，区间查询运算：返回集合中界于x和y之间，即xzy的所有元素z组成的集合。 (7)Min( )，最小元运算：返回当前集合中依线性序最小的元素。 9.3 字典 679.3 字典 9.3.2 用数组实现字典 用数组实现字典与用数组实现符号表的不同之处： 可以利用线性序将字典中的元素从小到大依序存储在数组中，通过数组下标来反映有序字典元素之间的序关系。优点：可用二分法高效地实现与线性序有关的一些运算。如：Member(x) ，Predecessor(x)和 Successor(x)可在时间O(logn)内实现。缺点：插入和删除运算的效率较低。每执行一次Insert或Delete运算，需要移动部分数

31、组元素，从而导致它们在最坏情况下的计算时间为O(n)。考虑：能否用链表来实现字典？Member运算需要O(n)时间，一旦找到元素在链表中插入或删除的位置后，只要用O(1)时间就可完成插入或删除操作。 两种实现方式均不可取！689.3 字典 9.3.3 用二叉搜索树实现字典9.3.3.1 基本思想： 用二叉树来存储有序集，每一个结点存储一个元素。 满足：存储于每个结点中的元素x大于其左子树中任一结点中所存储的元素，小于其右子树中任一结点中所存储的元素。699.3 字典 9.3.3 用二叉搜索树实现字典9.3.3.2 二叉搜索树结点的定义及程序实现709.3 字典 9.3.3 用二叉搜索树实现字典

32、9.3.3.3 二叉搜索树的定义及运算的实现:71例 10， 18， 3， 8， 12， 2， 7， 41010181018310183810183812210183812710183812247101838122二叉搜索树的建立过程：72删除508060120110150557053删除6080551201101505370805012060110150557053删除43例80501206011015055705343运算Delete(const T& x)的实现73运算Delete(const T& x)的实现（续）设要删除二叉搜索树中的结点p ，分三种情况：p为叶结点 直接删除节点pp

33、只有左子树或右子树p只有左子树 用p的左儿子代替p p只有右子树 用p的右儿子代替p p左、右子树均非空找p的左子树的最大元素结点（即p的前驱结点），用该结点代替结点p，然后删除该结点。74用二叉搜索树实现字典时间复杂性分析 最坏情况分析member,insert,delete都需要O(n) 平均情况分析引入记号:记：p(n)为含有n个结点的二叉搜索树的平均查找长度。显然p(0)=0,p(1)=1; 若设某二叉搜索树的左子树有i个结点，则：p(i)+1为查找左子树中每个结点的平均查找长度;p(n-i-1)+1为查找右子树中每个结点的平均查找长度；由此构造而得的二叉搜索树在n个结点的查找概率相等

34、的情况下，其平均查找长度为：75对n用数学归纳法可以证明:又假设当前的二叉搜索树有n个结点，而它是从空树开始反复调用n次的Insert运算得到的，且被插入的n个元素的所有可能的顺序是等概率的。则：当n=1时显然成立。若设in时有 ，则76平均情况下的时间复杂度为：略去 -1/n 项77运算Predecessor(x)和Successor(x)的实现：类似于Search(x)算法运算Range(y, z)的实现：可借助于Search(y)和Successor(y)运算首先，用Search(y)检测y是否在二叉搜索树中，是则输出y，否则不输出y；然后，从y开始，不断地用Successor找当前元素

35、在二叉搜索树中的后继元素。当找出的后继元素x满足x z时，就输出x，并将x作为当前元素。重复这个过程，直到找出的当前元素的后继元素大于z，或二叉搜索树中已没有后继元素为止。时间复杂度：若二叉树搜索树中有r个元素x满足y x z，则在最坏情况下用 时间，在平均情况下用 时间可实现Range运算。 78运算Range(y,z)的改进：考虑半无限查询区域 , 即找出二叉搜索树中满足y x的所有元素x。 当y不在二叉搜索树中时，产生一条从根到叶的路径。如下图(a) 当y在二叉搜索树中时，产生一条从根到存储元素y的结点的路径。如下图(b) 79在找到的搜索路径上的所有结点可分为以下3种情况，如下图 ：8

36、0运算Range(y,z)的实现：可用类似于Range(y,)算法 从二叉搜索树的根结点开始，同时与y和z比较,此时,结点分类的情况可能有（见下图） ：81运算Range(y,z)的搜索路径如下图： 829.4 优先队列 9.4.0 优先队列的原型排队上车，老弱病残者优先上车排队候诊，危急病人优先就诊洗相馆为顾客洗照片，加钱加急者优先洗分时操作系统运行程序，小程序优先贪心算法对解分量的选择，按元素的某种特征值，大(或小)的优先在一个集合中搜索，按元素的某种特征值，大(或小)的优先处理或服务时只关心对象中谁的优先级最高通常的队列是一种优先队列最先到者优先级最高839.4 优先队列9.4.1 优先

37、队列的定义优先队列也是一个以集合为基础的抽象数据类型。优先队列中的每一个元素都有一个优先级值。优先队列中元素x的优先级值记为p(x)，它可以是一个实数，也可以是一个一般的全序集中的元素。优先级值用来表示该元素出列的优先级。通常约定优先级值小的优先级高。也可以约定优先级值大的优先级高。优先队列支持的基本运算有：(1)Size( )：返回优先队列中元素个数。(2)Min( )：返回优先队列中具有最小优先级值的元素。(3)Insert(x)：将元素x插入优先队列。(4)DeleteMin(x)：删除优先队列中具有最小优先级值的元素，并保存到x中。 849.4 优先队列9.4.2 用实现有序字典的方式

38、实现优先队列(1)优先队列与字典的相似性与区别：优先队列中元素的优先级值可以看作是有序字典中元素的线性序值。在有序字典中，不同的元素具有不同的线性序值，其插入运算仅当要插入元素x的线性序值与当前字典中所有元素的线性序值都不同时才执行。对于优先队列来说，不同的元素可以有相同的优先级值。因此，优先队列的插入运算即使在当前优先队列中存在与要插入元素x有相同的优先级值的元素时，也要执行元素x的插入。 859.4 优先队列9.4.2 用实现有序字典的方式实现优先队列(2)由于优先队列与字典的相似性,除了散列表之外,所有实现字典和有序字典的方法都可用于实现优先队列。 用有序链表实现优先队列;(Insert

39、低效) 用二叉搜索树实现优先队列;(Insert,DeleteMin, Min 均低效) 用AVL树实现优先队列;(逻辑复杂) 用无序链表实现优先队列;(DeleteMin, Min均低效) 都有缺点。原因在于没有考虑到优先队列的特性。869.4 优先队列9.4.3 用优先级树实现优先队列 1.优先队列的特征:DeleteMin和Min只关心优先级最高的元素Insert的元素不要求全局的序关系 因此实现优先队列的结构只要求方便DeleteMin 和Min,而对Insert也只要求不给结构的维护带来 太大的麻烦。 根据这两个特征,人们发明了优先级树。879.4 优先队列9.4.3 用优先级树实现

40、优先队列(续)2.优先级树的概念 优先级树是满足下面的优先级性质的二叉树： (1)树中每一结点存储一个元素。 (2)任一结点中存储的元素的优先级值不大(小)于 其儿子结点中存储的元素的优先级值即父结点的 优先级不低于其儿子结点的优先级。 换句话说，越接近根的结点中的元素的优先级越高，越方便被访问，因为根最方便被访问。 相应的优先级树称为极小(大)化优先级树。889.4 优先队列9.4.4用堆实现优先队列用优先级树实现优先队列仍有不足： Insert(x)和DeleteMin(x)后对结构的维护，在最坏情况下，仍需O(h)=O(n)。如果让优先级树近似满,从而h=log n,达到最小,那么，结果

41、将令人满意：在最坏情况下， Min( )将只需O(1), Insert(x)和DeleteMin(x)后对结构的维护只需O(log n)。因而引入堆的概念并用堆来实现优先队列。(1)堆的概念：如果一棵优先级树是一棵近似满二叉树，那么，这棵具有优先级性质的近似满二叉树(外形像堆)就叫做堆。(2)用堆实现优先队列： Min( )、Insert(x)和DeleteMin(x)运算的实现899.4 优先队列9.4.5 用数组表示堆从而实现优先队列(1) 用数组表示堆： 从1开始对堆的结点从根开始自上而下逐层、 每层从左到右进行编号，然后让结点中的元 素按编号在数组A中与下标对号入座。(2) 用数组表示

42、堆的优点： 存储紧凑，空间利用率高 父子关系简单清晰:存放在Ai的是结点i的元 素, A2i和A2i+1分别是结点i的左和右儿子 结点2i和2i+1的元素， Ai/2是结点i的父结 点的元素。909.4 优先队列9.4.5 用数组表示堆从而实现优先队列（续）(3)数组实现优先队列极小化堆MinHeap919.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.1 问题的提出 已知一个文本文件，要求把它转换成一个电子文档，以便存储在磁介质中或在网络上传输。从存储的角度看， 我们自然希望该电子文档越短越好即存储占用的空间越 少越好；从传输的角度看，我们自然也希望该电子文档 越短越好

43、即传输占用的时间越少越好。因此，我们要求 转换成的电子文档尽量地短，尽量地压缩。 有许多名家说过，把一个问题表述清楚了，就已经解决 了问题的一半。这说明问题的表述很重要，表述得越清 楚、越精确，对问题的解决越好。 上述问题还需要更精确的表述。929.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.2 表述Huffman编码问题的准备 对涉及的有关对象、概念、术语、和记号的准备 一个文本文件就是一个字符串，记为F。 文本文件中所用到的不同的字符组成的集合，记为C。 C中的字符c在文件中出现的频率/次数，记为f(c)或fc。 字符的编码0/1串。如字符a的ASCII码是0110

44、0001。 字符编码的码长0/1串的串长。记cC的码长为l(c)。 文件F编码的码长原文本文件编码后的0/1串的累计长。记为L(F)=cC f(c)* l(c) 。 字符的定长编码。 ASCII码是一种定长编码。不可能压缩。 字符的变长编码字符的码长随字符而变。 939.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.2 表述Huffman编码问题的的准备(续) 编码与解码既要编码又要解码，以便复原文件。 二义性:不能造成一串编码有两种理解。 前缀码：为了解码时不会出现二义性， 要求任意一个字符的编码不能是另一个 字符的前缀。 字符集C的前缀码的表示以C中的 字符为叶结点的

45、二叉树，如a0，b101，c100，d111，e1101，f1100 可表示成右图的二叉树。 这棵树叫字符集C的前缀编码树,记为T。acbfed0101010101949.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.3 Huffman编码问题的表述问题数学化。 经上述准备，我们看到，字符cC的码长l (c) 正是c在字符集C的前缀编码树T中的深度，记 为dT(c)。这样，我们的问题可更具体、更精 确地表述为：已知字符串F和出现在F中的字 符集C及C中每一字符c出现的频率/次数f(c) ， 要求C的一棵最优的前缀编码树T, 使得F的编 码长cC f(c)* dT(c) B

46、(T)达到最小。这棵 最优的前缀编码树叫Huffman编码树。相应的 前缀编码叫Huffman编码。959.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.4 求解问题的设想与分析 (1) 问题的目标是求C的最优前缀编码树T，因此，我们应 该先分析一下C的最优的前缀编码树T的性质:它是一棵以C中 的字符为叶结点的健全二叉树(这容易用反证法加以证明)。 因而一定有两个最深的叶结点是兄弟结点。 (2) 按照大数学家、大教育家波利亚的观点，“除数学和论 证逻辑外,我们所有的知识都是由一些猜想所构成的。” 为了 得到有用的结论、方法，总是从猜想开始。而猜想的依据是 合情推理。 就摆

47、在面前的问题而言，可直观地设想：最深的叶结点中 有两个兄弟是C中频 度最低的字符x和y ，因为编码最长的字 符应该是频度最低的字符(这需要证明)。969.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.4 求解问题的设想与分析(续) (3) 用字符z代替字符x和y ,让f(x)+f(y)作为字符z 的频度 f(z)，相应地，在T中删去兄弟叶结点x和y ，而且用z 取代已经成为叶结点的x和y的父结点，得到一棵新的健全二叉编码树T，那么，T应该是C-x,yz的最优前缀编码树(这需要证明) 。 若上述设想与分析正确，那么，问题就有了解法：把C中的字符以其频度为优先级值，且以小者优

48、先组织成优先队列Q。然后反复地执行下面两个语句： 删除Q中优先级最高的两个字符，设为x和y； 虚拟字符z(分别以x和y为左和右儿子)，并赋予优先 级值f(z)=f(x)+f(y),插入Q；直到Q为空，其结果就是C的最优前缀编码树。979.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.5 Huffman编码问题的解决 从理论上看待Huffman编码问题，在9.4.6.4 求 解问题的设想与分析中的(2)和(3)所猜想的分 别是问题的解的贪心选择性质和最优子结构性 质。这两个性质保证了问题可以用基于优先队 列的前述算法正确地加以求解。所以问题的真 正解决有待对贪心选择性质和最

49、优子结构性质 作理论上的证明。此外，还得给出Huffman编 码和解码的简洁实现。989.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.5 Huffman编码问题的解决(续) (1) 问题解的贪心选择性质：设x和y是C 中具有最小频度的两个字符，则存在C的 一个最优前缀码使x和y具有最长的相同码 长且仅最后一位编码不同，即x和y是编码 树中最深的一对叶结点兄弟。 证明：999.4 优先队列9.4.6 优先队列的应用Huffman编码9.4.6.5 Huffman编码问题的解决（续） (2) 问题解的最优子结构性质：设x和y是C的最优编码树T中的两个叶子且为兄弟，z是它们的父亲。若将z看作是具有频率f(z)=f