第四講 順序表

1、第四講 順序表 本講主要內容：本講主要內容： 一、線性表的順序存儲結構一、線性表的順序存儲結構 二、順序表的實現(xiàn)二、順序表的實現(xiàn) 線性表的順序存儲結構及實現(xiàn) 順序表順序表線性表的順序存儲結構線性表的順序存儲結構 線性表的順序存儲結構：線性表的順序存儲結構： 將線性表的結點按邏輯次序依次存放在一組地址將線性表的結點按邏輯次序依次存放在一組地址 連續(xù)的存儲單元內。連續(xù)的存儲單元內。采用順序存儲結構的線性表采用順序存儲結構的線性表 又稱為順序表。又稱為順序表。 順序表的虛擬存儲是采用程序設計語言的一維數(shù)順序表的虛擬存儲是采用程序設計語言的一維數(shù) 組來存儲線性表。組來存儲線性表。 順序表的元素依次存儲

2、在一段連續(xù)的空間內，邏順序表的元素依次存儲在一段連續(xù)的空間內，邏 輯上相鄰的元素在存儲位置上也相鄰。輯上相鄰的元素在存儲位置上也相鄰。 線性表的順序存儲結構及實現(xiàn) 線性表的順序存儲結構示意圖：線性表的順序存儲結構示意圖：( (假設線性表假設線性表L L的起始存儲位置為的起始存儲位置為 LOC(A) LOC(A) ） 下標位置線性表存儲空間存儲地址 0a1 LOC(A) 1a2 LOC(A)+sizeof(ElemType) i-1ai LOC(A)+(i-1)*sizeof(ElemType) n-1an LOC(A)+(n-1)*sizeof(ElemType) Maxsize-1 LOC(

3、A)+(MaxSize-1)*sizeof(ElemType) 提示：用提示：用LOC(aLOC(ai i) )表示線性表元素表示線性表元素a ai i的存儲空間的的存儲空間的 起始地址，若起始地址，若L L表示一個元素的長度表示一個元素的長度 (L=sizeof(ElemType)(L=sizeof(ElemType)，則對于正整數(shù)，則對于正整數(shù)i i有：有： LOC(aLOC(ai+1 i+1)= LOC(a )= LOC(ai i)+ L)+ L 若線性表的起始地址是若線性表的起始地址是b b，則：，則： LOC(aLOC(ai i)=b+(i-1)=b+(i-1)* *L L 或者或者

4、 LOC(aLOC(ai i)= LOC(a)= LOC(a1 1)+(i-1)+(i-1)* *L L 整個線性表占用的空間大小是整個線性表占用的空間大小是:n:n* *L L，n n是線性表的是線性表的 長度長度 線性表的順序存儲結構及實現(xiàn) 線性表的順序存儲結構及實現(xiàn) 順序表順序表線性表的順序存儲結構線性表的順序存儲結構 例：（例：（34, 23, 67, 43） 34236743 4 存儲要點存儲要點 用一段地址用一段地址連續(xù)連續(xù)的存儲單元的存儲單元 依次依次存儲線性表中的數(shù)據(jù)元素存儲線性表中的數(shù)據(jù)元素 線性表的順序存儲結構及實現(xiàn) 順序表順序表線性表的順序存儲結構線性表的順序存儲結構 例

5、：（例：（34, 23, 67, 43） 34236743 存儲空間的起始位置存儲空間的起始位置 4 用什么屬性來描述順序表？用什么屬性來描述順序表？ 順序表的容量（最大長度）順序表的容量（最大長度） 順序表的當前長度順序表的當前長度 線性表的順序存儲結構及實現(xiàn) 順序表順序表線性表的順序存儲結構線性表的順序存儲結構 例：（例：（34, 23, 67, 43） 34236743 4 如何實現(xiàn)順序表的內存分配？如何實現(xiàn)順序表的內存分配？ 順序表順序表一維數(shù)組一維數(shù)組 如何求得任意元素的存儲地址？如何求得任意元素的存儲地址？ 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空

6、閑 長度長度 線性表的順序存儲結構及實現(xiàn) 順序表順序表 一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：的順序存儲： c Loc(ai) Loc(a1) 0 i-2 i-1 n-1 Max-1 a1 ai-1 ai an 空閑空閑 長度長度 Loc(ai)=Loc(a1) + (i - -1)c 隨機存取隨機存?。涸谠贠(1)時間內存取數(shù)據(jù)元素時間內存取數(shù)據(jù)元素 線性表的順序存儲結構及實現(xiàn) 順序表順序表 一般情況下，一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：的順序存儲： c Loc(ai) Loc(a1) 線性表的順序存儲結構及

7、實現(xiàn) 存儲結構是數(shù)據(jù)及其邏輯結構在計算機中的表示；存儲結構是數(shù)據(jù)及其邏輯結構在計算機中的表示； 存取結構是在一個數(shù)據(jù)結構上對查找操作的時間性存取結構是在一個數(shù)據(jù)結構上對查找操作的時間性 能的一種描述。能的一種描述。 存儲結構和存取結構存儲結構和存取結構 “順序表是一種順序表是一種隨機存取隨機存取的的存儲存儲結構結構”的含義為：的含義為： 在順序表這種存儲結構上進行的查找操作，其時間在順序表這種存儲結構上進行的查找操作，其時間 性能為性能為O(1)。 #include #define maxsize 50 /定義線性表的最大長度定義線性表的最大長度 typedef int ElemType; /

8、定義線性表中數(shù)據(jù)元素的類型定義線性表中數(shù)據(jù)元素的類型 class SqList private: ElemType datamaxsize; /存放線性表的數(shù)據(jù)元素的值存放線性表的數(shù)據(jù)元素的值 int length;/存放線性表的長度存放線性表的長度 public: SqList() /構造函數(shù)構造函數(shù) SqList() /析構函數(shù)析構函數(shù) /初始化線性表，即創(chuàng)建空的線性表初始化線性表，即創(chuàng)建空的線性表 void InitList(); 用類來實現(xiàn)順序表 /建立非空線性表，線性表的數(shù)據(jù)元素的值由數(shù)組a給出 void CreateList(ElemType a,int n); /判斷線性表是否為

9、空 int ListEmpty(); /求線性表的長度 int ListLength(); /顯示線性表中所有元素的值 void DispList(); 用類來實現(xiàn)順序表 /取得線性表中指定位序的元素值 int GetElem(int i,ElemType /查找線性表中第一個值與給定參數(shù)e相同的元素的位序 int LocateElem(ElemType e); /在線性表中指定位序上插入新的數(shù)據(jù)元素e int ListInsert(int i,ElemType e); /刪除線性表中指定位序上的元素 int ListDelete(int i,ElemType ; 用類來實現(xiàn)順序表 操作接口：

10、操作接口：SqList( ) ( ) 算法描述：算法描述： SqList:SqList( ) length=0; /將線性表的長度設置為將線性表的長度設置為0 1、順序表的實現(xiàn)無參構造函數(shù) data length 0 用類來實現(xiàn)順序表 操作接口：操作接口：SqList(ElemType a,int n)(ElemType a,int n) 2、順序表的實現(xiàn)有參構造函數(shù) 順序表順序表 數(shù)組數(shù)組a 3512243342 5 3512243342 用類來實現(xiàn)順序表 /建立非空線性表，線性表的數(shù)據(jù)元素的值由數(shù)組建立非空線性表，線性表的數(shù)據(jù)元素的值由數(shù)組a給給 出出 void SqList(ElemTy

11、pe a ,int n) int i; for(i=0;in;i+) datai=ai; /將給定數(shù)組的值賦給線性表將給定數(shù)組的值賦給線性表 length=n; /由給定參數(shù)設置線性表長度由給定參數(shù)設置線性表長度 /for(i=0;in;i+) /coutdatai=MaxSize 合理的插入位置：合理的插入位置：1ilength+1（i指的是元素的序號）指的是元素的序號） 順序表的實現(xiàn)插入 4 35122442 a1a2a3a4 0 1 2 3 4 422412335 什么時候不能插入什么時候不能插入？注意邊界條件注意邊界條件 用類來實現(xiàn)順序表 /在線性表中指定位序上插入新的數(shù)據(jù)元素在線性表

12、中指定位序上插入新的數(shù)據(jù)元素e int ListInsert(int i,ElemType e) int j; if(ilength+1) return 0; /指定的位序不合法，操作指定的位序不合法，操作 失敗，返回失敗，返回0 i-; for(j=length;ji;j-) dataj=dataj-1; /將插入位置后的所有元素逐個將插入位置后的所有元素逐個 向后移動，空出要插入的位置向后移動，空出要插入的位置 datai=e; /將給定值寫入空出的單元將給定值寫入空出的單元 length+; /線性表長度加線性表長度加1 return 1; /操作成功，返回操作成功，返回1 用類來實現(xiàn)順

13、序表 最好最好情況（情況（ i=n+1）：）： 基本語句執(zhí)行基本語句執(zhí)行0次，時間復雜度為次，時間復雜度為O(1)。 最壞最壞情況（情況（ i=1）：）： 基本語句執(zhí)行基本語句執(zhí)行n+1次，時間復雜度為次，時間復雜度為O(n)。 平均平均情況（情況（1in+1）：）： 時間復雜度為時間復雜度為O(n)。 時間性能分析時間性能分析 順序表的實現(xiàn)插入 + +- - + + = = 1 1 )=1( n i i inp + +- - + + + + = = 1 1 )=1( 1 1 n i in n 2 n =O(n) 用類來實現(xiàn)順序表 操作接口：操作接口： int ListDelete(int i

14、,ElemType if(ilength) return 0; /位序不合法，操作失敗，返回位序不合法，操作失敗，返回0 i-; e=datai; /用變量用變量e保存要刪除的元素保存要刪除的元素 for(j=i;jlength-i;j+) dataj=dataj+1; /將刪除位置后的所有元素逐個向前移動，覆蓋要刪除的數(shù)據(jù)將刪除位置后的所有元素逐個向前移動，覆蓋要刪除的數(shù)據(jù) length-; /長度減長度減1 return 1; /操作成功，返回操作成功，返回1 5、順序表的實現(xiàn)、順序表的實現(xiàn)按位查找按位查找 操作接口：操作接口： int GetElem(int i,ElemType /指定

15、的的位序參數(shù)i不合法，操作失敗，返回0 e=datai-1; /取得指定位序的元素值 return 1; /操作成功，返回1 用類來實現(xiàn)順序表 6、順序表的實現(xiàn)、順序表的實現(xiàn)按值查找按值查找 操作接口：操作接口： int LocateElem(ElemType e) 5 35 a1a2a3a4 0 1 2 3 4 42241233 a5 例：在（例：在（35, 33, 12, 24, 42） 中查找值為中查找值為12的元素，的元素， 返回在表中的序號。返回在表中的序號。 iii 注意序號和下標之間的關系注意序號和下標之間的關系 用類來實現(xiàn)順序表 /查找線性表中第一個值與給定參數(shù)查找線性表中第一

16、個值與給定參數(shù)e相同的元素的位序相同的元素的位序 int LocateElem(ElemType e) int i=0; while(i=length) /如果位序超出有效范圍，表示未在線性表中找到與給定參數(shù)如果位序超出有效范圍，表示未在線性表中找到與給定參數(shù)e相同的元素，相同的元素， return 0; /操作失敗，返回操作失敗，返回0 else return i+1; /否則返回該元素的邏輯位序否則返回該元素的邏輯位序 順序表的實現(xiàn)順序表的實現(xiàn)按值查找按值查找 算法描述：算法描述： 用類來實現(xiàn)順序表 /判斷線性表是否為空判斷線性表是否為空 int ListEmpty() if(length

17、=0) return 1; /若線性表長度為若線性表長度為0，則為空表，該運算返回真值，則為空表，該運算返回真值 else return 0;/否則該表非空，返否則該表非空，返 回假值回假值 7、順序表的實現(xiàn)、順序表的實現(xiàn)判斷線性表是否為空判斷線性表是否為空 算法描述：算法描述： 用類來實現(xiàn)順序表 8、順序表的實現(xiàn)、順序表的實現(xiàn)求線性表長度求線性表長度 算法描述：算法描述： 用類來實現(xiàn)順序表 /求線性表的長度 int ListLength() return length; /返回線性表的長度 /顯示線性表中所有元素的值 void DispList() int i; if(length=0) return; /若為空表，不需要執(zhí)行下面的操 作，直接返回 for(i=0;ilength;i+) coutdatait; /將線性表中每個元素的值輸出 coutendl; 9、順序表的實現(xiàn)、順序表的實現(xiàn)顯示線性