博文
我所理解的线索二叉树(2006-05-18 16:21:00)
摘要：
从上节的讨论得知：遍历二杈树是以一定规则将二杈树中结点排列成一个线性序列，得到二杈树中结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。但是，当以二杈链表作为存储结构时，只能找到结点的左，右孩子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只能在遍历的动态过程中才能得到。 因为在有n个结点的二杈链表中必定存在n+1个空链域，故可以利用这些空链域来存放结点的前驱和后继信息。 试做如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，需要改变结点结构，增加两个标志域：LTag，RTag。 其中：LTag = 0，lchild域指示其左孩子； LTag = 1，lchild域指示其前驱。 RTag = 0，rchild域指示其右孩子； RTag = 1，rchild域指示其后继。 以这种结点结构构成的二杈链表作为二杈树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二杈树叫做线索二杈树。对二杈树以某种次序遍历使其变成线索二杈树的过程叫做线索化。 在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直到其后继为空为止。 求遍历后的线性序列的前驱和后继。前序线索化能依次找到后继，但是前驱需要求双亲；中序线索化前驱和后继都不需要求双亲，但是都不很直接；后序线索化能依次找到前驱，但是后继需......
求行列式的值(2006-04-23 22:13:00)
摘要：/*求行列式的值 函数介绍：输入一个行列式，求其值 */
#include <iostream>
using namespace std;
const int N = 10; //行列式的阶数
void Create1(int H[][N]); //构造一个行列式 void Create2(int H[][N]); //构造一个行列式 void PrintH(const int H[][N]); //输出行列式 int HLS(const int a[][N], int n);//输入一个行列式，求其值 void YZS(int Y[][N], const int a[][N], int len, int a_r);//求行列式当前元素的余子式
int main() { int a[N][N] = {0};
// Create1(a); //构造一个行列式 Create2(a); //构造一个行列式 PrintH(a); //输出行列式 cout << HLS(a,N) << endl; getchar(); return 0;}
void Create1(int H[][N]){ int i, j; printf("请按标准格式输入行列式：每行%d个数值，用空格隔开\n", N); for (i=0; i<N; i++) { for(j=0; j<N; j++) scanf("%d", &H[i][j]); fflush(stdin); } }void Create2(int H[][N]){ int i, j; for(i=0; i<N; i++) for(j=0; j<N; j++) H[i][j] = rand()......
迷宫的算法(2006-04-23 22:08:00)
摘要：/* Name: 迷宫的算法 Copyright: Author: Date: 23-04-06 20:53 Description: 1。建立迷宫（外围建筑围墙），可选择人工创建迷宫或计算机随机创建迷宫，还可修改迷宫 2。设置入口和出口。 3。寻找最短路径。 4。若找到可行路径，打印路径，否则报告错误。*/
#include <iostream>#include <time.h>using namespace std;
const int M = 20; //最大行数const int N = 20; //最大列数enum {OPEN, CLOSE, PASSED, ROAD=-1}; //分别表示该点通，不通，已走和属于所选路径
class MiGong{ struct stype{//存储每个路径点的有关数据；横坐标，纵坐标和其前驱在数组中的位置 int x; int y; int pre; } way[M*N];
int zx[4];//存储东南西北四个方向所对应的x的值 int zy[4];//存储东南西北四个方向所对应的y的值 int begin[2];//存储入口坐标 int end[2]; //存储出口坐标 ......
第24次比赛第2题之测试程序:(2006-04-17 20:51:00)
摘要：第2题之测试程序:/* Name: Tic-Tac-Toe Copyright: original Author: goal00001111 Date: 12-04-06 10:25 Description: tic-tac-toe 是在3*3的棋盘上进行对弈的游戏。两个玩家在方格上轮流放置自己的棋子。 谁先获得行，列或对角线上的连续3个方格，谁就获胜。 请编写一个程序与其他程序进行tic-tac-toe比赛。 我创建了一个棋盘，供两位选手对弈。选手根据我提供的当前棋盘布局情况，选择合适的棋子落点。 注意：棋子要下在适当的空白处，若落子在已有棋子的地方或超出棋盘界限，判负。 函数接口：void ChooseMove(const int board[][3], int & row, int & column); 输入：当前棋盘布局board[][3]，棋盘上某点的行号row和列号column,行号和列号均从0开始. 输出：棋子落点的坐标 row, column 当前棋盘布局board[][3]，空为0, 我方为1, 敌方为2.我会在测试程序中对棋盘布局board[][3]进行实时变更,使得面对每一个选手程序均为:空为0, 我方为1, 敌方为2. 评分方法：每一轮比赛由2个程序进行3局对弈，前两局分先，第3局猜先。每局对弈打平各得1分，胜利者得2分，失败者不得分。比赛按提交楼层顺序，每3个程序为一组（每人最多提交2个程序，如果超过2个则只取最后修改的2个程序）。每组进行循环赛，即组内任意2个程序进行一轮比赛。分组剩余的程序如果为1个则自动晋级。如果为2个则2个程序作为一组进行比赛。第一次循环赛结束后，每组得分最高的程序晋级，......
第24次比赛第1题之测试程序 (2006-04-17 20:50:00)
摘要：
第1题之测试程序:/* Name: 选美大奖赛 Copyright: c 语言趣味程序 Author: 梁见斌 Date: 13-04-06 16:08 Description:在选美大奖赛的半决赛现场，有一批选手参加比赛，比赛的规则是最后的得分越高，名次越低。当半决赛结束时，要在现场按照选手的出场顺序宣布最后得分和最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不要考虑同名次的选手人数。例如：选手序号：1，2，3，4，5，6，7选手得分：5，3，4，7，3，5，6则输出名次为：3，1，2，5，1，3，4请编程帮助大奖赛组委会完成半决赛的评分排名工作。函数接口：void ScorePlace(int place[], const int score[], int num);输入：存储选手名次的数组place[]，存储选手得分的数组score[]，选手人数num。输出：存储选手名次的数组place[]。示例1：输入：score[] = {2,8,5,1,10,5,9,9};输出：place[] = {2,4,3,1, 6,3,5,5};示例2：输入：score[] = {7,7,6,6,7};输出：place[] = {2,2,1,1,2};*/#include <iostream>#include <time.h>using namespace std;void ScorePlace(int place[], const int score[], int num);void ScorePlace_c(int place[], const int score[], int num);int ......
菜鸟在成长续集(2006-04-17 20:48:00)
摘要： 终于测试完了最后一个程序，我轻轻地关闭dev-c++编译器，伸了一个懒腰，然后起身到桌子那头拿起昨天喝剩的的农夫果汁，满意地猛灌一口----好爽！ 再一次检查了记事本上的测评记录，没错，是eastcowboy的程序速度最快，这小子采用了快速排序法，处理100组数据简直不费时间------其他人的就要逊色多了。 还是早点把结果传上去吧，想象自己以前等待结果的心情，那个猴急劲啊！可不能让大伙儿等的太久了。 “。。。。。现在我宣布：eastcowboy为本次比赛冠军!”手指在键盘上飞舞，此时的心情好激动啊-----当然更多的是自豪。（呵呵，有点自恋啊------增添点文学色彩，：）） 等了多久才能站在这个位置？我记不清楚了。编程比赛已经成功举行了24次了，算每周一次，那就是过了168天了。在过去的168天里，我几乎天天与c/c++为伴（说的过了点，但也差不多了），从仰看高手们的高妙身手，到今天能在这论坛里占有一席之地------又来了，纯粹是为了增添点文学色彩，大家不要往心里去啊，其实我的水平还低的很，要想和论坛里的高手们站在一起，还需要买一架高梯子啊！ 能够成为第23次比赛的冠军，除了幸运还是幸运！什么阴差阳错，鬼使神差，天上掉馅饼，用在这里全不为过。想想看，1217次点击，10个回帖，却只有我一个人交的是程序，而且恰好对了-------虽然算法不咋地-------这真有点像买彩票中了奖的感觉（其实我买彩票中的最大的奖是去年11月中的5元，而且打那以后再也没有中过）。 编程比赛开展了快半年了，这半年中人们来来往往，由于各种各样的原因，很多人在论坛里如匆匆过客，一些高手曾经在某些比赛中为大家展现过高妙的算......
我所理解的继承及多态性(2006-04-04 14:10:00)
摘要： 我所理解的继承及多态性
现在让我们来谈谈继承及多态性，继承对面向对象编程至关重要，创建继承类的能力，从一般到具体，这样可以更好地控制程序，而且使程序更容易理解和扩展。 我将从以下几个方面谈谈我对继承及多态性的理解： 1。继承的特点。 2。继承的三种方式及其特点。 3。多层继承。 4。多重继承。 5。虚函数。 6。纯虚函数和抽象类。
1.1 继承的基本概念 对象（Object）是类（Class）的一个实例（Instance）。如果将对象比作房子，那么类就是房子的设计图纸。所以面向对象设计的重点是类的设计，而不是对象的设计。 对于C++程序而言，设计孤立的类是比较容易的，难的是正确设计基类及其派生类。 继承概念的基础是基类和派生类的关联，如果A是基类，B是A的派生类，那么B将继承A的数据和函数。例如： #include <iostream> using namespace std; //基类A class A { public: int numA; void SetNumA(int n) { numA = n; } int GetNumA() { return numA; } }; //派生类B class B: public A { public: int numB; void SetNumB......
妙用数学原理巧解编程趣题(2006-04-02 16:37:00)
摘要： 妙用数学原理巧解编程趣题有这样一道有趣的题目：有编号为1--100的灯初始状态是全开着的，现进行如下操作：A 编号是1的倍数灯拨一下开关，（开--关算一次拨操作；关--开算一次拨操作）；B 是2的倍数灯再拨一下开关；C 是3的倍数的灯再拨一下开关；。。。。。。如此直到100的倍数。问：此时有哪些编号的灯是熄灭的？累积熄灭的灯的个数，并输出其编号。
初看此题并不难，思路很快出来：创建一个整型数组用来存储所有灯的状态，设初值为0，表示灯初始状态是全开着的。遍历数组，从1到100对每个编号进行倍数判断操作，对满足条件的灯进行一次拨操作。最后判断有哪些编号的灯是熄灭的，即判断数组中哪些元素的值为1。具体代码如下：例程1：#include <iostream>using namespace std;
int Shift(int light); //执行一次拨操作
int main() { const int N = 100;//灯的总数 int a[N] = {0}; //整型数组用来存储所有灯的状态，设初值为0，表示灯是全开着的 for (int i=0; i<N; i++)//遍历数组 for (int j=i+1; j>0; j--) //穷举所有不大于当前编号的数 { if ((i+1)%j == 0) //如果j是当前编号i+1的约数，即i+1是j的倍数，则执行一次拨操作 a[i] = Shift(a[i]);//也可用a[i] = (a[i] == 0)? 1 : 0; 实现 } int sum = 0; //用来累计熄灭的灯的个数 cout << "熄灭的灯的编号:" << endl; for (int i=0; i<N; i++)//累积熄灭的灯的个数，并输出其编号 { &n......
我所理解的构造函数的初始化列表(2006-03-12 20:48:00)
摘要：在前面的例程中，我们对成员数据的初始化，都是在函数体中进行的，但有些情况下这种初始化的方法是行不通的，例如：#include <iostream>using namespace std;
class Date{ int da, mo; const int yr;//const常量public: Date(int d, int m, int y) //有参数的构造函数 { cout << "Have parameter: "; da = d; mo = m; yr = y; //此处有错误 } void display() { cout << "\n" << mo << "-" << da << "-" << yr; }};
int main() { Date a; a.display(); getchar(); return 0;}在类Data中有一个成员yr是一个const int类型，它是不能在函数体中被重新赋值的。这种情况下我们只有使用另一种特殊的初始化方式——初始化列表。初始化列表位于函数参数表之后，却在函数体 {} 之前。这说明该表里的初始化工作发生在函数体内的任何代码被执行之前。构造函数初始化列表的使用规则：如果类存在继承关系，派生类必须在其初始化表里调用基类的构造函数。例如 class A {… A(int x); // A的构造函数 }; class B : public A {… B(int x, int ......
我所理解的拷贝构造函数和赋值函数(2006-03-12 20:47:00)
摘要：3.1 拷贝构造函数概述现在我们来学习一种特殊的构造函数——拷贝构造函数。对于普通类型的对象来说，他们之间的复制是很简单的，例如： int a = 10; int b =a; 自己定义的类的对象同样是对象，谁也不能阻止我们用以下的方式进行复制,例如：#include <iostream>using namespace std; class Test { int p;public: Test(int temp) { p = temp; } void Show() { cout << "p = " << p << endl; } };
int main() { Test a(99); Test b = a; a.Show(); b.Show(); getchar(); return 0;}程序将正确运行并输出：p = 99p = 99普通对象和类对象同为对象，他们之间的特性有相似之处也有不同之处，类对象内部存在成员变量，而普通对象是没有的，当同样的复制方法发生在不同的对象上的时候，那么系统对他们进行的操作也是不一样的，就类对象而言，相同类型的类对象是通过拷贝构造函数来完成整个复制过程的，在上面的代码中,我们并没有看到拷贝构造函数，同样完成了复制工作，这又是为什么呢？因为当一个类没有自定义的拷贝构造函数的时候系统会自动提供一个默认的拷贝构造函数，来完成复制工作。 例如：#include &......