博文
用队列实现的带度数的后根次序恢复树(2007-05-02 21:57:00)
摘要：
用队列实现的带度数的后根次序恢复树
算法思想：
从左向右扫描数组，每遇到一个结点都进队列，当结点度数degree不为0时，则从队列中出degree个结点作为其子结
点，由于是先进先出，出队列的顺序正好是从左到右的子树顺序。
但要注意，出队列的结点应是队列中最后的degree个，所以要不断进行出队列、入队列操作直到找到正确的子结点。
//queue.cpp#include"iostream.h"#include"math.h"class BinNode{public: BinNode(char e) { left=NULL; right=NULL; elem=e; } char elem; BinNode* left; BinNode* right;};class Queue{public: BinNode* *listarray; int size; int front; int rear;// int queuenum; Queue(int n) { size=n; front=rear=0; listarray=new BinNode*[size]; } ~Queue() { delete [] listarray; } bool isEmpty......
并归排序算法和优化后的算法(2007-05-02 21:49:00)
摘要：// merge sort in C++// 并归排序算法和优化后的算法//作者：Andyhou#include <iostream>using namespace std;
const int THRESHOLD=9;class intCompare{public: static bool it(int x,int y) { return x<y; } static bool gt(int x,int y) { return x>y; } static bool eq(int x,int y) { return x==y; }};
template<class Elem,class Compare>class Merge{private: Elem* array; int arraySize; void inssort(Elem A[],int n); void swap(Elem A[],int i,int j);public: void mergesort1(Elem A[],Elem temp[],int left,int right); void mergesort2(Elem A[],Elem temp[],int left,int right); void print(Elem A[],int n);};
template<cla......
内部排序算法比较(2007-05-02 16:44:00)
摘要：排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较．
问题分析和总体设计
ADT OrderableList{数据对象：D={ai| ai∈IntegerSet，i=1，2，…，n，n≥0}数据关系：R1={〈ai-1，ai〉|ai-1， ai∈D， i=1，2，…，n}基本操作：InitList(n)操作结果：构造一个长度为n，元素值依次为1，2，…，n的有序表。Randomizel(d，isInverseOrser)操作结果：随机打乱BubbleSort( )操作结果：进行起泡排序InserSort( )操作结果：进行插入排序SelectSort( )操作结果：进行选择排序QuickSort( )操作结果：进行快速排序HeapSort( )操作结果：进行堆排序ListTraverse(visit( ))操作结果：依次对L种的每个元素调用函数visit( )}ADT OrderableList
待排序表的元素的关键字为整数.用正序，逆序和不同乱序程度的不同数据做测试比较，对关键字的比较次数和移动次数(关键字交换计为3次移动)进行测试比较.要求显示提示信息，用户由键盘输入待排序表的表长(100-1000)和不同测试数据的组数(8-18).每次测试完毕，要求列表现是比较结果.要求对结果进行分析.
详细设计1、起泡排序算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好
bubblesort(struct rec r[]，int n){int i，j;struct rec w;unsigned long int compare=0，move=0;for(i=1;i<=n-1;i++)for(j=n;j>=i+1;j--){if(r[j].key<r[j-1].key){w=r[j];r[j]=r[j-1];r[j-1]=w;move=move+3;}compare++;}printf("BubbleSort compare= %ld，move= %ld"，compar......
一种极为有趣算法 摇头丸排序法 (2007-05-01 07:56:00)
摘要：普通的冒泡排序法,在一次循环中,只把最小的元素排到数组的顶部,而摇头丸排序法则在一次循环中,把最小元素排到顶部,并把最大的元素排到底部.下面是实现代码: #include <iostream>
using namespace std;
template <class T> void Swap( T &t1, T &t2 ) { T temp; temp = t1; t1 = t2; t2 = temp; }
int iArray[10] = { 8, 4, 3, 6, 2, 9, 1, 7, 0, 5 };
void Display( int a[], int iSize ) { for ( int i = 0; i < iSize; ++i ) cout << a[i]; cout << endl; }
void Sort( int a[], int iSize ) { int i,j; int temp = 0; int iIndexMax;
for ( i = 0; i < iSize; ++i ) { iIndexMax = iSize - i - 1;
for ( j = iSize - i - 1; j > i; --j ) { if ( a[j] < a[j-1] ) //把最小元素排到顶部 Swap( a[j], a[j-1] ); if ( a[j] > a[iIndexMax] ) //把最大元素排到底部 iIndexMax = j; } Swap( a[iSize - i - 1], a[iIndexMax] ); Display( a, iSize ); } }
int main() { Display( iArray, 10 ); Sort( iArray, 10 ); Display( iArray, 10 ); return 0; }
整个算法,就像把最小元素和最大元素摇到数组的两头
可是它的时间代价为多少呢,它是否比冒泡排序法更快呢?
转http://bbs.csai.cn/......
《栈的计数》问题的算法分析(2007-04-29 13:00:00)
摘要：
问题转述：
求一列共n辆的火车按顺序通过一个栈所产生的排列总数。
分析：
这一类组合计数题目显然不能用搜索的方法把所有可能的移动方案都穷举出来再统计总数──这样做时间复杂度极大。这道题与经典的HANOI问题很相似，所以应当根据问题本身的性质，利用组合数学的原理，将原问题转化为递归形式，找到计算总数的递归方程，再进行计算。
摘要：
算法一
算法二
算法三
算法
递推
递推
Catalan数
时间复杂度
O(n2)
O(n2)
O(n)
空间复杂度
O(n)
O(n2)
O(1)
算法一：
我们不妨直接设n辆火车产生的排列总数为f(n)。看看能不能找到一些规律。 如图,n列火车通过栈,起始车头在车列最前端。经过移动后,车头处在了第a+1位,车头前有a辆车,车头后有b辆车(a>=0,b>=0)。则n=a+b+1,b=n-a-1。
若要达到上述移动目的,步骤为:
(1) 将车头进栈;
(2) 将车头后a辆车依次通过栈，移至轨道另一端；
(3) 将车头出栈，则车头恰好排在第a+1位；
(4) 将轨道右端剩余b辆车依次通过栈，移至轨道另一端；
不难证明，移动方案仅此一种。问题是每个步骤又有许多种不同的移动方法。显然步骤（1）（3）各只有一种移动方法。仔细观察步骤（2）（4）。我们前面定义了“n辆火车依次通过栈产生的排列总数为f(n)”，而步骤（2）恰恰是这个问题的子问题。即步骤二可写为“将a辆火车依次通过栈”，根据前面定义，其移动方案总数为f(a)。同理，步骤(4)的移动方法总数为f(b)。
根据乘法原理，要完成上述工作：
总的方法数tot=步骤(1)的方法数*步骤(2)的方法数*步骤(3)的方法数*步骤(4)的方法数
=1* f(a) * 1* f(b)
=f(a) * f(b)
=f(a) * f(n-a-1) (因为b=n-a-1)
我们目前已求......
c++中const的用法详解(2007-04-29 12:55:00)
摘要：
原创作者: 晁智平 如转贴请保留此行
const是用于保护程序的健壮性，减少程序隐患。const的用法比较复杂，总结起来又分为以下两种:1:在定义变量时使用:
a: const int a=100; 最简单的用法，说明变量a是一个常变量; b: int const b=100; 与a功能相同; c: const int *a=&b; 指向常数的指针，即指针本身的值是可以 改变的，但指向的内容是不能改变的; d: int const *a=&b; 与c功能相同; e: int * const a = &b; 常指针，即指针本身的值是不可改变的， 但指向的内容是可改变的; f: const int * const a = &b;指向常数的常指针,即指针本身与 指向的内容都是不可改变的; g: const int &a=100; 常数引用,即不能改变引用的值; 总结: 在使用const定义变量时，一定要进行初始化操作,在操作 符(*,&)左边的修饰的是指向的内容，在右边的是本身。 2:在函数用使用:
a: void func(const int a); 做为参数使用，说明函数体内是不 能修改该参数的;对不参数定义时不同的形式，可参见定义变量 时使用方式;&......
C++中虚析构函数的作用(2007-04-29 12:44:00)
摘要：我们知道，用C++开发的时候，用来做基类的类的析构函数一般都是虚函数。可是，为什么要这样做呢？下面用一个小例子来说明： 有下面的两个类：
class ClxBase{public: ClxBase() {}; virtual ~ClxBase() {}; virtual void DoSomething() { cout << "Do something in class ClxBase!" << endl; };};class ClxDerived : public ClxBase{public: ClxDerived() {}; ~ClxDerived() { cout << "Output from the destructor of class ClxDerived!" << endl; }; void DoSomething() { cout << "Do something in class ClxDerived!" << endl; };};
代码
ClxBase *pTest = new ClxDerived;pTest->DoSomething();del......
排列组合问题的通用算法(2007-04-29 12:37:00)
摘要：尽管排列组合是生活中经常遇到的问题，可在程序设计时，不深入思考或者经验不足都让人无从下手。由于排列组合问题总是先取组合再排列，并且单纯的排列问题相对简单，所以本文仅对组合问题的实现进行详细讨论。以在n个数中选取m(0<m<=n)个数为例，问题可分解为：1. 首先从n个数中选取编号最大的数，然后在剩下的n-1个数里面选取m-1个数，直到从n-(m-1)个数中选取1个数为止。2. 从n个数中选取编号次小的一个数，继续执行1步，直到当前可选编号最大的数为m。很明显，上述方法是一个递归的过程，也就是说用递归的方法可以很干净利索地求得所有组合。下面是递归方法的实现：/// 求从数组a[1..n]中任选m个元素的所有组合。/// a[1..n]表示候选集，m表示一个组合的元素个数。/// b[1..M]用来存储当前组合中的元素, 常量M表示一个组合中元素的个数。void combine( int a[], int n, int m, int b[], const int M ){ for(int i=n; i>=m; i--) // 注意这里的循环范围 { b[m-1] = i - 1; if (m > 1) combine(a,i-1,m-1,b,M); else // m == 1, 输出一个组合 { for(int j=M-1; j>=0; j--) cout << a[b[j]] << " "; cout << endl; } }}
因为递归程序均可以通过引入栈，用回溯转化为相应的非递归程序，所以组合问题又可以用回溯的方法来解决。为了便于理解，我们可以把组合问题化归为图的路径遍历问题，在n个数中选取m个数的所有组合，相当于在一个这样的图中（下面以从1,2,3,4中任选3个数为例说......
C++内存管理基础之new & delete(2007-04-29 12:35:00)
摘要：
内存管理的基础是要知道怎么获得以及释放内存，如你所知，在C/C++中就是调用new和delete操作。1. 分清operator new和new operator 全局函数operator new通常这样声明：void * operator new(size_t size);返回值类型是void*，表示其返回的是一个未经处理（raw）的指针，指向未初始化的内存。参数size_t确定分配多少内存。你能增加额外的参数重载函数operator new，但是第一个参数类型必须是size_t。头文件<new>中有一个很好的重载的例子，那就是placement new，它看上去象这样：void * operator new(size_t, void *location){ return location;}这初看上去有些陌生，但它却是new操作符的一种常见重载方法，使用一个额外的变量buffer，当new操作符隐含调用operator new函数时，把这个变量传递给它。被调用的operator new函数除了持有强制的参数size_t外，还必须接受void*指针参数，指向构造对象占用的内存空间。未被使用的（但是强制的）参数size_t没有参数名字，以防止编译器警告说它未被使用。在使用placement new的情况下，调用者已经获得了指向内存的指针，因为调用者知道对象应该放在哪里。placement new需要做的就是返回传递给它的指针。 我们更经常使用的new是new操作符(new operator)，而非操作符new(operator new)，如当你使用new操作符构建一个对象的时候，实际上做了两件事情，一是调用operator new函数获取内存，二是调用对象的构造函数，如：string *ps = new string("Hello, world!");它完成与下面代码相似的功能：void *memory = operator new(sizeof(string)); // 为String对象得到未经处理的内存call string::string("Hello, wor......
建立C/C++算法群35814549(2007-04-29 10:48:00)
摘要： 最近我建立一个计算机C/C++算法的群。欢迎大家加入共同的学习35814549。......