数据结构课设指北

版本3：12.13修改

最近张老师（其实我也不确定谁出的，但感觉张老师有这个水平）出了一道有意思的题目，有很多学弟学妹来问我，为了方便省的每个人都要来问我好几遍，我就把我个人的思路给大家分享一下。

首先题目：

本课程设计为独立设置的课程综合设计，学分为2.0（物联网工程），主要涉及C语言、数据结构等课程知识，涵盖了本专业的主要专业课程知识。

背景： 儋州校区是个风景如画的校区，这里不但有着浓厚的人文学习氛围，也有美丽的风景。假设你父母或者朋友来儋州校区旅游，但是他们的时间有限，要在最短的时间内走完儋州校区主要的教学、办公、旅游点，你如何才能当好这个导游？给定儋州校区地图，并标注了主要的教学楼、办公地点和景点及其距离。

问题描述： 图的最短路径问题是指从指定的某一点v开始，求得从该地点到其他每个顶点的最短路径。给出求得的最短路径的长度以及途径的地点。除了完成最短路径的求解外，还能对该图进行修改，如顶点及边的增删，边上权值的修改等。

主要元素包括：

1. 顶点：教学点、办公点、景点。
2. 边数：各地点之间道路数。
3. 边长（权值）：距离。

功能要求：

1. 输出顶点信息：各个教学、办公、景点名称

2. 边的信息：将任意两个位置之间的距离输出（如果有直接路径）

3. 修改：修改两个位置之间的距离，重新输出每两个位置之间的距离。

4. 删除：删除任意一条边。

5. 插入：插入任意一条边。

6. 求最短路径：给出任意两个点，输出两点之间的路径长度及途径地点，输出任一点与其他各点的最短路径。

我就直接就事论事，直接按着题目要求来说：

题目要求1-5都是很基础的问题，临近期末如果是我写肯定选用邻接矩阵，这样实现速度最快，效率最高。

前两个就不说了没什么可说的，实在太简单。

修改：这个需要注意的是，在存在的情况修才能修改，然后读入修改目标，读入修改内容直接修改数组对应内容即可。

删除：这个要注意的是，如何删除，对于最短路问题来说，永远不能到达的距离就相当于删除，所以建议直接赋值成一个很大的数字。

插如：和上边一样都是直接赋值。

求最短路径：这个其实有两个要求，一个是输出距离，一个是输出路径，这里推荐两个算法一个是Floyd 一个是Dijkstra，因为这一段在学算法，顺便就把这两个写了一下，练练手。

用户交互界面设计：推荐用一个while死循环，轮询用户可能输入的内容。

就像这个一样：

while(1)//死循环保持一直运行
	{
		printf("\r\n 请输入命令序号 来开启任务\r\n");
		scanf("%d",命令); //读入命令
		if(命令 == 0)//每一个都是先输入命令序号开始命令 再输入起始地点和结束地点
		else if(命令 == 1)//某一个命令执行
            
         else if(命令 == 2)//某一个命令
             
		else if(命令 == 3)//某一个命令
            
		else if(命令 == 4)//某一个命令
            
		else if(命令 == 5)//某一个命令
            
	}

每一个操作像修改、删除、插入都差不多。

void 某个操作()//操作函数
{
	//读入输入参数
    //赋值
    //结束
}

图的建立，图的情况很简单，看图片应该是单向图。

既然用了数组，那就直接赋值就行了

int 二维数组[][]=
{
    [东门][教学楼]=距离
    //直接对应地图赋值即可
}

最短路算法：

我直接给两段大概的代码吧，具体怎么写自己看看。网上教程很多。。

不详细写了。

void fold()//弗洛伊德算法
{
	int k=0,i=0,j=0;
     for(k=0;k< N;k++)
        for(i=0;i< N;i++)
			for(j=0;j< N;j++)
				if(边[i][j]>边[i][k]+边[k][j])
					 边[i][j]=边[i][k]+边[k][j];
}

/*
与求最短路相比，增加一个path数组，来记录最短路的路径
先将path[i]=-1，之后每次找出最短路的点p后将path[j]=p
用path[j]=i表示从i到j最短路的路径
*/

void Dijkstra(int number,int target)//Dijkstra算法//随便手写的记不太清楚了大概这样
{
    int i,j,k;
    int min;
    int tmp;
    int flag[MAX];      // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。

    // 初始化
    for (i = 0; i < G.vexnum; i++)
    {
        flag[i] = 0;              // 顶点i的最短路径还没获取到。
        prev[i] = 0;              // 顶点i的前驱顶点为0。
        dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。
    }

    // 对"顶点vs"自身进行初始化
    flag[vs] = 1;
    dist[vs] = 0;

    // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。
    for (i = 1; i < G.vexnum; i++)
    {
        // 寻找当前最小的路径；
        // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。
        min = INF;
        for (j = 0; j < G.vexnum; j++)
        {
            if (flag[j]==0 && dist[j]<min)
            {
                min = dist[j];
                k = j;
            }
        }
        // 标记"顶点k"为已经获取到最短路径
        flag[k] = 1;

        // 修正当前最短路径和前驱顶点
        // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。
        for (j = 0; j < G.vexnum; j++)
        {
            tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出
            if (flag[j] == 0 && (tmp  < dist[j]) )
            {
                dist[j] = tmp;
                prev[j] = k;
            }
        }
	}
        //路径记录方法//需要逆向读取
	for(int j=1; j<=n; j++)
    {
        if(!visited[j] && dis[p]+mapp[p][j]<dis[j])
        {
            dis[j]=dis[p]+mapp[p][j];
            path[j]=p;
        }
	}
	
}