1、試比較順序儲存結構和鏈式儲存結構的優缺點。在什麼情況下用順序錶比鍊錶好?
優點:儲存密度大(=1),儲存空間利用率高。缺點:插入或刪除元素時不方便。
②鏈式儲存時,相鄰資料元素可隨意存放,但所佔儲存空間分兩部分,一部分存放結點值,另一部分存放表示結點間關係的指標
優點:插入或刪除元素時很方便,使用靈活。缺點:儲存密度小(<1),儲存空間利用率低。
順序表適宜於做查詢這樣的靜態操作;鍊錶宜於做插入、刪除這樣的動態操作。
若線性表的長度變化不大,且其主要操作是查詢,則採用順序表;
若線性表的長度變化較大,且其主要操作是插入、刪除操作,則採用鍊錶。
順序表與鍊錶的比較
基於空間的比較
儲存分配的方式
順序表的儲存空間是靜態分配的
鍊錶的儲存空間是動態分配的
儲存密度 = 結點資料本身所佔的儲存量/結點結構所佔的儲存總量
順序表的儲存密度 = 1
鍊錶的儲存密度 < 1
基於時間的比較
訪問方式
順序表可以隨機訪問,也可以順序訪問
鍊錶是順序訪問的
插入/刪除時移動元素個數
順序表平均需要移動近一半元素
鍊錶不需要移動元素,只需要修改指標
順序表和煉表的比較
順序表和煉表各有短長。在實際應用中究竟選用哪一種儲存結構呢?這要根據具體問題的要求和性質來決定。通常有以下幾方面的考慮:
順序錶鏈表
│基│分│靜態分配。程式執行之前必須明確│動態分配只要記憶體空間尚有空閒,│
│於│配│規定儲存規模。若線性表長度n變│就不會產生溢位。因此,當線性表│
│空│方│化較大,則儲存規模難於預先確定│的長度變化較大,難以估計其儲存│
│間│式│估計過大將造成空間浪費,估計太│規模時,以採用動態鍊錶作為儲存│
│考│ │小又將使空間溢位機會增多。 │結構為好
│慮│ │存│為1。當線性表的長度變化不大, │<1
│ │儲│易於事先確定其大小時,為了節約
│ │密│儲存空間,宜採用順序表作為儲存
│ │度│結構
│基│存│隨機訪問結構,對錶中任一結點都│順序訪問結構,鍊錶中的結點,需│
│於│取│可在o(1)時間內直接取得 │從頭指標起順著鏈掃瞄才能取得。│
│時│方│線性表的操作主要是進行查詢,很
│間│法│少做插入和刪除操作時,採用順序
│考│ │表做儲存結構為宜
│慮│ │插│在順序表中進行插入和刪除,平均│在鍊錶中的任何位置上進行插入和│
│ │入│要移動表中近一半的結點,尤其是│刪除,都只需要修改指標。對於頻│
│ │刪│當每個結點的資訊量較大時,移動│繁進行插入和刪除的線性表,宜採│
│ │除│結點的時間開銷就相當可觀。 │用鍊錶做儲存結構。若表的插入和│
│ │操刪除主要發生在表的首尾兩端,則│
│ │作採用尾指標表示的單迴圈鍊錶為宜│
為什麼在單迴圈鍊錶中設定尾指標比設定頭指標更好?
答:尾指標是指向終端結點的指標,用它來表示單迴圈鍊錶可以使得查詢鍊錶的開始結點和終端結點都很方便,設一帶頭結點的單迴圈鍊錶,其尾指標為rear,則開始結點和終端結點的位置分別是rear->next->next 和 rear, 查詢時間都是o(1)。 若用頭指標來表示該鍊錶,則查詢終端結點的時間為o(n)。
在鍊錶中設定頭結點有什麼好處?
頭結點即在鍊錶的首元結點之前附設的乙個結點,該結點的資料域可以為空,也可存放表長度等附加資訊,其作用是為了對鍊錶進行操作時,可以對空表、非空表的情況以及對首元結點進行統一處理,程式設計更方便。
順序表和鏈式表儲存結構研究
摘要 資料結構是指相互之間存在著一種或多種關係的資料元素的集合和該集合中資料元素之間的關係組成。本文主要研究的是常用的資料結構線性表,線性表分為順序表和鏈式表。了這兩種儲存結構的邏輯結構 物理結構 資料結構的運算及對比分析。關鍵詞 資料結構 線性表 順序表 鏈式表 儲存結構 運算 1 線性表的概述 ...
硬碟的儲存原理與儲存結構
大家都知道磁鐵有兩個極性,乙個是南極 s極 乙個是北極 n 極 硬碟正是利用磁粒子的極性來記錄資料的。碟片表面的那些磁粉就是磁粒子。碟片被劃分成若干個同心圓 稱為磁軌 在每個同心圓的磁軌上就好像有無數的任意排列的小磁鐵,當這些小磁鐵受到來自磁頭磁場的影響時,排列的方向隨之改變,利用磁頭的磁力統一某區...
IC卡的儲存結構和工作原理
ic卡儲存結構 m1卡分為16個扇區,每個扇區由4塊 塊0 塊1 塊2 塊3 組成,我們也將16個扇區的64個塊按絕對位址編號為0 63,存貯結構如下圖所示 第0扇區的塊0 即絕對位址0塊 它用於存放廠商 已經固化,不可更改。每個扇區的塊0 塊1 塊2為資料塊,可用於存貯資料。ic卡工作原理 卡片的...