什麼是串列 ? 他是要幹麻用的 ? 我突然發現我跟老師好像都沒有跟你們仔細提到這個問題 串列 簡單來說就是一堆資料串在一起 ( 康熙字典有云：「串者，與貫通也。」 ) 先想像之前學過的陣列 陣列就像表格一樣 當你需要存很 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