熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

順序表和鏈表的比較

2013-11-15 15:07:04  來源: 數據結構 

順序表和鏈表的比較

    順序表和鏈表各有短長在實際應用中究竟選用哪一種存儲結構呢?這要根據具體問題的要求和性質來決定通常有以下幾方面的考慮
┌───┬───────────────┬───────────────┐
│      │         順序表          │         鏈表            │
├─┬─┼───────────────┼───────────────┤
│基│分│靜態分配程序執行之前必須明確│動態分配只要內存空間尚有空閒
│於│配│規定存儲規模若線性表長度n變 │就不會產生溢出因此當線性表│
│空│方│化較大則存儲規模難於預先確定│的長度變化較大難以估計其存儲│
│間│式│估計過大將造成空間浪費估計太│規模時以采用動態鏈表作為存儲│
│考│  │小又將使空間溢出機會增多    │結構為好                    │
│慮├─┼───────────────┼───────────────┤
│  │存│為當線性表的長度變化不大 │<                            │
│  │儲│易於事先確定其大小時為了節約│                              │
│  │密│存儲空間宜采用順序表作為存儲│                              │
│  │度│結構                        │                              │
├─┼─┼───────────────┼───────────────┤
│基│存│隨機存取結構對表中任一結點都│順序存取結構鏈表中的結點需│
│於│取│可在O()時間內直接取得      │從頭指針起順著鏈掃描才能取得
│時│方│線性表的操作主要是進行查找很│                              │
│間│法│少做插入和刪除操作時采用順序│                              │
│考│  │表做存儲結構為宜            │                              │
│慮├─┼───────────────┼───────────────┤
│  │插│在順序表中進行插入和刪除平均│在鏈表中的任何位置上進行插入和│
│  │入│要移動表中近一半的結點尤其是│刪除都只需要修改指針對於頻│
│  │刪│當每個結點的信息量較大時移動│繁進行插入和刪除的線性表宜采│
│  │除│結點的時間開銷就相當可觀    │用鏈表做存儲結構若表的插入和│
│  │操│                              │刪除主要發生在表的首尾兩端則│
│  │作│                              │采用尾指針表示的單循環鏈表為宜│
└─┴─┴───────────────┴───────────────┘


    存儲密度(Storage Density)是指結點數據本身所占的存儲量和整個結點結構所占的存儲量之比

    存儲密度=(結點數據本身所占的存儲量)/(結點結構所占的存儲總量)

 


From:http://tw.wingwit.com/Article/program/sjjg/201311/22873.html
  • 上一篇文章:

  • 下一篇文章:
  • 推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.