博文
平衡有序树AVL树之两种思路(2006-06-05 17:34: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树基本操作的算法实现--------------------递归算法： P......
我所理解的线索二叉树(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-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-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 &......
我所理解的构造函数与析构函数(2006-03-12 20:44:00)
摘要： 学习c++一段时间了，入门教材是〈〈c++基础教程（第2版）〉〉（清华大学出版社；（美）Herbert Schildt 著，王军 译），花两周粗粗地看了一遍，感觉有点印象了。后来又看〈〈c,c++程序员实用大全〉〉，看〈〈标准c++宝典〉〉，感觉越来越糊涂，特别对const的使用和类的构造函数，析构函数，拷贝构造函数和赋值函数的认识有些摸棱两可，于是决定写篇文章，做一个阶段性的总结，同时希望拙文能够给各位初学者一些帮助。
1.1 构造函数与析构函数的起源 作为比C更先进的语言，C++提供了更好的机制来增强程序的安全性。C++编译器具有严格的类型安全检查功能，它几乎能找出程序中所有的语法问题，这的确帮了程序员的大忙。但是程序通过了编译检查并不表示错误已经不存在了，在“错误”的大家庭里，“语法错误”的地位只能算是小弟弟。级别高的错误通常隐藏得很深，就象狡猾的罪犯，想逮住他可不容易。 根据经验，不少难以察觉的程序错误是由于变量没有被正确初始化或清除造成的，而初始化和清除工作很容易被人遗忘。Stroustrup在设计C++语言时充分考虑了这个问题并很好地予以解决：把对象的初始化工作放在构造函数中，把清除工作放在析构函数中。当对象被创建时，构造函数被自动执行。当对象消亡时，析构函数被自动执行。这下就不用担心忘了对象的初始化和清除工作。 构造函数与析构函数的名字不能随便起，必须让编译器认得出才可以被自动执行。Stroustrup的命名方法既简单又合理：让构造函数、析构函数与类同名，由于析构函数的目的与构造函数的相反，就加前缀‘~’以示区别。 除了名字外，构造函数与析构函数的另一个特别之处是没有返回值类型，这与返回值类型为void的函数不同。构造函数与析构函数的使命非常明确，就象出生与死亡，光溜溜地来光溜溜地去。如果它们有返回值类型，那么编译器将不知所措。为了防止节外生枝，干脆规定没有返回值类型。（引自〈〈高质量c++编程指南〉〉）
1.2 构造函数概述 创建对象实例时，程序通常初始化对象的数据成员，为了简化初始化对象的过程，c++使用了一个特殊的函数——构造函数，程序每次创建对象实例时，自动执行构造函数。在正式讲解之前，我们先看看c++对构造函数的一个基本定义。 1.C++规定，每个类必须有构造函数，......
我所理解的矩阵04(2006-01-10 21:34:00)
摘要：一个组合应用，做了一个工程文件，大家可以去下载。把基本函数写下来，其他的功能函数可以在文中找到.#define N 100#define MAXSIZE 1000 //假设非零元素的个数最多为1000个 #define MAXRC 100 //假设矩阵的行（列）数最多为100
typedef struct matnode{ int row, col; //结点的行域和列域 struct matnode *right, *down;//结点的向下域（down）和向右域（right） union //结点的数据域，若为表头结点则无数值，而用指向其后继的指针代替 { int data; struct matnode *next; } tag;} CrossNode, *CrossList;
typedef struct{ int x, y; //该非零元素的行下标和列下标 int e; //该非零元素的值 } Triple;typedef struct{ Triple data[MAXSIZE+1];//非零元素三元组顺序表data[0]未用 int mu, nu, tu; //矩阵的行数，列数和非零元素的个数 } TSMatrix;
typedef struct node{ int data; //存储元素的值 int x; //存储元素的横坐标 int y; //存储元素的纵坐标 } array;
int sum; //全局变量，存储行列式的值
void DoArray(void); // 二维数组存储矩阵演示void CreateArray(int H[][N], int m, int n); //构造一个二维数组存储矩阵void PrintArray(const int H[][N], int m, int n); //输出......
我所理解的矩阵03(2006-01-10 21:33:00)
摘要：除了用三元组顺序表来存储压缩矩阵，我们还可以用链表结构来存储，实际上后者应用更广泛，因为当非零元素的数目较大时，三元组的时间复杂度实在太高。链表结构中最常见的是十字链表，在十字链表中，稀疏矩阵每一行用一个带头结点的循环链表表示，每一列也用一个带头结点的循环链表表示。在这个结构中，除头结点外，每个结点都代表矩阵中的一个非零元素，它由5个域组成：行域（row），列域（col），数据域（data），向下域（down）和向右域（right）。 为了使所有结点的存储结构一致，规定表头结点的结构与非零元素的结点完全一致，只是将其行域和列域设置为0，由于每一行链表的表头（行头）和每一列链表的表头（列头）的行域和列域的值均为0，故这两组表头结点可以共用，即同行号，同列号的行头和列头共同存储在一个结点中，只是将其逻辑分开（实际上行头使用该结点的向右域，而列头使用该结点的向下域），起到资源共享的效果。由此可知，稀疏矩阵的十字链表存储表示的结点总数等于非零元素的个数加上行头和列头（两者共用标号相同的结点，实际上只要提供其中的较大者的个数就可以了），再加上总表头Head[0]，其中总表头Head[0]的行域和列域分别存储矩阵的总行数和总列数，为节省空间，把矩阵非零元素的个数存储在Head[1]的行域。//------稀疏矩阵的十字链表存储表示-------------------#define MAXRC 100 //假设矩阵的行（列）数最多为100typedef struct matnode{ int row, col; //结点的行域和列域 struct matnode *right, *down;//结点的向下域（down）和向右域（right） union //结点的数据域，若为表头结点则无数值，而用指向其后继的指针代替 { ElemType data; struct matnode *next; } tag;} CrossNode, *CrossList;//---------------------------------------------------------------------------------创建一个十字链表voi......
我所理解的矩阵02(2006-01-10 21:32:00)
摘要：在实际应用中，我们经常碰到这样一类矩阵，它们的非零元素很少，而且分布没有规律，我们称之为稀疏矩阵。很显然，若用二维数组存储稀疏矩阵，将浪费大量的时间和空间。因此我们对稀疏矩阵一般采取压缩存储的方法，即只存储其非零元素。常用的数据结构有三元组顺序表 和十字链表。 我们先来看三元组顺序表。//------稀疏矩阵的三元组顺序表存储表示-------------------#define MAXSIZE 1000 //假设非零元素的个数最多为1000个 typedef struct{ int x, y; //该非零元素的行下标和列下标 ElemType e; //该非零元素的值 } Triple;typedef struct{ Triple data[MAXSIZE+1];//非零元素三元组顺序表data[0]未用 int mu, nu, tu; //矩阵的行数，列数和非零元素的个数 } TSMatrix;在此，data域中表示非零元素的三元组是以行序为主序顺序排列的，这为我们的某些计算将带来方便。创建一个三元组TSMatrix CreateTriple(int m, int n) //构造一个三元组顺序表存储矩阵{ TSMatrix T; int i=0; puts("请按行序为主序依次输入矩阵的非零元素的行号，列号和元素值，每行输入一个元素的信息："); printf("注意行号不能超过%d,列号不能超过%d\n", m, n); do { i++; &nb......
我所理解的矩阵01(2006-01-10 21:30:00)
摘要：矩阵应用系列 矩阵是很多科学与工程计算问题中研究的数学对象。我这里主要是提供一些矩阵的计算方法和用不同方式存储矩阵元进行计算时算法的比较。 矩阵的存储方式很多，最为常见的是用二维数组来存储矩阵元；但是在处理稀疏矩阵时，这种存储方法会浪费大量的时间和空间，一般采用三员组和十字链表的方法来存储。我将依次讲解这三种方法的不同特点。 首先是最为常见的二维数组存储法。这种存储方法形式简单明了，进行各种计算时算法也很容易理解。矩阵的常见计算有求转置矩阵，求逆矩阵，矩阵的加法和乘法。void CreateArray(int H[][N], int m, int n) //构造一个二维数组存储矩阵 { int i, j; for(i=0; i<m; i++) for(j=0; j<n; j++) H[i][j] = rand()%4;}void PrintArray(const int H[][N], int m, int n) //输出二维数组存储矩阵 { int i, j; for(i=0; i<m; i++) { for(j=0; j<n; j++) printf("%6d ", H[i][j]); printf("\n"); }}
1。转置矩阵转置是一种最简单的矩阵运算，对于一个m*n的矩阵Amn，其转置矩阵是一个n*m的矩阵Bnm，且B[j][i] = A[i][j]，0<=i<m, 0<=j<n，其函数如下；void trsmat(const int A[][N], int B[][N], int m, int n) { int i, j; for(i=0; i<m; i++) for(j=0; j<n; j++) B[j][i] = A[i][j];}
2。矩阵相加两个大小均为m*n的矩阵的元素相加后得到一个m*n的矩阵C，其运算是把A与B的相同位置的元素相加得到C，即Cij......