| victor's blog's profileVictor's BlogPhotosBlogLists |  Tools  Help |
|
June 12 Unicode 问答集(转）问：什么是Unicode？ 问：为什么使用Unicode？ 问：举个例子吧。 问：Unicode的优点是什么？ January 14 未熄的灯，孤独的人飞机在黑幕中开始起飞，我紧紧地靠着椅背，感受着加速所带来的快感。快感过后是一段Boring的漫长等待，选了一部史莱克来看，看完了倒头就睡……。隐隐约约听见流利的英语，眼睛慢慢张开，原来是空少在和我后面的小姐聊天，我打开窗户，阳光刺得我的眼睛难受，这个时候我听到机长告诉大家还有1个半小时将要到达目的地，我已经睡了九个多小时了！吃过早饭，飞机开始慢慢下降，穿过厚厚的云层，出现在我面前的是美丽的城市，迎接我的是新的生活。 想起马上就必须要自己租房子，自己买菜，自己烧饭，自己交电话费，自己买保险etc，才发现人是逼出来的，这好像跟平时学习差不多，我想如果没有英语考试，大家也不会去背这么多的单词吧。一下子，感觉自己成熟了好多。 我对这里还不熟，每天的在msn上和我的好朋友们聊天就变成了我最大的乐趣。Allen，Zico，Neo，Chiuchin，Cynthia，Crissy，Gogo等等，今天我找房子的时候发现一条路叫Nelson Street，突然想起Neo现在在哈尔滨，我想还要过几天才能和他接上头。 今天是周末，晚上同志们大多都不在，闲来无事再一次拜读了Allen的大作——“佛说”。感觉比上一次看更深华了一层，我想真的算是读书百遍，其义自见吧，呵呵。我相信“佛”说的话，我同时认为每一场爱情都应该是一个故事，否则就不能称之为爱情。仔细分析“爱情”两个字我得出了这样的结论：这两个字虽然是整体但又可以分解。毋庸置疑，是先有“爱”后有“情”的，why？因为我相信“爱”是一种感觉，没有理由，而“情”是在“爱”的基础上双方共同的积累，“爱”的程度又直接决定着“情”积累速度的快慢。（这再一次证明了辩证法 夜已深，大街上安静得可怕，放眼望去，还是有几盏未熄灭的灯，我想每一盏灯下都应该有一个孤独的人，他们也都应该有一个自己的故事吧！ December 08 数据结构——链式赫夫曼树以及赫夫曼编码的实现作者：张奎 Email:victory_chair@yahoo.com.cn Homepage:www.zkui.com 赫夫曼编码广泛的用于包括压缩在内的多个领域，今天将赫夫曼树和赫夫曼编码实现了一下，参考《数据结构(C语言版)》，和上次一样，这次我仍然使用模板类将数据结构进行封装，可以针对各种类型的数据进行操作，书上用的是顺序存储结构的二叉树，难免十分笨拙，我用了链式二叉树将其实现。 首先是赫夫曼编码存储的数据结构，定义如下： #define MAX_CODE_LEN 100 struct HuffmanCode{ char huffmanStr[MAX_CODE_LEN]; int lenth;//编码长度 }; 然后是赫夫曼树上结点数据结构的定义，其中data成员用于存放结点数据，权重weight我们不妨设成整型 template <class Type> class HuffmanNode{ public: int weight; Type data; HuffmanNode<Type> *parent,*lchild,*rchild; };//表示结点的数据结构 最后是封装了赫夫曼树的类，定义如下： template <class Type> class HuffmanTree{ private: HuffmanNode<Type> *root;//代表根结点，初始化时不需要动态分配 LinkList<HuffmanNode<Type> *> nodeList;//结点数组链表 LinkList<HuffmanNode<Type> *> ZKNodeList;//已经摘下的叶结点数组链表 HuffmanCode *code;//赫夫曼编码和ZKNodeList中的叶结点对应 int nodeNum;//结点数量 public: HuffmanTree(); HuffmanTree(Type *d,int *w ,int n); //代参数的构造函数,参数1代表结点数据，参数2代表结点权值指针，参数3代表数量 ~HuffmanTree();//析构函数 void Create(Type *d,int *w ,int n); //Create方法,参数1代表结点数据，参数2代表结点权值指针，参数3代表数量 void CreateHuffmanTree(); //创建赫夫曼树，参数意义与构造函数一样 HuffmanNode<Type> * SelectMin(); //从结点链中摘下最小的结点 void HuffmanCoding(); //进行赫夫曼编码 void Display(); }; 下面我们来看看赫夫曼树的构造过程 首先完成初始化工作，以Create方法为例： template <class Type> void HuffmanTree<Type>::Create(Type *d,int *w ,int n) { nodeNum = n;//得到节点个数 code = new HuffmanCode[n]; for(int i=0;i<n;i++) { HuffmanNode<Type> *node = new HuffmanNode<Type>(); node->data = d[i]; node->weight = w[i]; node->lchild = NULL; node->rchild = NULL; node->parent = NULL; nodeList.AddNode(node); } } 在这里比较关键的是初始化时孩子以及双亲指针必须全附为空值。 有了节点链后，我们就可以构造我们的赫夫曼树了，构造赫夫曼树的方法是CreateHuffmanTree，代码如下所示： template <class Type> void HuffmanTree<Type>::CreateHuffmanTree() { HuffmanNode<Type> *p,*q; for(int i=0;i<nodeNum-1;i++)//到n-1时数已经构造完成 { p=SelectMin();//p是最小值，q是次小值 q=SelectMin();//p是最小值，q是次小值 HuffmanNode<Type> *newNode = new HuffmanNode<Type>(); newNode->weight = p->weight+q->weight; newNode->lchild = p; newNode->rchild = q; newNode->parent = NULL; p->parent = newNode; q->parent = newNode; //构造完成，开始修改临时节点链 nodeList.AddNode(newNode); //如果是叶节点,压回叶节点链 if(p->lchild==NULL&&p->rchild==NULL) { ZKNodeList.AddNode(p); } if(q->lchild==NULL&&q->rchild==NULL) { ZKNodeList.AddNode(q); } } //构造完成根节点附值 root=nodeList.GetFirstNode()->data; } SelectMin方法的作用是选出当前链中最小权值的节点将其脱离链表后返回改节点，所以连续取两次，得到最小权值和次小权值的两个节点，然后在这两个节点的基础上，创建一个新节点，新节点的权值等于所得到两个节点的权值和，并且为这两个节点的父亲，注意新产生的节点不需要对data附值，因为我们并不关心data是什么。新节点产生后，将其加入到节点链的末尾，加入到末尾很关键，这样我们就可以避免在编码过程中产生相同值所带来的麻烦。最后如果节点是叶节点的话，将其压入ZKNodeList链表，我们这样做的目的是为了方便产生赫夫曼编码。
最后我们来看一看赫夫曼编码的过程，代码如下： template <class Type> void HuffmanTree<Type>::HuffmanCoding() { LNode<HuffmanNode<Type> *> *curNode = ZKNodeList.GetFirstNode(); int i=0;//代表当前的节点位置 while(curNode!=NULL) { HuffmanNode<Type> *p=curNode->data;
LStack<char> s; while(p->parent!=NULL) { if(p->parent->lchild==p)//如果是左孩子 { s.Push('0'); } else { s.Push('1'); } p=p->parent; } int j=0;//代表当前编码位置 while(!s.IsEmpty()) { code[i].huffmanStr[j]=s.Pop(); j++; } code[i].lenth=j; curNode=curNode->next; i++; } } 在这当中我们用到了堆栈，主要是应为我们是从叶子开始进行搜索的，最后将堆栈的数据弹出，我们也就会得到正确的赫夫曼编码，栈是上次做的，在此就不赘述了。
该程序在MS.NET2003下调试通过。 如果需要完整源代码，请发邮件给我，我会将他们发给您
December 07 数据结构——二叉树遍历的递归与非递归实现(2)作者：张奎 Email:victory_chair@yahoo.com.cn Homepage:www.zkui.com
（接上篇） 先序遍历，先序遍历的思想小弟总结如下： 1． 从根节点开始，首先访问根节点 2． 依次将根节点的右孩子和左孩子压进栈中 3． 开始循环，弹出栈中一个节点后进行访问，然后将其右孩子和左孩子压进栈中 4． 直到栈空为止 代码如下： template <class Type> void BinaryTreeL<Type>::PreOrderTraverse(BiTNode<Type> *T)//非递归先根遍历 { Visit(T); LStack<BiTNode<Type> *> s;//将栈设置成节点类型 BiTNode<Type> *p=T; if(p->rchild!=NULL)//先将右子树进栈 { s.Push(p->rchild); } if(p->lchild!=NULL)//然后将左子树进栈 { s.Push(p->lchild); } while(!s.IsEmpty()) { p=s.Pop(); Visit(p); if(p->rchild!=NULL)//先将右子树进栈 { s.Push(p->rchild); } if(p->lchild!=NULL)//然后将左子树进栈 { s.Push(p->lchild); } }
}
后序遍历，后序遍历稍微要复杂一些，其过程如下： 1．当前节点入栈 2．如果有左节点，左节点成为当前节点 3．如果没有左节点只有右节点，右节点成为当前节点 4．如果发现叶节点，所作的处理应该是： a.首先本节点出栈 b.访问该节点 c.取得栈顶节点，若该叶节点是栈顶节点的右孩子或者栈顶节点没有右孩子，则栈顶节点 出栈，一直到以上两条条件均不满足 d.循环完成遍历结束 代码如下： template <class Type> void BinaryTreeL<Type>::PostOrderTraverse(BiTNode<Type> *T)//非递归后根遍历 { LStack<BiTNode<Type> *> s;//将栈设置成节点类型 BiTNode<Type> *p=T; BiTNode<Type> *q; do { s.Push(p);//自己进栈 if(p->rchild!=NULL&&p->lchild==NULL) { p=p->rchild; } else if(p->lchild!=NULL) { p=p->lchild; } else if(p->lchild==NULL&&p->rchild==NULL) { q=s.Pop();//自己出栈 Visit(q); if(!s.IsEmpty()) { p=s.GetTop();//返回上一层,但暂时不出栈 while(p->rchild==q||p->rchild==NULL)//这句话十分关键 { q=s.Pop(); Visit(q); if(!s.IsEmpty()) p=s.GetTop(); else break; } //现在已经排除p->rchild是NULL的情况了 p=p->rchild;
} else break; } }while(!s.IsEmpty());
}
测试程序： 按照《数据结构（C语言版）》清华大学出版社第129页图6.9
运行结果是： 数据结构——二叉树遍历的递归与非递归实现(1)作者：张奎 Email:victory_chair@yahoo.com.cn Homepage:www.zkui.com
关键字： 二叉树 堆栈 数据结构丢了有一段时间了，这两天可能要用到，小弟捡起来看了一看，晚上心血来潮用C++实现了一颗二叉树，主要功能包括添加节点，递归遍历和非递归遍历。整个程序用模板类实现，完全实现了对整棵二叉树的封装，使用不受数据类型的限制，什么类型都可以在其中使用，现在将我整个程序拿出来，希望能和大家探讨，分享。 程序首先开始当然是定义数据结构，结构定义如下： 首先是节点类： template <class Type> class BiTNode{ public: Type data; BiTNode<Type> *lchild,*rchild; }; 然后当然是封装了二叉树的类了： template <class Type> class BinaryTreeL { public: BinaryTreeL(void); ~BinaryTreeL(void);
BiTNode<Type> *root;//约定root的左节点代表根 void AddLeftChild(BiTNode<Type> *parent, BiTNode<Type> *leftchild);//添加左孩子,可挂载另一颗树 BiTNode<Type>* AddLeftChild(BiTNode<Type> *parent, Type data);//添加左孩子,只需要填值,返回添加节点 void AddRightChild(BiTNode<Type> *parent, BiTNode<Type> *rightchild);//添加右孩子,可挂载另一颗树 BiTNode<Type>* AddRightChild(BiTNode<Type> *parent, Type data);//添加右孩子,只需要填值,返回添加节点 void Visit(BiTNode<Type> *Node);//声明访问函数,为简便起见暂时用简单地访问函数 void PreOrderTraverseRec(BiTNode<Type> *T);//递归先根遍历 void PreOrderTraverse(BiTNode<Type> *T);//非递归先根遍历 void InOrderTraverseRec(BiTNode<Type> *T);//递归中根遍历 void InOrderTraverse(BiTNode<Type> *T);//非递归中根遍历 void PostOrderTraverseRec(BiTNode<Type> *T);//递归后根遍历 void PostOrderTraverse(BiTNode<Type> *T);//非递归后根遍历 }; 在这里，我们约定root的左孩子指向根节点（可能有点混淆，呵呵） 在遍历的函数中之所以要加入参数主要是为了功能更多，可以从任何节点遍历，而不是只从根开始遍历. 然后我们来看一看各个方法的实现： 添加节点很简单的啦，我们简单看一下就好： template <class Type> BiTNode<Type>* BinaryTreeL<Type>::AddLeftChild(BiTNode<Type> *parent, Type data) //添加左孩子,只需要填值,返回添加节点 { if(parent->lchild!=NULL) { cout<<"左孩子已存在，不能添加左孩子\n"; return NULL; } BiTNode<Type> *child = (BiTNode<Type> *)malloc(sizeof(BiTNode<Type>)); child->data = data; child->lchild = NULL; child->rchild = NULL; parent->lchild = child; return child; } 这中间只涉及到一个动态分配的问题，本来想用new的，但是数据结构学了这么久，还是把malloc拿出来现一下把，就全当作回忆了.
主要讲一下非递归遍历，在非递归遍历中需要使用栈，小弟自己写了一个简易链式栈顶了一顶。 template <class Type> class QNode{ public: Type data; QNode *next; }; template <class Type> class LStack{ QNode<Type> *head; void InitStack(); public: LStack(); void Push(Type value); Type Pop(); Type GetTop(); bool IsEmpty(); }; template <class Type> LStack<Type>::LStack() { InitStack(); } template <class Type> void LStack<Type>::InitStack() { head = (QNode<Type> *)malloc(sizeof(QNode<Type>)); head->next=NULL; } template <class Type> void LStack<Type>::Push(Type value) { QNode<Type> *Node = (QNode<Type> *)malloc(sizeof(QNode<Type>)); Node->data=value; Node->next=head->next; head->next=Node; } template <class Type> Type LStack<Type>::Pop() { if(IsEmpty()) { cout<<"栈为空，不能弹出数据"; return NULL; } QNode<Type> *Node=head->next; head->next=head->next->next; return Node->data; } template <class Type> Type LStack<Type>::GetTop() { if(IsEmpty()) { cout<<"栈为空，不能取出数据"; return NULL; } QNode<Type> *Node=head->next; return Node->data; } template <class Type> bool LStack<Type>::IsEmpty() { if(head->next==NULL) return true; else return false; }
下面首先介绍继续中序遍历，中序遍历的主要思想小弟总结如下： 1. 从根节点开始，逐个搜索左孩子，并且将他们压入栈中，直到走到尽头。 2. 如果发现当前节点为空则作下面的操作 3. 从栈中将以前Push进去的节点弹出 4. 访问弹出节点，然后将当前节点设为该节点的右孩子 5. 重复该过程 代码如下： template <class Type> void BinaryTreeL<Type>::InOrderTraverse(BiTNode<Type> *T)//非递归中根遍历 { LStack<BiTNode<Type> *> s;//将栈设置成节点类型 BiTNode<Type> *p=T; while(p!=NULL||!s.IsEmpty()) { if(p!=NULL) { s.Push(p); p=p->lchild; } else { p=s.Pop(); Visit(p); p=p->rchild; } } } (未完待续。。。。）
|
）。|
|
