AOV拓扑排序

2024-04-18 13:48
文章标签 排序 拓扑 aov

本文主要是介绍AOV拓扑排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这是一个AOV拓扑排序的例子，为了应付公司测试而作，写起来也不容易，给记录一下。

在Visual C++2005下做的，这个版本的IDE环境用起来还不错。

aov.h

 

// data structure
 // linked graph

#include  < iostream >
#include  < vector >
#include  < string >
#include  < map >

class  EdgeNode
 {
public:
    int adjvex;
    //double weight;   useless in this program.
    EdgeNode *nextarc;
public:
    EdgeNode(const int idx)
    {
        adjvex = idx;
        nextarc = 0;
    }
} ;

 //  table head
class  VNode 
 {
public:
    std::string data;
    EdgeNode *firstarc;
public:
    VNode(const char* data, EdgeNode * firstarc)
    {
        if(data != 0)
            this->data = data;
        else
            printf("check test file. VNode Constructor. ");
        this->firstarc = firstarc;
    }
} ;

 class  Graph
 {
public:
    int vnum;
    std::vector<VNode> Vertices;
private:
    std::map<std::string, int> node_map;//pretend to be hash_map
public:
    Graph()
    {
        vnum = 0;
    }
    int addNode(VNode& node);
    int getNode(const char* name); //return the index in Vertices.
    void clear();
} ;

aov.cpp

 

// Normal return 0, otherwise -1
 // Graph DAG, which records clothes information.
 //
 #include  " aov.h "

using   namespace  std;

 int  Graph::addNode(VNode &  node)
 {
    node_map.insert(map<std::string, int>::value_type(node.data, vnum++));
    Vertices.push_back(node);
    return 0;
}

int  Graph::getNode( const   char *  name)
 {
    map<string, int>::iterator it;
    it = node_map.find(name);
    if(it != node_map.end())
        return it->second;
    return -1;
}

void  Graph::clear()
 {
    vector<EdgeNode*> needtodel;
    for(vector<VNode>::iterator it = Vertices.begin(); it != Vertices.end(); ++it)
    {
        EdgeNode* next = it->firstarc;
        while(next)
        {
            needtodel.push_back(next);
            next = next->nextarc;
        }
    }
    for(vector<EdgeNode*>::iterator it = needtodel.begin(); it != needtodel.end(); ++it)
    {
        delete *it;
    }
}

 

test.h

 

#include  " aov.h "

#define  PATH_LEN 256

class  AOVTest
 {
    Graph G;
    std::vector<int> outputArray;
public:
    int prepare(const char* file);
    int TopologicalSort();
    int output(const char* file);
} ;

 

test.cpp

 

#include  " test.h "
#include  < fstream >
#include  < stack >
using   namespace  std;

 #define  BUFFER_SIZE 1024

int  AOVTest::TopologicalSort()
 {
    int count = 0;
    int* indegree = (int*)calloc(G.vnum, sizeof(int));
    if(!indegree)
    {
        printf( "Can't allocate memory " );
        return -1;
    }

    for(int i = 0; i < G.vnum; ++i)
    {
        EdgeNode* t = G.Vertices[i].firstarc;
        while(t)
        {
            indegree[t->adjvex]++;
            t = t->nextarc;
        }
    }

    stack<int> S;
    for(int i = 0; i<G.vnum; ++i)
    {
        if(indegree[i] == 0)
            S.push(i);
    }
    count = 0;
    while(!S.empty())
    {
        int idx = S.top();
        outputArray.push_back(idx);
        S.pop();
        ++count;
        for(EdgeNode* t = G.Vertices[idx].firstarc; t ; t = t->nextarc)
        {
            int k = t->adjvex;
            indegree[k]--;
            if(indegree[k] == 0)
                S.push(k);
        }
    }
    if(count < G.vnum)
    {
        free(indegree);
        return -1;
    }
    free(indegree);
    return 0;
}

//
// create graph from test file
int  AOVTest::prepare( const   char *  file)
 {
    fstream fs(file, ios::in);
    if(!fs)
    {
        cout << "in file open failed!" << endl;
        return -1;
    }

    while(!fs.eof())
    {
        char buffer[BUFFER_SIZE];
        memset(buffer, 0, BUFFER_SIZE);
        fs.getline(buffer, BUFFER_SIZE);

        string line(buffer);
        if(line.empty())
            continue;

        string::size_type pos = 0;
        pos = line.find("->", 0);
        if(pos != string::npos)
        {
            //handle with first cloth
            string sfirst = line.substr(0, pos);
            if(sfirst.empty())
            {
                printf("Error format. check test file. //->first one not exist!");
                return -1;
            }
            int idx1 = G.getNode(sfirst.c_str());
            if(idx1 == -1)
            {  //find in VNode
                idx1 = G.vnum;
                VNode vnode1(sfirst.c_str(), 0);
                G.addNode(vnode1);
            }

            //handle with last cloth
            string slast = line.substr(pos + 2, line.length() - pos - 2);
            if(slast.empty())
            {
                printf("Error format. check test file. //->last one not exist!");
                return -1;
            }
            int idx2 = G.getNode(slast.c_str());
            if(idx2 == -1)
            {  //find in VNode
                idx2 = G.vnum;
                VNode vnode2(slast.c_str(), 0);
                G.addNode(vnode2);
            }

            //connection reverse
            EdgeNode* plink = new EdgeNode(idx2);
            EdgeNode* next = G.Vertices[idx1].firstarc;
            if(!next)
                G.Vertices[idx1].firstarc = plink;
            else
            {
                EdgeNode* current;
                while(next)
                {
                    current = next;
                    next = next->nextarc;
                }
                current->nextarc = plink;
            }
        }    
    }
    return 0;
}

int  AOVTest::output( const   char *  file)
 {
    fstream fs(file, ios::out);
    if(!fs)
    {
        cout << "out file open failed!" << endl;
        return -1;
    }

    for(vector<int>::iterator it = outputArray.begin(); it != outputArray.end(); ++it)
    {
        fs << G.Vertices[*it].data << endl;
    }
    return 0;
}

 

最后的了，main.cpp

 

#include  " test.h "

#define  USAGE_MSG "Usage: AOV [infile] + options
                - o refer to output file.
                default   - o  is  result.txt. "
 int  main( int  argc,  char **  argv)
 {
    if(argc < 2)
    {
        //printf("Usage: AOV [infile] + options
        //       -o refer to output file.
        //       default -o is result.txt. ");
        printf(USAGE_MSG);
        getchar();
        return -1;
    }

    char infile[256];
    char outfile[256];
    memset(outfile, 0, sizeof(outfile));

    for(int i = 1; i < argc; ++i)
    {
        if(argv[i][0] != '-')
        {
            if(i == 1)
                strcpy(infile, argv[i]);
            else if(i == 3)
                strcpy(outfile, argv[i]);
            else
            {
                printf(USAGE_MSG);
                getchar();
                return -1;
            }

        }
        else
        {
            if(argv[i][1] != 'o' || strlen(argv[i]) > 2)
            {
                printf(USAGE_MSG);
                getchar();
                return -1;
            }
        }
    }
    if(!outfile)
    {
        strcpy(outfile, "result.txt");
    }

    AOVTest ts;
    int ret = 0;
    ret = ts.prepare(infile);
    if(ret)
        _ASSERT(0);
    ret = ts.TopologicalSort();
    if(ret)
        _ASSERT(0);
    ret = ts.output(outfile);
    if(ret)
        _ASSERT(0);

    getchar();
    return 0;
}

这篇关于AOV拓扑排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/914957。

相关文章

大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...
Python中lambda排序的六种方法

Python中lambda排序的六种方法

《Python中lambda排序的六种方法》本文主要介绍了Python中使用lambda函数进行排序的六种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录1.对单个变量进行排序2. 对多个变量进行排序3. 降序排列4. 单独降序1.对单个变量进行排序
阅读更多...
关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...
hdu 1285（拓扑排序）

hdu 1285（拓扑排序）

题意： 给各个队间的胜负关系，让排名次，名词相同按从小到大排。 解析： 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式，对一个有向无回路图进行拓扑排序后，所有的顶点形成一个序列，对所有边(u,v)，满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上，某些工程完成后，另一些工程才能继续，此时
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
【软考】希尔排序算法分析

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组，例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量，换值int temp;in
阅读更多...
学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

学习记录：js算法（二十八）：删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一：循环解法二：递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1：（图一）输入：head = [1,1,2]输出：[1,2]示例 2：（图
阅读更多...
鸡尾酒排序算法

鸡尾酒排序算法

目录 引言 一、概念 二、算法思想 三、图例解释 1.采用冒泡排序：   2.采用鸡尾酒排序：  3.对比总结 四、算法实现  1.代码实现  2.运行结果 3.代码解释   五、总结 引言 鸡尾酒排序（Cocktail Sort），也被称为双向冒泡排序，是一种改进的冒泡排序算法。它在冒泡排序的基础上进行了优化，通过双向遍历来减少排序时间。今天我们将学习如何在C
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2