數(shù)據(jù)結構與算法-第2章線性表

數(shù)據(jù)結構與算法

《數(shù)據(jù)結構（C語言版）》第2章線性表

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

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

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

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

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

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

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

i個元素,并用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;//從被刪元素之后的下一個位置，元素依次左移，覆蓋前一個――L.length;//表長減一returnOK;}//ListDelete_Sq對以上兩個算法的時間復雜度的分析以上兩個算法的時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。算法2.4假設pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時所需移動元素次數(shù)的期望值（平均次數(shù)）為

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

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

Status(*compare)(ElemType,ElemType)){//在順序線性表L中查找第1個值與e滿足compare()(即相等)的元素的位序//若找到,則返回其在L中的位序,否則返回0i=1;//i的初值為第1個元素的位序p=L.elem;//p的初值為第1個元素的存儲位置while(i<=L.length&& !(*compare)(*P++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq兩個非遞減有序的線性表的合并算法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);//存儲分配失敗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線性表的鏈式表示的實現(xiàn)線性鏈表①鏈式存儲結構的特點是用任意的一組存儲單元（不連續(xù)）存儲線性表的數(shù)據(jù)元素。②對數(shù)據(jù)元素ai來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息。這兩部分信息組成數(shù)據(jù)元素ai的存儲映象，稱為結點。即結點包括兩個域：數(shù)據(jù)域和指針域。

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

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

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

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

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

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

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

//找不到欲刪除的結點q=p－＞next;p－＞next=q－＞next;

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

//生成新結點

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

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

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

^L初始情況(習題集17頁2.19)已知線性表中的元素（整數(shù)）以值遞增有序排列，并以單鏈表作存儲結構。試寫一高效算法，刪除表中所有大于mink且小于maxk的元素（若表中存在這樣的元素），分析你的算法的時間復雜度（注意：mink和maxk是給定的兩個參變量，它們的值為任意的整數(shù)）。(習題集18頁2.22)試以單鏈表為存儲結構實現(xiàn)線性表的就地逆置算法，即在原表的存儲空間將線性表（a1,a2...,an）逆置為（an,an-1,...,a1）。(習題集19頁2.31)假設有一個循環(huán)鏈表的長度大于1，且表中既無頭結點也無頭指針。已知s為指向鏈表某個結點的指針，試編寫算法在鏈表中刪除指針s所指結點的前趨結點。(習題集19頁2.33)已知有單鏈表表示的線性表中含有三類字符的數(shù)據(jù)元素（如字母字符、數(shù)字字符和其它字符），試編寫算法來構造三個以循環(huán)鏈表表示的線性表，使每個表中只含同一類的字符，且利用原表中的結點空間作為這三個表的結點空間，頭結點可另辟空間。。單鏈表習題歸并兩個非遞減有序的單鏈表的算法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的頭結點作為Lc的頭結點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的頭結點}//MergeList_L靜態(tài)鏈表―――借助一維數(shù)組來描述的線性鏈表簡介其它類型的鏈表單向循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表a1a2a3

^頭結點首元結點第二個最后一個單向循環(huán)鏈表

雙向鏈表/雙向循環(huán)鏈表表中的結點有兩個指針，其一指向直接前趨，另一指向其直接后繼//線性表的雙向循環(huán)鏈表存儲結構typedefstructDuLNode{