谁有MinHeap.h,UFSet.h,等头文件啊，能传给我吗，网上找不到啊， geninsf009 写的算法里有包含这些头文件，但我找不到，大家帮帮我啊
yeahxiaoxl@

[[it] 本帖最后由 xiaoxl 于 2008-10-23 14:34 编辑 [/it]]

我有，我贴给你，直接问我要不就得了:)

[[it] 本帖最后由 geninsf009 于 2008-10-23 14:38 编辑 [/it]]

我给你发了消息还有邮件啊，还以为你不在呢，你能传我邮箱里吗，谢谢你了，

MinHeap.h文件，这是我写的最小堆的类模板，
ps：发觉这个数据结构很有用，在huffman编码，最小生成树中都用到了，
所有成员函数的代码全部通过测试，放心使用:

#ifndef MINHEAP_h
#define MINHEAP_H

#include<iostream.h>
#include<stdlib.h>

#define DefaultSize 20

////////////////////////////////////////////////////////
//MinHeap堆类  最小堆的声明和定义
//即以完全二叉树的顺序存储方式来实现优先级队列
//T为关键码的类型,E为元素结点数据域的类型
////////////////////////////////////////////////////////
template<class T,class E>       //T为关键码的类型,E为元素结点的类型
class MinHeap
{
public:
    MinHeap(int sz=DefaultSize);//构造函数,建立一个空堆
    MinHeap(E* arr,int n);      //构造函数,通过数组来建堆
    ~MinHeap()                  //析构函数,释放堆的内存空间
    {delete [] heap;};
    bool Insert(const E& x);    //将元素x插入到最小堆中
    bool RemoveMin(E& x);       //删除堆顶的最小元素
    bool IsEmpty()const         //判断当前堆是否为空
    {return currentSize==0;};
    bool IsFull()const          //判断当前堆是否为满
    {return currentSize==maxHeapSize;};
    void MakeEmpty()            //把当前堆置空
    {currentSize=0;};     
    void Display();             //显示当前堆的内容
    void siftDown();            //下浮全部调整
    void siftUp();              //上浮全部调整

private:
    E* heap;                    //存放最小堆中元素的数组的首指针
    int currentSize;            //最小堆中当前元素的个数
    int MaxHeapSize;            //最小堆中最多允许的元素的个数
    void siftDown(int start,int m);//从start到m下滑调整成为最小堆
    void siftUp(int start);     //从start到0上滑调整成最小堆
    //友元重载运算浮输出堆的内容
    friend ostream& operator<<(ostream& os,MinHeap<T,E> MH);
};
///////////////////////////////////////MinHeap类声明结束

////////////////////////////////////////////////////////
//构造函数
//建立一个空的最小堆,并在定义的是否指定堆的尺寸大小
//T为关键码的类型,E为元素结点的类型
////////////////////////////////////////////////////////
template<class T,class E>
MinHeap<T,E>::MinHeap(int sz)
{
    //设定堆的最多允许的元素的个数
    MaxHeapSize=(DefaultSize<sz)?sz:DefaultSize;
    //为堆的顺序存储结构开辟内存空间
    heap=new E[MaxHeapSize];
    //如果内存分配失败
    if(heap==NULL)
    {
        cout<<"最小堆的内存分配失败!"<<endl;
        exit(1);
    }
    //刚开始堆中的元素的个数是0个
    currentSize=0;
};
////////////////////////////////////////////构造函数结束

////////////////////////////////////////////////////////
//带参数的构造函数
//通过数组中的元素、来创建一个堆
////////////////////////////////////////////////////////
template<class T,class E>
MinHeap<T,E>::MinHeap(E* arr,int n)
{
    //得到最大允许的元素的个数
    MaxHeapSize=(DefaultSize<n)?n:DefaultSize;
    //开辟最小堆的内存
    heap=new E[MaxHeapSize];
    //如果内存分配失败
    if(heap==NULL)
    {
        cout<<"最小堆的内存分配失败!"<<endl;
        exit(1);
    };
    //把参数数组中的元素一次复制到堆中
    currentSize=0;
    for(int i=0;i<n;i++)
        Insert(arr[i]);    
};
////////////////////////////////////带参数的构造函数结束

////////////////////////////////////////////////////////
//siftDown()私有成员函数
//从start到m下滑调整成为最小堆
//下滑调整的前提是当前结点的左右子树都已经成堆
////////////////////////////////////////////////////////
template<class T,class E>
void MinHeap<T,E>::siftDown(int start,int m)
{
    int i=start;          //i从start开始调整
    int j=2*i+1;          //用于指向要和i对调的结点,先指向i的左子结点
    E temp;               //交换时用到的中间结点
    while(j<=m)           //到m时调整结束
    {                     //如果至少有一个子结点小于根结点,则需要调整
        if(heap[j]<heap[i] || heap[j+1]<heap[i])
        {                 //如果左子结点大于右子结点
            if(heap[j]>heap[j+1])
                j=j+1;    //跟较小的子结点进行位置调整
                          //如果根根结点更大,则要进行调整
            if(heap[i]>heap[j])
            {
                //交换Heap[i]和Heap[j]的数据内容
                temp=heap[i];
                heap[i]=heap[j];
                heap[j]=temp;
            }
            i=j;          //还有从刚对调完的子结点继续调整下去
            j=2*i+1;
        }
        else
            break;
    };
};         
//////////////////////////////////////siftDown()函数结束

////////////////////////////////////////////////////////
//siftDown()公有成员函数
//对堆进行全部的下浮调整,只针对所有分支结点从后往前即可
////////////////////////////////////////////////////////
template<class T,class E>
void MinHeap<T,E>::siftDown()
{
    //找到最后一个还有子结点的结点
    int currentPos=(currentSize-2)/2;
    //从当前的currentPos依次向前进行下滑调整
    while(currentPos>=0)
    {
        //局部自上而下地下滑调整
        siftDown(currentPos,currentSize-1);
        //再向前换一个分支结点
        currentPos--;
    };
};
//////////////////////////////////////siftDown()函数结束

////////////////////////////////////////////////////////
//siftUp()私有成员函数
//从start开始向上调整到根结点(0)
//利用了一个子结点都至多有一个父结点的特性
////////////////////////////////////////////////////////
template<class T,class E>
void MinHeap<T,E>::siftUp(int start)
{
    int i=start;           //从i结点开始向上浮动调整
    int j;                 //指向要调整的父结点
    E temp;                //交换用的临时变量

    while(i>0)
    {
        //得到当前结点i的父结点的指针
        if(i%2==1)         //如果i是奇数结点   
            j=(i-1)/2;     //说明i是j的左子结点
        else
            j=(i-2)/2;     //说明i是j的右子结点
        
        if(heap[i]<heap[j])//如果子结点小于父结点
        {
            //交换Heap[i]和Heap[j]的数据内容
            temp=heap[i];
            heap[i]=heap[j];
            heap[j]=temp;
        }
        i=j;               //继续上浮调整
    }
};
////////////////////////////////////////siftUp()函数结束

////////////////////////////////////////////////////////
//siftUp()公有成员函数
//对堆进行全部的上浮调整,即堆所有的叶子结点从后往前调整
////////////////////////////////////////////////////////
template<class T,class E>
void MinHeap<T,E>::siftUp()
{
    //通过上浮的方法来调整堆
    //从最后一个结点进行上浮调整
    int currentPos=currentSize-1;
    //从后往前调整到第一个叶子结点就可以了
    int end=currentSize-int((currentSize-1)/2)-1;   
    //从后往前对每个叶子结点进行上浮调整
    while(currentPos>=end)
    {
        siftUp(currentPos);
        currentPos--;
    };
};
////////////////////////////////////////siftUp()函数结束

////////////////////////////////////////////////////////
//Display()公有成员函数
//显示当前堆序列的内容
////////////////////////////////////////////////////////
template<class T,class E>
void MinHeap<T,E>::Display()
{
    //显示堆的内容
    for(int i=0;i<currentSize-1;i++)
        cout<<heap[i]<<" ";
};
///////////////////////////////////////Display()函数结束

////////////////////////////////////////////////////////
//友元重载输出运算符<<输出当前堆的内容
////////////////////////////////////////////////////////
template<class T,class E>
ostream& operator<<(ostream& os,MinHeap<T,E> MH)
{
    //显示堆中的内容
    for(int i=0;i<MH.currentSize;i++)
        os<<MH.heap[i]<<" ";
    cout<<endl;

    return os;
};
//////////////////////////////////////////<<友元重载结束

////////////////////////////////////////////////////////
//Insert()公有成员函数
//在堆的尾部插入一个元素,并进行重新调整
////////////////////////////////////////////////////////
template<class T,class E>
bool MinHeap<T,E>::Insert(const E& x)
{
    //如果堆中的元素已经满了
    if(currentSize==MaxHeapSize)
    {
        cout<<"堆的空间已经满了!"<<endl;
        return false;
    }
    //把新元素先放在最后一个位置
    heap[currentSize]=x;
    currentSize++;

    //对堆进行重新调整,只要对最后一个结点作一次上浮调整即可
    siftUp(currentSize-1);
    return true;
};
////////////////////////////////////////Insert()函数结束

////////////////////////////////////////////////////////
//RemoveMin()公有成员函数
//删除堆顶的最小的结点,并进行再次调整
//(只需对新堆顶作一次下沉调整即可)
////////////////////////////////////////////////////////
template<class T,class E>
bool MinHeap<T,E>::RemoveMin(E& x)
{
    //如果堆中的元素已经没有了
    if(currentSize==0)
    {
        cout<<"堆中已经没有元素了!"<<endl;
        return false;
    }
    //删除堆顶的元素
    x=heap[0];
    //把最后一个元素替换到堆顶的位置
    heap[0]=heap[currentSize-1];
    //现存的元素个数减一
    currentSize--;
    //对堆顶元素作一次下沉调整即可
    siftDown(0,currentSize-1);
    return true;
};
/////////////////////////////////////RemoveMin()函数结束

#endif

这是我写的并查集的类模板的实现，里面包含了等价类的划分的算法，
这个数据结构在Cruskal算法中用于判断两个顶点是否出于同一个连同分量中，
起到了很好的作用:


UFSet.h文件：
代码如下：
#ifndef UFSET_H
#define UFSET_H

#include<iostream.h>
#include<stdlib.h>
#include<cmath>

#define defaultSize 20

///////////////////////////////////////////////////
//Relative等价关系描述结构
///////////////////////////////////////////////////
struct Relative
{
    int left;     //等价关系左值
    int right;    //等价关系右值
};
///////////////////////////////Relative结构描述结束

///////////////////////////////////////////////////
//并查集合UFSet类的声明和定义
//该集合中,其每个子集都互不相交
//根结点对应的parent数组的值是元素的个数
///////////////////////////////////////////////////
class UFSet
{
public:
    //构造函数
    UFSet(int sz=defaultSize);
    //析构函数
    ~UFSet(){delete [] parent;};
    //重载=赋值运算符
    UFSet& operator=(UFSet& R);
    //把子集Root1和Root2合并
    void Union(int Root1,int Root2);
    //搜索集合x的根
    int findRoot(int x);
    //加权的合并算法
    void WeightedUnion(int Root1,int Root2);
    //折叠算法,对集合树进行折叠优化,使深度减小
    int CollapseFind(int i);
    //根据给定的等价关系,对当前集合求等价类
    void FindEqualClass(Relative* Rel,int n);

    //以集合描述字符串的形式来显示当前的并查集
    void Display();

private:
    int *parent;     //集合元素的父指针数组
    int size;        //当前集合元素的个数
};
////////////////////////////////////UFSet类声明结束

///////////////////////////////////////////////////
//构造函数
//起初每个元素本身构成一个子集并且互不相交
///////////////////////////////////////////////////
UFSet::UFSet(int sz)
{
    //初始化集合元素个数
    size=sz;
    //为集合元素父结点数组开辟内存空间
    parent=new int[size];
    //起初是所有的元素都是一个子集
    for(int i=0;i<size;i++)
        parent[i]=-1;
};
///////////////////////////////////////构造函数结束

///////////////////////////////////////////////////
//Union()公有成员函数
//把集合Root1和集合Root2合并
///////////////////////////////////////////////////
void UFSet::Union(int Root1,int Root2)
{
    //首先判断Root1和Root2是否超出集合的范围
    if(Root1>=size || Root2>=size)
    {
        cout<<"两个集合已经超出了范围!"<<endl;
        exit(1);
    };
    //可以把Root2集合树根结点作为Root1的子结点
    
    //集合Root1的结点个数要加上原来Root2集合中元素的个数
    parent[Root1]=parent[Root1]+parent[Root2];   
    //把Root2的父结点改成Root1
    parent[Root2]=Root1;
};
////////////////////////////////////Union()函数结束

///////////////////////////////////////////////////
//成员重载=赋值运算符
///////////////////////////////////////////////////
UFSet& UFSet::operator=(UFSet& R)
{
    //首先把当前的父指针数组清空
    delete [] parent;
    //以集合R里的内容重建父指针数组
    parent=new int[R.size];
    //复制R.parent里内容到当前集合
    for(int i=0;i<size;i++)
        parent[i]=R.parent[i];
    size=R.size;
    return *this;
};
//////////////////////////////////////=成员重载结束

///////////////////////////////////////////////////
//findRoot()公有成员函数
//找集合x的根结点的指针
///////////////////////////////////////////////////
int UFSet::findRoot(int x)
{
    //如果父结点是负值,说明就是根结点
    if(parent[x]<0)
        return x;
    else
        //递归寻找x父结点的根结点
        return findRoot(parent[x]);
};
/////////////////////////////////findRoot()函数结束

///////////////////////////////////////////////////
//WeightedUnion()公有成员函数
//带加权的集合的合并
//即Root1和Root2,以结点数多的为根结点
///////////////////////////////////////////////////
void UFSet::WeightedUnion(int Root1,int Root2)
{
    //如果Root1的结点数多于Root2的结点数
    if(parent[Root1]<parent[Root2])
        Union(Root1,Root2);
    else
        Union(Root2,Root1);
};
////////////////////////////WeightedUnion()函数结束

///////////////////////////////////////////////////
//Display()公有成员函数
///////////////////////////////////////////////////
void UFSet::Display()
{
    //用于标记处理的当前子集的第几个元素
    int f=0;
    //外层循环寻找每个子集
    for(int i=0;i<size;i++)
    {
        //如果父指针数组<0说明是子集根结点
        if(parent[i]<0)
        {
            f=0;
            cout<<'{';
            //该i子集里其他的元素
            for(int j=0;j<size;j++)
                //判断集合元素j是否是以i为根结点
                if(i==findRoot(j))
                {
                    f++;
                    cout<<j;
                    //如果不是当前子集的最后一个元素
                    if(f!=abs(parent[i]))
                        cout<<',';
                };
            cout<<'}';
        };
    };
};
//////////////////////////////////Display()函数结束

///////////////////////////////////////////////////
//CollapseFind()公有成员函数
//利用折叠算法，减小集合树的层次,进行路径压缩
///////////////////////////////////////////////////
int UFSet::CollapseFind(int i)
{
    //把结点i和其所在集合的根之间的所有的结点作为根的子结点

    for(int r=i;parent[r]>=0;r=parent[r]);//寻找结点i的根结点
    while(i!=r)                           //从结点i逐个向上进行压缩
    {
        int temp=parent[i];  //保存当前结点的父结点

        parent[i]=r;         //把当前结点挂入根结点
        i=temp;              //指向剩下的结点
    }
    return r;                //返回根结点
};
/////////////////////////////CollapseFind()函数结束

///////////////////////////////////////////////////
//FindEqualClass()公有成员函数
///////////////////////////////////////////////////
void UFSet::FindEqualClass(Relative* Rel,int n)
{
    //逐个遍历每个等价关系
    //如果等价关系的左值和右值同属一个子集,则不做任何事
    //如果等价关系属于不同的集合,则把该两个自己合并
    for(int i=0;i<n;i++)
    {
        //如果等价关系的左值和右值不再同一个集合
        int RootLeft=findRoot(Rel[i].left);
        int RootRight=findRoot(Rel[i].right);
        //把这两个元素所在的集合合并
        if(RootLeft!=RootRight)
            Union(RootLeft,RootRight);
    }
};
///////////////////////////FindEqualClass()函数结束

#endif

看到了，谢谢你，真是个热心的好人！

我看到你贴出来的关于最小生成树的算法中还包含了Graphlink.h，Graphmtx.h等两个头文件，也一并给我好吗

真的是太感谢你 了

[[it] 本帖最后由 xiaoxl 于 2008-10-23 14:49 编辑 [/it]]

乖乖，这个两个代码可长啦，
Graphlink.h，是图的邻接表的类模板，
Graphmtx.h，是图的邻接矩阵的类模板，
都是写了很长时间的，

Graphlink.h代码如下：

#ifndef GRAPHLINK_H
#define GRAPHLINK_H

#include"BaseGraph.h"
#include<iostream.h>
#include<stdlib.h>
#include"LinkedQueue.h"
#include"GenTree.h"
#include"Forest.h"

/////////////////////////////////////////////////
//Edge 边结点结构的定义
/////////////////////////////////////////////////
template<class T,class E>
struct Edge
{
    int dest;             //目的结点的结点号
    E cost;               //边对应的权值
    Edge<T,E>* link;      //下一条边结点的指针
    Edge(){};             //默认构造函数
    Edge(int num,E weight)//带参数的构造函数
    :dest(num),cost(weight),link(NULL){};
    bool operator!=(Edge<T,E>& R)const
    {                     //成员重载运算符
        if(R.dest==dest)  //判断两个边结点是否相等
            return true;
        else
            return false;
    };
};
///////////////////////////Edge边结点结构定义结束

/////////////////////////////////////////////////
//Vertex结构 图的顶点结点的定义
/////////////////////////////////////////////////
template<class T,class E>
struct Vertex
{
    T data;        //结点的数据域
    Edge<T,E>* adj;//边链表的首指针
};
///////////////////////////Vertex顶点结构定义结束

/////////////////////////////////////////////////
//Graphlink<T,E>类模板的实现
//以邻接链表方式实现的图的类模板的声明和实现
//该类以Graph<T,E>为虚基类
//T是顶点数据域类型,E是边的权值类型
/////////////////////////////////////////////////
template<class T,class E>
class Graphlink:public Graph<T,E>
{
private:
    Vertex<T,E>* NodeTable;                 //顶点表数组
    int getVertexPos(const T vertex)        //给出指定顶点Vertex的结点号
    {
        for(int i=0;i<numVertices;i++)      //遍历所有的邻接顶点
            if(NodeTable[i]==vertex)
                return i;
        return -1;                          //没有找到
    };
    bool* visited;                          //用于标记第i个结点是否被访问的数组
    void DFS(int start);                    //递归:深度优先遍历本图,start是起始结点
public:
    Graphlink(int sz=DefaultVertices);      //默认构造函数
    ~Graphlink();                           //析构函数
    T getValue(int i)                       //取结点号为i的结点里的数据
    {
        if(i>=0 && i<maxVertices)
            return NodeTable[i].data;
        else
            return 0;
    };
    
    E getWeight(int v1,int v2);              //取得边(v1,v2)上的权值
    bool insertVertex(const T vertex);       //在图中插入一个顶点vertex
    bool removeVertex(int v);                //在图中删除指定结点号v的结点
    bool insertEdge(int v1,int v2,E cost);   //插入一条边以及对应的权值
    bool removeEdge(int v1,int v2);          //删除边(v1,v2)
    int getFirstNeighbor(int v);             //取得结点v的第一个邻接结点
    int getNextNeighbor(int v,int w);        //取得v的邻接结点中w后的那个邻接结点

    void DFSGraphic(int start);              //深度优先遍历当前图所有结点
    void BFSGraphic();                       //广度优先遍历
    void Find_Connected_Component();         //求图的所有的连通分量顶点集
    TreeNode<T>* DFSTree(int v);             //递归:得到以v为出发点的深度优先生成树TS
    void DisplayDFSTree(int v);              //调用上面的递归函数求图的深度优先生成树
    TreeNode<T>* DFSForest(int v);           //则求其所有连通分量的的深度优先生成森林
    void Find_DFSForest(int v)               //得到非连通图的深度优先生成森林
    {
        Forest<char> F;
        F.setRoot(DFSForest(0));
        cout<<"深度优先生成森林是:"<<endl;
        F.Display();
    };
    int getFirstUnvisit(int p,bool* visited);     //得到当前未访问的第一个邻接结点
    int getNextUnvisit(int p,int v,bool* visited);//得到下个未访问的邻接结点
    void DepthFirst(int start);                   //非递归深度优先遍历当前图
    //友元重载输出运算符
    friend ostream& operator<<(ostream& os,Graphlink<T,E>& G);
    //友元重载输入运算符
    friend istream& operator>>(istream& is,Graphlink<T,E>& G);
};
/////////////////////Graphlink<T,E>类模板声明结束

/////////////////////////////////////////////////
//默认构造函数
/////////////////////////////////////////////////
template<class T,class E>
Graphlink<T,E>::Graphlink(int sz)
{
    maxVertices=sz;     //图中最大的顶点数
    numEdges=0;         //初始边数
    numVertices=0;      //初始顶点数
    
    //顶点表数组开辟内存区域
    NodeTable=new Vertex<T,E>[sz];
    if(NodeTable==NULL)
    {
        cout<<"内存分配失败!"<<endl;
        exit(1);
    };
    //初始化顶点数组里的内容
    for(int i=0;i<maxVertices;i++)
        //把每个边链表的手指指针初始化为空
        NodeTable[i].adj=NULL;
};
/////////////////////////////////默认构造函数结束

/////////////////////////////////////////////////
//析构函数结束
//释放所有的边链表的内存以及结点数组的内存
/////////////////////////////////////////////////
template<class T,class E>
Graphlink<T,E>::~Graphlink()
{
    //首先遍历每条边链表的首结点
    for(int i=0;i<numVertices;i++)
    {
        Edge<T,E>*& ptr=NodeTable[i].adj;//游标指针
        Edge<T,E>* pre;                  //前个边结点的指针
        while(ptr!=NULL)
        {
            pre=ptr;                     //保留当前边结点
            ptr=ptr->link;               //指向下个边结点
            delete  pre;                 //释放结点内存
        };
    };
};
/////////////////////////////////////析构函数结束

/////////////////////////////////////////////////
//getWeight()公有成员函数
//得到指定边(v1,v2)上的权值
/////////////////////////////////////////////////
template<class T,class E>
E Graphlink<T,E>::getWeight(int v1,int v2)
{
    Edge<T,E>* ptr=NodeTable[v1].adj;//得到v1结点的边链表的首指针
    while(ptr!=NULL)                 //遍历该边链表找结点v2
    {
        if(ptr->dest==v2)            //如果找到就返回
            return ptr->cost;
        ptr=ptr->link;
    }
    return maxWeight;                //即这两点之间不存在边
};
//////////////////////getWeight()公有成员函数结束

/////////////////////////////////////////////////
//insertVertex()公有成员函数
//在图中插入一个顶点
/////////////////////////////////////////////////
template<class T,class E>
bool Graphlink<T,E>::insertVertex(const T vertex)
{
    if(numVertices<maxVertices)      //结点表不满则插入新结点
    {
         NodeTable[numVertices++].data=vertex;
        return true;                 //插入成功
    }
    else
        return false;                //表满插入失败
};
///////////////////////////insertVertex()函数结束

/////////////////////////////////////////////////
//removeVertex()公有成员函数
//在图中删除指定结点号的结点v,也删除和v关联的边
/////////////////////////////////////////////////
template<class T,class E>
bool Graphlink<T,E>::removeVertex(int v)
{
    if(v<0 || v>=numVertices)       //如果给出的结点号不存在
        return false;
    /*首先删除和结点v相关联的边链表*/
    Edge<T,E>* ptr=NodeTable[v].adj;//游标指针
    Edge<T,E>* pre;                 //指向释放的前一个结点
    while(ptr!=NULL)                //释放边链表中所有结点
    {
        pre=ptr;
        ptr=ptr->link;
        delete pre;
        numEdges--;                 //每删去一个边结点,numEdges减1
    };
    NodeTable[v].adj=NULL;          //该与结点的边链表置空

    /*在其他的边链表中也对称删除dest为v的边结点*/
    for(int i=0;i<numVertices;i++)  //遍历每一个边链表
    {
        ptr=NodeTable[i].adj;       //取得每个边链表的首指针
        if(ptr==NULL)               //如果边链表是空的
            continue;
        else if(ptr!=NULL           //如果是在头部删除
            && ptr->dest==v)
        {
            NodeTable[i].adj=ptr->link;
            delete ptr;
        }
        else
        {
            while(ptr->link!=NULL)
            {
                if(ptr->link->dest==v)
                {                   //如果找到该结点
                    pre=ptr->link;
                    ptr->link=ptr->link->link;
                    delete pre;
                    break;
                };
                ptr=ptr->link;      //指针向后推进一格
            };
        };
    };
    /*把NodeTable中的最后一个元素填补到v对应的位置*/
    NodeTable[v].data=NodeTable[numVertices-1].data;
    NodeTable[v].adj=NodeTable[numVertices-1].adj;
    NodeTable[numVertices-1].adj=NULL;
   
    /*把所有的原来结点号是numVertices-1的结点
    的结点号改为v*/
    int p=numVertices-1;            //原来最后一个结点的结点号
    for(i=0;i<numVertices-1;i++)    //遍历所有的边链表
    {
        ptr=NodeTable[i].adj;       //游标指针
        while(ptr!=NULL)            //遍历每个边结点
        {
            if(ptr->dest==p)        //原来目的结点是p的
                ptr->dest=v;        //现在改为v
            ptr=ptr->link;
        };
    };
    numVertices--;                  //结点的个数减1
    return true;                    //删除成功
};
///////////////////////////removeVertex()函数结束

/////////////////////////////////////////////////
//insertEdge()公有成员函数  
//在结点v1和v2之间建立一条边,同时对称建立边链表结点
/////////////////////////////////////////////////
template<class T,class E>
bool Graphlink<T,E>::insertEdge(int v1,int v2,E cost)
{
    if(v1<0 || v2<0 || v1>=numVertices || v2>=numVertices)
        return false;
    /*在v1的边链表中插入v2*/
    Edge<T,E>* ptr=NodeTable[v1].adj;         //游标指针
    Edge<T,E>* newEdge1=new Edge<T,E>(v2,cost);//新建边链表
    
    if(NodeTable[v1].adj==NULL)               //如果边链表本来是空的
    {
        NodeTable[v1].adj=newEdge1;
    }
    else if(v2<NodeTable[v1].adj->dest)       //在头部插入
    {
        newEdge1->link=NodeTable[v1].adj;
        NodeTable[v1].adj=newEdge1;
    }
    else
    {
        while(ptr->link!=NULL)                //寻找位置插入
        {
            if(ptr->dest<v2 && ptr->link->dest>v2)
            {
                newEdge1->link=ptr->link;
                ptr->link=newEdge1;
                break;
            }
            ptr=ptr->link;
        };
        if(ptr->link==NULL)                   //如果在尾部插入
            ptr->link=newEdge1;
    };
    /*在v2的边链表中插入v1*/
    ptr=NodeTable[v2].adj;
    Edge<T,E>* newEdge2=new Edge<T,E>(v1,cost);//新建边链表
    
    if(NodeTable[v2].adj==NULL)               //如果边链表本来是空的
    {
        NodeTable[v2].adj=newEdge2;
    }
    else if(v1<NodeTable[v2].adj->dest)       //在头部插入
    {
        newEdge2->link=NodeTable[v2].adj;
        NodeTable[v2].adj=newEdge2;
    }
    else
    {
        while(ptr->link!=NULL)                //寻找位置插入
        {
            if(ptr->dest<v1 && ptr->link->dest>v1)
            {
                newEdge2->link=ptr->link;
                ptr->link=newEdge2;
                break;
            }
            ptr=ptr->link;
        };
        if(ptr->link==NULL)                   //如果在尾部插入
            ptr->link=newEdge2;
    };
    numEdges++;                               //边数加1
    return true;
};
/////////////////////insertEdge()公有成员函数结束

/////////////////////////////////////////////////
//removeEdge()公有成员函数
//删除图中指定的一条变
/////////////////////////////////////////////////
template<class T,class E>
bool Graphlink<T,E>::removeEdge(int v1,int v2)
{
    if(v1<0 || v1>=maxWeight              //如果v1和v2是合法的
    || v2<0 || v2>=maxWeight)
        return false;                     //删除失败
    Edge<T,E>* ptr;                       //游标指针
    Edge<T,E>* pre;                       //前一个结点

    /*在v1的边链表中删除边结点v2*/
    ptr=NodeTable[v1].adj;                //v1边链表的首指针
    if(NodeTable[v1].adj==NULL)           //比边链表是空的
        return false;                     //删除失败
    else if(NodeTable[v1].adj->dest==v2)  //如果是在头部删
    {                                     //删除结点
        pre=NodeTable[v1].adj;
        NodeTable[v1].adj=NodeTable[v1].adj->link;
        delete pre;
    }
    else                                  //如果是在头结点以外结点删除
    {
        int flag=0;                       //是否有结点删除
        while(ptr->link!=NULL)            //寻找要删除的v2边结点
        {
            if(ptr->link->dest==v2)       //删除v2边结点
            {
                flag=1;                  
                pre=ptr->link;
                ptr->link=ptr->link->link;
                delete pre;
                break;
            };
            ptr=ptr->link;                //指针向后推进一格
        };
        if(flag==0)                       //如果没有找到边结点v2
        {
            cout<<"该边不存在!"<<endl;
            return false;                 //该边不存在删除失败
        };
    };
    /*在v2的边链表中删除边结点v1*/
    ptr=NodeTable[v2].adj;                //v1边链表的首指针
    if(NodeTable[v2].adj==NULL)           //比边链表是空的
        return false;                     //删除失败
    else if(NodeTable[v2].adj->dest==v1)  //如果是在头部删
    {                                     //删除结点
        pre=NodeTable[v2].adj;
        NodeTable[v2].adj=NodeTable[v2].adj->link;
        delete pre;
    }
    else                                  //如果是在头结点以外结点删除
    {
        int flag=0;                       
        while(ptr->link!=NULL)            //寻找要删除的v2边结点
        {
            if(ptr->link->dest==v1)       //删除v2边结点
            {
                flag=1;
                pre=ptr->link;
                ptr->link=ptr->link->link;
                delete pre;
                break;
            };
            ptr=ptr->link;                //指针向后推进一格
        };
        if(flag==0)        
            //该边不存在
            return false;                 //删除失败
    };
    numEdges--;                           //边的个数减1
    return true;
};
/////////////////////////////removeEdge()函数结束

/////////////////////////////////////////////////
//getFirstNeighbor()公有成员函数
//得到指定结点v的第一个相邻的结点
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::getFirstNeighbor(int v)
{
    if(v>=0 && v<numVertices)         //如果指定的结点存在
    {
        Edge<T,E>* p=NodeTable[v].adj;//边链表的首结点指针
        if(p!=NULL)
            return p->dest;
        else
            return -1;
    }
    else
        return -1;
};
///////////////////////getFirstNeighbor()函数结束

/////////////////////////////////////////////////
//getNextNeighbor()公有成员函数
//得到当前结点v的邻接顶点w下个邻接顶点的顶点号
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::getNextNeighbor(int v,int w)
{
    if(v>=0 && v< maxWeight             //如果结点号合法
    && w>=0 && w< maxWeight)
    {
        Edge<T,E>* ptr=NodeTable[v].adj;//获得和结点v对应的边链表的首指针
        while(ptr!=NULL)                //遍历该边链表对应的多有的边结点
        {
            if(ptr->dest==w)            //如果找到目的结点为w的边结点
                break;                  //结束查找
            ptr=ptr->link;
        };
        if(ptr!=NULL && ptr->link!=NULL)//如果ptr和ptr的下个结点都不空
            return ptr->link->dest;
        else
            return -1;                  //这样的结点不存在，查找失败
    }
    else
        return -1;
};
////////////////////////getNextNeighbor()函数结束

/////////////////////////////////////////////////
//DFS()私有成员函数
//递归:深度优先遍历图所有结点,start是起始结点
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DFS(int start)
{
    cout<<getValue(start)<<" ";      //访问当前的起始结点
    visited[start]=true;             //把对应的访问标志置为"已访问"

    int p=getFirstNeighbor(start);   //获取start的第一个邻接结点
    while(p!=-1)                     //递归访问start的所有邻接结点
    {
        if(visited[p]==false)        //如果neighbor没有被访问过
            DFS(p);                  //以neighbor为当前结点继续递归访问
        p=getNextNeighbor(start,p);  //获取下个邻接结点的结点号
    };
};
////////////////////////////DFS()私有成员函数结束

/////////////////////////////////////////////////
//DFSGraphic()公有成员函数
//深度优先遍历图所有结点,通过键盘输入起始结点
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DFSGraphic(int start)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;//把每个结点的访问标志置为否

    cout<<endl<<"深度优先遍历的结果是:"<<endl;
    if(start>=0 && start<numVertices)
         DFS(start);      //如果输入的结点号合法就开始遍历
    else
        exit(1);
    delete [] visited;   //释放标记数组的内存空间
};
/////////////////////DFSGraphic()公有成员函数结束

/////////////////////////////////////////////////
//BFSGraphic()公有成员函数
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::BFSGraphic()
{
    cout<<"请输入遍历的起始顶点号:";
    int start;                         //起始的结点号
    cin>>start;
    visited=new bool[numVertices];     //开辟标记数组的内存空间
    for(int i=0;i<numVertices;i++)
        visited[i]=false;              //把标记数组置为未访问
    LinkedQueue<int> Q;                //用于存放结点号的队列
    Q.EnQueue(start);                  //首先把起始顶点的标号压入队列
    if(start<0 || start>=numVertices)  //如果起始的结点号不合法
        exit(1);
    int p;                             //当前正在访问的顶点的顶点号
    int q;                             //所有邻接结点的游标指针

    while(!Q.IsEmpty())                //按层次遍历图的所有顶点
    {
        Q.DeQueue(p);                  //从队列中取出一个结点
        if(visited[p]==false)          //如果不曾被访问
        {
            cout<<getValue(p)<<" ";    //访问该结点
            visited[p]=true;           //已经被访问过
            q=getFirstNeighbor(p);     //获取当前访问结点的第一个邻接结点
            while(q!=-1)               //把所有的未被访问过的邻接结点全部送入队列
            {
                if(visited[q]==false)
                    Q.EnQueue(q);      //如果没有被访问过就压入队列
                q=getNextNeighbor(p,q);//获取下个邻接结点号
            };
        };
    };
    delete [] visited;                 //释放标记数组的内存空间
};
/////////////////////////BFSGraphic()公有函数结束

/////////////////////////////////////////////////
//Find_Connected_Component()公有成员函数
//寻找当前图的所有的连通分量(极大连通子图)
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::Find_Connected_Component()
{
    visited=new bool[numVertices];    //开辟标记数组的空间
    for(int i=0;i<numVertices;i++)
        visited[i]=false;             //标记全部初始化为未被访问
    cout<<"所有连通分量顶点的集合如下:";
    cout<<endl;
    for(i=0;i<numVertices;i++)
    {
        if(visited[i]==false)         //如果没有被访问,则可以顺次找出
        {
            DFS(i);                   //连通分量
            cout<<endl;
        }
    };
    delete [] visited;
};
///////Find_Connected_Component()公有成员函数结束

/////////////////////////////////////////////////
//DFSTree()公有成员函数
//递归:得到当前图的深度优先生成树的算法
//其中该树采用FirstChild-NextSibling存储结束
//v是遍历起始的顶点,subTree是以v为当前顶点的生成子树
/////////////////////////////////////////////////
template<class T,class E>
TreeNode<T>* Graphlink<T,E>::DFSTree(int v)
{
    T value=getValue(v);                 //通过结点v创建一个树的结点
    TreeNode<T>* subTree;
    subTree=new TreeNode<T>(value);      //作为当前生成子树的根结
    visited[v]=true;                     //当前结点v已经访问过

    int flag=1;                          //判断是否是长子结点
    TreeNode<T>* ptr=NULL;               //获取长子树的树根
    TreeNode<T>* pre=NULL;               //保留前棵兄弟子树的根结点

    for(int p=getFirstNeighbor(v);       //递归遍历v的所有未访问的邻接结点
        p!=-1;p=getNextNeighbor(v,p))
    {                                    
        if(visited[p]==false)            //如果邻接点p还未被访问过
        {
            ptr=DFSTree(p);              //递归生成一棵子树
            if(flag==1)                  //如果是长子结点
            {
                subTree->firstChild=ptr;
                flag=0;                  //标志表示已经不是长子结点
            }
            else
                pre->nextSibling=ptr;    //接到前面的子树的后面
            pre=ptr;
        };
    };
    return subTree;                      //返回根结点指针
};
////////////////////////////////DFSTree()函数结束

/////////////////////////////////////////////////
//DisplayDFSTree()公有成员函数
//调用上面的DFSTree()递归函数求当前图的深度优先生成树
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DisplayDFSTree(int v)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;
    cout<<"先根遍历以"<<getValue(v)<<"为起点的深度优先生成树:";
    Tree<T> T;             //定义一棵空树
    T.setRoot(DFSTree(v)); //设置根结点
    T.pre();               //先根遍历该树
    cout<<endl<<"深度优先生成树是:";
    T.Display();
    cout<<endl;
    cout<<"广度优先遍历的结果是:";
    T.levelOrder();

    delete [] visited;
};
/////////////////////////DisplayDFSTree()函数结束

/////////////////////////////////////////////////
//DFSForest()公有成员函数
//如果图是非连通的,则求其深度优先生成森林
//即每个连通分量的深度优先树构成的森林
/////////////////////////////////////////////////
template<class T,class E>
TreeNode<T>* Graphlink<T,E>::DFSForest(int v)
{
    visited=new bool[numVertices];
    for(int i=0;i<numVertices;i++)
        visited[i]=false;            //标志数组清为未访问
    TreeNode<T>* root;               //森林的根
    TreeNode<T>* ptr;                //游标指针
    TreeNode<T>* pre;                //前一棵生成树树的根结点
    int flag=1;                      //是否是森林里的第一棵树的标志
    for(int p=0;p<numVertices;p++)   //试着以每个结点开始寻找每个连通分量
    {                                //的深度优先生成树
        if(visited[p]==false)
        {
            ptr=DFSTree(p);          //找出以p为根的连通分量的深度优先生成树
            if(flag==1)              //是森林里的第一棵树
            {
                root=ptr;            //把ptr作为森林的根
                flag=0;
            }
            else
                pre->nextSibling=ptr;//把树连接入前面已经形成的森林中
            pre=ptr;                 //保留前棵树的根结点
        };
    };
    delete [] visited;
    return root;
};
//////////////////////////////DFSForest()函数结束

/////////////////////////////////////////////////
//getFirstUnvisit()公有成员函数
//得到p的第一个邻接的结点
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::getFirstUnvisit(int p,bool* visited)
{
    Edge<T,E>* ptr=NodeTable[p].adj; //获得p的边链表的头指针
    while(ptr!=NULL)                 //搜索该边链表
    {
        int des=ptr->dest;           //获得每条边的目的结点号
        if(visited[des]==false)      //如果第一个碰到一个未访问的
            return des;              //返回结点号
        ptr=ptr->link;
    };
    return -1;                       //没有找到就返回-1
};
////////////////////////getFirstUnvisit()函数结束

/////////////////////////////////////////////////
//getNextUnvisit()公有成员函数
//得到p的w之后的未访问的邻接结点号
/////////////////////////////////////////////////
template<class T,class E>
int Graphlink<T,E>::getNextUnvisit(int p,int v,bool* visited)
{
    Edge<T,E>* ptr=NodeTable[p].adj;//获得p的边链表的首指针
    int flag=0;                     //判断是否已经找到v
    while(ptr!=NULL)                //搜索边链表中v的指针
    {
        int des=ptr->dest;          //获得每条边的目的结点号
        if(des==v)                  //如果找到
        {
            flag=1;                 //已经找到
            break;
        }
        ptr=ptr->link;
    };
    if(flag==0)                     //边链表中连v都没有
        return -1;
    ptr=ptr->link;                  //指向v后的第一个结点
    while(ptr!=NULL)                //从边结点v后的第一个结点开始搜索
    {
        int des=ptr->dest;          //搜索v后的第一个未被访问的邻接结点
        if(visited[des]==false)
            return des;
        ptr=ptr->link;
    };
    return -1;
};
/////////////////////////getNextUnvisit()函数结束

/////////////////////////////////////////////////
//DepthFirst()公有成员函数
//采用非递归的方式深度遍历当前图
/////////////////////////////////////////////////
template<class T,class E>
void Graphlink<T,E>::DepthFirst(int start)
{
    visited=new bool[numVertices];   //是否被访问过的标记
    for(int i=0;i<numVertices;i++)
        visited[i]=false;

    LinkedStack<int> Stack;          //回溯过程中用到的堆栈
    int p=start;                     //指向当前的结点
    int parent=-1;                   //指向当前结点的遍历父结点
    int first;                       //存放获取长子结点号
    int next;                        //存放下个兄弟结点的地址
    do
    {
        cout<<getValue(p)<<" ";                //访问当前结点p
        visited[p]=true;                       //设置已经访问过

        first=getFirstNeighbor(p);             //获取当前访问结点p的未访问过的第一个邻接结点号
        while(first!=-1 && visited[first]==true)
            first=getNextNeighbor(p,first);    //继续看下个邻接结点
 
        if(first!=-1)                          //如果不是根结点而且长子结点不空
        {
            if(p==start)                       //如果当前访问的结点是根结点
                next=-1;                       //则没有下个兄弟结点
            else
            {
                next=getNextNeighbor(parent,p);//寻找p之后第一个未被访问的第一个兄弟结点
                while(next!=-1 && visited[next]==true)
                    next=getNextNeighbor(parent,next);
            };
            
            if(next!=-1)                       //如果p的下个兄弟结点存在,且不在堆栈中
            {
                Stack.Push(parent);            //先把父结点压入堆栈
                Stack.Push(next);              //再把该下个兄弟结点压入堆栈
            };
            parent=p;
            p=first;                           //下个结点
        }
        else                                   //如果长子结点是空的
        {
            if(p==start)                       //如果就是根结点
                break;                         //推出遍历循环
            else
            {
                do
                {
                    Stack.Pop(p);              //从堆栈中弹出一个结点作为下个结点
                    Stack.Pop(parent);         //从堆栈中同时获得
                }
                while(visited[p]!=false);      //弹出的结点如果是已经访问过的,就继续弹
            };
        };
    }while(first!=-1 || !Stack.IsEmpty());     //如果堆栈和长子结点都空了,说明遍历结束
};
/////////////////////////DepthFirst()公有函数结束

/////////////////////////////////////////////////
//友元重载<<输出运算符
/////////////////////////////////////////////////
template<class T,class E>
ostream& operator<<(ostream& os,Graphlink<T,E>& G)
{
    cout<<"当前图的内容是:"<<endl;
    Edge<T,E>* ptr;
    for(int i=0;i<G.numVertices;i++)
    {
        cout<<"第"<<i<<"个顶点"<<T(G.NodeTable[i].data)<<"边结点:";
        ptr=G.NodeTable[i].adj;
        while(ptr!=NULL)
        {
            cout<<"("<<ptr->dest<<","<<ptr->cost<<")"<<" ";
            ptr=ptr->link;
        };
        cout<<endl;
    };
    cout<<"当前图的总结点数是:"<<G.numVertices<<endl;
    cout<<"当前图的总边的个数:"<<G.numEdges<<endl;
    return os;
};
///////////////////////////////////<<友元重载结束

/////////////////////////////////////////////////
//友元重载>>输入运算符
/////////////////////////////////////////////////
template<class T,class E>
istream& operator>>(istream& is,Graphlink<T,E>& G)
{
    cout<<"通过键盘输入输入顶点和边";
    cout<<"请输入顶点的个数:";
    is>>G.numVertices;
    cout<<endl;
    for(int i=0;i<G.numVertices;i++)
    {
        cout<<"请输入第"<<i<<"个结点的数据内容:";
        is>>G.NodeTable[i].data;
    };
    cout<<"请输入边的个数:";
    is>>G.numEdges;
    cout<<endl;
    int v1,v2;
    E weight;
    for(i=0;i<G.numEdges;i++)
    {
        cout<<"输入起点:";
        is>>v1;
        cout<<"输入终点:";
        is>>v2;
        cout<<"输入权值:";
        is>>weight;
        G.insertEdge(v1,v2,weight);
        cout<<endl;
    }
    return is;
};
/////////////////////////////>>输入运算符重载结束

#endif