1.本周學(xué)習(xí)總結(jié)

1.1思維導(dǎo)圖

1.2學(xué)習(xí)體會

本章學(xué)習(xí)了圖，圖的定義，圖的存儲結(jié)構(gòu)，圖的遍歷以及最小生成樹，最短路徑，拓?fù)渑判虻人惴?#xff0c;學(xué)習(xí)圖的存儲結(jié)構(gòu)比較容易，但在學(xué)習(xí)普里姆最小生成樹和狄克斯特最短路徑時花費的時間較多，對于這種復(fù)雜的算法，需要慢慢地理解其思路然后再學(xué)習(xí)代碼的寫法。

2.PTA實驗作業(yè)

2.1 題目1：7-1 圖著色問題

2.1.1設(shè)計思路

建立鄰接矩陣g 將顏色存入到數(shù)組a[]中 for i=1 to i=nfor j=1 to j=nif(if(a[i]==a[j]&&g[i][j]==1) flag=0 //對于每一個條邊g[i][j],其兩個頂點的顏色分別位a[i]和a[j],若有a[i]=a[j],則可判斷不滿足條件

2.1.2代碼截圖

2.1.3本題PTA提交列表說明

1.部分正確是因為沒注意題目要求顏色數(shù)要等于輸出的顏色數(shù)N 2.所以后面加了c[]數(shù)組判斷顏色數(shù)

2.2 題目2：7-3 六度空間

2.2.1 設(shè)計思路

建立鄰接表g 用廣度遍歷的方法遍歷g visited[]數(shù)組來判斷結(jié)點時否被訪問過，訪問過就為1，否則為0 定義(int) temp,tail,last=x三個變量,x是參數(shù),該函數(shù)作用是“輸出與x結(jié)點距離不超過6的結(jié)點數(shù)”,第一層的最后一個結(jié)點就是x，所以laxt=x 定義(int) sum 變量用于儲存與x結(jié)點距離不超過6的結(jié)點數(shù) queue<int> q;//新建一個隊列q q.push(x)//先將x放入隊列中 visited[x]=0; while(!q.enmpty())//當(dāng)q不為空時 {temp=q.front();p訪問q中隊頭所對應(yīng)的鄰接表結(jié)點q.pop();while(p!=NULL){ 如果p未被訪問 {入隊，sum++，visited[(p->adjvex)]=1，tail=p->adjvex//這樣子當(dāng)訪問到最后該層的最后一個結(jié)點時,tail儲存的會是下一層最后一個結(jié)點的位置 }p=p->nextarc //p訪問p的下一個鄰接點}if(temp=last) {level++；last=tail //tail此時找到了下一層結(jié)點的最后一個元素位置,將其值給last} } 結(jié)果return sum

2.2.2 代碼截圖

2.2.3本題PTA提交列表說明

1.一開始的算法思路不對，導(dǎo)致只能過一個測試點，后來去問到了這種判斷層次的思路才過了所有測試點 2.編譯錯誤就是用了c提交，為什么會這樣我也不知道

2.3 題目3：7-6 修建道路

2.3.1 設(shè)計思路

建立鄰接矩陣g 將已經(jīng)連通的道路的價格g.price[i][j]變成0； 最后用普里姆算法即可計算最少花費(普里姆算法這里就不詳細(xì)解說)

2.3.2 代碼截圖

2.3.3本題PTA提交列表說明

1.一開始的思路是把已經(jīng)連通的路的頂點放入v集合中，然后再計算最少消費。但是后來發(fā)現(xiàn)這樣做的話v集合中的頂點不一定個個連通，也就是v集合不一定連通，導(dǎo)致后面全錯 2.后來在別人指導(dǎo)下，把已經(jīng)連通的路的修路費用改成0，然后再用普里姆算法計算最少消費

3、上機(jī)考試錯題及處理辦法

3.1 6-2 jmu-ds-圖鄰接表操作錯誤代碼

錯誤代碼

改正后得到代碼

錯誤就錯在這里 少了G->n=n;G->e=e; 由于本人比較偏向完美主義，做不過的題目不想跳過。所以只寫了 第一題最短路徑，卡在第二題卡了一節(jié)課，考試結(jié)束后通過和練習(xí)比對發(fā)現(xiàn)只是少了G->n=n;G->e=e;兩行代碼，(但是考試的時候我通過調(diào)試發(fā)現(xiàn)的卻是visited在第二次運(yùn)行函數(shù)是沒有初始化導(dǎo)致的，雖然主函數(shù)已經(jīng)有for(i=1;i<=G->n;i++) visited[i]=0這個語句，但是我在隨后運(yùn)行的BFS()函數(shù)中查了一下visited[]的值全部輸出1，但是出去比對以后發(fā)現(xiàn)是少了G->n=n;G->e=e,但是為什么導(dǎo)致我考試時候遇見的問題我也沒有深究)，改正后可以通過。而后面的六度空間等題目在上面我也詳細(xì)地講過了，這里就不再寫一遍了

轉(zhuǎn)載于:https://www.cnblogs.com/syt666/p/9545446.html

總結(jié)

以上是生活随笔為你收集整理的第零次作业的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。