第2講 線性表及其順序存儲

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲結(jié)構(gòu)第2講線性表及其順序存儲2.1線性表2.2順序表A=（a1,a2,…ai-1，ai,ai＋1

，…,an）2.1

線性表1.定義：n個（n≥0）數(shù)據(jù)元素(結(jié)點(diǎn))的有限序列n=0時(shí)稱為數(shù)據(jù)元素開始結(jié)點(diǎn)ai的直接前驅(qū)ai的直接后繼下標(biāo)，是元素的序號，表示元素在表中的位置n為元素總個數(shù)，即表長空表終端結(jié)點(diǎn)線性表的特性：邏輯結(jié)構(gòu)是線性結(jié)構(gòu)除開始結(jié)點(diǎn)外，任何一個結(jié)點(diǎn)有且僅有一個前驅(qū)除終端結(jié)點(diǎn)外，任何一個結(jié)點(diǎn)有且僅有一個后繼其中n稱為線性表的表長說明：(a1，a2，…an)其中數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例：26個英文字母組成的英文表

（A,B,C,D,……,Z）學(xué)號姓名性別年齡班級2001011810205于春梅女182001級電信016班2001011810260何仕鵬男182001級電信017班2001011810284王爽女182001級通信011班2001011810360王亞武男182001級通信012班……………例：學(xué)生情況登記表數(shù)據(jù)元素都是學(xué)生記錄;元素間關(guān)系是線性；表長為4數(shù)據(jù)元素都是字母;元素間關(guān)系是線性；表長為26同一線性表中的元素必定具有相同特性2.線性表上的運(yùn)算置一個空表建一個線性表求表長查找某個元素插入一個元素刪除一個元素拆分線性表合并排序…2.2順序表2.2.1順序表的基本概念及描述2.2.2順序表的實(shí)現(xiàn)2.2.1順序表的基本概念及描述

——線性表的順序存儲稱為順序表1、順序表的定義

用一組連續(xù)的存儲單元（地址連續(xù)）依次存放線性表的各個數(shù)據(jù)元素。即利用數(shù)組技術(shù)存放元素。2、順序表的結(jié)點(diǎn)地址計(jì)算設(shè)首元素a1的存放地址為location(a1)（稱為首地址），設(shè)每個元素占用存儲空間（地址長度）為len字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

loction(ai)=loction(a1)+len*（i-1）(1≤i≤n)

若首元素為a0：

loction(ai)=loction(a0)+len*i(0≤i≤n-1)

（參見順序表存儲結(jié)構(gòu)示意圖）順序表存儲結(jié)構(gòu)示意圖a1a2……aiai+1……an

地址內(nèi)容元素在數(shù)組中的下標(biāo)0i-11n-1空閑區(qū)ilenloction(a1)=bb+lenb+(i-1)lenb+(n-1)lenb+(MAX-1)lenMAX-1一個一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個數(shù)組元素用相鄰的５個字節(jié)存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素Ｍ[０]的第一個字節(jié)的地址是9８，則Ｍ[３]的第一個字節(jié)的地址是

113例1因此：loction(M[3])=98+5×3=113解：地址計(jì)算通式為：loction(ai)=loction(a0)+len*i1、順序表數(shù)據(jù)類型的定義(1)定義數(shù)組的體積(最多允許的元素個數(shù))#defineMAXSIZE100(2)數(shù)據(jù)元素類型定義為datatype如：處理學(xué)生信息typedefstruct{intn;charname[20];ints;}datatype;如：處理inttypedefintdatatype;2.2.2順序表的實(shí)現(xiàn)(3)順序表的類型定義typedefstruct{datatypea[MAXSIZE];/*存放線性表元素的數(shù)組*/

intsize;/*表示a中實(shí)際存放元素個數(shù)(表長)*/}sequence_list;/*順序表的數(shù)據(jù)類型sequence_list*/(4)順序表變量的定義sequence_listslt;

/*slt為順序表變量*/sequence_list*lp;/*lp為順序表指針變量*/結(jié)構(gòu)體變量slta(數(shù)組)size(變量)slt.a[i]slt.size結(jié)構(gòu)指針lpa(數(shù)組)size(變量)lp->a[i]lp->size本課堂順序表的存儲結(jié)構(gòu)的C語言描述如下：#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;即定義相應(yīng)運(yùn)算的C語言函數(shù)。定義函數(shù)要確定：函數(shù)名形參返回值傳入量傳出量出錯處理函數(shù)exit(1);/*返回OS,告知OS程序非正常結(jié)束，該函數(shù)定義在stdlib.h中*/2、順序表的算法實(shí)現(xiàn)算法2.1初始化——建立一個空表空表的表長為0，使順序表變量中的size為0。函數(shù)形參：須初始化順序表的地址返回值：無算法實(shí)現(xiàn)：

voidinit(sequence_listlp){lp->size=0;}a(數(shù)組)size(變量)lp0算法2.2在表尾插入元素即在數(shù)組的size位置插入元素，表長增1。函數(shù)形參：指定順序表的地址，插入元素返回值：無算法實(shí)現(xiàn)：

voidappend(sequence_listlp,datatypex){if(lp->size==MAXSIZE){printf("順序表是滿的!");exit(1);}lp->a[lp->size]=x;lp->size++;}

共size個元素01……size-1size……x算法2.3打印表中每個元素遍歷整個順序表，輸出元素值。函數(shù)形參：指定順序表變量返回值：無算法實(shí)現(xiàn)：

voiddisplay(sequence_listslt){inti;if(!slt.size)printf("\n順序表是空的!");elsefor(i=0;i<slt.size;i++)printf("%5d",slt.a[i]);}算法2.4判順序表是否為空表判斷表長是否為0。函數(shù)形參：指定順序表變量返回值：

1表示空,0表示非空算法實(shí)現(xiàn)：

intempty(sequence_listslt){ returnslt.size==0;}

遍歷順序表，查找與給定值x相同的元素，找到后返回元素的下標(biāo)值，沒找到返回-1。函數(shù)形參：指定順序表變量被找元素值返回值：若找到——下標(biāo)值若未找到——-1

遍歷查找的范圍01……size-1……算法2.5順序表中查找指定值的元素intfind(sequence_listslt,datatypex){inti;

for(i=0;i<slt.size;i++)

if(slt.a[i]==x)returni;

return-1;

}

若datatype是結(jié)構(gòu)類型，不能用“==”直接整體比較，應(yīng)逐一比較結(jié)構(gòu)中每個成員算法實(shí)現(xiàn)：

返回序號為i的元素值。函數(shù)形參：指定順序表變量取元素值的序號返回值：序號為i的元素值i的有效范圍01……size-1……算法2.6取得順序表中序號為i的元素值

datatypeget(sequence_listslt,inti){if(i<0||i>=slt.size)/*查找位置不正確*/{printf("\n指定位置的結(jié)點(diǎn)不存在!");exit(1);}elsereturnslt.a[i];}算法實(shí)現(xiàn)：

順序表的插入運(yùn)算是將一個值為x的結(jié)點(diǎn)插入到順序表的第i個位置0≤i≤n，即將x插入到ki-1和ki之間，如果i=n，則表示插入到表的最后，一般地可表示為： 插入前：{k0,k1,…,ki-1,ki,…,kn-1}

插入后：{k0,k1,…,ki-1,x,ki,…,kn-1}

插入過程的圖示見下圖：

kik0k1ki-1kn-1k0k1ki-1kn-1xki后移開始位置后移結(jié)束位置插入前插入后順序表的插入運(yùn)算

在順序表下標(biāo)為i（0<=i<=size)

的位置插入一個新的數(shù)據(jù)元素x。使長度為size的順序表長增1。

元素可插入位置(0~size)0…i…size-1sizex

從表尾開始到下標(biāo)i的元素依次向后移一位算法2.7在順序表的i位置上插入x值返回值：無函數(shù)形參：指定順序表的地址，插入元素值，

插入的位置（下標(biāo)：0~size）

voidinsert(sequence_listlp,datatypex,inti){intj;if(lp->size==MAXSIZE)/*判表滿*/{printf("\n順序表是滿的!沒法插入!");exit(1);}if(i<0||i>lp->size)/*判插入位置不對*/ {printf("\n指定的插入位置不存在!");exit(1);}for(j=lp->size-1;j>=i;j--)/*從后往前元素后移*/

lp->a[j+1]=lp->a[j];lp->a[i]=x;lp->size++;/*插入并表長增1*/}插入算法實(shí)現(xiàn)：

元素可插入位置(0~size)0…i…size-1sizex

從表尾開始到下標(biāo)i的元素依次向后移一位k0k1…ki…kn-1…移動n-i次插入位置移動次數(shù)

0n最壞O(n)

1n-1……n-11n0最好O(1)

in-i插入算法分析：

可能的插入位置為i=0,1,…,n共n+1個位置按等概率考慮,則插入概率：pi=1/(n+1)平均移動次數(shù)：順序表插入算法平均約需移動一半元素，時(shí)間復(fù)雜度為O(n)順序表的刪除運(yùn)算

順序表的刪除操作是指刪除順序表中的第i個結(jié)點(diǎn)，0≤i≤n-1，一般地可表示為：刪除前：{k0,k1,…,ki-1,ki,ki+1,,…,kn-1}

刪除后：{k0,k1,…,ki-1,ki+1,…,kn-1}

刪除過程的圖示見下圖：kik0k1ki-1kn-1k0k1ki-1kn-1ki+1前移結(jié)束位置前移開始位置刪除前刪除后ki+1在順序表中刪除下標(biāo)為i（0<=i<=size-1)

的元素。使長度為size的順序表長減1。算法2.8刪除順序表的i位置上元素返回值：無函數(shù)形參：指定順序表的地址，刪除元素的位置（下標(biāo)：0~size-1）

刪除元素位置(0~size-1)0…i…size-1size刪除

從下標(biāo)i+1開始到表尾的元素依次向前移一位

voiddele(sequence_listlp,inti){intj;if(lp->size==0)/*判表為空*/{printf("\n順序表是空的!");exit(1);}if(i<0||i>=lp->size)

)/*判刪除位置不對*/{printf("\n指定的刪除位置不存在!");exit(1);}for(j=i+1;j<=lp->size-1;j++)/*元素前移*/

lp->a[j-1]=lp->a[j];lp->size--;/*表長減1*/}刪除算法實(shí)現(xiàn)：

刪除元素位置(0~size-1)0…i…size-1size刪除

從下標(biāo)i+1開始到表尾的元素依次向前移一位k0k1…kiki+1…kn-1…移動n-i-1次刪除位置移動次數(shù)

0n-1最壞O(n)

1n-2……n-21n-10最好O(1)

in-i-1刪除算法分析：

可能的刪除位置為i=0,1,…,n-1共n個位置按等概率考慮,則刪除概率：pi=1/n平均移動次數(shù)：順序表刪除算法平均約需移動一半元素。時(shí)間復(fù)雜度為O(n)（1）voidreverse(sequence_list*lp)

將順序表L就地倒置，即借助于O（1）的輔助空間。（2）voidsprit(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)

將有序順序表L1分裂成兩個線性表L2與L3，L2由表中所奇數(shù)組成，L3由所有偶數(shù)組成。順序表上的一些其它常見算法（3）voidmerge(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)[見順序表應(yīng)用]

將有序順序表L1與L2合并成有序順序表L3。元素類型：typedefstruct{intnum;/*學(xué)生學(xué)號*/charname[20];/*學(xué)生姓名*/intscore;/*成績*/}datatype;建表要求：按輸入順序依次建表,輸入學(xué)號為負(fù)時(shí)結(jié)束函數(shù)形參：被建順序表地址返回值：無建立順序表voidCreate(sequence_listslt)/*建立學(xué)生結(jié)點(diǎn)順序表*/{datatypee;inti=0;/*i為計(jì)結(jié)點(diǎn)個數(shù)變量*/while(1){printf(“\nEnternewstudent:”);scanf(“%d”,&e.num);if(e.num<0)break;/*若學(xué)號值為負(fù)結(jié)束*/getchar();/*跳過輸入學(xué)號后的回車換行*/gets();/*已是地址,前不要加&符*/scanf(“%d”,&e.score);slt->a[i]=e;i++;}slt->size=i;/*表長就是結(jié)點(diǎn)數(shù)*/}運(yùn)算實(shí)現(xiàn)：優(yōu)點(diǎn)：(1)邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素，其物理位置也是相鄰的