1第二章線性表1234567891第二章線性表12345678912本章內容2.1線性表的類型定義2.2線性表類型的實現順序映象2.3線性表類型的實現鏈式映象2本章內容2.1線性表的類型定義23順序表示及其特點3順序表示及其特點34順序表示及其特點順序映象——以x的存儲位置和y的存儲位置之間某種關系表示邏輯關系<x,y>。最簡單的一種順序映象方法是：用一組地址連續的存儲單元依次存放線性表中的數據元素。

a1a2…ai-1ai…an線性表的起始地址稱作線性表的基地址4順序表示及其特點順序映象——以x的存儲位置和y的45順序表示及其特點以“存儲位置相鄰〞表示有序對<ai-1，ai>即：LOC(ai)=LOC(ai-1)+CC是一個數據元素所占存儲量所有數據元素的存儲位置均取決于第一個數據元素的存儲位置LOC(ai)=LOC(a1)+(i-1)×C

5順序表示及其特點以“存儲位置相鄰〞表示有序對<ai-1，a5小結：順序表的特點用連續的存儲單元存放線性表的元素(采用一維數組存放)。元素存儲順序與元素的邏輯順序一致。讀寫元素方便，通過下標即可指定位置。6

a1a2…ai-1ai…an線性表的起始地址稱作線性表的基地址小結：順序表的特點用連續的存儲單元存放線性表的元素(采用一維67#defineLIST_INIT_SIZE80

//線性表存儲空間的初始分配量#defineLISTINCREMENT10

//線性表存儲空間的分配增量typedefstruct{ElemType*elem;//存儲空間基址

intlength;//當前長度

intlistsize;//當前分配的存儲容量

//(以sizeof(ElemType)為單位)}SqList;//俗稱順序表7#defineLIST_INIT_SIZE87801….i-2i-1….n-1……順序表a1a2…ai-1ai…an...L.elem+L.length－1L.elem+L.listsize－1elemlengthlistsizeL注意：由于數組的下標從“0”開始，表中第i個元素是L.elem[i-1].typedefstruct{ElemType*elem;

intlength;

intlistsize;

}SqList;//順序表SqListL;801….89順序表的初始化操作StatusInitList_Sq(SqList&L){//構造一個空的線性表

L.elem=(ElemType*)malloc

(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//InitList_Sqtypedefstruct{ElemType*elem;

intlength;

intlistsize;

}SqList;//順序表9順序表的初始化操作StatusInitList_Sq(910順序表的插入操作ListInsert(&L,i,e)

//插入元素在順序表L的第i個元素之前插入新的元素e,把e插入到第i個元素的位置

i的合法范圍為1≤i≤L.length+101….i-2i-1….n-1a1a2…ai-1ai…anee10順序表的插入操作ListInsert(&L,i,e)1011操作的過程：ListInsert(&L,6,30)341611825313416118253130341611825313416118302531341611830253111操作的過程：ListInsert(&L,6,30)1112操作的過程：ListInsert(&L,6,30)34161182531341611830253134161182531pqp34161182531pq=&(L.elem[i-1]);p=&(L.elem[L.length-1]);*(p+1)=*p;p--;34161182531p*(p+1)=*p;*q=e;p>=q;插入操作12操作的過程：ListInsert(&L,6,30)1213操作步驟判斷插入位置是否合法：1≤i≤L.length+1初始化指針循環：從表尾開場，依次將第i-1個元素之后的元素順序后移一位將新元素e寫入到第i個位置將表的長度加113操作步驟1314StatusListInsert_Sq(SqList&L,inti,ElemTypee){

if(i<1||i>L.length+1)returnERROR;//步驟1：位置不合法

q=&(L.elem[i-1]);//步驟2：q指示插入位置

for(p=&(L.elem[L.length-1]);p>=q;p--)*(p+1)=*p;//步驟3：元素依次后移*q=e;//步驟4：插入e

++L.length;//步驟5：表長加1

returnOK;}//ListInsert_Sq算法時間復雜度取決于:移動元素的次數14StatusListInsert_Sq(SqList1415插入操作的算法復雜度考慮移動元素的平均情況：假設在第i個元素之前插入的概率為pi，那么在長度為n的線性表中插入一個元素所需移動元素次數的期望值為：若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：算法時間復雜度為:O(n)15插入操作的算法復雜度考慮移動元素的平均情況：若假定在線性1516if(L.length>=L.listsize){

//當前存儲空間已滿，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);//存儲分配失敗

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲容量}如果存儲空間已滿怎么辦？16if(L.length>=L.listsize)1617程序設計方法的兩點說明先考慮一般情況，后考慮特殊情況一般不用根本操作實現其他根本操作17程序設計方法的兩點說明先考慮一般情況，后考慮特殊情況1718兩個實際問題錯誤的類型：正常處理的錯誤：是一些常見、合理的錯誤〔如：用戶輸入的錯誤〕，通過錯誤代碼返回。意外錯誤：拋出Exception，通過try－catch撲捉。初始化問題：數據構造沒有初始化就使用往往也是錯誤，但無法判定。在C++和Java中通過構造函數解決。18兩個實際問題錯誤的類型：1819順序表的刪除操作ListDelete(&L,i,&e)//刪除元素刪除線性表中第i個元素，并將刪除的元素方在e中i的合法范圍為1≤i≤L.length刪除操作19順序表的刪除操作ListDelete(&L,i,&e1920操作的過程：ListDelete(&L,5,&e)34161253134161253134161182531pp341612531pp=&(L.elem[i-1]);*e=*p;p++;341612531p*(p-1)=*p;p>=L.elem+L.length-1;pp++;341612531p*(p-1)=*p;20操作的過程：ListDelete(&L,5,&e2021操作步驟判斷插入位置是否合法：1≤i≤L.length初始化指針將第i個元素的值賦給變量e循環：從第i+1個元素開場，依次將后面的元素順序前移一位將表的長度減121操作步驟2122StatusListDelete_Sq(SqList&L,inti,ElemType&e){

//步驟1：位置是否合法

if((i<1)||(i>L.length))returnERROR;

p=&(L.elem[i-1]);//步驟2：初始化指針

e=*p;//步驟3:賦給eq=L.elem+L.length-1;//表尾的位置

for(++p;p<=q;++p)*(p-1)=*p;//步驟4：被刪除元素之后的元素左移

--L.length;//步驟5：表長減1returnOK;}//ListDelete_Sq算法時間復雜度取決于:移動元素的次數22StatusListDelete_Sq算法時間復雜度取2223刪除操作的算法復雜度考慮移動元素的平均情況：假設在刪除第i個元素的概率為pi，那么在長度為n的線性表中刪除一個元素所需移動元素次數的期望值為：若假定在線性表中任何一個位置上進行刪除的概率都是相等的，則移動元素的期望值為：算法時間復雜度為:O(n)23刪除操作的算法復雜度考慮移動元素的平均情況：若假定在線性2324LocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p基本操作：將順序表中的元素逐個和給定值e相比較。定位操作循環結束標志：找到e或者p超過表尾的地址24LocateElem_Sq(SqListL,Elem2425定位操作請大家寫出順序表的定位操作的操作步驟和程序要求：在順序表中查詢第一個滿足判定條件的數據元素，假設存在，那么返回它的位序，否那么返回0算法時間復雜度為:O(n)25定位操作請大家寫出順序表的定位操作的算法時間復雜度為:O25小結：順序表的優缺點優點不需要附加空間隨機存取任一個元素〔根據下標〕缺點很難估計所需空間的大小開場就要分配足夠大的一片連續的內存空間更新操作代價大26小結：順序表的優缺點優點262627END27END2728第二章線性表1234567891第二章線性表1234567892829本章內容2.1線性表的類型定義2.2線性表類型的實現順序映象2.3線性表類型的實現鏈式映象2本章內容2.1線性表的類型定義2930順序表示及其特點3順序表示及其特點3031順序表示及其特點順序映象——以x的存儲位置和y的存儲位置之間某種關系表示邏輯關系<x,y>。最簡單的一種順序映象方法是：用一組地址連續的存儲單元依次存放線性表中的數據元素。

a1a2…ai-1ai…an線性表的起始地址稱作線性表的基地址4順序表示及其特點順序映象——以x的存儲位置和y的3132順序表示及其特點以“存儲位置相鄰〞表示有序對<ai-1，ai>即：LOC(ai)=LOC(ai-1)+CC是一個數據元素所占存儲量所有數據元素的存儲位置均取決于第一個數據元素的存儲位置LOC(ai)=LOC(a1)+(i-1)×C

5順序表示及其特點以“存儲位置相鄰〞表示有序對<ai-1，a32小結：順序表的特點用連續的存儲單元存放線性表的元素(采用一維數組存放)。元素存儲順序與元素的邏輯順序一致。讀寫元素方便，通過下標即可指定位置。33

a1a2…ai-1ai…an線性表的起始地址稱作線性表的基地址小結：順序表的特點用連續的存儲單元存放線性表的元素(采用一維3334#defineLIST_INIT_SIZE80

//線性表存儲空間的初始分配量#defineLISTINCREMENT10

//線性表存儲空間的分配增量typedefstruct{ElemType*elem;//存儲空間基址

intlength;//當前長度

intlistsize;//當前分配的存儲容量

//(以sizeof(ElemType)為單位)}SqList;//俗稱順序表7#defineLIST_INIT_SIZE8343501….i-2i-1….n-1……順序表a1a2…ai-1ai…an...L.elem+L.length－1L.elem+L.listsize－1elemlengthlistsizeL注意：由于數組的下標從“0”開始，表中第i個元素是L.elem[i-1].typedefstruct{ElemType*elem;

intlength;

intlistsize;

}SqList;//順序表SqListL;801….3536順序表的初始化操作StatusInitList_Sq(SqList&L){//構造一個空的線性表

L.elem=(ElemType*)malloc

(LIST_INIT_SIZEsizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}//InitList_Sqtypedefstruct{ElemType*elem;

intlength;

intlistsize;

}SqList;//順序表9順序表的初始化操作StatusInitList_Sq(3637順序表的插入操作ListInsert(&L,i,e)

//插入元素在順序表L的第i個元素之前插入新的元素e,把e插入到第i個元素的位置

i的合法范圍為1≤i≤L.length+101….i-2i-1….n-1a1a2…ai-1ai…anee10順序表的插入操作ListInsert(&L,i,e)3738操作的過程：ListInsert(&L,6,30)341611825313416118253130341611825313416118302531341611830253111操作的過程：ListInsert(&L,6,30)3839操作的過程：ListInsert(&L,6,30)34161182531341611830253134161182531pqp34161182531pq=&(L.elem[i-1]);p=&(L.elem[L.length-1]);*(p+1)=*p;p--;34161182531p*(p+1)=*p;*q=e;p>=q;插入操作12操作的過程：ListInsert(&L,6,30)3940操作步驟判斷插入位置是否合法：1≤i≤L.length+1初始化指針循環：從表尾開場，依次將第i-1個元素之后的元素順序后移一位將新元素e寫入到第i個位置將表的長度加113操作步驟4041StatusListInsert_Sq(SqList&L,inti,ElemTypee){

if(i<1||i>L.length+1)returnERROR;//步驟1：位置不合法

q=&(L.elem[i-1]);//步驟2：q指示插入位置

for(p=&(L.elem[L.length-1]);p>=q;p--)*(p+1)=*p;//步驟3：元素依次后移*q=e;//步驟4：插入e

++L.length;//步驟5：表長加1

returnOK;}//ListInsert_Sq算法時間復雜度取決于:移動元素的次數14StatusListInsert_Sq(SqList4142插入操作的算法復雜度考慮移動元素的平均情況：假設在第i個元素之前插入的概率為pi，那么在長度為n的線性表中插入一個元素所需移動元素次數的期望值為：若假定在線性表中任何一個位置上進行插入的概率都是相等的，則移動元素的期望值為：算法時間復雜度為:O(n)15插入操作的算法復雜度考慮移動元素的平均情況：若假定在線性4243if(L.length>=L.listsize){

//當前存儲空間已滿，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);//存儲分配失敗

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲容量}如果存儲空間已滿怎么辦？16if(L.length>=L.listsize)4344程序設計方法的兩點說明先考慮一般情況，后考慮特殊情況一般不用根本操作實現其他根本操作17程序設計方法的兩點說明先考慮一般情況，后考慮特殊情況4445兩個實際問題錯誤的類型：正常處理的錯誤：是一些常見、合理的錯誤〔如：用戶輸入的錯誤〕，通過錯誤代碼返回。意外錯誤：拋出Exception，通過try－catch撲捉。初始化問題：數據構造沒有初始化就使用往往也是錯誤，但無法判定。在C++和Java中通過構造函數解決。18兩個實際問題錯誤的類型：4546順序表的刪除操作ListDelete(&L,i,&e)//刪除元素刪除線性表中第i個元素，并將刪除的元素方在e中i的合法范圍為1≤i≤L.length刪除操作19順序表的刪除操作ListDelete(&L,i,&e4647操作的過程：ListDelete(&L,5,&e)34161253134161253134161182531pp341612531pp=&(L.elem[i-1]);*e=*p;p++;341612531p*(p-1)=*p;p>=L.elem+L.length-1;pp++;341612531p*(p-1)=*p;20操作的過程：ListDelete(&L,5,&e4748操作步驟判斷插入位置是否合法：1≤i≤L.length初始化指針將第i個元素的值賦給變量e循環：從第i+1個元素開場，依次將后面的元素順序前移一位將表的長度減121操作步驟4849StatusListDelete_Sq(SqList&L,inti,ElemType&e){