推 rockmyangel:真的棒 我可能快要 稍微懂了 04/02 20:49
→ rockmyangel:越來越難了欸 大家努力阿 04/02 20:49
推 didi12252001:我有完整版的 包然有的沒的標準 還包含英英註解 04/03 00:00
推 didi12252001:要先上傳的找我拿檔案吧 04/03 00:00
其實不用想的那麼複雜
現在程式要做的事情有
1. 輸入資料
2. 產生節點
3. 找到節點在串列裡面的位置
4. 插進去
上禮拜是把 3 簡化成 所有新的節點的位置都是 head
現在需要思考一下 怎麼找到新的節點 他的後一個跟前一個
這裡先把這三個點取個名字
新的這個點叫做 p
他後面那個點（比他大的）叫做 q1
他前面那個點（比他小的）叫做 q2
（ p, q1, q2 都是 指標 ）
為什麼需要q1和q2？
先看第四步你就知道了
在串列裡面 不管你要擦頭 擦屁 還是擦中間
一定要有的步驟是
把前面一個人屁股的那條線接到你頭上
把你屁股上的線貼到後面那個人臉上
寫成程式就是
q2->setNext(p);
p->setNext(q1);
再回來想 3 怎麼寫
找到串列裡面的位置
想想我上禮拜有跟你們說把串列印出來的方法（走得很匆忙那次）
q=head;
while(q!=NULL)
{
cout<<q->getNo();
q=q->getNext();
}
先解釋一下
q=head; // 從頭開始
while(q!=NULL) // 如果 q 不是接地 （ 沒有東西了 ）
cout // 把 q 印出來
q=q->getNext(); // getNext()是傳回下一個人的位址 （ 你的函數名字可能不一樣 ）
// 所以 q 會指向他下一個人
OK 把 cout 拿掉然後改一下這個就可以用在 3 了
q1=head; // 用來存 p 的下一個 （ 比他大的那個 ） 人的指標
q2=NULL; // 用來存 p 的前一個 （ 比他小的那個 ） 人的指標
while(q1!=NULL && q1->getNo() < p->getNo() ){
q2=q1;
q1=q1->getNext();
}
// 迴圈裡面一樣 q1 指向 q1 的下一個
// 先看 while 裡面條件 如果 q1 比 p 的數字小的話 就代表還要往下找
// 這時 先把原本的 q1 存到 q2 （ 等下舉例說明 ）
// 然後 q1 指到他下面的那個人
說明一下為什麼要 q2=q1
假設你的串列已經有
1 5 7
要把 6 插進來
一開始 q1=1, q2=null ; 1 < 6 所以要繼續找
q1=5, q2=剛才的q1=1 ; 5 < 6 繼續往下
q1=7, q2=剛才的q1=5 ; 7 > 6 所以這就是他的位置
這時 從while迴圈裡面跳出來
把 5 ( q2 ) 接到 6 ( p )
把 6 ( p ) 接到 7 ( q1 )
-- 解釋部份到這裡結束 --
完整程式碼參考 http://0rz.tw/io1uG
這個是示意版
只有串列的部份
至於每個節點內的資料我只有設定作號
老師要求的其他資料就自己試著加上去吧
有問題在msn問我
掰XD
※ 引述《gingkoginkgo (人中拉拉!)》之銘言：
: ※ 引述《didi12252001 (撒嬌)》之銘言：
: : 有誰把程式寫出來的
: : 今天王老大的作業
: : 我卡題了
: : 哪個寫的出來的交一下吧
: 大致上思考流程如下 //這是當年的我寫的 說不定有錯 不過給個方向就是
: 插頭
: 1.產生新node 指定data
: 2.新node連結到head
: 3.head=新node
: 插屁屁
: 情形(1)head=NULL時 直接連上去
: 情形(2)head!=NULL時
: 1.p=head //make sure head exist
: 2.利用P移動到下一個(next)直到next=NULL
: 從小到大
: 1.先決定要3->5->6 還是9->8->2
: 2.考慮三種情況：插頭.插屁屁或是插中間
: 第一次 head->□ 進for洄圈
: node* temp=new node;
: node*p = new node;
: 上面這串的結果是 temp→□(temp指到一個新的)
: p→□(p也是指到一個新的)
: temp=head->next; 這串的話,就是讓Temp指到NULL,
: 因為你head只到的物件,
: 並沒有串到任何物件然後又讓
: p=temp->next;
: temp本身就沒指到東西了,又讓p指過去,
: 所以還是沒任何意義到最後就變成
: head→□ □ □ 成功只有head,
: 剩下的兩個就失連了
: 其實也可以爬爬100級的版? 看當年學長我(?)是怎麼跌跌撞撞到頭很痛XD
: 不過現在仍舊頭痛中就是
: 其實作法有很多種
: 也可以說你就先生出個空的頭 這個頭不放任何資料 只是指向下一個
: 你就會意外的發現好像有比較簡單嘍....
: 其實個人覺得Link list畫圖很重要
: 會把架構和你要做的事清楚的看明白
: 如果你能嚐試講出你每一步再做什麼 那大概就OK了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.15.209