数据结构研讨代码以及ppt

数据结构课程 研讨题目 中国邮路问题 c++代码实现以及 研讨ppt

#include 
#include 
#include 

#define min（ab） （ （a） < （b） ? （a） : （b） ）
#define MAX_NODE 100
#define MAX_EDGE 100
#define INF 0x7fffffff      // 表示两点不连通

typedef struct 
{
    int number;   // 标记位
    int cost;     // 结点间距
    int dis;      // 结点最近距离
}Node;

typedef struct 
{
    int from;     // 边起点
    int to;       // 边终点
    int dis;      // 边距离
}Edge;

int n m;                              // 点的个数和边的个数
int total_edge odd_point;             // 总边数和奇点数
Node map[MAX_NODE][MAX_NODE];          // 结点连接情况
int point[MAX_NODE];                   // 每个结点的度数
int need_add_num min_count edge_num; // 需要添加边的个数  
Edge odd_edge[MAX_EDGE];
int point_flag[MAX_EDGE];
int min_edge[MAX_EDGE];
int tmp_edge[MAX_EDGE];
int top;
int finish_flag = 0;
int path_stack[MAX_EDGE];



void Floyd（）
{
    // 比较i到j直达近还是从i到k加上k到j近。添加的结点k放在最外层循环。
    for （int k = 1; k <= n; k++）
        for （int i = 1; i <= n; i++）
            if（map[i][k].dis != INF）
            {
                for （int j = 1; j < n; j++）
                    if（map[k][j].dis != INF）
                    {
                        map[i][j].dis = map[j][i].dis = min（map[i][j].dis map[i][k].dis + map[k][j].dis）;
                    }
            }
}

void search_edge（int count int step）
{
    // 深度寻找距离最短的添加最优方案
    // step用于记录数量，count记录最短长度
    // 寻找路径存入了数组中，可通过i访问

    if （step == need_add_num）
    {
        if （count < min_count）
        {
            for （int i = 0; i < need_add_num; i++）
            {
                min_edge[i] = tmp_edge[i];
            }
            min_count = count;
        }
        return;
    }
    int a b c;
    for （int i = 0; i < edge_num; i++）
    {
        a = odd_edge[i].from;
        b = odd_edge[i].to;
        c = odd_edge[i].dis;
        if （point_flag[a] == 1 && point_flag[b] == 1）
            // 如果两点均未相连
        {
            point_flag[a] = point_flag[b] = 0;    // 置标记位为0
            tmp_edge[step] = i;
            search_edge（count + c step + 1）;
            point_flag[a] = point_flag[b] = 1;
        }
    }
}

void dijkstra_to_add_edge（int s int e） //用dijkstra算法确定从该始点到终点的最短路径
{
    int dis[MAX_NODE];       // 点到起始（s）点的距离
    int used[MAX_NODE];      // 标记位
    int pre[MAX_NODE];       // 记录其从哪一点过来的，方便回溯

    memset（used 0 sizeof（used））;   // 初始化
    for （int i = 1; i <= n; i++）
    {
        dis[i] = INF;
    }
    dis[s] = 0;

    while （1）
    {
        int v = -1;
        for （int i = 1; i <= n; i++）
        {
            if （!used[i] && （v == -1 || dis[i] < dis[v]））
            {
                v = i;
            }
        }
        if （v == e || v == -1）
        // 当当前点是末点e时或本身v就是最小时
            break;
        used[v] = 1;    // 修改标记位
        for （int i = 1; i <= n; i++）
        {
            if （map[v][i].cost < INF && （dis[v] + map[v][i].cost） < dis[i]）
            {
                pre[i] = v;
        

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      15641  2018-04-28 13:28  研讨代码以及测试用例\Debug\main.o

     文件      64197  2018-04-28 13:28  研讨代码以及测试用例\Debug\yantao.exe

     文件         53  2018-04-23 14:51  研讨代码以及测试用例\in1.txt

     文件         44  2018-04-23 15:01  研讨代码以及测试用例\in2.txt

     文件         63  2018-04-23 16:04  研讨代码以及测试用例\in3.txt

     文件         68  2018-04-23 16:07  研讨代码以及测试用例\in4.txt

     文件         39  2018-04-23 14:19  研讨代码以及测试用例\in5.txt

     文件         42  2018-04-26 10:42  研讨代码以及测试用例\in6.txt

     文件       7583  2018-04-28 13:28  研讨代码以及测试用例\main.cpp

     文件         37  2018-04-28 13:18  研讨代码以及测试用例\out1.txt

     文件         31  2018-04-28 13:22  研讨代码以及测试用例\out2.txt

     文件         40  2018-04-28 13:24  研讨代码以及测试用例\out3.txt

     文件         43  2018-04-28 13:26  研讨代码以及测试用例\out4.txt

     文件         25  2018-04-28 13:28  研讨代码以及测试用例\out5.txt

     文件         34  2018-04-28 13:17  研讨代码以及测试用例\out6.txt

     文件       1478  2018-04-28 13:39  研讨代码以及测试用例\yantao.mdsp

     文件     173433  2018-04-28 12:21  DS研讨第七题—第十四小组.pptx

     目录          0  2018-04-28 13:28  研讨代码以及测试用例\Debug

     目录          0  2018-04-28 13:39  研讨代码以及测试用例

----------- ---------  ---------- -----  ----

               262851                    19