vc_节点矩阵最短路径guildmap.doc

包括编译程序词法分析器、操作系统进程状态切换演示、VC_哈夫曼树halftree、节点矩阵最短路径guildmap、串基本操作的演示

struct way
{
	int path[15];
	int count;
};
extern char* names[];
extern int position[][2], roads[][2], matrix[][15],nodnum, roadnum;
extern struct way shortestway, mostsight, temp;
extern int nodtype[];
extern int nod1, nod2;
extern int visited[];
int floyd();
int linkm();
int path(int i, int j);
void waycpy(way* w1, way* w2);
int enumeration(int nod, int n);


void waycpy(way* w1, way* w2)
{
	int i;
	for(i=0; i<=nodnum-1; i++)
	{
		w2->path[i]=w1->path[i];
	}
	w2->count = w1->count;
}

int enumeration(int nod, int n)
{
	int i;
	for(i=0; i<=roadnum-1; i++)
	{
		if((roads[i][0]==nod && visited[roads[i][1]]!=1))
		{
			if(roads[i][1]==nod2)
			{
				if(n>maxsight)
				{
					maxsight = n;
					waycpy(&temp, &mostsight);
					return 1;
				}
			}
			else
			{
				visited[roads[i][1]]=1;
				temp.path[temp.count]=roads[i][1];
				temp.count++;
				if(nodtype[nod]==1)
					enumeration(roads[i][1], n+1);
				else
					enumeration(roads[i][1], n);
				visited[roads[i][1]]=0;
				temp.path[temp.count]=-1;
				temp.count--;
			}
		}
		if((roads[i][1]==nod && visited[roads[i][0]]!=1))
		{
			if(roads[i][0]==nod2)
			{
				if(n>maxsight)
				{
					maxsight = n;
					waycpy(&temp, &mostsight);
					return 1;
				}
			}
			else
			{
				visited[roads[i][0]]=1;
				temp.path[temp.count]=roads[i][0];
				temp.count++;
				if(nodtype[nod]==1)
					enumeration(roads[i][0], n+1);
				else
					enumeration(roads[i][0], n);
				visited[roads[i][0]]=0;
				temp.path[temp.count]=-1;
				temp.count--;
			}
		}
	}
	return 1;
}
int floyd()
{
	int i,j,k;
	for(i=0; i<=nodnum-1; i++)
		for(j=0; j<=nodnum-1; j++)
			p[i][j]=-1;
	for(k=0; k<=nodnum-1; k++)
		for(i=0; i<=nodnum-1; i++)
			for(j=0; j<=nodnum-1; j++)
			{
				if(matrix[i][k]>=0 && matrix[k][j]>=0 &&
					(matrix[i][j]<0 || matrix[i][k]+matrix[k][j]<matrix[i][j]))
				{
					matrix[i][j] = matrix[i][k]+matrix[k][j];
					p[i][j] = k;
				}
			}	
	return 1;
}

int path(int i, int j)
{
	int k;
	k = p[i][j];
	if(k>=0)
	{
		path(i,k);
		shortestway.path[shortestway.count]=k;
		shortestway.count++;
		path(k,j);
	}
	return 1;
}

int nodtype[]={1,0,1,1,1,1,1,0,1,1,0,1,0,1,1};
int nod1, nod2;

char* names[] = {"A","B","C","D","E",
				"F","G","H","I","J",
				"K","L","M","N","O"};
int position[][2] = {
						{0,0},{0,1},{0,5},{0,9},{0,14},
						{4,2},{4,10},{4,14},{8,2},{8,10},
						{12,2},{12,6},{12,10},{12,14},{14,2}
};

int roads[][2] = {
					{0,1},{1,2},{2,3},{3,4},{1,5},{3,6},
					{6,7},{5,8},{6,9},{8,9},{8,10},{9,12},
					{7,13},{10,11},{11,12},{12,13},{10,14}
};

int matrix[15][15],p[15][15];

way shortestway;
way mostsight;
way temp;
int maxsight;


int nodnum = 15;
int roadnum = 17;
int visited[15];

int linkm()
{
	int i,j;
	int power;
	for(i=0; i<=14; i++)
	{
		for(j=0; j<=14; j++)
		{
			if(i==j)
				matrix[i][j] = 0;
			else
				matrix[i][j] = -1;
		}
	}
	for(i=0; i<= roadnum-1; i++)
	{
		power = abs(position[roads[i][0]][0]-position[roads[i][1]][0])+
				abs(position[roads[i][0]][1]-position[roads[i][1]][1]);
		matrix[roads[i][0]][roads[i][1]] = power;
		matrix[roads[i][1]][roads[i][0]] = power;
	}
	return 1;
}

HINSTANCE hInst;								
TCHAR szTitle[MAX_LOADSTRING];								
TCHAR szWindowClass[MAX_LOADSTRING];								


ATOM				MyRegisterClass(HINSTANCE hInstance);
BOOL				InitInstance(HINSTANCE, int);
LRESULT CALLBACK	WndProc(HWND, UINT, WPARAM, LPARAM);
LRESULT CALLBACK	About(HWND, UINT, WPARAM, LPARAM);
LRESULT CALLBACK	Input(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam);
void DrawMap(HDC hdc, int t, int offset);
void DrawMap(HDC hdc, int t, int offset)
{
	HPEN p1,p2,p3;
	int i;
	p1 = CreatePen(PS_SOLID, 1, 0x0);
	p2 = CreatePen(PS_SOLID, 10, 0x0);
	p3 = CreatePen(PS_SOLID, 4, 0x000000ff);
	char c[33];

	for(i=0; i<=roadnum-1; i++)
	{
		SelectObject(hdc, p1);
		MoveToEx(hdc, position[roads[i][0]][0]*t+offset,
					position[roads[i][0]][1]*t+offset, NULL);
		LineTo(hdc, position[roads[i][1]][0]*t+offset,
					position[roads[i][1]][1]*t+offset);
	}

	for(i=0; i<=nodnum-2 && shortestway.path[i+1]>=0; i++)
	{
		SelectObject(hdc, p2);
		MoveToEx(hdc, position[shortestway.path[i]][0]*t+offset,
					position[shortestway.path[i]][1]*t+offset, NULL);
		LineTo(hdc, position[shortestway.path[i+1]][0]*t+offset,
					position[shortestway.path[i+1]][1]*t+offset);
	}

	for(i=0; i<=nodnum-2 && mostsight.path[i+1]>=0; i++)
	{
		SelectObject(hdc, p3);
		MoveToEx(hdc, position[mostsight.path[i]][0]*t+offset,
					position[mostsight.path[i]][1]*t+offset, NULL);
		LineTo(hdc, position[mostsight.path[i+1]][0]*t+offset,
					position[mostsight.path[i+1]][1]*t+offset);
	}

	for(i=0; i<=nodnum-1; i++)
	{
		if(nodtype[i]==1)
		{
			SelectObject(hdc,p1);
			Ellipse(hdc,position[i][0]*t+offset-10,
						position[i][1]*t+offset-10,
						position[i][0]*t+offset+10,
						position[i][1]*t+offset+10);
			_itoa(i,c,10);
			TextOut(hdc,position[i][0]*t+offset-4,
						position[i][1]*t+offset-7,
						c,1);
		}
	}
}

int APIENTRY WinMain(HINSTANCE hInstance,
                     HINSTANCE hPrevInstance,
                     LPSTR     lpCmdLine,
                     int       nCmdShow)
{
 	// TODO: Place code here.
	MSG msg;
	HACCEL hAccelTable;
	int i;

	// Initialize global strings
	LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
	LoadString(hInstance, IDC_GUIDMAP, szWindowClass, MAX_LOADSTRING);
	for(i=0; i<=nodnum-1; i++)
	{
		shortestway.path[i] = -1;
	}
	MyRegisterClass(hInstance);

	// Perform application initialization:
	if (!InitInstance (hInstance, nCmdShow)) 
	{
		return FALSE;
	}

	hAccelTable = LoadAccelerators(hInstance, (LPCTSTR)IDC_GUIDMAP);

	// Main message loop:
	while (GetMessage(&msg, NULL, 0, 0)) 
	{
		if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg)) 
		{
			TranslateMessage(&msg);
			DispatchMessage(&msg);
		}
	}

	return msg.wParam;
}


ATOM MyRegisterClass(HINSTANCE hInstance)
{
	WNDCLASSEX wcex;

	wcex.cbSize = sizeof(WNDCLASSEX); 

	wcex.style			= CS_HREDRAW | CS_VREDRAW;
	wcex.lpfnWndProc	= (WNDPROC)WndProc;
	wcex.cbClsExtra		= 0;
	wcex.cbWndExtra		= 0;
	wcex.hInstance		= hInstance;
	wcex.hIcon			= LoadIcon(hInstance, (LPCTSTR)IDI_GUIDMAP);
	wcex.hCursor		= LoadCursor(NULL, IDC_ARROW);
	wcex.hbrBackground	= (HBRUSH)(COLOR_WINDOW+1);
	wcex.lpszMenuName	= (LPCSTR)IDC_GUIDMAP;
	wcex.lpszClassName	= szWindowClass;
	wcex.hIconSm		= LoadIcon(wcex.hInstance, (LPCTSTR)IDI_SMALL);

	return RegisterClassEx(&wcex);
}

BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   HWND hWnd;

   hInst = hInstance; // Store instance handle in our global variable

   hWnd = CreateWindow(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;
	TCHAR szHello[MAX_LOADSTRING];
	int i;
	LoadString(hInst, IDS_HELLO, szHello, MAX_LOADSTRING);

	switch (message) 
	{
		case WM_COMMAND:
			wmId    = LOWORD(wParam); 
			wmEvent = HIWORD(wParam); 
			// Parse the menu selections:
			switch (wmId)
			{
				case IDM_ABOUT:
				   DialogBox(hInst, (LPCTSTR)IDD_ABOUTBOX, hWnd, (DLGPROC)About);
				   break;
				case IDM_INPUT:
					if(DialogBox(hInst, (LPCTSTR)IDD_INPUTDLG, hWnd, (DLGPROC)Input))
					{
						linkm();
						floyd();
						for(i=0; i<=nodnum-1; i++)
						{
							shortestway.path[i] = -1;
						}
						shortestway.count = 0;
						shortestway.path[0] = nod1;
						shortestway.count++;
						path(nod1, nod2);
						shortestway.path[shortestway.count]=nod2;
						shortestway.count++;
						for(i=0; i<=nodnum-1; i++)
						{
							mostsight.path[i]=-1;
							temp.path[i]=-1;
						}
						mostsight.count = 0;
						temp.count = 0;
						temp.path[temp.count]=nod1;
						temp.count++;
						visited[nod1]=1;
						enumeration(nod1,nodtype[nod1]);
						mostsight.path[mostsight.count]=nod2;
						mostsight.count++;
						InvalidateRect(hWnd, NULL, TRUE);
						UpdateWindow(hWnd);
					}
					break;
				case IDM_EXIT:
				   DestroyWindow(hWnd);
				   break;
				default:
				   return DefWindowProc(hWnd, message, wParam, lParam);
			}
			break;
		case WM_PAINT:
			hdc = BeginPaint(hWnd, &ps);
			// TODO: Add any drawing code here...
			DrawMap(hdc,30,20);
			EndPaint(hWnd, &ps);
			break;
		case WM_DESTROY:
			PostQuitMessage(0);
			break;
		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
   }
   return 0;
}

LRESULT CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	switch (message)
	{
		case WM_INITDIALOG:
				return TRUE;

		case WM_COMMAND:
			if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL) 
			{
				EndDialog(hDlg, LOWORD(wParam));
				return TRUE;
			}
			break;
	}
    return FALSE;
}


LRESULT CALLBACK Input(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
	char s[30], e[30];
	switch (message)
	{
		case WM_INITDIALOG:
				return TRUE;

		case WM_COMMAND:
			if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL) 
			{
				GetDlgItemText(hDlg, IDC_START, s, 30);
				GetDlgItemText(hDlg, IDC_END, e, 30);
				nod1 = atoi(s);
				nod2 = atoi(e);
				EndDialog(hDlg, LOWORD(wParam));
				return TRUE;
			}
			break;
	}
    return FALSE;
}