數(shù)據(jù)結(jié)構(gòu)9課件

第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)習(xí)題2數(shù)據(jù)結(jié)構(gòu)9線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集線性結(jié)構(gòu)的基本特征:1．集合中必存在唯一的一個(gè)“第一元素”；2．集合中必存在唯一的一個(gè)“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。數(shù)據(jù)結(jié)構(gòu)92.1線性表的類型定義線性表（linear_list）是最常用且最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。簡(jiǎn)言之，一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。例如：（A,B,C,D,……Z） （6,17,28,50,92,188）在線性表中，一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)（item）組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）。數(shù)據(jù)結(jié)構(gòu)9抽象數(shù)據(jù)類型線性表的定義如下：ADTList{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0} //{稱n為線性表的表長(zhǎng);稱n=0時(shí)的線性表為空表。}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n} //{設(shè)線性表為(a1，a2,....，an),稱i為ai在線性表中的位序。}基本操作：

InitList(&L) 結(jié)構(gòu)初始化 操作結(jié)果：構(gòu)造一個(gè)空的線性表L。

DestroyList(&L) 銷毀結(jié)構(gòu)

初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表L。數(shù)據(jù)結(jié)構(gòu)9ListEmpty(L)初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則FALSE。ListLength(L)初始條件：線性表L已存在。操作結(jié)果：返回L中元素個(gè)數(shù)。PriorElem(L,cur_e,&pre_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的元素，但不是第一個(gè)，則用pre_e返回它的前驅(qū)，否則操作失敗，pre_e無(wú)定義。數(shù)據(jù)結(jié)構(gòu)9NextElem(L,cur_e,&next_e)初始條件：線性表L已存在。操作結(jié)果：若cur_e是L的元素，但不是最后一個(gè)，則用next_e返回它的后繼，否則操作失敗，next_e無(wú)定義。GetElem(L,cur_e,&next_e)初始條件：線性表L已存在，1≤i≤LengthList(L)操作結(jié)果：用e返回L中第i個(gè)元素的值。LocateElem(L,e,compare())初始條件：線性表L已存在，compare()是元素判定函數(shù)。操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的元素的位序。若這樣的元素不存在，則返回值為0。數(shù)據(jù)結(jié)構(gòu)9ListTraverse(L,visit())初始條件：線性表L已存在。操作結(jié)果：依次對(duì)L的每個(gè)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ClearList(&L)初始條件：線性表L已存在。操作結(jié)果：將L重置為空表。PutElem(L,i,&e)初始條件：線性表L已存在，1≤i≤LengthList(L)操作結(jié)果：L中第i個(gè)元素賦值同e的值。ListInsert(&L,i,e)初始條件：線性表L已存在，1≤i≤LengthList(L)+1操作結(jié)果：在L的第i個(gè)元素之前插入新的元素e，L的長(zhǎng)度增1。數(shù)據(jù)結(jié)構(gòu)9ListDelete(&L,i,&e)初始條件：線性表L已存在且非空，1≤i≤LengthList(L)操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。}ADTList數(shù)據(jù)結(jié)構(gòu)9例2-1假設(shè)有兩個(gè)集合A和B分別用兩個(gè)線性表LA和LB表示（即：線性表中的數(shù)據(jù)元素即為集合中的成員），現(xiàn)要求一個(gè)新的集合A＝A∪B。上述問(wèn)題可演繹為，要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。1．從線性表LB中依次取得每個(gè)數(shù)據(jù)元素;GetElem(LB,i)→e2．依值在線性表LA中進(jìn)行查訪;LocateElem(LA,e,equal())3．若不存在，則插入之。ListInsert(LA,n+1,e)數(shù)據(jù)結(jié)構(gòu)9voidunion(List&La,ListLb){//將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表的長(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ù)元素，則插入之}}//union數(shù)據(jù)結(jié)構(gòu)92.2線性表類型的實(shí)現(xiàn)--順序映象用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表中的數(shù)據(jù)元素線性表的起始地址，稱作線性表的基地址以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1，ai>

即：所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置數(shù)據(jù)結(jié)構(gòu)9順序映像的C語(yǔ)言描述//-----線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)-----#defineLIST_INIT_SIZE80//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量typedefstruct{ElemType*elem;//存儲(chǔ)空間基址

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

intlistsize;//當(dāng)前分配的存儲(chǔ)容量(以sizeof(ElemType)為單位)}SqList;//俗稱順序表數(shù)據(jù)結(jié)構(gòu)9線性表的初始化在順序映像中的實(shí)現(xiàn)StatusInitList_Sq(SqList&L){//構(gòu)造一個(gè)空的線性表L。L.elem=(ElemType)malloc(LISTINCREMENT*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存儲(chǔ)分配失敗L.length=0;//長(zhǎng)度為0L.listsize=LISTINCREMENT;//初始存儲(chǔ)容量returnOK;}//InitList_Sq數(shù)據(jù)結(jié)構(gòu)9線性表操作ListInsert(&L,i,e)的實(shí)現(xiàn)：?jiǎn)枺翰迦朐貢r(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)數(shù)據(jù)結(jié)構(gòu)9StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在順序線性表L的第pos個(gè)元素之前插入新的元素e，//pos的合法值為1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(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ǔ)容量}q=&(L.elem[pos-1]); //q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //插入位置及之后的元素右移*q=e; //插入e++L.length; //表長(zhǎng)增1returnOK;}

//ListInsert_Sq數(shù)據(jù)結(jié)構(gòu)9線性表操作ListDelete(&L,i,&e)的實(shí)現(xiàn)：?jiǎn)枺簞h除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?a1,…,ai-1,ai+1,…,an)數(shù)據(jù)結(jié)構(gòu)9StatusListDelete_Sq(SqList&L,intpos,ElemType&e){//在順序線性表L中刪除第pos個(gè)元素，并用e返回其值。//pos的合法值為1≤pos≤ListLength_Sq(L)if((pos<1)||(pos>L.length))returnERROR;//刪除位置不合法p=&(L.elem[pos-1]);//p為被刪除元素的位置e=*p;//被刪除元素的值賦給eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被刪除元素之后的元素左移--L.length;//表長(zhǎng)減1returnOK;}

//ListDelete_Sq數(shù)據(jù)結(jié)構(gòu)92.3線性表類型的實(shí)現(xiàn)－－鏈?zhǔn)接诚笠?、單鏈表用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。

元素 + 指針 = 結(jié)點(diǎn)

(數(shù)據(jù)元素的映象)

(指示后繼元素存儲(chǔ)位置的)

(表示數(shù)據(jù)元素)

以“結(jié)點(diǎn)的序列”表示線性表－－稱作鏈表。以線性表中第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址作為線性表的地址，為線性表的頭指針。數(shù)據(jù)結(jié)構(gòu)9單鏈表結(jié)構(gòu)

(a)結(jié)點(diǎn)結(jié)構(gòu)；(b)空表；(c)非空表DataNext(a)H(b)a0a1…an－1(c)H數(shù)據(jù)結(jié)構(gòu)9二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述typedefstructLNode{ElemTypedata;//數(shù)據(jù)域structLnode*next;//指針域}LNode,*LinkList;在單鏈表前增加一個(gè)結(jié)點(diǎn)，稱為表頭結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)9帶表頭結(jié)點(diǎn)的單鏈表

(a)空表；(b)非空表HeadHeada0a1…an－1(a)(b)數(shù)據(jù)結(jié)構(gòu)9看下面的程序段：inti,*pi; /*定義整型變量i和指向整型的指針變量pi*/pi=&i; /*將變量i的地址賦給指針(變量)pi*/i=5; /*對(duì)變量i賦整數(shù)值5*/printf("%d，"，i); /*輸出i的值5和逗號(hào)*/*pi=10; /*對(duì)指針pi所指示的存儲(chǔ)位置(變量i)賦值10*/printf("%d"，*pi); /*輸出i的當(dāng)前值10*/運(yùn)行上面的程序段將顯示：5，10。數(shù)據(jù)結(jié)構(gòu)9

指針定義和運(yùn)算254piipi＝&i;2545piii＝5;25410piipi＝10;pi&i＝254inti,*pi;*數(shù)據(jù)結(jié)構(gòu)9單鏈表的插入和刪除在單鏈表的指定結(jié)點(diǎn)(設(shè)由指針變量p指示)后面插入新結(jié)點(diǎn)(由q指示)的方法很簡(jiǎn)單，只需使用指針賦值語(yǔ)句q->Next=p->Next;和p->Next=q;，即修改兩個(gè)結(jié)點(diǎn)的指針域的值就可以了，如圖所示。數(shù)據(jù)結(jié)構(gòu)9單鏈表的插入

(a)插入前；(b)插入后xqPq->Next＝p->Next；p->Next＝q；xpq(a)(b)數(shù)據(jù)結(jié)構(gòu)9線性表的操作ListInsert(&L,i,e)在鏈表中的實(shí)現(xiàn):基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針有序?qū)?lt;ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>StatusListInsert_L(LinkListL,intpos,ElemTypee){//在帶頭結(jié)點(diǎn)的單鏈表L中第pos個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素ep=L;j=0;while(p&&j<pos-1){

p=p->next;++j;}

//尋找第pos-1個(gè)結(jié)點(diǎn)if(!p||j>pos-1)returnERROR; //pos小于1或者大于表長(zhǎng)s=(LinkList)malloc(sizeof(LNode)); //生成新結(jié)點(diǎn)s->data=e;s->next=p->next;

//插入L中p->next=s;returnOK;}//LinstInsert_L數(shù)據(jù)結(jié)構(gòu)9

刪除操作如圖所示。刪除p所指示的結(jié)點(diǎn)時(shí)，只需修改一個(gè)指針：q->Next=p->Next，但還需使用free(p)語(yǔ)句回收結(jié)點(diǎn)占用的空間。這里，結(jié)點(diǎn)*q是結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)(predecessor)。由此可見，在單鏈表中，為了刪除一個(gè)結(jié)點(diǎn)，我們必須知道它的前驅(qū)結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)9單鏈表的刪除

(a)刪除前；(b)刪除后qq->Next＝p->Next；pqp(a)(b)數(shù)據(jù)結(jié)構(gòu)9StatusListDelete_L(LinkListL,intpos,ElemType&e){//在帶頭結(jié)點(diǎn)的單鏈表L中，刪除第pos個(gè)元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前趨p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//刪除位置不合理q=p->next;p->next=q->next;

//刪除并釋放結(jié)點(diǎn)e=q->data;free(q);returnOK;}

//ListDelete_L算法的時(shí)間復(fù)雜度為:O(ListLength(L))數(shù)據(jù)結(jié)構(gòu)9五、循環(huán)鏈表

另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。由此，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，如圖為單鏈表的循環(huán)鏈表和帶頭結(jié)點(diǎn)的循環(huán)鏈表。最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表數(shù)據(jù)結(jié)構(gòu)9單循環(huán)鏈表(a)空表；(b)非空表(a)(b)Heada0a1…an－1Head數(shù)據(jù)結(jié)構(gòu)9帶表頭結(jié)點(diǎn)的單循環(huán)鏈表(a)空表；(b)非空表(a)(b)Heada0a1…an－1Head數(shù)據(jù)結(jié)構(gòu)9六、雙向鏈表我們已經(jīng)看到，在各種單鏈表中插入一個(gè)新結(jié)點(diǎn)時(shí)，需知道新結(jié)點(diǎn)插入位置的前驅(qū)結(jié)點(diǎn)，而當(dāng)刪除一個(gè)結(jié)點(diǎn)時(shí)也需知道該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。常常為了得到前驅(qū)結(jié)點(diǎn)的地址，必須從頭開始查找，這一過(guò)程是費(fèi)時(shí)的。此外，在實(shí)際應(yīng)用中，有時(shí)需要逆向訪問(wèn)表中元素，這對(duì)單鏈表結(jié)構(gòu)來(lái)說(shuō)顯然是困難的。為解決這類問(wèn)題，可將鏈表設(shè)計(jì)成雙向鏈表(doublylinkedlist)。數(shù)據(jù)結(jié)構(gòu)9

雙向鏈表的每個(gè)結(jié)點(diǎn)包含三個(gè)域：Element、Prior和Next。其中，Element為元素域，Next域?yàn)橹赶蚝罄^結(jié)點(diǎn)的指針，新增的Prior域用以指向前驅(qū)結(jié)點(diǎn)。雙向鏈表也可以帶表頭結(jié)點(diǎn)，并且也可構(gòu)成雙向循環(huán)鏈表。此時(shí)，表頭結(jié)點(diǎn)的Next和Prior分別指向雙向循環(huán)鏈表的頭結(jié)點(diǎn)(或表頭結(jié)點(diǎn))和尾結(jié)點(diǎn)。帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表的結(jié)構(gòu)示意圖如圖所示。數(shù)據(jù)結(jié)構(gòu)9帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表(a)空表；(b)非空表(a)(b)HeadHeada0an－1…數(shù)據(jù)結(jié)構(gòu)9//-----線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)

-----typedefstructDuLNode{ElemTypedata; //數(shù)據(jù)域structDuLNode*prior; //指向前驅(qū)的指針域structDuLNode*next; //

指向后繼的指針域}DuLNode,*DuLinkList;數(shù)據(jù)結(jié)構(gòu)9線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：1、優(yōu)點(diǎn)（1）結(jié)構(gòu)簡(jiǎn)單（2）可直接定位到表中任一元素，并可隨機(jī)存取元素；連續(xù)存儲(chǔ)速度快2、缺點(diǎn)（1）存儲(chǔ)空間難于準(zhǔn)確靜態(tài)分配，大了浪費(fèi)，小了不夠（2）插入、刪除操作大不方便，需移動(dòng)大量數(shù)據(jù)元素，效率低數(shù)據(jù)結(jié)構(gòu)9線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)：1、優(yōu)點(diǎn)（1）存儲(chǔ)空間動(dòng)態(tài)分配，可以按需使用（2）插入、刪除結(jié)點(diǎn)操作時(shí)通常只要修改指針，不必移動(dòng)數(shù)據(jù)元素2、缺點(diǎn)（1）每一結(jié)點(diǎn)附加指針域（2）非隨機(jī)存取結(jié)構(gòu)，查找定位操作需從頭指針出發(fā)順著鏈表掃描數(shù)據(jù)結(jié)構(gòu)9習(xí)題22－1定義一個(gè)結(jié)構(gòu)類型，它包括年、月、日。用該結(jié)構(gòu)類型定義一個(gè)結(jié)構(gòu)變量。

2－2設(shè)計(jì)一個(gè)算法，用來(lái)復(fù)制一個(gè)單鏈表

2－3設(shè)有長(zhǎng)度為n的一維整型數(shù)組A，設(shè)計(jì)一個(gè)算法，將原數(shù)組中的元素以逆序排列。

2－4設(shè)計(jì)一個(gè)算法，將一個(gè)單鏈表鏈接到另一個(gè)單鏈表的尾部。數(shù)據(jù)結(jié)構(gòu)92－5設(shè)一維數(shù)組的每個(gè)元素具有前面的年、月、日結(jié)構(gòu)類型，設(shè)計(jì)一個(gè)函數(shù)Cop