數(shù)據(jù)結(jié)構(gòu)課件線性表順序表

1第二章線性表1234567891第二章線性表12345678912本章內(nèi)容2.1線性表的類型定義2.2線性表類型的實(shí)現(xiàn)順序映象2.3線性表類型的實(shí)現(xiàn)鏈?zhǔn)接诚?本章內(nèi)容2.1線性表的類型定義23順序表示及其特點(diǎn)3順序表示及其特點(diǎn)34順序表示及其特點(diǎn)順序映象——以x的存儲(chǔ)位置和y的存儲(chǔ)位置之間某種關(guān)系表示邏輯關(guān)系<x,y>。最簡單的一種順序映象方法是：用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素。

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

5順序表示及其特點(diǎn)以“存儲(chǔ)位置相鄰〞表示有序?qū)?lt;ai-1，a5小結(jié)：順序表的特點(diǎn)用連續(xù)的存儲(chǔ)單元存放線性表的元素(采用一維數(shù)組存放)。元素存儲(chǔ)順序與元素的邏輯順序一致。讀寫元素方便，通過下標(biāo)即可指定位置。6

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

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

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

intlength;//當(dāng)前長度

intlistsize;//當(dāng)前分配的存儲(chǔ)容量

//(以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注意：由于數(shù)組的下標(biāo)從“0”開始，表中第i個(gè)元素是L.elem[i-1].typedefstruct{ElemType*elem;

intlength;

intlistsize;

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

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個(gè)元素之前插入新的元素e,把e插入到第i個(gè)元素的位置

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初始化指針循環(huán)：從表尾開場，依次將第i-1個(gè)元素之后的元素順序后移一位將新元素e寫入到第i個(gè)位置將表的長度加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算法時(shí)間復(fù)雜度取決于:移動(dòng)元素的次數(shù)14StatusListInsert_Sq(SqList1415插入操作的算法復(fù)雜度考慮移動(dòng)元素的平均情況：假設(shè)在第i個(gè)元素之前插入的概率為pi，那么在長度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：算法時(shí)間復(fù)雜度為:O(n)15插入操作的算法復(fù)雜度考慮移動(dòng)元素的平均情況：若假定在線性1516if(L.length>=L.listsize){

//當(dāng)前存儲(chǔ)空間已滿，增加分配

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

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

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}如果存儲(chǔ)空間已滿怎么辦？16if(L.length>=L.listsize)1617程序設(shè)計(jì)方法的兩點(diǎn)說明先考慮一般情況，后考慮特殊情況一般不用根本操作實(shí)現(xiàn)其他根本操作17程序設(shè)計(jì)方法的兩點(diǎn)說明先考慮一般情況，后考慮特殊情況1718兩個(gè)實(shí)際問題錯(cuò)誤的類型：正常處理的錯(cuò)誤：是一些常見、合理的錯(cuò)誤〔如：用戶輸入的錯(cuò)誤〕，通過錯(cuò)誤代碼返回。意外錯(cuò)誤：拋出Exception，通過try－catch撲捉。初始化問題：數(shù)據(jù)構(gòu)造沒有初始化就使用往往也是錯(cuò)誤，但無法判定。在C++和Java中通過構(gòu)造函數(shù)解決。18兩個(gè)實(shí)際問題錯(cuò)誤的類型：1819順序表的刪除操作ListDelete(&L,i,&e)//刪除元素刪除線性表中第i個(gè)元素，并將刪除的元素方在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個(gè)元素的值賦給變量e循環(huán)：從第i+1個(gè)元素開場，依次將后面的元素順序前移一位將表的長度減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算法時(shí)間復(fù)雜度取決于:移動(dòng)元素的次數(shù)22StatusListDelete_Sq算法時(shí)間復(fù)雜度取2223刪除操作的算法復(fù)雜度考慮移動(dòng)元素的平均情況：假設(shè)在刪除第i個(gè)元素的概率為pi，那么在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：算法時(shí)間復(fù)雜度為:O(n)23刪除操作的算法復(fù)雜度考慮移動(dòng)元素的平均情況：若假定在線性2324LocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType))23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p基本操作：將順序表中的元素逐個(gè)和給定值e相比較。定位操作循環(huán)結(jié)束標(biāo)志：找到e或者p超過表尾的地址24LocateElem_Sq(SqListL,Elem2425定位操作請(qǐng)大家寫出順序表的定位操作的操作步驟和程序要求：在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，假設(shè)存在，那么返回它的位序，否那么返回0算法時(shí)間復(fù)雜度為:O(n)25定位操作請(qǐng)大家寫出順序表的定位操作的算法時(shí)間復(fù)雜度為:O25小結(jié)：順序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)不需要附加空間隨機(jī)存取任一個(gè)元素〔根據(jù)下標(biāo)〕缺點(diǎn)很難估計(jì)所需空間的大小開場就要分配足夠大的一片連續(xù)的內(nèi)存空間更新操作代價(jià)大26小結(jié)：順序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)262627END27END2728第二章線性表1234567891第二章線性表1234567892829本章內(nèi)容2.1線性表的類型定義2.2線性表類型的實(shí)現(xiàn)順序映象2.3線性表類型的實(shí)現(xiàn)鏈?zhǔn)接诚?本章內(nèi)容2.1線性表的類型定義2930順序表示及其特點(diǎn)3順序表示及其特點(diǎn)3031順序表示及其特點(diǎn)順序映象——以x的存儲(chǔ)位置和y的存儲(chǔ)位置之間某種關(guān)系表示邏輯關(guān)系<x,y>。最簡單的一種順序映象方法是：用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素。

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

5順序表示及其特點(diǎn)以“存儲(chǔ)位置相鄰〞表示有序?qū)?lt;ai-1，a32小結(jié)：順序表的特點(diǎn)用連續(xù)的存儲(chǔ)單元存放線性表的元素(采用一維數(shù)組存放)。元素存儲(chǔ)順序與元素的邏輯順序一致。讀寫元素方便，通過下標(biāo)即可指定位置。33

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

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

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

intlength;//當(dāng)前長度

intlistsize;//當(dāng)前分配的存儲(chǔ)容量

//(以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注意：由于數(shù)組的下標(biāo)從“0”開始，表中第i個(gè)元素是L.elem[i-1].typedefstruct{ElemType*elem;

intlength;

intlistsize;

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

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個(gè)元素之前插入新的元素e,把e插入到第i個(gè)元素的位置

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初始化指針循環(huán)：從表尾開場，依次將第i-1個(gè)元素之后的元素順序后移一位將新元素e寫入到第i個(gè)位置將表的長度加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算法時(shí)間復(fù)雜度取決于:移動(dòng)元素的次數(shù)14StatusListInsert_Sq(SqList4142插入操作的算法復(fù)雜度考慮移動(dòng)元素的平均情況：假設(shè)在第i個(gè)元素之前插入的概率為pi，那么在長度為n的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為：若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：算法時(shí)間復(fù)雜度為:O(n)15插入操作的算法復(fù)雜度考慮移動(dòng)元素的平均情況：若假定在線性4243if(L.length>=L.listsize){

//當(dāng)前存儲(chǔ)空間已滿，增加分配

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

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

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存儲(chǔ)容量}如果存儲(chǔ)空間已滿怎么辦？16if(L.length>=L.listsize)4344程序設(shè)計(jì)方法的兩點(diǎn)說明先考慮一般情況，后考慮特殊情況一般不用根本操作實(shí)現(xiàn)其他根本操作17程序設(shè)計(jì)方法的兩點(diǎn)說明先考慮一般情況，后考慮特殊情況4445兩個(gè)實(shí)際問題錯(cuò)誤的類型：正常處理的錯(cuò)誤：是一些常見、合理的錯(cuò)誤〔如：用戶輸入的錯(cuò)誤〕，通過錯(cuò)誤代碼返回。意外錯(cuò)誤：拋出Exception，通過try－catch撲捉。初始化問題：數(shù)據(jù)構(gòu)造沒有初始化就使用往往也是錯(cuò)誤，但無法判定。在C++和Java中通過構(gòu)造函數(shù)解決。18兩個(gè)實(shí)際問題錯(cuò)誤的類型：4546順序表的刪除操作ListDelete(&L,i,&e)//刪除元素刪除線性表中第i個(gè)元素，并將刪除的元素方在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個(gè)元素的值賦給變量e循環(huán)：從第i+1個(gè)元素開場，依次將后面的元素順序前移一位將表的長度減121操作步驟4849StatusListDelete_Sq(SqList&L,inti,ElemType&e){