C++數(shù)據結構(第2版)課件第2章 線性表.ppt

,第 2 章 線性表,線性表的邏輯結構 線性表的順序存儲及實現(xiàn) 線性表的鏈接存儲及實現(xiàn) 順序表和鏈表的比較 線性表的其他存儲方法,本章的基本內容是：,2.1 線性表的邏輯結構,數(shù)據元素之間的關系是什么？,2.1 線性表的邏輯結構,數(shù)據元素之間的關系是什么？,現(xiàn)實生活中，許多問題抽象出的數(shù)據模型是線性表，如何存儲這種線性結構并實現(xiàn)插入、刪除、查找等基本操作呢？,線性表：簡稱表，是n（n0）個具有相同類型的數(shù)據元素的有限序列。 線性表的長度：線性表中數(shù)據元素的個數(shù)。 空表：長度等于零的線性表，記為：L=( )。 非空表記為：L（a1, a2 , , ai-1, ai , , an),2.1 線性表的邏輯結構,線性表的定義,其中，ai（1in）稱為數(shù)據元素； 下角標 i 表示該元素在線性表中的位置或序號 。,2.1 線性表的邏輯結構,線性表的特性,1. 有限性：線性表中數(shù)據元素的個數(shù)是有窮的。,2. 相同性：線性表中數(shù)據元素的類型是同一的。,3. 順序性：線性表中相鄰的數(shù)據元素ai-1和ai之間存在序偶關系(ai-1, ai)，即ai-1是ai的前驅， ai是ai-1的后繼；a1無前驅，an無后繼，其它每個元素有且僅有一個前驅和一個后繼。,線性表的抽象數(shù)據類型定義,ADT List Data 線性表中的數(shù)據元素具有相同類型， 相鄰元素具有前驅和后繼關系 Operation InitList 前置條件：表不存在 輸入：無 功能：表的初始化 輸出： 無 后置條件：建一個空表,2.1 線性表的邏輯結構,DestroyList 前置條件：表已存在 輸入：無 功能：銷毀表 輸出：無 后置條件：釋放表所占用的存儲空間 Length 前置條件：表已存在 輸入：無 功能：求表的長度 輸出：表中數(shù)據元素的個數(shù) 后置條件：表不變,2.1 線性表的邏輯結構,線性表的抽象數(shù)據類型定義,Get 前置條件：表已存在 輸入：元素的序號i 功能：在表中取序號為i的數(shù)據元素 輸出：若i合法，返回序號為i的元素值，否則拋出異常 后置條件：表不變 Locate 前置條件：表已存在 輸入：數(shù)據元素x 功能：在線性表中查找值等于x的元素 輸出：若查找成功，返回x在表中的序號，否則返回0 后置條件：表不變,2.1 線性表的邏輯結構,線性表的抽象數(shù)據類型定義,Insert 前置條件：表已存在 輸入：插入i；待插x 功能：在表的第i個位置處插入一個新元素x 輸出：若插入不成功，拋出異常 后置條件：若插入成功，表中增加一個新元素 Delete 前置條件：表已存在 輸入：刪除位置i 功能：刪除表中的第i個元素 輸出：若刪除成功，返回被刪元素，否則拋出異常 后置條件：若刪除成功，表中減少一個元素,2.1 線性表的邏輯結構,線性表的抽象數(shù)據類型定義,Empty 前置條件：表已存在 輸入：無 功能：判斷表是否為空 輸出：若是空表，返回1，否則返回0 后置條件：表不變 ADT,進一步說明: （1）線性表的基本操作根據實際應用是而定； （2）復雜的操作可以通過基本操作的組合來實現(xiàn)； （3）對不同的應用，操作的接口可能不同。,2.1 線性表的邏輯結構,線性表的抽象數(shù)據類型定義,2.2 線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,例：（34, 23, 67, 43）,34,23,67,43,4,2.2 線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,例：（34, 23, 67, 43）,34,23,67,43,4,用什么屬性來描述順序表？,2.2 線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,例：（34, 23, 67, 43）,34,23,67,43,4,如何實現(xiàn)順序表的內存分配？,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空閑,長度,2.2 線性表的順序存儲結構及實現(xiàn),順序表,一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：,數(shù)組的長度Max,線性表的長度Length,數(shù)組的長度大于等于當前線性表的長度,如何求得任意元素的存儲地址？,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空閑,長度,2.2 線性表的順序存儲結構及實現(xiàn),順序表,一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空閑,長度,Loc(ai)=Loc(a1) + (i -1)c,隨機存?。涸贠(1)時間內存取數(shù)據元素,2.2 線性表的順序存儲結構及實現(xiàn),順序表,一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：,2.2 線性表的順序存儲結構及實現(xiàn),存儲結構是數(shù)據及其邏輯結構在計算機中的表示； 存取結構是在一個數(shù)據結構上對查找操作的時間性能的一種描述。,存儲結構和存取結構,“順序表是一種隨機存取的存儲結構”的含義為：在順序表這種存儲結構上進行的查找操作，其時間性能為O(1)。,順序表類的聲明,const int MaxSize=100; template /模板類 class SeqList public: SeqList( ) ; /構造函數(shù) SeqList(DataType a , int n); SeqList( ) ; /析構函數(shù) int Length( ); DataType Get(int i); int Locate(DataType x ); void Insert(int i, DataType x); DataType Delete(int i); private: DataType dataMaxSize; int length; ;,2.2 線性表的順序存儲結構及實現(xiàn),操作接口：SeqList( ),算法描述： SeqList :SeqList( ) length = 0; ,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)無參構造函數(shù),0,操作接口：SeqList(DataType a , int n),順序表的實現(xiàn)有參構造函數(shù),2.2 線性表的順序存儲結構及實現(xiàn),5,35,12,24,33,42,template SeqList :SeqList(DataType a , int n) if (n MaxSize) throw “參數(shù)非法“; for (i = 0; i n; i+ +) datai = ai; length = n; ,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)有參構造函數(shù),算法描述：,操作接口： void Insert(int i, DataType x) 插入前：(a1, , ai-1, ai, , an) 插入后：(a1, , ai-1, x , ai, , an),順序表的實現(xiàn)插入,2.2 線性表的順序存儲結構及實現(xiàn),ai-1和ai之間的邏輯關系發(fā)生了變化,順序存儲要求存儲位置反映邏輯關系,存儲位置要反映這個變化,例：（35，12，24，42），在i=2的位置上插入33。,表滿：length=MaxSize 合理的插入位置：1ilength+1（i指的是元素的序號）,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)插入,4,35,12,24,42,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,什么時候不能插入？,1. 如果表滿了，則拋出上溢異常; 2. 如果元素的插入位置不合理，則拋出位置異常; 3. 將最后一個元素至第i個元素分別向后移動一個位置； 4. 將元素x填入位置i處； 5. 表長加1；,算法描述偽代碼,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)插入,template void SeqList:Insert(int i, DataType x) if (length = MaxSize) throw “上溢“; if (i length + 1) throw “位置“; for (j = length; j = i; j-) dataj = dataj-1; datai-1 = x; length+; ,算法描述C+描述,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)插入,基本語句？,最好情況（ i=n+1）： 基本語句執(zhí)行0次，時間復雜度為O(1)。 最壞情況（ i=1）： 基本語句執(zhí)行n+1次，時間復雜度為O(n)。 平均情況（1in+1）： 時間復雜度為O(n)。,時間性能分析,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)插入,操作接口： DataType Delete(int i) 刪除前：(a1, , ai-1,ai,ai+1,an) 刪除后：(a1,ai-1,ai+1, ,an),順序表的實現(xiàn)刪 除,2.2 線性表的順序存儲結構及實現(xiàn),ai-1和ai之間的邏輯關系發(fā)生了變化,順序存儲要求存儲位置反映邏輯關系,存儲位置要反映這個變化,例：（35, 33, 12, 24, 42），刪除i=2的數(shù)據元素。,仿照順序表的插入操作，完成： 1. 分析邊界條件； 2. 分別給出偽代碼和C+描述的算法； 3. 分析時間復雜度。,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)刪 除,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,12,24,42,順序表的實現(xiàn)按位查找,操作接口： DataType Get(int i),2.2 線性表的順序存儲結構及實現(xiàn),0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空閑,n,算法描述： template DataType SeqList :Get( int i ) if (i = 1 ,時間復雜度？,順序表的實現(xiàn)按值查找,操作接口： int Locate(DataType x ),2.2 線性表的順序存儲結構及實現(xiàn),5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,例：在（35, 33, 12, 24, 42） 中查找值為12的元素，返回在表中的序號。,template int SeqList :Locate(DataType x) for (i = 0; i length; i+) if (datai = x) return i + 1; return 0; ,2.2 線性表的順序存儲結構及實現(xiàn),順序表的實現(xiàn)按值查找,算法描述：,時間復雜度？,順序表的優(yōu)缺點,順序表的優(yōu)點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間； 隨機存取：可以快速地存取表中任一位置的元素。,順序表的缺點： 插入和刪除操作需要移動大量元素； 表的容量難以確定，表的容量難以擴充； 造成存儲空間的碎片。,2.2 線性表的順序存儲結構及實現(xiàn),單鏈表：線性表的鏈接存儲結構。 存儲思想：用一組任意的存儲單元存放線性表的元素。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,存儲特點： 邏輯次序和物理次序 不一定相同。 2.元素之間的邏輯關系 用指針表示。,2.3 線性表的鏈接存儲結構及實現(xiàn),例：(a1, a2 ,a3, a4)的存儲示意圖,單鏈表,a1 0200,a2 0325,a3 0300,a4 ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,數(shù)據域,指針域,單鏈表是由若干結點構成的； 單鏈表的結點只有一個指針域。,data：存儲數(shù)據元素 next：存儲指向后繼結點的地址,template struct Node DataType data; Node *next; ;,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,如何申請一個結點？,s=new Node ;,template struct Node DataType data; Node *next; ;,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,s=new Node ;,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,如何引用數(shù)據元素？,data,如何引用指針域？,next,s-next;,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,重點在數(shù)據元素之間的邏輯關系的 表示，所以，將實際存儲地址抽象。,什么是存儲結構？,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,頭指針：指向第一個結點的地址。 尾標志：終端結點的指針域為空。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,空表和非空表不統(tǒng)一，缺點？ 如何將空表與非空表統(tǒng)一？,頭結點：在單鏈表的第以一個元素結點之前附設一個類型相同的結點，以便空表和非空表處理統(tǒng)一。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表,非空表,template class LinkList public: LinkList( )； LinkList(DataType a , int n); LinkList( ); int Length( ); DataType Get(int i); int Locate(DataType x); void Insert(int i, DataType x); DataType Delete(int i); void PrintList( ); private: Node *first; ;,單鏈表類的聲明,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)遍歷操作,操作接口： void PrintList( );,核心操作（關鍵操作）：工作指針后移。從頭結點（或開始結點）出發(fā)，通過工作指針的反復后移而將整個單鏈表“審視”一遍的方法稱為掃描（或遍歷）。,2.3 線性表的鏈接存儲結構及實現(xiàn),first,a1,a2,an,ai,單鏈表的實現(xiàn)遍歷操作,操作接口： void PrintList( );,2.3 線性表的鏈接存儲結構及實現(xiàn),template void LinkList : PrintList( ) p = first-next; while (p != NULL) cout data; p = p-next; ,單鏈表的實現(xiàn)按位查找,操作接口： DataType Get(int i);,2.3 線性表的鏈接存儲結構及實現(xiàn),first,a1,a2,an,ai,1. 工作指針p初始化; 累加器count初始化; 2. 重復執(zhí)行下述操作，直到p為空： 2.1 工作指針p后移; 2.2 count+; 3. 返回累加器count的值；,template int LinkList : Length( ) p = first-next; count = 0; while (p != NULL) p = p-next; count+; return count; /注意count的初始化和返回值之間的關系 ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)按位查找,算法描述C+描述,template int LinkList : Locate(DataType x) p = first-next; count = 1; while (p != NULL) if (p-data = x) return count; /查找成功，返回序號 p = p-next; count+; return 0; /退出循環(huán)表明查找失敗 ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)按值查找,算法描述C+描述,單鏈表的實現(xiàn)插入,操作接口： void Insert(int i, DataType x);,2.3 線性表的鏈接存儲結構及實現(xiàn),如何實現(xiàn)結點ai-1、x和ai之間邏輯關系的變化？,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,注意分析邊界情況表頭、表尾。,單鏈表的實現(xiàn)插入,2.3 線性表的鏈接存儲結構及實現(xiàn),first,a1,an,ai,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,由于單鏈表帶頭結點，表頭、表中、表尾三種情況的操作語句一致。,算法描述偽代碼,1. 工作指針p初始化； 2. 查找第i-1個結點并使工作指針p指向該結點； 3. 若查找不成功，則插入位置不合理，拋出插入位置異常； 否則， 3.1 生成一個元素值為x的新結點s； 3.2 將新結點s插入到結點p之后；,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)插入,template void LinkList : Insert(int i, DataType x) p = first ; count = 0; /工作指針p應指向頭結點 while (p != NULL /結點s插入結點p之后 ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)插入,基本語句？時間復雜度？,單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),頭插法：將待插入結點插在頭結點的后面 。,算法描述： first=new Node; first-next=NULL;,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),頭插法：將待插入結點插在頭結點的后面 。,2.3 線性表的鏈接存儲結構及實現(xiàn),算法描述： s=new Node; s-data=a0; s-next=first-next; first-next=s;,插入第一個元素結點,first,單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),頭插法：將待插入結點插在頭結點的后面 。,2.3 線性表的鏈接存儲結構及實現(xiàn),算法描述： s=new Node; s-data=a1; s-next=first-next; first-next=s;,依次插入每一個結點,template LinkList : LinkList(DataType a , int n) first = new Node; first-next = NULL; for (i = 0; i data = ai; s-next = first-next; first-next = s; ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),尾插法：將待插入結點插在終端結點的后面。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),算法描述： first=new Node; rear=first;,尾插法：將待插入結點插在終端結點的后面。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),算法描述： s=new Node; s-data=a0; rear-next=s; rear=s;,插入第一個元素結點,尾插法：將待插入結點插在終端結點的后面。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),算法描述： s=new Node; s-data=a1; rear-next=s; rear=s;,依次插入每一個結點,35,尾插法：將待插入結點插在終端結點的后面。,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),操作接口：LinkList(DataType a , int n),算法描述： rear-next=NULL;,最后一個結點插入后,35,template LinkList : LinkList(DataType a , int n) first = new Node; /生成頭結點 r = first; /尾指針初始化 for (i = 0; i data = ai; r-next = s; r = s; r-next = NULL; ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)構造函數(shù),算法描述：,單鏈表的實現(xiàn)刪除,操作接口： DataType Delete(int i);,2.3 線性表的鏈接存儲結構及實現(xiàn),如何實現(xiàn)結點ai-1和ai之間邏輯關系的變化？,算法描述： q=p-next; x=q-data; p-next=q-next; delete q;,單鏈表的實現(xiàn)刪除,2.3 線性表的鏈接存儲結構及實現(xiàn),算法描述： q=p-next; x=q-data; p-next=q-next; delete q;,注意分析邊界情況表頭、表尾。,表尾的特殊情況： 雖然被刪結點不存在，但其前驅結點卻存在。,p-next=NULL,算法描述偽代碼,1.工作指針p初始化； 2. 查找第i-1個結點并使工作指針p指向該結點； 3. 若p不存在或p不存在后繼結點，則拋出位置異常； 否則， 3.1 暫存被刪結點和被刪元素值； 3.2 摘鏈，將結點p的后繼結點從鏈表上摘下； 3.3 釋放被刪結點； 3.4 返回被刪元素值；,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)刪除,template DataType LinkList : Delete(int i) p = first ; count = 0; while (p != NULL ,2.3 線性表的鏈接存儲結構及實現(xiàn),單鏈表的實現(xiàn)刪除,單鏈表的實現(xiàn)析構函數(shù),析構函數(shù)將單鏈表中所有結點的存儲空間釋放。,2.3 線性表的鏈接存儲結構及實現(xiàn),操作接口：LinkList( );,first,a1,a2,an,ai,算法描述： q = first; first = first-next; delete q;,注意：保證鏈表未處理的部分不斷開,單鏈表的實現(xiàn)析構函數(shù),template LinkList : LinkList( ) while (first != NULL) q = first; first = first-next; delete q; ,2.3 線性表的鏈接存儲結構及實現(xiàn),算法描述：,啟示：算法設計的一般過程,算法設計的一般步驟： 第一步：確定入口（已知條件）、出口（結果）； 第二步：根據一個小實例畫出示意圖； 第三步： 正向思維：選定一個思考問題的起點，逐步提出問題、解決問題； 逆向思維：從結論出發(fā)分析為達到這個結論應該先有什么； 正逆結合； 第四步：寫出頂層較抽象算法，分析邊界情況； 第五步：驗證第四步的算法； 第六步：寫出具體算法； 第七步：進一步驗證，手工運行。,循環(huán)鏈表,first,a1,ai-1,an,ai,從單鏈表中某結點p出發(fā)如何找到其前驅？,將單鏈表的首尾相接，將終端結點的指針域由空指針改為指向頭結點，構成單循環(huán)鏈表，簡稱循環(huán)鏈表。,2.3 線性表的鏈接存儲結構及實現(xiàn),循環(huán)鏈表,2.3 線性表的鏈接存儲結構及實現(xiàn),first,a1,ai-1,an,ai,循環(huán)鏈表插入,算法描述： s=new Node; s-data=x; s-next=p-next; p-next=s;,2.3 線性表的鏈接存儲結構及實現(xiàn),template void LinkList :Insert(int i, DataType x) p = first ; count = 0; while (p != first ,循環(huán)鏈表插入,與單鏈表的插入操作相比，差別是什么？,2.3 線性表的鏈接存儲結構及實現(xiàn),循環(huán)條件： p != NULLp != first p-next != NULLp-next != first,循環(huán)鏈表,2.3 線性表的鏈接存儲結構及實現(xiàn),如何查找開始結點和終端結點？,循環(huán)鏈表,開始結點：first-next 終端結點：將單鏈表掃描一遍，時間為O(n),2.3 線性表的鏈接存儲結構及實現(xiàn),開始結點：rear-next-next 終端結點：rear,循環(huán)鏈表,帶尾指針的循環(huán)鏈表,一個存儲結構設計得是否合理，取決于基于該存儲結構的運算是否方便，時間性能是否提高。,2.3 線性表的鏈接存儲結構及實現(xiàn),雙鏈表,如何求結點p的直接前驅，時間性能？,為什么可以快速求得結點p的后繼？,如何快速求得結點p的前驅？,2.3 線性表的鏈接存儲結構及實現(xiàn),雙鏈表：在單鏈表的每個結點中再設置一個指向其前驅結點的指針域。,雙鏈表,結點結構：,data：數(shù)據域，存儲數(shù)據元素； prior：指針域，存儲該結點的前趨結點地址； next：指針域，存儲該結點的后繼結點地址。,2.3 線性表的鏈接存儲結構及實現(xiàn),template struct DulNode DataType data; DulNode *prior, *next; ;,雙鏈表,啟示？,時空權衡空間換取時間,定義結點結構：,2.3 線性表的鏈接存儲結構及實現(xiàn),雙鏈表的操作插入,s-prior=p;,s-next=p-next;,p-next-prior=s;,p-next=s;,ai-1,ai,操作接口： void Insert(DulNode *p, DataType x);,注意指針修改的相對順序,2.3 線性表的鏈接存儲結構及實現(xiàn),雙鏈表的操作刪除,(p-prior)-next=p-next;,(p-next)-prior=p-prior;,操作接口： DataType Delete(DulNode *p);,ai-1,ai,ai,結點p的指針是否需要修改？,delete p;,2.3 線性表的鏈接存儲結構及實現(xiàn),存儲分配方式比較,順序表采用順序存儲結構，即用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據元素，數(shù)據元素之間的邏輯關系通過存儲位置來實現(xiàn)。 鏈表采用鏈接存儲結構，即用一組任意的存儲單元存放線性表的元素，用指針來反映數(shù)據元素之間的邏輯關系。,2.4 順序表和鏈表的比較,2.4 順序表和鏈表的比較,時間性能比較,時間性能是指實現(xiàn)基于某種存儲結構的基本操作（即算法）的時間復雜度。,按位查找： 順序表的時間為(1)，是隨機存??； 鏈表的時間為(n)，是順序存取。 插入和刪除： 順序表需移動表長一半的元素，時間為(n)； 鏈表不需要移動元素，在給出某個合適位置的指針后，插入和刪除操作所需的時間僅為(1)。,2.4 順序表和鏈表的比較,空間性能比較,空間性能是指某種存儲結構所占用的存儲空間的大小。,定義結點的存儲密度：,結點的存儲密度： 順序表：結點的存儲密度為1（只存儲數(shù)據元素），沒有浪費空間； 鏈表：結點的存儲密度1（包括數(shù)據域和指針域），有指針的結構性開銷。,2.4 順序表和鏈表的比較,空間性能比較,空間性能是指某種存儲結構所占用的存儲空間的大小。,定義結點的存儲密度：,結構的存儲密度： 順序表：需要預分配存儲空間，如果預分配得過大，造成浪費，若估計得過小，又將發(fā)生上溢； 鏈表：不需要預分配空間，只要有內存空間可以分配，單鏈表中的元素個數(shù)就沒有限制。,結論,若線性表需頻繁查找卻很少進行插入和刪除操作，或其操作和元素在表中的位置密切相關時，宜采用順序表作為存儲結構；若線性表需頻繁插入和刪除時，則宜采用鏈表做存儲結構。 當線性表中元素個數(shù)變化較大或者未知時，最好使用鏈表實現(xiàn)；而如果用戶事先知道線性表的大致長度，使用順序表的空間效率會更高。,2.4 順序表和鏈表的比較,總之，線性表的順序實現(xiàn)和鏈表實現(xiàn)各有其優(yōu)缺點，不能籠統(tǒng)地說哪種實現(xiàn)更好，只能根據實際問題的具體需要，并對各方面的優(yōu)缺點加以綜合平衡，才能最終選定比較適宜的實現(xiàn)方法。,靜態(tài)鏈表：用數(shù)組來表示單鏈表，用數(shù)組元素的下標來模擬單鏈表的指針。,靜態(tài)鏈表,2.5 線性表的其它存儲方法,data：存儲放數(shù)據元素； next：也稱游標，存儲該元素的后繼在數(shù)組的下標。,數(shù)組元素（結點）的構成：,數(shù)據域,指針域,例：線性表(張，王，李，趙，吳)的靜態(tài)鏈表存儲,0 1 2 3 4 5 6 7 8,2.5 線性表的其它存儲方法,data next,靜態(tài)鏈表,first,avail,first：靜態(tài)鏈表頭指針，為了方便插入和刪除操作，通常靜態(tài)鏈表帶頭結點； avail：空閑鏈表頭指針，空閑鏈表由于只在表頭操作，所以不帶頭結點；,2.5 線性表的其它存儲方法,靜態(tài)鏈表,靜態(tài)鏈表的存儲結構定義如下： const int MaxSize = 100; /100只是示例數(shù)據 template struct SNode DataType data; / DataType表示不確定的數(shù)據類型 int next; /指針域（也稱游標） SListMaxSize;,在線性表(張，王，李，趙，吳)中“王”之后插入“孫”,0 1 2 3 4 5 6 7 8,2.5 線性表的其它存儲方法,data next,靜態(tài)鏈表,2.5 線性表的其它存儲方法,靜態(tài)鏈表,假