博文
我所理解的二杈树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......
：[转帖]软件开发入门学习的个人看法（转贴自dearbook (2005-12-27 08:11:00)
摘要：踏实
偶然在网上看到《由C#风潮想起的－给初学编程者的忠告》一文. 其中一个角度：避免“浮躁”，倡导“踏实”的学习方法，我是很认同的，但总觉该文作者标题“-给初学编程者的忠告”太大，所以在其文列出的一些具体的“操作方法”上我认为可以探讨，如同自己在某次公司总结会上就《软件开发，我们积累的是什么？》为题跟同事聊了半个多小时后，其中一个同事提到希望我能继续把这个题目细化，就刚入行的他们具体该如何发展有更“具操作性”的指引，当时我是跟他们说这只是我在这一行呆了5年多的体会，谈“指引”还太远，只是可以提出来大家思考、讨论。
不要过度贬低编码
不要真的认为"不少大师级的计算机技术研究者是不懂编程的",做软件开发编码是最最基础的东西,只有踏踏实实的掌握好这个基础你才有办法往上走,不管做分析做设计做项目管理你都需要能清楚东西是如何实现的?可不可以实现?否则肯定出现大量的:"设计是设计,编码是编码","产品都是代码人员从头到尾实现的","究竟需花多少时间,难度有多大,开发人员说了算","质量/成本/进度全是黑匣子"...现象,如果你是做编码那编码就更重要了:).所以对于有志从事这个行业(软件开发)的个人来说,必须先从"重视编码"开始.过了这一关才能去考虑做系统分析,做项目管理...
软件开发的各个环节是相辅相承的,分析有分析的重要,设计有设计的重要,编码有编码的重要,测试实施也各有其地位,任何一个环节搞不好就如同我们熟悉的木桶理论,"最薄弱的一个环节制约着其总容量".
既然编码重要,那该如何学编码?
专心学好一门语言
算算自己用过的语言也不少（括弧里为使用该语言写的比较有代表性的东东）,C（dos版的图像/图标编辑工具,96年的《电脑报》有介绍）,C++（可自定义方块形状的方块游戏,被收录于99年《软件》杂志的附送光盘上）,汇编(DOS汉字系统,97年底完成),PB(学校自动排课/排考模块,98年),ASP(一套web版的企业信息系统,99年),VB(企业信息系统的核心组件,9......
连连看游戏(2005-12-22 11:11:00)
摘要：连连看游戏连连看游戏是一个在10 \Theta 15 的板子上玩的单人游戏。每个方块里都有一个红球，绿球或者蓝球。两个同颜色的球属于同一串，每一个球都能被它周围上下左右四个方位同颜色的球够着（即属于同一串）。在游戏的每一个阶段中，游戏者选择一个球，这个球所属的串至少包含两个球，然后在木板上移走该串球。然后这个木板在经过以下两个阶段后被“压缩”。
1，把每一列中剩下的球往下移动以填补空位。球的排列顺序被保留。
2，如果某列中球全被拿走了，把其右边的球整列整列地尽量往左移。球的排列顺序被保留。
在下面的例子里我们选择左下角的球：(很可惜,图象传不上来)
游戏的目的是把所有的球从木板中移走，当所有的球都被移走或者每串球只剩一个的时候游戏就算结束了。每次游戏分数的计算如下：玩家开始分数为0，每移走含m个球一串球，玩家分数增加 (m-2)^2分。如果在游戏结束时所有的球都被移走，玩家将得到额外的1000分的奖励。
你猜想最好的策略可能是每次都选择拥有最大串的球，那么你要做的就是编一个程序模拟用这种策略来玩这个游戏。如果有两个或以上的球可以选择，程序将选择最左边的球来得到最大串。如果仍然有同时满足条件的，将优先选择最底端的球。
输入：
输入游戏中球最初的排列，即所谓迷宫的分布。每一行包括MaxLine个字母，每一个字母为“R”，“G”或“B”，明确给出各行各列的球的颜色，共MaxRow行。
输出：
关于每次移动的信息，和每次移动所得到的分数，每次移动的输出按照如下格式：Move x at (r,c): removed b balls of color C, got s points，其中x是移动的次序数，r和c表示被选中的球所在的行数和列数。行数从下往上数1-MaxRow总共是MaxRow行，列数从左往右数1-MaxLin总共MaxLin行。b表示被移走的那串球的个数；C表示球的颜色，可以是“R”，“G”或“B”；s是移动所得的分数。这个分数并不包括因把球全部移走而得到的额外奖励。最后的分数必须象这样公布：Final score: s, with......
我所理解的队列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......