数据结构课程设计

重庆交通大学。

学生实验报告。

实验课程名称数据结构课程设计

开课实验室计算机中心。

学院级专业班

学生姓名。学号。

开课时间至学年第学期。

一．需求分析。

问题归纳为：从某一个城市出发，到达另一个城市，求所有可能花费最多的路费。路费与路程成正比，所以应先求任意两点间的最短路径中的最长路径，即树的直径。

考虑到当数据较大时用floyd算法耗时太长，时间复杂度o（n^3）过高，故采用两次dfs深度优先遍历求出树的直径，而非floyd算法。第一次dfs遍历从任意一点开始，找出最远点，第二次dfs从这个最远点开始，得到的最远点与这一个最远点的路径就是这棵树的直径（最长路），时间复杂度为o（nlogn）。

二．概要设计：

1）存储结构。

vector是c++提供的容器的一种，也就是存储数据，考虑到vector在原本使用数组的地方均可以替代，并且其可以动态增长，不需要考虑大小，所以用vector存储边以及边的权值。如g[0]存储与第1个点相连的边。e[0]存储与g[0]中对应边的权值。

同时vector还具备随机存取的优点，也就是可以使用下标访问。vector添加数据的方法是push_back()。push_back()函数表示将数据添加到vector的尾部，并按需要来分配内存。

vector g[1000005]; 存储边。

vector e[1000005]; 存储边的权值（距离）

for(int i=0;i

如上图，存储格式如下：

g[1] g[2] g[3] g[4] g[5]……

e[1] e[2] e[3] e[4] e[5]……

2）dfs遍历函数。

深度优先遍历是连通图的一种遍历策略。其基本思想如下：

设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。

1.从1开始，首先找到1的关联顶点2

2.由2出发，找到4；由4出发，没有关联的顶点。

3.回到2，从2出发，找到5；由5出发，没有关联的顶点。

4.回到1，出1出发，找到4，遍历完毕。

所以最后顺序是1，2，4，5，3。

深度优先遍历函数**如下：

void dfs(int u)

vis[u]=1;

int size=g[u].size();

for(int i=0;i

三．详细设计：

#include

#define inf 1000000000 //表示无穷大。

using namespace std;

vector g[1000005]; 存储边。

vector e[1000005]; 存储边对应的权值（距离）

bool vis[1000005]; 存储点的访问情况，值=1时表示已经该点被访问过，0表示未被访问。

int d[1000005]; 存储初始点至任意点的距离。

void init() 重置所有点为未访问状态的函数。

memset(vis, 0, sizeof(vis));

void dfs(int u) /深度优先遍历函数

vis[u]=1;

int size=g[u].size();

for(int i=0;i

int main()

int n;

cin>>n;

int u,v,w;

for(int i=0;i

// 第一遍dfs遍历，选取任意一点为初始点。

init();

for(i=0;i d[i]=(i==0?0:inf);

dfs(0);

int start=0;

int max=-1;

for(i=0;i if(d[i]>max&&d[i]!=inf)

max=d[i];

start=i; /更新最远点。

// 第二遍dfs遍历，以第一次遍历的最远点作初始点。

init();

for(i=0;i d[i]=(i==start?0:inf);

dfs(start);

int ans=-1;

for(i=0;i if(d[i]>ans&&d[i]!=inf)

ans=d[i]; 更新最远距离。

ans=10*ans+ans*(ans+1)/2;

cout<}

四．调试分析：

根据输入可得知各城市之间的交通情况，如下图：

可以看出，最长路径为4---2---5，路径长度为9千米。

而题目说道，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。所以总花费为 1+10+2+10+3+10+4+10+5+10+6+10+7+10+8+10+9+10=135。

输出正确。

五．总结：。

1．对vector容器的理解。vector是c++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

2．对求树的直径的两种思想的理解：floyd算法与dfs两次遍历。floyd算法，只需要一个三重for循环结构便能求出任意两个顶点之间的最短路径，虽然算法简单，但是时间复杂度o（n^3）较高，只适合适合数据量较小的情况，对于大量数据的处理，所需时间过长。

而dfs两次遍历思想运用了树直径的一个性质：树上任意某个节点到树上任意节点的最远距离的端点一定会是树上某一个直径的两个端点之一。所以先从任意一点开始第一次dfs遍历，找出最远点，然后再从这个最远点开始第二次dfs得到的最长路径便是树的直径，大大缩减了算法执行时间。

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了