平衡二叉树 (Balanced binary tree)

形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ，其严格定义是：
　　一棵空树是平衡二叉树；若 T 是一棵非空二叉树，其左、右子树为 TL 和 TR ，令 hl 和 hr 分别为左、右子树的深度。当且仅当
　　　①TL 、 TR 都是平衡二叉树；
　　　② ｜ hl － hr ｜≤ 1；
时，则 T 是平衡二叉树。
【例】如图 8.4 所示。
         
             （a）平衡二叉树           （b）非平衡二叉树
                      图8.3 平衡二叉树与非平衡二叉树
相应地定义 hl － hr 为二叉平衡树的平衡因子 (balance factor) 。因此，平衡二叉树上所有结点的平衡因子可能是 -1 ， 0 ， 1 。换言之，若一棵二叉树上任一结点的平衡因子的绝对值都不大于 1 ，则该树是就平衡二叉树。
动态平衡技术
1.动态平衡技术
Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：
　　在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树。
2.最小不平衡子树
　　以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为 A ，则调整该子树的规律可归纳为下列四种情况：
（1） LL 型：
　　新结点 X 插在 A 的左孩子的左子树里。调整方法见图 8.5(a) 。图中以 B 为轴心，将 A 结点从 B 的右上方转到 B 的右下侧，使 A 成为 B 的右孩子。
      
          图8.5 平衡调整的4种基本类型（结点旁的数字是平衡因子）
（2）RR 型：
　　新结点 X 插在 A 的右孩子的右子树里。调整方法见图 8.5(b) 。图中以 B 为轴心，将 A 结点从 B 的左上方转到 B 的左下侧，使 A 成为 B 的左孩子。
（3）LR 型：
　　新结点 X 插在 A 的左孩子的右子树里。调整方法见图 8.5(c) 。分为两步进行：第一步以 X 为轴心，将 B 从 X 的左上方转到 X 的左下侧，使 B 成为 X 的左孩子， X 成为 A 的左孩子。第二步跟 LL 型一样处理 ( 应以 X 为轴心 ) 。
（4）RL 型：
　　新结点 X 插在 A 的右孩子的左子树里。调整方法见图 8.5(d) 。分为两步进行：第一步以 X 为轴心，将 B 从 X 的右上方转到 X 的右下侧，使 B 成为 X 的右孩子， X 成为 A 的右孩子。第二步跟 RR 型一样处理 ( 应以 X 为轴心 ) 。
【例】
实际的插入情况，可能比图 8.5 要复杂。因为 A 、 B 结点可能还会有子树。现举一例说明，设一组记录的关键字按以下次序进行插入： 4 、 5 、 7 ， 2 、 1 、 3 、 6 ，其生成及调整成二叉平衡树的过程示于图 8.6 。
　　在图 8.6 中，当插入关键字为 3 的结点后，由于离结点 3 最近的平衡因子为 2 的祖先是根结点 5 。所以，第一次旋转应以结点 4 为轴心，把结点 2 从结点 4 的左上方转到左下侧，从而结点 5 的左孩子是结点 4 ，结点 4 的左孩子是结点 2 ，原结点 4 的左孩子变成了结点 2 的右孩子。第二步再以结点 4 为轴心，按 LL 类型进行转换。这种插入与调整平衡的方法可以编成算法和程序，这里就不再讨论了。

         图 8.6 二叉平衡树插入结点 ( 结点旁的数字为其平衡因子 )

posted @ 2012-08-17 14:42 章涛 阅读(428) | 评论 (0) | 编辑 收藏

指向函数的指针

　　可以用指针变量指向整形变量、字符串、数组、结构体、也可以指向一个函数。一个函数在编译时被分配一个入口地址。这个入口地址就称为函数指针。可以用一个指针变量指向函数，然后通过该指针变量调用此函数。用简单的数值比较为例：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4  int main()
 5 {
 6     int max(int,int);
 7     int (*p)(int,int);
 8     int a,b,c;
 9     p = max;
10     scanf("%d,%d",&a,&b);
11     c = (*p)(a,b);
12     printf("a=%d,b=%d,max=%d\n",a,b,c);
13     return 0;
14 }
15 
16 int max(int x,int y)
17 {
18     int z;
19     if(x>y) z = x;
20     else z = y;
21     return(z);
22 }

　　main函数中的" c = max(a,b); " 包括了一次函数的调用。每一个函数都占用一段内存单元。因此，可以用一个指针变量指向一个函数，通过指针变量来访问它指向的函数。

　　第7行：int （*p）( int,int );  用来定义 p 是一个指向函数的指针变量，该函数有两个整形参数，函数值为整形。注意 *p 两侧的括号不可省略，表示 p 先与 * 结合，是指针变量，然后再与后面的 ( ) 结合，表示此指针变量指向函数，这个函数值 (即函数的返回值) 是整形的。如果写成 int *p ( int,int ) ,由于( )的优先级高于 *，它就成了声明一个函数P( 这个函数的返回值是指向整形变量的指针)。

　　赋值语句 p = max ; 作用是将函数 max 的入口地址赋给指针变量p。和数组名代表数组首元素地址类似，函数名代表该函数的入口地址。这时 p 就是指向函数 max 的指针变量，此时 p 和 max都指向函数开头，调用 *p 就是调用 max 函数。但是p作为指向函数的指针变量，它只能指向函数入口处而不可能指向函数中间的某一处指令处，因此不能用 *(p + 1)来表示指向下一条指令。

　　注意:

　　(1) 指向函数的指针变量的一般定义形式为：

　　数据类型 （*指针变量名）（函数参数列表）

　　这里数据类型就是函数返回值的类型

　　(2) int (* p) ( int,int ); 它只是定义一个指向函数的指针变量 p, 它不是固定指向哪一个函数的，而只是表示定义这样一个类型的变量，它是专门用来存放函数的入口地址的。在程序中把哪一函数(该函数的值应该是整形的，且有两个整形参数)的地址赋给它，他就指向哪一个函数。在一个函数中，一个函数指针变量可以先后指向同类型的不同函数。

　　(3) p = max; 在给函数指针变量赋值时，只需给出函数名而不必给出函数参数，因为是将函数的入口地址赋给 p ，而不涉及 实参和形参的结合问题，不能写成 p = max(a,b);

　　(4) c = (*p)(a,b) 在函数调用时，只需将( *p ) 代替函数名即可，后面实参依旧。

　　(5) 对于指向函数的指针变量，像 p++ ,p+n.....是无意义的。

　　(二) 用指向函数的指针作为函数参数

　　函数指针变量通常的用途之一就是把指针作为参数传递到其他函数。

　　函数的参数可以是变量、指向变量的指针变量、数组名、指向数组的指针变量，也可以是指向函数的指针也可以作为参数，以实现函数地址的传递，这样就能够在被调用的函数中使用实参函数。

　　void  sub ( int ( *x1) (int), int (*x2) (int,int) )

　　　　{

　　　　　　int a,b,i,j;

　　　　　　a = (*x1)(i);　　　　　 /* 调用 f1 函数 */

　　　　　　b = (*x2)(i)(j);　　　　/* 调用 f2 函数 */

　　　　}

　　如果实参为两个 函数名 f1 和 f2. 在函数首部定义x1、x2为函数指针变量，x1指向的函数有一个整形形参，x2指向的函数有两个形参。i 和 j 是函数f1 和 f2所要的参数。函数sub的形参 x1、x2(指针变量)在函数 sub 未被调用时并不占用内存单元，也不指向任何函数。在sub被调用时，把实参函数 f1 和 f2的入口地址传给形式指针变量 x1 和 x2.

　　既然在 sub 函数中要调用 f1 和 f2 函数，为什么不直接调用f1 和 f2而要用函数指针变量呢? 确实，如果只是用到f1 和 f2 函数，完全可以在sub函数中直接调用f1 和 f2,而不必设指针变量 x1 和 x2。 但是,如果在每次调用sub时，调用的函数不是固定的，下次是f3 和 f4，再是f5 和 f6...这时用指针变量就比较方便了。

我们在类里面会定义成员函数，同时我们也希望定义成员函数指针。因此需要解决3个问题，第一怎么定义类的函数指针，第二赋值，第三使用。
我定义一个类，

我现在想要定义一个指针，指向A类型中返回值为int，参数为两个int的函数指针。熟悉C的同学马上会写出typedef int (*oper)(int,int)。但是这个用到C++里就有问题了，
因为我们知道，类的非static成员方法实际上还有this指针的参数。比如add方法，它实际的定义可能会这样int add(A* this,int a,int b);因此，我们不能简单把C语言里的那套东西搬过来，我们需要重新定义这种类型的指针。正确做法是加上类型，typedef int (A::*Action)(int,int)

上面这种方式是针对非static成员函数的，那么static成员函数的函数指针应该怎么定义呢，还能用上面这种方式吗？我们知道static成员函数是没有this指针的，所以不会加上的类的限定，它的函数指针定义方式和C里面的函数指针定义方式一样的。

总结起来，非static成员函数的函数指针需要加上类名，而static的成员函数的函数指针和普通的函数指针一样，没有什么区别。
另外注意一点的是
如果函数指针定义在类中，调用的时候有点区别。

posted @ 2012-08-15 15:42 章涛 阅读(346) | 评论 (0) | 编辑 收藏

关于set中存放的元素的排列顺序

posted @ 2012-08-13 13:37 章涛 阅读(1813) | 评论 (0) | 编辑 收藏

map类型.

2。map简介

map是一类关联式容器，它是模板类。关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置类获取。它的特点是增加和删除节点对迭代器的影响很小，除了操作节点，对其他的节点都没有什么影响。对于迭代器来说，不可以修改键值，只能修改其对应的实值。

3。map的功能

1. 自动建立Key － value的对应。key 和 value可以是任意你需要的类型，但是需要注意的是对于key的类型，唯一的约束就是必须支持<操作符。
2. 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。
3. 快速插入Key - Value 记录。
4. 快速删除记录
5. 根据Key 修改value记录。
6. 遍历所有记录。

4。map的定义

使用map得包含map类所在的头文件：#include <map> //注意，STL头文件没有扩展名.h

map对象是模板类，需要关键字和存储对象两个模板参数，基本的定义模式如下：

std:map<int, string> personnel;

这样就定义了一个以int为键，值为string的map对象personnel。

map中定义了以下三个类型：

• map<K, V>::key_type : 表示map容器中，索引的类型；
• map<K, V>::mapped_type : 表示map容器中，键所关联的值的类型；
• map<K, V>::value_type : 表示一个pair类型，它的first元素具有const map<K, V>::key_type类型，而second元素则有map<K, V>::mapped_type类型

对迭代器进行解引用时，将获得一个引用，指向容器中一个value_type类型的值，对于map容器，其value_type是pair类型。

为了使用方便，可以对模板类进行一下类型定义，

typedef map<int, CString> UDT_MAP_INT_CSTRING; 
UDT_MAP_INT_CSTRING enumMap;

5。在map中添加元素

给map中添加元素主要有两种方法：

•   使用下标操作符获取元素，然后给元素赋值

          For example:

          map<string, int> word_count; // 定义了一个空的map对象word_count;

          word_count["Anna"] = 1;

          程序说明：

          1.在word_count中查找键为Anna的元素，没有找到.

          2.将一个新的键-值对插入到word_count中，他的键是const string类型的对象，保存Anna。而他的值则采用直初始化，这就意味着在本例中指为0.

          3.将这个新的键-值对插入到word_count中

          4.读取新插入的元素，并将她的值赋为1.

          使用下标访问map与使用下标访问数组或者vector的行为是截然不同的：使用下标访问不存在的元素将导致在map容器中添加一个新的元素，他的键即为该下标值。

• 使用map::insert方法添加元素

          map容器提供的insert操作：

          1. map.insert(e) : e是一个用在map中的value_type类型的值。如果键不存在，则插入一个值为e.second的新元素；如果键在map中已经存在，那么不进行任何操作。该函数返回一个pair类型，该pair类型的first元素为当前插入e的map迭代器，pair的second类型是一个bool类型，表示是否插入了该元素。

          2. map.insert(beg, end) : beg和end是迭代器，返回void类型

          3. map.insert(iter, e) : e是value_type类型的值，如果e.first不在map中，则创建新元素，并以迭代器iter为起点搜索新元素存储的位置，返回一个迭代器，指向map中具有给定键的元素。

          For example:

          word_count.insert(map<sting, int>::value_type("Anna", 1));

          word_count.insert(make_pair("Anna", 1)); 

          返回值：如果该键已在容器中，则其关联的值保持不变，返回的bool值为true。

6。查找并获取map中的元素

使用下标获取元素存在一个很危险的副作用：如果该键不在map容器中，那么下标操作会插入一个具有该键的新元素。

因此引入map对象的查询操作：

map.count(k) : 返回map中键k的出现次数(对于map而言，由于一个key对应一个value，因此返回只有0和1，因此可以用此函数判断k是否在map中)

map.find(k) :  返回map中指向键k的迭代器，如果不存在键k，则返回超出末端迭代器。

For example:

int occurs = 0;

if( word_count.cout("foobar") )

     occurs = word_count["foobar"];

int occurs = 0;

map<string, int>::iterator it = word_count.find("foobar");

if( it != word_count.end() )

     occurs = it ->second;

7。从map中删除元素

移除某个map中某个条目用erase()

该成员方法的定义如下:

1. iterator erase(iterator it); //通过一个条目对象删除
2. iterator erase(iterator first, iterator last);        //删除一个范围
3. size_type erase(const Key& key); //通过关键字删除

8. map对象的迭代遍历

与其他容器一样，map同样提供begin和end运算，以生成用于遍历整个容器的迭代器。

posted @ 2012-08-13 10:03 章涛 阅读(422) | 评论 (0) | 编辑 收藏

float与double的范围和精度

posted @ 2012-08-10 09:05 章涛 阅读(649) | 评论 (0) | 编辑 收藏

文件结束标志符

posted @ 2012-08-09 19:38 章涛 阅读(314) | 评论 (0) | 编辑 收藏

这是一个linux常见命令的列表

posted @ 2012-08-09 17:25 章涛 阅读(206) | 评论 (0) | 编辑 收藏

一个类的对象作为另一个类的数据成员

一个类的对象作为另一个类的数据成员

posted @ 2012-08-09 15:25 章涛 阅读(4022) | 评论 (0) | 编辑 收藏

C++中string--->char[] / char[]--->string

posted @ 2012-08-09 10:12 章涛 阅读(269) | 评论 (0) | 编辑 收藏

C++数据结构之单链表

线性表包含数据域和指针域。单链表用一组地址任意的存储单元存放线性表中的数据元素。

线性表包含 数据域和指针域 其中，data存储数据本身的值，next存储后继元素的地址 下面的图表示的是一个数据节点

单链表的结构示意图（包括空的单链表）：

单链表的节点类:

　template<classT>  
classNode  
{  
public:  
T data;//数据  
Node<T> *next;//next指针  
Node()  
{  
this->next=NULL;//构造空的节点  
}  
Node(T data,Node<T> *next=NULL)//构造一个节点  
{  
this->data=data;  
this->next=next;  
}  
}; 

单链表类声明如下：

#include<iostream>  
#include "Node.h"//单链表节点类  
template<classT>  
classSinglyLinkedList //单链表类  
{  
public:  
Node<T> *head;//单链表的头指针。  
SinglyLinkedList();//构造空的单链表。  
SinglyLinkedList(T value[], intn);//构造由指定的数组提供的单链表  
~SinglyLinkedList();//析构  
boolisEmpty();//判断是否为空。  
intlength();//获取长度  
Node<T>* getNode(inti);//返回第i(i>=0)个节点指针  
T get(inti);//返回第i个元素  
boolset(inti,T x);//设置第i个元素为x  
template<classT> friend std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list);  
Node<T>* insert(inti,T x);//插入第I个节点并返回第i个节点的指针  
boolremove(inti,T& old);//删除第i个元素，将删除的元素存放到old  
voidclear();//清空单链表  
voidconcat(SinglyLinkedList<T> &list);//将List链接在当前单链表之后  
}; 

单链表部分如构造空的链表对象，析构，判断为空的实现，没有要讲的算法，实现如下：

template<classT>  
SinglyLinkedList<T>::SinglyLinkedList()//构造空的单链表  
{  
this->head=NULL;  
　}  
template<classT>  
SinglyLinkedList<T>::~SinglyLinkedList()//析构  
{  
clear();  
}  
template<classT>  
boolSinglyLinkedList<T>::isEmpty()//判断链表是否为空  
{  
returnthis->head==NULL;  
} 

单链表的遍历操作，遍历单链表是指从第一个节点开始访问，沿着节点的Next可依次访问单链表中的各个节点，并且各个节点只被访问一次。实现的单链表遍历的基本算法如下：

intj=0;  
Node<T> *p=head;  
while(p!=NULL&&j<i)  
{  
j++;  
p=p->next;  
} 

单链表的length(),get(),set(),clear()和输出等操作都基于以上算法。

template<classT>  
intSinglyLinkedList<T>::length()  
{  
　inti=0;  
Node<T> *p=head;//创建一个用于遍的变量  
while(p!=NULL)  
{  
i++;  
std::cout<<p->data;  
p=p->next;  
}  
　returni;  
}  
template<classT>  
Node<T>* SinglyLinkedList<T>::getNode(inti)  
{  
if(i<0)  
returnNULL;  
intj=0;  
Node<T> *p=head;  
while(p!=NULL&&j<i)  
{  
j++;  
p=p->next;  
}  
returnp;  
}  
template<classT>  
T SinglyLinkedList<T>::get(inti)  
{  
Node<T> *p=getNode(i);  
if(p!=NULL)  
returnp->data;  
T d;  
returnd;  
//throw "单链表为空或者参数指定的元素不存在";  
}  
template<classT>  
boolSinglyLinkedList<T>::set(inti,T x)  
{  
Node<T> *p=getNode(i);  
if(p!=NULL)  
{  
p->data=x;  
returntrue;  
}  
returnfalse;  
}  
template<classT>  
std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list)  
{  
Node<T> *p=list.head;  
out<<"(";  
while(p!=NULL)  
{  
out<<p->data;  
p=p->next;  
if(p!=NULL)  
out<<",";  
}  
out<<") ";  
returnout;  
}  
template<classT>  
voidSinglyLinkedList<T>::clear()  
{  
Node<T> *p=head;  
while(p!=NULL)  
{  
Node<T> *q=p;  
p=p->next;  
delete q;  
}  
head=NULL;  
　} 

单链表的插入操作，单链表不像顺序表，对与表的插入和删除很简单：

空表插入/头插入

Node<T> *q=NULL;  
if(head==NULL||i<0)//头插入(单链表为空或者)  
{  
q=newNode<T>(x,head);  
head=q;  
}  
中间插入/尾插入  
p->next=newNode<T>(x,p->next);  
单链表insert()以及参数构造函数：  
　template<classT>  
Node<T>* SinglyLinkedList<T>::insert(inti,T x)  
{  
Node<T> *q=NULL;  
if(head==NULL||i<0)//头插入(单链表为空或者)  
{  
q=newNode<T>(x,head);  
head=q;  
}  
else 
{  
intj=0;  
Node<T> *p=head;  
while(p->next!=NULL&&j<i-1)  
{  
j++;  
p=p->next;  
}  
q=newNode<T>(x,p->next);  
　p->next=q;  
}  
returnq;  
}  
　template<classT>  
SinglyLinkedList<T>::SinglyLinkedList(T table[],intn)  
{  
head=NULL;  
if(n>0)  
{  
head=newNode<T>(table[0]);//创建节点  
　Node<T> *rear=head;//创建一个指向头节点的指针  
inti=1;  
　while(i<n)  
{  
rear->next=newNode<T>(table[i++]);  
rear=rear->next;  
}  
}  
} 

　单链表的删除操作也分两类：

头删除

Node<T> *q=head;  
head=head->next;  
delete q; 

中间/尾删除

Node<T> *q=p->next;  
if(q!=NULL)//判断删除节点  
{  
p->next=q->next;//让删除节点的前驱Next指针下一节点  
delete q;//删除该节点  
} 

单链表的删除函数remove（）实现：

template<classT>  
boolSinglyLinkedList<T>::remove(inti,T &old)  
{  
if(i<0||head==NULL)  
{  
Node<T> *q=head;  
old=q->data;  
head=head->next;  
delete q;  
　}  
else 
{  
Node<T> *p=getNode(i-1);//获取删除节点的前驱  
　if(p!=NULL&&p->next!=NULL)//判断删除节点和删除节点是否为空  
{  
Node<T> *q=p->next;//新建一个节点指针，将删除接点复制过去  
old=q->data;  
p->next=q->next;//让删除节点的前驱Next指针下一节点  
delete q;//删除该节点  
　returntrue;  
}  
　}  
returnfalse;  
}  
单链表的链接函数：concat()  
template<classT>  
voidSinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)  
{  
if(this->head==NULL)  
{  
this->head=list->head;  
}  
else 
{  
Node<T> *p=head;  
while(p->next!=NULL)  
{  
p=p->next;  
}  
p=list->head;  
}  
list->head=NULL;//设置单链表为空，否则运行出错  
} 

以上对C++单链表的分析 添加一个学生结构和一个测试函数：

Student.h  
structStudent  
{  
charnumber[10]; //学号  
charname[20]; //姓名  
doublescore; //得分  
friend std::ostream& operator<<(std::ostream& out,Student &stu)  
{  
out<<"学号："<<stu.number<<"姓名："<<stu.name<<"得分："<<stu.score;  
returnout;  
}  
};  
主函数：  
#include<iostream>  
#include "SinglyLinkedList.h" 
#include "Student.h" 
void_TestToSinglyLinkedList()  
{  
Student data[]={{"090313018","Silvester",45.4},{"090313018","捐赠",45.4},{"090313018","版主",45.6}};  
SinglyLinkedList<Student> m(data,3);  
Student t;  
std::cout<<(m.isEmpty()?"不为空！":"该链表为空！")<<std::endl;  
std::cout<<"长度："<<m.length()<<std::endl;  
std::cout<<"移除2个学生"<<m.remove(1,t)<<std::endl;  
std::cout<<"t:"<<t<<std::endl;  
std::cout<<"2个学生信息"<<m.getNode(1)<<std::endl;  
Student s={"415646","fdsfs",453.1};  
std::cout<<m.get(1)<<m.set(1,s)<<m.insert(5,s)<<std::endl;  
}  
voidmain()  
　{  
_TestToSinglyLinkedList();  
system("pause");  
} 

提供源代码下载地址：http://39327.42la.com.cn/DataFile/Code/C++/SinglyLinkedList.zip

原文地址：http://www.cnblogs.com/Arrays/archive/2012/02/01/2335164.html

posted @ 2012-08-02 14:58 章涛 阅读(341) | 评论 (0) | 编辑 收藏