博文
无向图的最小支撑树Kruskal算法的实现(2008-04-28 01:26:00)
摘要：// 无向图的最小支撑树Kruskal算法的实现//主题： 用邻接表的方式实现最小支撑树Kruskal算法
//作者：Andyhou
//时间：2008年4月28日
//具体算法实现：// 采用的是最小堆的方式找最小边，用等价类的方式步步合并最小的边。// 程序中还声明了一个等价类。#include <iostream>using namespace std;
const int MaxNode=100;const int VISITED=1;const int UNVISITED=0;const int ROOT=-1;const int INFINITY=9999;
struct Node{ int adjvex; //终点顶点 int weight; //权 struct Node *next; //指向下个顶点的指针};class VNode{public: int data; struct Node* first; //指向第一个邻接顶点 VNode(){} VNode(int Data,struct Nod......
无向图的最小支撑树Prim算法的实现(2008-04-28 00:45:00)
摘要：// 无向图的最小支撑树Prim算法的实现//主题：实现最小支撑树的算法
//作者：Andyhou
//时间：2008年4月27日
//具体重要算法：// 采用了最小堆来实现取最小边，定义了一个边的类。// Prim算法的具体实现。// 顶点的存储都是从1开始。#include <iostream>using namespace std;
const int MaxNode=100;const int VISITED=1;const int UNVISITED=0;
struct Node{ int adjvex; //终点顶点 int weight; //权 struct Node *next; //指向下个顶点的指针};class VNode{public: int data; struct Node* first; &nb......
有向图的邻接表的建立和个类算法的实现(2008-04-26 15:58:00)
摘要：// 有向图的邻接表的建立和个类算法的实现//主题：用邻接表的方式实现有向图的一些算法
//作者：侯永华
//时间：2008年4月26日
//内容：具体实现：创建向图的邻接存储方式。打印邻接表的个顶点数据， //建立邻接表 void CreateAdj(); //打印邻接表 //void printAll(); //删除邻接表 //void Del(); //深度优先搜索 //void DFS(int V); //广度优先搜索 //void BFS(int V); //队列实现拓扑排序 //void TopSortQueue(); //递归的拓扑排序 //void TopSortbyDFS(); //void Do_topsort(int V,int *result,int &tag); //Dijkstra算法的实现 //void Dijkstra(int s); //Floyd算法的实现 //void Floyd(Dist** &D); //其中很多用到的辅助的类，堆的方式在程序中都写出来了。用到队列的才用的VC中自带的队列。//任务：测试所有数据的正确性。//注意：本程序没有采用头文件形式，所有的节点存储都是从1开始的。
#include <iostream>#include <queue>using namespace std;
const int MaxNode=100;const int VISITED=1;const int UNVISITED=0;con......
数据结构中的关于拉链的举例(2008-04-11 00:55:00)
摘要： 数据结构中的关于拉链的举例
作者：andyhou
这几天在复习数据结构没事编程练习写点东西。好久没动手有点生疏了。呵呵！！
在数据结构中有很多的地方都涉及都拉链来解决问题。虽然我们每个人对这个很熟悉。但是也有很多人看似觉得很简单。就是从一个数组中拉一条链出来存储一些数据，但是到了真正实现的时候却不知道怎么下手，似乎也觉得很麻烦，而且写出来的程序错误很多。对指针的控制也不知道怎么下手。我自己写的这个程序程序很多的需要拉链的地方都可以模仿的使用。
程序说明：这个程序是把所输入的数据的个位数都存放在一个基数相同位置拉出来的地方
并且对这些数据的查找和打印。程序很容易理解所以没有什么注释应该很
容易看懂。
#include <iostream>using namespace std;
const int r=10;//基数const int N=20; //设置数组长度
struct Node{ int element; Node *next;};
//初始化void Init(struct Node *Array,int r){ for(int i=0;i<r;i++) { Array[i].element=i; Array[i].next=NULL; }}
void Insert(struct Node *Array,int &item){ int R; struct Node *temp=new struct Node; struct Node *T; temp->element=item; R=item%10; if(Array[R].next==......
基于静态链的基数排序（C++）(2008-04-09 17:04:00)
摘要： 基于静态链的基数排序（C++）
基于链表的实现主要是将分配出来的子序列存放在r个（静态链组织的）队列中，在数组中设置next段。
#include <iostream>using namespace std;const int N=20;const int r=10;
//节点类class Node{public: int key; int next;};
//静态队列类class StaticQueue{public: int head; int tail;};
template <class Record>class LinkRadixSorter{private: void Distribute(Record *Array,int first,int i,int r,StaticQueue* queue); //分配过程 void Collect(Record* Array,int &first,int i,int r,StaticQueue* queue); //收集过程 void PrintArray(Record* A,int first); //输出序列public: void Sort(Record* Array,int n,int d,int r);};
template<class Record>void LinkRadixSorter<Record>::Sort(Record* Array,int n,int d,int r){ int first=0; StaticQueue* queue; queue=new StaticQueue[r]; for(int i=0;i<n;i++) Array[i].next=i+1;&nb......
败者树的实现（c++)(2008-04-05 19:38:00)
摘要：#include <iostream.h>#include <stdlib.h>#include <stdio.h>#include <time.h>#include <string.h>
#define MAX_BUFFER 512 //buffer最大容量#define NO_MEANING 99999999 //当某顺串已经全部处理完时，给败方树外部节点填充这个超大值#define MAX 10 //最大选手数目
/********************* 缓冲区类，用环状数组实现的队列来实现之 ********************///设置头指针front，尾指针rear//插入在rear处，删除在front处template <class Elem> class Buffer{ private: Elem * buf; //存放元素的数组 int front, rear; int n; //buffer中当前元素的数目 public: //constructor Buffer(){ buf = new Elem [MAX_BUFFER]; front = 0; rear = 0; n = 0; }
//destructor ~Buffer(){ delete buf; }
//判断buffer是否为空 bool isEmpty(){ return (n==0); }
//判断buffer是否满 bool isFull(){ ......
排序算法的实现(2008-03-29 19:14:00)
摘要：// 排序算法的实现#include <iostream>using namespace std;
//插入排序void swap(int Array[],int i,int j){ int temp=Array[i]; Array[i]=Array[j]; Array[j]=temp;}void InsertSort(int Array[],int n){ for(int i=1;i<n;i++) { for(int j=i;j>0;j--) { if(Array[j]<Array[j-1]) swap(Array,j,j-1); else break; } }}//优化插入排序void ImprovedInertSorter(int Array[],int n){ int Temp; for(int i=1;i<n;i++) { Temp=Array[i]; int j=i-1; while((j>=0)&&(Temp<Array[j])) { Array[j+1]=Array[j]; j=j-1; } Array[j+1]=Temp; }}//二分法插入排序void BinaryInsertSorter(int Array[],int n){ int temp; int left,right,middle; for(int i=1;i<n;i++) { temp=Arr......
平衡二叉树源码(2007-10-11 21:59:00)
摘要：
#include <stdio.h>
typedef struct bitreetype { int item; int bdegree;/*平衡因子,左子树深度-右子树深度*/ struct bitreetype *lchild; struct bitreetype *rchild; }bitree;
typedef struct treequeuetype { int head; int tail; bitree *items[1000]; }treequeue;/*定义一个队列,后面的平衡调整要用层序遍历,于是要用这个队列*/
void resetqueue(treequeue *queue) { queue->head=-1; queue->tail=-1; return; }/*把队列清空*/void inqueue(treequeue *queue,bitree *element) { queue->tail++; queue->items[queue->tail]=element; }/*入队列*/bitree *outqueue(treequeue *queue) { queue->head++; return queue->items[queue->head]; }/*出队列*/int isqueueempty(treequeue *queue) { if(queue->head==queue->tail) return 1; else return 0; }/*判断队列是否为空*/void fillmemory(char *source,int len,char content) { while(len) { source=source+len;......
平衡树与非平衡树(2007-10-11 21:33:00)
摘要：左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的）。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。几种主要的二叉平衡树：红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。红黑树有两个特征：(1) 节点都有颜色(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。红黑规则：1. 每一个节点不是红色的就是黑色的2. 根总是黑色的3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置）AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：(1) 其根的左右子树高度之差的绝对值不能超过1；(2) 其根的左右子树都是二叉平衡树。AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。AVL树插入的C++代码：
template <class T>ResultCode AVLTree<T>::Insert(AVLNode<T> * &p,T &x,bool &unBalanced)...{ ResultCode result=Success;&nbs......
Hash_Table（散列表）(2007-10-05 16:14:00)
摘要： 最近在学习散列。学的很迷糊。我就找了个别人编的程序看看。
以下代码仅在 g++ 3.4.2中编译通过，令人惊奇的是VC 2005竟然编译出错，看来以后用VC 2005还得小心才行。
//结点类型template <typename T, typename Tar>struct node...{ T data; Tar value; node* next; //初始化为空 node() : value(0), next(NULL) ...{}};//Hash表//第一个类型参数的类型可以是：int, long, char, string//第二个类型参数的类型可以是：int, bool, char//此Hash表支持的操作有：//insert(T x)：将类型为T的元素插入hash表中，如果已存在则直接退出//search(T x)：查找是否存在值为x的元素（返回bool型）//remove(T x)：将值为x的元素从表中删除//对于[]的重载：返回value域的引用template <typename T, typename Tar>class Hash_Table...{private: static const int size......