c++最短路徑往回走之問題 |
尚未結案
|
liyanzi
一般會員 發表:51 回覆:45 積分:19 註冊:2005-01-24 發送簡訊給我 |
請問各位大大~~我最短路徑本來的資料 是一筆接一筆的~~現在想改可以往回走~~ 本來的宣告是
//路徑名稱 struct DList { String roadname ;//用來存道路名稱 int num ; int number ;//目前沒有用到 int road_numeral ;//存一條距離用的 int an_road_numeral ;//存另一條距離用的 DList *road ;//連接下一條道路用的 DList *an_road ;//連接另下一條道路用的 }; void __fastcall TForm1::FormCreate(TObject *Sender)//原本路徑的指標 { for ( int i = 0; i < 6; i ) delete_road[ i ] = new Save_roadname ; head = new DList ;//先將其設為NULL find_head = new DList ; for ( int i = 0; i < 10; i ) temp_road[ i ] = new DList ; all_num = 0 ; DList *pointer, *temp[6] ; for ( int i = 0; i < 6; i ) temp[ i ] = new DList ; head -> number = 1 ; head -> an_road_numeral = 0 ; head -> roadname = "成功路" ; ComboBox1 -> Items -> Add( head -> roadname ) ; head -> road_numeral = 35 ; temp[ 0 ] -> road_numeral = 45 ; temp[ 0 ] -> an_road_numeral = 30 ; temp[ 0 ] -> roadname = "自由路" ; ComboBox1 -> Items -> Add( temp[ 0 ] -> roadname ) ; temp[ 0 ] -> number = 2 ; head -> road = temp[ 0 ] ; temp[ 1 ] -> number = 3 ; temp[ 1 ] -> road_numeral = 25 ; temp[ 1 ] -> an_road_numeral = 0 ; temp[ 1 ] -> roadname = "博愛路" ; ComboBox1 -> Items -> Add( temp[ 1 ] -> roadname ) ; temp[ 0 ] -> road = temp[ 1 ] ; temp[ 2 ] -> road_numeral = 45 ; temp[ 2 ] -> number = 4 ; temp[ 2 ] -> an_road_numeral = 130 ; temp[ 2 ] -> roadname = "中正路" ; ComboBox1 -> Items -> Add( temp[ 2 ] -> roadname ) ; temp[ 0 ] -> an_road = temp[ 2 ] ; temp[ 0 ] = temp[ 2 ] ; temp[ 3 ] -> an_road_numeral = 0 ; temp[ 3 ] -> number = 5 ; temp[ 3 ] -> road_numeral = 100 ; temp[ 3 ] -> roadname = "仁愛路" ; ComboBox1 -> Items -> Add( temp[ 3 ] -> roadname ) ; temp[ 1 ] -> road = temp[ 3 ] ; //第三點接到第五點 temp[ 1 ] = temp[ 3 ] ; temp[ 0 ] -> road = temp[ 3 ] ;//第四點接到第五點 temp[ 4 ] -> number = 6 ; temp[ 4 ] -> road_numeral = 0 ; temp[ 4 ] -> an_road_numeral = 0 ; temp[ 4 ] -> roadname = "中山路" ; ComboBox1 -> Items -> Add( temp[ 4 ] -> roadname ) ; temp[ 0 ] -> an_road = temp[ 4 ] ; temp[ 1 ] -> road = temp[ 4 ] ; }現在改成~~往回走~~就多設一個值 int tn_road_numeral;//用來存第三條 DList *tn_road;//用來連接第三條道路用的 而資料改成如下 //----------------------------------------------------------------- void __fastcall TForm1::FormCreate(TObject *Sender) { for ( int i = 0; i < 6; i ) delete_road[ i ] = new Save_roadname ; head = new DList ;//先將其設為NULL find_head = new DList ; for ( int i = 0; i < 10; i ) temp_road[ i ] = new DList ; all_num = 0 ; DList *pointer, *temp[6] ; for ( int i = 0; i < 6; i ) temp[ i ] = new DList ; head -> number = 1 ; head -> an_road_numeral = 0 ; head -> roadname = "成功路" ; ComboBox1 -> Items -> Add( head -> roadname ) ; head -> road_numeral = 35 ; temp[ 0 ] -> road = head; temp[ 0 ] -> road_numeral = 45 ; temp[ 0 ] -> an_road_numeral = 30 ; temp[ 0 ] -> tn_road_numeral=35; temp[ 0 ] -> roadname = "自由路" ; ComboBox1 -> Items -> Add( temp[ 0 ] -> roadname ) ; temp[ 0 ] -> number = 2 ; head -> road = temp[ 0 ] ; temp[ 1 ] -> an_road = temp[ 0 ] ; temp[ 2 ] -> tn_road = temp[ 0 ] ; temp[ 1 ] -> number = 3 ; temp[ 1 ] -> road_numeral = 45 ; temp[ 1 ] -> an_road_numeral = 25 ; temp[ 1 ] -> roadname = "博愛路" ; ComboBox1 -> Items -> Add( temp[ 1 ] -> roadname ) ; temp[ 0 ] -> road = temp[ 1 ] ; temp[ 3 ] -> an_road = temp[ 1 ]; temp[ 2 ] -> road_numeral = 45 ; temp[ 2 ] -> number = 4 ; temp[ 2 ] -> an_road_numeral = 130 ; temp[ 2 ] -> tn_road_numeral = 30 ; temp[ 2 ] -> roadname = "中正路" ; ComboBox1 -> Items -> Add( temp[ 2 ] -> roadname ) ; temp[ 0 ] -> an_road = temp[ 2 ] ; temp[ 0 ] = temp[ 2 ] ; temp[ 2 ] -> tn_road = temp[ 2 ] ; temp[ 2 ] -> an_road = temp[ 2 ]; temp[ 3 ] -> an_road_numeral = 45 ; temp[ 3 ] -> tn_road_numeral = 25 ; temp[ 3 ] -> number = 5 ; temp[ 3 ] -> road_numeral = 100 ; temp[ 3 ] -> roadname = "仁愛路" ; ComboBox1 -> Items -> Add( temp[ 3 ] -> roadname ) ; temp[ 1 ] -> tn_road = temp[ 3 ] ; //第三點接到第五點 temp[ 4 ] -> road = temp[ 3 ] ; temp[ 1 ] = temp[ 3 ] ; temp[ 0 ] -> an_road = temp[ 3 ] ;//第四點接到第五點 temp[ 4 ] -> number = 6 ; temp[ 4 ] -> road_numeral = 50 ; temp[ 4 ] -> an_road_numeral = 100 ; temp[ 4 ] -> tn_road_numeral = 130 ; temp[ 4 ] -> roadname = "中山路" ; ComboBox1 -> Items -> Add( temp[ 4 ] -> roadname ) ; temp[ 0 ] -> an_road = temp[ 4 ] ; temp[ 1 ] -> road = temp[ 4 ] ; temp[ 5 ] -> tn_road = temp[ 4 ] ; temp[ 5 ] -> number = 7; temp[ 5 ] -> road_numeral = 50 ; temp[ 5 ] -> an_road_numeral = 0 ; temp[ 5 ] -> roadname = "00路" ; ComboBox1 -> Items -> Add( temp[ 5 ] -> roadname ) ; temp[ 4 ] -> road = temp[ 5 ] ; }程式雖然可以complier, 但執行時會出現此行錯誤~~* ptr = ptr -> road* 請各位大大~~幫幫忙~~~ |
RedSnow
版主 發表:79 回覆:1322 積分:845 註冊:2003-12-15 發送簡訊給我 |
liyanzi 妳好: 說實在的,妳的路徑設定資料蠻亂的,我把它整理了一下之後,發現有些資料的設定似乎不正確,例如下列資料:
temp[ 0 ] = temp[ 2 ] ;
temp[ 0 ] -> road = head;
因此我重新整理了一下那些設定資料如下:
head -> number = 1 ; head -> roadname = "成功路" ; ComboBox1 -> Items -> Add( head -> roadname ) ; head -> road = temp[ 0 ] ; // 成功 -> 自由 head -> road_numeral = 35 ; // head -> an_road = NULL ; // 無 head -> an_road_numeral = 0 ; // head -> tn_road = NULL ; // 無 head -> tn_road_numeral = 0; temp[ 0 ] -> number = 2 ; temp[ 0 ] -> roadname = "自由路" ; ComboBox1 -> Items -> Add( temp[ 0 ] -> roadname ) ; temp[ 0 ] -> road = temp[ 1 ] ; // 自由 -> 博愛 temp[ 0 ] -> road_numeral = 45 ; temp[ 0 ] -> an_road = temp[ 2 ] ; // 自由 -> 中正 temp[ 0 ] -> an_road_numeral = 30 ; temp[ 0 ] -> tn_road = head ; // 成功 <- 自由 temp[ 0 ] -> tn_road_numeral = 35; temp[ 1 ] -> number = 3 ; temp[ 1 ] -> roadname = "博愛路" ; ComboBox1 -> Items -> Add( temp[ 1 ] -> roadname ) ; temp[ 1 ] -> road = temp[ 3 ] ; // 博愛 -> 仁愛 temp[ 1 ] -> road_numeral = 25 ; // temp[ 1 ] -> an_road = NULL ; // 無 temp[ 1 ] -> an_road_numeral = 0 ; temp[ 1 ] -> tn_road = temp[ 0 ]; // 自由 <- 博愛 temp[ 1 ] -> tn_road_numeral = 45 ; temp[ 2 ] -> number = 4 ; temp[ 2 ] -> roadname = "中正路" ; ComboBox1 -> Items -> Add( temp[ 2 ] -> roadname ) ; temp[ 2 ] -> road = temp[ 3 ]; // 中正 -> 仁愛 temp[ 2 ] -> road_numeral = 45 ; temp[ 2 ] -> an_road = temp[ 4 ]; // 中正 -> 中山 temp[ 2 ] -> an_road_numeral = 130 ; temp[ 2 ] -> tn_road = temp[ 1 ] ; // 博愛 <- 中正 temp[ 2 ] -> tn_road_numeral = 30 ; temp[ 3 ] -> number = 5 ; temp[ 3 ] -> roadname = "仁愛路" ; ComboBox1 -> Items -> Add( temp[ 3 ] -> roadname ) ; temp[ 3 ] -> road = temp[ 4 ] ; // 仁愛 -> 中山 temp[ 3 ] -> road_numeral = 100 ; // temp[ 3 ] -> an_road = NULL ; // 無 temp[ 3 ] -> an_road_numeral = 0 ; temp[ 3 ] -> tn_road = temp[ 2 ] ; // 中正 <- 仁愛 temp[ 3 ] -> tn_road_numeral = 25 ; temp[ 4 ] -> number = 6 ; temp[ 4 ] -> roadname = "中山路" ; ComboBox1 -> Items -> Add( temp[ 4 ] -> roadname ) ; temp[ 4 ] -> road = temp[ 5 ] ; // 中山 -> 00 temp[ 4 ] -> road_numeral = 50 ; // temp[ 4 ] -> an_road = NULL ; // 無 temp[ 4 ] -> an_road_numeral = 0 ; temp[ 4 ] -> tn_road = temp[ 3 ] ; // 仁愛 <- 中山 temp[ 4 ] -> tn_road_numeral = 130 ; temp[ 5 ] -> number = 7; temp[ 5 ] -> roadname = "00路" ; ComboBox1 -> Items -> Add( temp[ 5 ] -> roadname ) ; // temp[ 5 ] -> road = NULL ; // 無 temp[ 5 ] -> road_numeral = 0 ; // temp[ 5 ] -> an_road = NULL ; // 無 temp[ 5 ] -> an_road_numeral = 0 ; temp[ 5 ] -> tn_road = temp[ 4 ] ; // 中山 <- 00 temp[ 5 ] -> tn_road_numeral = 50 ;我用上次的遞迴程式測試上述資料是 OK 的,妳試試看吧。 另外妳要增加結構項目,以便處理 "往回走" 的動作,那麼妳可能在這次增加一組往回走的資料之外,還要考慮再增設一組往回走的第二條路徑與距離資料,因為依據妳原先的資料來看,有的道路是有兩條分岔的,例如仁愛路往回走就有博愛路與中正路。 7 天天敲鍵盤 v 時時按滑鼠 8 |
liyanzi
一般會員 發表:51 回覆:45 積分:19 註冊:2005-01-24 發送簡訊給我 |
請問各位大大: 如果不要再新增節構的話~~就是單純想要在路徑的資料改的話~~
就是~~把路想成兩個方向~~
是不是不可能ㄚ~~還是說會很複雜~~ 比如說原本比如說~~1->2->3->4有四條路, 1 ↗ 2 → 4
?↘ 3 ↗ 反方向是 1 ↙ 2 ← 4
?↖ 3 ↙ 把他們兩個結合在一次的話~~~就是會變成 1有出去兩條路到2.3寫法如下
head->road=temp[0]
head->an_road=temp[1] 而到1的也有2.3 就寫成 temp[0]->raod=head
temp[1]->road=head 想問各位大大是我這種寫法有錯,我觀念錯誤~~ 還是有可能是我資料給錯的關係`~~
|
RedSnow
版主 發表:79 回覆:1322 積分:845 註冊:2003-12-15 發送簡訊給我 |
liyanzi 妳好:
引言:head->road=temp[0] head->an_road=temp[1] 而到1的也有2.3 就寫成 temp[0]->raod=head temp[1]->road=headhead 的 road 指向 temp[0] 而 temp[0] 的 raod 又指向 head,如果程式循著 road 去找下一條路,那不就變成無限循環了嗎?而且 temp[0] 的 raod 指向 head 之後,妳要如何讓 temp[0] 去連接至下一條路呢? 另外請妳回應一下,我貼上來的那份重新整理過的設定資料是否解決了妳開題篇的問題? 7 天天敲鍵盤 v 時時按滑鼠 8 |
liyanzi
一般會員 發表:51 回覆:45 積分:19 註冊:2005-01-24 發送簡訊給我 |
RedSnow這位大大: 非常謝謝你~~你貼的那份重新整理的設定資料~~是解決了我可以complier了!! 1有出去兩條路到2.3寫法如下 head->road=temp[0]
head->an_road=temp[1] 而到1的也有2.3 就寫成 temp[0]->raod=head
temp[1]->road=head ---------------------------------------------------------------------
head 的 road 指向 temp[0] 而 temp[0] 的 raod 又指向 head,如果程式循著 road 去找下一條路,那不就變成無限循環了嗎?而且 temp[0] 的 raod 指向 head 之後,妳要如何讓 temp[0] 去連接至下一條路呢? *我想的意思是~~以下算是往回走的走法 temp[0]->raod=head
temp[1]->road=head 而應該還有往下走的 temp[0]->road=temp[2] //就是2->4
temp[1]->raod=temp[2] //就是3->4 原本~~1->2->3->4有四條路, 1 ↗ 2 → 4
?↘ 3 ↗ 反方向是 1 ↙ 2 ← 4
?↖ 3 ↙ 例如~~在道路2的資料裡 temp[ 0 ] -> road_numeral = 45 ;//道路2的長度
temp[ 0 ] -> roadname = "自由路" ;
ComboBox1 -> Items -> Add( temp[ 0 ] -> roadname ) ;
temp[ 0 ] -> number = 2 ; //變成有1->2?跟?4->2
head -> road = temp[ 0 ] ;//1->2
temp[ 2 ] -> an_road = temp[ 0 ] ;4->2
|
RedSnow
版主 發表:79 回覆:1322 積分:845 註冊:2003-12-15 發送簡訊給我 |
liyanzi 妳好: 妳的意思要將整個程式的路徑連結改個方向或是修改程式為具備雙向處理的功能嗎?如果是的話,那就無需變更資料結構,但是.... 如果妳的意思要將整個程式的路徑連結改個方向,那妳當初給的概念就錯誤了,因為妳的結構資料本來就是單向的,如果妳不是要同時存在兩個方向的處理動作,那就不應該使用 "往回走" 的說法,而且程式中的路徑設定資料也有 head -> road = temp[ 0 ] ; 這樣的設定,那代表者路徑方向仍是由 "成功路" 開始的,以至於誤導了我的方向。其實電腦只知道妳給的是單向的路徑資料,它並不會去管妳是往前走還是往回走?有誰規定由 "成功路 -> 中山路" 叫做 "往前" 走,而 "中山路 -> 成功路" 就必須要叫做 "往回" 走嗎?因此妳這個問題其實並不是問題,這只是路徑設定的方向而已 (原先是由 "成功路" 往 "中山路" 的方向設定路徑,現在則改由 "中山路" 往 "成功路" 的方向設定路徑)。 如果妳是要修改程式為具備雙向處理功能,而不想變更資料結構,想在往回走時重新設定路徑資料,那麼這麼一來妳就必須要在使用者每次變更處理方向時,就重新設定一次路徑資料了,這樣的處理方式似乎會比較欠缺效率,妳得好好再斟酌一下。 7 天天敲鍵盤 v 時時按滑鼠 8
|
liyanzi
一般會員 發表:51 回覆:45 積分:19 註冊:2005-01-24 發送簡訊給我 |
感謝Redsnow大大的回答~~ 那如果我新增了一組~~往回走的結構 sturct Return_roadname
{
String re_roadname;
Return_roadname *next;
};
Return_roadname *return_head , *return_tail; 要怎麼處理呢? 我只是想原本成功路能到中山路 而變成能選中山路到成功路~~ 兩種結果的距離應該會是一樣的吧!應該不可能會走回來就不一樣了吧! 那是不是要改comboBox抓的值ㄚ~~
|
RedSnow
版主 發表:79 回覆:1322 積分:845 註冊:2003-12-15 發送簡訊給我 |
liyanzi 妳好:
引言:那如果我新增了一組~~往回走的結構 sturct Return_roadname { String re_roadname; Return_roadname *next; }; Return_roadname *return_head , *return_tail; 要怎麼處理呢? 我只是想原本成功路能到中山路 而變成能選中山路到成功路~~ 兩種結果的距離應該會是一樣的吧!應該不可能會走回來就不一樣了吧! 那是不是要改comboBox抓的值ㄚ~~那要看妳打算用何種方式來操作,例如增加一個 CheckBox,未被圈選時代表著 "往前走",若被圈選則代表 "往回走",那麼妳就可以在相關的動作中以那個 CheckBox 的 Checked 值來當做判斷,然後進行不同的處理。 無論妳往那個方向去處理?距離資料都是不變的,只是妳必須要在比對新增的那個資料結構,取得連結的上一個路名後,再由原先的那個結構資料中取得該路名與上一個路名之間的距離資料,既然講到這裡了,那我就提一下我的建議,你似乎可以考慮將這個新的結構內容由 String 改成 int,然後存放的不是 "路名" 而是改成 "路名編號",也就是對應到妳原先那個 temp 陣列的索引值,這樣子或許處理起來會簡單一些。 如果妳要用新增結構的方式來處理往回走的動作,妳仍要記得我在本篇討論中的第一篇回應所提: 另外妳要增加結構項目,以便處理 "往回走" 的動作,那麼妳可能在這次增加一組往回走的資料之外,還要考慮再增設一組往回走的第二條路徑與距離資料,因為依據妳原先的資料來看,有的道路是有兩條分岔的,例如仁愛路往回走就有博愛路與中正路。 7 天天敲鍵盤 v 時時按滑鼠 8 |
liyanzi
一般會員 發表:51 回覆:45 積分:19 註冊:2005-01-24 發送簡訊給我 |
感謝RedSnow這位大大: 我的問題很多~~希望不要覺得不耐煩!!=.=" 那如果我要新增一個往回走的結構的話
*另外妳要增加結構項目,以便處理 "往回走" 的動作,那麼妳可能在這次增加一組往回走的資料之外,還要考慮再增設一組往回走的第二條路徑與距離資料,因為依據妳原先的資料來看,有的道路是有兩條分岔的,例如仁愛路往回走就有博愛路與中正路。
是不是用原本~~
void creat_combobox(String road)//從comboBox1所選擇的道路往下搜尋得到的道路新增到comboBox2的暫存字串裡 { Save_roadname *pointer, *an_pointer ; an_pointer = new Save_roadname ; an_pointer -> roadname = road ; an_pointer -> next = NULL ; save_head -> roadname = save_head -> roadname ; pointer = save_head ; while ( pointer != NULL ) { if ( pointer -> roadname == road || pointer -> roadname == "" ) break ; else { if ( pointer -> next != NULL ) pointer = pointer -> next ; else break ; } } if ( pointer -> next == NULL && pointer -> roadname != road ) { if ( pointer -> roadname == "" ) pointer -> roadname = road ; else pointer -> next = an_pointer ; } }往回走結構 sturct Return_roadname { String re_roadname; Return_roadname *next; }; Return_roadname *re_head , *re_tail; 再以此類推~~寫一個一模一樣的嗎? 例如 Save_roadname *pointer, *an_pointer ; 我就要寫成 Return_roadname *re_pointer,*re_an_pointer; 例如: ????head -> number = 1 ; head -> an_road_numeral = 0 ; head -> roadname = "成功路" ; ComboBox1 -> Items -> Add( head -> roadname ) ; head -> road_numeral = 35 ; 要變成~~ re_head->number=1; re_head->re_an_road_numeral=0; re_head -> re_roadname = "成功路" ; ComboBox1 -> Items -> Add( re_head -> re_roadname ) ; re_head -> re_road_numeral = 35 ; 之類的呢? |
RedSnow
版主 發表:79 回覆:1322 積分:845 註冊:2003-12-15 發送簡訊給我 |
liyanzi 妳好: 我不針對妳前一篇的個別問題作回覆了,請多包涵,以下我就妳的整體狀況做個建議: 就妳的狀況而言,想要做 "反向" 路徑的處理,其實在資料的結構與程式的處理流程上,與原先 "正向" 的處理應該是一樣的,只有路徑連結的設定有所不同而已。 因此妳不妨先按照原先的方式,另設一組資料結構 (變成兩組 "單向" 的路徑資料),然後按照 "反方向" 來設定另一組路徑資料,對於程式中有處理到路徑資料的地方,先以判斷 (配合 CheckBox 之類的設定) 的方式來做分別的處理 (使用相同程式敘述,但是依據判斷條件分別處理不同方向的路徑資料)。 等到程式能夠正確的運作 (包含正向與反向路徑的設定與處理),再設法對資料結構與程式敘述做最佳化處理 (用不著的部份予以精簡掉、重覆的部份予以合併....等),甚至將兩個資料結構再合併為一個 (雙向連結路徑),這樣子就應該可以完成一個完整的雙向路徑處理程式了。 7 天天敲鍵盤 v 時時按滑鼠 8
|
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |