数据结构课程设计 带权无向图及景区路线规划

中国地质大学（武汉）数据结构课程设计项目3，带权无向图及路线规划，使用双链表和哈希表辅助实现的高效带权无向图数据结构，内附完整代码和注释，以及作业要求和测试数据。

#include“stdafx.h“
#include 

struct String
{
	string str;
	int key;
	String（string s = ““）
	{
		key = 0;
		str = s;
		for （size_t i = 0; i < str.length（）; i++）
		{
			key = key + （int）str[i]*（i*i*i）;
		}
	}
	int operator+（String &s）
	{
		return key + s.key;
	}
	int operator+（const int &x）
	{
		return key + x;
	}
	bool operator==（const String &s）const
	{
		return str == s.str;
	}
};

void infileV（ifstream &in Graphlnk &G）
{
	clock_t pre_time = clock（）;
	string s;
	while （in >> s）
	{
		String v（s）;
		G.addVertex（v）;
	}
	cout << “插入点: “ << clock（） - pre_time << “ms“ << endl;
}

void infileE（ifstream &in Graphlnk &G）
{
	clock_t pre_time = clock（）;
	string s1 s2;
	int w;
	while （in >> s1 >> s2 >> w）
	{
		String v1（s1） v2（s2）;
		G.addEdge（v1 v2 w）;
	}
	cout << “插入边: “ << clock（） - pre_time << “ms“ << endl;
}

void infileReE（ifstream &in Graphlnk &G）
{
	clock_t pre_time = clock（）;
	string s1s2;
	while （in >> s1 >> s2）
	{
		String v1（s1） v2（s2）;
		G.removeEdge（v1 v2）;
	}
	cout << “删除边: “ << clock（） - pre_time << “ms“ << endl;
}

void infileReV（ifstream &in Graphlnk &G）
{
	clock_t pre_time = clock（）;
	string s;
	while （in >> s）
	{
		String v（s）;
		G.removeVertex（v）;
	}
	cout << “删除点: “ << clock（） - pre_time << “ms“ << endl;
}

bool infilecheV（ifstream &inv ifstream &ino Graphlnk &G）
{
	int xy = 0;
	inv >> x;
	string sv sot;
	string *s = new string[x];
	while （ino>>so）
	{
		s[y] = so;
		y++;
	}
	y = 0;
	clock_t pre_time = clock（）;
	while （inv >> sv）
	{
		String v（sv）;
		pre_time = clock（）;
		if （G.isVertex（v））
			t = “yes“;
		else
			t = “no“;
		if （t != s[y]）
		{
			delete[] s;
			return false;
		}
		y++;
	}
	cout << “查询点: “ << clock（） - pre_time << “ms“ << endl;
	delete[] s;
	return true;
}

bool infilecheDegree（ifstream &inv ifstream &ino Graphlnk &G）
{
	int t x y = 0;
	inv >> x;
	int *d = new int[x];
	string sv;
	while （ino >> x）
	{
		d[y] = x;
		y++;
	}
	y = 0;
	clock_t pre_time = clock（）;
	while （inv >> sv）
	{
		String v（sv）;
		t = G.degree（v）;
		if （t != d[y]）
		{
			delete[] d;
			return false;
		}
		y++;
	}
	cout << “查询度: “ << clock（） - pre_time << “ms“ << endl;
	delete[] d;
	return true;
}

bool infilecheE（ifstream &inv ifstream &ino Graphlnk &G）
{
	int x y = 0;
	inv >> x;
	string sv1 sv2 so t;
	string *s = new string[x];
	while （ino >> so）
	{
		s[y] = so;
		y++;
	}
	y = 0;
	clock_t pre_time = clock（）;
	while （inv >> sv1 >>sv2）
	{
		String v1（sv1）v2（sv2）;
		if （G.isEdge（v1v2））
			t = “yes“;
		else
			t = “no“;
		if （t != s[y]）
		{
			delete[] s;
			return false;
		}
		y++;
	}
	cout << “查询边: “ << clock（） - pre_time << “ms“ << endl;
	delete[] s;
	return true;
}

bool infilecheW（ifstream &inv ifstream &ino Graphlnk &G）
{
	int t x y = 0;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件      921730  2018-12-25 16:17  2018年秋数据结构课程设计A.pdf
     目录           0  2019-03-09 21:01  Finalprj\
     目录           0  2019-03-09 21:00  Finalprj\Finalprj\
     文件        5638  2019-01-17 23:07  Finalprj\Finalprj\DblinkList.h
     文件        6429  2019-01-17 23:27  Finalprj\Finalprj\Finalprj.vcxproj
     文件        1708  2019-01-10 01:38  Finalprj\Finalprj\Finalprj.vcxproj.filters
     文件         165  2019-01-08 17:09  Finalprj\Finalprj\Finalprj.vcxproj.user
     文件         175  2019-01-10 07:14  Finalprj\Finalprj\Global_Variable.h
     文件       12755  2019-01-17 23:09  Finalprj\Finalprj\GraphLnk.h
     文件        3246  2019-01-15 19:30  Finalprj\Finalprj\HashTable.h
     文件        1514  2019-01-16 22:40  Finalprj\Finalprj\MSTEdgeTree.h
     文件        3193  2019-01-15 19:36  Finalprj\Finalprj\MinHeap.h
     文件        1369  2019-01-15 19:36  Finalprj\Finalprj\UFSets.h
     文件         171  2019-01-18 11:03  Finalprj\Finalprj\checkdegree.txt
     文件          90  2019-01-18 11:03  Finalprj\Finalprj\checkdegreeo.txt
     文件         476  2019-01-18 11:03  Finalprj\Finalprj\checke.txt
     文件         101  2019-01-18 11:03  Finalprj\Finalprj\checkeo.txt
     文件         181  2019-01-18 11:03  Finalprj\Finalprj\checkv.txt
     文件         108  2019-01-18 11:03  Finalprj\Finalprj\checkvo.txt
     文件         453  2019-01-18 11:03  Finalprj\Finalprj\checkw.txt
     文件         108  2019-01-18 11:03  Finalprj\Finalprj\checkwo.txt
     文件       55591  2019-01-18 11:03  Finalprj\Finalprj\e_in.txt
     文件       55248  2019-01-18 11:03  Finalprj\Finalprj\e_in2.txt
     文件      283659  2019-01-17 11:41  Finalprj\Finalprj\e_in3.txt
     文件    10189614  2019-01-16 23:00  Finalprj\Finalprj\e_in4.txt
     文件         465  2019-01-18 11:03  Finalprj\Finalprj\in.txt
     文件         185  2019-01-18 11:03  Finalprj\Finalprj\in2.txt
     文件         526  2019-01-17 11:41  Finalprj\Finalprj\in3.txt
     文件         387  2019-01-17 11:41  Finalprj\Finalprj\rin.txt
     文件       10546  2019-01-17 23:28  Finalprj\Finalprj\stdafx.h
     文件        8795  2019-01-18 11:21  Finalprj\Finalprj\test.cpp
............此处省略26个文件信息