【数据结构】

双向链表的添加、查找、删除算法

前段时间看一个很早前写的驱动，发现对双向链表的操作还有BUG，删除时会蓝屏，修正了一下，把修正后的代码贴出来，方便日后使用前直接复制，大牛不用看了。?

============================================

链表(创建，插入，删除和打印输出 )

/*-----------------------------------------------------------------------------
时间:2011年9月28日
文件功能:实现了动态建立一个学生信息的链表包括链表的
创建、插入、删除、和打印输出学生信息包括姓名和分数
本链表是带有头结点的，头结点的内容为空内容
-----------------------------------------------------------------------------*/
/*-------------------------包含头文件------------------------------------*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>

/*-------------------------结构体定义部分------------------------------*/
struct?Node
{
?char?name[10];
?int?score;
?struct?Node?*next;
};

typedef?struct?Node?ListNode;
/*----------------------------函数声明部分------------------------------*/

/*---------------------------函数实现部分-------------------------------*/
/*-----------------------------创建链表---------------------------------*/
/*在链表的末端插入新的节点，建立链表*/
ListNode?*CreateList(int?n)
{
?ListNode?*head;//指向头结点指针
?ListNode?*p,*pre;
?int?i;
?head=(ListNode?*)malloc(sizeof(ListNode));//为头节点分配内存空间
?head->next=NULL;//将头结点的指针域清空
?pre=head;//先将头结点首地址赋给中间变量pre
?for(i=1;i<=n;i++)//通过for循环不断加入新的结点
??{
???printf("input?name?of?the?%d?student:",i);//打印出第几个人的名字
???p=(ListNode?*)malloc(sizeof(ListNode));//为要插入的节点分配
???//内存空间p指向新插入结点的首地址
???scanf("%s",&p->name);//输入姓名
???printf("input?score?of?the?%d?student:",i);
???scanf("%d",&p->score);//输入分数
???pre->next=p;//将p指向新结点插入链表也就是头结点指针域指向
???//下个结点
???//第一个结点就是p指向的，因为头结点内容为空
???pre=p;//这个起着指向下一个结点的作用
??}
?p->next=NULL;//最后将最后一个结点的指针域清空了
?return?head;//返回这个链表的首地址
}
/*-------------------------输出链表-----------------------------------*/
void?PrintList(ListNode?*h)
{
?ListNode?*p;
?p=h->next;
?while(p)
??{
???printf("%s,%d",p->name,p->score);
???p=p->next;
???printf("n");
??}
}
/*----------------------插入链表结点--------------------------*/
/*--------------------------------------------------------------------
函数名称:InsertList(ListNode?*h,int?i,char?name[],int?e,int?n)
函数功能:插入链表结点
入口参数:?h:?头结点地址?i:插入到第几个结点?name:插入
结点的姓名?e:插入结点的分数?n:
链表中结点的个数
除下头结点外的个数

出口参数:
--------------------------------------------------------------------*/
void?InsertList(ListNode?*h,int?n)
{
?ListNode?*q,*p;//先定义2个指向一个结点的指针
?int?j;
?if(i<1?||?i>n+1)
??printf("Error!?Please?input?again.n");
?else
??{
???j=0;
???p=h;//将指针p指向要链表的头结点
???while(j<i-1)
????{
?????p=p->next;
?????j++;
????}
???q=(ListNode?*)malloc(sizeof(ListNode));/*为要插入的
???结点分配内存空间*/
????
???//----赋值操作---------?
???strcpy(q->name,name);?//将名字拷到要插入的节点内
???q->score=e;?//将要插入的节点中分数赋值

???//调整指针域
???
???q->next?=?p->next;?/*这个是将新插入的结点指针域指向
???上一个结点指针域指向的结点地址即为p->next*/
????
???p->next=q;/*将要插入结点位置前面的结点指针域
???指向现在插入的结点首地址*/
??}
}

/*--------------------------------------------------------------------
函数名称:DeleteList(ListNode?*h,?int?i,?int?n)
函数功能:删除链表结点
入口参数:?h:?头结点地址?i:要删除的结点所在位置
n:
链表中结点的个数除下头结点外的个数

出口参数:
--------------------------------------------------------------------*/
void?DeleteList(ListNode?*h,?int?n)
{
?ListNode?*p,*q;//首先定义2个指向结点型结构体的指针
?int?j;
?char?name[10];
?int?score;
?if(i<1?||?i>n)//如果位置超出了1和n的范围的话则打印出错误信息
??printf("Error!?Please?input?again.n");
?else//没有超出除头结点外的1到n?的范围的话那么执行删除操作
??{
???j=0;
???p=h;//将指针指向链表的头结点首地址
???while(j<i-1)
????{
?????p=p->next;
?????j++;
????}
???q=p->next;?/*q指向要删除的位置之前的那个结点指针域指向的
???地址q指向的结点就是要删除的结点*/
????
???p->next=q->next;/*这个就是将要删除的结点的前面那个结点
???的指针域指向要删除的结点指针域中存放的下个结点的
???首地址从而实现了删除第i个结点的作用*/

???strcpy(name,q->name);
???score=q->score;
???
???free(q);//释放q指向的结点
???printf("name=%s,score=%dn",name,score);
??}
}

/*--------------------------主函数-------------------------------*/
void?main()
{
?ListNode?*h;//h指向结构体NODE
?int?i?=?1,?n,?score;
?char?name?[10];

?while?(?i?)
??{
???/*输入提示信息*/
???printf("1--建立新的链表n");
???printf("2--添加元素n");
???printf("3--删除元素n");
???printf("4--输出当前表中的元素n");
???printf("0--退出n");

???scanf("%d",&i);
???switch(i)
????{
?????case?1:
??????printf("n=");???/*输入创建链表结点的个数*/
??????scanf("%d",&n);
??????h=CreateList(n);/*创建链表*/
??????printf("list?elements?is?:?n");
??????PrintList(h);
??????break;

?????case?2:
??????printf("input?the?position.?of?insert?element:");
??????scanf("%d",&i);
??????printf("input?name?of?the?student:");
??????scanf("%s",name);
??????printf("input?score?of?the?student:");
??????scanf("%d",&score);
??????InsertList(h,i,score,n);
??????printf("list?elements?is:n");
??????PrintList(h);
??????break;

?????case?3:
??????printf("input?the?position?of?delete?element:");
??????scanf("%d",&i);
??????DeleteList(h,n);
??????printf("list?elements?in?:?n");
??????PrintList(h);
??????break;

?????case?4:
??????printf("list?element?is?:?n");
??????PrintList(h);
??????break;
?????case?0:
??????return;
??????break;
?????default:
??????printf("ERROR!Try?again!n");
????}
??}
}

===========================================

对链表的删除操作?

应考虑以下情况：

１、找到需要删除的结点，用p1指向它。并用p2指向p1的前一个结点。

２、要删除的结点是头结点。

３、要删除的结点不是头结点

根据以上情况分析，得到删除一个结点的算法：

程序：

在链表head中删除学号为num的结点。以表头指针head和需要删除的结点的num（学号）为参数，返回删除操作后的链表表头。

struct?student?*?del(struct?student?*head,?long?num)
{
　struct?student?*p1;?/*?指向要删除的结点?*/
　struct?student?*p2;?/*?指向p1的前一个结点?*/

　if?(head?==?NULL)?/*?空表?*/?
　{
　　printf("n?List?is?NULLn");
　　return?(head);
　}?
　p1?=?head;
　while(num?!=?p1->num?&&?p1->next?!=?NULL)?/*?查找要删除的结点?*/
　{
　　p2?=?p1;
　　p1?=?p1->next;
　}
　if?(num?==?p1->num)?/*?找到了?*/
　{
　　if?(p1?==?head)?/*?要删除的是头结点?*/
　　　head?=?p1->next;
　　else　　　　　　/*?要删除的不是头结点?*/
　　　p2->next?=?p1->next;
　　/*?释放被删除结点所占的内存空间?*/
　　　　　　　/*?教材p235称：删除一个结点，并不是真正从内存把它抹掉????*/
　　printf("delete:?%ldn",?num);
　　n?=?n?-?1;
　}?
　else?/*?在表中未找到要删除的结点?*/
　　printf("%ld?not?foundn");

　return?(head);?/*?返回新的表头?*/
}

设在链表中，各结点按成员num（学号）由小到大顺序存放，把结点p0插入链表。

用指针p0指向待插入结点，设把p0插在p1结点之前，插入算法：

1、在p1之前、p2之后插入p0

2、将p0插入第一个结点之前

3、将p0插入表尾结点之后

4、找到应插入的位置

　应插入的位置：p1之前、p2之后。

　在链表中，各结点按成员num（学号）由小到大顺序存放，从第一个结点开始，把待插入结点p0->num与每一个结点p1->num比较，若(p0->num)?>?(p1->num)，则p1移到下一个结点。同时，p2也移到下一个位置。

根据以上分析，得出插入算法：

程序：

在链表head中，插入stud结点，并返回新链表的表头。

struct?student?*?insert(struct?student?*head,?struct?student?*stud)
{
　struct?student?*p0;?/*?待插入结点?*/
　struct?student?*p1;?/*?p0插入p1之前、p2之后?*/
　struct?student?*p2;

　p1?=?head;
　p0?=?stud;
　if(head?==?NULL)?/*?原链表是空表?*/
　　{
　　　head?=?p0;
　　　p0->next?=?NULL;
　　}
　else
　{
　　while?((p0->num?>?p1->num)?&&?(p1->next?!=?NULL))?/*查找待插入位置?*/
　　{
　　　p2?=?p1;
　　　p1?=?p1->next;
　　}?
　　if(p0->num?<=?p1->num)?/*?num从小到大排列，p0应插入表内（不是表尾）?*/
　　{
　　　?if?(p1?==?head)?/*?p1是表头结点?*/
　　　　{?
　　　　　head?=?p0;
　　
　　　　}?
　　　?else?
　　　　{
　　　　　p2->next?=?p0;
　　　　　p0->next?=?p1;
　　　　}?　　　　　?
　　}?
　　else?/*?p0插入表尾结点之后?*/
　　{
　　　p1->next?=?p0;
　　　p0->next?=?NULL;
　　}?
　}?
　n?=?n?+?1;?/*?结点数加1?*/
　return?(head);
}

5、举例

主程序（一）（有错）

void?main()
{
　struct?student?*?head;
　struct?student
　long?del_num;

　printf("input?records:n");?
　head?=?creat();?/*?建立链表，并返回表头?*/
　print(head);　　/*?输出链表?*/

　printf("nInput?the?deleted?number:");
　scanf("%ld",?&del_num);
　head?=?del(head,?del_num);?/*?从链表中删除del_num结点?*/
　print(head);?　　/*?输出链表?*/

　printf("nInput?the?inserted?record:");
　scanf("%ld,%f",?&stu.num,?&stu.score);
　head?=?insert(head,?&stu);?/*?在链表中插入一个结点stu?*/
　print(head);　　/*?输出链表?*/?
}

该程序插入多个结点时要出错。因为，使用一个普通变量stu不能代表多个结点。

正确的做法是：每一个插入的结点都应有自己的内存空间，因此，应在插入时为需要插入的结点分配内存。

主程序（二）（正确的程序）

void?main()
{
　struct?student?*?head;
　struct?student?
　long?del_num;

　printf("input?records:n");?
　head?=?creat();?/*?建立链表，并返回表头?*/
　print(head);　　/*?输出链表?*/

　printf("nInput?the?deleted?number:");
　scanf("%ld",?&del_num);
　while(del_num?!=?0)
　{?
　　head?=?del(head,?del_num);?/*?从链表中删除del_num结点?*/
　　print(head);?　　/*?输出链表?*/
　　printf("nInput?the?deleted?number:");
　　scanf("%ld",?&del_num);
　}

　printf("nInput?the?inserted?record:");
　while(stu->num?!=?0)
　{?
　　head?=?insert(head,?/*?在链表中插入一个结点stu?*/
　　print(head);　　/*?输出链表?*/?
　　printf("nInput?the?inserted?record:");
　　stu?=?(struct?student?*)malloc(LEN);
　　scanf("%ld,?&stu->num,?&stu->score);
　}?
/*　对于num=0的结点，未插入，应删除其空间?*/

=====================================================

五大内存分区
?????在C++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
?????栈，就是那些由编译器在需要的时候分配，在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
?????堆，就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。
?????自由存储区，就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。
?????全局/静态存储区，全局变量和静态变量被分配到同一块内存中，在以前的C语言中，全局变量又分为初始化的和未初始化的，在C++里面没有这个区分了，他们共同占用同一块内存区。
?????常量存储区，这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改（当然，你要通过非正当手段也可以修改，而且方法很多）
明确区分堆与栈
?????在bbs上，堆与栈的区分问题，似乎是一个永恒的话题，由此可见，初学者对此往往是混淆不清的，所以我决定拿他第一个开刀。
?????首先，我们举一个例子：
?????void?f()?{?int*?p=new?int[5];?}?
?????这条短短的一句话就包含了堆与栈，看到new，我们首先就应该想到，我们分配了一块堆内存，那么指针p呢？他分配的是一块栈内存，所以这句话的意思就是：在栈内存中存放了一个指向一块堆内存的指针p。在程序会先确定在堆中分配内存的大小，然后调用operator?new分配内存，然后返回这块内存的首地址，放入栈中，他在VC6下的汇编代码如下：
?????00401028????push?????????14h
?????0040102A????call?????????operator?new?(00401060)
?????0040102F????add??????????esp,4
?????00401032????mov??????????dword?ptr?[ebp-8],eax
?????00401035????mov??????????eax,dword?ptr?[ebp-8]
?????00401038????mov??????????dword?ptr?[ebp-4],eax
?????这里，我们为了简单并没有释放内存，那么该怎么去释放呢？是delete?p么？澳，错了，应该是delete?[]p，这是为了告诉编译器：我删除的是一个数组，VC6就会根据相应的Cookie信息去进行释放内存的工作。
?????好了，我们回到我们的主题：堆和栈究竟有什么区别？?
?????主要的区别由以下几点：
?????1、管理方式不同；
?????2、空间大小不同；
?????3、能否产生碎片不同；
?????4、生长方向不同；
?????5、分配方式不同；
?????6、分配效率不同；
?????管理方式：对于栈来讲，是由编译器自动管理，无需我们手工控制；对于堆来说，释放工作由程序员控制，容易产生memory?leak。
?????空间大小：一般来讲在32位系统下，堆内存可以达到4G的空间，从这个角度来看堆内存几乎是没有什么限制的。但是对于栈来讲，一般都是有一定的空间大小的，例如，在VC6下面，默认的栈空间大小是1M（好像是，记不清楚了）。当然，我们可以修改：????
?????打开工程，依次操作菜单如下：Project->Setting->Link，在Category?中选中Output，然后在Reserve中设定堆栈的最大值和commit。
注意：reserve最小值为4Byte；commit是保留在虚拟内存的页文件里面，它设置的较大会使栈开辟较大的值，可能增加内存的开销和启动时间。
?????碎片问题：对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，他们是如此的一一对应，以至于永远都不可能有一个内存块从栈中间弹出，在他弹出之前，在他上面的后进的栈内容已经被弹出，详细的可以参考数据结构，这里我们就不再一一讨论了。
?????生长方向：对于堆来讲，生长方向是向上的，也就是向着内存地址增加的方向；对于栈来讲，它的生长方向是向下的，是向着内存地址减小的方向增长。
?????分配方式：堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。
?????分配效率：栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，它的机制是很复杂的，例如为了分配一块内存，库函数会按照一定的算法（具体的算法可以参考数据结构/操作系统）在堆内存中搜索可用的足够大小的空间，如果没有足够大小的空间（可能是由于内存碎片太多），就有可能调用系统功能去增加程序数据段的内存空间，这样就有机会分到足够大小的内存，然后进行返回。显然，堆的效率比栈要低得多。
?????从这里我们可以看到，堆和栈相比，由于大量new/delete的使用，容易造成大量的内存碎片；由于没有专门的系统支持，效率很低；由于可能引发用户态和核心态的切换，内存的申请，代价变得更加昂贵。所以栈在程序中是应用最广泛的，就算是函数的调用也利用栈去完成，函数调用过程中的参数，返回地址，EBP和局部变量都采用栈的方式存放。所以，我们推荐大家尽量用栈，而不是用堆。
?????虽然栈有如此众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，还是用堆好一些。
?????无论是堆还是栈，都要防止越界现象的发生（除非你是故意使其越界），因为越界的结果要么是程序崩溃，要么是摧毁程序的堆、栈结构，产生以想不到的结果,就算是在你的程序运行过程中，没有发生上面的问题，你还是要小心，说不定什么时候就崩掉，那时候debug可是相当困难的：）
?????对了，还有一件事，如果有人把堆栈合起来说，那它的意思是栈，可不是堆，呵呵，清楚了？
static用来控制变量的存储方式和可见性
????????函数内部定义的变量，在程序执行到它的定义处时，编译器为它在栈上分配空间，函数在栈上分配的空间在此函数执行结束时会释放掉，这样就产生了一个问题:?如果想将函数中此变量的值保存至下一次调用时，如何实现？?最容易想到的方法是定义一个全局的变量，但定义为一个全局变量有许多缺点，最明显的缺点是破坏了此变量的访问范围（使得在此函数中定义的变量，不仅仅受此函数控制）。

????????需要一个数据对象为整个类而非某个对象服务,同时又力求不破坏类的封装性,即要求此成员隐藏在类的内部，对外不可见。

????????static的内部机制：
????????静态数据成员要在程序一开始运行时就必须存在。因为函数在程序运行中被调用，所以静态数据成员不能在任何函数内分配空间和初始化。
????????这样，它的空间分配有三个可能的地方，一是作为类的外部接口的头文件，那里有类声明；二是类定义的内部实现，那里有类的成员函数定义；三是应用程序的main（）函数前的全局数据声明和定义处。
???????静态数据成员要实际地分配空间，故不能在类的声明中定义（只能声明数据成员）。类声明只声明一个类的“尺寸和规格”，并不进行实际的内存分配，所以在类声明中写成定义是错误的。它也不能在头文件中类声明的外部定义，因为那会造成在多个使用该类的源文件中，对其重复定义。
???????static被引入以告知编译器，将变量存储在程序的静态存储区而非栈上空间，静态
数据成员按定义出现的先后顺序依次初始化，注意静态成员嵌套时，要保证所嵌套的成员已经初始化了。消除时的顺序是初始化的反顺序。

????????static的优势：
????????可以节省内存，因为它是所有对象所公有的，因此，对多个对象来说，静态数据成员只存储一处，供所有对象共用。静态数据成员的值对每个对象都是一样，但它的值是可以更新的。只要对静态数据成员的值更新一次，保证所有对象存取更新后的相同的值，这样可以提高时间效率。

?????????引用静态数据成员时，采用如下格式：
??????????<类名>::<静态成员名>
?????如果静态数据成员的访问权限允许的话(即public的成员)，可在程序中，按上述格式
来引用静态数据成员。

????????PS:
???????(1)类的静态成员函数是属于整个类而非类的对象，所以它没有this指针，这就导致
了它仅能访问类的静态数据和静态成员函数。
???????(2)不能将静态成员函数定义为虚函数。
???????(3)由于静态成员声明于类中，操作于其外，所以对其取地址操作，就多少有些特殊
，变量地址是指向其数据类型的指针?，函数地址类型是一个“nonmember函数指针”。

???????(4)由于静态成员函数没有this指针，所以就差不多等同于nonmember函数，结果就
产生了一个意想不到的好处：成为一个callback函数，使得我们得以将C++和C-based?X?W
indow系统结合，同时也成功的应用于线程函数身上。
???????(5)static并没有增加程序的时空开销，相反她还缩短了子类对父类静态成员的访问
时间，节省了子类的内存空间。
???????(6)静态数据成员在<定义或说明>时前面加关键字static。
???????(7)静态数据成员是静态存储的，所以必须对它进行初始化。
???????(8)静态成员初始化与一般数据成员初始化不同:
???????初始化在类体外进行，而前面不加static，以免与一般静态变量或对象相混淆；
???????初始化时不加该成员的访问权限控制符private，public等；
????????????初始化时使用作用域运算符来标明它所属类；
????????????所以我们得出静态数据成员初始化的格式：
??????????<数据类型><类名>::<静态数据成员名>=<值>
???????(9)为了防止父类的影响，可以在子类定义一个与父类相同的静态变量，以屏蔽父类的影响。这里有一点需要注意：我们说静态成员为父类和子类共享，但我们有重复定义了静态成员，这会不会引起错误呢？不会，我们的编译器采用了一种绝妙的手法：name-mangling?用以生成唯一的标志。

==========================================================

数据结构与算法分析

4月7日买起来看，前几天才看完。这可以说明很多问题，比如，学习很紧张，没有时间；书本身很好，很有看头；看书看得很细心，很有耐心。
????打算大致写一下书里的内容。
????Data?Structures?and?Algorithm?Analysis?in?C,?Second?Edition，机械工业出版社。封面很丑，一个黑底版，上面有些大理石花纹，正中间生硬的摆一个原版封面，同样丑。一共12章，近400页。
????400多页是很多的。我们必须要“把厚书读薄”，厚的变薄的，薄的变一页，一页变一行，一行变成一个字。因此，我要在有限的字数内把整本书说完。

????算法分析，就是复杂度的问题。复杂度只算“最要命的”，比如，执行n^2的算法前来个快排根本不拖速度，n^2多的都豁出去了不在乎区区一个nlogn。书里对复杂度进行了严格的定义，包括O()、o()、Θ()、Ω()四种符号。简单地说，O(n^2)就是顶破天了搞个n^2次；o(n^2)就是天花板不到n^2，比n^2矮一点（比如希尔排序就是o(n^2)，因为它再倒霉也达不到n^2）；Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2，比如所有基于比较的排序都是Ω(nlogn)；Θ(n^2)就是说它即是O(n^2)又是Ω(n^2)，被天花板和水泥地夹在中间了，动不了了，就是它了。这里面有一个经典的例子，就是最大子序列（找数列中连续一段数之和最大）的四种算法，复杂度分别为O(n^3)、O(n^2)、O(nlogn)和O?(n)。这书一个特色在于，对每种数据结构都有严格的算法复杂度证明，这往往是看上去最头痛的部分。

????表、栈和队列是三个基本的数据结构。说穿了表就是把数据找起来排排坐吃果果，找什么东西都来把整个队伍找一遍。栈就是一个桶，后放进去的先拿出来，它下面本来有的东西要等它出来之后才能出来，就好像你看到了一个丑人不可能今天的中饭还没吐出来就先把早饭吐出来了。栈是拿来模拟多个过程的调用的（比如递归），实际点的用途就是表达式计算。队列好比堵车，先进去的先出来。先进队先买票，不能插队。常拿来实现广搜。

????树，是一种植物，有很多枝枝丫丫。不同的是这里的树是倒着的，树枝朝下长。最上面叫根，尖尖的地方叫树叶，生出树叶的是他爸，他爸生的是他儿子。不管是根是树叶还是儿子还是儿子他爸都叫节点。我们常常把数据储存在节点上，并且以后还要不断地插入、改变和删除数据。
????二叉树就是每个分叉的地方最多分两个岔，而且还分得清左右。二叉查找树就是说把数据存在节点上，而且左边的都比他爸小，右边的都比他爸大，以后要找哪个数就可以只找其中的一边，一半一半地扔掉。在二叉查找树里也可以插入一个数，删掉一个数（只有一个儿子好办，有两个就把右边的最小的一个拿来替代这个），找最小的数（一直往左走），找最大的数（一直往右走），但是容易搞着搞着的树就变畸形了，比如说左边猛起长右边萎缩导致以后往左边走要走很久。我们就需要一种方法来让树左右差不多一样多而且左边的值仍然比右边的小。事实上这种方法已经找到了，而且不只一种方法，而是一卡车的方法，比如AVL、Splay、红黑树、Treap等。几种方法都靠一个叫“旋转”的技巧，就是把几个节点怎么个一转，左边的就跑到右边去了一点。看下面这个图你就明白了。

?????????①???????????????????②
????????/????????旋转???????/??
??????②???ZZ????------>????XX??①
?????/????????????????????????/??
????XX??YY????????????????????YY??ZZ

这样一来左边就少了，如果左边的XX本来很多的话就可以往上提一层从而平衡。同样地，右边多了反过来做就是了。这只是最简单的“单旋转”，事实上还有很多其它的较复杂的旋转方法。Splay树就是把刚才访问过的节点转啊转啊转啊转转到最顶上去，Treap就是每个节点附加一个随机的数，随时通过旋转保持儿子的这些随机数比他爸大，其余的有点复杂。这些方法都能使二叉查找树相对地平衡一些，防止畸变导致的时间浪费。
????B-树和二叉查找树有两个不同，一个是节点不存数据，数据全在树叶子上，二个是它不一定是二叉。数据仍然左边小右边大方便查找。每个节点最多的儿子数有限制，最多三叉的叫2-3树，最多四叉的叫2-3-4树。因为只有树叶上有数据，所以可以递归地用分裂的方法处理新插入后出现的分叉比规定的最多的儿子个数时还多的情况。比如，2-3树中如果哪里分了四个岔，就把它重新分成两个两个的岔。我们还规定，除了根以外，每个节点最少的儿子数是规定的最多儿子数的一半，除不尽取上整。容易想到，删除的话可以把插入时的分裂反过来做，什么时候只剩一个儿子了就和旁边的合并起来。

????Hash表又叫散列表，一般用于判断有没有重复。比如我想找我们班有没有两个一天生的，我们不必每两个人都来比较一次，而是准备一个年历，让人一个一个上去在他的生日那天那里画一个圈，如果谁要画圈时发现那里已经有一个圈了，就找到了一对。这个很简单，不说了。
????那天班上流行一个心里测试，当时我还真发现了一个和我一天生的，女的。

=========================================================================================

?堆，就是一陀一陀的东西。头重脚轻不算堆，要上面小下面大才算一个堆。堆是一棵二叉树，满足下面的始终比上面的大。它和二叉查找树比较起来既有好的又有不好的：好的就是要想知道数据里的最小值时根本就不用找了，直接就是最顶上的那个了；不好的就是堆除了这个以外基本上不能做别的事了。除了最顶上的那个以外，你几乎没办法控制其余的部分。当然，插入和删除数据这种基本操作还是可以做的。插入就是把数据暂时先放在最下面的某个位置，然后通过与它上面一个进行比较、交换不断往上冒直到已经到了自己的位置不能再向上为止。删除反起来，通过不断交换往下沉一直沉到底。因为是往下走，所以要考虑到一个把左边的放上来还是把右边的放上来的问题。当然，为了保证堆上小下大的性质，应该把小的一边换上来。刚才说过，由于你只能“看”到最顶上的东西，不知道中间部分是什么样，我们通常只删除最小的（最上面的）那个节点。其实堆还有一个最大的好处：容易写代码。因为我们可以有意让数据把树“排得满满的”，满到它是一行一行挨着排下来的。这叫做“完全二叉树”。我们可以给完全二叉树编个号，从上到下从左到右挨着数下来。根是1，找左儿子就乘2，找右儿子就乘2加1，找它爸就?div?2。以后叫谁就是谁，很方便。这样整个树就可以用一个数组实现了。由于堆基本上只用来找最小，因此如果某个问题要求很复杂的话，最好还是用成二叉查找树；当然，如果问题只要求插入、删除和找最小三种操作，你应该毫不犹豫地选择堆，毕竟找最小时堆方便得多，写起又简单。什么时候出现这种问题呢？比如说，我的女友排起队的，我每次要选一个最纯洁的，就是受那些的影响最小的人。每当我遇见了一个新的美女，我就把她放在这个队伍里合适的位置供我以后娱乐。这时，我只关心每次插入、取最小和删最小。这个队伍就可以用一个堆来优化。因此，堆还有一个形象的名字叫优先队列。如果谁问题目要求不找最小找最大怎么办，那人肯定是个傻子，把堆变通一下，上大下小不就完了吗？

????研究堆麻烦的地方就是堆的合并。如何把两个堆合并成一个堆？这个解决了很有用，至少上面的这些操作跟着全部统一了：插入就是与一个单节点的堆合并，删除根就是把根不要了，把根的左右两边（显然还是堆）合并起来。一个简单的办法就是递归地不断把根大的堆往根小的堆的右边合并，把新得到的堆替换原来的右儿子。注意递归过程中哪个根大哪个根小是不停在改变的。这样下来的结果就是典型的“右倾错误”，而且破坏了完全二叉树的完美。为此，我们想要随时保证堆的最右边尽量少。于是，干脆不要完全二叉树了，不过是多写几行代码嘛。这个不存在像二叉查找树那样“某一边越做越多”的退化问题，因为对于一个堆来说，反正我只管最顶上的东西，下面平不平衡无所谓，只要不挡我合并的道就行。于是，我们想到人为下一个能让堆尽量往左边斜的规定。这个规定就是，对于左右两个儿子来说，左边那个离它下面最近的两个儿子不全（有可能一个都没有）的节点的距离比右边那个的远。这规定看着麻烦，其实还真有效，最右边的路径的长比想像中的变得短得多。这就叫左式堆（左偏树）。这下合并倒是方便了，但合并着合并着要不了多少次右边又多了。解决的办法就是想办法随时保持左式堆的性质。办法很简单，你合并不是递归的吗？每次递归一层后再看看左右两边儿子离它下面没有两个儿子的节点哪个远，如果右边变远了就把左边右边调一下。由于我们已经没有用数组实现这玩意了，因此链表搞起很简单。这个对调左右的方法给了我们一个启发：哪里还要管什么到没有两个儿子的节点的距离嘛，既然我每次都在往右合并，我为什么不每次合并之后都把它对调到左边去呢？这种想法是可行的，事实上它还有一个另外的名字，叫斜堆。

????二项堆更强，它也是堆，也能合并，不过它已经超越了堆的境界了：它不是一个堆，而是满屋子的堆。也就是说，找最小值不能再一下子找到了，而是要把二项堆中的每个堆的顶部都看一下。二项堆的合并也很强，直接把根大的堆放在根小的堆的下面。这意味着二项堆的每个堆都可能不是二叉树了。这增加了编程的难度，不过可以用一个叫做“左儿子右兄弟”的技巧来解决问题。这个技巧，说穿了就是仍然用二叉树来表示多叉树：把树画好，然后规定节点的左儿子是下一层的最左边那个，右儿子就是它右边那个。就是说，左儿子才是真正的儿子，右儿子不过是一起生出来的。为了让二项堆好看些，让堆的个数和大小保持在一个能快速操作的数目和比例内，二项堆作出了一个明智的规定：每个堆的大小（总的节点个数）只能是1、2、4、8、16…中的一个，且每种大小的堆只能有一个。若干个互不相同的2的幂足以表示任意一个正整数，因此这个规定可以保证不管多大的二项堆都能表示出来。保持这个性质很简单，遇到两个大小相等的堆就合并起来成为一个大一号的堆。由于总是两个大小相等的堆在合并，因此二项堆中的每一个堆都有一个奇妙的样子，看看本文结束后下面附的一个大小为16的堆的示意图，再看一下，再看一下，你就能体会到了。图下面有一个用“左儿子右兄弟”法表示的同样的树，其中，往下走的线是左儿子，往右走的线是右儿子。

????最后简单说一下Fibonacci堆。保持一个跟着变的数组记录现在某个节点在堆中的位置，我们还是可以对堆里的数据进行一些操作的，至少像删除、改变数值等操作是完全可以的。但这个也需要耗费一些时间。Fibonacci堆相当开放，比二项堆更开放，它可以不花任何时间减少（只能是减少）某个节点的值。它是这样想的：你二项堆都可以养一屋子的堆，我为什么不行呢？于是，它懒得把减小了的节点一点一点地浮上去，而是直接就把它作为根拿出来当成一个新的堆。每次我要查最小值时我就再像二项堆一样（但不要求堆的大小了）一个个合并起来还原成一个堆。当然，这样的做法是有适用范围的，就是前面说的数值只能是减少。在什么时候需要一个数值只减少不增加的堆结构呢？莫过于Dijkstra一类的图论算法了。所以说，这些图论算法用Fibonacci堆优化可以进一步提速。

=========================================================================================

??有一个女人的男人很幸福。事实上，这是片面的。应该说，有不止一个女人的男人更幸福。但是，这样会坏了我的人品，而且被女的知道了也不好。两个耍得好的女人话很多，秘密在女人中传得很快。于是，我打算不同时和两个耍得好的女的耍朋友。后来我意识到，这样也不行。女人太无敌了，即使A与B耍得好，B与C耍得好，A和C的消息也是互通的。哪怕只有一个朋友关系也能把两群人联系在一起。我不得不改变策略，使得我的女朋友之间没有任何渠道传递信息。也就是说，在上面的A、B、C三个人中，虽然A和C没有直接的联系，但我也不能同时和A、C耍。不久后，我想知道，某两个女人是否可以通过某条“朋友链”传递信息。这就是所谓的等价关系——基本上算是判断一个无向图的连通性。就像很多个集合，每次选两个并成一个，而且我们随时想知道某两个元素经过前面的合并后是否在同一个集合内。怎么办呢？后来有一天，我发现那些小女生喜欢玩些认亲戚的游戏，什么谁是谁妈，谁是谁姐，谁是谁女儿之类的（不知道为什么这些疯女人喜欢搞这些）。我突然恍然大悟，我的问题可以用树结构来完成。亲戚的亲戚还是亲戚，但有一点总相同：所有亲戚的始祖总是一样的。始祖一样的都是一伙的。因此，把两个集合并在一起，只要让其中一个集合的根成为另一个集合中的某个元素的一个儿子就行了，这种家谱关系的改变将使前面的集合中所有的元素拥有和后面那个集合一样的鼻祖，而这将成为这些元素的“标志”。这个想法的灵感是来自女人世界的，因此女人还是有一定的作用。 ????这就叫并查集，又叫不相交集。它可以合并两个集合并且查询两个元素是否在同一集合。我们有一个很有效的剪枝：递归时顺便把路上经过的祖祖辈辈全部变成根的儿子。这样的程序只用2行来解决。 function?find_set(x:integer):integer; ???begin ???if?x<>p[x]?then?p[x]:=find_set(p[x]); ???exit(p[x]); end; ????p[x]表示元素x的父亲的位置。一开始，p[x]都等于x自己，表示自己一个人是一个集合。函数find_set(x)将返回x所在集合（一棵树）的根。 ????并查集还有些其它的剪枝和一些很复杂的效率分析问题，这里不多说了。 ????写到这里，《数据结构与算法分析》中的几个大块内容算是说清楚了。由于本文的叙述调整了原书各章节的顺序且至此还没有涉及书里的一些小问题，因此这里想把遗漏下的一些小东西提一下。 ????有一些树结构可能要求同时满足多个要求。比如一个简单的问题：如果要求构造一个堆使得既能查找最小元素又能查找最大元素怎么办？这时，我们可以用一个特殊的方法来实现：树的单数层满足一种性质，树的双数层满足另一种性质。我们用一个叫做最小-最大堆的东西来实现前面说的问题。这个堆的双数层的数据小于它爸大于它爸的爸，单数层的数据反过来，大于它爸小于它爸的爸。用类似的方法，我们还可以设计一个二叉查找树，使得它能够支持含有2种不同类型元素的数据。在单数层按其中一种操作，在双数层按另一种操作，这样可以方便的查找同时位于两个不同类元素的指定区间内的数据。这种二叉查找树叫做2-d树。扩展2-d?树，我们可以得到k-d树。这些数据结构的具体实现方法这里不说了，书上本来也是作为一个习题介绍的。 ????书里的第7章花了近50页介绍并分析各种排序算法，分析得很全。其中第11节花了10页介绍外部排序。所谓外部排序，就是说怎样快速地把一个根本无法全部读入内存的大文件进行排序。很多排序之所以可行是因为它们可以随意读写任意一个指定的数。但在大文件里，我们无法实现“第1234567890个元素和第?123个元素交换位置”，更无法实现递归之类的操作，而只能像磁带一样“过一遍”，从头到尾扫一遍，由于文件太大内存不能接受，因此必须要读一截扔一截。于是，外部排序产生了。不要以为这个限制会把排序速度拖得很慢。事实上，外部排序同样突破了O(n^2)的界限。它借助了归并排序中的“合并两个已经有序的数组”的思想，因为这个操作可以边读就边做。把文件先拆成两个文件，再把每个文件处理成一段一段的等长有序序列（一段多大取决于内存能一次处理多大），然后不断从两个文件中各取一段出来合并。可以看到，每段有序序列的长度变长了，变成了2倍长。过不了几次，这个长度将变成文件的总长。注意，我们必须要让每次合并时为下次合并做好准备（就是说合并后的结果仍然要是两个分了段的文件）。一个好的方法是将合并的结果交替存在两个不同的新文件中。 ????第9章讲图论算法。讲了图的遍历（广搜和深搜）、AOV、AOE、Dijkstra、网络流、Prim、Kruskal和NP问题。在讲深搜时，我学到了两个新东西，用线性时间查找割点（去掉了的话图就不连通了的点）和强分支（有向图中的一个分支满足其中任两个点之间都可以互相到达）。后来发现黑书上也有，又觉得这个东西很不好说，因此这里不想说了。说到了黑书还想顺便补一句：黑书真的看不得——太多错误了。不是说LRJ怎么了，LRJ在真正的大问题上有他的思想和经验，但很多细节的概念他也是昏的，这不利于初学者接受知识。不信哪天我还要写一篇日志纠正黑书的错误。引用政治书上抨击“人性自私论”的经典语言：“从理论到实践都是错的”。 ????第10章讲“算法设计技巧”，大概是些贪心啊，分治啊，动规啊，回溯啊，随机化啊之类的。调度问题、Huffman树、装箱问题近似算法、最近点距分治算法、最优二叉查找树、Floyd-Warshall、跳跃表、Miller-Rabin素性测试、博弈算法等都在这章中有讲，并且讲得相当好。由于这不是本书的重点内容，这里也不说了。 ????第11章整章都在讲摊还分析。这是一个相当复杂的问题，是分析时间复杂度的一个有力工具。它的分析告诉我们的不是某一个操作的复杂度，而是重复执行某一个操作的平均复杂度。研究这个是很有必要的，因为我们会遇到一些“越变越慢”的退化情形和“自我保持不变”的自调整性等数据结构，单个操作并不能反映它真正的效率。 ????到这里，这本书的所有东西都已经介绍完了。总的来说，这本书很值得一看（虽然有些地方翻译得很差）。它的理论性很强，证明过程完整（再复杂的分析它也证明得很清楚，满足那些刨根问底的人）；整本书自成一个体系，前后呼应；习题具有研究性，与课文互相补充。事实上，这些都是国外教材共有的特点。这算是我完整读过的第一本国外教材，今后我还会读一些。这几天在看《组合数学》（仍然是这个出版社出版的），看完后也打算写一下“对《组合数学》一书中部分内容的形象理解”。读一本国外教材，你会发现它与国内书籍的不同并会从中获益更多。 ????这篇文章就写到这里了。号称是一个5000字缩写，没想到写着写着已经超过8000字了。而且，这个并不是缩写，而是一些简单的、系统的、清晰的、形象化的思想和理解。这篇文章或许对已经知道一些有关知识的人有用，但不适合一点也没有接触过数据结构与算法分析的人。如果有一个人能从中收获一件东西，我写这个的目的也就达到了。