邻接表排序（链表排序）

采取冒泡的思想，一次选取两个，再套一层循环即可，但是由于在邻接表中表头节点和边表节点的数据类型并不一样，因此这相当于一个没有头结点的链表的排序。

可以优化一下的是：如果走一遍没有发生交换，说明已经有序了，因此就不用再进行冒泡了。可以直接跳出循环，减少循环次数。

在边表节点中，我存储的是string类型的数据，按照其在表头节点中的索引顺序从大到小排序，这样便于在dfs和bfs的过程中对同一个图得到一样的结果，而不因用户输入的不同而使得结果不同。

map<string,int> mmp;//映射字符串和坐标之间的关系

struct ArcNode//边表节点
{
    string name;
    int wigth;
    ArcNode* next;
};

struct VertexNode//顶点表节点
{
    string name;//名字
    ArcNode* firstarc;//指向边表节点的第一个元素
};

class Graph
{
private:
    int pointnum,eagenum;
    VertexNode point[maxn];//顶点数组
    ArcNode* last[maxn];//指向尾节点
    int vis[maxn];//标记数组
    int dis[maxn];//距离数组
    void insertElement(int pos, ArcNode * p);
    void sortlist(VertexNode nil);
public:
    Graph();//构造函数
    void create(int pointnum,int eagenum);
    void initvis();
    void get_agree();//输出度
    void dfs(string begin,int flag);//深度优先搜索
    void bfs(string begin);//广度优先搜索
    void dfs_all(string begin);
    void sort();
    void bfs_all(string begin);
    int get_connected_num();//求连通分量
    bool is_connected();//是否连通
    bool is_exit(string str);//一点是否存在
    void delete_point(string str);
    void Dijkstra(string begin);
    void Prim();
    void Kruskal();
    //TODO:最小生成树，
    void print();
};

void Graph::sortlist(VertexNode nil)
{
    ArcNode *pre,*now;
    int cnt=0;
    pre=nil.firstarc;
    while(pre)
    {
        cnt++;
        pre=pre->next;
    }
    if(cnt<=1)
    {
        return ;
    }
    //printf("cnt=%d\n",cnt);
    ArcNode *tmp;
    int ok=1;
    for(int i=0;i<cnt;i++)
    {
        pre=nil.firstarc;
        now=nil.firstarc->next;
        ok=1;
        while(now)
        {
            if(mmp[now->name]>mmp[pre->name])
            {
                swap(now->name,pre->name);
                swap(now->wigth,pre->wigth);
                ok=0;
            }
            pre=now;
            now=pre->next;
        }
        if(ok==1)
        {
            break;
        }
    }
    /*pre=nil.firstarc;
    while(pre)
    {
        cout<<pre->name<<"|"<<pre->wigth<<endl;
        pre=pre->next;
    }*/
}

void Graph::sort()
{
    for(int i=0;i<pointnum;i++)
        sortlist(point[i]);
}

邻接表排序（链表排序）

推荐阅读