Re: [閒聊] 程設作業

[game0416 (鳳狼)]

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);
    }
    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
推 CaptainWill:鳳狼幹嘛這麼說...
推 Arashinoon:害我突然很好奇到底是發生什麼事情=  =
推 ip3311:12~34 建立順?
→ ip3311:    行
→ game0416:建立順序...表示產生的順序(輸入順序)
推 yantchen:我的朋友 是鳳娘(握
推 CaptainWill:元品跳針= =
推 Arashinoon:誰跳針=__= 不就是鳳狼最近文章火藥味很濃
推 Arashinoon:我很好奇發生什麼事情霸了
噓 dosomethnig:我們是馬吉耶!!! 馬吉PO文 就是要推阿!!
→ dosomethnig:準備怒吼了媽??       沒關係 你問小胖我睡覺都帶耳塞
推 suan710:看來當事者出面了..
→ dosomethnig:我們是馬吉耶
→ Arashinoon:所以到底是發生什麼大事可以讓鳳狼這麼生氣??
→ Arashinoon:                  ￣￣
→ suan710:請一哥說明:
推 CaptainWill:一哥表示:
噓 dosomethnig:ㄜ...我按錯了  我要按1推文的
→ dosomethnig:誤會一場 等我睡醒 再幫他推回來
推 suan710:看來誤會大囉  揪竟會怎麼樣呢?  讓我們繼續看下去
推 Arashinoon:說好的資科向心力呢 快GG了
推 CaptainWill:一哥只是開玩笑，別認真
推 Arashinoon:我幫一哥推回來一個
→ CaptainWill:一哥表示
→ s86186654418:       好像在看連載唷
推 suan710:                          什麼時候出下一集
→ Arashinoon:                                           下集待續
→ CaptainWill:你們這群顧吃雞排不幫忙解決事情的人 囧
→ Arashinoon:樓上別這樣 我也有幫忙
→ s86186654418:coming soon
→ CaptainWill:                               是說我想吃宵夜了...
推 suan710:遺憾的是宿舍出不去派克又關了..
→ Arashinoon:看到上面的雞排我肚子餓了
→ CaptainWill:雞排 珍奶 茄汁牛肉麵 味噌拉麵 麻辣鍋 臭豆腐.......
→ Arashinoon:幹=  =
→ CaptainWill:幹很餓....
→ CaptainWill:http://tinyurl.com/yb4ozhx
→ Arashinoon:幹  樓上恐怖連結都不用說的喔
→ CaptainWill:說了你會點?!
→ CaptainWill:http://tinyurl.com/ydc65nf  幹...真的受不了
→ Genya0:呵呵呵
→ CaptainWill:呵呵
→ Arashinoon:我沒存糧了 好餓....
→ CaptainWill:http://tinyurl.com/ybusxy4  阿辣試試這個
→ Arashinoon:草尼馬的魷魚+美乃滋
推 suan710:存糧大拍賣!!
→ Arashinoon:樓上有啥 說來聽聽    幹還是算了 會更餓
推 pk873:          ╴╴╴╴             ▌
→ pk873:        ／∵ ∴ ∵＼  \￣￣￣￣￣￣/
→ pk873:       /∴ ∵ ∴ ∵ \  \          /
→ pk873:      ███████▋  \        /
→ pk873:       \ ∴ ∵ ∴ ∵/    \      /
→ pk873:        ＼∵ ∴ ∵／      \____/
→ pk873:          ￣￣￣￣
→ pk873:頭痛...睡覺去...
→ suan710:泡麵X N 糖果  口糧   應有盡有喔  揪咪
→ CaptainWill:http://tinyurl.com/y9bnmpg 這張史上最恐怖(無膽勿試
→ suan710:算了真的要睡了...8點記得叫我
→ CaptainWill:這樣睡得著嗎 阿辣?
→ Arashinoon:阿花洗個澡?? 還是洗過了
→ CaptainWill:我下午從陽明山觀光回來的時候洗過了－ˇ－
→ CaptainWill:我要用睡眠來克服肌餓了...掰
→ Arashinoon:掰...
→ CaptainWill:                   (講得自己很像難民= =
推 pig456654:                 ◢████████████◤▏
→ pig456654:                ◢◤____◢◤____◢◤____◢◤╱
→ pig456654:              ◢◤╱  ◢◤╱  ◢◤╱  ◢◤╱
→ pig456654:            ◢████◤╱  ◢████◤╱
→ pig456654:          ◢◤▏    ▕╱  ▕______◢◤╱
→ pig456654:        ◢◤╱￣￣￣￣          ◢◤╱
→ pig456654:      ◢◤╱   ◢████◤▏ ◢◤╱
→ pig456654:    ◢◤╱   ◢◤____◢◤╱ ◢◤╱
→ pig456654:  ◢◤╱   ◢◤╱  ◢◤╱ ◢◤╱
→ pig456654:◢████████████◤╱
→ pig456654:▏                      ▕╱
→ pig456654:￣￣￣￣￣￣￣￣￣￣￣￣￣