數(shù)據(jù)結(jié)構(gòu)電子科技-第二章線性表

數(shù)據(jù)結(jié)構(gòu)關(guān)聯(lián)圖

串n個字符的有限序列前驅(qū)后繼數(shù)數(shù)據(jù)元素限制線性表的變型帶頭結(jié)點、循環(huán)、雙向結(jié)點變化棧

插入、刪除限定在一端進(jìn)行的線性表隊列插入限定在一端，刪除在另一端進(jìn)行的線性表操作限制數(shù)據(jù)元素擴展數(shù)組數(shù)據(jù)元素之間的關(guān)系在維數(shù)上擴充的線性表維數(shù)擴展廣義表數(shù)據(jù)元素可以是表的線性表樹每個結(jié)點可以有多個后繼,但至多一個前驅(qū)圖每個結(jié)點可以有多個后繼和多個前驅(qū)線性表

n個數(shù)據(jù)元素的有限序列第二章線性表線性結(jié)構(gòu)特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼2.1線性表的類型定義定義：一個線性表是n個相同類型數(shù)據(jù)元素的有限序列例英文字母表（A,B,C,…..Z)是一個線性表例數(shù)據(jù)元素特征：元素個數(shù)n—表長度，n=0空表1<i<n時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼i為數(shù)據(jù)元素ai在線性表中的位序ADTList{線性表的抽象數(shù)據(jù)類型定義數(shù)據(jù)對象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}1}ADTList數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}2基本操作：結(jié)構(gòu)初始化操作結(jié)構(gòu)銷毀操作引用型操作加工型操作32.1.1線性表的定義Data_Structure＝（D，L，S，O）基本操作O：是在邏輯結(jié)構(gòu)上對數(shù)據(jù)結(jié)構(gòu)或數(shù)據(jù)元素的一組基本運算，與具體實現(xiàn)無關(guān)；可利用給定的基本操作構(gòu)造更復(fù)雜的運算如：線性表初始化；求線性表的長度；按值查找；插入元素操作；刪除元素操作等

StatusList_Init(ListPtrL)初始條件：表L不存在。操作結(jié)果：成功返回success，構(gòu)造一個空的線性表L；否則返回fatal。(1).線性表初始化操作：假設(shè)：所有操作都通過函數(shù)來實現(xiàn)，函數(shù)通常包括函數(shù)名字、返回類型、函數(shù)參數(shù)以及函數(shù)體（具體實現(xiàn)），其中函數(shù)參數(shù)包括參數(shù)個數(shù)、參數(shù)類型和參數(shù)順序。線性表定義為指針類型ListPtr，數(shù)據(jù)元素類型為ElemType

voidList_Destory(ListPtrL)初始條件：表L存在。操作結(jié)果：釋放L所占空間。⑵銷毀線性表操作：

voidList_Clear(ListPtrL)初始條件：表L存在。操作結(jié)果：清除線性表L的所有元素，L變?yōu)榭毡?。⑶線性表清空操作：

boolList_Empty(ListPtrL)初始條件：表L存在。操作結(jié)果：線性表L空返回true，否則返回false。

⑷線性表判空操作：

intList_Size(ListPtrL)初始條件：表L存在。操作結(jié)果：返回線性表L中的所含數(shù)據(jù)元素的個數(shù)。⑸求線性表的長度操作：

StatusList_Retrieve(ListPtrL,intpos,ElemType*elem)初始條件：表L存在。操作結(jié)果：若1<=pos<=List_Size(L)，返回success，同時將線性表L中的第pos個元素的值存放在elem中；否則返回range_error。⑹取表中元素操作：

StatusList_Locate(ListPtrL,ElemTypeelem,int*pos)初始條件：表L存在，elem是給定的一個數(shù)據(jù)元素。操作結(jié)果：在表L中查找首次值為elem的數(shù)據(jù)元素，若找到，返回success，同時將L中首次值為elem的數(shù)據(jù)元素的序號記入pos;否則，返回fail。⑺按值查找操作：

StatusList_Insert(ListPtrL,intpos,ElemTypeelem)初始條件：表L存在。操作結(jié)果：若1<=pos<=List_Size(L)+1，且線性表中還有未用的存儲空間，在線性表L的第pos個位置上插入一個值為elem的新元素，原序號為pos,pos+1,...,n的數(shù)據(jù)元素的序號變?yōu)閜os+1,pos+2,...,n+1，插入后表長=原表長+1,返回success；否則，若沒有空間返回overflow，位置不對返回range_error。⑻插入操作：

StatusList_Remove(ListPtrL,intpos)初始條件：表L存在。操作結(jié)果：若1<=pos<=List_Size(L)，在線性表L中刪除序號為pos的數(shù)據(jù)元素，刪除后使序號為pos+1,pos+2,...,n的元素的序號變?yōu)閜os,pos+1,...,n-1，新表長＝原表長－１,返回success；否則返回range_error。⑼

刪除操作：StatusList_Prior(ListPtrL,int*pos,ElemTypeelem)初始條件：表L存在。操作結(jié)果：若第pos個數(shù)據(jù)元素的直接前驅(qū)存在，將其存入elem中,返回success;否則返回fail。⑽

求前驅(qū)操作：

StatusList_Next(ListPtrL,int*pos,ElemTypeelem)初始條件：表L存在。操作結(jié)果：若第pos個數(shù)據(jù)元素的直接后繼存在，將其存入elem中,返回success;否則返回fail。⑾

求后繼操作：例1：合并線性表問題：集合A和B分別用兩個線性表LA和LB表示，求A∪B并用線性表LA表示。算法設(shè)計：思想：從LB中逐一取出元素,判該元素是否在LA中,若不在則將該元素插入到LA中。細(xì)化：到實現(xiàn)程度逐一：從第一個到最后一個,計數(shù)型循環(huán),前提是需要知道元素個數(shù)如何取出第i個數(shù)據(jù)元素bi？如何判斷bi是否已在A中？如果不在A中，怎樣實現(xiàn)將bi插入？1．依次從LB中取出第i個數(shù)據(jù)元素;2．判elem是否在LA中存在;3．若不存在，則將elem插入到LA中。List_Retrieve(Lb,i,&elem)→elem

List_Locate(La,elem,&j)

List_Insert(La,1,elem)用基本操作實現(xiàn)：StatusList_Union(ListPtrLa,ListPtrLb){

ElemTypeelem;/*存放從Lb中取出的元素*/Statusstatus;/*狀態(tài)代碼*/

inti,j,len=List_Size(Lb);/*len存放Lb的元素個數(shù)*/

for(i=1;i<=len;i++){

List_Retrieve(Lb,i,&elem);/*取出Lb中第i個數(shù)據(jù)元素*/status=List_Locate(La,elem,&j);/*判它是否在La中*/if(status!=success){/*如果不在*/status=List_Insert(La,1,elem);/*插入到第一個位置*/if(status!=success)break;/*插入失敗則退出*/

}}

returnstatus;}例：合并線性表算法例：合并線性表算法分析如何分析？設(shè)m和n分別表示La和Lb的長度（元素個數(shù)）先確定基本操作----判斷是否在La中基本操作執(zhí)行次數(shù)是否確定？確定：次數(shù)不確定：最好/最壞/平均情況分析本例不確定最好情形分析B為A的前面部分元素:1+2+…+n=(n+1)*n/2最壞情形分析B∩A為空:m+(m+1)…+(m+n-1)=n*m+(n-1)*n/2優(yōu)化？選數(shù)據(jù)元素個數(shù)少的作為Lb例2：合并有序表問題：已知線性表La和Lb中元素分別按非遞減順序排列，現(xiàn)要求將它們合并成一個新的線性表Lc，并使得Lc中元素也按照非遞減順序排列。分析：線性表Lc初始為空。依次掃描La和Lb中的元素，比較當(dāng)前元素的值，將較小值的元素插入Lc的表尾之后，如此反復(fù)，直到一個線性表掃描完畢，然后將未完的那個線性表中余下的元素逐個插入到Lc的表尾之后細(xì)化：現(xiàn)有操作可實現(xiàn)否？StatusList_Merge(ListPtrLa,ListPtrLb,ListPtrLc){ElemTypeelem1,elem2;status=List_Init(Lc);inti=1,j=1,k=1;/*i,j,k分別用于指示La,Lb,Lc中當(dāng)前元素*/intn=List_Size(La)，m=List_Size(Lb);

while(i<=n&&j<=m){/*兩個表都還未處理完*/List_Retrieve(La,i,&elem1);List_Retrieve(Lb,j,&elem2);if(elem1<elem2){status=List_Insert(Lc,k,elem1);i=i+1;}else{status=List_Insert(Lc,k,elem2);j=j+1;}k=k+1;}

while(i<=n){/*表La都還未處理完*/

List_Retrieve(La,i,&elem1);status=List_Insert(Lc,k,elem1);i=i+1;k=k+1;}

while(j<=m){/*表Lb都還未處理完*/List_Retrieve(Lb,j,&elem2);status=List_Insert(Lc,k,elem2);j=j+1;k=k+1;}returnstatus;}算法分析：該算法中包含了三個while語句，第一個處理了某一張表的全部元素和另一張表的部分元素；后兩個while循環(huán)只可能有一個執(zhí)行，用來完成將未歸并到Lc中的余下部分元素插入到Lc中?！安迦搿笔枪懒繗w并算法時間復(fù)雜度的基本操作，次數(shù)為兩個表的元素個數(shù)之和：n+m該算法的時間復(fù)雜度為：O（n+m）若La和Lb的元素個數(shù)為同數(shù)量級n，則該算法的時間復(fù)雜度為：O（n）。2.1.2線性表的順序存儲結(jié)構(gòu)順序表：定義：用一組地址連續(xù)的存儲單元存放一個線性表叫~元素地址計算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一個元素占用的存儲單元個數(shù)LOC(ai)—線性表第i個元素的地址LOC(a1)—起始地址，基地址特點：實現(xiàn)邏輯上相鄰—物理地址相鄰實現(xiàn)隨機存取實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;元素序號a1a2anbb+lb+（n-1）l12n內(nèi)存存儲地址b+(maxlen-1)l備用空間數(shù)據(jù)元素不是簡單類型時,可定義結(jié)構(gòu)體數(shù)組動態(tài)申請內(nèi)存L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));插入定義：線性表的插入是指在第i（1in+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表

變成長度為n+1的線性表

需將第i至第n共（n-i+1)個元素后移算法Ch2_1.c內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1an-1x算法時間復(fù)雜度T(n)設(shè)Pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：刪除定義：線性表的刪除是指將第i（1in）個元素刪除，使長度為n的線性表

變成長度為n-1的線性表

需將第i+1至第n共（n-i)個元素前移算法Ch2_2.c內(nèi)存a1a2aiai+1an01i-1V數(shù)組下標(biāo)n-1in12i元素序號i+1nn+1內(nèi)存a1a2ai+1V數(shù)組下標(biāo)01i-1n-2in-112i元素序號i+1n-1nanai+2算法評價設(shè)Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數(shù)的平均次數(shù)為：故在順序表中插入或刪除一個元素時，平均移動表的一半元素，當(dāng)n很大時，效率很低順序存儲結(jié)構(gòu)的優(yōu)缺點優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴充2.1.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點：用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息結(jié)點

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲位置數(shù)據(jù)域指針域結(jié)點ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數(shù)據(jù)域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針實現(xiàn)typedefstructLNode{

ElemType

data;structLNode*next;}LNode,*LinkList;LNode*h,*p;datanextp結(jié)點（*p）(*p)表示p所指向的結(jié)點(*p).datap->data表示p指向結(jié)點的數(shù)據(jù)域(*p).nextp->next表示p指向結(jié)點的指針域生成一個新結(jié)點：p=(LinkList)malloc(sizeof(Lnode));系統(tǒng)回收p結(jié)點：free(p)線性鏈表定義：結(jié)點中只含一個指針域的鏈表叫~，也叫單鏈表頭結(jié)點：在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點叫~頭結(jié)點指針域為空表示線性表為空ha1a2頭結(jié)點an^…...h空表^單鏈表的基本運算查找：查找單鏈表中是否存在結(jié)點X，若有則返回指向X結(jié)點的指針；否則返回NULL算法描述While循環(huán)中語句頻度為若找到結(jié)點X，為結(jié)點X在表中的序號否則，為npabxs算法評價插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as->next=p->next;p->next=s;算法描述算法評價Ch2_4.c算法描述pabc算法評價刪除：單鏈表中刪除b，設(shè)p指向ap->next=p->next->next;Ch2_5.c動態(tài)建立單鏈表算法：設(shè)線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針?biāo)惴枋鏊惴ㄔu價h頭結(jié)點an^0h頭結(jié)點an-10an^a2…...h頭結(jié)點an-10an^ha1a2頭結(jié)點an^…...0Ch2_6.ch頭結(jié)點0^單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢循環(huán)鏈表(circularlinkedlist)循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next=NULL循環(huán)鏈表p或p->next=hhh空表雙向鏈表（doublelinkedlist）單鏈表具有單向性的缺點結(jié)點定義typedefstructDuLNode{ElemTypetata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;bcaP刪除算法描述算法評價：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;Status

ListDelete_Dul(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_Dul(L,i)))returnERROR;e=p->data;p->prior->next=p->next;

p->next->prior=p->prior;

free(p);returnOK}StatusListInsert_Dul(DuLinkList&L,inti,ElemTypee){if(!(p=GetElemP_Dul(L,i)))returnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) returnERRORs->data=e;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;

returnOK}算法描述算法評價：T(n)=O(1)xSbaP插入4.靜態(tài)鏈表某些語言中不提供指針，如Java和VisualBASIC等，則只能通過其他方式來模擬指針采用數(shù)組模擬鏈表的指針，用以表示數(shù)據(jù)元素后繼所存放位置數(shù)據(jù)元素的存儲空間像順序表一樣是事先靜態(tài)分配的數(shù)據(jù)元素之間的關(guān)系像鏈表一樣是顯示的

dataNexthead=004

1a45

29

3a31

4a18

5a5-1av=667

72

8a23

910

1011

11-1順序與鏈?zhǔn)酱鎯Y(jié)構(gòu)比較順存儲結(jié)構(gòu)的特點邏輯上相鄰的元素，其物理位置也相鄰；可隨機存取表中任一元素必須按最大可能長度預(yù)分存儲空間，存儲空間利用率低，表的容量難以擴充，是一種靜態(tài)存儲結(jié)構(gòu)插入刪除時，需移動大量元素，平均移動元素為n/2鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點邏輯上相鄰的元素，其物理位置不一定相鄰；元素之間的鄰接關(guān)系由指針域指示是非隨機存取存儲結(jié)構(gòu)；對鏈表的存取必須從頭指針開始是一種動態(tài)存儲結(jié)構(gòu)；插入刪除運算非常方便；只需修改相應(yīng)指針值2.1.5

線性表的應(yīng)用存儲結(jié)構(gòu)選擇原則各有優(yōu)缺點，選擇那一種存儲結(jié)構(gòu)由實際問題中的主要因素決定(1)基于存儲空間的考慮：線性表的長度或存儲規(guī)模難以估計時，或數(shù)據(jù)元素動態(tài)變化較大時，使用鏈表(2)基于運算時間的考慮：經(jīng)常做的是訪問數(shù)據(jù)元素操作，插入刪除操作極少時用順序表(3)基于實現(xiàn)的考慮：順序表的實現(xiàn)較為簡單，鏈表的實現(xiàn)較為復(fù)雜1.線性表倒置問題：把線性表(a1，a2，…,an)變?yōu)?an，an-1，…,a1)算法：算法1：對應(yīng)數(shù)據(jù)元素相交換，如a1與an交換、a2與an-1交換等等算法2：前驅(qū)后繼關(guān)系改變，即倒置前a1是a2的前驅(qū)、a2是a1后繼，倒置后a1是a2的后繼、a2是a1前驅(qū)，……實現(xiàn)：順序表上實現(xiàn)單鏈表上實現(xiàn)1.線性表倒置在順序表上按算法1（對應(yīng)數(shù)據(jù)元素相交換）實現(xiàn)P.41：voidList_Reverse(ListPtrL){inti=1,j=L->length; ElemTypetemp; while(i<j){ temp=L->elem[i]; L->elem[i]=L->elem[j]; L->elem[j]=temp; i++;j--;

}}思考：能否用for循環(huán)？1.線性表倒置在單鏈表上按算法2（前驅(qū)后繼關(guān)系互換）實現(xiàn)P.42：voidList_Reverse(ListPtrL){ListNodePtrq,p=(*L)->next;/*p指向第一個數(shù)據(jù)結(jié)點*/(*L)->next=NULL;/*將原鏈表置為空表*/while(p){q=p;p=p->next;q->next=(*L)->next;/*插到頭結(jié)點的后面*/(*L)->next=q;

}}線性表元素按照訪問頻度排序問題：設(shè)計一個在線性表中實現(xiàn)Locate運算的函數(shù)，使得線性表中所有結(jié)點按訪問頻度遞減的順序排列，以使訪問頻繁高的結(jié)點總是靠近表頭分析：運算主要包括查找如果該元素比前一個頻繁，則需要將其向前移動，也就是插入和刪除操作結(jié)構(gòu)選擇查找：順序或者鏈?zhǔn)骄?；插入刪除：鏈?zhǔn)酱鎯C合：選擇鏈?zhǔn)侥姆N鏈?zhǔn)浇Y(jié)構(gòu)呢？涉及前驅(qū)操作：雙向鏈表線性表元素按照訪問頻度排序選用帶頭結(jié)點的雙向鏈表L，每個結(jié)點有4部分： 指向前驅(qū)結(jié)點的指針prior

指向后繼結(jié)點的指針next

存放數(shù)據(jù)的成員data

記載訪問頻度freq，初始時所有結(jié)點的freq都為0。首先在鏈表中查找指定數(shù)據(jù)，如找到，將其freq加1，然后向前尋找freq大于它的結(jié)點，并在該結(jié)點后面進(jìn)行插入。priorfreqdatanext線性表元素按照訪問頻度排序voidLocate(DuListL,ElemTypex){

pNodep=L->next,q; while(p&&p->data!=x)p=p->next;/*定位*/ if(p){

/*鏈表中存在x*/ p->freq++; /*該結(jié)點的訪問頻度加1*/ q=p; /*從鏈表中摘下這個結(jié)點*/ if(p->prior)p->prior->next=p->next; if(p->next)p->next->prior=p->proir; p=q->prior;

while(p!=L&&q->freq>p->freq)/*尋找插入位置*/ p=p->prior; q->next=p->next; /*插入在p之后*/ q->prior=p; if(p->next)p->next->prior=q; p->next=q;

} else Error("Notfound!\n"); /*沒找到*/}typedefstructnode{ElemTypedata;intfreq;structnode*prior,*next;}*DuList,*pNode;priorfreqdatanext思考：能否不要第二個循環(huán)？2.4線性表的應(yīng)用舉例一元多項式的表示及相加一元多項式的表示：可用線性表P表示但對S(x)這樣的多項式浪費空間一般其中用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示其存儲結(jié)構(gòu)可以用順序存儲結(jié)構(gòu)，也可以用單鏈表單鏈表的結(jié)點定義typedefstructnode{intcoef,exp;structnode*next;}JD;coefexpnext-1A703198517^-1B81227-98^-1C70111227517^一元多項式相加設(shè)p,q分別指向A,B中某一結(jié)點，p,q初值是第一結(jié)點，結(jié)果保存在A中比較p->exp與q->expp->exp<q->exp:p結(jié)點是和多項