數(shù)據(jù)結(jié)構(gòu)與算法-第2章線性表

數(shù)據(jù)結(jié)構(gòu)與算法

《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》第2章線性表

安財(cái).管理科學(xué)與工程學(xué).計(jì)算機(jī).王準(zhǔn)生郵箱：bbwhs@163.com2.1線性表的類(lèi)型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎镜膶?shí)現(xiàn)第2章線性表線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素的非空有限集中，存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼2.1線性表的類(lèi)型定義什么是線性表一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。在稍復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，在這種情況下常把數(shù)據(jù)元素稱為記錄（Record）,含有大量記錄的線性表又稱文件（File）。若將線性表記為

（a1，．．．，ai-1，ai，ai+1，．．．，an）,則表中ai-1是ai的直接前驅(qū)元素，ai+1是ai的直接后繼元素

。n是線性表的長(zhǎng)度，n≥0，n=0時(shí)稱為空表。a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱i是數(shù)據(jù)元素ai在線性表中的位序。抽象數(shù)據(jù)類(lèi)型線性表的定義應(yīng)用舉例例2－1假設(shè)利用兩個(gè)線性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合A＝A∪B。（集合中的成員即線性表中的元素）voidunion(List&La,ListLb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//分別求兩個(gè)線性表的長(zhǎng)度f(wàn)or(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i個(gè)數(shù)據(jù)元素賦給eif(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);//假如La中不存在和e相同的數(shù)據(jù)元素，則將e插入到La中}}//union例2－2已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線性表LC，LC中的數(shù)據(jù)元素仍按值非遞減有序排列。voidMergeList(ListLa,ListLb,List&Lc){//已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列//歸并La和Lb得到新的線性表LC，LC中的數(shù)據(jù)元素仍按值非遞減排列。InitList(Lc);//初始化一個(gè)線性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len))//當(dāng)La和Lb均為非空時(shí){GetElem(La,i,ai);GetElem(Lb,,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){//當(dāng)La仍為非空時(shí)GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){//當(dāng)Lb仍為非空時(shí)GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序表示指的是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。線性表的順序存儲(chǔ)結(jié)構(gòu)／順序映象假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，則線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：LOC(ai)=LOC(a1)+(i-1)*l,式中LOC(a1)是線性表中的第一個(gè)數(shù)據(jù)元素a1的在存儲(chǔ)位置，通常稱做線性表的起始位置，或基地址。線性表的這種機(jī)內(nèi)表示稱作線性表的順序存儲(chǔ)結(jié)構(gòu)或順序映象，反之，稱這種存儲(chǔ)結(jié)構(gòu)的線性表為順序表。特點(diǎn)以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。只要確定了存儲(chǔ)線性表的起始位置，線性表中任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，所以，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)C語(yǔ)言的描述由于線性表的長(zhǎng)度可變，且所需最大存儲(chǔ)空間隨問(wèn)題不同而不同，則在C語(yǔ)言中可用動(dòng)態(tài)分配的一維數(shù)組描述。//――――線性表的動(dòng)態(tài)順序存儲(chǔ)結(jié)構(gòu)――――#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量typedefstruct{Elemtype*elem;//存儲(chǔ)空間基址，即線性表的基址intlength;//線性表的當(dāng)前長(zhǎng)度intlistsize;//順序表當(dāng)前分配的存儲(chǔ)容量（以sizeof(ElemType)為單位）//插入空間不足時(shí)可再分配能存儲(chǔ)LISTINCREMENT個(gè)數(shù)據(jù)元素的空間}SqList;初始化順序表L的算法2.3StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));If(!L.elem)

exit(OVERFLOW);//存儲(chǔ)分配失敗L.length=0;//空表長(zhǎng)度應(yīng)為0L.listsize=LIST_INIT_SIZE://初始的存儲(chǔ)容量returnOK;}//InitList_Sq

注意：C語(yǔ)言中數(shù)組的下標(biāo)從0開(kāi)始，因此，若L是SqList類(lèi)型的順序表，則表中第i個(gè)數(shù)據(jù)元素是L.elem[i-1]。算法2.4：在第i個(gè)元素之前插入一個(gè)數(shù)據(jù)元素e。

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在順序線性表L中第i個(gè)位置之前插入新的元素e。//i的合法值為1≤i≤ListLength_Sq(L)+1if(i<1||i>L.length+1) returnERROR;//i值不合法if(L.length>=L.listsize){//當(dāng)前存儲(chǔ)空間已滿，應(yīng)增加分配newbase＝（ElemType*）realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存儲(chǔ)分配失敗L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加了存儲(chǔ)容量}q=&(L.elem[i–1]);//q為插入位置，C語(yǔ)言數(shù)組從0開(kāi)始下標(biāo)for(p=&(L.elem[L.length–1];p>=q;--p)*(p+1)=*p;//從最后一個(gè)元素開(kāi)始直到第i個(gè)元素為止，所有元素依次后移*q=e;//插入元素e到第個(gè)i位置++L.length;//表長(zhǎng)增1returnOK;}//ListInsert_sq算法2.5刪除第i個(gè)元素StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在順序線性表L中刪除第

i個(gè)元素,并用e返回其值//i的合法值為1≤i≤ListLength_Sq(L)if((i<1)||(i>L.length))returnERROR;//i值不合法p=&(L.elem[i–1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給

eq=L.elem+L.length–1;//表尾元素的位置for(++p;p<=q;++p)*(p–1)=*P;//從被刪元素之后的下一個(gè)位置，元素依次左移，覆蓋前一個(gè)――L.length;//表長(zhǎng)減一returnOK;}//ListDelete_Sq對(duì)以上兩個(gè)算法的時(shí)間復(fù)雜度的分析以上兩個(gè)算法的時(shí)間主要耗費(fèi)在移動(dòng)元素上，而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。算法2.4假設(shè)pi是在第i個(gè)元素之前插入一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為

假定概率相等，即pi=1/(n+1)，則上式可簡(jiǎn)化為若表長(zhǎng)為n,則時(shí)間復(fù)雜度為O（n）

算法2.5分析假設(shè)qi是刪除第i個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素時(shí)所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為假定概率相等，即qi=1/n，則上式可簡(jiǎn)化為若表長(zhǎng)為n,則時(shí)間復(fù)雜度為O（n）定位算法，即求線性表中元素e的位置2.6intLocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){//在順序線性表L中查找第1個(gè)值與e滿足compare()(即相等)的元素的位序//若找到,則返回其在L中的位序,否則返回0i=1;//i的初值為第1個(gè)元素的位序p=L.elem;//p的初值為第1個(gè)元素的存儲(chǔ)位置while(i<=L.length&& !(*compare)(*P++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq兩個(gè)非遞減有序的線性表的合并算法2.7voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//已知順序表La和Lb的元素按值非遞減排列//歸并La和Lb得到新的順序表Lc，Lc的元素也按值非遞減排列Pa=La.elem;Pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));if(!Lc.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗pa_last=La..elem+La.length–1;pb_last=Lb..elem+Lb.length–1;while(pa<=pa_last&&pb<=pb_last){//歸并if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}

//插入La的剩余元素while(pa<=pa_last)*pc++=*pa++;

//插入Lb的剩余元素while(pb<=pb_last)*pc++=*pb++;}//MergeList_Sq2.3線性表的鏈?zhǔn)奖硎镜膶?shí)現(xiàn)線性鏈表①鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用任意的一組存儲(chǔ)單元（不連續(xù)）存儲(chǔ)線性表的數(shù)據(jù)元素。②對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映象，稱為結(jié)點(diǎn)。即結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域和指針域。

指針域中存儲(chǔ)的信息稱作指針或鏈。③N個(gè)結(jié)點(diǎn)的結(jié)成一個(gè)鏈表。即為線性表（a1,a2,．．．,an）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。邏輯上相鄰的兩個(gè)數(shù)據(jù)元素其存儲(chǔ)的物理位置不要求緊鄰，因此，這種存儲(chǔ)結(jié)構(gòu)為非順序映象或鏈?zhǔn)接诚蟆Ｓ捎诿總€(gè)結(jié)點(diǎn)只包含一個(gè)指針域，故又稱線性鏈表或單鏈表。④頭指針指示鏈表中的第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。⑤頭結(jié)點(diǎn)：在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，其數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)諸如線性表的長(zhǎng)度等之類(lèi)的附加信息，其指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。定義描述//單鏈表可由頭指針唯一確定，在C語(yǔ)言中可用“結(jié)構(gòu)指針”來(lái)描述//線性表的單鏈表存儲(chǔ)結(jié)構(gòu)typedefstructLnode{ElemTypedata;StructLnode*next;}LNode,*LinkList;函數(shù)GetElem在單鏈表中的實(shí)現(xiàn)，算法2.8StatusGetElem-_L(LinkListL,inti,ElemType&e){//L為帶頭結(jié)點(diǎn)的單鏈表的頭指針,當(dāng)?shù)趇個(gè)元素存在//時(shí)，

其值賦給e并返回OK，否則返回ERRORp=L－＞next;j=1;

//初始化，p指向第一個(gè)結(jié)點(diǎn)，j為計(jì)數(shù)器while(p&&j<i){p=p－＞next;++j;}//順著指針向后查找，直到p指向第

i個(gè)元素或p為空if(!p||j>i)returnERROR;e=p－＞data;returnOK;}//GetElem-_L單鏈表的插入StatusListInsert_L(LinkList&L,inti,ElemTypee){

//在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置之前插入元素ep=L;j=0;while(p&&j<i－1){p=p－＞next;++j;}//尋找第i－1個(gè)結(jié)點(diǎn)if(!P||j>i－1)returnERROR;//插入位置i小于1或大于表長(zhǎng)s=(LinkList)malloc(sizeof(Lnode));s－＞data=e;//生成新結(jié)點(diǎn)s－＞next=p－＞next;p－＞next=s;//插入到鏈表中P結(jié)點(diǎn)之后returnOK;}//ListInsert_Laiai+1ai-1eS②p－＞next=S

①S－＞next=p－＞nextPai+1^…a1…L插入位置StatusListDelete_L(LinkList&L,inti,ElemType&e){

//在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素，并由e返回其值p=L;j=0;while(p－＞next&&j<i－1){p=p－＞next;++j;}//尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)結(jié)點(diǎn)(第i-1個(gè)結(jié)點(diǎn))if(!(p－＞next)||j>i－1)returnERROR;

//找不到欲刪除的結(jié)點(diǎn)q=p－＞next;p－＞next=q－＞next;

//刪除指針q所指向的第i個(gè)結(jié)點(diǎn)e=q－＞data;free(q);//用參數(shù)e保留q結(jié)點(diǎn)的值，并釋放結(jié)點(diǎn)所占的空間returnOK;}//ListDelete_L單鏈表的刪除②p－＞next=q－＞nextaiai+1ai-1P①q=p－＞nextqai+1^…a1…L欲刪結(jié)點(diǎn)voidCreateList_L(LinkList&L,intn){//逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈線性表LL=(LinkList)malloc(sizeof(Lnode));L－＞next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(Lnode))；

//生成新結(jié)點(diǎn)

scanf(&p－＞data);//輸入元素值

p－＞next=L－＞next;L－＞next=p;//插入到表頭}}//CreateList_La2a1a3eP②

L－＞next=p;①p－＞next=L－＞next;頭結(jié)點(diǎn)L單鏈表的創(chuàng)建頭結(jié)點(diǎn)

^L初始情況(習(xí)題集17頁(yè)2.19)已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫(xiě)一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時(shí)間復(fù)雜度（注意：mink和maxk是給定的兩個(gè)參變量，它們的值為任意的整數(shù)）。(習(xí)題集18頁(yè)2.22)試以單鏈表為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)線性表的就地逆置算法，即在原表的存儲(chǔ)空間將線性表（a1,a2...,an）逆置為（an,an-1,...,a1）。(習(xí)題集19頁(yè)2.31)假設(shè)有一個(gè)循環(huán)鏈表的長(zhǎng)度大于1，且表中既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針。已知s為指向鏈表某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)。(習(xí)題集19頁(yè)2.33)已知有單鏈表表示的線性表中含有三類(lèi)字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫(xiě)算法來(lái)構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含同一類(lèi)的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。。單鏈表習(xí)題歸并兩個(gè)非遞減有序的單鏈表的算法2.12voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//已知單鏈表La和Lb的元素按值非遞減有序排列//歸并La和Lb得到新的單鏈表Lc，Lc的元素也按值非遞減有序排列pa=La－＞next；

pb=Lb－＞next;Lc=pc=la;//用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn)while(pa&&pb){if(pa－＞data<=pb－＞data){pc－＞next=pa;pc=pa;pa=pa－＞next;}else{pc－＞next=pb;pc=pb;pb=pb－＞next;}}pc－＞next=pa?pa:pb;//插入剩余段free(Lb);//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L靜態(tài)鏈表―――借助一維數(shù)組來(lái)描述的線性鏈表簡(jiǎn)介其它類(lèi)型的鏈表單向循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表a1a2a3

^頭結(jié)點(diǎn)首元結(jié)點(diǎn)第二個(gè)最后一個(gè)單向循環(huán)鏈表

雙向鏈表/雙向循環(huán)鏈表表中的結(jié)點(diǎn)有兩個(gè)指針，其一指向直接前趨，另一指向其直接后繼//線性表的雙向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)typedefstructDuLNode{