欢迎学习数据结构与算法分析第一章 数据结构和算法
大多数计算机程序的主要目标是存储信息和尽快地检索信息。因此，研究数据结构和算法就成了计算机科学的核心问题。本书的目的就是帮助读者理解怎样组织信息，以便支持高效的数据处理。
– 介绍常用的数据结构
– 引入并加强“权衡” (tradeoff)的概念，每一个数据结构都有其相关的代价和效益的权衡
– 评估一个数据结构或算法的有效性。
程序设计的目标
1．设计一种容易理解、编码和调试的算法。
2．设计一种能有效利用计算机资源的算法目标 1主要涉及到的是软件工程原理；
本书主要讲的是与目标 2有关的问题效 率 度 量
算法分析：
– 估算一种算法或者一个计算机程序的效率的方法
– 算法分析可以度量一个问题的内在复杂程度。
学习数据结构的必要性
一个数据结构就是一类数据的表示及其相关操作。
一个数据结构被认为是一组数据项的组织或者结构。
存储一组数据项，数据结构执行所有必需的运算：查找、打印或排序，或者更改数据项的值。选择不同的数据结构可能会产生很大的差异。
资源限制
资源限制包括空间和时间。
算法的代价 (cost)是指这种算法消耗的资源量。
选择数据结构的步骤：
– 1．分析问题，以确定任何算法均会遇到的资源限制。
– 2．确定必须支持的基本操作，并度量每种操作所受的资源限制。
– 3．选择最接近这些开销的数据结构。
选择数据结构需要考虑的问题
开始时是将所有数据项都插人数据结构，
还是与其他操作混合在一起插入。
数据项能否删除。
所有数据项是否按某一个已经定义好的顺序排列，是否允许查找特定的数据项。
代价与效益一家银行的简单交易情况：
顾客可以新开账户、注销账户以及从账户上存款和取款。
可以从两个层面上考虑这个问题：
(1)银行用来与顾客交互的物理基础结构和工作处理流程的需求，
(2)管理账户的数据库系统的需求。
抽象数据类型和数据结构
类型 (type)是一组值的集合。
数据项 (data item)是一条信息或者其值属于某种类型的一条记录，数据项又称数据类型的成员 (member)。
数据类型 (data type)是指一种类型和定义在该类型上的一组操作。
抽象数据类型和数据结构 (续 )
抽象数据类型 (ADT)是指数据结构作为一个软件组件的实现。
– ADT的接口用一种类型和该类型上的一组操作来定义，每个操作由它的输入和输出定义。
数据结构 (data structure)是 ADT的实现。
数据项、抽象数据类型和数据结构之间的关系
数据项有逻辑形式和物理形式两个方面。
– 用 ADT给出的数据项的定义是它的逻辑形式，
– 数据结构中对数据项的实现是它的物理形式。
比 ADT更高层的抽象是对描述程序设计
(即对象和类的相互关系 )的抽象。
数据类型
ADT:
类型
操作数据项：
逻辑形式数据项：
物理形式数据结构,
存储空间
子程序数据项、抽象数据类型和数据结构之间的关系图问题、算法和程序
问题：
– 是一个需要完成的任务，即一组输入就有一组相应的输出。
– 可以把问题看做函数。函数是输入和输出之间的一种映射关系。
算法
算法是指解决问题的一种方法或者一个过程。如果将问题看做函数，那么算法就是把输入转换为输出。
算法的性质：
– 1．正确性
– 2．具体步骤
– 3．确定性
– 4．有限性
– 5．可终止性
`
第二章 数学预备知识
集合和关系
对数
递归
级数求和与递归
数学证明方法
– 反证法
– 数学归纳法评估
粗略（快速）的评估：
称为“餐巾纸背面计算”或“信封背面计算”
– 确定影响问题的主要参数
– 推导出一个与问题的参数的有关的公式
– 选择参数值，由该公式得出一个评估解评估示例要存放 100万页书籍需要多少图书馆书架?
估算,
– 1英寸高的书由多少页
– 书架的宽度
– 书架的层数第三章 算法分析如何测算算法的效率?
1,程序实现来测量
2,渐近算法分析影响程序运行时间有很多因素,
由于影响运行时间的主要因素是输入的规模，
因此常将执行算法所需时间 T表示成 T(n)
算法的增长率是指当输入的值（规模）增长时，算法代价的增长速度增长率示例例 1.
// Find largest value
int largest(int array[],int n) {
int currlarge = 0; // Largest value seen
for (int i=1; i<n; i++) // For each val
若 (array[currlarge] < array[i])
currlarge = i; // Remember pos
return currlarge; // Return largest
}
示例 (续 )
例 2,赋值语句,
例 3:
sum = 0;
for (i=1; i<=n; i++)
for (j=1; j<n; j++)
sum++;
}
增长率图示最佳,最差和平均情况
有些算法即使问题规模相同，如果输入数据不同，时间代价也会不一样,
在一个 n元一维数组中顺序搜索给定的 K
最佳,
最差,
平均情况,
分析哪种情况好?
最佳情况很少考虑最差情况很重要平均情况通常会考虑，但有时有难度换计算机还是算法?
给定时间内，速度加快 10倍 的计算机处理问题规模的增长情况
T(n) n n’ 变化 n’/n
10n 1,000 10,000 n’ = 10n 10
20n 500 5,000 n’ = 10n 10
5n log n 250 1,842?10 n < n’ < 10n 7.37
2n2 70 223 n’ =?10n 3.16
2n 13 16 n’ = n + 3 -----
渐近分析：大 O
定义,
对于非负函数 T(n),若存在两个正常数 c和
n0,对任意 n > n0,有 T(n) <= cf(n)，称
T(n)在集合 O(f(n))中用法,
某算法的 [最佳,平均,最差 ] 情况在 O(n2) 中,
含义为,
对于问题的所有 [最佳,平均,最差 ] 输入，只要输入规模足够大 (n>n0),该算法总能在 cf(n)步内完成,
大 O (续 )
大 O表示法描述上限,
例,若 T(n) = 3n2 则 T(n) 在 O(n2)中,
最紧的上限,
虽然 T(n) = 3n2 在 O(n3)中,但我们多说在
O(n2)中,
大 O 示 例例 1,在数组中找值 X (平均情况 ).
T(n) = csn/2.
对于所有的 n > 1,csn/2 <= csn.
根据定义,T(n)在 O(n) 中,n0 = 1,c = cs.
大 O 示 例（续）
例 2,T(n) = c1n2 + c2n （平均情况）,
对于所有的 n > 1,
c1n2 + c2n <= c1n2 + c2n2 <= (c1 + c2)n2.
T(n) <= cn2,（ c = c1 + c2,n0 = 1）,
因此,T(n)在 O(n2) 中,
例 3,T(n) = c,此时说在 O(1)中,
通常的错误理解错误说法：
“我的算法的最佳情况是 n=1,因为这时算法运行时间最短,”
最佳情况是指对于所有的输入规模为 n的情况，
资源耗费（时间）最少的那种情况而大 O则是指 n趋向?时的增长率下限?
定义,
对于非负函数 T(n),若存在两个正常数 c
和 n0,对任意 n > n0,有 T(n) >= cf(n)，
称 T(n)在集合?(f(n))中对于问题的所有输入，只要输入规模足够大
(n>n0),该算法均多于 cf(n)步,
示例
T(n) = c1n2 + c2n.
对于所有的 n > 1,c1n2 + c2n >= c1n2
因此对于 c = c1 和 n0 = 1，有
T(n) >= cn2
根据定义,T(n)在?(n2)中同样，我们希望找出 最紧（最大的）的下限
表示法当上、下限相等时，可用?表示法定义,
如果一种算法既在 O(h(n))中，又在?(h(n))
中，则称其为?(h(n)).
一个错误理解混淆最差情况和上限的概念,
上限指的是增长率,
而最差情况是指给定规模时，在所有可能的输入情况中，最差的那种输入情况,
化简法则
1,若 f(n) 在 O(g(n))中，且 g(n) 在 O(h(n))中,
则 f(n) 在 O(h(n))中,
2,若 f(n) 在 O(kg(n))中，对于任意常数 k > 0
成立,则 f(n) 在 O(g(n))中,
3,若 f1(n) 在 O(g1(n))中，且 f2(n) 在 O(g2(n))
中,则 (f1 + f2)(n) 在 O(max(g1(n),g2(n)))中,
4,若 f1(n) 在 O(g1(n))中，且 f2(n) 在 O(g2(n))
中,则 f1(n)f2(n) 在 O(g1(n)g2(n))中,
程序运行时间示例 (1)
例 1,a = b;
执行时间为常量?(1).
例 2:
sum = 0;for (i=1; i<=n; i++)
sum += n;
程序段的代价为?(n).
程序运行时间示例 (2)
例 3:
sum = 0;for (i=1; i<=n; j++)
for (j=1; j<=i; i++)sum++;
for (k=0; k<n; k++)A[k] = k;
程序段的代价为?(n2).
程序运行时间示例 (3)
例 4:
sum1 = 0;for (i=1; i<=n; i++)
for (j=1; j<=n; j++)sum1++;
sum2 = 0;for (i=1; i<=n; i++)
for (j=1; j<=i; j++)sum2++;
程序段的代价为?(n2).
程序运行时间示例 (4)
例 5:
sum1 = 0;for (k=1; k<=n; k*=2)
for (j=1; j<=n; j++)sum1++;
程序段的代价为?(nlogn).
sum2 = 0;for (k=1; k<=n; k*=2)
for (j=1; j<=k; j++)sum2++;
程序段的代价为?(n).
二分法搜索求最差情况下的代价?
二分法搜索的程序
// Return position of element in sorted
// array of size n with value K,
int binary(int array[],int n,int K) {
int l = -1;
int r = n; // l,r are beyond array bounds
while (l+1 != r) { // Stop when l,r meet
int i = (l+r)/2; // Check middle
if (K < array[i]) r = i; // Left half
if (K == array[i]) return i; // Found it
if (K > array[i]) l = i; // Right half
}
return n; // Search value not in array
}
其他控制语句
while循环,与 for循环类似 l.
if 语句,最差情况下，取 then和
else语句 中时间较大的,
switch语句,最差情况时间代价是所有分支中开销最大的那一个,
问题的分析上限,
不超过已知最优解的上限,
下限,
所有可能的算法的下限,
问题分析示例例,排序
1,输入输出的代价,?(n).
2,冒泡和插入排序,O(n2).
3,好一点的排序 (快速排序,归并排序 ):
O(n log n).
4,第 7章证明排序算法的最差情况代价都在
(n log n)中,
多参数问题根据图像中各像素值出现频率对其排序
（ C 个像素值,P 个像素个数）
for (i=0; i<C; i++) // Initialize count
count[i] = 0;
for (i=0; i<P; i++) // Look at all pixels
count[value(i)]++; // Increment count
sort(count); // Sort pixel counts
算法的代价为?(P + C log C).
空间代价空间代价的分析技巧也可用渐近分析法空间代价针对数据结构而言时间代价针对算法而言空间 /时间权衡原则牺牲空间通常可以减少时间代价，反之亦然,
例 1：存储包含 32个布尔值集合例 2：查找表例 3：数组排序基本数据结构线性表、栈和队列二叉树树线性表线性表：
由数据项组成的一种有限且有序的序列,
表中每个元素都有自己的位置，也都有自己的数据类型表示方法,<a0,a1,…,an-1>
线性表的实现原则支持当前位置的概念,
假设线性表被一个“栅栏”分成左右两部分,
左、右均可以为空,
<20,23 | 12,15>
线性表的 ADT
template <class Elem> class List {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool append(const Elem&) = 0;
virtual bool remove(Elem&) = 0;
virtual void setStart() = 0;
virtual void setEnd() = 0;
virtual void prev() = 0;
virtual void next() = 0;
线性表的 ADT(续 )
virtual int leftLength() const = 0;
virtual int rightLength() const = 0;
virtual bool setPos(int pos) = 0;
virtual bool getValue(Elem&) const = 0;
virtual void print() const = 0;
};
线性表 ADT示例线性表,<12 | 32,15>
MyList.insert(99);
结果,<12 | 99,32,15>
遍历整个线性表,
for (MyList.setStart(); MyList.getValue(it);
MyList.next())
DoSomething(it);
线性表的查找函数
// Return true if K is in list
bool find(List<int>& L,int K)
{
int it;
for (L.setStart();L.getValue(it);L.next())
if (K == it) return true; // Found it
return false; // Not found
}
顺序表的插入线性表的实现：顺序表和链表顺序表 (1)
template <class Elem> // Array-based list
class AList,public List<Elem>
{
private:
int maxSize; // Maximum size of list
int listSize; // Actual elem count
int fence; // Position of fence
Elem* listArray; // Array holding list
public:
AList(int size=DefaultListSize)
{
maxSize = size;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
顺序表 (2)
~AList() { delete [] listArray; }
void clear()
{
delete [] listArray;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
void setStart() { fence = 0; }
void setEnd() { fence = listSize; }
void prev() { 若 (fence != 0) fence--; }
void next()
{ 若 (fence <= listSize)
fence++;
}
int leftLength() const { return fence; }
int rightLength() const
{ return listSize - fence; }
顺序表 (3)
bool setPos(int pos)
{
if ((pos >= 0) && (pos <= listSize))
fence = pos;
return (pos >= 0) && (pos <= listSize);
}
bool getValue(Elem& it) const
{
if (rightLength() == 0) return false;
else {
it = listArray[fence];
return true;
}
}
插入
// Insert at front of right partition
template <class Elem>
bool AList<Elem>::insert(const Elem& item)
{
if (listSize == maxSize) return false; for(int i=listSize; i>fence; i--)
// Shift Elems up to make room
listArray[i] = listArray[i-1]; listArray[fence] = item;
listSize++; // Increment list size
return true;
}
添加
// Append Elem to end of the list
template <class Elem>
bool AList<Elem>::append(const Elem& item)
{
if (listSize == maxSize) return false;
listArray[listSize++] = item;
return true;
}
删除顺序表右边第一个元素
// Remove and return first Elem in right
// partition
template <class Elem> bool AList<Elem>::remove(Elem& it)
{
if (rightLength() == 0) return false;
it = listArray[fence]; // Copy Elem
for(int i=fence; i<listSize-1; i++)
// Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return true;
}
链表
利用指针，按照需要动态地为表中新的元素分配存储空间,
–链表由一系列结点对象组成。
–结点的完整定义叫做 Link类，包括一个存储元素值的域和一个存储表中下一结点指针的 next域
–Link类的构造函数有两种形式，一个函数有初始化元素的值，而另一个没有链表实现 (1)
fence指针指向右边部分的第一个元素当链表为空，或者左边部分为空时，需要额外的处理来给 head,tail和 fence来指向链表实现 (2)
fence指针指向左边部分的最后一个元素当链表为空，或者左边部分为空时，可增加特殊的表头结点来解决链表实现 － class (1)
/ Linked list implementation
template <class Elem> class LList:
public List<Elem>
{
private:
Link<Elem>* head; // Point to list header
Link<Elem>* tail; // Pointer to last Elem Link<Elem>* fence;// Last element on left
int leftcnt; // Size of left
int rightcnt; // Size of right
void init()
{ // Intialization routine
fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
}
链表实现 － class(2)
void removeall()
{ // Return link nodes to free store
while(head != NULL)
{
fence = head;
head = head->next;
delete fence;
}
}
public:
LList(int size=DefaultListSize)
{ init(); }
~LList() { removeall(); } // Destructor
void clear() { removeall(); init(); }
链表实现 － class(3)
void setStart() {
fence = head; rightcnt += leftcnt;leftcnt = 0;
}void setEnd()
{ fence = tail; leftcnt += rightcnt;
rightcnt = 0; }
void next() { // Don't move fence if right empty
if (fence != tail) {
fence = fence->next; rightcnt--; leftcnt++;
}}
int leftLength() const { return leftcnt; }int rightLength() const { return rightcnt; }
bool getValue(Elem& it) const {
if(rightLength() == 0) return false;it = fence->next->element;
return true; }
}
插入插入 /添加
// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem& item)
{
fence->next =
new Link<Elem>(item,fence->next);
if (tail == fence) tail = fence->next; rightcnt++;
return true;
}
// Append Elem to end of the list
template <class Elem>
bool LList<Elem>::append(const Elem& item)
{
tail = tail->next =
new Link<Elem>(item,NULL);
rightcnt++;
return true;
}
删除删除
// Remove and return first Elem in right
// partition
template <class Elem> bool LList<Elem>::remove(Elem& it)
{
if (fence->next == NULL) return false;
it = fence->next->element; // Remember val
// Remember link node
Link<Elem>* ltemp = fence->next;
fence->next = ltemp->next; // Remove
if (tail == ltemp) // Reset tail
tail = fence;
delete ltemp; // Reclaim space
rightcnt--;
return true;
}
fence指针向表头移动一个位置
（ Prev 函数）
// Move fence one step left;
// no change if left is empty
template <class Elem> void
LList<Elem>::prev()
{
Link<Elem>* temp = head;
if (fence == head) return; // No prev Elem
while (temp->next!=fence)
temp=temp->next;
fence = temp;
leftcnt--;
rightcnt++;
}
fence指针指向第 i个位置
（ Setpos 函数）
// Set the size of left partition to pos
template <class Elem>
bool LList<Elem>::setPos(int pos) {
if ((pos < 0) || (pos > rightcnt+leftcnt))
return false;
fence = head;
for(int i=0; i<pos; i++)
fence = fence->next;
return true;
}
可利用空间表直接调用系统级的 new/delete 操作相对效率不高,
链表类增加自己管理的可利用空间表（ freelist），
取代反复调用的 new/delete 操作。
可利用空间表存放当前不用的线性表结点。链表上删除的结点放到可利用空间表的首端。新增元素到链表时，先检查可利用空间表是否有可用结点，若有，则可直接利用。只有当可利用空间表为空时，
才调用标准操作符 new
实现可利用空间表：
1。增加新的函数
2。用 C＋＋操作符重载替代 new和 delete。
Freelist（ 1）
// Singly-linked list node with freelist
template <class Elem> class Link {
private:
static Link<Elem>* freelist; // Head
public:
Elem element; // Value for this node
Link* next; // Point to next node Link(const Elem& elemval,
Link* nextval =NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval =NULL) {next=nextval;}
void* operator new(size_t); // Overload
void operator delete(void*); // Overload
};
Freelist (2)
template <class Elem>
Link<Elem>* Link<Elem>::freelist = NULL;
template <class Elem> // Overload for new
void* Link<Elem>::operator new(size_t)
{
if (freelist == NULL) return,:new Link;
Link<Elem>* temp = freelist; // Reuse
freelist = freelist->next;
return temp; // Return the link
}
template <class Elem> // Overload delete
void Link<Elem>::operator delete(void* ptr)
{
((Link<Elem>*)ptr)->next = freelist;
freelist = (Link<Elem>*)ptr;
}
线性表两种实现方式的比较顺序表,
插入和删除操作的效率是?(n).
向前和定位操作的效率是?(1).
数组的大小必须事先固定,
不能超越预定的长度,
链表,
插入和删除操作的效率是?(1).
向前和定位操作的效率是?(n).
链表中元素个数没有限制,
元素的存储需要额外的开销,
空间比较临界点 n（线性表中当前元素的个数）,
n = DE
P + E
DE = n(P + E);
E,数据元素的存储单元大小,
P,指针的存储单元大小,
D,数组中可存储元素的最大数目,
n超过临界值时，顺序表的空间效率更高线性表元素数目变化较大或未知时，最好用链表实现而事先知道线性表的大致长度，用顺序表的空间效率更高双链表简化插入和删除操作,增加指向前驱结点的指针,
// Doubly-linked list link node
template <class Elem> class Link {
public:
Elem element; // Value for this node
Link *next; // Pointer to next node
Link *prev; // Pointer to previous node
Link(const Elem& e,Link* prevp =NULL,
Link* nextp =NULL)
{ element=e; prev=prevp; next=nextp; }
Link(Link* prevp =NULL,Link* nextp =NULL)
{ prev = prevp; next = nextp; }
};
双链表示例双链表的插入双链表的插入程序
// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem& item) {
fence->next =
new Link<Elem>(item,fence,fence->next);
if (fence->next->next != NULL)
fence->next->next->prev = fence->next;
if (tail == fence) // Appending new Elem
tail = fence->next; // so set tail
rightcnt++; // Added to right
return true;
}
双链表的删除双链表的删除程序
// Remove,return first Elem in right part
template <class Elem>
bool LList<Elem>::remove(Elem& it) {
if (fence->next == NULL) return false;
it = fence->next->element;
Link<Elem>* ltemp = fence->next;
if (ltemp->next != NULL)
ltemp->next->prev = fence;
else tail = fence; // Reset tail
fence->next = ltemp->next; // Remove delete ltemp; // Reclaim space
rightcnt--; // Removed from right
return true;
}
字典提高数据的插入、删除和搜索操作的效率原则,
检索关键码,用一个关键码来描述所要查找的内容
关键码可比
– 是否相等,顺序搜索
– 全序,排序
记录可比定义用于比较的类如何实现比较?
用 ==,<=,>= 运算符
重载 ==,<=,>= 运算符
定义一个具有固定名称的函数
– 要求记录是某个类，该类继承一个抽象基本类
– 当记录具有多个检索关键码时行不通
策略设计模式
– 用户明确提供操作策略
– 函数通过参数实现
– 用户定义作为模板的参数比较示例
class intintCompare {
public:
static bool lt(int x,int y)
{ return x < y; }
static bool eq(int x,int y)
{ return x == y; }
static bool gt(int x,int y)
{ return x > y; }
};
比较示例 (2)
class PayRoll {
public:
int ID;
char* name;
};
class IDCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return x.ID < y.ID; }
};
class NameCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return strcmp(x.name,y.name) < 0; }
};
字典 ADT
// The Dictionary abstract class.
template <class Key,class Elem,
class KEComp,class EEComp>
class Dictionary {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool remove(const Key&,Elem&) = 0;
virtual bool removeAny(Elem&) = 0;
virtual bool find(const Key&,Elem&)
const = 0;
virtual int size() = 0;
};
无序表字典
template <class Key,class Elem,
class KEComp,class EEComp>
class UALdict,public
Dictionary<Key,Elem,KEComp,EEComp> {
private,AList<Elem>* list;
public:
bool remove(const Key& K,Elem& e) {
for(list->setStart(); list->getValue(e);
list->next())
if (KEComp::eq(K,e)) {
list->remove(e);
return true;
}
return false;
}
};
栈
LIFO,后进先出（ Last In,First Out）,
线性表的限制实现,
仅在线性表的顶端进行插入或删除操作,
符号定义,
插入,入栈 PUSH
删除,出栈 POP
称栈的可访问元素为栈顶元素 TOP.
栈 ADT
// Stack abtract class
template <class Elem> class Stack {
public:
// Reinitialize the stack
virtual void clear() = 0;
// Push an element onto the top of the stack.
virtual bool push(const Elem&) = 0;
// Remove the element at the top of the stack,
virtual bool pop(Elem&) = 0;
// Get a copy of the top element in the stack
virtual bool topValue(Elem&) const = 0;
// Return the number of elements in the stack.
virtual int length() const = 0;
};
顺序栈
// Array-based stack implementation
private:
int size; // Maximum size of stack
int top; // Index for top element
Elem *listArray; // Array holding elements
问题,
数组哪一端作为栈顶?
,top” 指向哪个位置?
操作的时间代价?
链式栈
// Linked stack implementation
private:
Link<Elem>* top; // Pointer to first elem
int size; // Count number of elems
操作的时间代价?
与顺序栈所需空间的比较?
递归实现
栈广泛应用于（递归）子程序调用
子程序调用通过将相关信息（活动记录）
存放在栈中实现
子程序调用：先将活动记录入栈，返回时，从栈中弹出一个活动记录
示例,递归阶乘函数实现队列
FIFO,先进先出（ First in,First Out）
也是线性表的限制实现,
在表的末端加入，从顶端进行删除操作,
符号定义,
插入,入队 Enqueue
删除,出队 Dequeue
第一个元素,Front
最后一个元素,Rear
队列实现 (1)
队列实现 (2)
队列实现方法
顺序队列
链式队列
– 成员函数都需要常数时间
– 空间比较与栈类似二叉树
二叉树由结点的有限集合组成，集合或者为空，或者由一个根结点以及两棵不相交的二叉树组成，两棵二叉树分别称为此根结点的左子树和右子树,
两棵子树的根称为此二叉树根结点的子结点。
从一个结点到其两个子结点都有边相连，
此结点称为其子结点的父结点二叉树示例称呼,结点,子结点,边,
父结点,祖先,子孙,
路径,深度,高度,层数,叶结点,内部结点
（分支结点）,子树,
满二叉树和完全二叉树满二叉树,
每个结点要么是叶结点，要么是带有两个非空子结点的分支结点,
完全二叉树,若树的高度为 d,则除了第 d － 1层外，
每一层都是满的,底层叶结点集中在左边的若干位置上,
满二叉树定理 (1)
定理 5。 1,
非空满二叉树的叶结点等于其分支结点数加 1.
证明 (数学归纳法 n个分支结点个数 ):
初始情况,
– 没有分支结点的非空满二叉树有一个叶结点
– 有一个分支结点的非空满二叉树有两个叶结点
– 即当 n＝ 0及 n＝ 1时定理成立
归纳假设,
– 假设任意一棵有 n－ 1个分支结点的满二叉树有 n个叶结点成立,
满二叉树定理 (2)
归纳步骤,
– 假设树 T 有 n 个分支结点
– 取一个左右子结点均为叶结点的分支结点 I,
– 去掉 I的两个子结点，则 I成为叶结点，把新树记为 T’.
– 满二叉树 T’ 有 n－ 1个分支结点，根据归纳假设,T’ 有
n 个叶结点,
– 将 T’ 还原到 T，则可知 T有 n个分支结点,n＋ 1个叶结点,
根据归纳原理，定理对任意 n≥0 成立满二叉树推论定理 5。 2,
一棵非空二叉树空子树的数目等于其结点数目加 1.
证明,将所有空子树换成叶结点,原树成为一棵满二叉树,
二叉树结点类 (1)
// Binary tree node class
template <class Elem>
class BinNodePtr,public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e,BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
二叉树结点类 (2)
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const
{ return lc; }
void setLeft(BinNode<Elem>* b)
{ lc = (BinNodePtr*)b; }
inline BinNode<Elem>* right() const
{ return rc; }
void setRight(BinNode<Elem>* b)
{ rc = (BinNodePtr*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); }
};
遍历 (1)
按照一定顺序访问二叉树的结点，称为一次 遍历对每一个结点进行一次访问并将其列出，
称为二叉树的 枚举,
遍历 (2)
前序遍历,
– 先访问结点后访问其子结点,
后序遍历,
– 先访问结点的子结点（包括子树），再访问该结点,
中序遍历,
– 先访问左子结点（包括整棵子树），然后访问该结点，最后访问右子结点（包括整棵子树）,
遍历 (3)
template <class Elem> // Good implementation
void preorder(BinNode<Elem>* subroot) {
if (subroot == NULL) return; // Empty
visit(subroot); // Perform some action
preorder(subroot->left());
preorder(subroot->right());
}
template <class Elem> // Bad implementation
void preorder2(BinNode<Elem>* subroot) {
visit(subroot); // Perform some action
if (subroot->left() != NULL)
preorder2(subroot->left());
if (subroot->right() != NULL)
preorder2(subroot->right());
}
遍历示例
// Return the number of nodes in the tree
template <class Elem>
int count(BinNode<Elem>* subroot) {
if (subroot == NULL)
return 0; // Nothing to count
return 1 + count(subroot->left())
+ count(subroot->right());
}
二叉树实现 (1)
二叉树实现 (2)
叶结点与分支结点采用不同的类定义：
区别方法：
采用联合结构类继承复合设计模式联合结构 (1)
enum Nodetype {leaf,internal};
class VarBinNode { // Generic node classpublic:
Nodetype mytype; // Store type for nodeunion {
struct { // nternal nodeVarBinNode* left; // Left child
VarBinNode* right; // Right childOperator opx; // Value
} intl;Operand var; // Leaf,Value only
};
联合结构 (2)
// Leaf constructorVarBinNode(const Operand& val)
{ mytype = leaf; var = val; }// Internal node constructor
VarBinNode(const Operator& op,VarBinNode* l,VarBinNode* r) {
mytype = internal; intl.opx = op;intl.left = l; intl.right = r;
}bool isLeaf() { return mytype == leaf; }
VarBinNode* leftchild(){ return intl.left; }
VarBinNode* rightchild(){ return intl.right; }
};
联合结构 (3)
// Preorder traversalvoid traverse(VarBinNode* subroot) {
if (subroot == NULL) return;if (subroot->isLeaf())
cout << "Leaf:,<< subroot->var << "\n";
else {cout << "Internal:,
<< subroot->intl.opx << "\n";traverse(subroot->leftchild());
traverse(subroot->rightchild());}
}
类继承 (1)
class VarBinNode { // Abstract base classpublic:
virtual bool isLeaf() = 0;};
class LeafNode,public VarBinNode { // Leafprivate:
Operand var; // Operand valuepublic:
LeafNode(const Operand& val){ var = val; } // Constructor
bool isLeaf() { return true; }Operand value() { return var; }
};
类继承 (2)
// Internal nodeclass IntlNode,public VarBinNode {
private:VarBinNode* left; // Left child
VarBinNode* right; // Right childOperator opx; // Operator value
public:IntlNode(const Operator& op,
VarBinNode* l,VarBinNode* r){ opx = op; left = l; right = r; }
bool isLeaf() { return false; }VarBinNode* leftchild() { return left; }
VarBinNode* rightchild() { return right; } Operator value() { return opx; }
};
类继承 (3)
// Preorder traversalvoid traverse(VarBinNode *subroot) {
if (subroot == NULL) return; // Emptyif (subroot->isLeaf()) // Do leaf node
cout << "Leaf,"<< ((LeafNode *)subroot)->value()
<< endl;else { // Do internal node
cout << "Internal,"<< ((IntlNode *)subroot)->value()
<< endl;traverse(
((IntlNode *)subroot)->leftchild());traverse(
((IntlNode *)subroot)->rightchild());}
}
复合 (1)
class VarBinNode { // Abstract base classpublic:
virtual bool isLeaf() = 0;virtual void trav() = 0;
};
class LeafNode,public VarBinNode { // Leaf private:
Operand var; // Operand valuepublic:
LeafNode(const Operand& val){ var = val; } // Constructor
bool isLeaf() { return true; }Operand value() { return var; }
void trav() { cout << "Leaf," << value()<< endl; }
};
复合 (2)
class IntlNode,public VarBinNode {private:
VarBinNode* lc; // Left childVarBinNode* rc; // Right child
Operator opx; // Operator valuepublic:
IntlNode(const Operator& op,VarBinNode* l,VarBinNode* r)
{ opx = op; lc = l; rc = r; }bool isLeaf() { return false; }
VarBinNode* left() { return lc; } VarBinNode* right() { return rc; }
Operator value() { return opx; }void trav() {
cout << "Internal," << value() << endl;if (left() != NULL) left()->trav();
if (right() != NULL) right()->trav();}
};
复合 (3)
// Preorder traversalvoid traverse(VarBinNode *root) {
if (root != NULL)root->trav();
}
空间代价 (1)
由满二叉树定理可知,
半数指针是空的,
如果只是叶结点存储数据，则结构性开销的比例取决于二叉树是否“满”,
例,若所有结点采用相同结构，且都有两个指针指向其子结点,
总的空间,(2p + d)n
结构性开销,2pn
如果 p = d,意味着总空间的 2p/(2p + d) = 2/3 被结构性开销占用,
空间代价 (2)
若去掉叶结点的指针，则结构性开销比例为,
n/2(2p) p
n/2(2p) + dn p + d
当 p = d时，比例为 1/2.
当满二叉树的分支结点不存放数据时，结构性开销的比例为 2p/(2p + d)? 2/3,
以上的比较都没有考虑当叶结点和分支结点需要进行区别的代价,
=
数组实现完全二叉树 (1)
Position 0 1 2 3 4 5 6 7 8 9 10 11
Parent -- 0 0 1 1 2 2 3 3 4 4 5
Left Child 1 3 5 7 9 11 -- -- -- -- -- --
Right Child 2 4 6 8 10 -- -- -- -- -- -- --
Left Sibling -- -- 1 -- 3 -- 5 -- 7 -- 9 --
Right Sibling -- 2 -- 4 -- 6 -- 8 -- 10 -- --
数组实现完全二叉树 (1)
Parent (r) =└(r-1)/2┘当 r>0时
Leftchild(r) =2r＋ 1,当 2r+1<n时
Rightchild(r) = 2r＋ 2,当 2r+2<n时
Leftsibling(r) = r -1,当 r为偶数并且 0≤r≤n-1时
Rightsibling(r) = r +1，当 r为奇数并且 r＋ 1<n时二叉查找树二叉查找树（ BST） 属性,
对于树中任意结点，设其值为 K，则该结点左子树中任意结点的值都小于 K,该结点右子树中任意结点的值都大于或等于 K。
二叉查找树 ADT(1)
// BST implementation for the Dictionary ADTtemplate <class Key,class Elem,
class KEComp,class EEComp>class BST,public Dictionary<Key,Elem,
KEComp,EEComp> {private:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes
void clearhelp(BinNode<Elem>*);BinNode<Elem>*
inserthelp(BinNode<Elem>*,const Elem&);BinNode<Elem>*
deletemin(BinNode<Elem>*,BinNode<Elem>*&);BinNode<Elem>* removehelp(BinNode<Elem>*,
const Key&,BinNode<Elem>*&);bool findhelp(BinNode<Elem>*,const Key&,
Elem&) const;void printhelp(BinNode<Elem>*,int) const;
二叉查找树 ADT(2)
public:BST() { root = NULL; nodecount = 0; }
~BST() { clearhelp(root); } void clear() { clearhelp(root); root = NULL;
nodecount = 0; }bool insert(const Elem& e) {
root = inserthelp(root,e);nodecount++;
return true; }bool remove(const Key& K,Elem& e) {
BinNode<Elem>* t = NULL;root = removehelp(root,K,t);
if (t == NULL) return false;e = t->val();
nodecount--;delete t;
return true; }
二叉查找树 ADT(3)
bool removeAny(Elem& e) { // Delete min valueif (root == NULL) return false; // Empty
BinNode<Elem>* t;root = deletemin(root,t);
e = t->val();delete t;
nodecount--;return true;
}bool find(const Key& K,Elem& e) const
{ return findhelp(root,K,e); }int size() { return nodecount; }
void print() const {if (root == NULL)
cout << "The BST is empty.\n";else printhelp(root,0);
}
二叉查找树的搜索
template <class Key,class Elem,
class KEComp,class EEComp>
bool BST<Key,Elem,KEComp,EEComp>::
findhelp(BinNode<Elem>* subroot,
const Key& K,Elem& e) const {
if (subroot == NULL) return false;
else if (KEComp::lt(K,subroot->val()))
return findhelp(subroot->left(),K,e);
else if (KEComp::gt(K,subroot->val()))
return findhelp(subroot->right(),K,e);
else { e = subroot->val(); return true; }
}
二叉查找树的插入 (1)
二叉查找树的插入 (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
inserthelp(BinNode<Elem>* subroot,
const Elem& val) {
if (subroot == NULL) // Empty,create node
return new BinNodePtr<Elem>(val,NULL,NULL);
if (EEComp::lt(val,subroot->val()))
subroot->setLeft(inserthelp(subroot->left(),
val));
else subroot->setRight(
inserthelp(subroot->right(),val));
// Return subtree with node inserted
return subroot;
}
删除最小值
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,
KEComp,EEComp>::
deletemin(BinNode<Elem>* subroot,
BinNode<Elem>*& min) {
if (subroot->left() == NULL) {
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(
deletemin(subroot->left(),min));
return subroot;
}
}
删除某个结点 (1)
删除某个结点 (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
removehelp(BinNode<Elem>* subroot,
const Key& K,BinNode<Elem>*& t) {
if (subroot == NULL) return NULL;
else if (KEComp::lt(K,subroot->val()))
subroot->setLeft(
removehelp(subroot->left(),K,t));
else if (KEComp::gt(K,subroot->val()))
subroot->setRight(
removehelp(subroot->right(),K,t));
删除某个结点 (3)
else { // Found it,remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL)
subroot = subroot->right();
else if (subroot->right() == NULL)
subroot = subroot->left();
else { // Both children are non-empty
subroot->setRight(
deletemin(subroot->right(),temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
} }
return subroot;
}
BST 操作的时间代价
Find:
Insert:
Delete:
堆与优先队列堆,具有堆属性的完全二叉树,
最小值堆,每个结点存储的值都小于或等于其子结点存储的值,
最大值堆,每个结点存储的值都大于或等于其子结点存储的值,
堆中数据的值是局部有序的,
堆的表示,往往用数组表示完全二叉树那样，
用数组来实现,
堆 ADT
template<class Elem,class Comp> class maxheap{private:
Elem* Heap; // Pointer to the heap arrayint size; // Maximum size of the heap
int n; // Number of elems now in heapvoid siftdown(int); // Put element in place
public:maxheap(Elem* h,int num,int max);
int heapsize() const;bool isLeaf(int pos) const;
int leftchild(int pos) const;int rightchild(int pos) const;
int parent(int pos) const;bool insert(const Elem&);
bool removemax(Elem&);bool remove(int,Elem&);
void buildHeap();};
建堆
(a) (4-2) (4-1) (2-1) (5-2) (5-4) (6-3) (6-5) (7-5) (7-6)
(b) (5-2),(7-3),(7-1),(6-1)
Siftdown操作 (1)
效率高的建堆操作,
从数组的较大序号结点向较小序号结点顺序访问,
对每个分支结点调用 siftdown.
叶结点不需要调用 siftdown.
template <class Elem,class Comp>void maxheap<Elem,Comp>::siftdown(int pos) {
while (!isLeaf(pos)) {int j = leftchild(pos);
int rc = rightchild(pos);if ((rc<n) && Comp::lt(Heap[j],Heap[rc]))
j = rc;if (!Comp::lt(Heap[pos],Heap[j])) return;
swap(Heap,pos,j);pos = j;
}}
Siftdown操作 (2)
建堆的代价调用 Siftdown 的代价之和,
log n
(i - 1) n/2i? n.
i=1
删除最大值
template <class Elem,class Comp>
bool maxheap<Elem,Comp>:,
removemax(Elem& it) {
if (n == 0) return false; // Heap is empty
swap(Heap,0,--n); // Swap max with end
if (n != 0) siftdown(0);
it = Heap[n]; // Return max value
return true;
}
优先队列 (1)
一些按照重要性或优先级来组织的对象称为优先队列,
例,在多任务操作系统的作业调度,
作业的优先级可能改变，也就要求将队列中的作业重新排序,
实现,使用堆来存储优先队列,
优先队列 (2)
为了支持优先级重新排序,删除和插入操作需要知道操作对象在队列中的索引位置,
template <class Elem,class Comp>
bool maxheap<Elem,Comp>::remove(int pos,
Elem& it) {
if ((pos < 0) || (pos >= n)) return false;
swap(Heap,pos,--n);
while ((pos != 0) && (Comp::gt(Heap[pos],
Heap[parent(pos)])))
swap(Heap,pos,parent(pos));
siftdown(pos);
it = Heap[n];
return true;
}
Huffman 编码树
ASCII 编码,每个字符占用一个字节 8bit.
固定长度编码,
– 如果每个字符的使用频率都相等，则空间效率最高,
变长编码
按照最小外部路径权重建立一棵树,
Z K F C U D L E
2 7 24 32 37 42 42 120
建立 Huffman 编码树 (1)
建立 Huffman 编码树 (2)
定理引理
一棵至少包含两个结点的 Huffman树，会把字母使用频率最小的两个字母作为兄弟结点存储，
其深度不比树中其它任何结点小
定理
对于一组给定的字母，函数 buildHuff实现了
“最小外部路径权重”
代码标记
Letter Freq Code Bits
C 32
D 42
E 120
F 24
K 7
L 42
U 37
Z 2
编码和解码如果一组代码中的任何一个代码都不是另一个代码的前缀，则称这组代码符合前缀特性,
为单词 DEED编码,
为数字串 1011001110111101解码,
代码长度比较,
通用树树结点的抽象数据结构
// General tree node ADTtemplate <class Elem> class GTNode {
public:GTNode(const Elem&); // Constructor
~GTNode(); // DestructorElem value(); // Return value
bool isLeaf(); // TRUE if is a leafGTNode* parent(); // Return parent
GTNode* leftmost_child(); // First childGTNode* right_sibling(); // Right sibling
void setValue(Elem&); // Set valuevoid insert_first(GTNode<Elem>* n);
void insert_next(GTNode<Elem>* n);void remove_first(); // Remove first child
void remove_next(); // Remove sibling};
通用树的遍历
template <class Elem>void GenTree<Elem>::
printhelp(GTNode<Elem>* subroot) {if (subroot->isLeaf()) cout << "Leaf,";
else cout << "Internal,";cout << subroot->value() << "\n";
for (GTNode<Elem>* temp =subroot->leftmost_child();
temp != NULL;temp = temp->right_sibling())
printhelp(temp);}
父指针实现等价类问题父指针表示法精确地保存了解答下面问题所需的信息,
– 给出两个结点，它们是否在同一棵树中?
// Return TRUE if nodes in different trees
bool Gentree::differ(int a,int b) {
int root1 = FIND(a); // Find root for a
int root2 = FIND(b); // Find root for b
return root1 != root2; // Compare roots
}
Union/Find
void Gentree::UNION(int a,int b) {int root1 = FIND(a); // Find root for a
int root2 = FIND(b); // Find root for bif (root1 != root2) array[root2] = root1;
}
int Gentree::FIND(int curr) const {while (array[curr]!=ROOT) curr = array[curr];
return curr; // At root}
为了使等价对的处理尽可能高效，要尽量降低树的高度,
重量权衡合并原则,树合并时，将结点较少的树的根结点指向结点较多树的根结点,
等价类处理 (1)
等价类处理 (2)
路径压缩
int Gentree::FIND(int curr) const {
if (array[curr] == ROOT) return curr;
return array[curr] = FIND(array[curr]);
}
子结点表左子结点 /右兄弟结点表示法 (1)
左子结点 /右兄弟结点表示法 (2)
动态结点表示法 (1)
动态结点表示法 (2)
森林转化为二叉树左子结点 /右兄弟结点表示法本质上是存储了一棵二叉树,
顺序树表示法 (1)
把结点值按照它们在先序遍历的顺序存储起来，同时保存描述树形状的充足信息,
节省空间,但对于结点的存取，都必须顺序查找所有在结点表中排在它前面的结点,
例,对于二叉树,用,/”表示空指针 null.
AB/D//CEG///FH//I//
顺序树表示法 (2)
例,将上例的树理解为满二叉树,对叶结点和分支结点分别标记,
A’B’/DC’E’G/F’HI
例,对于通用树，给每个子树的结束给出标记,
RAC)D)E))BF)))
内排序排序术语及记号：
所有排序算法的输入都是存储在数组中的一组记录
每个记录都包含一个关键码域,
– 线性次序,关键码比较,
代价的衡量,
– 关键码比较的次数
– 交换次数插入排序 (1)
插入排序 (2)
template <class Elem,class Comp>void inssort(Elem A[],int n) {
for (int i=1; i<n; i++)for (int j=i; (j>0) &&
(Comp::lt(A[j],A[j-1])); j--)swap(A,j,j-1);
}
最好情况,
最差情况,
平均情况,
起泡排序 (1)
起泡排序 (2)
template <class Elem,class Comp>void bubsort(Elem A[],int n) {
for (int i=0; i<n-1; i++)for (int j=n-1; j>i; j--)
if (Comp::lt(A[j],A[j-1]))swap(A,j,j-1);
}
最好情况,
最差情况,
平均情况,
选择排序 (1)
选择排序 (2)
template <class Elem,class Comp>void selsort(Elem A[],int n) {
for (int i=0; i<n-1; i++) {int lowindex = i; // Remember its index
for (int j=n-1; j>i; j--) // Find leastif (Comp::lt(A[j],A[lowindex]))
lowindex = j; // Put it in placeswap(A,i,lowindex);
}}
最好情况,
最差情况,
平均情况,
指针交换总结插入排序 起泡排序 选择排序比较次数,
最佳情况?(n)?(n2)?(n2)
平均情况?(n2)?(n2)?(n2)
最差情况?(n2)?(n2)?(n2)
交换次数：
最佳情况 0 0?(n)
平均情况?(n2)?(n2)?(n)
最差情况?(n2)?(n2)?(n)
交换排序
All of the sorts so far rely on exchanges of
adjacent records.
What is the average number of exchanges
required?
– There are n! permutations
– Consider permuation X and its reverse,X’
– Together,every pair requires n(n-1)/2
exchanges.
Shell排序
Shell排序
// Modified version of Insertion Sorttemplate <class Elem,class Comp>
void inssort2(Elem A[],int n,int incr) {for (int i=incr; i<n; i+=incr)
for (int j=i;(j>=incr) &&
(Comp::lt(A[j],A[j-incr])); j-=incr)swap(A,j,j-incr);
}
template <class Elem,class Comp>void shellsort(Elem A[],int n) { // Shellsort
for (int i=n/2; i>2; i/=2) // For each incrfor (int j=0; j<i; j++) // Sort sublists
inssort2<Elem,Comp>(&A[j],n-j,i);inssort2<Elem,Comp>(A,n,1);
}
快速排序
template <class Elem,class Comp>void qsort(Elem A[],int i,int j) {
if (j <= i) return; // List too smallint pivotindex = findpivot(A,i,j);
swap(A,pivotindex,j); // Put pivot at end// k will be first position on right side
int k = partition<Elem,Comp>(A,i-1,j,A[j]);
swap(A,k,j); // Put pivot in placeqsort<Elem,Comp>(A,i,k-1);
qsort<Elem,Comp>(A,k+1,j);}
template <class Elem>int findpivot(Elem A[],int i,int j)
{ return (i+j)/2; }
快速排序分割
template <class Elem,class Comp>int partition(Elem A[],int l,int r,
Elem& pivot) {do { // Move the bounds in until they meet
while (Comp::lt(A[++l],pivot));while ((r != 0) && Comp::gt(A[--r],
pivot));swap(A,l,r); // Swap out-of-place values
} while (l < r); // Stop when they crossswap(A,l,r); // Reverse last swap
return l; // Return first pos on right}
The cost for partition is?(n).
分割示例快速排序示例快速排序的代价最佳情况,每次轴值都将数组二等分,
最差情况,轴值的分割效果很差,
平均情况,
T(n) = n + 1 + 1/(n-1)?(T(k) + T(n-k))
快速排序的优化,
– 改进轴值的选择
– 当子序列小时，改进排序算法
– 减少递归
k=1
n-1
归并排序
List mergesort(List inlist) {
if (inlist.length() <= 1)return inlist;
List l1 = half of the items from inlist;
List l2 = other half of items from inlist;
return merge(mergesort(l1),
mergesort(l2));
}
归并排序实现
template <class Elem,class Comp>void mergesort(Elem A[],Elem temp[],
int left,int right) {int mid = (left+right)/2;
if (left == right) return; mergesort<Elem,Comp>(A,temp,left,mid);
mergesort<Elem,Comp>(A,temp,mid+1,right);for (int i=left; i<=right; i++) // Copy
temp[i] = A[i];int i1 = left; int i2 = mid + 1;
for (int curr=left; curr<=right; curr++) {if (i1 == mid+1) // Left exhausted
A[curr] = temp[i2++];else if (i2 > right) // Right exhausted
A[curr] = temp[i1++];else if (Comp::lt(temp[i1],temp[i2]))
A[curr] = temp[i1++];else A[curr] = temp[i2++];
}}
归并排序优化
template <class Elem,class Comp>void mergesort(Elem A[],Elem temp[],
int left,int right) {if ((right-left) <= THRESHOLD) {
inssort<Elem,Comp>(&A[left],right-left+1);return;
}int i,j,k,mid = (left+right)/2;
if (left == right) return;mergesort<Elem,Comp>(A,temp,left,mid);
mergesort<Elem,Comp>(A,temp,mid+1,right);for (i=mid; i>=left; i--) temp[i] = A[i];
for (j=1; j<=right-mid; j++)temp[right-j+1] = A[j+mid];
for (i=left,j=right,k=left; k<=right; k++)if (temp[i] < temp[j]) A[k] = temp[i++];
else A[k] = temp[j--];}
归并排序的代价归并排序的代价,
归并排序可以很好地处理单链表,
归并排序需要双倍 的空间,
堆排序
template <class Elem,class Comp>
void heapsort(Elem A[],int n) { // Heapsort
Elem mval;
maxheap<Elem,Comp> H(A,n,n);
for (int i=0; i<n; i++) // Now sort
H.removemax(mval); // Put max at end
}
基于最大值堆排序：首先构造堆，然后取出堆顶的最大元素，然后重排堆再取出堆顶最大值，重复下去，直到堆为空,
堆排序的时间代价,
找到数组中第 K大的元素,
堆排序示例 (1)
堆排序示例 (2)
分配排序 (1)
一个简单高效的排序,
for (i=0; i<n; i++)
B[A[i]] = A[i];
扩展方法,
– 允许关键码重复,使数组的每个元素称为一个链表的头结点
– 允许关键码范围大于 n.
分配排序 (2)
template <class Elem>
void binsort(Elem A[],int n) {
List<Elem> B[MaxKeyValue];
Elem item;
for (i=0; i<n; i++) B[A[i]].append(A[i]);
for (i=0; i<MaxKeyValue; i++)
for (B[i].setStart();
B[i].getValue(item); B[i].next())
output(item);
}
代价,
基数排序 (1)
基数排序 (2)
template <class Elem,class Comp>
void radix(Elem A[],Elem B[],
int n,int k,int r,int cnt[]) {
// cnt[i] stores # of records in bin[i]
int j;
for (int i=0,rtok=1; i<k; i++,rtok*=r) {
for (j=0; j<r; j++) cnt[j] = 0;
// Count # of records for each bin
for(j=0; j<n; j++) cnt[(A[j]/rtok)%r]++;
// cnt[j] will be last slot of bin j.
for (j=1; j<r; j++)
cnt[j] = cnt[j-1] + cnt[j];
for (j=n-1; j>=0; j--)\
B[--cnt[(A[j]/rtok)%r]] = A[j];
for (j=0; j<n; j++) A[j] = B[j];
}}
基数排序示例基数排序的代价代价,?(nk + rk)
如何看待 n,k,和 r 的关系?
如果关键码的取值范围较小,则代价只为?(n).
如果有 n 个不重复的关键码值,则至少需要 log n位来区别这 n 个不同的关键码值,
– 因此,基数排序在平均情况下的代价为?(n log n)
排序算法的实验比较 (1)
排序算法的实验比较 (2)
排序问题的下限我们想知道所有可能的排序算法的时间代价的下限,
排序问题的输入和输出需要?(n) 时间，就实际而知，排序的时间在?(n) 和 O(n log n)
之间将要证明：没有一种基于关键码比较的排序算法可以将最差执行时间降低到?(n log n)
以下,
插入排序的判定树下限证明
n个数据会有 n! 种排列,
一个排序算法可以看作决定哪一种排序作为输出,
判定树
判定树的每一个叶结点对应一种排列,
一棵具有 n 个结点的二叉树有?(log n) 层,
因此一棵具有 n! 个结点的二叉树有?(log
n!) =?(n log n) 层,
Primary vs,Secondary Storage
Primary storage,Main memory (RAM)
Secondary Storage,Peripheral devices
– Disk drives
– Tape drives
Comparisons
RAM is usually volatile.
RAM is about 1/4 million times faster than
disk.
Medium Early 1996 Mid 1997 Early 2000
RAM $45.00 7.00 1.50
Disk 0.25 0.10 0.01
Floppy 0.50 0.36 0.25
Tape 0.03 0.01 0.001
Golden Rule of File Processing
Minimize the number of disk accesses!
1,Arrange information so that you get what you want
with few disk accesses.
2,Arrange information to minimize future disk accesses.
An organization for data on disk is often called a
file structure.
Disk-based space/time tradeoff,Compress
information to save processing time by
reducing disk accesses.
Disk Drives
Sectors
A sector is the basic unit of I/O.
Interleaving factor,Physical distance
between logically adjacent sectors on a
track.
Terms
Locality of Reference,When record is read
from disk,next request is likely to come from
near the same place in the file.
Cluster,Smallest unit of file allocation,usually
several sectors.
Extent,A group of physically contiguous clusters.
Internal fragmentation,Wasted space within
sector if record size does not match sector size;
wasted space within cluster if file size is not a
multiple of cluster size.
Seek Time
Seek time,Time for I/O head to reach
desired track,Largely determined by
distance between I/O head and desired
track.
Track-to-track time,Minimum time to move
from one track to an adjacent track.
Average Seek time,Average time to reach a
track for random access.
Other Factors
Rotational Delay or Latency,Time for data
to rotate under I/O head.
– One half of a rotation on average.
– At 7200 rpm,this is 8.3/2 = 4.2ms.
Transfer time,Time for data to move under
the I/O head.
– At 7200 rpm,Number of sectors
read/Number of sectors per track * 8.3ms.
Disk Spec Example
16.8 GB disk on 10 platters = 1.68GB/platter
13,085 tracks/platter
256 sectors/track
512 bytes/sector
Track-to-track seek time,2.2 ms
Average seek time,9.5ms
4KB clusters,32 clusters/track.
Interleaving factor of 3.
5400RPM
Disk Access Cost Example (1)
Read a 1MB file divided into 2048 records of
512 bytes (1 sector) each.
Assume all records are on 8 contiguous
tracks.
First track,9.5 + 11.1/2 + 3 x 11.1 = 48.4 ms
Remaining 7 tracks,2.2 + 11.1/2 + 3 x 11.1
= 41.1 ms.
Total,48.4 + 7 * 41.1 = 335.7ms
Disk Access Cost Example (2)
Read a 1MB file divided into 2048 records of
512 bytes (1 sector) each.
Assume all file clusters are randomly spread
across the disk.
256 clusters,Cluster read time is
(3 x 8)/256 of a rotation for about 1 ms.
256(9.5 + 11.1/2 + (3 x 8)/256) is about
3877 ms,or nearly 4 seconds.
How Much to Read?
Read time for one track:
9.5 + 11.1/2 + 3 x 11.1 = 48.4ms.
Read time for one sector:
9.5 + 11.1/2 + (1/256)11.1 = 15.1ms.
Read time for one byte:
9.5 + 11.1/2 = 15.05 ms.
Nearly all disk drives read/write one sector
at every I/O access.
– Also referred to as a page.
Buffers
The information in a sector is stored in a
buffer or cache.
If the next I/O access is to the same buffer,
then no need to go to disk.
There are usually one or more input buffers
and one or more output buffers.
Buffer Pools
A series of buffers used by an application to
cache disk data is called a buffer pool.
Virtual memory uses a buffer pool to imitate
greater RAM memory by actually storing
information on disk and,swapping”
between disk and RAM.
Buffer Pools
Organizing Buffer Pools
Which buffer should be replaced when new
data must be read?
First-in,First-out,Use the first one on the
queue.
Least Frequently Used (LFU),Count buffer
accesses,reuse the least used.
Least Recently used (LRU),Keep buffers on
a linked list,When buffer is accessed,
bring it to front,Reuse the one at end.
Bufferpool ADT (1)
class BufferPool { // (1) Message Passingpublic:
virtual void insert(void* space,int sz,int pos) = 0;
virtual void getbytes(void* space,int sz,int pos) = 0;
};
class BufferPool { // (2) Buffer Passing
public:
virtual void* getblock(int block) = 0;
virtual void dirtyblock(int block) = 0;
virtual int blocksize() = 0;
};
Design Issues
Disadvantage of message passing:
– Messages are copied and passed back and forth,
Disadvantages of buffer passing:
– The user is given access to system memory (the
buffer itself)
– The user must explicitly tell the buffer pool when
buffer contents have been modified,so that modified
data can be rewritten to disk when the buffer is
flushed,
– The pointer might become stale when the bufferpool
replaces the contents of a buffer.
Programmer’s View of Files
Logical view of files:
– An a array of bytes.
– A file pointer marks the current position.
Three fundamental operations:
– Read bytes from current position (move file pointer)
– Write bytes to current position (move file pointer)
– Set file pointer to specified byte position.
C++ File Functions
#include <fstream.h>
void fstream::open(char* name,openmode mode);
– Example,ios::in | ios::binary
void fstream::close();
fstream::read(char* ptr,int numbytes);
fstream::write(char* ptr,int numbtyes);
fstream::seekg(int pos);
fstream::seekg(int pos,ios::curr);
fstream::seekp(int pos);
fstream::seekp(int pos,ios::end);
External Sorting
Problem,Sorting data sets too large to fit
into main memory.
– Assume data are stored on disk drive.
To sort,portions of the data must be brought
into main memory,processed,and
returned to disk.
An external sort should minimize disk
accesses.
Model of External Computation
Secondary memory is divided into equal-sized
blocks (512,1024,etc…)
A basic I/O operation transfers the contents of one
disk block to/from main memory.
Under certain circumstances,reading blocks of a
file in sequential order is more efficient,
(When?)
Primary goal is to minimize I/O operations.
Assume only one disk drive is available.
Key Sorting
Often,records are large,keys are small.
– Ex,Payroll entries keyed on ID number
Approach 1,Read in entire records,sort
them,then write them out again.
Approach 2,Read only the key values,store
with each key the location on disk of its
associated record.
After keys are sorted the records can be
read and rewritten in sorted order.
Simple External Mergesort (1)
Quicksort requires random access to the
entire set of records.
Better,Modified Mergesort algorithm.
– Process n elements in?(log n) passes.
A group of sorted records is called a run.
Simple External Mergesort (2)
Split the file into two files.
Read in a block from each file.
Take first record from each block,output them in
sorted order.
Take next record from each block,output them
to a second file in sorted order.
Repeat until finished,alternating between output
files,Read new input blocks as needed.
Repeat steps 2-5,except this time input files
have runs of two sorted records that are merged
together.
Each pass through the files provides larger runs.
Simple External Mergesort (3)
Problems with Simple Mergesort
Is each pass through input and output files
sequential?
What happens if all work is done on a single disk
drive?
How can we reduce the number of Mergesort
passes?
In general,external sorting consists of two phases:
– Break the files into initial runs
– Merge the runs together into a single run.
Breaking a File into Runs
General approach:
– Read as much of the file into memory as
possible.
– Perform an in-memory sort.
– Output this group of records as a single run.
Replacement Selection (1)
Break available memory into an array for
the heap,an input buffer,and an output
buffer.
Fill the array from disk.
Make a min-heap.
Send the smallest value (root) to the
output buffer.
Replacement Selection (2)
If the next key in the file is greater than
the last value output,then
– Replace the root with this key
else
– Replace the root with the last key in the
array
Add the next record in the file to a new heap
(actually,stick it at the end of the array).
RS Example
Snowplow Analogy (1)
Imagine a snowplow moving around a circular
track on which snow falls at a steady rate.
At any instant,there is a certain amount of
snow S on the track,Some falling snow
comes in front of the plow,some behind.
During the next revolution of the plow,all of
this is removed,plus 1/2 of what falls
during that revolution.
Thus,the plow removes 2S amount of snow.
Snowplow Analogy (2)
Problems with Simple Merge
Simple mergesort,Place runs into two files.
– Merge the first two runs to output file,then
next two runs,etc.
Repeat process until only one run remains.
– How many passes for r initial runs?
Is there benefit from sequential reading?
Is working memory well used?
Need a way to reduce the number of passes.
Multiway Merge (1)
With replacement selection,each initial run
is several blocks long.
Assume each run is placed in separate file.
Read the first block from each file into
memory and perform an r-way merge.
When a buffer becomes empty,read a block
from the appropriate run file.
Each record is read only once from disk
during the merge process.
Multiway Merge (2)
In practice,use only one file and seek to
appropriate block.
Limits to Multiway Merge (1)
Assume working memory is b blocks in size.
How many runs can be processed at one
time?
The runs are 2b blocks long (on average).
How big a file can be merged in one pass?
Limits to Multiway Merge (2)
Larger files will need more passes -- but the
run size grows quickly!
This approach trades (log b) (possibly)
sequential passes for a single or very
few random (block) access passes.
General Principles
A good external sorting algorithm will seek to do
the following:
– Make the initial runs as long as possible.
– At all stages,overlap input,processing and
output as much as possible.
– Use as much working memory as possible,
Applying more memory usually speeds
processing.
– If possible,use additional disk drives for
more overlapping of processing with I/O,
and allow for more sequential file processing.
检索假定,互不相同的关键码值 k1,k2,…,kn 和一个包含 n 条记录的集合 C，形式为：
(k1,I1),(k2,I2),…,( kn,In)
其中 Ij 是与关键码值 kj相关联的信息,1 <= j
<= n.
检索问题,对于给定的关键码值 K,在 C 中定位记录 (kj,Ij),使得 kj = K.
检索 就是定位关键码值 kj = K 的记录的系统化方法,
检索结果检索成功 就是找到至少一个关键码值为 kj的记录，使得 kj = K.
检索失败 就是找不到记录，使得 kj = K.
检索算法
1.顺序表和线性表方法,
2,根据关键码值直接访问方法 (散列法 )
3,树索引方法,
检索已排序的数组顺序检索二分查找插值检索（字典检索）
自组织线性表根据（估算的）访问频率排列记录,
–顺序检索预计的比较时间代价为：
..,,21 21 nn npppC
例 (1)
(1) 所有记录的访问频率相同,
2/)1(/
1
nniC
n
i
n
例 (2)
(2) 指数频率
ni
ni
p
n
i
i
if2/1
11if2/1
1
{
n
i
i
n iC
1
.2)2/(
Zipf 分布应用,
– 自然语言的单词使用频率,
– 城市中的人口规模,
80/20 规则,
– 80% 的访问都是对 20% 的记录进行的,
– 当频率遵循 80/20 规则,代价为
n
i
ennn nnniiC
1
.lo g/H/Η/
.1.0 nC n?
自组织线性表自组织线性表根据实际的记录访问模式在线性表中修改记录顺序,
自组织线性表使用 启发式规则 决定如何重新排列线性表,
启发式规则假设有 8条记录，关键码值为 A到 H，最初以字母顺序排列。
按照下面的访问模式：
F D F G E G F A D F G E
计数统计方法,保持线性表按照访问频率排序,(类似于缓冲池替代策略中的“最不频繁使用”法,)
结果,FGDEABCH
2,移至前端,找到一条记录就把它放到线性表的最前面,
结果,EGFDABCH
3,转置,把找到的记录与它在线性表中的前一条记录交换位置,
结果,ABFDGECH
文本压缩示例发送者和接收者都以同样的方式记录单词在线性表中的位置，线性表根据移至前端规则自组织,
如果单词没有出现过，就传送这个单词,
否则就传送这个单词在线性表当前的位置,
The car on the left hit the car I left.
The car on 3 left hit 3 5 I 5.
这种压缩方法的思想类似于 Ziv-Lempel 编码算法,
集合的检索对于密集集合 (关键码范围小，集合中元素的分布百分比高 ).
可以采用存储一个逻辑位数组进行操作,
例,寻找 0～ 15之间的奇素数,
0011010100010100 & 0101010101010101
散列方法 (1)
散列,把关键码值映射到检索表中的位置来访问记录,
散列函数把关键码值映射到检索表中的位置,
用 h 表示,
散列表就是存放记录的数组,用 HT 表示,
散列表 HT 有 M 个槽,槽从 0 到 M-1编号,
散列方法 (2)
设计散列函数的目标是：对于表中任意关键码值 K
和某个散列函数 h,h(K) = i,0 <= i < M,使得
(HT[i]) = K.
散列方法一般只适用于集合 (关键码不重复 ).
既适用于基于主存的检索，也适合于基于磁盘的检索,
适合于回答：“如果有的话，哪条记录的关键码值等于 K?”
简单的例子
(1) N条记录，每条记录具有唯一关键码值，范围从
0 到 n-1.
– 带有关键码 i 的记录存储在槽 HT[i]中,
– 散列函数 h(K) = K.
(2) 更为实际的例子,
– 存储约 1000条记录，关键码值范围在 0 到 65536.
– 使用带有 65536个槽的散列表是不切实际的,
– 必须设计一个散列函数，允许把记录存储在更小的表中,
冲突 (1)
给定,散列函数 h 和两个关键码值 k1 和 k2,? 是表中的一个槽,
如果 h(k1) =? = h(k2),则 k1 和 k2 对于? 在散列函数 h下有冲突,
在根据散列方法组织的数据库中，找到具有关键码值 K 的记录,
1,计算表的位置 h(K).
2,从槽 h(K)开始,使用冲突解决策略找到吧具有关键码值 K 的记录,
散列函数 (1)
一个散列函数的返回值必须在散列表范围内,
实际应用中,散列函数应该将记录均匀地分布到散列表的各个槽中,
希望选择的散列函数能把记录以相同的概率分布到散列表的所有槽中,在一般情况下,
散列函数的实现依赖于关键码值在可允许的关键码范围内的分布,
散列函数 (2)
如果对关键码值的分布不了解：
希望选择的 散列函数 在关键码范围内能产生一个大致平均的关键码值随机分布，同时避免明显的聚集可能性如果对关键码值的分布有所了解：
使用一个依赖于分布的散列函数，避免把一组相关的关键码值映射到散列表的同一个槽中,
示例 (1)
int h(int x)
{
return(x % 16);
}
散列函数的返回值只依赖于关键码的最低四位,
平方取中法,
计算关键码的平方，对于长度为 2r的表，取出中间的 r位,
示例 (2)
对于字符串,将字符串所有字母的 ASCII值累加起来，对 M取模,
int h(char* x) {
int i,sum;
for (sum=0,i=0; x[i] != '\0'; i++)
sum += (int) x[i];
return(sum % M);
}
当累加值比 M 大得多时，散列效果很好,
示例 (3)
ELF Hash,在 UNIX系统 V Release 4的 ELF
(Executable and Linking Format )文件格式用到,
int ELFhash(char* key) {
unsigned long h = 0;
while(*key) {
h = (h << 4) + *key++;
unsigned long g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h % M;
}
开散列方法冲突解决技术,开散列方法，闭散列方法开散列方法 把冲突记录存储在表外,
闭散列方法闭散列方法把所有的记录直接存储在散列表中,
每条记录 i 有一个基位置 h(ki).
如果另一条记录已经占用了 i的基位置,则根据冲突解决策略将它存到表中的其他槽内。
检索必须遵循同样的策略，以便重复进行冲突解决过程，找出基位置没有找到的记录,
桶式散列把散列表的槽分成多个桶,
– 例,有 7个数的桶式散列方法,
包含一个溢出桶,
记录被散列到某个桶的第一个槽，如果被占用，则顺序地沿着桶查找，直到找到一个空槽。如果桶中全被占满，则存往溢出桶,
检索时,首先散列关键码，在相应的桶中检索。如果未找到而桶是满的，还需查找溢出桶,
冲突解决插入期间,冲突解决策略的目的就是：当记录的基位置已被占用时在散列表中找到一个空槽,
探查序列,在插入 /检索时遵循某种冲突解决策略的对散列表中槽的访问序列,
插入
// Insert e into hash table HT
template <class Key,class Elem,
class KEComp,class EEComp>
bool hashdict<Key,Elem,KEComp,EEComp>::
hashInsert(const Elem& e) {
int home; // Home position for e
int pos = home = h(getkey(e)); // Init
for (int i=1;
!(EEComp::eq(EMPTY,HT[pos])); i++) {
pos = (home + p(getkey(e),I)) % M;
if (EEComp::eq(e,HT[pos]))
return false; // Duplicate
}
HT[pos] = e; // Insert e
return true;
}
检索
// Search for the record with Key Ktemplate <class Key,class Elem,
class KEComp,class EEComp>bool hashdict<Key,Elem,KEComp,EEComp>::
hashSearch(const Key& K,Elem& e) const {int home; // Home position for K
int pos = home = h(K); // Initial positfor (int i = 1; !KEComp::eq(K,HT[pos]) &&
!EEComp::eq(EMPTY,HT[pos]); i++)pos = (home + p(K,i)) % M; // Next
if (KEComp::eq(K,HT[pos])) { // Found ite = HT[pos];
return true;}
else return false; // K not in hash table}
探查函数注意语句中的探查函数 p().
pos = (home + p(getkey(e),i)) % M;
每次调用 p(),返回从基位置开始的偏移量，
从而检查此位置上的槽,
从散列表中检索记录和插入记录都根据 p()
采用相同的探查序列
– 并非所有的探查函数都采用相同的参数,
线性探查简单线性探查的探查函数为,
p(K,i) = i;
线性探查：如果记录的基位置被占用，则简单地在桶中下移，直到找到一个空槽,
– 如果探查过了底部，则换到顶部探查,
为了避免出现死循环，必须保证探查序列中至少有一个空槽,
线性探查示例基本聚集,
线性探查的把记录聚集到一起的倾向,
改进的线性探查线性探查时每次跳过常数 c个槽而非一个槽,
– 注意,慎重选择 M 和 c,
探查序列应该能走遍表中的所有槽,
– 常数 c 与 M互素,
仍然会有聚集可能
– 如,c=2,h(k1) = 3; h(k2) = 5.
– k1 和 k2 的探查序列链接到了一起,
伪随机探查 (1)
在探查序列中随机地从未走过的槽中选择下一个位置,
实际上不能随机地从探查序列中选择下一个位置,(为什么?)
伪随机探查 (2)
选择一个（随机的）排列，其值从 1到 M-
1:
r1,r2,…,rM-1
所有的插入和检索使用同样的排列数组,
例,散列表长度 M = 101
– r1=2,r2=5,r3=32.
– h(k1)=30,h(k2)=28.
– k1的探查序列,
– k2的探查序列,
二次探查令探查序列的第 i个值是
h(K,i) = i2;
例,M=101
– h(k1)=30,h(k2) = 29.
– k1的探查序列,
– k2的探查序列,
二级聚集伪随机探查和二次探查都能基本消除基本聚集,
如果两个关键码散列到同一个基位置，则它 们有相同的探查序列,这个问题称为 二级聚集,
为了避免二级聚集，需要使探查序列 是原始关键码值的函数，而不是基位置的函数,
双散列方法
p(K,i) = i * h2(K)
应保证所有探查序列常数 (h2(K))都与表长度 M互素,
– 选择 M 为一个素数
– 对于某个值 m，设 M=2m 返回一个 1到 2m之间的奇数值,
例,散列表长度 M = 101
– h(k1)=30,h(k2)=28,h(k3)=30.
– h2(k1)=2,h2(k2)=5,h2(k3)=5.
– k1的探查序列,
– k2的探查序列,
– k3的探查序列,
闭散列方法分析负载因子为 a = N/M,其中 N 是表中当前的记录个数,
删除删除记录一定不能影响后面的检索,
不希望让散列表中的位置由于记录删除而不可再用，释放的槽应该能为后来的插入所使用,
墓碑 (1)
上述两个问题可以通过在被删除记录的位置上设置一个特殊标记，该标记被称为 墓碑通过使用墓碑，检索仍能正常工作，并且能够重新使用已删除记录的槽,
墓碑 (2)
由于墓碑的存在，将增加记录本身到其基位置的平均长度,
解决方案,
1,删除时进行一次局部重组，试图缩小平均路径长度,
2,定期重新散列整个表,
Indexing
Goals:
– Store large files
– Support multiple search keys
– Support efficient insert,delete,and range
queries
Terms(1)
Entry sequenced file,Order records by time
of insertion.
– Search with sequential search
Index file,Organized,stores pointers to
actual records.
– Could be organized with a tree or other data
structure.
Terms(2)
Primary Key,A unique identifier for records,
May be inconvenient for search.
Secondary Key,An alternate search key,
often not unique for each record,Often
used for search key.
Linear Indexing
Linear index,Index file organized as a
simple sequence of key/record pointer
pairs with key values are in sorted order.
Linear indexing is good for searching
variable-length records.
Linear Indexing (2)
If the index is too large to fit in main memory,
a second-level index might be used.
Tree Indexing (1)
Linear index is poor for insertion/deletion.
Tree index can efficiently support all desired
operations:
– Insert/delete
– Multiple search keys (multiple indices)
– Key range search
Tree Indexing (2)
Difficulties when storing tree
index on disk:
– Tree must be balanced.
– Each path from root to leaf
should cover few disk pages.
2-3 Tree (1)
A 2-3 Tree has the following properties:
1,A node contains one or two keys
2,Every internal node has either two children
(if it contains one key) or three children (if it
contains two keys).
3,All leaves are at the same level in the tree,
so the tree is always height balanced.
The 2-3 Tree has a search tree property
analogous to the BST.
2-3 Tree (2)
The advantage of the 2-3 Tree over the BST
is that it can be updated at low cost.
2-3 Tree Insertion (1)
2-3 Tree Insertion (2)
2-3 Tree Insertion (3)
B-Trees (1)
The B-Tree is an extension of the 2-3 Tree.
The B-Tree is now the standard file
organization for applications requiring
insertion,deletion,and key range
searches.
B-Trees (2)
1,B-Trees are always balanced.
2,B-Trees keep similar-valued records
together on a disk page,which takes
advantage of locality of reference.
3,B-Trees guarantee that every node in the
tree will be full at least to a certain
minimum percentage,This improves
space efficiency while reducing the
typical number of disk fetches necessary
during a search or update operation.
B-Tree Definition
A B-Tree of order m has these properties:
– The root is either a leaf or has at least two children.
– Each node,except for the root and the leaves,has
between?m/2? and m children.
– All leaves are at the same level in the tree,so the
tree is always height balanced.
A B-Tree node is usually selected to match the
size of a disk block.
– A B-Tree node could have hundreds of children.
B-Tree Search (1)
Search in a B-Tree is a generalization of
search in a 2-3 Tree.
1,Do binary search on keys in current node,If
search key is found,then return record,If
current node is a leaf node and key is not
found,then report an unsuccessful search.
2,Otherwise,follow the proper branch and
repeat the process.
B+-Trees
The most commonly implemented form of the B-
Tree is the B+-Tree.
Internal nodes of the B+-Tree do not store record --
only key values to guild the search.
Leaf nodes store records or pointers to records.
A leaf node may store more or less records than
an internal node stores keys.
B+-Tree Example
B+-Tree Insertion
B+-Tree Deletion (1)
B+-Tree Deletion (2)
B+-Tree Deletion (3)
B-Tree Space Analysis (1)
B+-Trees nodes are always at least half full.
The B*-Tree splits two pages for three,and
combines three pages into two,In this
way,nodes are always 2/3 full.
Asymptotic cost of search,insertion,and
deletion of nodes from B-Trees is?(log n).
– Base of the log is the (average) branching
factor of the tree.
B-Tree Space Analysis (2)
Example,Consider a B+-Tree of order 100
with leaf nodes containing 100 records.
1 level B+-tree:
2 level B+-tree:
3 level B+-tree:
4 level B+-tree:
Ways to reduce the number of disk fetches:
– Keep the upper levels in memory.
– Manage B+-Tree pages with a buffer pool.
图的应用
– 为计算机与通信网络的互联建模
– 把一张地图表示为一组位置以及位置之间的距离，以求得位置之间的最短路径
– 为交通网络的流量建模
– 寻找从开始状态到目标状态的路径，如人工智能问题求解
– 为计算机算法建模，显示程序状态的变化
– 为复杂活动各子任务的完成寻找较优顺序，如大型建筑的建造
– 为家族、商业或军事组织和自然科学分类中的各种关系建模图
图可以用 G＝ (V,E)来表示，每个图都包括一个顶点集合 V和一个边集合 E，其中 E中的每条边都是 V中某一对顶点之间的连接，顶点总数记为 |V|，边的总数记为 |E|。边数较少的图称为稀疏图，边数较多的图称为密集图，包括所有可能边的图称为完全图。
图 (2)
(a)一个图； (b)一个有向图 ； ( c)一个有向标号图，其边上标有权。
( c)中从顶点 0到顶点 3存在一条包括顶点 0、顶点 1和顶点 3的简单路径。
顶点 0,1,3,2,4再到顶点 1也构成一条路径，但不是简路径，因为顶点 1出现了两次。顶点 1,3,2,4再到顶点 1构成了一条简单回路路径和回路
路径,
– 如果顶点序列 v1,v2,…,vn,从 vi到 vi+1(1 <= i < n)的边均存在，则称顶点序列 v1,v2,…,vn 构成一条长度为 n-1的路径 (path)。
简单路径,
– 如果路径上的各个顶点都不同，则称这个路径为简单路径。
路径长度,
– 是指路径包含的边数。
回路,
– 如果一条路径将某个顶点 (如 vi)连接到它本身，且其长度大于或等于 3，则称此路径为回路。
简单回路,
– 如果构成回路的路径是简单路径，除了首尾两个顶点相同以外其他顶点均不同，则称此回路为简单回路。
无环图,
– 不带回路的图称为无环图。不带回路的有向图则称为有向无环图。
自由树,
– 不带简单回路的连通无向图。同样还可以把一棵自由树定义为连通且有
|V|-1条边的图。
连通分量
子图,
– 子图 S是通过从图 G中选出其顶点集的一个子集 Vs，以及与 Vs中顶点相关联的一些边构成的子集 Es所形成的。
连通分量,
– 如果一个无向图中任意一个顶点到其他任意顶点都至少存在一条路径，则称此无向图为连通的。
– 无向图的最大连通子图称为连通分量
顶点 0,1,2,3和顶点 4构成一个连通分量。顶点 5和顶点 6构成第二个连通分量。顶点
7单独构成第三个连通分量图的表示图有两种常用的表示方法：
相邻矩阵表示法：
– 图的相邻矩阵是一个 |V|× |V|数组。假设 |V|=n，各顶点依次记为 v0,v1,…,vn-1，则相邻矩阵的第 i行包括所有以 vi 为起点的边。如果从 vi 到 vj 存在一条边，
则对第 i行的第 j个元素进行标记，否则不做标记。
邻接表表示法：
– 邻接表是一个以链表为元素的数组。该数组包含 |V|
个元素，其中第 i个元素存储的是一个指针，它指向顶点 vi的边构成的链表。这个链表存储由顶点 vi的邻接点。
有向图的表示无向图的表示表示法的代价相邻矩阵,
( |V|2 )
邻接表,
( |V|＋ |E| )
图的抽象数据类型
class Graph { // Graph abstract class
public:
virtual int n() =0; // # of vertices
virtual int e() =0; // # of edges
// Return index of first,next neighbor
virtual int first(int) =0;
virtual int next(int,int) =0;
// Store new edge
virtual void setEdge(int,int,int) =0;
// Delete edge defined by two vertices
virtual void delEdge(int,int) =0;
// Weight of edge connecting two vertices
virtual int weight(int,int) =0;
virtual int getMark(int) =0;
virtual void setMark(int,int) =0;
};
图的周游有的应用需要对图中每个结点恰好访问一次,
有的应用需要基于图的拓扑结构，以特定的顺序依次访问图中各个结点,
如,
– 人工智能领域的搜索问题
– 最短路径问题图的周游 (2)
为确保访问所有顶点必须避免,
– 在非连通图中，从起点出发可能到达不了所有其他顶点
– 因有些图存在回路而陷入死循环采取为图的每个顶点保留一个标志位的方法
void graphTraverse(const Graph* G) {
for (v=0; v<G->n(); v++)
G->setMark(v,UNVISITED); // Initialize
for (v=0; v<G->n(); v++)
if (G->getMark(v) == UNVISITED)
doTraverse(G,v);
}
深度优先搜索 (1)
// Depth first search
void DFS(Graph* G,int v) {
PreVisit(G,v); // Take action
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
DFS(G,w);
PostVisit(G,v); // Take action
}
深度优先搜索 (2)
Cost,?(|V| + |E|).
广度优先搜索 (1)
除了用队列代替递归栈外，广度优先搜索的 实现与深度优先搜索相似,
– 在进一步访问其它顶点前，检查起点的所有邻接点,
– 如果图是一个树结构，而且以树的根结点为起点，广度优先搜索将由顶层至底层逐层地对各个结点进行访问广度优先搜索 (2)
void BFS(Graph* G,int start,Queue<int>*Q) {
int v,w;
Q->enqueue(start); // Initialize Q
G->setMark(start,VISITED);
while (Q->length() != 0) { // Process Q
Q->dequeue(v);
PreVisit(G,v); // Take action
for(w=G->first(v);w<G->n();w=G->next(v,w))
if (G->getMark(w) == UNVISITED) {
G->setMark(w,VISITED);
Q->enqueue(w);
}
}
}
广度优先搜索 (3)
拓扑排序需要为一组任务安排进度（安排课程、建筑任务等），只有一项任务的先决条件任务被完成后才能开始这项任务。我们希望以某种线性顺序组织这些任务，以便在能满足先决条件的情况下逐个完成各项任务,
可以用一个有向无环图（ DAG）来为此问题建模。
将一个 DAG中所有顶点在不违反先决条件规定的基础上排成线性序列的过程称为 拓扑排序拓扑排序,AOV网在实际工作中，经常用有向图来表示工程的施工流程图或产品生产的流程图。一个工程一般可分为若干子工程，我们把子工程称为“活动”。在有向图中若以顶点表示“活动”，用有向边表示“活动”之间的优先关系，则这样的有向图称为以顶点表示“活动”的网 (Activity On Vertex
Network)，简称 AOV网。
AOV网中的弧表示了“活动”之间的优先关系，也可以说是一种制约关系。
教学活动的例子（ 1）
计算机专业学生必须学完一系列规定的课程后才能毕业。这可看作一个工程，图中所示的 AOV
网中的顶点表示各门课程的教学活动，有向边表示各门课程的制约关系。如图中有一条弧 <c3,c9>，
其中 c3和 c9分别表示“普通物理”和“计算机组成原理”的教学活动，这说明“普通物理”是“计算机组成原理”的直接前驱，“普通物理”教学活动一定要安排在“计算组成原理”教学活动之前。
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
教学活动的例子（ 2）
课程代号?课程名称 先行课程
c1 高等数学 无
c2 工程数学 c1
c3 普通物理 c1
c4 程序设计基础 无
c5 C语言程序设计 c1 c2 c4
c6 离散数学 c1
c7 数据结构 c4 c5 c6
c8 编译方法 c5 c7
c9 计算机组成原理 c3
c10 操作系统 c7 c9
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
教学活动的例子（ 3）
图中顶点 c1,c4是顶点 c5的直接前驱；顶点 c7是顶点 c4，
c5,c6的直接后继；顶点 c1是顶点 c9的前驱，但不是直接前驱。显然，在 AOV网中，由弧表示的优先关系有传递性，
如顶点 c1是 c3的前驱，而 c3是 c9的前驱，则 c1也是 c9的前驱。在 AOV网中不能出现有向回路，如果存在回路，则说明某个“活动”能否进行要以自身任务的完成作为先决条件，显然，这样的工程是无法完成的。如果要检测一个工程是否可行，首先就得检查对应的 AOV网是否存在回路。
检查 AOV网中是否存在回路的方法就是拓扑排序。
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
教学活动的例子（ 4）
某个 AOV网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各子工程可按拓扑有序序列的次序进行安排。一个 AOV网的拓扑有序序列并不是惟一的，例如，下面的两个序列都是图示 AOV网的拓扑有序序列。
– c1 c4 c3 c2 c5 c6 c9 c7 c8 c10
– c4 c1 c2 c3 c9 c6 c5 c7 c8 c10
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
拓扑排序 (2)
对 AOV网进行拓扑排序的步骤是,
– 在网中选择一个没有前驱的顶点且输出之。
– 在网中删去该顶点，并且删去从该顶点发出的全部有向边。
– 重复上述两步，直到网中不存在没有前驱的顶点为止。
这样操作结果有两种：一种是网中全部顶点均被输出，说明网中不存在有向回路；另一种是网中顶点未被全部输出，剩余的顶点均有前驱顶点，
说明网中存在有向回路。
拓扑排序的方法很多，主要有两种
– 深度优先搜索排序（基于递归、栈）
– 广度优先搜索排序（基于队列）
基于深度优先搜索的拓扑排序
void topsort(Graph* G) { // Topological sort
int i;
for (i=0; i<G->n(); i++) // Initialize
G->setMark(i,UNVISITED);
for (i=0; i<G->n(); i++) // Do vertices
if (G->getMark(i) == UNVISITED)
tophelp(G,i); // Call helper
}
void tophelp(Graph* G,int v) { // Process v
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
tophelp(G,w);
printout(v); // PostVisit for Vertex v
}
基于队列的拓扑排序
void topsort(Graph* G,Queue<int>* Q) {int Count[G->n()];
int v,w;for (v=0; v<G->n(); v++) Count[v] = 0;
for (v=0; v<G->n(); v++) // Process edgesfor (w=G->first(v); w<G->n();
w = G->next(v,w))Count[w]++; // Add to v2's count
for (v=0; v<G->n(); v++) // Initialize Qif (Count[v] == 0) // No prereqs
Q->enqueue(v);while (Q->length() != 0) {
Q->dequeue(v);printout(v); // PreVisit for V
for (w=G->first(v); w<G->n();w = G->next(v,w)) {
Count[w]--; // One less prereqif (Count[w] == 0) // Now free
Q->enqueue(w);}}}
拓扑排序 (3)
深度优先,J1,J3,J2,J6,J4,J5,J7
基于队列,J1,J2,J3,J6,J4,J5,J7
拓扑排序 (4)
求所有可能的拓扑有序序列
–深度优先：
–基于队列：
1
5
32
6
4
最短路径问题输入,在每条边上标记有数值（权或代价）的有向图,
输出,形成最短路径的边的序列,
问题示例,
– 找出给定两个顶点间的最短路径
– 找出给定顶点 S到其它所有顶点间的最短路径
– 找出所有顶点互相之间的最短路径计算路径长度,
最短路径的定义定义 d(A,B) 表示从顶点 A 到顶点 B的最短路径长度,
w(A,B) 为连接顶点 A 与 B的边的权,
– 如果顶点 A 与 B 之间没有边相连，则 w(A,B) =
.
最短路径问题的算法
单源最短路径,Dijstra算法
– 指的是对已知图 G=（ V,E），给定源顶点
s∈ V，找出 s到图中其它各顶点的最短路径。
每对顶点间的最短路径,Floyd算法
– 指的是对已知图 G=（ V,E），任意的顶点
Vi,Vj∈ V，找出从 Vi到 Vj的最短路径单源最短路径在图 G中给定顶点 s,找出 s到 G中其它所有顶点的最短路径,
方法 1,用固定的顺序对顶点进行处理,计算出当前所有顶点间的最短距离,然后将其加入到下一个顶点 x的最短路径值中,
可能的问题,已经处理的到某个顶点的最短路径可能经过顶点 x.
解决办法,从以 s 出发所到达点的距离（递增）为顺序，对各个顶点进行处理,
单源最短路径图例求上图中顶点 A到其它各顶点的最短路径
A
EC
B10
3
D
2
20
5
11
15
Dijstra算法基本思想
把图中所有顶点分成两组
– 第一组包括已确定最短路径的顶点
– 第二组包括尚未确定最短路径的顶点；
按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去
– 直至从 s出发可以到达的所有顶点都包括进第一组中。
在这个过程中，总保持从 s到第一组各顶点的最短路径长度都不大于从 s到第二组的任何顶点的最短路径长度，而且，每个顶点都对应一个距离值：
– 第一组的顶点对应的距离值就是从 s到该顶点的最短路径长度
– 第二组的顶点对应的距离值是从 s到该顶点的只包括第一组的顶点为中间顶点的最短路径长度
Dijkstra算法的具体做法
一开始第一组只包括顶点 s，第二组包括其它所有顶点；
s对应的距离值为 0，而第二组的顶点对应的距离值这样确定：
– 若图中有边 <s,Vi>或者（ s,Vi），则 Vi的距离值为此边所带的权，
否则 Vi的距离值为 ∞。
然后，每次从第二组的顶点中选一个其距离值为最小的顶点
Vm加入到第一组中；
每往第一组加入一个顶点 Vm，就要对第二组的各顶点的距离值进行一次修正：
– 若加进 Vm做中间顶点，使从 s到 Vi的最短路径比不加 Vm的为短，则需要修改 Vi的距离值。
修改后再选距离值最小的顶点加入到第一组中
……
如此进行下去，直到图的所有顶点都包括在第一组中或者再也没有可加入到第一组的顶点存在。
单源最短路径运算示意求上图中顶点 A到其它各顶点的最短路径
A
EC
B10
3
D
2
20
5
11
15
Dijkstra算法示例
A B C D E
初始状态 0
处理 A 0 10 3 20?
处理 C 0 5 3 20 18
处理 B 0 5 3 10 18
处理 D 0 5 3 10 18
处理 E 0 5 3 10 18
Dijkstra算法实现
// Compute shortest path distances from s,
// return them in D
void Dijkstra(Graph* G,int* D,int s) {
int i,v,w;
for (i=0; i<G->n(); i++) { // Do vertices
v = minVertex(G,D);
if (D[v] == INFINITY) return;
G->setMark(v,VISITED);
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > (D[v] + G->weight(v,w)))
D[w] = D[v] + G->weight(v,w);
}
}
minVertex实现问题,如何确定下一个最近的顶点? (即,如何实现 minVertex)
方法 1,搜索整个表中当前距离,
– 代价,?(|V|2 + |E|) =?(|V|2).
方法 2,将未被处理的顶点按照 D值大小的顺序保存在一个最小堆中,
– 代价,
((|V| + |E|)log|V|)
((|V| + |E|)log|E|)（最差情况下）
方法 1
// Find min cost vertex
int minVertex(Graph* G,int* D) {
int i,v;
// Set v to an unvisited vertex
for (i=0; i<G->n(); i++)
if (G->getMark(i) == UNVISITED)
{ v = i; break; }
// Now find smallest D value
for (i++; i<G->n(); i++)
if ((G->getMark(i) == UNVISITED)
&& (D[i] < D[v]))
v = i;
return v;
}
方法 2
void Dijkstra(Graph* G,int* D,int s) {
int i,v,w; // v is current vertexDijkElem temp;
DijkElem E[G->e()]; // Heap array temp.distance = 0; temp.vertex = s;
E[0] = temp; // Initialize heap arrayminheap<DijkElem,DDComp> H(E,1,G->e());
for (i=0; i<G->n(); i++) {// Get distances
do { if(!H.removemin(temp)) return;
v = temp.vertex;} while (G->getMark(v) == VISITED);
G->setMark(v,VISITED);if (D[v] == INFINITY) return;
for(w=G->first(v); w<G->n(); w=G->next(v,w))if (D[w] > (D[v] + G->weight(v,w)))
{D[w] = D[v] + G->weight(v,w);
temp.distance = D[w]; temp.vertex = w;H.insert(temp); // Insert in heap
}}
}
每对顶点之间的最短路径对于任意的顶点 u,v? V,计算 d(u,v)的值,
第一种方法可以使用 |V|次 Dijkstra算法,
第二种称为 Floyd算法，效率更高,
定义 k-path 是任意一条从 u 到 v 的、中间顶点序号都小于 k的路径,
Floyd算法思想（ 1）
假设用相邻矩阵 adj表示图
Floyd算法递推地产生一个矩阵序列 adj(0)，
adj(1),…,adj(k),…,adj(n)
adj(k)[i,j]等于从顶点 Vi到顶点 Vj中间顶点序号不大于 k的最短路径长度
Floyd算法思想（ 2）
假设已求得矩阵 adj(k-1)，那么从顶点 Vi到顶点 Vj中间顶点的序号不大于 k的最短路径有两种情况：
– 一种是中间不经过顶点 Vk，那么就有
adj(k)[i,j]=adj(k-1)[i,j]
– 另一种是中间经过顶点 Vk，那么
adj(k)[i,j]<adj(k-1)[i,j]
且 adj(k)[i,j]= adj(k-1)[i,k]+ adj(k-1)[k,j]
Floyd算法图示
Floyd算法
//Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
int D[G->n()][G->n()]; // Store distances
for (int i=0; i<G->n(); i++) // Initialize
for (int j=0; j<G->n(); j++)
D[i][j] = G->weight(i,j);
// Compute all k paths
for (int k=0; k<G->n(); k++)
for (int i=0; i<G->n(); i++)
for (int j=0; j<G->n(); j++)
if (D[i][j] > (D[i][k] + D[k][j]))
D[i][j] = D[i][k] + D[k][j];
}
最小支撑树最小支撑树 (MST) 问题,
输入,一个连通无向图 G.
输出,图 G的一个子图，满足
1) 子图中所有边的权之和是所有子图中最小的
2) 子图是连通的,
最小支撑树 MST举例
Prim算法实现
与 Dijkstra算法相似，主要区别在于不是寻找下一个离起点最近的顶点，而是下一个与 MST中某个顶点距离最近的顶点；
具体操作是：
– 从图中任意一个顶点开始，首先把这个顶点包括在 MST里，
– 然后在那些其一个端点已在 MST里，另一个端点还不是
MST里的边，找权最小的一条边，并把这条边和其不在
MST里的那个端点包括进 MST里。
– 如此进行下去，每次往 MST里加一个顶点和一条权最小的边，直到把所有的顶点都包括进 MST里。
与 Dijkstra算法相似，可以用优先队列来寻找下一个顶点
运行时间类似于相应的 Dijkstra算法,
最小支撑树的 Prim算法
void Prim(Graph* G,int* D,int s) {
int V[G->n()]; // Who's closest
int i,w;
for (i=0; i<G->n(); i++) {// Do vertices
int v = minVertex(G,D);
G->setMark(v,VISITED);
if (v != s) AddEdgetoMST(V[v],v);
if (D[v] == INFINITY) return;
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);// Update dist
V[w] = v; // Update who it came from
}
}
}
证明用 Prim算法构造的是 MST
首先证明这样一个结论（ MST性质）：
– 设 T(V*,E*)是连通无向图 G=(V,E)的一棵正在构造的生成树，又 E中有边 e=(Vx,Vy)，
其中 Vx∈ V*,Vy不属于 V*，且 e的权 W(e)是所有一个端点在 V*里，另一端不在 V*里的边的权中最小者，则一定存在 G的一棵包括 T的
MST包括边 e=( Vx,Vy)。
证明用 Prim算法构造的是 MST
反证法证明 MST性质
– 设 G的任何一棵包括 T的 MST都不包括 e=( Vx,Vy)，且设
T’是一棵这样的 MST
– 由于 T’是连通的，因此有从 Vx到 Vy的路径 Vx,…,Vy把边 e=( Vx,Vy)加进树 T’，得到一个回路 Vx,…,Vy,Vx
– 上述路径 Vx,…,Vy中必有边 e’=( Vp,Vq)，其中 Vp∈ V*，
Vq不属于 V*，由条件知边的权 W(e’)≥W(e)，从回路中去掉边 e’，回路打开，成为另一棵生成树 T”,T”包括边
e=( Vx,Vy)，且各边权的总和不大于 T’各边权的总和
– 因此 T”是一棵包括边 e的 MST，与假设矛盾，即证明了我们的结论。
– 也证明了 Prim算法构造 MST的方法是正确的，因为我们是从 T包括任意一个顶点和 0条边开始，每一步加进去的都是 MST中应包括的边，直至最后得到 MST。
Kruskal最小支撑树算法 (1)
初始化为 |V|个等价类,每个顶点自成一个等价类 MST.
合并具有最短的边相连的 MST.
– 通过使用最小值堆来实现按照权的顺序来处理每条边,
怎样确定两个顶点是否属于同一等价类?
– 使用基于父指针表示法的 UNION/FIND 算法,
Kruskal算法的基本思想
对于图 G=（ V,E），开始时，将顶点集分为 |V|个等价类，每个等价类包括一个顶点；
然后，以权的大小从小到大为顺序处理各条边，如果某条边连接两个不同等价类的顶点，
则这条边被添加到 MST，两个等价类被合并为一个；
反复执行此过程，直到只剩下一个等价类。
Kruskal最小支撑树算法 (2)
Kruskal最小支撑树算法 (3)
算法代价取决于按权处理每条边所需的时间确定,
– 当所有顶点都合并到一个等价类时可以结束处理总的代价,
– 使用了路径压缩,differ和 UNION函数几乎是常数
– 最差,?(|E| log |E|)
假设可能对几乎所有边都判断过了，则最坏情况下算法时间代价为 Θ（ |E|log |E|)，即堆排序的时间
– 平均,?(|V| log |E|)
通常情况下只找了接近顶点数目那么多边的情况下，
MST就已经生成，时间代价接近于 Θ（ |V|log |E|)
广义表 (1)
回顾线性表
– 由 n（ n≥0）个数据元素组成的有限有序序列
– 线性表的每个元素都具有相同的数据类型，
通常为同一某种类型的数据记录
如果一个线性表中还包括一个或者多个子表，那就称之为广义表（ Generalized
Lists，也称 Multi-list）一般记作：
– L＝（ x0,x1,…,xi,…,xn-1）
广义表 (2)
L＝（ x0,x1,…,xi,…,xn-1）
– L是广义表的名称
– n为长度
– 每个 xi（ 0≤i≤n-1）是 L的成员
可以是单个元素，即原子（也称“单元素”，
atom )
也可以是一个广义表，即子表（ sublist）
– 广义表的深度：表中元素都化解为原子后的括号层数广义表的各种类型（ 1）
纯表（ pure list）
– 从根结点到任何叶结点只有一条路径
– 也就是说任何一个元素（原子、子表）只能在广义表中出现一次广义表的各种类型（ 2）
可重入表 ( reentrant list )
– 图示对应于一个 DAG
– 其元素 (包括原子和子表 )可能会在表中多次出现
但不会出现回路
对子表和原子标号广义表的各种类型（ 3）
循环表 ( cyclic list,递归表 )的图示对应于任何有向图
– 有向图中可能包含回路
– 循环表的深度为无穷大广义表的各种类型（ 4）
广义表的 head和 tail
当广义表非空时：
– 称第一个元素为 表头
– 称其余元素组成的表为 表尾广义表的操作（ 1）
利用广义表的 head和 tail操作写出函数表达式，把以下各题中的单元素 banana从广义表中分离出来：
(1) L1(apple,pear,banana,orange)
Head (Tail (Tail (L1) ) )
(2) L2((apple,pear),(banana,orange))
Head (Head (Tail (L2) ) )
(3) L3(((apple),(pear),(banana),(orange)))
Head (Head (Tail (Tail (Head (L3) ) ) ) )
广义表的操作（ 2）
(4) L4((((apple))),((pear)),(banana),orange)
Head (Head (Tail (Tail (L4) ) ) )
(5) L5((((apple),pear),banana),orange)
Head (Tail (Head(L5) ) )
L6(apple,(pear,(banana),orange))
(6) Head (Head (Tail (Head (Tail (L6) ) ) ) )
平衡的二叉搜索树 (AVL)
BST受输入顺序影响
– 最好 O(log n)
– 最坏 O(n)
怎样使得 BST始终保持 O(log n)级的平衡状态？
Adelson-Velskii和 Landis发明了 AVL树
– 一种平衡的二叉搜索树
– 任何结点的左子树和右子树高度最多相差 1
AVL树的性质
可以为空
具有 n个结点的 AVL树，高度为 O(log n)
如果 T是一棵 AVL树
– 那么它的左右子树 TL,TR也是 AVL树
– 并且 | hL-hR|≤1
hL,hR 是它的左右子树的高度平衡因子
平衡因子，用 bf(x)来表示结点 x的平衡因子。它被定义为：
– bf(x)= x的右子树的高度 – x的左子树的高度
对于一个 AVL树中的结点平衡因子只可能取值为
0,1和 -1
AVL树结点的插入
插入与 BST一样
– 新结点作叶结点
需要调整
相应子树的根结点变化大致有三类
– 结点原来是平衡的，现在成为左重或右重的
修改相应前驱结点的平衡因子
– 结点原来是某一边重的，而现在成为平衡的了
树的高度未变，不修改
– 结点原来就是左重或右重的，而新结点又加到重的一边
不平衡
,危急结点”
恢复平衡不平衡的情况
正常情况下，一个结点 A的平衡因子只能是
0,1,-1，而在非正常情况有下面四种可能
– LL型：导致不平衡的结点为 A的左子树的左结点，这时 A的平衡因子为 -2
– LR型：导致不平衡的结点为 A的左子树的右结点，这时 A的平衡因子为 -2
– RL型：导致不平衡的结点为 A的右子树的左结点，这时 A的平衡因子为 2
– RR型：导致不平衡的结点为 A的右子树的右结点，这时 A的平衡因子为 2
不平衡的图示不平衡情况总结
LL型和 RR型是对称的,LR型和 RL型是对称的
不平衡的结点一定在根结点与新加入结点之间的路径上
它的平衡因子只能是 2或者 -2
– 如果是 2，它在插入前的平衡因子是 1
– 如果是 -2，它在插入前的平衡因子是 -1
解决不平衡的方法 ——旋转
我们可以使用一系列称为旋转 ( rotation )的局部操作解决这个问题
– LL和 RR的情况可以通过单旋转 ( single rotation )来解决
– RL和 LR的情况可以通过双旋转 ( double rotation )来解决
调整的整个过程称之为重构（ restructuring）
单旋转
如果加入一个新结点后需要对根为结点 a
的子树进行单旋转，假设 b为包含新加入结点的 a的子女,c为包含新加入结点的 b
的子女
单旋转，那么令 b代替 a成为新根,a和 c作为其子结点；原来 c的子树保持不变；原来 b中 c结点的兄弟子树，代替原 b子树作为 a的子树单旋转示意图（ LL型）
单旋转示意图（ RR型双旋转
RL或者 LR需要进行双旋转
– 这两种情况是对称的
我们只讨论 RL的情况
– LR是一样的
RL型双旋转第一步
RL型双旋转第二步旋转运算的实质（ 1）
以 RR型图示为例，总共有 7个部分
– 三个结点,a,b,c
– 四棵子树
a的左子树 T0
b的左子树 T1
c的左子树 T2 和右子树 T3
– 加重的是 c为根的子树，但是其结构其实没有变化
– 因此，可以整体地看作 b的右子树
目的：重新组成一个新的 AVL结构
– 平衡
– 保留了中序周游的性质
T0 a T1 b T2 c T3
旋转运算的实质（ 2）
把树做任何一种旋转（ RR,RL,LL、
LR）
– 新树保持了原来的中序周游顺序
– 旋转处理中仅需改变少数指针
– 而且新的子树高度为 h+2，保持插入前子树的高度不变
– 原来二叉树在 a结点上面的其余部分（若还有的话）总是保持平衡的
大多数计算机程序的主要目标是存储信息和尽快地检索信息。因此，研究数据结构和算法就成了计算机科学的核心问题。本书的目的就是帮助读者理解怎样组织信息，以便支持高效的数据处理。
– 介绍常用的数据结构
– 引入并加强“权衡” (tradeoff)的概念，每一个数据结构都有其相关的代价和效益的权衡
– 评估一个数据结构或算法的有效性。
程序设计的目标
1．设计一种容易理解、编码和调试的算法。
2．设计一种能有效利用计算机资源的算法目标 1主要涉及到的是软件工程原理；
本书主要讲的是与目标 2有关的问题效 率 度 量
算法分析：
– 估算一种算法或者一个计算机程序的效率的方法
– 算法分析可以度量一个问题的内在复杂程度。
学习数据结构的必要性
一个数据结构就是一类数据的表示及其相关操作。
一个数据结构被认为是一组数据项的组织或者结构。
存储一组数据项，数据结构执行所有必需的运算：查找、打印或排序，或者更改数据项的值。选择不同的数据结构可能会产生很大的差异。
资源限制
资源限制包括空间和时间。
算法的代价 (cost)是指这种算法消耗的资源量。
选择数据结构的步骤：
– 1．分析问题，以确定任何算法均会遇到的资源限制。
– 2．确定必须支持的基本操作，并度量每种操作所受的资源限制。
– 3．选择最接近这些开销的数据结构。
选择数据结构需要考虑的问题
开始时是将所有数据项都插人数据结构，
还是与其他操作混合在一起插入。
数据项能否删除。
所有数据项是否按某一个已经定义好的顺序排列，是否允许查找特定的数据项。
代价与效益一家银行的简单交易情况：
顾客可以新开账户、注销账户以及从账户上存款和取款。
可以从两个层面上考虑这个问题：
(1)银行用来与顾客交互的物理基础结构和工作处理流程的需求，
(2)管理账户的数据库系统的需求。
抽象数据类型和数据结构
类型 (type)是一组值的集合。
数据项 (data item)是一条信息或者其值属于某种类型的一条记录，数据项又称数据类型的成员 (member)。
数据类型 (data type)是指一种类型和定义在该类型上的一组操作。
抽象数据类型和数据结构 (续 )
抽象数据类型 (ADT)是指数据结构作为一个软件组件的实现。
– ADT的接口用一种类型和该类型上的一组操作来定义，每个操作由它的输入和输出定义。
数据结构 (data structure)是 ADT的实现。
数据项、抽象数据类型和数据结构之间的关系
数据项有逻辑形式和物理形式两个方面。
– 用 ADT给出的数据项的定义是它的逻辑形式，
– 数据结构中对数据项的实现是它的物理形式。
比 ADT更高层的抽象是对描述程序设计
(即对象和类的相互关系 )的抽象。
数据类型
ADT:
类型
操作数据项：
逻辑形式数据项：
物理形式数据结构,
存储空间
子程序数据项、抽象数据类型和数据结构之间的关系图问题、算法和程序
问题：
– 是一个需要完成的任务，即一组输入就有一组相应的输出。
– 可以把问题看做函数。函数是输入和输出之间的一种映射关系。
算法
算法是指解决问题的一种方法或者一个过程。如果将问题看做函数，那么算法就是把输入转换为输出。
算法的性质：
– 1．正确性
– 2．具体步骤
– 3．确定性
– 4．有限性
– 5．可终止性
`
第二章 数学预备知识
集合和关系
对数
递归
级数求和与递归
数学证明方法
– 反证法
– 数学归纳法评估
粗略（快速）的评估：
称为“餐巾纸背面计算”或“信封背面计算”
– 确定影响问题的主要参数
– 推导出一个与问题的参数的有关的公式
– 选择参数值，由该公式得出一个评估解评估示例要存放 100万页书籍需要多少图书馆书架?
估算,
– 1英寸高的书由多少页
– 书架的宽度
– 书架的层数第三章 算法分析如何测算算法的效率?
1,程序实现来测量
2,渐近算法分析影响程序运行时间有很多因素,
由于影响运行时间的主要因素是输入的规模，
因此常将执行算法所需时间 T表示成 T(n)
算法的增长率是指当输入的值（规模）增长时，算法代价的增长速度增长率示例例 1.
// Find largest value
int largest(int array[],int n) {
int currlarge = 0; // Largest value seen
for (int i=1; i<n; i++) // For each val
若 (array[currlarge] < array[i])
currlarge = i; // Remember pos
return currlarge; // Return largest
}
示例 (续 )
例 2,赋值语句,
例 3:
sum = 0;
for (i=1; i<=n; i++)
for (j=1; j<n; j++)
sum++;
}
增长率图示最佳,最差和平均情况
有些算法即使问题规模相同，如果输入数据不同，时间代价也会不一样,
在一个 n元一维数组中顺序搜索给定的 K
最佳,
最差,
平均情况,
分析哪种情况好?
最佳情况很少考虑最差情况很重要平均情况通常会考虑，但有时有难度换计算机还是算法?
给定时间内，速度加快 10倍 的计算机处理问题规模的增长情况
T(n) n n’ 变化 n’/n
10n 1,000 10,000 n’ = 10n 10
20n 500 5,000 n’ = 10n 10
5n log n 250 1,842?10 n < n’ < 10n 7.37
2n2 70 223 n’ =?10n 3.16
2n 13 16 n’ = n + 3 -----
渐近分析：大 O
定义,
对于非负函数 T(n),若存在两个正常数 c和
n0,对任意 n > n0,有 T(n) <= cf(n)，称
T(n)在集合 O(f(n))中用法,
某算法的 [最佳,平均,最差 ] 情况在 O(n2) 中,
含义为,
对于问题的所有 [最佳,平均,最差 ] 输入，只要输入规模足够大 (n>n0),该算法总能在 cf(n)步内完成,
大 O (续 )
大 O表示法描述上限,
例,若 T(n) = 3n2 则 T(n) 在 O(n2)中,
最紧的上限,
虽然 T(n) = 3n2 在 O(n3)中,但我们多说在
O(n2)中,
大 O 示 例例 1,在数组中找值 X (平均情况 ).
T(n) = csn/2.
对于所有的 n > 1,csn/2 <= csn.
根据定义,T(n)在 O(n) 中,n0 = 1,c = cs.
大 O 示 例（续）
例 2,T(n) = c1n2 + c2n （平均情况）,
对于所有的 n > 1,
c1n2 + c2n <= c1n2 + c2n2 <= (c1 + c2)n2.
T(n) <= cn2,（ c = c1 + c2,n0 = 1）,
因此,T(n)在 O(n2) 中,
例 3,T(n) = c,此时说在 O(1)中,
通常的错误理解错误说法：
“我的算法的最佳情况是 n=1,因为这时算法运行时间最短,”
最佳情况是指对于所有的输入规模为 n的情况，
资源耗费（时间）最少的那种情况而大 O则是指 n趋向?时的增长率下限?
定义,
对于非负函数 T(n),若存在两个正常数 c
和 n0,对任意 n > n0,有 T(n) >= cf(n)，
称 T(n)在集合?(f(n))中对于问题的所有输入，只要输入规模足够大
(n>n0),该算法均多于 cf(n)步,
示例
T(n) = c1n2 + c2n.
对于所有的 n > 1,c1n2 + c2n >= c1n2
因此对于 c = c1 和 n0 = 1，有
T(n) >= cn2
根据定义,T(n)在?(n2)中同样，我们希望找出 最紧（最大的）的下限
表示法当上、下限相等时，可用?表示法定义,
如果一种算法既在 O(h(n))中，又在?(h(n))
中，则称其为?(h(n)).
一个错误理解混淆最差情况和上限的概念,
上限指的是增长率,
而最差情况是指给定规模时，在所有可能的输入情况中，最差的那种输入情况,
化简法则
1,若 f(n) 在 O(g(n))中，且 g(n) 在 O(h(n))中,
则 f(n) 在 O(h(n))中,
2,若 f(n) 在 O(kg(n))中，对于任意常数 k > 0
成立,则 f(n) 在 O(g(n))中,
3,若 f1(n) 在 O(g1(n))中，且 f2(n) 在 O(g2(n))
中,则 (f1 + f2)(n) 在 O(max(g1(n),g2(n)))中,
4,若 f1(n) 在 O(g1(n))中，且 f2(n) 在 O(g2(n))
中,则 f1(n)f2(n) 在 O(g1(n)g2(n))中,
程序运行时间示例 (1)
例 1,a = b;
执行时间为常量?(1).
例 2:
sum = 0;for (i=1; i<=n; i++)
sum += n;
程序段的代价为?(n).
程序运行时间示例 (2)
例 3:
sum = 0;for (i=1; i<=n; j++)
for (j=1; j<=i; i++)sum++;
for (k=0; k<n; k++)A[k] = k;
程序段的代价为?(n2).
程序运行时间示例 (3)
例 4:
sum1 = 0;for (i=1; i<=n; i++)
for (j=1; j<=n; j++)sum1++;
sum2 = 0;for (i=1; i<=n; i++)
for (j=1; j<=i; j++)sum2++;
程序段的代价为?(n2).
程序运行时间示例 (4)
例 5:
sum1 = 0;for (k=1; k<=n; k*=2)
for (j=1; j<=n; j++)sum1++;
程序段的代价为?(nlogn).
sum2 = 0;for (k=1; k<=n; k*=2)
for (j=1; j<=k; j++)sum2++;
程序段的代价为?(n).
二分法搜索求最差情况下的代价?
二分法搜索的程序
// Return position of element in sorted
// array of size n with value K,
int binary(int array[],int n,int K) {
int l = -1;
int r = n; // l,r are beyond array bounds
while (l+1 != r) { // Stop when l,r meet
int i = (l+r)/2; // Check middle
if (K < array[i]) r = i; // Left half
if (K == array[i]) return i; // Found it
if (K > array[i]) l = i; // Right half
}
return n; // Search value not in array
}
其他控制语句
while循环,与 for循环类似 l.
if 语句,最差情况下，取 then和
else语句 中时间较大的,
switch语句,最差情况时间代价是所有分支中开销最大的那一个,
问题的分析上限,
不超过已知最优解的上限,
下限,
所有可能的算法的下限,
问题分析示例例,排序
1,输入输出的代价,?(n).
2,冒泡和插入排序,O(n2).
3,好一点的排序 (快速排序,归并排序 ):
O(n log n).
4,第 7章证明排序算法的最差情况代价都在
(n log n)中,
多参数问题根据图像中各像素值出现频率对其排序
（ C 个像素值,P 个像素个数）
for (i=0; i<C; i++) // Initialize count
count[i] = 0;
for (i=0; i<P; i++) // Look at all pixels
count[value(i)]++; // Increment count
sort(count); // Sort pixel counts
算法的代价为?(P + C log C).
空间代价空间代价的分析技巧也可用渐近分析法空间代价针对数据结构而言时间代价针对算法而言空间 /时间权衡原则牺牲空间通常可以减少时间代价，反之亦然,
例 1：存储包含 32个布尔值集合例 2：查找表例 3：数组排序基本数据结构线性表、栈和队列二叉树树线性表线性表：
由数据项组成的一种有限且有序的序列,
表中每个元素都有自己的位置，也都有自己的数据类型表示方法,<a0,a1,…,an-1>
线性表的实现原则支持当前位置的概念,
假设线性表被一个“栅栏”分成左右两部分,
左、右均可以为空,
<20,23 | 12,15>
线性表的 ADT
template <class Elem> class List {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool append(const Elem&) = 0;
virtual bool remove(Elem&) = 0;
virtual void setStart() = 0;
virtual void setEnd() = 0;
virtual void prev() = 0;
virtual void next() = 0;
线性表的 ADT(续 )
virtual int leftLength() const = 0;
virtual int rightLength() const = 0;
virtual bool setPos(int pos) = 0;
virtual bool getValue(Elem&) const = 0;
virtual void print() const = 0;
};
线性表 ADT示例线性表,<12 | 32,15>
MyList.insert(99);
结果,<12 | 99,32,15>
遍历整个线性表,
for (MyList.setStart(); MyList.getValue(it);
MyList.next())
DoSomething(it);
线性表的查找函数
// Return true if K is in list
bool find(List<int>& L,int K)
{
int it;
for (L.setStart();L.getValue(it);L.next())
if (K == it) return true; // Found it
return false; // Not found
}
顺序表的插入线性表的实现：顺序表和链表顺序表 (1)
template <class Elem> // Array-based list
class AList,public List<Elem>
{
private:
int maxSize; // Maximum size of list
int listSize; // Actual elem count
int fence; // Position of fence
Elem* listArray; // Array holding list
public:
AList(int size=DefaultListSize)
{
maxSize = size;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
顺序表 (2)
~AList() { delete [] listArray; }
void clear()
{
delete [] listArray;
listSize = fence = 0;
listArray = new Elem[maxSize];
}
void setStart() { fence = 0; }
void setEnd() { fence = listSize; }
void prev() { 若 (fence != 0) fence--; }
void next()
{ 若 (fence <= listSize)
fence++;
}
int leftLength() const { return fence; }
int rightLength() const
{ return listSize - fence; }
顺序表 (3)
bool setPos(int pos)
{
if ((pos >= 0) && (pos <= listSize))
fence = pos;
return (pos >= 0) && (pos <= listSize);
}
bool getValue(Elem& it) const
{
if (rightLength() == 0) return false;
else {
it = listArray[fence];
return true;
}
}
插入
// Insert at front of right partition
template <class Elem>
bool AList<Elem>::insert(const Elem& item)
{
if (listSize == maxSize) return false; for(int i=listSize; i>fence; i--)
// Shift Elems up to make room
listArray[i] = listArray[i-1]; listArray[fence] = item;
listSize++; // Increment list size
return true;
}
添加
// Append Elem to end of the list
template <class Elem>
bool AList<Elem>::append(const Elem& item)
{
if (listSize == maxSize) return false;
listArray[listSize++] = item;
return true;
}
删除顺序表右边第一个元素
// Remove and return first Elem in right
// partition
template <class Elem> bool AList<Elem>::remove(Elem& it)
{
if (rightLength() == 0) return false;
it = listArray[fence]; // Copy Elem
for(int i=fence; i<listSize-1; i++)
// Shift them down
listArray[i] = listArray[i+1];
listSize--; // Decrement size
return true;
}
链表
利用指针，按照需要动态地为表中新的元素分配存储空间,
–链表由一系列结点对象组成。
–结点的完整定义叫做 Link类，包括一个存储元素值的域和一个存储表中下一结点指针的 next域
–Link类的构造函数有两种形式，一个函数有初始化元素的值，而另一个没有链表实现 (1)
fence指针指向右边部分的第一个元素当链表为空，或者左边部分为空时，需要额外的处理来给 head,tail和 fence来指向链表实现 (2)
fence指针指向左边部分的最后一个元素当链表为空，或者左边部分为空时，可增加特殊的表头结点来解决链表实现 － class (1)
/ Linked list implementation
template <class Elem> class LList:
public List<Elem>
{
private:
Link<Elem>* head; // Point to list header
Link<Elem>* tail; // Pointer to last Elem Link<Elem>* fence;// Last element on left
int leftcnt; // Size of left
int rightcnt; // Size of right
void init()
{ // Intialization routine
fence = tail = head = new Link<Elem>;
leftcnt = rightcnt = 0;
}
链表实现 － class(2)
void removeall()
{ // Return link nodes to free store
while(head != NULL)
{
fence = head;
head = head->next;
delete fence;
}
}
public:
LList(int size=DefaultListSize)
{ init(); }
~LList() { removeall(); } // Destructor
void clear() { removeall(); init(); }
链表实现 － class(3)
void setStart() {
fence = head; rightcnt += leftcnt;leftcnt = 0;
}void setEnd()
{ fence = tail; leftcnt += rightcnt;
rightcnt = 0; }
void next() { // Don't move fence if right empty
if (fence != tail) {
fence = fence->next; rightcnt--; leftcnt++;
}}
int leftLength() const { return leftcnt; }int rightLength() const { return rightcnt; }
bool getValue(Elem& it) const {
if(rightLength() == 0) return false;it = fence->next->element;
return true; }
}
插入插入 /添加
// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem& item)
{
fence->next =
new Link<Elem>(item,fence->next);
if (tail == fence) tail = fence->next; rightcnt++;
return true;
}
// Append Elem to end of the list
template <class Elem>
bool LList<Elem>::append(const Elem& item)
{
tail = tail->next =
new Link<Elem>(item,NULL);
rightcnt++;
return true;
}
删除删除
// Remove and return first Elem in right
// partition
template <class Elem> bool LList<Elem>::remove(Elem& it)
{
if (fence->next == NULL) return false;
it = fence->next->element; // Remember val
// Remember link node
Link<Elem>* ltemp = fence->next;
fence->next = ltemp->next; // Remove
if (tail == ltemp) // Reset tail
tail = fence;
delete ltemp; // Reclaim space
rightcnt--;
return true;
}
fence指针向表头移动一个位置
（ Prev 函数）
// Move fence one step left;
// no change if left is empty
template <class Elem> void
LList<Elem>::prev()
{
Link<Elem>* temp = head;
if (fence == head) return; // No prev Elem
while (temp->next!=fence)
temp=temp->next;
fence = temp;
leftcnt--;
rightcnt++;
}
fence指针指向第 i个位置
（ Setpos 函数）
// Set the size of left partition to pos
template <class Elem>
bool LList<Elem>::setPos(int pos) {
if ((pos < 0) || (pos > rightcnt+leftcnt))
return false;
fence = head;
for(int i=0; i<pos; i++)
fence = fence->next;
return true;
}
可利用空间表直接调用系统级的 new/delete 操作相对效率不高,
链表类增加自己管理的可利用空间表（ freelist），
取代反复调用的 new/delete 操作。
可利用空间表存放当前不用的线性表结点。链表上删除的结点放到可利用空间表的首端。新增元素到链表时，先检查可利用空间表是否有可用结点，若有，则可直接利用。只有当可利用空间表为空时，
才调用标准操作符 new
实现可利用空间表：
1。增加新的函数
2。用 C＋＋操作符重载替代 new和 delete。
Freelist（ 1）
// Singly-linked list node with freelist
template <class Elem> class Link {
private:
static Link<Elem>* freelist; // Head
public:
Elem element; // Value for this node
Link* next; // Point to next node Link(const Elem& elemval,
Link* nextval =NULL)
{ element = elemval; next = nextval; }
Link(Link* nextval =NULL) {next=nextval;}
void* operator new(size_t); // Overload
void operator delete(void*); // Overload
};
Freelist (2)
template <class Elem>
Link<Elem>* Link<Elem>::freelist = NULL;
template <class Elem> // Overload for new
void* Link<Elem>::operator new(size_t)
{
if (freelist == NULL) return,:new Link;
Link<Elem>* temp = freelist; // Reuse
freelist = freelist->next;
return temp; // Return the link
}
template <class Elem> // Overload delete
void Link<Elem>::operator delete(void* ptr)
{
((Link<Elem>*)ptr)->next = freelist;
freelist = (Link<Elem>*)ptr;
}
线性表两种实现方式的比较顺序表,
插入和删除操作的效率是?(n).
向前和定位操作的效率是?(1).
数组的大小必须事先固定,
不能超越预定的长度,
链表,
插入和删除操作的效率是?(1).
向前和定位操作的效率是?(n).
链表中元素个数没有限制,
元素的存储需要额外的开销,
空间比较临界点 n（线性表中当前元素的个数）,
n = DE
P + E
DE = n(P + E);
E,数据元素的存储单元大小,
P,指针的存储单元大小,
D,数组中可存储元素的最大数目,
n超过临界值时，顺序表的空间效率更高线性表元素数目变化较大或未知时，最好用链表实现而事先知道线性表的大致长度，用顺序表的空间效率更高双链表简化插入和删除操作,增加指向前驱结点的指针,
// Doubly-linked list link node
template <class Elem> class Link {
public:
Elem element; // Value for this node
Link *next; // Pointer to next node
Link *prev; // Pointer to previous node
Link(const Elem& e,Link* prevp =NULL,
Link* nextp =NULL)
{ element=e; prev=prevp; next=nextp; }
Link(Link* prevp =NULL,Link* nextp =NULL)
{ prev = prevp; next = nextp; }
};
双链表示例双链表的插入双链表的插入程序
// Insert at front of right partition
template <class Elem>
bool LList<Elem>::insert(const Elem& item) {
fence->next =
new Link<Elem>(item,fence,fence->next);
if (fence->next->next != NULL)
fence->next->next->prev = fence->next;
if (tail == fence) // Appending new Elem
tail = fence->next; // so set tail
rightcnt++; // Added to right
return true;
}
双链表的删除双链表的删除程序
// Remove,return first Elem in right part
template <class Elem>
bool LList<Elem>::remove(Elem& it) {
if (fence->next == NULL) return false;
it = fence->next->element;
Link<Elem>* ltemp = fence->next;
if (ltemp->next != NULL)
ltemp->next->prev = fence;
else tail = fence; // Reset tail
fence->next = ltemp->next; // Remove delete ltemp; // Reclaim space
rightcnt--; // Removed from right
return true;
}
字典提高数据的插入、删除和搜索操作的效率原则,
检索关键码,用一个关键码来描述所要查找的内容
关键码可比
– 是否相等,顺序搜索
– 全序,排序
记录可比定义用于比较的类如何实现比较?
用 ==,<=,>= 运算符
重载 ==,<=,>= 运算符
定义一个具有固定名称的函数
– 要求记录是某个类，该类继承一个抽象基本类
– 当记录具有多个检索关键码时行不通
策略设计模式
– 用户明确提供操作策略
– 函数通过参数实现
– 用户定义作为模板的参数比较示例
class intintCompare {
public:
static bool lt(int x,int y)
{ return x < y; }
static bool eq(int x,int y)
{ return x == y; }
static bool gt(int x,int y)
{ return x > y; }
};
比较示例 (2)
class PayRoll {
public:
int ID;
char* name;
};
class IDCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return x.ID < y.ID; }
};
class NameCompare {
public:
static bool lt(Payroll& x,Payroll& y)
{ return strcmp(x.name,y.name) < 0; }
};
字典 ADT
// The Dictionary abstract class.
template <class Key,class Elem,
class KEComp,class EEComp>
class Dictionary {
public:
virtual void clear() = 0;
virtual bool insert(const Elem&) = 0;
virtual bool remove(const Key&,Elem&) = 0;
virtual bool removeAny(Elem&) = 0;
virtual bool find(const Key&,Elem&)
const = 0;
virtual int size() = 0;
};
无序表字典
template <class Key,class Elem,
class KEComp,class EEComp>
class UALdict,public
Dictionary<Key,Elem,KEComp,EEComp> {
private,AList<Elem>* list;
public:
bool remove(const Key& K,Elem& e) {
for(list->setStart(); list->getValue(e);
list->next())
if (KEComp::eq(K,e)) {
list->remove(e);
return true;
}
return false;
}
};
栈
LIFO,后进先出（ Last In,First Out）,
线性表的限制实现,
仅在线性表的顶端进行插入或删除操作,
符号定义,
插入,入栈 PUSH
删除,出栈 POP
称栈的可访问元素为栈顶元素 TOP.
栈 ADT
// Stack abtract class
template <class Elem> class Stack {
public:
// Reinitialize the stack
virtual void clear() = 0;
// Push an element onto the top of the stack.
virtual bool push(const Elem&) = 0;
// Remove the element at the top of the stack,
virtual bool pop(Elem&) = 0;
// Get a copy of the top element in the stack
virtual bool topValue(Elem&) const = 0;
// Return the number of elements in the stack.
virtual int length() const = 0;
};
顺序栈
// Array-based stack implementation
private:
int size; // Maximum size of stack
int top; // Index for top element
Elem *listArray; // Array holding elements
问题,
数组哪一端作为栈顶?
,top” 指向哪个位置?
操作的时间代价?
链式栈
// Linked stack implementation
private:
Link<Elem>* top; // Pointer to first elem
int size; // Count number of elems
操作的时间代价?
与顺序栈所需空间的比较?
递归实现
栈广泛应用于（递归）子程序调用
子程序调用通过将相关信息（活动记录）
存放在栈中实现
子程序调用：先将活动记录入栈，返回时，从栈中弹出一个活动记录
示例,递归阶乘函数实现队列
FIFO,先进先出（ First in,First Out）
也是线性表的限制实现,
在表的末端加入，从顶端进行删除操作,
符号定义,
插入,入队 Enqueue
删除,出队 Dequeue
第一个元素,Front
最后一个元素,Rear
队列实现 (1)
队列实现 (2)
队列实现方法
顺序队列
链式队列
– 成员函数都需要常数时间
– 空间比较与栈类似二叉树
二叉树由结点的有限集合组成，集合或者为空，或者由一个根结点以及两棵不相交的二叉树组成，两棵二叉树分别称为此根结点的左子树和右子树,
两棵子树的根称为此二叉树根结点的子结点。
从一个结点到其两个子结点都有边相连，
此结点称为其子结点的父结点二叉树示例称呼,结点,子结点,边,
父结点,祖先,子孙,
路径,深度,高度,层数,叶结点,内部结点
（分支结点）,子树,
满二叉树和完全二叉树满二叉树,
每个结点要么是叶结点，要么是带有两个非空子结点的分支结点,
完全二叉树,若树的高度为 d,则除了第 d － 1层外，
每一层都是满的,底层叶结点集中在左边的若干位置上,
满二叉树定理 (1)
定理 5。 1,
非空满二叉树的叶结点等于其分支结点数加 1.
证明 (数学归纳法 n个分支结点个数 ):
初始情况,
– 没有分支结点的非空满二叉树有一个叶结点
– 有一个分支结点的非空满二叉树有两个叶结点
– 即当 n＝ 0及 n＝ 1时定理成立
归纳假设,
– 假设任意一棵有 n－ 1个分支结点的满二叉树有 n个叶结点成立,
满二叉树定理 (2)
归纳步骤,
– 假设树 T 有 n 个分支结点
– 取一个左右子结点均为叶结点的分支结点 I,
– 去掉 I的两个子结点，则 I成为叶结点，把新树记为 T’.
– 满二叉树 T’ 有 n－ 1个分支结点，根据归纳假设,T’ 有
n 个叶结点,
– 将 T’ 还原到 T，则可知 T有 n个分支结点,n＋ 1个叶结点,
根据归纳原理，定理对任意 n≥0 成立满二叉树推论定理 5。 2,
一棵非空二叉树空子树的数目等于其结点数目加 1.
证明,将所有空子树换成叶结点,原树成为一棵满二叉树,
二叉树结点类 (1)
// Binary tree node class
template <class Elem>
class BinNodePtr,public BinNode<Elem> {
private:
Elem it; // The node's value
BinNodePtr* lc; // Pointer to left child
BinNodePtr* rc; // Pointer to right child
public:
BinNodePtr() { lc = rc = NULL; }
BinNodePtr(Elem e,BinNodePtr* l =NULL,
BinNodePtr* r =NULL)
{ it = e; lc = l; rc = r; }
二叉树结点类 (2)
Elem& val() { return it; }
void setVal(const Elem& e) { it = e; }
inline BinNode<Elem>* left() const
{ return lc; }
void setLeft(BinNode<Elem>* b)
{ lc = (BinNodePtr*)b; }
inline BinNode<Elem>* right() const
{ return rc; }
void setRight(BinNode<Elem>* b)
{ rc = (BinNodePtr*)b; }
bool isLeaf()
{ return (lc == NULL) && (rc == NULL); }
};
遍历 (1)
按照一定顺序访问二叉树的结点，称为一次 遍历对每一个结点进行一次访问并将其列出，
称为二叉树的 枚举,
遍历 (2)
前序遍历,
– 先访问结点后访问其子结点,
后序遍历,
– 先访问结点的子结点（包括子树），再访问该结点,
中序遍历,
– 先访问左子结点（包括整棵子树），然后访问该结点，最后访问右子结点（包括整棵子树）,
遍历 (3)
template <class Elem> // Good implementation
void preorder(BinNode<Elem>* subroot) {
if (subroot == NULL) return; // Empty
visit(subroot); // Perform some action
preorder(subroot->left());
preorder(subroot->right());
}
template <class Elem> // Bad implementation
void preorder2(BinNode<Elem>* subroot) {
visit(subroot); // Perform some action
if (subroot->left() != NULL)
preorder2(subroot->left());
if (subroot->right() != NULL)
preorder2(subroot->right());
}
遍历示例
// Return the number of nodes in the tree
template <class Elem>
int count(BinNode<Elem>* subroot) {
if (subroot == NULL)
return 0; // Nothing to count
return 1 + count(subroot->left())
+ count(subroot->right());
}
二叉树实现 (1)
二叉树实现 (2)
叶结点与分支结点采用不同的类定义：
区别方法：
采用联合结构类继承复合设计模式联合结构 (1)
enum Nodetype {leaf,internal};
class VarBinNode { // Generic node classpublic:
Nodetype mytype; // Store type for nodeunion {
struct { // nternal nodeVarBinNode* left; // Left child
VarBinNode* right; // Right childOperator opx; // Value
} intl;Operand var; // Leaf,Value only
};
联合结构 (2)
// Leaf constructorVarBinNode(const Operand& val)
{ mytype = leaf; var = val; }// Internal node constructor
VarBinNode(const Operator& op,VarBinNode* l,VarBinNode* r) {
mytype = internal; intl.opx = op;intl.left = l; intl.right = r;
}bool isLeaf() { return mytype == leaf; }
VarBinNode* leftchild(){ return intl.left; }
VarBinNode* rightchild(){ return intl.right; }
};
联合结构 (3)
// Preorder traversalvoid traverse(VarBinNode* subroot) {
if (subroot == NULL) return;if (subroot->isLeaf())
cout << "Leaf:,<< subroot->var << "\n";
else {cout << "Internal:,
<< subroot->intl.opx << "\n";traverse(subroot->leftchild());
traverse(subroot->rightchild());}
}
类继承 (1)
class VarBinNode { // Abstract base classpublic:
virtual bool isLeaf() = 0;};
class LeafNode,public VarBinNode { // Leafprivate:
Operand var; // Operand valuepublic:
LeafNode(const Operand& val){ var = val; } // Constructor
bool isLeaf() { return true; }Operand value() { return var; }
};
类继承 (2)
// Internal nodeclass IntlNode,public VarBinNode {
private:VarBinNode* left; // Left child
VarBinNode* right; // Right childOperator opx; // Operator value
public:IntlNode(const Operator& op,
VarBinNode* l,VarBinNode* r){ opx = op; left = l; right = r; }
bool isLeaf() { return false; }VarBinNode* leftchild() { return left; }
VarBinNode* rightchild() { return right; } Operator value() { return opx; }
};
类继承 (3)
// Preorder traversalvoid traverse(VarBinNode *subroot) {
if (subroot == NULL) return; // Emptyif (subroot->isLeaf()) // Do leaf node
cout << "Leaf,"<< ((LeafNode *)subroot)->value()
<< endl;else { // Do internal node
cout << "Internal,"<< ((IntlNode *)subroot)->value()
<< endl;traverse(
((IntlNode *)subroot)->leftchild());traverse(
((IntlNode *)subroot)->rightchild());}
}
复合 (1)
class VarBinNode { // Abstract base classpublic:
virtual bool isLeaf() = 0;virtual void trav() = 0;
};
class LeafNode,public VarBinNode { // Leaf private:
Operand var; // Operand valuepublic:
LeafNode(const Operand& val){ var = val; } // Constructor
bool isLeaf() { return true; }Operand value() { return var; }
void trav() { cout << "Leaf," << value()<< endl; }
};
复合 (2)
class IntlNode,public VarBinNode {private:
VarBinNode* lc; // Left childVarBinNode* rc; // Right child
Operator opx; // Operator valuepublic:
IntlNode(const Operator& op,VarBinNode* l,VarBinNode* r)
{ opx = op; lc = l; rc = r; }bool isLeaf() { return false; }
VarBinNode* left() { return lc; } VarBinNode* right() { return rc; }
Operator value() { return opx; }void trav() {
cout << "Internal," << value() << endl;if (left() != NULL) left()->trav();
if (right() != NULL) right()->trav();}
};
复合 (3)
// Preorder traversalvoid traverse(VarBinNode *root) {
if (root != NULL)root->trav();
}
空间代价 (1)
由满二叉树定理可知,
半数指针是空的,
如果只是叶结点存储数据，则结构性开销的比例取决于二叉树是否“满”,
例,若所有结点采用相同结构，且都有两个指针指向其子结点,
总的空间,(2p + d)n
结构性开销,2pn
如果 p = d,意味着总空间的 2p/(2p + d) = 2/3 被结构性开销占用,
空间代价 (2)
若去掉叶结点的指针，则结构性开销比例为,
n/2(2p) p
n/2(2p) + dn p + d
当 p = d时，比例为 1/2.
当满二叉树的分支结点不存放数据时，结构性开销的比例为 2p/(2p + d)? 2/3,
以上的比较都没有考虑当叶结点和分支结点需要进行区别的代价,
=
数组实现完全二叉树 (1)
Position 0 1 2 3 4 5 6 7 8 9 10 11
Parent -- 0 0 1 1 2 2 3 3 4 4 5
Left Child 1 3 5 7 9 11 -- -- -- -- -- --
Right Child 2 4 6 8 10 -- -- -- -- -- -- --
Left Sibling -- -- 1 -- 3 -- 5 -- 7 -- 9 --
Right Sibling -- 2 -- 4 -- 6 -- 8 -- 10 -- --
数组实现完全二叉树 (1)
Parent (r) =└(r-1)/2┘当 r>0时
Leftchild(r) =2r＋ 1,当 2r+1<n时
Rightchild(r) = 2r＋ 2,当 2r+2<n时
Leftsibling(r) = r -1,当 r为偶数并且 0≤r≤n-1时
Rightsibling(r) = r +1，当 r为奇数并且 r＋ 1<n时二叉查找树二叉查找树（ BST） 属性,
对于树中任意结点，设其值为 K，则该结点左子树中任意结点的值都小于 K,该结点右子树中任意结点的值都大于或等于 K。
二叉查找树 ADT(1)
// BST implementation for the Dictionary ADTtemplate <class Key,class Elem,
class KEComp,class EEComp>class BST,public Dictionary<Key,Elem,
KEComp,EEComp> {private:
BinNode<Elem>* root; // Root of the BST
int nodecount; // Number of nodes
void clearhelp(BinNode<Elem>*);BinNode<Elem>*
inserthelp(BinNode<Elem>*,const Elem&);BinNode<Elem>*
deletemin(BinNode<Elem>*,BinNode<Elem>*&);BinNode<Elem>* removehelp(BinNode<Elem>*,
const Key&,BinNode<Elem>*&);bool findhelp(BinNode<Elem>*,const Key&,
Elem&) const;void printhelp(BinNode<Elem>*,int) const;
二叉查找树 ADT(2)
public:BST() { root = NULL; nodecount = 0; }
~BST() { clearhelp(root); } void clear() { clearhelp(root); root = NULL;
nodecount = 0; }bool insert(const Elem& e) {
root = inserthelp(root,e);nodecount++;
return true; }bool remove(const Key& K,Elem& e) {
BinNode<Elem>* t = NULL;root = removehelp(root,K,t);
if (t == NULL) return false;e = t->val();
nodecount--;delete t;
return true; }
二叉查找树 ADT(3)
bool removeAny(Elem& e) { // Delete min valueif (root == NULL) return false; // Empty
BinNode<Elem>* t;root = deletemin(root,t);
e = t->val();delete t;
nodecount--;return true;
}bool find(const Key& K,Elem& e) const
{ return findhelp(root,K,e); }int size() { return nodecount; }
void print() const {if (root == NULL)
cout << "The BST is empty.\n";else printhelp(root,0);
}
二叉查找树的搜索
template <class Key,class Elem,
class KEComp,class EEComp>
bool BST<Key,Elem,KEComp,EEComp>::
findhelp(BinNode<Elem>* subroot,
const Key& K,Elem& e) const {
if (subroot == NULL) return false;
else if (KEComp::lt(K,subroot->val()))
return findhelp(subroot->left(),K,e);
else if (KEComp::gt(K,subroot->val()))
return findhelp(subroot->right(),K,e);
else { e = subroot->val(); return true; }
}
二叉查找树的插入 (1)
二叉查找树的插入 (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
inserthelp(BinNode<Elem>* subroot,
const Elem& val) {
if (subroot == NULL) // Empty,create node
return new BinNodePtr<Elem>(val,NULL,NULL);
if (EEComp::lt(val,subroot->val()))
subroot->setLeft(inserthelp(subroot->left(),
val));
else subroot->setRight(
inserthelp(subroot->right(),val));
// Return subtree with node inserted
return subroot;
}
删除最小值
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,
KEComp,EEComp>::
deletemin(BinNode<Elem>* subroot,
BinNode<Elem>*& min) {
if (subroot->left() == NULL) {
min = subroot;
return subroot->right();
}
else { // Continue left
subroot->setLeft(
deletemin(subroot->left(),min));
return subroot;
}
}
删除某个结点 (1)
删除某个结点 (2)
template <class Key,class Elem,
class KEComp,class EEComp>
BinNode<Elem>* BST<Key,Elem,KEComp,EEComp>::
removehelp(BinNode<Elem>* subroot,
const Key& K,BinNode<Elem>*& t) {
if (subroot == NULL) return NULL;
else if (KEComp::lt(K,subroot->val()))
subroot->setLeft(
removehelp(subroot->left(),K,t));
else if (KEComp::gt(K,subroot->val()))
subroot->setRight(
removehelp(subroot->right(),K,t));
删除某个结点 (3)
else { // Found it,remove it
BinNode<Elem>* temp;
t = subroot;
if (subroot->left() == NULL)
subroot = subroot->right();
else if (subroot->right() == NULL)
subroot = subroot->left();
else { // Both children are non-empty
subroot->setRight(
deletemin(subroot->right(),temp));
Elem te = subroot->val();
subroot->setVal(temp->val());
temp->setVal(te);
t = temp;
} }
return subroot;
}
BST 操作的时间代价
Find:
Insert:
Delete:
堆与优先队列堆,具有堆属性的完全二叉树,
最小值堆,每个结点存储的值都小于或等于其子结点存储的值,
最大值堆,每个结点存储的值都大于或等于其子结点存储的值,
堆中数据的值是局部有序的,
堆的表示,往往用数组表示完全二叉树那样，
用数组来实现,
堆 ADT
template<class Elem,class Comp> class maxheap{private:
Elem* Heap; // Pointer to the heap arrayint size; // Maximum size of the heap
int n; // Number of elems now in heapvoid siftdown(int); // Put element in place
public:maxheap(Elem* h,int num,int max);
int heapsize() const;bool isLeaf(int pos) const;
int leftchild(int pos) const;int rightchild(int pos) const;
int parent(int pos) const;bool insert(const Elem&);
bool removemax(Elem&);bool remove(int,Elem&);
void buildHeap();};
建堆
(a) (4-2) (4-1) (2-1) (5-2) (5-4) (6-3) (6-5) (7-5) (7-6)
(b) (5-2),(7-3),(7-1),(6-1)
Siftdown操作 (1)
效率高的建堆操作,
从数组的较大序号结点向较小序号结点顺序访问,
对每个分支结点调用 siftdown.
叶结点不需要调用 siftdown.
template <class Elem,class Comp>void maxheap<Elem,Comp>::siftdown(int pos) {
while (!isLeaf(pos)) {int j = leftchild(pos);
int rc = rightchild(pos);if ((rc<n) && Comp::lt(Heap[j],Heap[rc]))
j = rc;if (!Comp::lt(Heap[pos],Heap[j])) return;
swap(Heap,pos,j);pos = j;
}}
Siftdown操作 (2)
建堆的代价调用 Siftdown 的代价之和,
log n
(i - 1) n/2i? n.
i=1
删除最大值
template <class Elem,class Comp>
bool maxheap<Elem,Comp>:,
removemax(Elem& it) {
if (n == 0) return false; // Heap is empty
swap(Heap,0,--n); // Swap max with end
if (n != 0) siftdown(0);
it = Heap[n]; // Return max value
return true;
}
优先队列 (1)
一些按照重要性或优先级来组织的对象称为优先队列,
例,在多任务操作系统的作业调度,
作业的优先级可能改变，也就要求将队列中的作业重新排序,
实现,使用堆来存储优先队列,
优先队列 (2)
为了支持优先级重新排序,删除和插入操作需要知道操作对象在队列中的索引位置,
template <class Elem,class Comp>
bool maxheap<Elem,Comp>::remove(int pos,
Elem& it) {
if ((pos < 0) || (pos >= n)) return false;
swap(Heap,pos,--n);
while ((pos != 0) && (Comp::gt(Heap[pos],
Heap[parent(pos)])))
swap(Heap,pos,parent(pos));
siftdown(pos);
it = Heap[n];
return true;
}
Huffman 编码树
ASCII 编码,每个字符占用一个字节 8bit.
固定长度编码,
– 如果每个字符的使用频率都相等，则空间效率最高,
变长编码
按照最小外部路径权重建立一棵树,
Z K F C U D L E
2 7 24 32 37 42 42 120
建立 Huffman 编码树 (1)
建立 Huffman 编码树 (2)
定理引理
一棵至少包含两个结点的 Huffman树，会把字母使用频率最小的两个字母作为兄弟结点存储，
其深度不比树中其它任何结点小
定理
对于一组给定的字母，函数 buildHuff实现了
“最小外部路径权重”
代码标记
Letter Freq Code Bits
C 32
D 42
E 120
F 24
K 7
L 42
U 37
Z 2
编码和解码如果一组代码中的任何一个代码都不是另一个代码的前缀，则称这组代码符合前缀特性,
为单词 DEED编码,
为数字串 1011001110111101解码,
代码长度比较,
通用树树结点的抽象数据结构
// General tree node ADTtemplate <class Elem> class GTNode {
public:GTNode(const Elem&); // Constructor
~GTNode(); // DestructorElem value(); // Return value
bool isLeaf(); // TRUE if is a leafGTNode* parent(); // Return parent
GTNode* leftmost_child(); // First childGTNode* right_sibling(); // Right sibling
void setValue(Elem&); // Set valuevoid insert_first(GTNode<Elem>* n);
void insert_next(GTNode<Elem>* n);void remove_first(); // Remove first child
void remove_next(); // Remove sibling};
通用树的遍历
template <class Elem>void GenTree<Elem>::
printhelp(GTNode<Elem>* subroot) {if (subroot->isLeaf()) cout << "Leaf,";
else cout << "Internal,";cout << subroot->value() << "\n";
for (GTNode<Elem>* temp =subroot->leftmost_child();
temp != NULL;temp = temp->right_sibling())
printhelp(temp);}
父指针实现等价类问题父指针表示法精确地保存了解答下面问题所需的信息,
– 给出两个结点，它们是否在同一棵树中?
// Return TRUE if nodes in different trees
bool Gentree::differ(int a,int b) {
int root1 = FIND(a); // Find root for a
int root2 = FIND(b); // Find root for b
return root1 != root2; // Compare roots
}
Union/Find
void Gentree::UNION(int a,int b) {int root1 = FIND(a); // Find root for a
int root2 = FIND(b); // Find root for bif (root1 != root2) array[root2] = root1;
}
int Gentree::FIND(int curr) const {while (array[curr]!=ROOT) curr = array[curr];
return curr; // At root}
为了使等价对的处理尽可能高效，要尽量降低树的高度,
重量权衡合并原则,树合并时，将结点较少的树的根结点指向结点较多树的根结点,
等价类处理 (1)
等价类处理 (2)
路径压缩
int Gentree::FIND(int curr) const {
if (array[curr] == ROOT) return curr;
return array[curr] = FIND(array[curr]);
}
子结点表左子结点 /右兄弟结点表示法 (1)
左子结点 /右兄弟结点表示法 (2)
动态结点表示法 (1)
动态结点表示法 (2)
森林转化为二叉树左子结点 /右兄弟结点表示法本质上是存储了一棵二叉树,
顺序树表示法 (1)
把结点值按照它们在先序遍历的顺序存储起来，同时保存描述树形状的充足信息,
节省空间,但对于结点的存取，都必须顺序查找所有在结点表中排在它前面的结点,
例,对于二叉树,用,/”表示空指针 null.
AB/D//CEG///FH//I//
顺序树表示法 (2)
例,将上例的树理解为满二叉树,对叶结点和分支结点分别标记,
A’B’/DC’E’G/F’HI
例,对于通用树，给每个子树的结束给出标记,
RAC)D)E))BF)))
内排序排序术语及记号：
所有排序算法的输入都是存储在数组中的一组记录
每个记录都包含一个关键码域,
– 线性次序,关键码比较,
代价的衡量,
– 关键码比较的次数
– 交换次数插入排序 (1)
插入排序 (2)
template <class Elem,class Comp>void inssort(Elem A[],int n) {
for (int i=1; i<n; i++)for (int j=i; (j>0) &&
(Comp::lt(A[j],A[j-1])); j--)swap(A,j,j-1);
}
最好情况,
最差情况,
平均情况,
起泡排序 (1)
起泡排序 (2)
template <class Elem,class Comp>void bubsort(Elem A[],int n) {
for (int i=0; i<n-1; i++)for (int j=n-1; j>i; j--)
if (Comp::lt(A[j],A[j-1]))swap(A,j,j-1);
}
最好情况,
最差情况,
平均情况,
选择排序 (1)
选择排序 (2)
template <class Elem,class Comp>void selsort(Elem A[],int n) {
for (int i=0; i<n-1; i++) {int lowindex = i; // Remember its index
for (int j=n-1; j>i; j--) // Find leastif (Comp::lt(A[j],A[lowindex]))
lowindex = j; // Put it in placeswap(A,i,lowindex);
}}
最好情况,
最差情况,
平均情况,
指针交换总结插入排序 起泡排序 选择排序比较次数,
最佳情况?(n)?(n2)?(n2)
平均情况?(n2)?(n2)?(n2)
最差情况?(n2)?(n2)?(n2)
交换次数：
最佳情况 0 0?(n)
平均情况?(n2)?(n2)?(n)
最差情况?(n2)?(n2)?(n)
交换排序
All of the sorts so far rely on exchanges of
adjacent records.
What is the average number of exchanges
required?
– There are n! permutations
– Consider permuation X and its reverse,X’
– Together,every pair requires n(n-1)/2
exchanges.
Shell排序
Shell排序
// Modified version of Insertion Sorttemplate <class Elem,class Comp>
void inssort2(Elem A[],int n,int incr) {for (int i=incr; i<n; i+=incr)
for (int j=i;(j>=incr) &&
(Comp::lt(A[j],A[j-incr])); j-=incr)swap(A,j,j-incr);
}
template <class Elem,class Comp>void shellsort(Elem A[],int n) { // Shellsort
for (int i=n/2; i>2; i/=2) // For each incrfor (int j=0; j<i; j++) // Sort sublists
inssort2<Elem,Comp>(&A[j],n-j,i);inssort2<Elem,Comp>(A,n,1);
}
快速排序
template <class Elem,class Comp>void qsort(Elem A[],int i,int j) {
if (j <= i) return; // List too smallint pivotindex = findpivot(A,i,j);
swap(A,pivotindex,j); // Put pivot at end// k will be first position on right side
int k = partition<Elem,Comp>(A,i-1,j,A[j]);
swap(A,k,j); // Put pivot in placeqsort<Elem,Comp>(A,i,k-1);
qsort<Elem,Comp>(A,k+1,j);}
template <class Elem>int findpivot(Elem A[],int i,int j)
{ return (i+j)/2; }
快速排序分割
template <class Elem,class Comp>int partition(Elem A[],int l,int r,
Elem& pivot) {do { // Move the bounds in until they meet
while (Comp::lt(A[++l],pivot));while ((r != 0) && Comp::gt(A[--r],
pivot));swap(A,l,r); // Swap out-of-place values
} while (l < r); // Stop when they crossswap(A,l,r); // Reverse last swap
return l; // Return first pos on right}
The cost for partition is?(n).
分割示例快速排序示例快速排序的代价最佳情况,每次轴值都将数组二等分,
最差情况,轴值的分割效果很差,
平均情况,
T(n) = n + 1 + 1/(n-1)?(T(k) + T(n-k))
快速排序的优化,
– 改进轴值的选择
– 当子序列小时，改进排序算法
– 减少递归
k=1
n-1
归并排序
List mergesort(List inlist) {
if (inlist.length() <= 1)return inlist;
List l1 = half of the items from inlist;
List l2 = other half of items from inlist;
return merge(mergesort(l1),
mergesort(l2));
}
归并排序实现
template <class Elem,class Comp>void mergesort(Elem A[],Elem temp[],
int left,int right) {int mid = (left+right)/2;
if (left == right) return; mergesort<Elem,Comp>(A,temp,left,mid);
mergesort<Elem,Comp>(A,temp,mid+1,right);for (int i=left; i<=right; i++) // Copy
temp[i] = A[i];int i1 = left; int i2 = mid + 1;
for (int curr=left; curr<=right; curr++) {if (i1 == mid+1) // Left exhausted
A[curr] = temp[i2++];else if (i2 > right) // Right exhausted
A[curr] = temp[i1++];else if (Comp::lt(temp[i1],temp[i2]))
A[curr] = temp[i1++];else A[curr] = temp[i2++];
}}
归并排序优化
template <class Elem,class Comp>void mergesort(Elem A[],Elem temp[],
int left,int right) {if ((right-left) <= THRESHOLD) {
inssort<Elem,Comp>(&A[left],right-left+1);return;
}int i,j,k,mid = (left+right)/2;
if (left == right) return;mergesort<Elem,Comp>(A,temp,left,mid);
mergesort<Elem,Comp>(A,temp,mid+1,right);for (i=mid; i>=left; i--) temp[i] = A[i];
for (j=1; j<=right-mid; j++)temp[right-j+1] = A[j+mid];
for (i=left,j=right,k=left; k<=right; k++)if (temp[i] < temp[j]) A[k] = temp[i++];
else A[k] = temp[j--];}
归并排序的代价归并排序的代价,
归并排序可以很好地处理单链表,
归并排序需要双倍 的空间,
堆排序
template <class Elem,class Comp>
void heapsort(Elem A[],int n) { // Heapsort
Elem mval;
maxheap<Elem,Comp> H(A,n,n);
for (int i=0; i<n; i++) // Now sort
H.removemax(mval); // Put max at end
}
基于最大值堆排序：首先构造堆，然后取出堆顶的最大元素，然后重排堆再取出堆顶最大值，重复下去，直到堆为空,
堆排序的时间代价,
找到数组中第 K大的元素,
堆排序示例 (1)
堆排序示例 (2)
分配排序 (1)
一个简单高效的排序,
for (i=0; i<n; i++)
B[A[i]] = A[i];
扩展方法,
– 允许关键码重复,使数组的每个元素称为一个链表的头结点
– 允许关键码范围大于 n.
分配排序 (2)
template <class Elem>
void binsort(Elem A[],int n) {
List<Elem> B[MaxKeyValue];
Elem item;
for (i=0; i<n; i++) B[A[i]].append(A[i]);
for (i=0; i<MaxKeyValue; i++)
for (B[i].setStart();
B[i].getValue(item); B[i].next())
output(item);
}
代价,
基数排序 (1)
基数排序 (2)
template <class Elem,class Comp>
void radix(Elem A[],Elem B[],
int n,int k,int r,int cnt[]) {
// cnt[i] stores # of records in bin[i]
int j;
for (int i=0,rtok=1; i<k; i++,rtok*=r) {
for (j=0; j<r; j++) cnt[j] = 0;
// Count # of records for each bin
for(j=0; j<n; j++) cnt[(A[j]/rtok)%r]++;
// cnt[j] will be last slot of bin j.
for (j=1; j<r; j++)
cnt[j] = cnt[j-1] + cnt[j];
for (j=n-1; j>=0; j--)\
B[--cnt[(A[j]/rtok)%r]] = A[j];
for (j=0; j<n; j++) A[j] = B[j];
}}
基数排序示例基数排序的代价代价,?(nk + rk)
如何看待 n,k,和 r 的关系?
如果关键码的取值范围较小,则代价只为?(n).
如果有 n 个不重复的关键码值,则至少需要 log n位来区别这 n 个不同的关键码值,
– 因此,基数排序在平均情况下的代价为?(n log n)
排序算法的实验比较 (1)
排序算法的实验比较 (2)
排序问题的下限我们想知道所有可能的排序算法的时间代价的下限,
排序问题的输入和输出需要?(n) 时间，就实际而知，排序的时间在?(n) 和 O(n log n)
之间将要证明：没有一种基于关键码比较的排序算法可以将最差执行时间降低到?(n log n)
以下,
插入排序的判定树下限证明
n个数据会有 n! 种排列,
一个排序算法可以看作决定哪一种排序作为输出,
判定树
判定树的每一个叶结点对应一种排列,
一棵具有 n 个结点的二叉树有?(log n) 层,
因此一棵具有 n! 个结点的二叉树有?(log
n!) =?(n log n) 层,
Primary vs,Secondary Storage
Primary storage,Main memory (RAM)
Secondary Storage,Peripheral devices
– Disk drives
– Tape drives
Comparisons
RAM is usually volatile.
RAM is about 1/4 million times faster than
disk.
Medium Early 1996 Mid 1997 Early 2000
RAM $45.00 7.00 1.50
Disk 0.25 0.10 0.01
Floppy 0.50 0.36 0.25
Tape 0.03 0.01 0.001
Golden Rule of File Processing
Minimize the number of disk accesses!
1,Arrange information so that you get what you want
with few disk accesses.
2,Arrange information to minimize future disk accesses.
An organization for data on disk is often called a
file structure.
Disk-based space/time tradeoff,Compress
information to save processing time by
reducing disk accesses.
Disk Drives
Sectors
A sector is the basic unit of I/O.
Interleaving factor,Physical distance
between logically adjacent sectors on a
track.
Terms
Locality of Reference,When record is read
from disk,next request is likely to come from
near the same place in the file.
Cluster,Smallest unit of file allocation,usually
several sectors.
Extent,A group of physically contiguous clusters.
Internal fragmentation,Wasted space within
sector if record size does not match sector size;
wasted space within cluster if file size is not a
multiple of cluster size.
Seek Time
Seek time,Time for I/O head to reach
desired track,Largely determined by
distance between I/O head and desired
track.
Track-to-track time,Minimum time to move
from one track to an adjacent track.
Average Seek time,Average time to reach a
track for random access.
Other Factors
Rotational Delay or Latency,Time for data
to rotate under I/O head.
– One half of a rotation on average.
– At 7200 rpm,this is 8.3/2 = 4.2ms.
Transfer time,Time for data to move under
the I/O head.
– At 7200 rpm,Number of sectors
read/Number of sectors per track * 8.3ms.
Disk Spec Example
16.8 GB disk on 10 platters = 1.68GB/platter
13,085 tracks/platter
256 sectors/track
512 bytes/sector
Track-to-track seek time,2.2 ms
Average seek time,9.5ms
4KB clusters,32 clusters/track.
Interleaving factor of 3.
5400RPM
Disk Access Cost Example (1)
Read a 1MB file divided into 2048 records of
512 bytes (1 sector) each.
Assume all records are on 8 contiguous
tracks.
First track,9.5 + 11.1/2 + 3 x 11.1 = 48.4 ms
Remaining 7 tracks,2.2 + 11.1/2 + 3 x 11.1
= 41.1 ms.
Total,48.4 + 7 * 41.1 = 335.7ms
Disk Access Cost Example (2)
Read a 1MB file divided into 2048 records of
512 bytes (1 sector) each.
Assume all file clusters are randomly spread
across the disk.
256 clusters,Cluster read time is
(3 x 8)/256 of a rotation for about 1 ms.
256(9.5 + 11.1/2 + (3 x 8)/256) is about
3877 ms,or nearly 4 seconds.
How Much to Read?
Read time for one track:
9.5 + 11.1/2 + 3 x 11.1 = 48.4ms.
Read time for one sector:
9.5 + 11.1/2 + (1/256)11.1 = 15.1ms.
Read time for one byte:
9.5 + 11.1/2 = 15.05 ms.
Nearly all disk drives read/write one sector
at every I/O access.
– Also referred to as a page.
Buffers
The information in a sector is stored in a
buffer or cache.
If the next I/O access is to the same buffer,
then no need to go to disk.
There are usually one or more input buffers
and one or more output buffers.
Buffer Pools
A series of buffers used by an application to
cache disk data is called a buffer pool.
Virtual memory uses a buffer pool to imitate
greater RAM memory by actually storing
information on disk and,swapping”
between disk and RAM.
Buffer Pools
Organizing Buffer Pools
Which buffer should be replaced when new
data must be read?
First-in,First-out,Use the first one on the
queue.
Least Frequently Used (LFU),Count buffer
accesses,reuse the least used.
Least Recently used (LRU),Keep buffers on
a linked list,When buffer is accessed,
bring it to front,Reuse the one at end.
Bufferpool ADT (1)
class BufferPool { // (1) Message Passingpublic:
virtual void insert(void* space,int sz,int pos) = 0;
virtual void getbytes(void* space,int sz,int pos) = 0;
};
class BufferPool { // (2) Buffer Passing
public:
virtual void* getblock(int block) = 0;
virtual void dirtyblock(int block) = 0;
virtual int blocksize() = 0;
};
Design Issues
Disadvantage of message passing:
– Messages are copied and passed back and forth,
Disadvantages of buffer passing:
– The user is given access to system memory (the
buffer itself)
– The user must explicitly tell the buffer pool when
buffer contents have been modified,so that modified
data can be rewritten to disk when the buffer is
flushed,
– The pointer might become stale when the bufferpool
replaces the contents of a buffer.
Programmer’s View of Files
Logical view of files:
– An a array of bytes.
– A file pointer marks the current position.
Three fundamental operations:
– Read bytes from current position (move file pointer)
– Write bytes to current position (move file pointer)
– Set file pointer to specified byte position.
C++ File Functions
#include <fstream.h>
void fstream::open(char* name,openmode mode);
– Example,ios::in | ios::binary
void fstream::close();
fstream::read(char* ptr,int numbytes);
fstream::write(char* ptr,int numbtyes);
fstream::seekg(int pos);
fstream::seekg(int pos,ios::curr);
fstream::seekp(int pos);
fstream::seekp(int pos,ios::end);
External Sorting
Problem,Sorting data sets too large to fit
into main memory.
– Assume data are stored on disk drive.
To sort,portions of the data must be brought
into main memory,processed,and
returned to disk.
An external sort should minimize disk
accesses.
Model of External Computation
Secondary memory is divided into equal-sized
blocks (512,1024,etc…)
A basic I/O operation transfers the contents of one
disk block to/from main memory.
Under certain circumstances,reading blocks of a
file in sequential order is more efficient,
(When?)
Primary goal is to minimize I/O operations.
Assume only one disk drive is available.
Key Sorting
Often,records are large,keys are small.
– Ex,Payroll entries keyed on ID number
Approach 1,Read in entire records,sort
them,then write them out again.
Approach 2,Read only the key values,store
with each key the location on disk of its
associated record.
After keys are sorted the records can be
read and rewritten in sorted order.
Simple External Mergesort (1)
Quicksort requires random access to the
entire set of records.
Better,Modified Mergesort algorithm.
– Process n elements in?(log n) passes.
A group of sorted records is called a run.
Simple External Mergesort (2)
Split the file into two files.
Read in a block from each file.
Take first record from each block,output them in
sorted order.
Take next record from each block,output them
to a second file in sorted order.
Repeat until finished,alternating between output
files,Read new input blocks as needed.
Repeat steps 2-5,except this time input files
have runs of two sorted records that are merged
together.
Each pass through the files provides larger runs.
Simple External Mergesort (3)
Problems with Simple Mergesort
Is each pass through input and output files
sequential?
What happens if all work is done on a single disk
drive?
How can we reduce the number of Mergesort
passes?
In general,external sorting consists of two phases:
– Break the files into initial runs
– Merge the runs together into a single run.
Breaking a File into Runs
General approach:
– Read as much of the file into memory as
possible.
– Perform an in-memory sort.
– Output this group of records as a single run.
Replacement Selection (1)
Break available memory into an array for
the heap,an input buffer,and an output
buffer.
Fill the array from disk.
Make a min-heap.
Send the smallest value (root) to the
output buffer.
Replacement Selection (2)
If the next key in the file is greater than
the last value output,then
– Replace the root with this key
else
– Replace the root with the last key in the
array
Add the next record in the file to a new heap
(actually,stick it at the end of the array).
RS Example
Snowplow Analogy (1)
Imagine a snowplow moving around a circular
track on which snow falls at a steady rate.
At any instant,there is a certain amount of
snow S on the track,Some falling snow
comes in front of the plow,some behind.
During the next revolution of the plow,all of
this is removed,plus 1/2 of what falls
during that revolution.
Thus,the plow removes 2S amount of snow.
Snowplow Analogy (2)
Problems with Simple Merge
Simple mergesort,Place runs into two files.
– Merge the first two runs to output file,then
next two runs,etc.
Repeat process until only one run remains.
– How many passes for r initial runs?
Is there benefit from sequential reading?
Is working memory well used?
Need a way to reduce the number of passes.
Multiway Merge (1)
With replacement selection,each initial run
is several blocks long.
Assume each run is placed in separate file.
Read the first block from each file into
memory and perform an r-way merge.
When a buffer becomes empty,read a block
from the appropriate run file.
Each record is read only once from disk
during the merge process.
Multiway Merge (2)
In practice,use only one file and seek to
appropriate block.
Limits to Multiway Merge (1)
Assume working memory is b blocks in size.
How many runs can be processed at one
time?
The runs are 2b blocks long (on average).
How big a file can be merged in one pass?
Limits to Multiway Merge (2)
Larger files will need more passes -- but the
run size grows quickly!
This approach trades (log b) (possibly)
sequential passes for a single or very
few random (block) access passes.
General Principles
A good external sorting algorithm will seek to do
the following:
– Make the initial runs as long as possible.
– At all stages,overlap input,processing and
output as much as possible.
– Use as much working memory as possible,
Applying more memory usually speeds
processing.
– If possible,use additional disk drives for
more overlapping of processing with I/O,
and allow for more sequential file processing.
检索假定,互不相同的关键码值 k1,k2,…,kn 和一个包含 n 条记录的集合 C，形式为：
(k1,I1),(k2,I2),…,( kn,In)
其中 Ij 是与关键码值 kj相关联的信息,1 <= j
<= n.
检索问题,对于给定的关键码值 K,在 C 中定位记录 (kj,Ij),使得 kj = K.
检索 就是定位关键码值 kj = K 的记录的系统化方法,
检索结果检索成功 就是找到至少一个关键码值为 kj的记录，使得 kj = K.
检索失败 就是找不到记录，使得 kj = K.
检索算法
1.顺序表和线性表方法,
2,根据关键码值直接访问方法 (散列法 )
3,树索引方法,
检索已排序的数组顺序检索二分查找插值检索（字典检索）
自组织线性表根据（估算的）访问频率排列记录,
–顺序检索预计的比较时间代价为：
..,,21 21 nn npppC
例 (1)
(1) 所有记录的访问频率相同,
2/)1(/
1
nniC
n
i
n
例 (2)
(2) 指数频率
ni
ni
p
n
i
i
if2/1
11if2/1
1
{
n
i
i
n iC
1
.2)2/(
Zipf 分布应用,
– 自然语言的单词使用频率,
– 城市中的人口规模,
80/20 规则,
– 80% 的访问都是对 20% 的记录进行的,
– 当频率遵循 80/20 规则,代价为
n
i
ennn nnniiC
1
.lo g/H/Η/
.1.0 nC n?
自组织线性表自组织线性表根据实际的记录访问模式在线性表中修改记录顺序,
自组织线性表使用 启发式规则 决定如何重新排列线性表,
启发式规则假设有 8条记录，关键码值为 A到 H，最初以字母顺序排列。
按照下面的访问模式：
F D F G E G F A D F G E
计数统计方法,保持线性表按照访问频率排序,(类似于缓冲池替代策略中的“最不频繁使用”法,)
结果,FGDEABCH
2,移至前端,找到一条记录就把它放到线性表的最前面,
结果,EGFDABCH
3,转置,把找到的记录与它在线性表中的前一条记录交换位置,
结果,ABFDGECH
文本压缩示例发送者和接收者都以同样的方式记录单词在线性表中的位置，线性表根据移至前端规则自组织,
如果单词没有出现过，就传送这个单词,
否则就传送这个单词在线性表当前的位置,
The car on the left hit the car I left.
The car on 3 left hit 3 5 I 5.
这种压缩方法的思想类似于 Ziv-Lempel 编码算法,
集合的检索对于密集集合 (关键码范围小，集合中元素的分布百分比高 ).
可以采用存储一个逻辑位数组进行操作,
例,寻找 0～ 15之间的奇素数,
0011010100010100 & 0101010101010101
散列方法 (1)
散列,把关键码值映射到检索表中的位置来访问记录,
散列函数把关键码值映射到检索表中的位置,
用 h 表示,
散列表就是存放记录的数组,用 HT 表示,
散列表 HT 有 M 个槽,槽从 0 到 M-1编号,
散列方法 (2)
设计散列函数的目标是：对于表中任意关键码值 K
和某个散列函数 h,h(K) = i,0 <= i < M,使得
(HT[i]) = K.
散列方法一般只适用于集合 (关键码不重复 ).
既适用于基于主存的检索，也适合于基于磁盘的检索,
适合于回答：“如果有的话，哪条记录的关键码值等于 K?”
简单的例子
(1) N条记录，每条记录具有唯一关键码值，范围从
0 到 n-1.
– 带有关键码 i 的记录存储在槽 HT[i]中,
– 散列函数 h(K) = K.
(2) 更为实际的例子,
– 存储约 1000条记录，关键码值范围在 0 到 65536.
– 使用带有 65536个槽的散列表是不切实际的,
– 必须设计一个散列函数，允许把记录存储在更小的表中,
冲突 (1)
给定,散列函数 h 和两个关键码值 k1 和 k2,? 是表中的一个槽,
如果 h(k1) =? = h(k2),则 k1 和 k2 对于? 在散列函数 h下有冲突,
在根据散列方法组织的数据库中，找到具有关键码值 K 的记录,
1,计算表的位置 h(K).
2,从槽 h(K)开始,使用冲突解决策略找到吧具有关键码值 K 的记录,
散列函数 (1)
一个散列函数的返回值必须在散列表范围内,
实际应用中,散列函数应该将记录均匀地分布到散列表的各个槽中,
希望选择的散列函数能把记录以相同的概率分布到散列表的所有槽中,在一般情况下,
散列函数的实现依赖于关键码值在可允许的关键码范围内的分布,
散列函数 (2)
如果对关键码值的分布不了解：
希望选择的 散列函数 在关键码范围内能产生一个大致平均的关键码值随机分布，同时避免明显的聚集可能性如果对关键码值的分布有所了解：
使用一个依赖于分布的散列函数，避免把一组相关的关键码值映射到散列表的同一个槽中,
示例 (1)
int h(int x)
{
return(x % 16);
}
散列函数的返回值只依赖于关键码的最低四位,
平方取中法,
计算关键码的平方，对于长度为 2r的表，取出中间的 r位,
示例 (2)
对于字符串,将字符串所有字母的 ASCII值累加起来，对 M取模,
int h(char* x) {
int i,sum;
for (sum=0,i=0; x[i] != '\0'; i++)
sum += (int) x[i];
return(sum % M);
}
当累加值比 M 大得多时，散列效果很好,
示例 (3)
ELF Hash,在 UNIX系统 V Release 4的 ELF
(Executable and Linking Format )文件格式用到,
int ELFhash(char* key) {
unsigned long h = 0;
while(*key) {
h = (h << 4) + *key++;
unsigned long g = h & 0xF0000000L;
if (g) h ^= g >> 24;
h &= ~g;
}
return h % M;
}
开散列方法冲突解决技术,开散列方法，闭散列方法开散列方法 把冲突记录存储在表外,
闭散列方法闭散列方法把所有的记录直接存储在散列表中,
每条记录 i 有一个基位置 h(ki).
如果另一条记录已经占用了 i的基位置,则根据冲突解决策略将它存到表中的其他槽内。
检索必须遵循同样的策略，以便重复进行冲突解决过程，找出基位置没有找到的记录,
桶式散列把散列表的槽分成多个桶,
– 例,有 7个数的桶式散列方法,
包含一个溢出桶,
记录被散列到某个桶的第一个槽，如果被占用，则顺序地沿着桶查找，直到找到一个空槽。如果桶中全被占满，则存往溢出桶,
检索时,首先散列关键码，在相应的桶中检索。如果未找到而桶是满的，还需查找溢出桶,
冲突解决插入期间,冲突解决策略的目的就是：当记录的基位置已被占用时在散列表中找到一个空槽,
探查序列,在插入 /检索时遵循某种冲突解决策略的对散列表中槽的访问序列,
插入
// Insert e into hash table HT
template <class Key,class Elem,
class KEComp,class EEComp>
bool hashdict<Key,Elem,KEComp,EEComp>::
hashInsert(const Elem& e) {
int home; // Home position for e
int pos = home = h(getkey(e)); // Init
for (int i=1;
!(EEComp::eq(EMPTY,HT[pos])); i++) {
pos = (home + p(getkey(e),I)) % M;
if (EEComp::eq(e,HT[pos]))
return false; // Duplicate
}
HT[pos] = e; // Insert e
return true;
}
检索
// Search for the record with Key Ktemplate <class Key,class Elem,
class KEComp,class EEComp>bool hashdict<Key,Elem,KEComp,EEComp>::
hashSearch(const Key& K,Elem& e) const {int home; // Home position for K
int pos = home = h(K); // Initial positfor (int i = 1; !KEComp::eq(K,HT[pos]) &&
!EEComp::eq(EMPTY,HT[pos]); i++)pos = (home + p(K,i)) % M; // Next
if (KEComp::eq(K,HT[pos])) { // Found ite = HT[pos];
return true;}
else return false; // K not in hash table}
探查函数注意语句中的探查函数 p().
pos = (home + p(getkey(e),i)) % M;
每次调用 p(),返回从基位置开始的偏移量，
从而检查此位置上的槽,
从散列表中检索记录和插入记录都根据 p()
采用相同的探查序列
– 并非所有的探查函数都采用相同的参数,
线性探查简单线性探查的探查函数为,
p(K,i) = i;
线性探查：如果记录的基位置被占用，则简单地在桶中下移，直到找到一个空槽,
– 如果探查过了底部，则换到顶部探查,
为了避免出现死循环，必须保证探查序列中至少有一个空槽,
线性探查示例基本聚集,
线性探查的把记录聚集到一起的倾向,
改进的线性探查线性探查时每次跳过常数 c个槽而非一个槽,
– 注意,慎重选择 M 和 c,
探查序列应该能走遍表中的所有槽,
– 常数 c 与 M互素,
仍然会有聚集可能
– 如,c=2,h(k1) = 3; h(k2) = 5.
– k1 和 k2 的探查序列链接到了一起,
伪随机探查 (1)
在探查序列中随机地从未走过的槽中选择下一个位置,
实际上不能随机地从探查序列中选择下一个位置,(为什么?)
伪随机探查 (2)
选择一个（随机的）排列，其值从 1到 M-
1:
r1,r2,…,rM-1
所有的插入和检索使用同样的排列数组,
例,散列表长度 M = 101
– r1=2,r2=5,r3=32.
– h(k1)=30,h(k2)=28.
– k1的探查序列,
– k2的探查序列,
二次探查令探查序列的第 i个值是
h(K,i) = i2;
例,M=101
– h(k1)=30,h(k2) = 29.
– k1的探查序列,
– k2的探查序列,
二级聚集伪随机探查和二次探查都能基本消除基本聚集,
如果两个关键码散列到同一个基位置，则它 们有相同的探查序列,这个问题称为 二级聚集,
为了避免二级聚集，需要使探查序列 是原始关键码值的函数，而不是基位置的函数,
双散列方法
p(K,i) = i * h2(K)
应保证所有探查序列常数 (h2(K))都与表长度 M互素,
– 选择 M 为一个素数
– 对于某个值 m，设 M=2m 返回一个 1到 2m之间的奇数值,
例,散列表长度 M = 101
– h(k1)=30,h(k2)=28,h(k3)=30.
– h2(k1)=2,h2(k2)=5,h2(k3)=5.
– k1的探查序列,
– k2的探查序列,
– k3的探查序列,
闭散列方法分析负载因子为 a = N/M,其中 N 是表中当前的记录个数,
删除删除记录一定不能影响后面的检索,
不希望让散列表中的位置由于记录删除而不可再用，释放的槽应该能为后来的插入所使用,
墓碑 (1)
上述两个问题可以通过在被删除记录的位置上设置一个特殊标记，该标记被称为 墓碑通过使用墓碑，检索仍能正常工作，并且能够重新使用已删除记录的槽,
墓碑 (2)
由于墓碑的存在，将增加记录本身到其基位置的平均长度,
解决方案,
1,删除时进行一次局部重组，试图缩小平均路径长度,
2,定期重新散列整个表,
Indexing
Goals:
– Store large files
– Support multiple search keys
– Support efficient insert,delete,and range
queries
Terms(1)
Entry sequenced file,Order records by time
of insertion.
– Search with sequential search
Index file,Organized,stores pointers to
actual records.
– Could be organized with a tree or other data
structure.
Terms(2)
Primary Key,A unique identifier for records,
May be inconvenient for search.
Secondary Key,An alternate search key,
often not unique for each record,Often
used for search key.
Linear Indexing
Linear index,Index file organized as a
simple sequence of key/record pointer
pairs with key values are in sorted order.
Linear indexing is good for searching
variable-length records.
Linear Indexing (2)
If the index is too large to fit in main memory,
a second-level index might be used.
Tree Indexing (1)
Linear index is poor for insertion/deletion.
Tree index can efficiently support all desired
operations:
– Insert/delete
– Multiple search keys (multiple indices)
– Key range search
Tree Indexing (2)
Difficulties when storing tree
index on disk:
– Tree must be balanced.
– Each path from root to leaf
should cover few disk pages.
2-3 Tree (1)
A 2-3 Tree has the following properties:
1,A node contains one or two keys
2,Every internal node has either two children
(if it contains one key) or three children (if it
contains two keys).
3,All leaves are at the same level in the tree,
so the tree is always height balanced.
The 2-3 Tree has a search tree property
analogous to the BST.
2-3 Tree (2)
The advantage of the 2-3 Tree over the BST
is that it can be updated at low cost.
2-3 Tree Insertion (1)
2-3 Tree Insertion (2)
2-3 Tree Insertion (3)
B-Trees (1)
The B-Tree is an extension of the 2-3 Tree.
The B-Tree is now the standard file
organization for applications requiring
insertion,deletion,and key range
searches.
B-Trees (2)
1,B-Trees are always balanced.
2,B-Trees keep similar-valued records
together on a disk page,which takes
advantage of locality of reference.
3,B-Trees guarantee that every node in the
tree will be full at least to a certain
minimum percentage,This improves
space efficiency while reducing the
typical number of disk fetches necessary
during a search or update operation.
B-Tree Definition
A B-Tree of order m has these properties:
– The root is either a leaf or has at least two children.
– Each node,except for the root and the leaves,has
between?m/2? and m children.
– All leaves are at the same level in the tree,so the
tree is always height balanced.
A B-Tree node is usually selected to match the
size of a disk block.
– A B-Tree node could have hundreds of children.
B-Tree Search (1)
Search in a B-Tree is a generalization of
search in a 2-3 Tree.
1,Do binary search on keys in current node,If
search key is found,then return record,If
current node is a leaf node and key is not
found,then report an unsuccessful search.
2,Otherwise,follow the proper branch and
repeat the process.
B+-Trees
The most commonly implemented form of the B-
Tree is the B+-Tree.
Internal nodes of the B+-Tree do not store record --
only key values to guild the search.
Leaf nodes store records or pointers to records.
A leaf node may store more or less records than
an internal node stores keys.
B+-Tree Example
B+-Tree Insertion
B+-Tree Deletion (1)
B+-Tree Deletion (2)
B+-Tree Deletion (3)
B-Tree Space Analysis (1)
B+-Trees nodes are always at least half full.
The B*-Tree splits two pages for three,and
combines three pages into two,In this
way,nodes are always 2/3 full.
Asymptotic cost of search,insertion,and
deletion of nodes from B-Trees is?(log n).
– Base of the log is the (average) branching
factor of the tree.
B-Tree Space Analysis (2)
Example,Consider a B+-Tree of order 100
with leaf nodes containing 100 records.
1 level B+-tree:
2 level B+-tree:
3 level B+-tree:
4 level B+-tree:
Ways to reduce the number of disk fetches:
– Keep the upper levels in memory.
– Manage B+-Tree pages with a buffer pool.
图的应用
– 为计算机与通信网络的互联建模
– 把一张地图表示为一组位置以及位置之间的距离，以求得位置之间的最短路径
– 为交通网络的流量建模
– 寻找从开始状态到目标状态的路径，如人工智能问题求解
– 为计算机算法建模，显示程序状态的变化
– 为复杂活动各子任务的完成寻找较优顺序，如大型建筑的建造
– 为家族、商业或军事组织和自然科学分类中的各种关系建模图
图可以用 G＝ (V,E)来表示，每个图都包括一个顶点集合 V和一个边集合 E，其中 E中的每条边都是 V中某一对顶点之间的连接，顶点总数记为 |V|，边的总数记为 |E|。边数较少的图称为稀疏图，边数较多的图称为密集图，包括所有可能边的图称为完全图。
图 (2)
(a)一个图； (b)一个有向图 ； ( c)一个有向标号图，其边上标有权。
( c)中从顶点 0到顶点 3存在一条包括顶点 0、顶点 1和顶点 3的简单路径。
顶点 0,1,3,2,4再到顶点 1也构成一条路径，但不是简路径，因为顶点 1出现了两次。顶点 1,3,2,4再到顶点 1构成了一条简单回路路径和回路
路径,
– 如果顶点序列 v1,v2,…,vn,从 vi到 vi+1(1 <= i < n)的边均存在，则称顶点序列 v1,v2,…,vn 构成一条长度为 n-1的路径 (path)。
简单路径,
– 如果路径上的各个顶点都不同，则称这个路径为简单路径。
路径长度,
– 是指路径包含的边数。
回路,
– 如果一条路径将某个顶点 (如 vi)连接到它本身，且其长度大于或等于 3，则称此路径为回路。
简单回路,
– 如果构成回路的路径是简单路径，除了首尾两个顶点相同以外其他顶点均不同，则称此回路为简单回路。
无环图,
– 不带回路的图称为无环图。不带回路的有向图则称为有向无环图。
自由树,
– 不带简单回路的连通无向图。同样还可以把一棵自由树定义为连通且有
|V|-1条边的图。
连通分量
子图,
– 子图 S是通过从图 G中选出其顶点集的一个子集 Vs，以及与 Vs中顶点相关联的一些边构成的子集 Es所形成的。
连通分量,
– 如果一个无向图中任意一个顶点到其他任意顶点都至少存在一条路径，则称此无向图为连通的。
– 无向图的最大连通子图称为连通分量
顶点 0,1,2,3和顶点 4构成一个连通分量。顶点 5和顶点 6构成第二个连通分量。顶点
7单独构成第三个连通分量图的表示图有两种常用的表示方法：
相邻矩阵表示法：
– 图的相邻矩阵是一个 |V|× |V|数组。假设 |V|=n，各顶点依次记为 v0,v1,…,vn-1，则相邻矩阵的第 i行包括所有以 vi 为起点的边。如果从 vi 到 vj 存在一条边，
则对第 i行的第 j个元素进行标记，否则不做标记。
邻接表表示法：
– 邻接表是一个以链表为元素的数组。该数组包含 |V|
个元素，其中第 i个元素存储的是一个指针，它指向顶点 vi的边构成的链表。这个链表存储由顶点 vi的邻接点。
有向图的表示无向图的表示表示法的代价相邻矩阵,
( |V|2 )
邻接表,
( |V|＋ |E| )
图的抽象数据类型
class Graph { // Graph abstract class
public:
virtual int n() =0; // # of vertices
virtual int e() =0; // # of edges
// Return index of first,next neighbor
virtual int first(int) =0;
virtual int next(int,int) =0;
// Store new edge
virtual void setEdge(int,int,int) =0;
// Delete edge defined by two vertices
virtual void delEdge(int,int) =0;
// Weight of edge connecting two vertices
virtual int weight(int,int) =0;
virtual int getMark(int) =0;
virtual void setMark(int,int) =0;
};
图的周游有的应用需要对图中每个结点恰好访问一次,
有的应用需要基于图的拓扑结构，以特定的顺序依次访问图中各个结点,
如,
– 人工智能领域的搜索问题
– 最短路径问题图的周游 (2)
为确保访问所有顶点必须避免,
– 在非连通图中，从起点出发可能到达不了所有其他顶点
– 因有些图存在回路而陷入死循环采取为图的每个顶点保留一个标志位的方法
void graphTraverse(const Graph* G) {
for (v=0; v<G->n(); v++)
G->setMark(v,UNVISITED); // Initialize
for (v=0; v<G->n(); v++)
if (G->getMark(v) == UNVISITED)
doTraverse(G,v);
}
深度优先搜索 (1)
// Depth first search
void DFS(Graph* G,int v) {
PreVisit(G,v); // Take action
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
DFS(G,w);
PostVisit(G,v); // Take action
}
深度优先搜索 (2)
Cost,?(|V| + |E|).
广度优先搜索 (1)
除了用队列代替递归栈外，广度优先搜索的 实现与深度优先搜索相似,
– 在进一步访问其它顶点前，检查起点的所有邻接点,
– 如果图是一个树结构，而且以树的根结点为起点，广度优先搜索将由顶层至底层逐层地对各个结点进行访问广度优先搜索 (2)
void BFS(Graph* G,int start,Queue<int>*Q) {
int v,w;
Q->enqueue(start); // Initialize Q
G->setMark(start,VISITED);
while (Q->length() != 0) { // Process Q
Q->dequeue(v);
PreVisit(G,v); // Take action
for(w=G->first(v);w<G->n();w=G->next(v,w))
if (G->getMark(w) == UNVISITED) {
G->setMark(w,VISITED);
Q->enqueue(w);
}
}
}
广度优先搜索 (3)
拓扑排序需要为一组任务安排进度（安排课程、建筑任务等），只有一项任务的先决条件任务被完成后才能开始这项任务。我们希望以某种线性顺序组织这些任务，以便在能满足先决条件的情况下逐个完成各项任务,
可以用一个有向无环图（ DAG）来为此问题建模。
将一个 DAG中所有顶点在不违反先决条件规定的基础上排成线性序列的过程称为 拓扑排序拓扑排序,AOV网在实际工作中，经常用有向图来表示工程的施工流程图或产品生产的流程图。一个工程一般可分为若干子工程，我们把子工程称为“活动”。在有向图中若以顶点表示“活动”，用有向边表示“活动”之间的优先关系，则这样的有向图称为以顶点表示“活动”的网 (Activity On Vertex
Network)，简称 AOV网。
AOV网中的弧表示了“活动”之间的优先关系，也可以说是一种制约关系。
教学活动的例子（ 1）
计算机专业学生必须学完一系列规定的课程后才能毕业。这可看作一个工程，图中所示的 AOV
网中的顶点表示各门课程的教学活动，有向边表示各门课程的制约关系。如图中有一条弧 <c3,c9>，
其中 c3和 c9分别表示“普通物理”和“计算机组成原理”的教学活动，这说明“普通物理”是“计算机组成原理”的直接前驱，“普通物理”教学活动一定要安排在“计算组成原理”教学活动之前。
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
教学活动的例子（ 2）
课程代号?课程名称 先行课程
c1 高等数学 无
c2 工程数学 c1
c3 普通物理 c1
c4 程序设计基础 无
c5 C语言程序设计 c1 c2 c4
c6 离散数学 c1
c7 数据结构 c4 c5 c6
c8 编译方法 c5 c7
c9 计算机组成原理 c3
c10 操作系统 c7 c9
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
教学活动的例子（ 3）
图中顶点 c1,c4是顶点 c5的直接前驱；顶点 c7是顶点 c4，
c5,c6的直接后继；顶点 c1是顶点 c9的前驱，但不是直接前驱。显然，在 AOV网中，由弧表示的优先关系有传递性，
如顶点 c1是 c3的前驱，而 c3是 c9的前驱，则 c1也是 c9的前驱。在 AOV网中不能出现有向回路，如果存在回路，则说明某个“活动”能否进行要以自身任务的完成作为先决条件，显然，这样的工程是无法完成的。如果要检测一个工程是否可行，首先就得检查对应的 AOV网是否存在回路。
检查 AOV网中是否存在回路的方法就是拓扑排序。
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
教学活动的例子（ 4）
某个 AOV网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各子工程可按拓扑有序序列的次序进行安排。一个 AOV网的拓扑有序序列并不是惟一的，例如，下面的两个序列都是图示 AOV网的拓扑有序序列。
– c1 c4 c3 c2 c5 c6 c9 c7 c8 c10
– c4 c1 c2 c3 c9 c6 c5 c7 c8 c10
c
3
c
2
c
6
c
9
c
1
c
8
c
7
c
4
c
10
c
5
拓扑排序 (2)
对 AOV网进行拓扑排序的步骤是,
– 在网中选择一个没有前驱的顶点且输出之。
– 在网中删去该顶点，并且删去从该顶点发出的全部有向边。
– 重复上述两步，直到网中不存在没有前驱的顶点为止。
这样操作结果有两种：一种是网中全部顶点均被输出，说明网中不存在有向回路；另一种是网中顶点未被全部输出，剩余的顶点均有前驱顶点，
说明网中存在有向回路。
拓扑排序的方法很多，主要有两种
– 深度优先搜索排序（基于递归、栈）
– 广度优先搜索排序（基于队列）
基于深度优先搜索的拓扑排序
void topsort(Graph* G) { // Topological sort
int i;
for (i=0; i<G->n(); i++) // Initialize
G->setMark(i,UNVISITED);
for (i=0; i<G->n(); i++) // Do vertices
if (G->getMark(i) == UNVISITED)
tophelp(G,i); // Call helper
}
void tophelp(Graph* G,int v) { // Process v
G->setMark(v,VISITED);
for (int w=G->first(v); w<G->n();
w = G->next(v,w))
if (G->getMark(w) == UNVISITED)
tophelp(G,w);
printout(v); // PostVisit for Vertex v
}
基于队列的拓扑排序
void topsort(Graph* G,Queue<int>* Q) {int Count[G->n()];
int v,w;for (v=0; v<G->n(); v++) Count[v] = 0;
for (v=0; v<G->n(); v++) // Process edgesfor (w=G->first(v); w<G->n();
w = G->next(v,w))Count[w]++; // Add to v2's count
for (v=0; v<G->n(); v++) // Initialize Qif (Count[v] == 0) // No prereqs
Q->enqueue(v);while (Q->length() != 0) {
Q->dequeue(v);printout(v); // PreVisit for V
for (w=G->first(v); w<G->n();w = G->next(v,w)) {
Count[w]--; // One less prereqif (Count[w] == 0) // Now free
Q->enqueue(w);}}}
拓扑排序 (3)
深度优先,J1,J3,J2,J6,J4,J5,J7
基于队列,J1,J2,J3,J6,J4,J5,J7
拓扑排序 (4)
求所有可能的拓扑有序序列
–深度优先：
–基于队列：
1
5
32
6
4
最短路径问题输入,在每条边上标记有数值（权或代价）的有向图,
输出,形成最短路径的边的序列,
问题示例,
– 找出给定两个顶点间的最短路径
– 找出给定顶点 S到其它所有顶点间的最短路径
– 找出所有顶点互相之间的最短路径计算路径长度,
最短路径的定义定义 d(A,B) 表示从顶点 A 到顶点 B的最短路径长度,
w(A,B) 为连接顶点 A 与 B的边的权,
– 如果顶点 A 与 B 之间没有边相连，则 w(A,B) =
.
最短路径问题的算法
单源最短路径,Dijstra算法
– 指的是对已知图 G=（ V,E），给定源顶点
s∈ V，找出 s到图中其它各顶点的最短路径。
每对顶点间的最短路径,Floyd算法
– 指的是对已知图 G=（ V,E），任意的顶点
Vi,Vj∈ V，找出从 Vi到 Vj的最短路径单源最短路径在图 G中给定顶点 s,找出 s到 G中其它所有顶点的最短路径,
方法 1,用固定的顺序对顶点进行处理,计算出当前所有顶点间的最短距离,然后将其加入到下一个顶点 x的最短路径值中,
可能的问题,已经处理的到某个顶点的最短路径可能经过顶点 x.
解决办法,从以 s 出发所到达点的距离（递增）为顺序，对各个顶点进行处理,
单源最短路径图例求上图中顶点 A到其它各顶点的最短路径
A
EC
B10
3
D
2
20
5
11
15
Dijstra算法基本思想
把图中所有顶点分成两组
– 第一组包括已确定最短路径的顶点
– 第二组包括尚未确定最短路径的顶点；
按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去
– 直至从 s出发可以到达的所有顶点都包括进第一组中。
在这个过程中，总保持从 s到第一组各顶点的最短路径长度都不大于从 s到第二组的任何顶点的最短路径长度，而且，每个顶点都对应一个距离值：
– 第一组的顶点对应的距离值就是从 s到该顶点的最短路径长度
– 第二组的顶点对应的距离值是从 s到该顶点的只包括第一组的顶点为中间顶点的最短路径长度
Dijkstra算法的具体做法
一开始第一组只包括顶点 s，第二组包括其它所有顶点；
s对应的距离值为 0，而第二组的顶点对应的距离值这样确定：
– 若图中有边 <s,Vi>或者（ s,Vi），则 Vi的距离值为此边所带的权，
否则 Vi的距离值为 ∞。
然后，每次从第二组的顶点中选一个其距离值为最小的顶点
Vm加入到第一组中；
每往第一组加入一个顶点 Vm，就要对第二组的各顶点的距离值进行一次修正：
– 若加进 Vm做中间顶点，使从 s到 Vi的最短路径比不加 Vm的为短，则需要修改 Vi的距离值。
修改后再选距离值最小的顶点加入到第一组中
……
如此进行下去，直到图的所有顶点都包括在第一组中或者再也没有可加入到第一组的顶点存在。
单源最短路径运算示意求上图中顶点 A到其它各顶点的最短路径
A
EC
B10
3
D
2
20
5
11
15
Dijkstra算法示例
A B C D E
初始状态 0
处理 A 0 10 3 20?
处理 C 0 5 3 20 18
处理 B 0 5 3 10 18
处理 D 0 5 3 10 18
处理 E 0 5 3 10 18
Dijkstra算法实现
// Compute shortest path distances from s,
// return them in D
void Dijkstra(Graph* G,int* D,int s) {
int i,v,w;
for (i=0; i<G->n(); i++) { // Do vertices
v = minVertex(G,D);
if (D[v] == INFINITY) return;
G->setMark(v,VISITED);
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > (D[v] + G->weight(v,w)))
D[w] = D[v] + G->weight(v,w);
}
}
minVertex实现问题,如何确定下一个最近的顶点? (即,如何实现 minVertex)
方法 1,搜索整个表中当前距离,
– 代价,?(|V|2 + |E|) =?(|V|2).
方法 2,将未被处理的顶点按照 D值大小的顺序保存在一个最小堆中,
– 代价,
((|V| + |E|)log|V|)
((|V| + |E|)log|E|)（最差情况下）
方法 1
// Find min cost vertex
int minVertex(Graph* G,int* D) {
int i,v;
// Set v to an unvisited vertex
for (i=0; i<G->n(); i++)
if (G->getMark(i) == UNVISITED)
{ v = i; break; }
// Now find smallest D value
for (i++; i<G->n(); i++)
if ((G->getMark(i) == UNVISITED)
&& (D[i] < D[v]))
v = i;
return v;
}
方法 2
void Dijkstra(Graph* G,int* D,int s) {
int i,v,w; // v is current vertexDijkElem temp;
DijkElem E[G->e()]; // Heap array temp.distance = 0; temp.vertex = s;
E[0] = temp; // Initialize heap arrayminheap<DijkElem,DDComp> H(E,1,G->e());
for (i=0; i<G->n(); i++) {// Get distances
do { if(!H.removemin(temp)) return;
v = temp.vertex;} while (G->getMark(v) == VISITED);
G->setMark(v,VISITED);if (D[v] == INFINITY) return;
for(w=G->first(v); w<G->n(); w=G->next(v,w))if (D[w] > (D[v] + G->weight(v,w)))
{D[w] = D[v] + G->weight(v,w);
temp.distance = D[w]; temp.vertex = w;H.insert(temp); // Insert in heap
}}
}
每对顶点之间的最短路径对于任意的顶点 u,v? V,计算 d(u,v)的值,
第一种方法可以使用 |V|次 Dijkstra算法,
第二种称为 Floyd算法，效率更高,
定义 k-path 是任意一条从 u 到 v 的、中间顶点序号都小于 k的路径,
Floyd算法思想（ 1）
假设用相邻矩阵 adj表示图
Floyd算法递推地产生一个矩阵序列 adj(0)，
adj(1),…,adj(k),…,adj(n)
adj(k)[i,j]等于从顶点 Vi到顶点 Vj中间顶点序号不大于 k的最短路径长度
Floyd算法思想（ 2）
假设已求得矩阵 adj(k-1)，那么从顶点 Vi到顶点 Vj中间顶点的序号不大于 k的最短路径有两种情况：
– 一种是中间不经过顶点 Vk，那么就有
adj(k)[i,j]=adj(k-1)[i,j]
– 另一种是中间经过顶点 Vk，那么
adj(k)[i,j]<adj(k-1)[i,j]
且 adj(k)[i,j]= adj(k-1)[i,k]+ adj(k-1)[k,j]
Floyd算法图示
Floyd算法
//Floyd's all-pairs shortest paths algorithm
void Floyd(Graph* G) {
int D[G->n()][G->n()]; // Store distances
for (int i=0; i<G->n(); i++) // Initialize
for (int j=0; j<G->n(); j++)
D[i][j] = G->weight(i,j);
// Compute all k paths
for (int k=0; k<G->n(); k++)
for (int i=0; i<G->n(); i++)
for (int j=0; j<G->n(); j++)
if (D[i][j] > (D[i][k] + D[k][j]))
D[i][j] = D[i][k] + D[k][j];
}
最小支撑树最小支撑树 (MST) 问题,
输入,一个连通无向图 G.
输出,图 G的一个子图，满足
1) 子图中所有边的权之和是所有子图中最小的
2) 子图是连通的,
最小支撑树 MST举例
Prim算法实现
与 Dijkstra算法相似，主要区别在于不是寻找下一个离起点最近的顶点，而是下一个与 MST中某个顶点距离最近的顶点；
具体操作是：
– 从图中任意一个顶点开始，首先把这个顶点包括在 MST里，
– 然后在那些其一个端点已在 MST里，另一个端点还不是
MST里的边，找权最小的一条边，并把这条边和其不在
MST里的那个端点包括进 MST里。
– 如此进行下去，每次往 MST里加一个顶点和一条权最小的边，直到把所有的顶点都包括进 MST里。
与 Dijkstra算法相似，可以用优先队列来寻找下一个顶点
运行时间类似于相应的 Dijkstra算法,
最小支撑树的 Prim算法
void Prim(Graph* G,int* D,int s) {
int V[G->n()]; // Who's closest
int i,w;
for (i=0; i<G->n(); i++) {// Do vertices
int v = minVertex(G,D);
G->setMark(v,VISITED);
if (v != s) AddEdgetoMST(V[v],v);
if (D[v] == INFINITY) return;
for (w=G->first(v); w<G->n();
w = G->next(v,w))
if (D[w] > G->weight(v,w)) {
D[w] = G->weight(v,w);// Update dist
V[w] = v; // Update who it came from
}
}
}
证明用 Prim算法构造的是 MST
首先证明这样一个结论（ MST性质）：
– 设 T(V*,E*)是连通无向图 G=(V,E)的一棵正在构造的生成树，又 E中有边 e=(Vx,Vy)，
其中 Vx∈ V*,Vy不属于 V*，且 e的权 W(e)是所有一个端点在 V*里，另一端不在 V*里的边的权中最小者，则一定存在 G的一棵包括 T的
MST包括边 e=( Vx,Vy)。
证明用 Prim算法构造的是 MST
反证法证明 MST性质
– 设 G的任何一棵包括 T的 MST都不包括 e=( Vx,Vy)，且设
T’是一棵这样的 MST
– 由于 T’是连通的，因此有从 Vx到 Vy的路径 Vx,…,Vy把边 e=( Vx,Vy)加进树 T’，得到一个回路 Vx,…,Vy,Vx
– 上述路径 Vx,…,Vy中必有边 e’=( Vp,Vq)，其中 Vp∈ V*，
Vq不属于 V*，由条件知边的权 W(e’)≥W(e)，从回路中去掉边 e’，回路打开，成为另一棵生成树 T”,T”包括边
e=( Vx,Vy)，且各边权的总和不大于 T’各边权的总和
– 因此 T”是一棵包括边 e的 MST，与假设矛盾，即证明了我们的结论。
– 也证明了 Prim算法构造 MST的方法是正确的，因为我们是从 T包括任意一个顶点和 0条边开始，每一步加进去的都是 MST中应包括的边，直至最后得到 MST。
Kruskal最小支撑树算法 (1)
初始化为 |V|个等价类,每个顶点自成一个等价类 MST.
合并具有最短的边相连的 MST.
– 通过使用最小值堆来实现按照权的顺序来处理每条边,
怎样确定两个顶点是否属于同一等价类?
– 使用基于父指针表示法的 UNION/FIND 算法,
Kruskal算法的基本思想
对于图 G=（ V,E），开始时，将顶点集分为 |V|个等价类，每个等价类包括一个顶点；
然后，以权的大小从小到大为顺序处理各条边，如果某条边连接两个不同等价类的顶点，
则这条边被添加到 MST，两个等价类被合并为一个；
反复执行此过程，直到只剩下一个等价类。
Kruskal最小支撑树算法 (2)
Kruskal最小支撑树算法 (3)
算法代价取决于按权处理每条边所需的时间确定,
– 当所有顶点都合并到一个等价类时可以结束处理总的代价,
– 使用了路径压缩,differ和 UNION函数几乎是常数
– 最差,?(|E| log |E|)
假设可能对几乎所有边都判断过了，则最坏情况下算法时间代价为 Θ（ |E|log |E|)，即堆排序的时间
– 平均,?(|V| log |E|)
通常情况下只找了接近顶点数目那么多边的情况下，
MST就已经生成，时间代价接近于 Θ（ |V|log |E|)
广义表 (1)
回顾线性表
– 由 n（ n≥0）个数据元素组成的有限有序序列
– 线性表的每个元素都具有相同的数据类型，
通常为同一某种类型的数据记录
如果一个线性表中还包括一个或者多个子表，那就称之为广义表（ Generalized
Lists，也称 Multi-list）一般记作：
– L＝（ x0,x1,…,xi,…,xn-1）
广义表 (2)
L＝（ x0,x1,…,xi,…,xn-1）
– L是广义表的名称
– n为长度
– 每个 xi（ 0≤i≤n-1）是 L的成员
可以是单个元素，即原子（也称“单元素”，
atom )
也可以是一个广义表，即子表（ sublist）
– 广义表的深度：表中元素都化解为原子后的括号层数广义表的各种类型（ 1）
纯表（ pure list）
– 从根结点到任何叶结点只有一条路径
– 也就是说任何一个元素（原子、子表）只能在广义表中出现一次广义表的各种类型（ 2）
可重入表 ( reentrant list )
– 图示对应于一个 DAG
– 其元素 (包括原子和子表 )可能会在表中多次出现
但不会出现回路
对子表和原子标号广义表的各种类型（ 3）
循环表 ( cyclic list,递归表 )的图示对应于任何有向图
– 有向图中可能包含回路
– 循环表的深度为无穷大广义表的各种类型（ 4）
广义表的 head和 tail
当广义表非空时：
– 称第一个元素为 表头
– 称其余元素组成的表为 表尾广义表的操作（ 1）
利用广义表的 head和 tail操作写出函数表达式，把以下各题中的单元素 banana从广义表中分离出来：
(1) L1(apple,pear,banana,orange)
Head (Tail (Tail (L1) ) )
(2) L2((apple,pear),(banana,orange))
Head (Head (Tail (L2) ) )
(3) L3(((apple),(pear),(banana),(orange)))
Head (Head (Tail (Tail (Head (L3) ) ) ) )
广义表的操作（ 2）
(4) L4((((apple))),((pear)),(banana),orange)
Head (Head (Tail (Tail (L4) ) ) )
(5) L5((((apple),pear),banana),orange)
Head (Tail (Head(L5) ) )
L6(apple,(pear,(banana),orange))
(6) Head (Head (Tail (Head (Tail (L6) ) ) ) )
平衡的二叉搜索树 (AVL)
BST受输入顺序影响
– 最好 O(log n)
– 最坏 O(n)
怎样使得 BST始终保持 O(log n)级的平衡状态？
Adelson-Velskii和 Landis发明了 AVL树
– 一种平衡的二叉搜索树
– 任何结点的左子树和右子树高度最多相差 1
AVL树的性质
可以为空
具有 n个结点的 AVL树，高度为 O(log n)
如果 T是一棵 AVL树
– 那么它的左右子树 TL,TR也是 AVL树
– 并且 | hL-hR|≤1
hL,hR 是它的左右子树的高度平衡因子
平衡因子，用 bf(x)来表示结点 x的平衡因子。它被定义为：
– bf(x)= x的右子树的高度 – x的左子树的高度
对于一个 AVL树中的结点平衡因子只可能取值为
0,1和 -1
AVL树结点的插入
插入与 BST一样
– 新结点作叶结点
需要调整
相应子树的根结点变化大致有三类
– 结点原来是平衡的，现在成为左重或右重的
修改相应前驱结点的平衡因子
– 结点原来是某一边重的，而现在成为平衡的了
树的高度未变，不修改
– 结点原来就是左重或右重的，而新结点又加到重的一边
不平衡
,危急结点”
恢复平衡不平衡的情况
正常情况下，一个结点 A的平衡因子只能是
0,1,-1，而在非正常情况有下面四种可能
– LL型：导致不平衡的结点为 A的左子树的左结点，这时 A的平衡因子为 -2
– LR型：导致不平衡的结点为 A的左子树的右结点，这时 A的平衡因子为 -2
– RL型：导致不平衡的结点为 A的右子树的左结点，这时 A的平衡因子为 2
– RR型：导致不平衡的结点为 A的右子树的右结点，这时 A的平衡因子为 2
不平衡的图示不平衡情况总结
LL型和 RR型是对称的,LR型和 RL型是对称的
不平衡的结点一定在根结点与新加入结点之间的路径上
它的平衡因子只能是 2或者 -2
– 如果是 2，它在插入前的平衡因子是 1
– 如果是 -2，它在插入前的平衡因子是 -1
解决不平衡的方法 ——旋转
我们可以使用一系列称为旋转 ( rotation )的局部操作解决这个问题
– LL和 RR的情况可以通过单旋转 ( single rotation )来解决
– RL和 LR的情况可以通过双旋转 ( double rotation )来解决
调整的整个过程称之为重构（ restructuring）
单旋转
如果加入一个新结点后需要对根为结点 a
的子树进行单旋转，假设 b为包含新加入结点的 a的子女,c为包含新加入结点的 b
的子女
单旋转，那么令 b代替 a成为新根,a和 c作为其子结点；原来 c的子树保持不变；原来 b中 c结点的兄弟子树，代替原 b子树作为 a的子树单旋转示意图（ LL型）
单旋转示意图（ RR型双旋转
RL或者 LR需要进行双旋转
– 这两种情况是对称的
我们只讨论 RL的情况
– LR是一样的
RL型双旋转第一步
RL型双旋转第二步旋转运算的实质（ 1）
以 RR型图示为例，总共有 7个部分
– 三个结点,a,b,c
– 四棵子树
a的左子树 T0
b的左子树 T1
c的左子树 T2 和右子树 T3
– 加重的是 c为根的子树，但是其结构其实没有变化
– 因此，可以整体地看作 b的右子树
目的：重新组成一个新的 AVL结构
– 平衡
– 保留了中序周游的性质
T0 a T1 b T2 c T3
旋转运算的实质（ 2）
把树做任何一种旋转（ RR,RL,LL、
LR）
– 新树保持了原来的中序周游顺序
– 旋转处理中仅需改变少数指针
– 而且新的子树高度为 h+2，保持插入前子树的高度不变
– 原来二叉树在 a结点上面的其余部分（若还有的话）总是保持平衡的
