博客

湖北工业大学数据结构用头文件、数据结构与算法王立柱2013

  • Post author:
  • Post category:其他


书中对Vector、List、Queue、Stack、Heap、Graph等进行了实现，全书代码在vc6中理论上运行通过，但是到了现代c++，使用vc6进行学习与写代码是比较麻烦的，基于提供的代码，仅对语法以及一些不合适的地方做了简单修改，以供学习使用。

在新版C/C++与数据结构第五版中应该是对代码进行了优化，但是我没有获取到第五版的代码。不过其中基本的算法思路是一样的。

修改之后在gcc version 12.2.0 (x86_64-win32-seh-rev0, Built by MinGW-W64 project)中简单测试通过。

gitee：

HBUTDataStructureHeader: 湖北工业大学数据结构所用头文件
 

//Vector.h

#ifndef VECTOR_H
#define VECTOR_H
#include <iostream>
#include <stdlib.h>
using namespace std;
template <class T>
class Vector
{
private:
    T *data;
    int theSize;
    int theMax;
    void Error(const char *cs) const
    {
        cout << cs << endl;
        exit(1);
    }

public:
    // explicit Vector(int n = 0) : theSize(0), theMax(n + SPARE_MAX)//
    explicit Vector(int n = 0) : theSize(n), theMax(n + SPARE_MAX) //这里原本的实现应该是有问题的
    {
        if (theMax > 0)
            data = new T[theMax];
    }
    Vector(const Vector &v) : data(nullptr), theMax(0)
    {
        operator=(v);
    }
    ~Vector(void)
    {
        delete[] data;
    }
    Vector &operator=(const Vector<T> &v);
    T &operator[](int id)
    {
        return (data[id]);
    }
    const T &operator[](int id) const
    {
        return (data[id]);
    }
    bool Empty(void) const
    {
        return (theSize == 0);
    }
    int Size(void) const
    {
        return (theSize);
    }
    int Max(void) const
    {
        return (theMax);
    }
    void Push_back(const T &item);
    void Pop_back(void);
    const T &Back(void) const;
    const T &Front(void) const;
    void Clear(void)
    {
        theSize = 0;
    }
    void Reserve(int newMax);
    void Resize(int newSize, const T &item = T());
    enum
    {
        SPARE_MAX = 16
    };

    typedef T *iterator;
    typedef const T *const_iterator;
    iterator begin()
    {
        return &data[0];
    }
    const_iterator begin() const
    {
        return &data[0];
    }
    iterator end()
    {
        return (&data[theSize]);
    }
    const_iterator end() const
    {
        return (&data[theSize]);
    }
    iterator Insert(iterator itr, const T &item);
    iterator Erase(iterator itr);
    int Count(const T &item) const
    {
        int res = 0;
        for (int i = 0; i < theSize; i++)
            if (item == data[i])
                res++;
        return res;
    }
    void print()
    {
        for (int i = 0; i < theSize; i++)
        {
            cout << data[i] << " ";
        }
        cout << endl;
    }
};

template <class T>
Vector<T> &Vector<T>::operator=(const Vector<T> &v)
{
    if (theMax != v.Max())
    {
        delete[] data;
        theMax = v.theMax;
        data = new T[theMax];
    }
    theSize = v.Size();
    for (int i = 0; i < theSize; i++)
        data[i] = v.data[i];
    return (*this);
}
template <class T>
void Vector<T>::Push_back(const T &item)
{
    if (theSize == theMax)
        Reserve(2 * theMax + 1);
    data[theSize++] = item;
}

template <class T>
typename Vector<T>::iterator
Vector<T>::Erase(iterator itr)
{
    if (theSize == 0)
        Error("Erase:an empty Vector!");
    if (itr < begin() || itr > end() - 1)
        Error("Erase: out of illegal!");
    for (iterator p = itr; p != end(); ++p)
        *p = *(p + 1);
    theSize--;
    return (itr);
}
template <class T>
typename Vector<T>::iterator
Vector<T>::Insert(iterator itr, const T &item)
{
    if (theSize == theMax)
        Reserve(2 * theMax + 1);
    if (itr < begin() || itr > end())
        Error("Insert:out of range");
    for (iterator p = end(); p != itr; --p)
        *p = *(p - 1);
    *itr = item;
    theSize++;
    return (itr);
}
template <class T>
void Vector<T>::Pop_back(void)
{
    if (theSize == 0)
        Error("Empty Vector!");
    theSize--;
}

template <class T>
const T &Vector<T>::Back(void) const
{
    if (theSize == 0)
        Error("Empty Vector!");
    return (data[theSize - 1]);
}
template <class T>
const T &Vector<T>::Front(void) const
{
    if (theSize == 0)
        Error("Empty Vector!");
    return (data[0]);
}
template <class T>
void Vector<T>::Reserve(int newMax)
{
    if (newMax < theSize)
        return;
    T *old = data;
    data = new T[newMax];
    for (int i = 0; i < theSize; i++)
        data[i] = old[i];
    theMax = newMax;
    delete[] old;
}
template <class T>
void Vector<T>::Resize(int newSize, const T &item)
{
    if (newSize > theMax)
        Reserve(newSize * 2 + 1);
    for (int i = theSize; i < newSize; i++)
        data[i] = item;
    theSize = newSize;
}

#endif

//List.h

#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
#include <iostream>
using std::cin;
using std::cout;
template <class T>
class List
{
    struct Node
    {
        T data;
        Node *prev, *next;
        Node(const T &d = T(), Node *p = NULL, Node *n = NULL) : data(d), prev(p), next(n) {}
    };
    int size;
    Node *head;
    Node *tail;
    void init()
    {
        size = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }

public:
    friend class const_iterator;
    friend class iterator;
    class const_iterator
    {
    protected:
        Node *current;
        T &retrieve() const
        {
            return current->data;
        }
        const_iterator(Node *p) : current(p) {}
        friend class List<T>;

    public:
        const_iterator() : current(NULL) {}
        const T &operator*() const
        {
            return retrieve();
        }
        const_iterator &operator++()
        {
            current = current->next;
            return *this;
        }
        const_iterator operator++(int)
        {
            const_iterator old = *this;
            ++(*this);
            return old;
        }
        const_iterator &operator--()
        {
            current = current->prev;
            return *this;
        }
        const_iterator operator--(int)
        {
            const_iterator old = *this;
            --(*this);
            return old;
        }
        bool operator==(const const_iterator &rhs) const
        {
            return current == rhs.current;
        }
        bool operator!=(const const_iterator &rhs) const
        {
            return current != rhs.current;
        }
    };
    class iterator : public const_iterator
    {
    protected:
        iterator(Node *p) : const_iterator(p) {}
        friend class List<T>;

    public:
        iterator() {}
        T &operator*()
        {
            return const_iterator::retrieve();
        }
        const T &operator*() const
        {
            return const_iterator::operator*();
        }
        iterator &operator++()
        {
            const_iterator::current = const_iterator::current->next;
            return *this;
        }
        iterator operator++(int)
        {
            iterator old = *this;
            ++(*this);
            return old;
        }
        iterator &operator--()
        {
            const_iterator::current = const_iterator::current->prev;
            return *this;
        }
        iterator operator--(int)
        {
            iterator old = *this;
            --(*this);
            return old;
        }
    };
    List()
    {
        init();
    }
    List(const List<T> &l)
    {
        init();
        operator=(l);
    }
    ~List()
    {
        Clear();
        delete head;
        delete tail;
    }
    const List &operator=(const List &l);
    int Size() const
    {
        return size;
    }
    bool Empty() const
    {
        return size == 0;
    }
    void Clear()
    {
        while (!Empty())
            Pop_front();
    }

    iterator begin()
    {
        return iterator(head->next);
    }
    const_iterator begin() const
    {
        return const_iterator(head->next);
    }
    iterator end()
    {
        return iterator(tail);
    }
    const_iterator end() const
    {
        return const_iterator(tail);
    }

    T &Front()
    {
        return *begin();
    }
    const T &Front() const
    {
        return *begin();
    }
    T &Back()
    {
        return *--end();
    }
    const T &Back() const
    {
        return *--end();
    }
    void Push_front(const T &item)
    {
        Insert(begin(), item);
    }
    void Push_back(const T &item)
    {
        Insert(end(), item);
    }
    void Pop_front()
    {
        Erase(begin());
    }
    void Pop_back()
    {
        Erase(--end());
    }
    iterator Erase(iterator itr);
    iterator Insert(iterator itr, const T &item);
    T &RemoveMin()
    {
        T res = *(this->begin());
        iterator i = this->begin();
        iterator j = i;
        for (; i != this->end(); i++)
            if (*(i) < res)
            {
                res = *(i);
                j = i;
            }
        this->Erase(j);
        return res;
    }
    void print()
    {
        for (iterator i = begin(); i != end(); i++)
            std::cout << *(i) << " ";
        std::cout << std::endl;
    }
};
template <class T>
const List<T> &List<T>::operator=(const List<T> &l)
{
    Clear();
    for (const_iterator itr = l.begin(); itr != l.end(); ++itr)
        Push_back(*itr);
    return *this;
}

template <class T>
typename List<T>::iterator List<T>::Erase(iterator itr)
{
    Node *p = itr.current;
    iterator re(p->next);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    size--;
    return re;
}
template <class T>
typename List<T>::iterator List<T>::Insert(iterator itr, const T &item)
{
    Node *p = itr.current;
    size++;
    p->prev->next = new Node(item, p->prev, p);
    p->prev = p->prev->next;
    return iterator(p->prev);
}

#endif

//Queue.h

#ifndef QUEUE_H
#define QUEUE_H
#include "List.h"
template <class T>
class Queue
{
    List<T> queueL;

public:
    Queue() {}
    ~Queue() {}
    int Size() const
    {
        return queueL.Size();
    }
    int Empty() const
    {
        return queueL.Empty();
    }
    const T &Front() const
    {
        return queueL.Front();
    }
    void Push(const T &item)
    {
        queueL.Push_back(item);
    }
    T Pop()
    {
        T item = queueL.Front();
        queueL.Pop_front();
        return item;
    }
    void Clear()
    {
        queueL.Clear();
    }
};

#endif

//Stack.h

#ifndef STACK_H
#define STACK_H
#include "list.h"
template <class T>
class Stack
{
    List<T> stackL;

public:
    Stack() {}
    ~Stack() {}
    int Size() const
    {
        return stackL.Size();
    }
    int Empty() const
    {
        return stackL.Empty();
    }
    const T &Top() const
    {
        return stackL.Back();
    }
    T Pop()
    {
        T item = stackL.Back();
        stackL.Pop_back();
        return item;
    }
    void Push(const T &item)
    {
        stackL.Push_back(item);
    }
    void Clear()
    {
        stackL.Clear();
    }
};

#endif

//heap.h

#ifndef HEAP_H
#define HEAP_H

#include "Vector.h"
#include <iostream>
using std::cin;
using std::cout;
template <class T>
class Heap //这是一个小根堆
{
    Vector<T> vec;
    int size;
    void BuildHeap();
    void PercolateDown(int h);
    void PercolateUp();

public:
    Heap(int max = 100) : vec(max), size(0) {}
    Heap(const Vector<T> &vt);
    bool Empty() const
    {
        return size == 0;
    }
    int Size()
    {
        return size;
    }

    void Insert(const T &item);
    const T &Top() const
    {
        return vec[0];
    }
    void DeleteMin();
    void DeleteMin(T &item);
    void Clear()
    {
        size = 0;
    }
    void print()
    {
        vec.print();
    }
};

template <class T>
void Heap<T>::PercolateDown(int h) //对h位置heapify
{
    int p = h, c = 2 * p + 1;
    T temp = vec[p];
    while (c < size)
    {
        if (c + 1 < size && vec[c + 1] < vec[c])
            ++c;
        if (temp < vec[c])
            break;
        else
        {
            vec[p] = vec[c];
            p = c;
            c = 2 * p + 1;
        }
    }
    vec[p] = temp;
}
template <class T>
void Heap<T>::PercolateUp() //向上调整堆，用于插入操作
{
    int c = size - 1, p = (c - 1) / 2;
    T temp = vec[c];
    while (c > 0)
        if (vec[p] <= temp)
            break;
        else
        {
            vec[c] = vec[p];
            c = p;
            p = (c - 1) / 2;
        }
    vec[c] = temp;
}

template <class T>
void Heap<T>::BuildHeap(void)
{
    for (int i = size / 2 - 1; i >= 0; i--)
        PercolateDown(i);
}

template <class T>
Heap<T>::Heap(const Vector<T> &vt)
// : vec(vt.Size() + 10), size(vt.Size())
{
    // for (int i = 0; i < size; ++i)
    //     vec[i] = vt[i];
    vec = vt;
    size = vt.Size();
    BuildHeap();
}

template <class T>
void Heap<T>::Insert(const T &item)
{
    if (size == vec.Size())
        vec.Resize(vec.Size() * 2);
    vec[size] = item;
    size++;
    PercolateUp();
}
template <class T>
void Heap<T>::DeleteMin(void)
{
    if (size == 0)
    {
        cout << "Heap empty!";
        exit(1);
    }
    vec[0] = vec[size - 1];
    size--;
    PercolateDown(0);
}
template <class T>
void Heap<T>::DeleteMin(T &item) //删除堆顶元素，把元素返回到item之中
{
    if (size == 0)
    {
        cout << "Heap empty!";
        exit(1);
    }
    item = vec[0];
    vec[0] = vec[size - 1];
    size--;
    PercolateDown(0);
}

#endif

//Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <stdlib.h>
#include <iostream>
#include <fstream>
#include "List.h"
#include "Stack.h"
#include "Queue.h"

using namespace std;

const double MAXCOST = 1000000; //最大权

struct PathData //用于最小生成树、单元最短路径等算法的结构
{
    int start, dest; //边的起点和终点的下标
    double cost;     //边上的权代表费用
    operator double() const
    {
        return cost; //成员转换函数，用于比较运算
    }
};

template <class T>
class Graph
{
    struct EdgeNode //边结点数据结构
    {
        int dest;    //边的终点下标
        double cost; //边的权
        operator int()
        {
            return dest; //成员转换函数
        }
    };

private:
    T *VA;                                                     //顶点数组指针
    List<EdgeNode> *HL;                                        //边链表数组指针
    int sizeV, sizeE;                                          //顶点数，边数
    int maxV;                                                  //顶点数组空间长度
    int InDegree(int pos) const;                               //读取下标为pos的顶点入度
    double GetCost(int si, int dj) const;                      //按始点和终点下标读取边的权
    void PercolateDown(PathData E[], int pos, int size) const; //从下标pos开始，向下调整为堆
    void BuildHeap(PathData E[], int size) const;              //建堆
    void BFS(List<T> &L, int pos, bool visited[]) const;
    void DFS(List<T> &L, int pos, bool visited[]) const;

public:
    Graph(int n = 100) : sizeV(0), sizeE(0), maxV(n) //构造函数
    {
        VA = new T[n];
        HL = new List<EdgeNode>[n];
    }
    ~Graph()
    {
        delete[] VA; //析构函数
        delete[] HL;
    }
    int Empty() const
    {
        return sizeV == 0; //判空
    }
    int Full() const
    {
        return sizeV == maxV; //判满
    }
    int SizeV() const
    {
        return sizeV; //取顶点数
    }
    int SizeE() const
    {
        return sizeE; //取边数
    }
    double GetCost(const T &v1, const T &v2) const; //取权
    int FindNode(const T &v) const;                 //取顶点的下标
    bool FindNode(T &v, int pos) const;             //将下标为pos的顶点存储到v中

    bool InsertV(const T &v);                         //插入顶点
    bool InsertE(const T &v1, const T &v2, double w); //插入边
    bool DeleteV(const T &v);                         //删除顶点
    bool DeleteE(const T &v1, const T &v2);           //删除边

    void BFS(List<T> &L, const T &v) const; //广度优先遍历一个连同子图
    void BFS(List<T> &L) const;
    void DFS(List<T> &L, const T &v) const;
    void DFS(List<T> &L) const;

    void ReadGraph(const char *filename);  //从文件读取图的数据
    void WriteGraph(const char *filename); //把图的数据写（输出）到文件
    template <typename T1>
    friend ostream &operator<<(ostream &ostr, const Graph<T1> &g); //重载输出运算符
    template <typename T1>
    friend istream &operator>>(istream &istr, Graph<T1> &g); //重载输入运算符

    bool Prim(const T &v, PathData E[], int ne) const;           //普里姆算法（ne表示最小生成树中边的个数，应该是结点顶点个数减1）
    bool Kruskal(PathData E[], int nv) const;                    //克鲁斯卡尔算法
    bool Dijkstra(const T &v, double D[], int P[], int n) const; //单源最短路径
    double MinPath(const T &sv, const T &ev) const;              //两个顶点间的最短路径成本
    void AllPath(double *A[], int *P[], int nv) const;
    bool TopSort(int *t, int n) const;                        //
    bool TopSort(List<T> &L) const;                           //拓扑序列
    void CriticalPath(double VE[], double VL[], int n) const; //关键路径
};

template <class T> //把长度为size的PathData结构数组调整为堆
void Graph<T>::BuildHeap(PathData E[], int size) const
{
    for (int i = size / 2 - 1; i >= 0; i--) //从临近叶子的第一个非叶子结点至根结点扫描
        PercolateDown(E, i, size);          //把下标[i,size)之间的元素向下调整为堆
}
template <class T> //将下标[pos,size)范围内的PathData结构数组元素向下调整为堆
void Graph<T>::PercolateDown(PathData E[], int pos, int size) const
{
    int p = pos, c = 2 * p + 1;
    PathData temp = E[p];
    while (c < size)
    {
        if (c + 1 < size && E[c + 1] < E[c]) //隐式调用PathData成员转换函数来比较权
            ++c;
        if (temp < E[c])
            break;
        else
        {
            E[p] = E[c];
            p = c;
            c = 2 * p + 1;
        }
    }
    E[p] = temp;
}

template <class T>
int Graph<T>::InDegree(int pos) const
{
    int id = 0;
    for (int i = 0; i < sizeV; i++)
    {
        typename List<EdgeNode>::const_iterator first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            if ((*first).dest == pos)
            {
                id++;
                break;
            }
    }
    return id;
}
template <class T>
double Graph<T>::GetCost(int si, int dj) const
{
    if (si < 0 || si >= sizeV || dj < 0 || dj >= sizeV || si == dj)
        return (0);
    typename List<EdgeNode>::const_iterator first = HL[si].begin(), last = HL[si].end();
    for (; first != last; ++first)
        if ((*first).dest == dj)
            return (*first).cost;
    return 0;
}
template <class T>
int Graph<T>::FindNode(const T &v) const
{
    for (int i = 0; i < sizeV; i++)
        if (VA[i] == v)
            return i;
    return -1;
}
template <class T>
bool Graph<T>::FindNode(T &v, int pos) const
{
    if (pos < 0 || pos >= sizeV)
        return 0;
    v = VA[pos];
    return 1;
}
template <class T>
double Graph<T>::GetCost(const T &v1, const T &v2) const
{
    return GetCost(FindNode(v1), FindNode(v2));
}

template <class T>
bool Graph<T>::InsertV(const T &v)
{
    if (sizeV == maxV)
        return 0;
    VA[sizeV] = v;
    sizeV++;
    return 1;
}
template <class T>
bool Graph<T>::InsertE(const T &v1, const T &v2, double w)
{
    int si = FindNode(v1), dj = FindNode(v2);
    if (si == -1 || dj == -1 || si == dj)
        return (0);
    EdgeNode en;
    en.dest = dj;
    en.cost = w;
    HL[si].Insert(HL[si].end(), en);
    sizeE++;
    return 1;
}

template <class T>
bool Graph<T>::DeleteV(const T &v)
{
    int si = FindNode(v);
    if (si == -1)
        return (0);
    int temp = HL[si].Size();
    for (int i = si; i < sizeV - 1; i++)
    {
        VA[i] = VA[i + 1];
        HL[i] = HL[i + 1];
    }
    HL[sizeV - 1].Clear();
    sizeV--;
    sizeE = sizeE - temp;
    int i;
    typename List<EdgeNode>::iterator first, last;
    for (i = 0; i < sizeV; i++)
    {
        first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            if ((*first).dest == si)
            {
                HL[i].Erase(first);
                sizeE--;
                break;
            }
    }
    for (i = 0; i < sizeV; i++)
    {
        first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            if ((*first).dest > si)
                (*first).dest--;
    }
    return 1;
}
template <class T>
bool Graph<T>::DeleteE(const T &v1, const T &v2)
{
    int si = FindNode(v1), dj = FindNode(v2);
    if (si == -1 || dj == -1 || si == dj)
        return (0);
    typename List<EdgeNode>::iterator first = HL[si].begin(), last = HL[si].end();
    for (; first != last; ++first)
        if ((*first).dest == dj)
        {
            HL[si].Erase(first);
            sizeE--;
            return 1;
        }
    return 0;
}
template <class T>
void Graph<T>::ReadGraph(const char *filename)
{
    char str[50];
    int n;
    double w;
    T v1, v2;
    ifstream fin;
    fin.open(filename, ios::in); //此处删去ios::nocreatefin.open(filename, ios::in | ios::nocreate);
    if (!fin)
    {
        cout << "cannot open " << filename << endl;
        exit(1);
    }
    fin >> str >> n;
    for (int i = 1; i <= n; ++i)
    {
        fin >> v1;
        InsertV(v1);
    }
    fin >> str >> n;
    int i;
    for (i = 1; i <= n; ++i)
    {
        fin >> v1 >> v2 >> w;
        InsertE(v1, v2, w);
    }
}
template <class T>
void Graph<T>::WriteGraph(const char *filename)
{
    ofstream fout;
    fout.open(filename, ios::out);
    if (!fout)
    {
        cout << "cannot open " << filename << endl;
        exit(1);
    }
    for (int i = 0; i < sizeV; i++)
    {
        fout << i << '-' << VA[i] << ':';
        typename List<Graph<T>::EdgeNode>::iterator first = HL[i].begin(), last = HL[i].end();
        for (; first != last; ++first)
            fout << '(' << (*first).dest << ',' << (*first).cost << ')' << ' ';
        fout << endl;
    }
}
template <class T>
istream &operator>>(istream &istr, Graph<T> &g)
{
    char str[50];
    int n;
    double w;
    T v1, v2;
    istr >> str >> n;
    for (int i = 1; i <= n; ++i)
    {
        istr >> v1;
        g.InsertV(v1);
    }
    istr >> str >> n;
    int i;
    for (i = 1; i <= n; ++i)
    {
        istr >> v1 >> v2 >> w;
        g.InsertE(v1, v2, w);
    }
    return istr;
}

template <class T>
ostream &operator<<(ostream &ostr, const Graph<T> &g)
{
    for (int i = 0; i < g.sizeV; i++)
    {
        ostr << i << '-' << g.VA[i] << ':';
        typename List<typename Graph<T>::EdgeNode>::iterator first = g.HL[i].begin(), last = g.HL[i].end();
        for (; first != last; ++first)
            ostr << '(' << (*first).dest << ',' << (*first).cost << ')' << ' ';
        ostr << endl;
    }
    return ostr;
}
template <class T>
void Graph<T>::BFS(List<T> &L, int pos, bool visited[]) const
{
    if (pos < 0 || pos >= sizeV)
        return;
    Queue<int> Q;
    Q.Push(pos);
    visited[pos] = 1;
    typename List<EdgeNode>::const_iterator first, last;
    while (!Q.Empty())
    {
        pos = Q.Pop();
        L.Push_back(VA[pos]);
        first = HL[pos].begin();
        last = HL[pos].end();
        for (; first != last; ++first)
            if (visited[(*first).dest] == 0)
            {
                Q.Push((*first).dest);
                visited[(*first).dest] = 1;
            }
    }
}
template <class T>
void Graph<T>::BFS(List<T> &L) const
{
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    int i;
    for (i = 0; i < sizeV; i++)
        if (visited[i] == 0)
            BFS(L, i, visited);
}

template <class T>
void Graph<T>::BFS(List<T> &L, const T &v) const
{
    int pos = FindNode(v), i;
    if (pos == -1)
        return;
    bool *visited = new bool[sizeV];
    for (i = 0; i < sizeV; i++)
        visited[i] = 0;
    Queue<int> Q;
    Q.Push(pos);
    visited[pos] = 1;
    typename List<EdgeNode>::const_iterator first, last;
    while (!Q.Empty())
    {
        pos = Q.Pop();
        L.Push_back(VA[pos]);
        first = HL[pos].begin();
        last = HL[pos].end();
        for (; first != last; ++first)
            if (visited[(*first).dest] == 0)
            {
                Q.Push((*first).dest);
                visited[(*first).dest] = 1;
            }
    }
}

template <class T>
void Graph<T>::DFS(List<T> &L, int pos, bool visited[]) const
{
    if (pos < 0 || pos >= sizeV)
        return;
    L.Push_back(VA[pos]);
    visited[pos] = 1;
    typename List<EdgeNode>::const_iterator first, last;
    first = HL[pos].begin();
    last = HL[pos].end();
    for (; first != last; ++first)
        if (visited[(*first).dest] == 0)
            DFS(L, (*first).dest, visited);
}

template <class T>
void Graph<T>::DFS(List<T> &L) const
{
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    int i;
    for (i = 0; i < sizeV; i++)
        if (visited[i] == 0)
            DFS(L, i, visited);
}

template <class T>
void Graph<T>::DFS(List<T> &L, const T &v) const
{
    int pos = FindNode(v);
    if (pos == -1)
        return;
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    DFS(L, pos, visited);
}

template <class T>
bool Graph<T>::Prim(const T &v, PathData E[], int ne) const
{
    int i, j, s, ns;
    PathData item;
    double cost;
    s = FindNode(v);
    if (s == -1)
        return 0;
    int id = 0;
    for (i = 0; i <= ne; i++)
        if (i != s)
        {
            item.start = s;
            item.dest = i;
            cost = GetCost(s, i);
            item.cost = (cost == 0 ? MAXCOST : cost);
            E[id++] = item;
        }
    int count = 0;
    BuildHeap(E, ne);
    for (i = 0; i < ne; i++)
    {
        if (E[0] < MAXCOST)
            count++;
        ns = E[0].dest;
        for (j = 1; j < ne - i; j++)
        {
            cost = GetCost(ns, E[j].dest);
            cost = (cost == 0 ? MAXCOST : cost);
            if (E[j] > cost)
            {
                E[j].cost = cost;
                E[j].start = ns;
            }
        }
        item = E[0];
        E[0] = E[ne - 1 - i];
        E[ne - 1 - i] = item;
        PercolateDown(E, 0, ne - 1 - i);
    }
    return count == ne ? 1 : 0;
}

template <class T>
bool Graph<T>::Kruskal(PathData E[], int ne) const
{
    Heap<PathData> H;
    int nv = ne + 1;
    int i, j, *DS = new int[nv];
    for (i = 0; i < nv; i++)
        DS[i] = -1;
    double cost;
    PathData e;
    for (i = 0; i < nv; i++)
        for (j = i + 1; j < nv; j++)
        {
            cost = GetCost(i, j);
            if (cost != 0)
            {
                e.start = i;
                e.dest = j;
                e.cost = cost;
                H.Insert(e);
            }
        }
    int id = 0;
    while (!H.Empty())
    {
        H.DeleteMin(e);
        i = e.start;
        while (DS[i] >= 0)
            i = DS[i];
        j = e.dest;
        while (DS[j] >= 0)
            j = DS[j];
        if (i != j)
        {
            if (i < j)
            {
                DS[i] += DS[j];
                DS[j] = i;
            }
            else
            {
                DS[j] += DS[i];
                DS[i] = j;
            }
            E[id++] = e;
        }
    }
    return id == ne ? 1 : 0;
}

template <class T>
bool Graph<T>::Dijkstra(const T &v, double D[], int P[], int nv) const
{
    int i, j, s, ns, ne = nv - 1;
    PathData item, *E = new PathData[ne];
    double cost;
    s = FindNode(v);
    if (s == -1)
        return 0;
    D[s] = 0;
    P[s] = -1;
    int id = 0;
    for (i = 0; i <= ne; i++)
        if (i != s)
        {
            item.start = s;
            item.dest = i;
            cost = GetCost(s, i);
            item.cost = (cost == 0 ? MAXCOST : cost);
            E[id++] = item;
            D[i] = item.cost;
            P[i] = (cost == 0 ? -1 : s);
        }
    int count = 0;
    BuildHeap(E, ne);
    for (i = 0; i < ne; i++)
    {
        if (E[0] < MAXCOST)
            count++;
        ns = E[0].dest;
        for (j = 1; j < ne - i; j++)
        {
            cost = GetCost(ns, E[j].dest);
            cost = (cost == 0 ? MAXCOST : cost);
            if (E[j] > E[0] + cost)
            {
                E[j].cost = E[0].cost + cost;
                E[j].start = ns;
                D[E[j].dest] = E[j].cost;
                P[E[j].dest] = ns;
            }
        }
        item = E[0];
        E[0] = E[ne - 1 - i];
        E[ne - 1 - i] = item;
        PercolateDown(E, 0, ne - 1 - i);
    }
    return count == ne ? 1 : 0;
}

template <class T>
double Graph<T>::MinPath(const T &sv, const T &dv) const
{
    int si = FindNode(sv), dj = FindNode(dv);
    if (si == -1 || dj == -1)
        return (-1);
    bool *visited = new bool[sizeV];
    for (int i = 0; i < sizeV; i++)
        visited[i] = 0;
    int id;
    double mincost, cost;
    Heap<PathData> PQ;
    PathData item;

    item.start = item.dest = FindNode(sv);
    item.cost = 0;
    PQ.Insert(item);
    id = FindNode(dv);

    while (!PQ.Empty())
    {
        PQ.DeleteMin(item);
        cout << item.start << ',' << item.dest << ',' << item.cost << endl;
        dj = item.dest;
        mincost = item.cost;
        if (dj == id)
            break;
        if (visited[dj] == 0)
        {
            visited[dj] = 1;
            si = dj;
            for (dj = 0; dj < sizeV; dj++)
            {
                cost = GetCost(si, dj);
                if (cost != 0 && visited[dj] == 0)
                {
                    item.start = si;
                    item.dest = dj;
                    item.cost = mincost + cost;
                    PQ.Insert(item);
                }
            }
        }
    }
    if (dj == id)
        return mincost;
    return -1;
}
template <class T>
void Graph<T>::AllPath(double *A[], int *P[], int nv) const
{
    int i, j, k;
    double cost;
    for (i = 0; i < nv; i++)
        for (j = 0; j < nv; j++)
        {
            if (i != j)
            {
                cost = GetCost(i, j);
                A[i][j] = (cost == 0 ? MAXCOST : cost);
            }
            else
                A[i][j] = 0;
            P[i][j] = (A[i][j] == MAXCOST ? -1 : i);
        }
    for (k = 0; k < nv; k++)
        for (i = 0; i < nv; i++)
            for (j = 0; j < nv; j++)
                if (A[i][k] + A[k][j] < A[i][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                    P[i][j] = P[k][j];
                }
}

template <class T>
bool Graph<T>::TopSort(int *t, int nv) const
{
    int i, j, id, count = 0;
    int *ID = new int[nv];
    Queue<int> Q;
    for (i = 0; i < nv; i++)
    {
        ID[i] = InDegree(i);
        if (ID[i] == 0)
            Q.Push(i);
    }
    typename List<EdgeNode>::const_iterator first, last;
    id = 0;
    while (!Q.Empty())
    {
        i = Q.Pop();
        t[id++] = i;
        count++;
        first = HL[i].begin();
        last = HL[i].end();
        for (; first != last; ++first)
        {
            j = (*first).dest;
            ID[j]--;
            if (ID[j] == 0)
                Q.Push(j);
        }
    }
    delete[] ID;
    if (count == nv)
        return 1;
    return 0;
}

template <class T>
bool Graph<T>::TopSort(List<T> &L) const
{
    int *top = new int[sizeV];
    if (TopSort(top, sizeV))
    {
        for (int i = 0; i < sizeV; i++)
            L.Push_back(VA[top[i]]);
        delete[] top;
        return 1;
    }
    delete[] top;
    return 0;
}

template <class T>
void Graph<T>::CriticalPath(double VE[], double VL[], int nv) const
{
    int i, j, k;
    int *top = new int[nv];
    double min, max, temp;
    if (TopSort(top, nv))
    {
        for (int n = 0; n < nv; n++)
            cout << top[n] << ',';
        cout << endl;
        VE[top[0]] = 0;
        for (k = 1; k < nv; k++)
        {
            j = top[k];
            max = 0;
            for (i = 0; i < nv; i++)
            {
                temp = GetCost(i, j);
                if (temp != 0 && (VE[i] + temp) > max)
                    max = VE[i] + temp;
            }
            VE[j] = max;
        }
        VL[top[nv - 1]] = VE[top[nv - 1]];
        for (k = nv - 2; k > -1; k--)
        {
            i = top[k];
            min = MAXCOST;
            for (j = 0; j < nv; j++)
            {
                temp = GetCost(i, j);
                if (temp != 0 && (VL[j] - temp) < min)
                    min = VL[j] - temp;
            }
            VL[i] = min;
        }
    }
    delete[] top;
}

#endif

duxingmengshou   HBUT


版权声明：本文为m0_69011137原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。