运行效果：
说明:
由于当年还不会使用多线程，所以很多获取用户点击的地方都是使用循环实现的。。。CPU占用率会比较高。
代码：
//校园导游系统.cpp
1 #include <graphics.h>
#include <conio.h>
#include <stdio.h>
#include <io.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <math.h>
#include <fstream>
#include "Stack.h"
#include "functions.h"
#include "Graph_List.h"
#define WIDTH (1000+(LEFTBORDER*2))
#define HEIGHT (574+TOPBORDER+LEFTBORDER)
#define UP 72
#define DOWN 80
#define LEFT 75
#define RIGHT 77
#define BACKGROUND "background.jpg"
#define BKCOLOR RGB(240,240,240) //原RGB(240,240,240)
#define SELECTCOLOR RGB(255,0,0) //原RED
#define TEXTCOLOR RGB(7,102,198)//GREEN// //原BLUE
#define MENUCOLOR RGB(208,161,227)//RGB(77,197,131)//RGB(112,112,112)//RGB(117,75,144)//RGB(7,102,198) //原GREEN
#define CheckCancel if(iscancel){return -1;}
using namespace std;
Graph_List graph;
int choose;
int menunum = ;
int menutop1 = ;
int menutop = (menutop1 + );
#define left (LEFTBORDER)
int menuwidth = ((WIDTH - * LEFTBORDER) / (menunum ));
int menuheight = ;
int GetChoose();
int FrontMenu(Graph_List &graph );
int ShowAllVertex(Graph_List &graph);
int ShowAllPath(Graph_List &graph);
int printroad(int dx, int dy, int sx, int sy) {
LINESTYLE linestyle;
getlinestyle(&linestyle);
setlinestyle(PS_SOLID,,NULL,);
setlinecolor(BLUE);
line(sx,sy,dx,dy);
setlinestyle(&linestyle);
double x1 = (sx + dx) / ;
double y1 = (sy + dy) / ;
double x2 = ((3.0 / 8.0) * sx + (5.0 / 8.0) * dx);
double y2 = ((3.0 / 8.0) * sy + (5.0 / 8.0) * dy);
//double x1=sx,x2=(sx+dx)/2,y1=sy,y2=(sy+dy)/2;
double k1 = (y2 - y1) / (x2 - x1);
double k2 = (-) / k1;
double delta = ; //=(y2-y1)*(y2-y1)+(x2-x1)*(x2-x1);
double a = sqrt((delta / ) / ( + k2 * k2));
double b = a * fabs(k2);
if(((x1 > x2) && (y1 < y2)) || ((x1 < x2) && (y1 > y2))) {
} else {
b = - * b;
}
if(x1 == x2) {
a = ;
b = ;
}
if(y1 == y2) {
a = ;
b = ;
}
POINT pts[] = { {x1, y1}, {x2 + a, y2 + b}, {(x1 + x2) / , (y1 + y2) / }, };
POINT pts1[] = { {x1, y1}, {x2 * - (x2 + a), y2 * - (y2 + b)}, {(x1 + x2) / , (y1 + y2) / }, };
setfillcolor(BLUE);
solidpolygon(pts1, );
solidpolygon(pts, );
return ;
}
int GetMouseXY(int& mousex,int& mousey) {
MOUSEMSG temp;
temp.mkLButton = false;
bool kick = false;
while(!kick) {
// if(MouseHit()) {
temp = GetMouseMsg();
FlushMouseMsgBuffer();
if(temp.mkLButton == false) {
mousex = temp.x;
mousey = temp.y;
}
else {
kick = temp.mkLButton ;
}
// }
}
return ;
}
int AddVertex(Graph_List &graph) {
LOGFONT font;
gettextstyle(&font);
settextstyle(, , _T("宋体"));
BeginBatchDraw();
setlinecolor(GREEN);
for(int lx = LEFTBORDER; lx <= WIDTH; lx += ) {
//outtextxy(lx, TOPBORDER - 10, &int_to_str(lx - LEFTBORDER)[0]);
line(lx, TOPBORDER, lx, HEIGHT - LEFTBORDER);
}
for(int ly = TOPBORDER; ly <= HEIGHT - LEFTBORDER; ly += ) {
//outtextxy(10, ly - 5, &int_to_str(ly - TOPBORDER)[0]);
line(LEFTBORDER, ly, WIDTH - LEFTBORDER, ly);
}
FlushBatchDraw();
setlinecolor(MENUCOLOR);
settextstyle(&font);
::MessageBox(GetHWnd(), "请在您要添加景点的位置点击", "添加景点", MB_OK);
int mousex,mousey;
GetMouseXY(mousex,mousey);
char name[];
bool iscancel = false;
iscancel = !InputBox(&(name[]), , "输入名称" , "添加景点", "", , , );
CheckCancel
char describe[];
iscancel = !InputBox(&(describe[]), , "输入简介：(按Ctrl+Enter确认输入)" , "添加景点", "", , , );
CheckCancel
char mark[];
int marki;
while() {
iscancel = !InputBox(&(mark[]), , "输入代号" , "添加景点", , , , );
CheckCancel
marki = str_to_num(mark);
if(marki > && graph.GetIndex(marki) == -) {
break;
}
::MessageBox(GetHWnd(), "此代号已存在，请重输", "添加景点", MB_OK);
}
string namestr = "", describestr = "";
graph.InsertVertex((string)(namestr + name), (string)(describestr + describe), marki, mousex, mousey);
::MessageBox(GetHWnd(), "添加成功", "添加景点", MB_OK);
return ;
}
int AddPath(Graph_List &graph) {
bool iscancel = false;
int v1, v2;
string source = "", destination = "", weightstr = "";
while() {
iscancel = !InputBox(&(source[]), , "输入起点代号" , "添加边", "", , , );
CheckCancel
v1 = str_to_num(source);
if(graph.GetIndex(v1) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "添加边", MB_OK);
}
while() {
iscancel = !InputBox(&(destination[]), , "输入终点代号", "添加边", "", , , );
CheckCancel
v2 = str_to_num(destination);
if(graph.GetIndex(v2) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "添加边", MB_OK);
}
double dx = graph.GetHead()[graph.GetIndex(v2)].GetX();
double sx = graph.GetHead()[graph.GetIndex(v1)].GetX();
double dy = graph.GetHead()[graph.GetIndex(v2)].GetY();
double sy = graph.GetHead()[graph.GetIndex(v1)].GetY();
double weight = (double)sqrt(((dx - sx) * (dx - sx) + (dy - sy) * (dy - sy)) / 24250.0) * 300.0;
int retop=graph.InsertEdge(graph.GetIndex(v1), graph.GetIndex(v2), weight);
if(retop==-){::MessageBox(GetHWnd(), "起点与终点相同！", "添加边", MB_OK);return -;}
if(retop==-){::MessageBox(GetHWnd(), "边已存在！", "添加边", MB_OK);return -;}
::MessageBox(GetHWnd(), "添加成功", "添加边", MB_OK);
return ;
}
int DeleteVertex(Graph_List &graph){
bool iscancel = false;
char v[];
int v1;
while() {
iscancel = !InputBox(&(v[]), , "输入代号" , "删除景点", "", , , );
CheckCancel
v1 = str_to_num(v); if(graph.GetIndex(v1)!= -) {
break;
}
::MessageBox(GetHWnd(), "此代号不存在，请重输", "删除景点", MB_OK);
}
graph.DeleteVertex(graph.GetIndex(v1));
return ;
}
int DeletePath(Graph_List &graph) {
bool iscancel = false;
int v1, v2;
string source = "", destination = "";
while() {
iscancel = !InputBox(&(source[]), , "输入起点代号" , "删除边", "", , , );
CheckCancel
v1 = str_to_num(source);
if(graph.GetIndex(v1) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "删除边", MB_OK);
}
while() {
iscancel = !InputBox(&(destination[]), , "输入终点代号", "删除边", "", , , );
CheckCancel
v2 = str_to_num(destination);
if(graph.GetIndex(v2) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "删除边", MB_OK);
}
int retop=graph.DeleteEdge(graph.GetIndex(v1), graph.GetIndex(v2));
if(retop==-){::MessageBox(GetHWnd(), "边不存在！", "删除边", MB_OK);return -;} ::MessageBox(GetHWnd(), "删除成功", "删除边", MB_OK);
return ;
}
int DrawShortestPath(Graph_List &graph, int v1, int v2) {
Vertex *Head = graph.GetHead(); int *path = new int [graph.NumberOfVertices()];
graph.DShortestPath(v1, path);
LStack<int > stack;
//stack.Push(v2);
if(path[v2] == -) {
::MessageBox(GetHWnd(), "*** 无路径 ***", "查询路径", MB_OK);
return -;
}
int i = v2;
while(i != path[v1]) {
stack.Push(i);
i = path[i];
}
delete []path;
//stack.Push(v1);
int temp = v1, temppre = v1, length = ;
string pathstr,tempstr;
BeginBatchDraw();
while(!stack.IsEmpty()) {
stack.Pop(temp);
printroad(Head[temppre].GetX(), Head[temppre].GetY(), Head[temp].GetX(), Head[temp].GetY());
int pathweight=graph.GetWeight(temppre, temp);
length += pathweight;
tempstr=tempstr+"从"+int_to_str(Head[temppre].GetMark())+"到"+int_to_str(Head[temp].GetMark())+" : "+int_to_str(pathweight)+" 米"+"\n";
temppre = temp;
} FlushBatchDraw();
setbkcolor(BKCOLOR);
settextcolor(TEXTCOLOR);
string str = "最短路径长度为：";
str = str + int_to_str(length) + " 米\n"+"步行所需时间："+int_to_str(length/)+"分钟\n";
str+=tempstr;
::MessageBox(GetHWnd(), &str[], "查询路径", MB_OK);
return ;
}
int FindPath(Graph_List &graph) {
bool iscancel = false;
int v1, v2;
string source = "", destination = "";
while() {
iscancel = !InputBox(&(source[]), , "输入起点代号" , "查询路径", "", , , );
CheckCancel
v1 = str_to_num(source);
if(graph.GetIndex(v1) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "查询路径", MB_OK);
}
while() {
iscancel = !InputBox(&(destination[]), , "输入终点代号", "查询路径", "", , , );
CheckCancel
v2 = str_to_num(destination);
if(graph.GetIndex(v2) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "查询路径", MB_OK);
}
DrawShortestPath(graph, graph.GetIndex(v1), graph.GetIndex(v2));
return ;
}
void ShowVertex(Graph_List &graph, int i) {
Vertex *Head = graph.GetHead();
if(i < || i > graph.NumberOfVertices() - ) {
::MessageBox(GetHWnd(), "查询位置不存在", "景点查询", MB_OK); //GetHWnd()获得窗口句柄
return ;
}
string str = "代号：" +int_to_str(Head[i].GetMark()) + "\n" + "简介: " + Head[i].GetDescribe();
str = "名称：" + Head[i].GetVerName() + "\n" + str;
::MessageBox(GetHWnd(), &str[], "景点查询", MB_OK); //GetHWnd()获得窗口句柄
}
int ModifyMenu() {
int choose1 = ;
char temp = , key;
while(temp != '\r') {
if(kbhit()) {
key = getch();
fflush(stdin);
switch(key) {
case UP: {
choose1--;
};
break;
case DOWN: {
choose1++;
};
}
}
if(choose1 == ) {
choose1 = ;
}
if(choose1 == ) {
choose1 = ;
}
cleardevice();
outtextxy((WIDTH / ) - , , "修改景点");
outtextxy((WIDTH / ) - , , "按↑和↓选择选项");
outtextxy((WIDTH / ) - , , "按ENTER键确定选择");
outtextxy(, , "请选择选项：");
outtextxy(, , "修改名称");
outtextxy(, , "修改简介");
outtextxy(, , "修改代号");
outtextxy(, , "修改坐标");
outtextxy(, , "返回");
outtextxy(, + (choose1 - ) * , "→");
FlushBatchDraw();
temp = getch();
}
return choose1;
}
int ModifyVertex(Graph_List &graph) {
bool iscancel = false;
int v1;
char v1str[] = {'a'};
while() {
iscancel = !InputBox(&(v1str[]), , "输入代号" , "修改景点", "", , , );
CheckCancel
v1= str_to_num(v1str);
if(graph.GetIndex(v1) != -) {
break;
}
::MessageBox(GetHWnd(), "该位置不存在，请重输", "修改景点", MB_OK);
}
int v=graph.GetIndex(v1);
Vertex *Head = graph.GetHead();
string name=Head[v].GetVerName();
string describe=Head[v].GetDescribe();
int marki=Head[v].GetMark(),x=Head[v].GetX()-LEFTBORDER,y=Head[v].GetY()-TOPBORDER;
bool isreturn = false;
while(!isreturn ) {
int in = ModifyMenu();
switch(in) {
case : {
iscancel = !InputBox(&(name[]), , "输入名称" , "修改景点", "", , , );
CheckCancel
};
break;
case : {
iscancel = !InputBox(&(describe[]), , "输入简介：(按Ctrl+Enter确认输入)" , "修改景点", "", , , );
CheckCancel
};
break;
case : {
char mark[];
while() {
iscancel = !InputBox(&(mark[]), , "输入代号" , "修改景点", , , , );
CheckCancel
marki = str_to_num(mark);
if(marki > && (marki == Head[v].GetMark() || graph.GetIndex(marki) == -)) {
break;
}
::MessageBox(GetHWnd(), "输入有误或代号已存在，请重输", "修改景点", MB_OK);
}
};
break;
case : {
char xstr[], ystr[];
while() {
iscancel = !InputBox(&(xstr[]), , "输入X坐标" , "修改景点", "", , , );
CheckCancel
x = str_to_num(xstr);
if(x > && x < WIDTH) {
break;
}
::MessageBox(GetHWnd(), "您所输入的坐标不在图像范围内", "修改景点", MB_OK);
}
while() {
iscancel = !InputBox(&(ystr[]), , "输入Y坐标" , "修改景点", "", , , );
CheckCancel
y = str_to_num(ystr);
if(y > && y < HEIGHT) {
break;
}
::MessageBox(GetHWnd(), "您所输入的坐标不在图像范围内", "修改景点", MB_OK);
}
};
break;
case : {
graph.ModifyVertex(v, name,describe, marki, x, y);
ShowVertex(graph, v);
isreturn = true;
};
break;
default:
{};
break;
}
}
return ;
}
int ShowAllVertex(Graph_List &graph){
Vertex *Head = graph.GetHead();
//putimage(LEFTBORDER, TOPBORDER, graph.GetMap());
setbkcolor(RGB(, , ));
settextcolor(RED);
setfillcolor(RGB(,,));
LOGFONT font1;
gettextstyle(&font1);
settextstyle(font1.lfHeight - , , _T("宋体"));
for(int i = ; i <= graph.NumberOfVertices() - ; i++) {
int x = Head[i].GetX(), y = Head[i].GetY();
string str = "";
str += int_to_str(Head[i].GetMark());
if(Head[i].GetVerName() != "*")
str = str + " " + Head[i].GetVerName();
solidcircle(x,y,);
outtextxy( x, y, &str[]);
}
settextstyle(&font1);
FlushBatchDraw();
return ;
}
int ShowAllPath(Graph_List &graph) {
LINESTYLE linestyle;
getlinestyle(&linestyle);
setlinestyle(PS_SOLID,,NULL,);
setlinecolor(BLUE);
for(int i=;i<=graph.NumberOfVertices()-;i++){
Edge* p=graph.GetHead()[i].Getadj();
while(p!=NULL){
line(graph.GetHead()[i].GetX(),graph.GetHead()[i].GetY(),graph.GetHead()[p->GetVerAdj()].GetX(),graph.GetHead()[p->GetVerAdj()].GetY());
p=p->Getlink();
}
}
setlinestyle(&linestyle);
FlushBatchDraw();
return ;
}
int FindMenu() {
int choose1 = ;
char temp = , key;
while(temp != '\r') {
if(kbhit()) {
key = getch();
fflush(stdin);
switch(key) {
case UP: {
choose1--;
};
break;
case DOWN: {
choose1++;
};
}
}
if(choose1 == ) {
choose1 = ;
}
if(choose1 == ) {
choose1 = ;
}
cleardevice();
outtextxy((WIDTH / ) - , , "查询景点");
outtextxy((WIDTH / ) - , , "按↑和↓选择选项");
outtextxy((WIDTH / ) - , , "按ENTER键确定选择");
outtextxy(, , "请选择选项：");
outtextxy(, , "按代号查询");
outtextxy(, , "按名称查询");
outtextxy(, , "返回");
outtextxy(, + (choose1 - ) * , "→");
FlushBatchDraw();
temp = getch();
}
return choose1;
}
int FindVertex(Graph_List &graph) {
bool iscancel = false;
bool isreturn = false;
while(!isreturn ) {
int in = FindMenu();
switch(in) {
case : {
char v1str[] = {'a'};
int v1;
iscancel = !InputBox(&(v1str[]), , "输入代号" , "查询景点", "", , , );
CheckCancel
v1 = str_to_num(v1str); ShowVertex(graph, graph.GetIndex(v1));
};
break;
case : {
char v1str[] = {'a'};
string v1;
iscancel = !InputBox(&(v1str[]), , "输入名称" , "查询景点", "", , , );
CheckCancel
v1 = "";
v1 += v1str;
ShowVertex(graph, graph.GetIndex(v1));
};
break;
case : { isreturn = true;
};
break;
default:
{};
break;
}
}
return ;
}
int Open(Graph_List &graph, bool isfirstopen) {
fstream filestr;
char mapname[] = {'a'};
if(isfirstopen) {
filestr.open ("map.txt");
strcpy(mapname, "map.jpg");
} else {
bool iscancel = false;
char filename[] = {'a'};
while() {
iscancel = !InputBox(&(filename[]), , "输入文本文件名(不需输'.txt')" , "打开", "", , , );
CheckCancel
strcat(filename, ".txt");
filestr.open (filename);
if (filestr.is_open()) {
break;
}
::MessageBox(GetHWnd(), "无此文件，请重输", "打开", MB_OK);
}
while() {
iscancel = !InputBox(&(mapname[]), , "输入图片文件名(不需输'.jpg')" , "打开", "", , , );
CheckCancel
strcat(mapname, ".jpg");
if( (_access(mapname, )) != - ) {
break;
}
::MessageBox(GetHWnd(), "无此文件，请重输", "打开", MB_OK);
}
}
graph.graph_con(filestr, mapname);
filestr.close();
putimage(LEFTBORDER, TOPBORDER, graph.GetMap());
return ;
}
int Save(Graph_List &graph) {
bool iscancel = false;
Vertex *Head = graph.GetHead();
char filename[] = {'a'};
iscancel = !InputBox(&(filename[]), , "输入文本文件名(不需输'.txt')" , "保存", "", , , );
CheckCancel
strcat(filename, ".txt");
graph.SaveFile(filename);
::MessageBox(GetHWnd(), "保存成功", "保存", MB_OK);
return ;
}
int GetChoose() {
FlushMouseMsgBuffer();
MOUSEMSG temp;
temp.mkLButton = false;
bool kick = false;
while(!kick) {
// if(MouseHit()) {
temp = GetMouseMsg();
FlushMouseMsgBuffer();
if(temp.mkLButton == false) {
} else {
if(temp.y < menutop + menuheight &&temp. y > menutop) {
kick = true;
}
}
// }
}
choose = (temp.x - left) / menuwidth;
return ;
}
int FrontMenu(Graph_List &graph) {
fflush(stdin);
settextcolor(TEXTCOLOR);
setfillcolor(BKCOLOR);
solidrectangle(, TOPBORDER, WIDTH, HEIGHT); //以背景色刷新
setfillcolor(MENUCOLOR);
solidrectangle(, , WIDTH - , menutop1); //画最上方的绿色条
putimage(LEFTBORDER, TOPBORDER, graph.GetMap());
setfillcolor(BKCOLOR);
solidrectangle(LEFTBORDER, menutop + textheight('a'), WIDTH - LEFTBORDER, menutop + textheight('a') + ); //去掉选中的菜单下方的小绿块
setfillcolor(TEXTCOLOR);
setfillcolor(MENUCOLOR);
solidrectangle(choose * menuwidth + left, menutop + textheight('a'), (choose + )*menuwidth + left, menutop + textheight('a') + ); //画选中的菜单下方的小绿块
roundrect(, menutop + textheight('a') + , WIDTH - , HEIGHT - , , ); //画图片周围的绿色边框
solidrectangle(, menutop + textheight('a') + , WIDTH - , menutop + textheight('a') + ); //画图片上方与小绿块相连的绿色条
setfillcolor(TEXTCOLOR);
LOGFONT font1;
gettextstyle(&font1);
settextstyle(font1.lfHeight, , _T("宋体"));
string menu[] = {" 打开", " 显示", " 查询路径", " 查询景点", " 修改景点", " 添加景点", " 删除景点", " 添加边", " 删除边"," 保存", " 退出"};
for(int index = ; index <= menunum - ; index++) {
if(index == choose)settextcolor(SELECTCOLOR);
const char *p = menu[index].c_str();
outtextxy(left + index * menuwidth, menutop, p);
if(index == choose)settextcolor(TEXTCOLOR);
}
settextstyle(&font1);
setlinecolor(MENUCOLOR);
for(int index1 = ; index1 <= menunum + ; index1++) {
line(left + index1 * menuwidth, menutop, left + index1 * menuwidth, menutop + textheight('a'));
}
LOGFONT font;
gettextstyle(&font);
settextstyle(, , _T("宋体"));
settextcolor(TEXTCOLOR);
for(int lx = LEFTBORDER; lx <= WIDTH; lx += ) {
outtextxy(lx, TOPBORDER - , &int_to_str(lx - LEFTBORDER)[]);
}
for(int ly = TOPBORDER; ly <= HEIGHT - LEFTBORDER; ly += ) {
outtextxy(, ly - , &int_to_str(ly - TOPBORDER)[]);
}
settextstyle(&font);
settextcolor(TEXTCOLOR);
FlushBatchDraw();
setbkcolor(BKCOLOR);
settextcolor(TEXTCOLOR);
return choose;
}
int main() {
graph;
initgraph(WIDTH, HEIGHT); //,0);//SHOWCONSOLE|NOMINIMIZE
setbkcolor(BKCOLOR);
cleardevice();
//int in = INT_MIN;
//FrontMenu(graph);
bool isfirstopen = true;
while() {
FrontMenu(graph);
//ShowAllVertex( graph);
if(isfirstopen) {
choose = ;
}
else {
GetChoose( );
}
FrontMenu(graph);
//ShowAllVertex( graph);
switch(choose) {
case : {
Open(graph, isfirstopen);
isfirstopen = false;
}
break;
case : {
ShowAllPath(graph);
ShowAllVertex( graph);
int vertexnum =graph.NumberOfVertices(),edgenum=graph.NumberOfEdges();
string numofvertices;
numofvertices = "图*有景点 " + int_to_str(vertexnum) + " 个\n"+"共有边 " + int_to_str(edgenum) + " 条\n";
::MessageBox(GetHWnd(), &numofvertices[], "显示", MB_OK);
}
break;
case : {
ShowAllVertex( graph);
FindPath(graph);
ShowAllVertex( graph);
};
break;
case : {
ShowAllVertex( graph);
FindVertex(graph);
};
break;
case : {
ShowAllVertex( graph);
ModifyVertex(graph );
};
break;
case : {
ShowAllVertex( graph);
AddVertex(graph);
};
break;
case : {
ShowAllVertex( graph);
DeleteVertex(graph);
};
break;
case : {
ShowAllPath(graph);
ShowAllVertex( graph);
AddPath( graph);
}
break;
case : {
ShowAllPath(graph);
ShowAllVertex( graph);
DeletePath(graph);
}
break;
case : {
Save(graph);
}
break;
case : {
WinExec(_T("taskkill /f /im conhost.exe /t"), );
//WinExec(_T("taskkill /f /im 校园导游系统.exe /t"), 1);
exit();
}
break;
default: {
}
break;
}
}
return ;
}
//Graph_List.h
1 //******************************** 类定义 ***************************************//
#ifndef _MYGraph_List_h_
#define _MYGraph_List_h_
#define LEFTBORDER 30
#define TOPBORDER 50
#include<string>
#include <fstream>
#include <graphics.h> class Edge
{
private:
int VerAdj;
int cost;
Edge *link;
public:
Edge()
{
VerAdj = -;
cost = -;
link = NULL;
}
Edge(int VerAdji, int costi,Edge *linki): VerAdj(VerAdji), cost(costi),link(linki) //初始化
{
}
int &GetVerAdj()
{
return VerAdj;
}
int &Getcost()
{
return cost;
}
Edge *&Getlink()
{
return link;
}
};
class Vertex
{
private:
string VerName;
string Describe;
Edge *adjacent;
int mark;
int x;
int y;
public:
Vertex()
{
VerName = "*";
Describe = "*";
adjacent = NULL;
mark=-;
x=-;
y=-;
}
string &GetVerName()
{
return VerName;
}
string &GetDescribe ()
{
return Describe;
}
Edge *&Getadj()
{
return adjacent;
}
int & GetMark()
{
return mark;
}
int & GetX()
{
return x;
}
int & GetY()
{
return y;
}
};
class Graph_List
{
private:
Vertex *Head;
int graphsize;
int MaxCost;
IMAGE* map;
int InsertEdge_Do(const int &v1, const int &v2, int weight) //插入时尽量保证顺序排列
{
if(Head[v1].Getadj() == NULL) {
Head[v1].Getadj() = new Edge(v2, weight, NULL); //若邻接表为空 直接在adjacent后添加边
return ;
}
Edge *p = Head[v1].Getadj();
Edge *pt = p;
while((p != NULL)&&(p->GetVerAdj() < v2)) {
pt = p;
p = p->Getlink();
}
if(p == NULL) { //到邻接表末端仍然比v2小
pt->Getlink() = new Edge(v2, weight, NULL);
return ;
}
if(p == Head[v1].Getadj() && p->GetVerAdj() > v2) { //邻接表第一个就比v2大
Edge *q = new Edge(v2, weight, NULL);
q->Getlink() = p;
Head[v1].Getadj() = q;
return ;
}
if(p->GetVerAdj() == v2) {
return -; //插入边已存在 返回-4
}
if(p != Head[v1].Getadj() && p->GetVerAdj() > v2) { //正常在邻接表中间添加的情况
Edge *q = new Edge(v2, weight, NULL);
pt->Getlink() = q;
q->Getlink() = p;
return ;
}
return ;
}
int DeleteEdge_Do(const int &v1, const int &v2)
{
Edge *p = Head[v1].Getadj();
if(p == NULL)
{
return -; //返回-1表示所删除的边不存在
} if(p->GetVerAdj() == v2) //邻接表第一个就是v2的情况
{
Head[v1].Getadj() = p->Getlink();
delete p;
return ;
}
Edge *pt = p;
while(p != NULL)
{
if(p->GetVerAdj() == v2)
{
pt->Getlink() = p->Getlink();
delete p;
break;
}
pt = p;
p = p->Getlink();
}
if(p == NULL) //到邻接表末端仍未找到v2 则边不存在
{
return -; //返回-1表示所删除的边不存在
}
return ;
}
int DeleteGraph_List()
{
for(int i = ; i <= graphsize - ; i++)
{
Edge *p = Head[i].Getadj();
Edge *q = p;
while(p != NULL)
{
p = p->Getlink();
delete q;
q = p;
}
}
delete [] Head;
delete map;
return ;
}
public:
int& GetMaxCost()
{
return MaxCost;
}
Vertex*& GetHead()
{
return Head;
}
IMAGE *& GetMap()
{
return map;
}
int GetIndex(int marki) //按代号查找在顶点表中的位置
{
for(int i = ; i <= graphsize - ; i++)
{
if(marki == Head[i].GetMark())
{
return i;
}
}
return -; //找不到则返回-1
}
int GetIndex(string name) //按名称查找在顶点表中的位置
{
for(int i = ; i <= graphsize - ; i++)
{
if(name == Head[i].GetVerName())
{
return i;
}
}
return -; //找不到则返回-1
}
int graph_con(fstream &file,char* mapname) //插入边创建
{
DeleteGraph_List();//先把类里面之前的内容删除掉
map=new IMAGE;
loadimage(map, _T(mapname));
file >> MaxCost;
file >> graphsize;
Head = new Vertex[graphsize];
for(int i = ; i <= graphsize - ; i++)
{
file >> Head[i].GetVerName();
file >> Head[i].GetDescribe();
file >> Head[i].GetMark();
file >> Head[i].GetX();
Head[i].GetX()+=LEFTBORDER; //加左边界
file >> Head[i].GetY();
Head[i].GetY()+=TOPBORDER; //加上边界
Head[i].Getadj() = NULL;
}
int edgenum;
file >> edgenum;
for(int j = ; j <= edgenum - ; j++)
{
int v1, v2, weight;
file >> v1;
file >> v2;
double dx=Head[GetIndex(v2)].GetX();
double sx=Head[GetIndex(v1)].GetX();
double dy=Head[GetIndex(v2)].GetY();
double sy=Head[GetIndex(v1)].GetY();
weight=(double)sqrt(((dx-sx)*(dx-sx)+(dy-sy)*(dy-sy))/24250.0)*300.0; //通过坐标计算边长度 赋给weight
InsertEdge(GetIndex(v1),GetIndex(v2), weight);
}
return ;
}
Graph_List() //构造函数 构造一个空图
{
Head=NULL;
map=NULL;
map=new IMAGE;
graphsize=;
MaxCost=;
}
~Graph_List(){
DeleteGraph_List();
}
int SaveFile(char* filename){
system("del filename "); //删除文件
ofstream fl(filename);//打开文件用于写，若文件不存在就创建它
if(!fl)return -;//打开文件失败则结束运行
fl << GetMaxCost() << endl;
fl << NumberOfVertices() << endl;
for(int i = ; i <= NumberOfVertices() - ; i++) {
fl << Head[i].GetVerName() << "\t\t\t" << Head[i].GetDescribe() << "\t\t\t\t\t\t" << Head[i].GetMark() << "\t" << Head[i].GetX() - LEFTBORDER << "\t" << Head[i].GetY() - TOPBORDER << endl;
} //用制表符对齐
fl << endl;
int numofedges =NumberOfEdges() * ;
fl << numofedges << endl;
int num = ;
for(int j = ; j <= NumberOfVertices() - ; j++) {
Edge *p = Head[j].Getadj();
while(p != NULL) {
if(num == ) {
fl << endl;
num = ;
}
fl << GetHead()[j].GetMark() << "\t" << GetHead()[p->GetVerAdj()].GetMark() << endl;
p = p->Getlink();
num++;
}
}
fl.close();
return ;
}
bool GraphEmpty()const
{
return graphsize == ;
}
int NumberOfVertices ()const
{
return graphsize;
}
int NumberOfEdges ()const
{
int n = ;
for(int i = ; i <= graphsize - ; i++)
{
Edge *p = Head[i].Getadj();
while(p != NULL)
{
n++;
p = p->Getlink();
}
}
return n / ; //返回边的数目 不计重复边
}
int GetWeight(const int &v1, const int &v2)
{
if(v1 > graphsize - || v2 > graphsize - || v1 < || v2 < )
{
//cout << "查找元素超界！" << endl;
return -;
}
if(v1 == v2) ///////
{
return ;
}
Edge *p = Head[v1].Getadj();
while(p != NULL && p->GetVerAdj() != v2)
{
p = p->Getlink();
}
if(p != NULL)
{
return p->Getcost();
}
else
return MaxCost + ; //两点之间没有边则返回 MaxCost + 1
}
void InsertVertex(string name,string describe,int mark,int x,int y)
{
Vertex *head = new Vertex[graphsize + ]; //创建一个新的顶点表 大小为现有大小再加1
for(int i = ; i <= graphsize - ; i++) //复制现有顶点表的内容到新顶点表
{
head[i] = Head[i];
}
head[graphsize].GetVerName() = name; //把新添加的顶点加在新顶点表最后一个位置
head[graphsize].GetDescribe() = describe;
head[graphsize].GetMark() = mark;
head[graphsize].GetX() = x;
head[graphsize].GetY() = y;
head[graphsize].Getadj() = NULL;
delete [] Head; //删除原顶点表
Head = head; //把Head指针指向新顶点表
graphsize++; //更新顶点数目
}
int InsertEdge(int v1,int v2, int weight)
{
if(v1 > graphsize - || v2 > graphsize - || v1 < || v2 < )
{
//cerr << "插入元素超界！无法完成操作！" << endl;
return -; //插入元素超界返回-1
}
if(weight > MaxCost)
{
//cerr << "插入权值超出最大权值！无法完成操作！" << endl;
return -; //返回-2表示权值过大
} if(v1 == v2)
{
//cerr << "操作不合法" << endl;
return -;
}
int i=InsertEdge_Do(v1, v2, weight);
if(i==-){ //边已存在
return i;
}
InsertEdge_Do(v2, v1, weight);
return i;
}
int DeleteVertex(const int &v)
{
if(v > graphsize - || v < )
{
//cerr << "删除元素超界！" << endl;
return -; //超界返回-1
}
for(int i = ; i <= graphsize - ; i++)
{
DeleteEdge(i, v); //删除指向该顶点的所有边
}
for(int j = v; j <= graphsize - ; j++)
{
Head[j] = Head[j + ]; //把该顶点后边的元素向前挪一个位置
}
graphsize--; //更新graphsize
for(int k = ; k <= graphsize - ; k++)
{
Edge *p = Head[k].Getadj();
while(p != NULL)
{
if(p->GetVerAdj() > v)
{
p->GetVerAdj()--; //所有边之中指向所删除顶点之后位置的 都要减1
}
p = p->Getlink();
}
}
return ;
}
int ModifyVertex(int v,string& name,string& describe,int& marki,int& x,int& y){
if(v < || v > NumberOfVertices() - ) {
return -;
}
Head[v].GetVerName() = name;
Head[v].GetDescribe() = describe;
Head[v].GetMark() = marki;
Head[v].GetX() = x;
Head[v].GetX() += LEFTBORDER;
Head[v].GetY() = y;
Head[v].GetY() += TOPBORDER;
return ;
}
int DeleteEdge(int v2, int v1)
{
if(v1 > graphsize - || v2 > graphsize - || v1 < || v2 < )
{
//cerr << "删除元素超界！" << endl;
return -;
}
if(v1 == v2)
{
return -;
}
int i=DeleteEdge_Do(v1,v2);
if(i==-){return i;}
DeleteEdge_Do(v2,v1);
return i;
}
int DShortestPath(const int v,int*& path)
{
int n = graphsize;
int *s = new int[n];
int *dist = new int[n];
int i = , temp = ;
for (i = ; i < n; i++)
{
s[i] = ;
dist[i] = MaxCost*graphsize*(graphsize-)/;
path[i] = -;
}
int u = v;
Edge *p = NULL;
dist[u] = ;
s[u] = ;
path[u] = u;
for (i = ; i < n; i++)
{
s[u] = ;
p = Head[u].Getadj();
while (p != NULL)
{
temp = p->GetVerAdj();
if (dist[u] + p->Getcost ()< dist[temp])
{
dist[temp] = dist[u] + p->Getcost();
path[temp] = u;
}
p = p->Getlink();
}
temp =MaxCost*graphsize*(graphsize-)/;;
for (int j = ; j < n; j++)
{
if (s[j] == && dist[j] < temp)
{
temp = dist[j];
u = j;//未访问中最小
}
}
}
delete[]s;
delete[]dist;
return ;
}
};
#endif
//Stack.h
1 #ifndef _MYStack_h_
#define _MYStack_h_
template<class TL>
class LStack;
//结点定义
template<class TL>
class LStackNode
{
private:
TL data;
LStackNode<TL>* next;
public:
friend class LStack<TL>;
LStackNode()
{
next=NULL;
}
LStackNode(TL item,LStackNode<TL>* nextnode=NULL)
{
data=item;
next=nextnode;
}
LStackNode(LStackNode<TL>& node)
{
data=node.data; // 为什么必须是引用&才行
next=node.next;
}
};
//栈定义
template<class TL>
class LStack
{
private:
LStackNode<TL> * top;
public:
LStack()
{
top=NULL;
}
bool Push(const TL& item)
{
LStackNode<TL>* p=top;
top=new LStackNode<TL>;
top->data=item;
top->next=p;
return true;
}
bool Pop( TL& item)
{
if(top==NULL)
{
return false;
}
else
{
item=top->data;
LStackNode<TL> * p=top;
top=top->next;
delete p;
}
return true;
}
bool Peek( TL& item)
{
if(top==NULL)
{
return false;
}
else
{
item=top->data;
}
}
~LStack()
{
LStackNode<TL>* p=top;
while(top!=NULL)
{
top=top->next;
delete p;
p=top;
}
top=p=NULL;
}
bool IsEmpty()
{
return top==NULL;
}
};
#endif
//functions.h
1 #ifndef _Functions_h_
#define _Functions_h_
#include<iostream>
#include<string>
#include<math.h>
#include <sstream>
using namespace std;
string int_to_str(int n){
std::stringstream ss;
std::string str;
ss<<n;
ss>>str;
return str;
}
int str_to_num1(const char*& str)
{
if(!(str[]=='-'||(str[]>=''&&str[]<=''))){
return INT_MIN;
}
int n=;
while(str[n]!='\0'){
n++;
}
int number=;
if(str[]!='-'){
for(int i=;i<n;i++){
if(!(str[i]>=''&&str[i]<='')){
return INT_MIN;
}
number+=(str[i]-'')*pow(,n-i-);
}
}
if(str[]=='-'){
for(int i=;i<n;i++){
if(!(str[i]>=''&&str[i]<='')){
return INT_MIN;
}
number+=(str[i]-'')*pow(,n-i-);
}
number*=-;
}
return number;
}
int str_to_num(const string& str)
{
const char* data=str.c_str();
int number=str_to_num1(data);
return number;
}
#endif
资源文件：
map.txt内容
东门 学校正门
图书馆 一楼可自习，可通宵
计算机楼 计算机学院和软件学院公用实验教学楼
第三教学楼 一教二教不在本校区╮(╯_╰)╭
逸夫楼 公共教学楼
北门 最繁忙的学校大门
办公楼 行政人员办公楼
四食堂 最小食堂，却居于最重要位置
体育馆 大型活动举办地
体育运动场 主体育场
南苑 学生公寓
小北门 小校门
经信教学楼 经济信息学院教学楼
北苑 学生公寓
新食堂 食堂，有两层
李四光楼 地质教学楼
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
音乐厅 音乐厅
逸夫图书馆 校史陈列馆
麦克德尔米德实验室 实验室
* *
* *
唐敖庆楼 唐敖庆楼
* *
* *
* *
* *
外语楼 外语学院教学楼
篮球场 新食堂篮球场
匡亚明楼 匡亚明楼
* *
南门 南门
* *
莘子园食堂 莘子园食堂
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
经信公寓 经信公寓
* *
* *
西门 西门
物理楼 物理楼
生科楼 生命科学楼
* *
* *
东荣
数学楼 数学学院数学楼
* *
* *
* *
* *
* *
* *
* *
* *
map.jpg
大二上学期数据结构课程设计写此程序。
2016.4.12更新博客。