hmmmm 我沒朋友，也開不起玩笑。 -- 延續插排的概念...作業五的構成 腦袋還沒空掉的話，鏈結可以當成是一套隨時變動長度的陣列 在基本盤來說，能用鏈結串列來做插排確實會比用陣列來得符合概念 只是實做上複雜性比較高一點，建立過程問題比較多，昨天抓個首項bug玩掉一小時(倒 好...再來先做個接下來用的表格說明 正確的長度會隨著說明一個一個冒出來，這裡先當做做出十個了 ┌—┬—┬—┬—┬—┬—┬—┬—┬—┬—┐ ｜０｜１｜２｜３｜４｜５｜６｜７｜８｜９｜ ←建立順、ID，兩者相同 ├—┼—┼—┼—┼—┼—┼—┼—┼—┼—┤ ｜０｜１｜２｜３｜４｜５｜６｜７｜８｜９｜ ←串列內順序 ├—┼—┼—┼—┼—┼—┼—┼—┼—┼—┤ ｜１｜１｜２｜４｜６｜８｜９｜10｜80｜99｜ ←分數內容 └—┴—┴—┴—┴—┴—┴—┴—┴—┴—┘ : 類別部分採前文用的名字、內容 -- 先來說明實作法，有其他概念再談hmm 這邊隨意排幾組 ┌—┐ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ｜０｜ ｜３｜ ｜１｜ ｜２｜ ｜４｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜０｜ ｜１｜ ｜２｜ ｜３｜ ｜４｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜１｜ ｜３｜ ｜６｜ ｜８｜ ｜９｜ └—┘ └—┘ └—┘ └—┘ └—┘ 現在假設有第５個、４要插入，就沿著串列順序去找大於４的那一個 確認是順序在２的１比較大，就把５的指標指向１(順序２)、３指向５ (５取代成為第２項、後面的跟著自動會往後退一個順序) 變成是 -- 插入 ↓ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ｜０｜ ｜３｜ ｜５｜ ｜１｜ ｜２｜ ｜４｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜０｜ ｜１｜ ｜２｜ ｜３｜ ｜４｜ ｜５｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜１｜ ｜３｜ ｜４｜ ｜６｜ ｜８｜ ｜９｜ └—┘ └—┘ └—┘ └—┘ └—┘ └—┘ 我不想多擠一行寫指向的下一項，所以就請稍微心領神會 每一個指向的下一項就看編號順 -- 首先，在開始時是NULL，只建立幾個aclass *p指標準備 或是你喜歡也能先new個位址給指標 我自己是試著整套用同個邏輯走，都放在迴圈內生成 int main(){ aclass *p,*head,*tmp; } 這裏三個指標，一個用來做運作(p)，一個用來指示起始點(head) tmp主要用來記錄前一項的位址，因為p一定會像前面例子跑到２，抓不到前一個１在哪 : 有另外建立前項指標的寫法另論 再來進每次輸入、生成的部份...因為無聊，所以寫成跟陣列的範例一樣沒有最大上限 這裡用while製作 剛進迴圈，一樣先不要管類別部份 我們就先接受id、grade後再研究要幹嘛 while(true){ int id,grade; cin>>id >>grade; } -- 針對第一項輸入沒有前後、內容，當作一個特例處理，在while之前設一個bool標記第一次 其他就照常輸入就好 bool start=true; while(true){ int id,grade; cin>>id >>grade; if (start){ start = false; p = head = new aclass; p->setid(id); p->setgrade(grade); p->setptr(NULL); } else{ } } 然後是之後開始輸入的每一項，都在else內處理 -- 從第二項開始，因為都不確定應該插在哪 因此從頭開始沿著串列比大小，把p跟tmp一起歸零回到第一項 開始沿著過程比大小，找出從哪個地方開始比輸入來得大 尋找要從哪裡插入 else{ p=tmp=head; while (true) { if (grade < p->getgrade()) break; else { tmp=p; if (p->getptr()==NULL) break; p=p->getptr(); } } -- 因為每次都是確定p->getgrade()小於輸入後tmp才變為p 一旦發現有比輸入值來得大的，或是一路沒有比輸入值來得小的數值就跳出 所以整個回圏結束時，tmp的位置一定會剛好是要插入的前一項 : 這部份不懂就多畫幾次圖，搞不懂來問我也無妨...我會看是誰決定怎樣說明 知道要插在哪項之後就很簡單... new個物件給p、把東西裝裝進去就是了 然後替換一下指標指向位址就好 p = new aclass; p->setid(id); p->setgrade(grade); p->setptr(tmp->getptr()); tmp->setptr(p); -- 就這樣...插入結束後就把內容印出來看有沒有問題 p=head; while (true){ cout <<p->getid() <<'\t' <<p->getgrade() <<'\n'; if (p->getptr()==NULL) break; p=p->getptr(); } 嗯...上面這樣算寫完八成左右 殘餘會出現一個bug，在第一項變成新的輸入值時會出錯 會插入到第二項，而不是第一項 為了這點，我是再針對這個特例做處理 在前面偵測要插入在哪的地方多加一點變數判斷 -- 加個bool記錄一下是不是第一項需要換 else{ p=tmp=head; bool first=true; while (true) { if (grade < p->getgrade()) break; else { first=false; tmp=p; if (p->getptr()==NULL) break; p=p->getptr(); } } -- 再來隨著這個判斷 將配置物件內指標指向的地方做一點修改 避免因為first判斷讓程式誤認為只要是first都要擺到第一項前 在判斷式確定應該在前或在後 p = new students; p->setid(id); p->setgrade(grade); if (first && grade<tmp->getgrade()) { p->setptr(tmp); head = p; } else { p->setptr(tmp->getptr()); tmp->setptr(p); } 這樣就算完成....大概吧 -- 完整內容大概就這樣 #include<iostream> using namespace std; class students{ public: int getid(); int getgrade(); students* getptr(); void setid(int ID); void setgrade(int GRADE); void setptr(students *PTR); private: int id; int grade; students *ptr; }; void students::setid(int ID){id=ID;}; void students::setgrade(int GRADE){grade=GRADE;}; void students::setptr(students *PTR){ptr=PTR;}; int students::getid(){return id;}; int students::getgrade(){return grade;}; students* students::getptr(){return ptr;}; int main() { students *p,*head,*tmp; bool start=true; while(true){ int id,grade; cin>>id >>grade; if (start){ p = head = new students; p->setid(id); p->setgrade(grade); p->setptr(NULL); start=false; } else{ p=tmp=head; bool first=true; while (true) { if (grade < p->getgrade()) break; else { first=false; tmp=p; if (p->getptr()==NULL) break; p=p->getptr(); } } p = new students; p->setid(id); p->setgrade(grade); if (first && grade<tmp->getgrade()) { p->setptr(tmp); head = p; } else { p->setptr(tmp->getptr()); tmp->setptr(p); } } p=head; while (true){ cout <<p->getid() <<'\t' <<p->getgrade() <<'\n'; if (p->getptr()==NULL) break; p=p->getptr(); } } } -- 所恐懼的，不是沒有知識的大眾　 所憎恨的，不是深沉幽暗的人心 而是自以為是的思考之聲 而是自恃甚高的執法者 所毀滅的，不是溫馨和諧的世界 這是我最後的期許，沒有憤怒、沒有悔恨 而是自欺欺人的夢境 只剩下，渾沌的死亡呼吸 　　　　　　　　　　　　　　 節自　新月神話－弒王者 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.114.76.199 小修個BUG ※ 編輯: game0416 來自: 120.127.47.93 (03/22 10:15)