博文
我所理解的二杈树03(2005-12-28 11:09:00)
摘要：有序二杈树是很好用的，在插入和查找的时候时间复杂度一般为O（logN），但如果左右子树失去平衡，也可能达到O（N）。为了防止这种现象发生，一种解决办法是是左右子树尽量保持平衡，即建立一种平衡有序树AVL树。
一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二杈有序树。空树的高度定义为-1。
AVL树的结点声明；
typedef struct avlnode
{
int height;//比普通二杈有序树多了一个高度信息
ElemType data;
struct bnode *lchild, *rchild;
} *AvlTree, *Position;
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);
//----------AVL树基本操作的算法实现--------------------
递归算法：
Position FindMin(AvlTree T)
{
if(T==NULL)
return NULL;
else if(T->lchild == NULL)
return T;
else
return FindMin(T->lchild);
}
Position FindMax(A......
我所理解的二杈树02(2005-12-28 11:09:00)
摘要： 二杈排序树
所谓二杈排序树，指的是一棵空二杈树，或者是一棵具有如下特性的非空二杈树：
1。若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
2。若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
3。左，右子树本身又各是一棵二杈排序树。
二杈排序树的基本操作包括二杈排序树的查找，生成（插入）和删除。
二杈排序树的查找：
在二杈排序树b中查找x的过程为：
1。若b是空树，则搜索失败，否则
2。若x等于b的根结点的数据域之值，则查找成功；否则
3。若x小于b的根结点的数据域之值，则搜索左子树；否则
4。搜索右子树
btree* search(btree *b, ElemType x)
{
if(b == NULL)
return NULL;
if(b->data == x)
return b;
if(b->data > x)
return search(b->lchild);
&n......
我所理解的二杈树01(2005-12-28 11:07:00)
摘要：我所理解的二杈树
二杈树的一个最大特点是只有两个儿子，这为它的运算带来极大方便。
二杈树的存储方式有三种：顺序存储，链接存储和线索存储。顺序存储最简单，用数组就
能实现，但它要求二杈树必须是一棵完全二杈树，这种情况很少见，所以用的不多。链接存储
是很常见的方法，我将着重介绍。
链接存储的二杈树类型和结构定义如下：
typedef struct bnode
{
ElemType data;
struct bnode *lchild, *rchild;
} btree;
链接存储的二杈树的基本运算包括遍历二杈树和输出二杈树。其中根据访问根结点的不同
次序又可以分为先序，中序和后序遍历。我将分别用递归和非递归的算法实现这三种不同遍历
过程。
1。递归算法
先序遍历
void preorder(btree *p)
{
if(p != NULL)
{
printf("%d", p->data);//输出该结点（根结点）
preorder(p->lchild); //遍历左子树
preorder(p->rchild);//遍历右子树
}
}
中序遍历
void inorder(btree *p)
{
if(p != NULL)
{
inorder(p->lchild); //遍历左子树
printf("%d", p->data);//输出该结点
inorder(p->rchild); //遍历右子树
}
}
后序遍历
void postorder(btree *p)
{
if(p != NULL)
{
postorder(p->lchild);&nbs......
我所理解的队列02(2005-12-18 15:47:00)
摘要：举个简单的例子，围圈问题的详细算法和程序
17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号。
这个题目的解法很多，我原来就总结了5种，但都不如用数组队列来的简明。算法如下：
/*求围圈问题的详细算法和程序*/
/*17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号 */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a[17]={0};
int front=0, rear=16; //因为数据较小，可令队头元素也占一个实用（有数据域）的空间
int i, count=0; //计数器
for (i = 0;i < 17;i++)
a[i] = i + 1; /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
while((front%17) != (rear%17))//当队列元素还有一个，注意这里不需要队列为空，而是留一个元素
{
......
我所理解的队列01(2005-12-18 15:43:00)
摘要：我所理解的队列
象栈一样，队列也是表。然而，使用队列时插入在一端进行而删除在另一端进行。
同样的，也有两种方法来实现队列，一种是用链表，一种是用数组。
先来看看用链表实现的队列。
我们把进行删除操作的一端叫队头（通常用链表的头结点表示），而进行插入操作的一端叫队尾，
通常用尾结点表示）。每当删除一个结点，头指针后移一位；反之，尾指针后移一位。所以用链表实现
队列的操作是很简单的，它的基本操作和链表的基本操作几乎完全相同。
实际上人们更喜欢用数组来实现队列。对于每一个队列数据结构，我们保留一个数组Queue[]以及
位置Front和Rear，他们位于表队列的两端。我们还要记录实际存在于队列中的元素的个数Size和
数组的最大容量Capacity，所有这些信息是作为一个结构的一部分。
数组实现的队列的一个特性就是可以循环使用数组的空间，只要Size小于Capacity（Front独占一个空间，
不放数据），就不会出现溢出。
//-----------用数组实现队列的存储结构-------------
#define MinQueueSize 5
typedef struct QueueRecord{
ElemType *Array;
int Capacity;
int Front;
int Rear;
int Size;
} *Queue;
//-------------------用数组实现队列......
我所理解的栈02(2005-12-15 16:00:00)
摘要：//-------用数组现栈的基本操作的算法实现------------------------
Stack InitStack(int MaxElements)//构造一个空栈
{
Stack S;
if(MaxElements < MinStackSize)
{
Puts("Stack size is too small!");
return NULL;
}
S = (Stack)malloc(sizeof(struct StackRecord));
if(!S)
{
printf("Out of space!");
return NULL;
}
S->Array = (ElemType*)malloc(sizeof(ElemType)*MaxElements);
if(!S->Array)
{
printf("Out of space!");
return NULL;
}
S->StackSize = MaxElements;
return MakeEmpty(S);
}
void Destr......
我所理解的栈01(2005-12-15 15:57:00)
摘要：我所理解的栈
栈（stack）是限制插入和删除只能在一个位置上进行的线性表，该位置通常在表的末端，叫做栈顶（top）----实际上我喜欢把链表的表头作为栈顶，栈顶不存储任何值，只是一个标志，所谓的“栈顶元素”实际上
是链表的头结点的直接后继的值。这样实行插入和删除操作都很方便。栈可以用链表（包括动态链表和静态链表）实现，也可以用数组实现。我们先来看看如何用链表实现（以动态链表为例，大家可以推广到静态链表中）。
//-----------用动态单链表实现栈的存储结构-------------
typedef struct Node{
ElemType data;
struct Node *next;
} *LNode, *Stack;
//-------------------用动态单链表实现栈的基本操作------------------------
Stack InitStack(void); //构造一个空栈
void DestroyStack(Stack *S);//初始条件：栈S已存在。 操作结果：销毁栈S。
Stack MakeEmpty(Stack S);//初始条件：栈S非空。 操作结果：将栈S重置为空栈。
int IsEmpty(Stack S);//初始条件：栈S已存在。 操作结果：判断栈是否为空栈。
int StackLength(Stack S);//初始条件：栈S已存在。 操作结果：返回栈S结点的个数。
ElemType GetTop(Stack S);//初始条件：栈S非空。 操作结果：返回栈顶元素的值
LNode NewLNode(ElemType X);//构造一个数据域为X的新结点
//初始条件：栈S已存在。 操作结果：插入元素X为新的栈顶元素
void Push(Stack S, ElemType X);
ElemType Pop(Stack S);//初始条件：栈S非空。 操作结果：删除S的栈顶元素, 并返回其值
//---------------------------------------------------------------
其实我们很容易发现，上面的9个基本操作......
我所理解的链表05(2005-12-07 21:08:00)
摘要：和动态链表一样，以上操作为线性静态单链表的最基本的操作，其他操作可以是上述操作的组合。
例如要实现“判断结点P是否为链表L的尾结点”操作，函数如下：
int IsLLast(SLink L, Position P)
{
if(LContaiP(L, P)
return IsLast(P);
return 0;
}
如果你仔细的阅读这些代码，你会发现动态链表和静态链表的基本操作的实现算法很相似，游标实现的接口和指针实现是一样的。静态链表可以代替动态链表实现，实际上在程序的其余部分不需要变化，而且速度更快。
同样的让我们用一个实际的例子说明。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集的非，即（A-B）并（B-A）。
算法思路是先把集合A和B分别存入两个单向链表LA和LB中，以LB的结点P为研究对象，遍历LA，看是否有与其同值的结点，若有删除与结点P相同的结点，否则把结点P插入链表LA。最后得到的LA就是集合A和B的交集的非。
具体的实现如下所示，因为函数部分已经包含在“线性表的静态单链表基本操作的算法实现“中，所以不做重复，只把其他的部分列出来。程序经过测试，可以运行。
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAXSIZE 100//链表的最大长度
typedef int Position;
typedef int SLink;
typedef int ElemType;
typedef struct Node{
ElemType data;
Position next;
} SLinkList[MAXSIZE];
SLink CreateList(ElemType a[], ElemType len);//用来构造一个链表
。。。//其他函数声明
int main(void)
......
我所理解的链表04(2005-12-07 21:07:00)
摘要：动态链表我们就先讲到这里，实际上更让我感兴趣的是静态链表。这种无需指针而有能够实现链表功能的结构，对于那些不支持指针的高级语言来说，无疑是个巨大的福音。它既可以像数组一样随机存取数据---它本身就是一个数组，又具有链表方便地实现插入和删除结点的功能；由于它是模拟的“动态分配空间”，实际上它的存储空间是由系统一次性分配好了的，这样在“动态分配空间”的时候，不需要内存管理程序，如果运行的Find函数相对较少，它实现的速度比动态链表要快很多；此外，他很少出现因为内存空间不够的原因而导致程序不正常终止的情况，因为它的空间一早就分配好了，只要不超出链表的最大长度，空间就足够。因此它真可以称的上是一个“宝贝”。
在链表的指针实现（即动态链表）中，有两个重要的特点：
1.数据存储在一组结构体中,每个结构包含有数据以及指向下一个结构体的指针.
2.一个新的结构体可以通过调用malloc()而从系统全局内存(global memory)得到,并可以通过调用
free()而被释放.
静态链表必须能够模仿实现这两条特性.满足条件1的逻辑方法是要有一个全局的结构体数组.对于该数组中的任何单元(元素),其数组下标可以用来表示一个地址(结点).也就是说数组元素(结构体)包含有数据以及指向下一个结构体的游标---即下一个结点的数组下标.可以建立不同的链表，但实际上每一个链表都是结构体数组一部分元素的集合。
为了模拟条件2，我们需要建立一个“模拟空间分配站”，它是一个规模较大的结构体数组。我们可以建立不同的链表，实际上我们创造的每一个链表都来自这个“模拟空间分配站”，每一个结点都是该结构体数组的元素，每一个链表都是结构体数组一部分元素的集合。
它的类型声明和基本操作如下表所示：
//-------------------线性表的静态单链表存储结构------------------------
#define MAXSIZE 1000//链表的最大长度
typedef int Position;
typedef int SLink;
typedef struct Node{
ElemType data;
Position next;
} SLinkList[MAXSIZE];
//......
我所理解的链表 03(2005-12-07 08:47:00)
摘要：以上操作为线性单链表的最基本的操作，其他操作可以是上述操作的组合。如，执行“在线性表L中寻找值为X的结点，并删除之”操作时，可先执行LNode FindPrefious(ElemType X, LinkList L)，再执行void ListDelete(LNode Pre)。 又如，执行“把一个值为X的新结点插入结点P之前”，可先执行LNode FindPrefious(ElemType X, LinkList L)，再执行LinkList NewLNode((ElemType X)，最后执行void ListInsert(LNode Pre, LNode S)。
我特意向大家推荐这种”坚持使用头结点“和“锁定前驱结点”的设计方法，这正是我和一般书本上有着不同理解的地方。有些书上的例程有时设置一个头结点，还有些根本就不使用头结点，也许是他们认为头结点占地方罢，但我认为为了更方便的编程实现我们的意图和更好的编程风格---主要指代码清晰易读，我再一次吐血推荐我的设计方法。因为这种设计方法就像一把万能钥匙---也许有些夸张了，呵呵！一般书上的例程在删除或插入结点时，要分别讨论链表头，链表中和链表尾三种不同的情况，采取不同的操作；而我上面所列的”删除“和”插入“操作可以全面搞定对链表中任意位置的结点（头结点除外）插入和删除功能。（除了”把新结点插入到链表尾“，但这可以组合执行LNode IsLast(LinkList L)和void ListInsert(LNode Pre, LNode S)）。
举一个实际的例子。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集。
算法思路是先把集合A和B分别存入两个单向链表LA和LB中，以LA的结点P为研究对象，遍历LB，看是否有与其同值的结点，根据情况判断是否执行删除结点P的指令。最后得到的LA就是集合A和B的交集。
具体的实现如下所示，因为函数部分已经包含在“线性表的单链表基本操作的算法实现“中，所以不做重复，只把其他的部分列出来。程序经过测试，可以运行。
#include
#include
#include
typedef int ElemType;
typedef struct Node{
ElemTyp......