數(shù)據(jù)結(jié)構(gòu)課程設(shè)計學(xué)校超市選址問題

1、精品文檔學(xué)校超市選址問題學(xué)生姓名專業(yè)班級學(xué)號題目學(xué)校超市選址問題課題性質(zhì)工程設(shè)計課題來源自選課題指導(dǎo)教師同組姓名無對于某一學(xué)校超市，其他各單位到其的距離不同，主要內(nèi)容任務(wù)要求參考文獻(xiàn)審查意見同時各單位人員去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。1. 實現(xiàn)公司到超市距離，頻率最優(yōu)。2. 確定超市位置，要求實現(xiàn)總體最優(yōu)。 C程序設(shè)計第三版譚浩強 著 清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu) （ C 語言版）嚴(yán)蔚敏著清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)及應(yīng)用沈華等編著機械工業(yè)出版社指導(dǎo)教師簽字：教研室主任簽字：。1 歡迎下載精品文檔一、需求分析1 ）核心問題 : 求最短路徑 ( 選址的要求就是超市到各單位權(quán)值之和最少

2、)2）數(shù)據(jù)模型（邏輯結(jié)構(gòu)） : 帶權(quán)有向圖 ( 權(quán)值計算 : 距離 * 頻度 )3）存儲結(jié)構(gòu) : typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph;核心算法 : Floyd算法 ( 弗洛伊德算法 - 每一對頂點之間的最短路徑)輸入數(shù)據(jù) :各單位名稱，距離，頻度，單位個數(shù)輸出數(shù)據(jù) :所選單位名稱總體思路 :如果超市是要選在某個單位，那么先用floyd算法得出各頂點間的最短距離 / 最小權(quán)值。假設(shè)頂點個數(shù)有n 個，那么就得到n*n 的

3、一張表格， arcs(i,j)表示 i 單位到 j單位的最短距離 / 最小權(quán)值 ,這張表格中和最小的那一行( 假設(shè)為第 t 行) ，那么超市選在 t 單位處就是最優(yōu)解。2 運行環(huán)境Visual Stdio C+6.0Windows Vista/2003/XP3 概要設(shè)計Floyd 算法利用動態(tài)規(guī)劃思想， 通過把問題分解為子問題來解決任意兩點見的最短路徑問題。設(shè) G=(V, E, w)是一個帶權(quán)有向圖，其邊 V=v1, v2, , vn 。對于 kn，考慮其結(jié)點 V 的一個子集。對于 V 中任何兩個結(jié)點 vi 、vj ，考慮從vi 到 vj 的中間結(jié)點都在 vk 中的所有路徑，設(shè)該路徑是其中最短

4、的，并設(shè)它的路徑長度為最短路徑長度。如果結(jié)點 vk 不在從 vi 到 vj 的最短路徑上，則；反之則可以把分為兩段，其中一段從 vi 到 vk，另一段從 vk 到 vj ，這樣便得到表。1 歡迎下載精品文檔達(dá)式。上述討論可以歸納為如下遞歸式：原問題轉(zhuǎn)化為對每個i 和 j 求，或者說求矩陣流程圖開始Main （）輸入基本信息GreatMgraph（Gh ）建立鄰接矩陣的存儲結(jié)構(gòu)Floyd 算法NYAij=INF,i!=ji 到 j 不存在路Floyed（Gh ）輸出 i->j 的路徑和路徑長度輸出超市的最佳地址：i結(jié)束4 詳細(xì)設(shè)計第一步，讓所有路徑加上中間頂點1，取 Aij與 Ai1+A1

5、j中較小的值作 Aij的新值，完成后得到 A(1), 如此進(jìn)行下去， 當(dāng)?shù)?k 步完成后， A。2 歡迎下載精品文檔（ k） ij表示從 i 到就且路徑上的中間頂點的路徑的序號小于或等于k 的最短路徑長度。當(dāng)?shù)趎-1 步完成后，得到 A（ n-1 ），A（n-1 ）即所求結(jié)果。 A（n-1 ）ij表示從 i 到 j且路徑上的中點頂點的序號小于或等于n-1 的最短路徑長度，即 A(n-1)ij表示從 i 到 j 的最短路徑長度。4.1 頭文件和變量設(shè)定#include <string.h>#include <stdio.h>#include <stdlib.h>

6、;#include <time.h>#include "malloc.h"#include <iostream.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXVEX=100;typedef char Vextype;4.2 結(jié)構(gòu)體的定義typedef structVextype vexsMAXVEXMAXVEX;/單位名稱（頂點信息）；int adjMAXVEXMAXVEX;/ 單位之

7、間的相通情況（是否有邊）；int disMAXVEXMAXVEX;/ 單位間距離（邊的長度） ；int fMAXVEX;/ 各單位去超市的頻率；。3 歡迎下載精品文檔int n;/ 頂點數(shù)和邊數(shù)；int e;Mgraph;4.3 變量的輸入void CreatMgraph(Mgraph *G)int i,j,k;printf("請輸入單位個數(shù) :n");scanf("%d",&(G->n);printf("請輸入單位間的路徑數(shù) :n");scanf("%d",&(G->e);printf

8、("請輸入單位名稱 :n");for(i=0;i<G->n;i+)printf("請輸入第 %d個單位名稱 :n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+) / 結(jié)構(gòu)體的初始化； for(j=0;j<G->n;j+)G->adjij=0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)printf("請輸入相通的兩單位( 輸入格式 :i,j):n");scanf(&

9、quot;%d,%d",&i,&j);/在距離上體現(xiàn)為無向；。4 歡迎下載精品文檔printf("請輸入相同兩個單位間的距離( 格式： dis) ： n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G->n;k+)printf(" 請輸入第 %d個單位去超市的相對頻率 :n",k); scanf("%d",&(G->fk);for(i=0;i<G->n;i+)/以距離和頻率之積作為權(quán)值；for(j=0;j<G->n;j+)G->disij*=G->fi;/最終權(quán)值非完全無向；if(G->adjij=0&&i!=j)G->disij=INF;4.4 帶權(quán)有向圖求最短路徑floyd