1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | template <class T> class Queue { public: Queue(int size = 30); ~Queue(); void EnQueue(T value); T DeQueue(); T GetFirst(); bool IsEmpty(); bool IsFull(); void ClearQueue(); private: T *queue; int front; int rare; int MaxSize; int CurLen; }; |
一个堆栈类模板，和用到此模板的一个表达式计算器。
输入四则运算表达式（可含括号），输出计算结果，暂未提供盛放运算和浮点数功能。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class Stack { public: Stack(int stack_size = 30); ~Stack(); void Push(T value); T Pop(); T Top(); bool IsEmpty(); bool IsFull(); void ClearStack(); private: int top; T* stack; int size; }; |
一种遍历算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | int main() { string word; cin>>word; int len = word.length()-1; long psb = 1; for (int i = 0;i < len;i++) { psb *= 2; } int *flags = new int[len]; for (int i = 0;i < psb;i++) { int temp = i; for (int j = 0;j < len;j++) { flags[j] = temp%2; temp = temp/2; } if(i>0) { for (int j = 0;j < len;j++) { cout<<word[j]; if(flags[j] == 1)cout<<"-"; } cout<<word[word.length()-1]<<endl; } } } |
这里的内存会被正确释放吗？答案要分两方面来讨论。*pd对象本身的内存(4Byte)会不会被释放，就像上例中所说，我还是不知道。但(*pd)::pi所指向的内存肯定是打了水漂啦！因为delete看到的只是一个char*类型的pd，只会简单做一些处理(待高人讲解)，而不会调用析构函数demo::~demo()。甚至有时候它会调用其他类的析构函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <iostream> using namespace std; class demo { public: //~ 此处省略代码数行…… ~demo() { delete [] pi; } private: int * pi; }; class foo { public: ~foo(){cout<<"foo's collapsing..."<<endl; }; int main() { demo * pd = new demo; delete (foo*)pd; return 0; } |
foo童鞋真是可怜，让我们来了个借尸还魂，Orz，借刀杀人才对！
1 2 3 4 5 6 7 8 9 10 11 12 | template <class T> T Min(T x, T y) { return x < y ? x : y; } int main() { unsigned ui = 0; int a = Min(ui, 1); return 0; } |
这几行代码又有哪些错误呢?cl.exe提示说，error C2782: ‘T Min(T,T)’ : template parameter ‘T’ is ambiguous。在参数类型的确定上产生了不确定性，这是为什么呢？好吧，1会被解释成是int型的，但是我们平时不是经常把int直接传给unsigned类型的参数吗？可惜的是，此时的Min还不是一个函数，它只是一个模板而已，实例化之前尚不能完成参数的隐式转化(其实，我认为这只是编译器支持与否的问题)。同样，可以用显式特例化的方法来解决：
int a = Min
当然，还可以强制类型转换：
int a = Min(ui, (unsigned)1); 或者 int a = Min(
我能抽象出整个世界．．． 但是我不能抽象出你．．． 因为你在我心中是那么的具体．．． 所以我的世界并不完整．．． 我可以重载甚至覆盖这个世界里的任何一种方法．．． 但是我却不能重载对你的思念．．． 也许命中注定了 你在我的世界里永远的烙上了静态的属性．．． 而我不慎调用了爱你这个方法．．． 当我义无返顾的把自己作为参数传进这个方法时．．． 我才发现爱上你是一个死循环．．． 它不停的返回对你的思念压入我心里的堆栈．．． 在这无尽的黑夜中．．． 我的内存里已经再也装不下别人．．． 我不停的向系统申请空间．．． 但却捕获一个异常－－－我爱的人不爱我．．． 为了解决这个异常．．． 我愿意虚拟出最后一点内存．．． 把所有我能实现的方法地址压入堆栈．．． 并且在栈尾压入最后一个方法－－－将字符串＂我爱你，你爱我吗？＂传递给你．．． 如果返回值为真－－我将用尽一生去爱你．．． 否则－－我将释放掉所有系统资源
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /* * pre存放先序序列， * in存放中序序列， * n为结点个数， * 返回二叉树根指针 */ BTree CreateBT(Type * pre, Type * in, int n) { if(n <= 0) return NULL; BTree bt = new BTNode; Type * p; int k; bt->data = *pre; for(p = in; p < in + n; ++p) if(*pre == *p) break; k = p - in; bt->lchild = CreateBT(pre+1, in, k); bt->rchild = CreateBT(pre+k+1, p+1, n-k-1); return bt; } |
严老太，在您面前小孙孙我实在心智底下啊！一个AVL就把我整的团团转，单向右旋，单向左旋，双向旋转先左后右，双向旋转先右后左，很简单的道理，您就是不肯轻易说出来，在那转啊转的，貌似很神秘的样子！
在构造AVL树的时候，会出现插入某个节点后输不再平衡的情况，这时候只需要找到离插入点最近的、平衡因子不合法的节点，调整以此节点为根的子树(*)，使其平衡因子合法，其实就是使这棵子树(*)的高度与插入节点前相比不发生变化。具体的调整策略因具体情况而异，但原则都是一样的：首先应该明确根节点大于左孩子而小于右孩子，另外，调整后的子树(*)的根是一定会发生变化的，且变化后的子树应该满足平衡条件，即平衡因子为1，0，-1之一。
AVL是一种二叉搜索树(Binary Search Tree)，被称为平衡树(Balanced Binary Tree)，由Adelsonr Velskii 和Landis 提出并以他们的名字命名。
今天看严蔚敏老太太的数据结构，她老人家是这么描述AVL的：AVL，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差(平衡因子：BF)的绝对值不超过1。看着这么个定义很别扭，总觉得对平衡因子的要求比较弱，也可能是我悟性较弱吧，在这句话上我很是下了一番功夫……如果这样来定义的话，可能会让我更容易理解一些：
- 根的左子树和右子树的高度差的最大值为1，空树的高度为0。
- 根的左子树和右子树都是AVL树。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Match { public: Match(): repos(NULL){} Match(const string& main, const string& mod) :repos(new int[mod.size()]), m_main(main), m_mod(mod) {} ~Match() { delete [] repos; } //~ kmp搜索，默认从主串0位置处开始， //~ 匹配成功返回匹配开始的索引，否则返回-1 int strkmp(size_t pos = 0); //~ 重设主串与模式串 void reset(const string& main, const string& mod); private: int * repos; string m_main; //~ 主串 string m_mod; //~ 模式串 //~ 生成重定位的索引值 void gen_rps(); }; |