第三講線性表的定義及順序表.ppt

1、第三講 線性表及順序存儲結構,本講主要內(nèi)容： 一、線性表的定義及邏輯結構 二、線性表的順序存儲結構 三、順序表的實現(xiàn),一、線性表的定義及邏輯結構,學生成績登記表,姓 名,英語,數(shù)據(jù)結構,高數(shù),學號,丁一,96,78,87,0101,李二,87,90,78,0102,張三,67,86,86,0103,孫紅,69,81,96,0104,王冬,87,74,66,0105,職工工資登記表,姓 名,崗位津貼,基本工資,獎金,職工號,丁一,600,278,200,0101,李二,300,190,100,0102,張三,300,186,100,0103,孫紅,500,218,200,0104,王冬,300,

2、190,100,0105,數(shù)據(jù)元素之間的關系是什么？,線性表：簡稱表，是n（n0）個具有相同類型的數(shù)據(jù)元素的有限序列。 線性表的長度：線性表中數(shù)據(jù)元素的個數(shù),一般用n表示, n0 。 空表：長度等于零的線性表，即n=0,記為：L=( )。,線性表的定義,非空表記為：L（a1, a2 , , ai-1, ai , , an),ai（1in）稱為數(shù)據(jù)元素； 下角標 i 表示該元素在線性表中的位置或序號 。 a1是表中第一個元素,稱為表頭元素; a2是表中第二個元素; an是最后一個元素,稱為表尾元素; 線性表中各元素在位置上是有序的,這種有序就稱為線性關系.,線性表的定義,例如： L1=( )：L

3、1是一個空的線性表； L2=(a,b,c,d,e)：L2線性表中有5個元素，其長度為5。a是表頭元素、e是表尾元素。c的直接前驅元素是b，c的直接后繼元素是d。a元素的序號是1，c元素的序號是3。,線性表的定義,線性表（a1, a2 , , ai-1, ai , , an)的圖形表示如下：,線性表的圖形表示,元素ai 和ai+1之間的先后關系用表示.,線性表（a1, a2 , , ai-1, ai , , an)的二元組表示如下：,線性表的二元組表示,線性表L=(D,R),其中 D=ai | 1in,n0, ai 屬于ElemType類型 R=r R=|1in-1 注意:ElemType類型是

4、C+的類型標識符,代表某種類型.,1.有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。,2.相同性：線性表中數(shù)據(jù)元素的類型是同一的。,3.順序性：線性表中相鄰的數(shù)據(jù)元素ai-1和ai之間存在序偶關系，即ai-1是ai的前驅， ai是ai-1的后繼；a1 無前驅，an無后繼，其它每個元素有且僅有一個前驅和一個后繼。,線性表的特性,線性表的抽象數(shù)據(jù)類型定義,ADT List 數(shù)據(jù)對象: D=ai | 1in,n0, ai 屬于ElemType類型 /ElemType是C+的類型標識符 數(shù)據(jù)關系: R=|ai,ai+1D,i=1,n-1,線性表的抽象數(shù)據(jù)類型定義,基本運算: InitList (/取得線性表

5、LA的長度 for(i=1;i=ListLength(LB);i+) GetElem(LB,i,e);/取LB中第i個數(shù)據(jù)元素，賦給e if(!LocateElem(LA,e) ListInsert(LC,+lena,e); /若LA中不存在和e相同者，則插入到LC中 算法的時間復雜度為O(n2),二、線性表的順序存儲結構,線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,線性表的順序存儲結構： 將線性表的結點按邏輯次序依次存放在一組地址連續(xù)的存儲單元內(nèi)。采用順序存儲結構的線性表又稱為順序表。 順序表的虛擬存儲是采用程序設計語言的一維數(shù)組來存儲線性表。 順序表的元素依次存儲在一段連續(xù)的空

6、間內(nèi)，邏輯上相鄰的元素在存儲位置上也相鄰。,線性表的順序存儲結構及實現(xiàn),線性表的順序存儲結構示意圖：(假設線性表L的起始存儲位置為LOC(A) ）,提示：用LOC(ai)表示線性表元素ai的存儲空間的起始地址，若L表示一個元素的長度(L=sizeof(ElemType)，則對于正整數(shù)i有： LOC(ai+1)= LOC(ai)+ L若線性表的起始地址是b，則：LOC(ai)=b+(i-1)*L 或者 LOC(ai)= LOC(a1)+(i-1)*L 整個線性表占用的空間大小是:n*L，n是線性表的長度,線性表的順序存儲結構及實現(xiàn),順序表的類型定義 #define MaxSize 50 type

7、def struct ElemType dataMaxSize; int length; SqList; ElemType表示線性表元素的抽象數(shù)據(jù)類型，用程序設計語言上機實現(xiàn)算法時，再定義為具體的數(shù)據(jù)類型。 MaxSize表示線性表最多允許的元素個數(shù)。 length表示線性表的當前長度。其值是0至MaxSize間的一個整數(shù)。,線性表的順序存儲結構及實現(xiàn),線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,例：（34, 23, 67, 43）,34,23,67,43,4,線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,例：（34, 23, 67, 43）,34,23,67,43,4,

8、用什么屬性來描述順序表？,線性表的順序存儲結構及實現(xiàn),順序表線性表的順序存儲結構,例：（34, 23, 67, 43）,34,23,67,43,4,如何實現(xiàn)順序表的內(nèi)存分配？,如何求得任意元素的存儲地址？,0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空閑,長度,線性表的順序存儲結構及實現(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)時間內(nèi)存取數(shù)據(jù)元素,線性表的順序存儲結構及實現(xiàn),順序

9、表,一般情況下，(a1，a2，, ai-1，ai , , an)的順序存儲：,線性表的順序存儲結構及實現(xiàn),存儲結構是數(shù)據(jù)及其邏輯結構在計算機中的表示； 存取結構是在一個數(shù)據(jù)結構上對查找操作的時間性能的一種描述。,存儲結構和存取結構,“順序表是一種隨機存取的存儲結構”的含義為：在順序表這種存儲結構上進行的查找操作，其時間性能為O(1)。,線性表的順序存儲結構及實現(xiàn),如果線性表采用如下存儲結構， #define MaxSize 50 typedef struct ElemType dataMaxSize; int length; SqList; 在此基礎上實現(xiàn)線性表的相關運算如下：,線性表的順序存

10、儲結構及實現(xiàn),1.建立順序表 void CreateList ( Sqlist * ,線性表的順序存儲結構及實現(xiàn),2順序表基本運算算法 （1）初始化線性表 void InitList ( SqList * 時間復雜度為O(1),線性表的順序存儲結構及實現(xiàn),（2）銷毀線性表 void DestroyList ( SqList * 時間復雜度為O(1),線性表的順序存儲結構及實現(xiàn),（3）判斷線性表是否為空 int ListEmpty ( SqList *L) Return(L-Length=0); 時間復雜度為O(1),線性表的順序存儲結構及實現(xiàn),（4）求線性表的長度 int ListLength

11、 ( SqList *L) Return(L-length); 時間復雜度為O(1),線性表的順序存儲結構及實現(xiàn),（5）輸出線性表 void DispList ( Sqlist *L) int I; if ( ListEmpty(L) ) return; for (i=0; ilength; i+) printf (“%c”, L-datai ); printf(“n”); 時間復雜度為O(L-length),線性表的順序存儲結構及實現(xiàn),（6）求線性表中某個數(shù)據(jù)元素值 int GetElem ( Sqlist *L, int I , ElemType 時間復雜度為 O(1),線性表的順序存儲結

12、構及實現(xiàn),（7）按元素值查找 Int LocateElem ( Sqlist *L, ElemType e) int i=0; while(ilength 時間復雜度為O(L-length),線性表的順序存儲結構及實現(xiàn),（8）插入數(shù)據(jù)元素 int ListInsert ( SqList * 時間復雜度為O(n),線性表的順序存儲結構及實現(xiàn),（9）刪除數(shù)據(jù)元素 int ListDelete (Sqlist * 時間復雜度為 O(n),順序表類的聲明,const int MaxSize=100; template /模板類 class SeqList public: SeqList( ) ; /默

13、認構造函數(shù) SeqList(T a , int n); /帶參數(shù)的構造函數(shù) SeqList( ) ; /析構函數(shù) int ListLength( ); /求線性表長度 T GetElem(int i); /求線性表中第i個元素的值 int LocateElem(T x ); /按元素查找 void ListInsert(int i, T x); /插入新的數(shù)據(jù)元素 T ListDelete(int i); /刪除數(shù)據(jù)元素,用類來實現(xiàn)順序表,順序表類的聲明,private: T dataMaxSize; int length; ;,用類來實現(xiàn)順序表,操作接口：SeqList( ),算法描述： S

14、eqList:SeqList( ) length=0; ,順序表的實現(xiàn)無參構造函數(shù),0,用類來實現(xiàn)順序表,操作接口：SeqList(T a , int n),順序表的實現(xiàn)有參構造函數(shù),5,35,12,24,33,42,用類來實現(xiàn)順序表,template SeqList:SeqList(T a , int n) if (nMaxSize) throw 參數(shù)非法; for (i=0; in; i+ +) datai=ai; length=n; ,順序表的實現(xiàn)有參構造函數(shù),算法描述：,用類來實現(xiàn)順序表,操作接口： void ListInsert(int i, T x) 插入前：(a1, , ai-1

15、, ai, , an) 插入后：(a1, , ai-1, x , ai, , an),順序表的實現(xiàn)插入,ai-1和ai之間的邏輯關系發(fā)生了變化,順序存儲要求存儲位置反映邏輯關系,存儲位置要反映這個變化,用類來實現(xiàn)順序表,例：（35，12，24，42），在i=2的位置上插入33。,表滿：length=MaxSize 合理的插入位置：1ilength+1（i指的是元素的序號）,順序表的實現(xiàn)插入,4,35,12,24,42,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,什么時候不能插入？,用類來實現(xiàn)順序表,1. 如果表滿了，則拋出上溢異常; 2. 如果元素的插入位置不合理，則拋

16、出位置異常; 3. 將最后一個元素至第i個元素分別向后移動一個位置； 4. 將元素x填入位置i處； 5. 表長加1；,算法描述偽代碼,順序表的實現(xiàn)插入數(shù)據(jù),用類來實現(xiàn)順序表,template void SeqList:ListInsert(int i, T x) if (length=MaxSize) throw 上溢; if (ilength+1) throw 位置; for (j=length; j=i; j-) dataj=dataj-1; datai-1=x; length+; ,算法描述C+描述,順序表的實現(xiàn)插入數(shù)據(jù),基本語句？,用類來實現(xiàn)順序表,最好情況（ i=n+1）： 基本語句

17、執(zhí)行0次，時間復雜度為O(1)。 最壞情況（ i=1）： 基本語句執(zhí)行n+1次，時間復雜度為O(n)。 平均情況（1in+1）： 時間復雜度為O(n)。,時間性能分析,順序表的實現(xiàn)插入,用類來實現(xiàn)順序表,操作接口： T ListDelete(int i) 刪除前：(a1, , ai-1,ai,ai+1,an) 刪除后：(a1,ai-1,ai+1, ,an),順序表的實現(xiàn)刪 除,ai-1和ai之間的邏輯關系發(fā)生了變化,順序存儲要求存儲位置反映邏輯關系,存儲位置要反映這個變化,用類來實現(xiàn)順序表,例：（35, 33, 12, 24, 42），刪除i=2的數(shù)據(jù)元素。,仿照順序表的插入操作，完成： 1.

18、 分析邊界條件； 2. 分別給出偽代碼和C+描述的算法； 3. 分析時間復雜度。,順序表的實現(xiàn)刪 除,5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,12,24,42,用類來實現(xiàn)順序表,順序表的實現(xiàn)按位查找,操作接口： T GetElem(int i),0 i-2 i-1 n-1 Max-1,a1,ai-1,ai,an,空閑,n,算法描述： template T SeqList:Get( int i ) if (i=1 ,時間復雜度？,用類來實現(xiàn)順序表,順序表的實現(xiàn)按值查找,操作接口： int LocateElem(T x ),5,35,a1,a2,a3,a4,0 1 2 3 4,42,24,12,33,a5,例：在（35, 33, 12, 24, 42） 中查找值為12的