[課業] 串列

看板NTUE-CS101作者yantchen (球童Yanting)時間16年前 (2009/04/09 17:48)推噓7(7推 0噓 1→)

留言8則, 5人參與討論串4/4 (看更多)

什麼是串列 ? 他是要幹麻用的 ? 我突然發現我跟老師好像都沒有跟你們仔細提到這個問題串列簡單來說就是一堆資料串在一起 ( 康熙字典有云：「串者，與貫通也。」 ) 先想像之前學過的陣列陣列就像表格一樣當你需要存很 n 筆資料的時候不需要宣告 int a,b,c,d, .... n; 只要宣告 int a[n]; // 這個語法只適用 dev c++ 電腦就會在記憶體內分配連續 n 個int的空間給你陣列很好用只要給電腦初始位置和 index 就可以當一般變數使用 ex: a[5]=3; a是初始位置 5是index 3是存進去的資料但是陣列因為先天上的設計 - 連續空間所以遇到一些問題的時候很棘手例如你要在 a[4] a[5] 之間插入一筆資料必須要把 a[5] 以後的東西往後推 ( a[n] 存到 a[n+1] ) 再把新的資料放到 a[5] 另外一個困難就是如果要刪除 a[3] 要把 a[3] 以後的資料往前推一格 ( a[n+1] 存到 a[n] ) 要解決上面的問題這時候就是串列派上用場的時候了串列只有起始位置他沒有 index 陣列有起始位置每筆資料有這個資料還有 index 串列有起始位置每筆資料有這個資料還有下一個人的記憶體位址(用指標存) 看下面的圖 ┌─┬┐ ┌─┬┐ ┌─┬┐ head →│１│─→│５│─→│８│─→ NULL 　　　　└─┴┘　└─┴┘　└─┴┘ head 就是起始位置就好像陣列 int a[10]裡面 a 是一個指標指向起始位置一樣改成這樣之後插入刪除資料就變的很輕鬆插入資料 ┌─┬┐　　 ┌─┬┐ ┌─┬┐ head →│１│─┐　┌│５│─→│８│─→ NULL 　　　　└─┴┘│　│└─┴┘　└─┴┘ 　　　　 ┌──┘　└┐ 　　　　　│ ┌─┬┐│　　 └→│３│─┘ 　　　　　　　└─┴┘ 要把 3 插到 1, 5中間就把 1 接到 3, 把 3 接到 5, 也就是說把前面一個人接到新的點, 把新的點接到後面的點刪除資料 ┌─┬┐　　 ┌─┬┐ ┌─┬┐ head →│１│───→│５│─→│８│─→ NULL 　　　　└─┴┘Ｘ　Ｘ└─┴┘　└─┴┘ 　　　　 ┌──┘　└┐ 　　　　　│ ┌─┬┐│　　 └→│３│─┘ 　　　　　　　└─┴┘ 要把 1, 3, 5 的 3 刪除只要把 1 接到 5 就好了也就是說把前面一個人接到要刪除的點後面的點那有了串列還要陣列幹嘛? 陣列因為是連續空間所以他的優點是速度快知道他的長度是多少串列是不連續空間所以速度較慢長度要從head跑到NULL才知道長度優點是資料常常會增減的時候很方便 -> 是什麼意思? 就好像要動指標 a 的資料的時候要用 *a 要動指標a的class成員的時候要用 a-> 所以 a->link()的意思是說呼叫 a指標所指的那個物件的link函數為什麼有時候用 head=p; 不用 head->link(p); 看一下新增節點(插入)的程式碼如果新的點要放在最前面的時候不可以直接 head->link(p); 因為這樣是 head所指到的人鏈結到p 這樣會導致 p變成第二個人要改成 head = p; ( head 存 p 裡面存的位址也就是說 head 指到 p指到的那個物件 ) 這就是 if(q2==NULL) head=p; else q2.link(p); 的原因 ( 我們在while外面指定 q1一開始=head q2一開始=NULL ) 最後要說基本上期中考應該就是串列了考試帶著課本還有之前交的作業看懂自己寫或是參考來的程式碼每一行在幹麻如果題目出現變化你要改哪裡怎麼改 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.68.15.209

推

linjrming

04/09 17:53, , 1^F

04/09 17:53, 1^F

推

chchwy

04/09 19:02, , 2^F

04/09 19:02, 2^F

推

linjrming

04/09 19:10, , 3^F

04/09 19:10, 3^F