數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)資料(完整版)(精華版)

序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作的 (1)邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。 (2)存儲結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示。 (3)操作：數(shù)據(jù)的運算(檢索、排序、插入、刪除、修改)。 (1)計算機內(nèi)的數(shù)值運算依靠方程式，而非數(shù)值運算(如表、樹、圖等)則要依靠數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)來表示，運算效率可能有明顯的差異。 設(shè)計一個好的算法。而好的算法在 構(gòu)及存儲方式。 (2)電話號碼表的結(jié)構(gòu)和存儲方式?jīng)Q定了查找(算法)的效率。 (1)一個程序不一定滿足有窮性，但算法一定。 (3)一個算法若用機器可執(zhí)行的語言來描述，則它就是一個程序。/62精品資料精品學(xué)習(xí)資料第1頁，共62頁算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，記作T(n)=O(f(n))，稱O(f(n))為算法的漸近時間復(fù)雜度，簡稱時間復(fù)雜度。算法效率的度量，采用時n)22n立方階O(n3)k次方階O(nk)for(i=1;i<n;i++){y=y+1;//語句1forjjnj)//語句21頻度為(n-1)；語句2頻度為(n-1)*(2n+1)=2n2-n-1，因此時間復(fù)雜度T(n)=2n2-2=O(n2)。i=1;//語句1while(i<=n)i=i*2;//語句2因此時間復(fù)雜度T(n)=1+log2n=O(log2n)。2/62精品資料精品學(xué)習(xí)資料第2頁，共62頁線性表的概念和運算對于非空的線性表，有且僅有一個開始結(jié)點和一個終端結(jié)點；開始結(jié)點沒有直接前趨，有且僅有一個端結(jié)點沒有直接后繼，有且僅有一個直接前趨；其余任何結(jié)點有且僅有一個直接前趨和一個(1)置空表SETNULL(L)：將線性表L置為空表。(2)求長度LENGTH(L)：返回是線性表L中結(jié)點的個數(shù)。(3)取結(jié)點GET(L,i)：當(dāng)1≤i≤LENGTH(L)時，返回線性表L中的第i個結(jié)點，否則返回(4)定位LOCATE(L,x)：當(dāng)線性表L中存在一個值為x的結(jié)點時，結(jié)果是該結(jié)點的位置；若表L中存在多個值為x的結(jié)點，則返回首次找到的結(jié)點位置；若表L中不存在值為x的結(jié)點，則返回一個特殊值表示值為x的結(jié)點不存在。(5)插入INSERT(L,x,i)：在線性表L的第i個位置插入一個值為x的新結(jié)點。這里1≤i≤n+1，n是原表L的長度。性表的存儲結(jié)構(gòu) (1)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。簡言之，邏輯上相鄰，物理上也相鄰。 a長度)為L字節(jié)，則地址計算公式：LOC(ai)=LOC(a1)+(i-1)*L。 #defineMAXSIZE1024typedefintdatatype;typedefstruct{//線性表的最大長度//線性表數(shù)據(jù)元素類型atypeequenlistdata[MAXSIZE];//指示線性表的終端結(jié)點在表中的下標(biāo)值3/62精品資料精品學(xué)習(xí)資料第3頁，共62頁 元存放邏輯上相鄰的元素，每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息。 頭指針是指向鏈表中第一個結(jié)點(或為頭結(jié)點或開始結(jié)點)的指針，單鏈表可由一個頭指針唯一確定。頭結(jié)點是在鏈表的開始結(jié)點之前附設(shè)的一個結(jié)點；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息；開始結(jié)點是指鏈表中存儲線性表第一個數(shù)據(jù)元素a1的結(jié)點。 針域為空時表示空表。 typedefintdatatype;//線性表數(shù)據(jù)元素類型typedefstructnode{datatypedata據(jù)域structnode*next;//指針域linklist 順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一)；要求內(nèi)存中可用存儲單元的地址 voidfindValue(Linklist*head,intx){Linklist*t;t=head->next;while(t!=NULL&&t->data!=x)t=t->next;if(t->data==x)printf成功找到\n");printf沒有找到\n");} voidinsert(Linklist*head,intx){4/62精品資料精品學(xué)習(xí)資料第4頁，共62頁p=(Linklist*)malloc(sizeof(Linklist));xt=head;while(t->next!=NULL&&t->next->data<x)t=t->next;pnexthead>next;extp}elseif(t->next==NULL){t->next=p;extNULLpnexttnextt->next=p;}} voiddele(LinklisteadLinklistwhile(p->next!=NULL){ifpdatap>next->data)p=p->next;q=p->next;p->next=q->next;free(q);}}} voidreverse(Linklist*head){Linklist*s,*t,*p;pnextwhile(s->next!=NULL)nextsnext=p;}s->next=p;head->next->next=NULL;headnext=s;5/62精品資料精品學(xué)習(xí)資料第5頁，共62頁2.3例題設(shè)存儲數(shù)組元素M[O]的第一個字節(jié)的地址是98，則M[3]的第一個字節(jié)的地址是113。niinni個元素(或刪除第i個元素，需要向前移動n-i個元素)。ssdatasdatat;qpnextpnextqnextfree(q);q=p->next;p->data=q->data;p->next=q->next;free(q);基本概念 鏈棧typedefintdatatype;typedefintdatatype;#defineMAXSIZE100typedefstructnode{typedefstruct{datatypedata;datatypedata[MAXSIZE];structnode*next;inttop;}linkstack;}seqstack;linkstack*top;seqstack*s;top是棧頂指針，它唯一地確定一個鏈棧。 intEMPTY(seqstack*s){return(!s–>top>=0);6/62精品資料精品學(xué)習(xí)資料第6頁，共62頁} voidSETNULL(seqstack*s){s–>top=-1;} intFULL(seqstack*s){opMAXSIZE} seqstack*PUSH(seqstack*sifFULLsreturns;} “stackoverflow”);returnNULL;}–>data[s–>top]=x;datatypePOP(seqstack*s){if(EMPTY(s)){printf(“stackunderflow”);}return(s–>data[s–>top+1]);} datatypeTOP(seqstack*s){if(EMPTY(s)){kis}return(s–>data[s–>top]);} linkstack*PUSHLSTACK(linkstack*top,datatypex){linkstack*p;returnp;/*返回新棧頂指針*/} linkstack*POPLSTACK(linkstack*top,datatype*datap){7/62精品資料精品學(xué)習(xí)資料第7頁，共62頁{printf(“underflow”);returnNULL;}epreturntop;/*返回新棧頂指針*/}ue先進先出(FIFO)的特點。 #defineMAXSIZE100typedefstructtypedefstruct{queuenode{datatypdatatypedata[MAXSIZE];edata;intfront;structqueuenode*next;intrear;}QueueNode;}sequeue;typedefstruct{sequeuesqQueueNode*front;QueueNode*rear; 無法重新利用。盡管隊 8/62精品資料精品學(xué)習(xí)資料第8頁，共62頁sq->front=(sq->front+1)%maxSizesqrear-sq->front+maxSize)%maxSize ①檢查隊列是否已滿，若隊滿，則進行溢出錯誤處理。②將隊尾指針后移一個位置(即加1)，指向下一單元。StatusEnQueue(SqQueue*Q,ElemTypee){if((Q->rear+1)%MAXQSIZE==Q->front)return(ERROR);//隊滿上溢earQrearMAXQSIZEQ->data[Q->rear]=e;} ①檢查隊列是否為空，若隊空，則進行下溢錯誤處理。②將隊首指針后移一個位置(即加1)。atusDeQueueSqQueueQifQrearQ>front)returnNULL/隊空下溢ntQfrontMAXQSIZE} Q->front=Q->rear=MAXQSIZE-1; datatypeGetHead(SqQueue*Q){if(Q->front==Q->rear)return(NULL);//隊空QdataQfrontMAXQSIZE} intQueueEmpty(SqQueue*Q){if(Q->front==Q-rear)return(True); voidInitQueue(LinkQueue*Q){Q.front=Q.rear=(queuenode*)malloc(sizeof(queuenode));9/62精品資料精品學(xué)習(xí)資料第9頁，共62頁Q.front->next=Q.rear->next=NULL;} intQueueEmpty(LinkQueue*Q){return(Q.front->next==NULL&&Q.rear->next==NULL);} voidEnQueue(LinkQueue*Q,datatypex){QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));Q->rear–>next=p;Q->rear=p;} nkqueueQlinkqueue*p;atypexpQ->front->next;Qfrontnextp>next;ifpnextNULLQ->rear=Q->front;x=p->data;freep);}和隊列的應(yīng)用CTintnreturn(n*FACT(n-1));}/62精品資料精品學(xué)習(xí)資料第10頁，共62頁 (1)中綴表示法計算機系統(tǒng)在處理表達式時，從左到右依次讀出表達式中的各個符號(操作ch是操作數(shù)，則將其壓入操作數(shù)棧ch繼續(xù)與OPTR棧頂元素入素 (2)波蘭表示法和逆波蘭表示法以5+(6–4/2)*3為例，波蘭表示法：+5*-6/423逆波蘭表示法：5642/-3*+?？稍O(shè)置一個棧，從左到右掃，每讀到一個操作數(shù)就將其壓入棧中；每讀到一個運算符時，則從棧頂取出兩個操#include<stdio.h>#definemaxsize100typedefintdatatype;typedefstruct{datatypedatamaxsizetatypetoptackqstacksvoidbuild();voidpush();voidpop();intcheck(charss[]);voidmain(){harssmaxsizeprintf("請輸入要測試的算數(shù)表達式:");scanf("%s",ss);if(check(ss)==-1)printf("算數(shù)表達式匹配!");}voidbuild(){s=(seqstack*)malloc(sizeof(seqstack));s->top=-1;}11/62精品資料精品學(xué)習(xí)資料第11頁，共62頁eckcharsswhile(ss[i]!=ielseifssi==')')}#include<stdio.h>#include<stdlib.h>#include<string.h>#definemaxsize100urnstop}voidpush(){s>top++;}voidpop(){}\\n");}returnstq->data[stq->front++];}typedefstruct{chardatamaxsizektypedefstruct{chardatamaxsizeintisempty_queue(queue*stq){returnstq->front==stq->rear;}voidinqueue(queue*stq,charvalue){ifisfull_queue(stq)){printf("隊列已滿，無法入隊\n");}stq->data[stq->rear++]=value;}stack*init_stack(){stack*tmp=(stackzeofstacktmp->top=0;}intisfull_queue(queue*stq){returnstq->rear>=maxsize-1;}intisempty_stack(stack*stk){returnstk->top==0?1:0;}queue*init_queue(){queue*tmplocsizeofqueuetmp->front=tmp->rear=0;}chardequeue(queue*stq){if(isempty_queue(stq)){=intisfull_stack(stack*stk){returnstk->top>=maxsize-1?1:0;}charpop(stack*stk){if(isempty_stack(stk)){printf("堆棧為空，無法出棧\n");xit}/62精品資料精品學(xué)習(xí)資料第12頁，共62頁returnstkdatastktop];}voidpush(stack*stk,charvalue){if(isfull_stack(stk)){printf("堆棧已滿，無法入棧\n");xit}stk->data[stk->top++]=value;}voidcompare(stack*stk,queue*stq,charstr[],intlen){lagchartemp_stack;chartemp_queue;for(i=0;i<len;i++){push(stk,str[i]);inqueue(stq,str[i]);}for(i=0;i<len;i++){temp_stack=pop(stk);temp_queue=dequeue(stq);if(temp_stack!=temp_queue){flag=1;}}if(}queue*stq=init_queue();stackstk=init_stack();charc[maxsize],s;rintfnscanf("%c",&s);while(s!='@'){isscanf("%c",&s);}ci]='\0';compare(stk,stq,c,strlen(c)-1);}3.3例題解：和普通線性表相比，對插入、刪除運算加以限制。一般的一維數(shù)組隊列的尾指針已經(jīng)到了數(shù)組的空位置，為了解決這種問題，就要引入循環(huán)隊列。/62精品資料精品學(xué)習(xí)資料第13頁，共62頁第四章串4.1串的基本概念tring空白串和空串g“”4.2串的存儲結(jié)構(gòu)#defineMAXSTRLEN256chars[MAXSTRLEN];typedefstruct{char*ch;//若是非空串,則按串長分配存儲區(qū),否則ch為NULLintlength;//串長度}HString; intstrlen(HStrings){returns.length;} Statusclearstring(HStrings){/62精品資料精品學(xué)習(xí)資料第14頁，共62頁{free(s.ch);s.ch=NULL;}length} //生成一個其值等于串常量chars的串trsfree(t.ch);//釋放原空間i=strlen(chars);//求串長{t.ch=NULL;t.length=0;}//空串//申請存儲sizeof//申請存儲Wfor(j=0;j<i;j++)t.ch[j]=chars[j];//復(fù)制t.length=i;}} intstrcmp(HStrings,HStringt){STST返回值0;S<T,返回值<0} Statusstrcat(HStringt,HStrings1,HStrings2){if(!(t.ch)=(char*)malloc(s1.length+s2.length)*sizeof(char)))exit(OVERFLOW);for(j=0;j<s1.length;j++)t.ch[j]=s1.ch[j];for(k=0;k<s2.length;k++)t.ch[j+k]=s2.ch[k];t.length=s1.length+s2.length;} //用Sub返回串S的第pos個字符起長度為len的子串Statussubstr(HStringsub,HStrings,intpos,intlen){if(pos<1||pos>s.length||len<0||len>s.length-pos+1)returnERRORbchfree(sub.ch);//釋放舊空間/62精品資料精品學(xué)習(xí)資料第15頁，共62頁{sub.ch=NULL;sub.length=0;}//sub.ch=(char*)malloc(len*sizeof(char));for(j=0;j<len;j++)sub.ch[j]=s.ch[pos-1+j];slengthlen}}typedefstructstructnode*next;string#defineCHUNKSIZE80typedefstructChunkcharch[CUNKSIZE];//可由用戶定義的塊大小，實際中根據(jù)需要設(shè)置大小//結(jié)點結(jié)構(gòu)structChunk*next;typedefstruct{l//串的當(dāng)前長度4.3串的基本運算值：strassign(S,T)，表示將T串的值賦給S串。2.聯(lián)接：strcat(T1,T2)，表示將T1串和T2串聯(lián)接起來，組成一個新的T1串。T4.子串：substr(S,i,len)，表示截取S串中從第i個字符開始連續(xù)len個字符，構(gòu)成一個新串(顯然該新串是S串的子串插入：strinsert(S,i,T)，在S串的第i個位置插入T串。indexSTTS中首次出現(xiàn)的位置，若T串不是S串的子串，則位置為9.串替換：replace(S,T1,T2)，用串T2替換串S中出現(xiàn)的所有子串T1。配1.BF算法/62精品資料精品學(xué)習(xí)資料第16頁，共62頁 相等。返回將主串的第pos個字符和模式的第1相等。返回的下一字符(pos+1)起，重新與第一個字符比較。直到主串的一個連續(xù)子串字符序列與模式。ST，返回值0。 intS_index(SStringt,SStringp,intpos){intn,m,i,j;m=strlen(t);n=strlen(p);for(i=pos-1;i<=m-n;i++){for(j=0;j<n&&t[i+j]==p[j];j++);if(j==n)return(i+1);}}2.*KMP算法 (略)4.5例題為mtSindexSStringsSStringt的子串，求子串t在主串s中首次出現(xiàn)位置的算法。找到返回下標(biāo)(>=1)，否則返回0;串類型為SStringfor(i=0;i<=m-n;i++){for(j=0;j<n&&s[i+j]==t[j];j++);ni}}數(shù)組的定義typedefelemtypearray2[m][n];/62精品資料精品學(xué)習(xí)資料第17頁，共62頁typedefelemtypearray1[n];typedefarray1array2[m];組的存儲方式①開始結(jié)點的存放地址(即基地址)。②維數(shù)和每維的上、下界。每③個數(shù)組元素所占用的單元數(shù)L。設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。殊矩陣 在一個n階方陣A中，若元素滿足下述性質(zhì)： aa21a22a31a32a33n1n2n3nnn1n2n3nnnnn若i≥j，則aij在下三角矩陣中。aij之前的i行(從第0行到第i-1行)一共有1+2++i=i*(i+1)/2個元素，在第i行上aij之前恰有j個元素(即ai0,ai1,ai2,,aij-1)，因此：可 以主對角線劃分，三角矩陣有上三角和下三角。上三角矩陣：它的下三角(不包括主對角線)中的/62資料精品學(xué)習(xí)資料第18頁，共62頁 三角矩陣中的重復(fù)元素c可共享一個存儲空間，其余的元素正好有n(n+1)/2個，因此，三角矩陣可壓縮存儲到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個分量中。時，aij在上三角部分中，前面共有i行，共有n+n-1+n-2++n-(i-1)=i*n-i*(i-1)/2=i*(2n-i+1)/2下三角矩陣的存儲和對稱矩陣用下三角存儲類似，a00=sa[0],a10=sa[1],a11=sa[2],，3.對角矩陣(三對角矩陣為例) 非零元素僅出現(xiàn)在主對角線(aii,0≤i≤n-1)上，緊鄰主對角線上面的那條對角線上(aii+1,0≤i≤n-2)和緊鄰主對角線下面的那條對角線上(ai+1i,0≤i≤n-2)。顯然，當(dāng)|i-j|>1時，元素aij=0。在一個n*n的三對角矩陣中，只有(n-1)+n+(n-1)個非零元素，故只需3n-2個存儲單元，零元已不占用存aij陣及存儲為e≤0.05時稱矩陣A為稀疏矩陣。A((0,1,12),(0,2,9),(2,0,-3),——矩陣的行數(shù)、列數(shù)及非零元數(shù)(3,2,24),(4,1,18),(5,0,15),/62精品資料精品學(xué)習(xí)資料第19頁，共62頁假設(shè)以順序存儲結(jié)構(gòu)來表示三元組表，則可得到稀疏矩陣的一種壓縮存儲方法——三元順序表。其定#definemaxsize1000typedefintdatatype;typedefstruct{inti,j;/*datatypev/*riplettypedefstruct{tripletdata[maxsize];}tripletable;/*稀疏矩陣類型*/ijv01122920-3Mi62532415053-73.三元組順序表的轉(zhuǎn)置B是一個n×m的矩陣，且a[i][j]=b[j][i]a.data置換為表B的三元組表b.data，如果只是簡單地交換a.data 即按mb中三元組次序依次ma中找到相應(yīng)的三元組進行轉(zhuǎn)置。為找M中每一列所有非零元素，是序。20/62精品資料精品學(xué)習(xí)資料第20頁，共62頁TnOMntOnttm*n同數(shù)量級，則T(n)=O(m*n)。由此可見，進行轉(zhuǎn)置運算時，雖然節(jié)省了存儲單元，卻大大增加了時間復(fù)雜度。 個即按ma中三元組次序個Mcpot[col]colMcol元個數(shù)。 typedefstructnode{intcol;intval;structnode*link;typedefstructnode*TD;21/62精品資料精品學(xué)習(xí)資料第21頁，共62頁5.十字鏈表 一個非零元。 tpedefstructnode{introw,col,val;structnode*down,*right;5.5廣義表原子)。廣義表是n≥0個元素a0,a1,,an-1的有限序列，其中每一個ai或者是原子，或者是一個廣義。稱第一個元素a0為廣義表GL的表頭，其余部分(a1,...an-1)為GL的表尾，分別記作：head(GL)=a0，tail(GL)=(a1,...an-1)。廣義表是多層次結(jié)構(gòu)。舉例，，，，A為空表，長度為0。，B是長度為2的廣義表，第一項為原子，第二項為廣義表。，C是長度為3的廣義表，每一項都是原子。D是長度為2的廣義表，每一項都是上面提到的廣義表。E是長度為2的廣義表，第一項為原子，第二項為它本身。 head(LS)=a1。取表頭運算得到的結(jié)果，head(((a1,a2),(a3,a4),a5))=(a1,a2)。22/62精品資料精品學(xué)習(xí)資料第22頁，共62頁若廣義表LS=(a1,a2,,an)，則tail(LS)=(a2,a3,,an)。即取表尾運算得到的結(jié)果是除表 ①.GetTail【(b,k,p,h)】＝(k,p,h);【((a,b),(c,d))】＝(a,b);④.GetTail【((a,b),(c,d))】＝((c,d));【(())】＝();。廣義表的存儲結(jié)構(gòu)通常采用鏈接存儲方法來存儲廣義表中元素，并稱之為廣義鏈表。1.結(jié)點的表示Tagdata/sublistlink若tag=0表示該結(jié)點為原子結(jié)點，第二個域data存放相應(yīng)原子元素的信息。若tag=1為子表結(jié)點，第二個域為sublist存放相應(yīng)子表第一個元素對應(yīng)的結(jié)點的地址。link存放本元素同一層的下一個元素所在鏈結(jié)點的地址。efstructstructnode*sublist;chardatastructnode*link;E k 的鏈接方法，這種鏈接方法在進行元素的5.7例題A[0..8]23/62精品資料精品學(xué)習(xí)資料第23頁，共62頁單元中，則元素a[5][5]的地址為。aA]的元素起始地址是LOC(A[0][0])=4000，每個元素占2個字節(jié)，則按行優(yōu)先次序存儲時LOC(A[3][3])為多少？，tail[B]=((c,d))，head[head[head[tail[C]]]]=a。6.1樹Tm(1)在非空樹中至少有一個結(jié)點——根結(jié)點的度：分支個數(shù)(結(jié)點擁有的子樹個數(shù))。結(jié)點的層次：假設(shè)根結(jié)點的層次為1，根的孩子就在第2層，一個結(jié)點在第l層，則其子樹的根結(jié)24/62精品資料精品學(xué)習(xí)資料第24頁，共62頁有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。二叉樹二叉樹是n(nN0)個結(jié)點的有限集，1)每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)。右之分，且其次序不能任意顛倒。3.性質(zhì) (1)在二叉樹的第i層上至多有2i-1個結(jié)點(iN1)。 (3)任何一棵二叉樹，若葉子結(jié)點個數(shù)為n0，度為2的結(jié)點數(shù)為n2，則必存在關(guān)系式：n0=n2+1。 (4)具有n個結(jié)點的完全二叉樹的深度為[log2n]+1。 (5)若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結(jié)點：有②若2i>n，則該結(jié)點無左孩子，如果2i<n，編號為2i的結(jié)點為其左孩子結(jié)點。③若2i+1>n，則該結(jié)點無右孩子，如果2i+1<n，編號為2i+1的結(jié)點為其右孩子結(jié)點。 25/62精品資料精品學(xué)習(xí)資料第25頁，共62頁定義：指的是深度為k且含有2k-1個結(jié)點的二叉樹。 定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至 typedefstructnode{datatypedata;structnode*lchild,*rchild;reetypedefstruct{datatypedata;detypedefstruct{pNodetnode[MAXSIZE];ee26/62精品資料精品學(xué)習(xí)資料第26頁，共62頁typedefstructnode{intchild;//孩子結(jié)點序號structnode*next;//孩子鏈表結(jié)點ktypedefstructtnode{datatypedata;//樹結(jié)點數(shù)據(jù)域link*headptr;//孩子鏈表頭指針treectreeT[MAXSIZE];弟結(jié)點。typedefstructnode{fsondatanextdatatypedata;structnode*fson,*next;叉樹和線索二叉樹遍歷一棵非空二叉樹，可分解為：訪問根結(jié)點D；遍歷左子樹L；遍歷右子樹R。因此有三種遍歷方法，分別是先序(根)遍歷(DLR)、中序(根)遍歷(LDR)和后序(根)遍歷(LRD)。 voidpreorder(bitree*t){iftNULL{27/62精品資料精品學(xué)習(xí)資料第27頁，共62頁printfdtt>data);rdertlchildrdertrchild}} voidpreorderbitree*t){}} voidpreorderbitree*t){}} 28/62精品資料精品學(xué)習(xí)資料第28頁，共62頁 遍歷序列。遍歷二叉樹是以一定的規(guī)則將二叉樹中的結(jié)點排列成一個線性序列,這實質(zhì)上是對一個非線性結(jié)構(gòu)fb但是，當(dāng)以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)時，要找到結(jié)點的前驅(qū)或后繼就不方便了。為此，引入線索二叉樹。我們發(fā)現(xiàn)，在含有n個結(jié)點的二叉樹中有n-1條邊指向其左、右孩子，意味著n個結(jié)點的二叉nnn針域是空的。可充分利用這些空指針來存放結(jié)點的線 兩個相鄰的結(jié)點互稱為前驅(qū)與后繼。。：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫線索化。 ①若結(jié)點有左子樹，則其lchild域指向其左孩子，否則令lchild域指向其直接前驅(qū)；②若結(jié)點有右子樹，則其rchild域指向其右孩子，否則令rchild域指向其直接后繼。 typedefstructnode{datatypedata;lchildltaggrtagrchild29/62精品資料精品學(xué)習(xí)資料第29頁，共62頁agltag=1structnode*lchild,ghptrrtag=16.6樹(森林)與二叉樹的轉(zhuǎn)換30/62精品資料精品學(xué)習(xí)資料第30頁，共62頁31/62精品資料精品學(xué)習(xí)資料第31頁，共62頁32/62精品資料精品學(xué)習(xí)資料第32頁，共62頁33/62精品資料精品學(xué)習(xí)資料第33頁，共62頁曼樹及哈夫曼編碼 個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑。 (2)路徑長度：路徑上的分支數(shù)。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為 (3)結(jié)點的路徑長度：從根結(jié)點到該結(jié)點的路徑上分支的數(shù)目。 (4)樹的路徑長度：樹中每個結(jié)點的路徑長度之和。 (5)結(jié)點的帶權(quán)路徑長度：從該結(jié)點到樹根的路徑長度與結(jié)點上權(quán)的乘積。 (6)樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和(其中Wk為權(quán)值，lk為結(jié)點到根的路徑長度路徑長度)WPLWL。KKKk樹(最優(yōu)二叉樹)。W1,W2,,Wn的二叉樹中，帶權(quán)路徑長度曼。WPL=7*1+5*2+2*3+4*3=35。(1)將w1,w2,,wn看成是有2)在森林中選出兩個根結(jié)點的刪除選取的兩棵樹n棵樹的森林(每棵樹僅有一個結(jié)點)；權(quán)值最小的樹合并，作為一棵新樹的左、右子樹；，且新樹的根結(jié)34/62精品資料精品學(xué)習(xí)資料第34頁，共62頁)步，直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。假設(shè)給定的葉子結(jié)點的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹過程如下所示：6.9例題一。nmm2結(jié)點數(shù)=結(jié)點數(shù)-1)例3：在一棵度為3的樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為6個。(公式：度數(shù)之和=結(jié)點數(shù)+1)35/62精品資料精品學(xué)習(xí)資料第35頁，共62頁LDR:BFJDGKACHELIM為為B，左子樹的右子樹的中序GEC，右子樹的左子樹的中序HF (注：首先將二叉樹分割為孤立的二叉樹，再將每個孤立的二叉樹轉(zhuǎn)換為樹)36/62精品資料精品學(xué)習(xí)資料第36頁，共62頁 (注：所有兄弟之間連線，然后刪除除左孩子之間的連線以外的所有其他連線) 左孩子，則指向左孩子，否則指向直接前驅(qū)；如果存在右孩子，則指向右孩子，W并求其37/62精品資料精品學(xué)習(xí)資料第37頁，共62頁第七章圖1.圖圖G由一個非空項點集V和一個頂點間的關(guān)系集合E(邊的集合)組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元有向邊也稱為弧,x為弧尾,y為弧頭,則<x,y>表示為一條弧,而<y,x>表示y為弧尾,x為弧頭的另一條弧。n。eG1=(V1,E1)中：vIDvODvV1={v1,v2,v3,v4,v5}。Evvvv,(v2,v3),(v2,v5),(v3,v4),(v3,v5)}。DvDv3,D(v3)=3,D(v4)=2,D(v5)=2例2：在G2=(E2,V2)中：Va,b,c,d}Eabac<c,d>,<d,a>}DaIDaODa,DbIDbODb,DcIDcODc2,DdIDdODd。5.子圖(Subgraph)圖V38/62精品資料精品學(xué)習(xí)資料第38頁，共62頁例如上圖v1tv2tv5與v1tv4tv3tv5是從頂點v1到頂點v5的兩條路徑，路徑長度分別為2和3。例如上圖atctdta為簡單回路或簡單環(huán)。通分量無向圖的極大連通子圖稱為G的連通分vi到頂點vjvi到頂點vj連12023(a)有向圖G中的極大強連通子圖稱為G的強連通分量。顯然，強連通圖只有一個強連通分量，即本G的生成樹，是G的包含其全n個頂占的一個極小連通子圖。它必定包含且僅包含G的n-1在非連通圖G中，由每個連通分量都可以得到一個極小連通子圖~一棵生成樹。這些連通分量的生成生成森林。圖的存儲 表示ij元素值為1，否則為0。39/62精品資料精品學(xué)習(xí)資料第39頁，共62頁 #definen6#definee8/*typedefcharvextype;/*typedeffloatadjtype;typedefstruct{vextypevexs[n];adjtypearcsn][n];O(n×n)O(n×n)/*圖的頂點數(shù)*//*圖的邊數(shù)*/頂點的數(shù)據(jù)類型*//*權(quán)值類型*//*存儲頂點信息*/~存儲邊的信息*/*圖的定義*/ 40/62精品資料精品學(xué)習(xí)資料第40頁，共62頁所示。 鄰接矩陣方便。 typedefcharvextype;typedefstructtadjvexstructnode*next;dgenodetypedefstruct{vertypevertex;edgenode*link;vexnodegan];/*頂點的數(shù)據(jù)類型*//*鄰接點域*//*權(quán)值域*//*頂點表結(jié)點*//*/*3.比較 鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。 頂點編號無關(guān))。On復(fù)雜度為O(n+e)。 圖的遍歷記錄每個頂visited[0..n-141/62]來標(biāo)志某個頂點是否被訪問過，未訪問的值精品資料精品學(xué)習(xí)資料第41頁，共62頁。 首先訪問頂點vi，并將其訪問標(biāo)志置為訪問過，即visited[i]=1；visitedj1，然后從vj開始重復(fù)此過程；若vj已訪問，再看與vi有邊相連的其它頂點； voiddfs(inti)tjvisit(i);visited[i]=1;//從頂點i出發(fā)遍歷//輸出訪問頂點//全局?jǐn)?shù)組訪問標(biāo)記置1表示已經(jīng)訪問for(j=1;j<=n;j++)if((A[i][j]==1)&&(!visited[j]))fsj}1出發(fā)的深度優(yōu)先搜索遍歷過程，其中實線表示下一層遞歸調(diào)用，虛線表示遞歸調(diào)用的返1的遍歷結(jié)果為1,2,4,8,5,6,3,7。 voiddfsl(inti){edgenode*p;visit(gl[i].vertex);visted[i]=1;p=gl[i].link;while(p!=NULL){if(!visited[p->adjvex])dfsl(p->adjvex);}}//輸出訪問頂點//全局?jǐn)?shù)組訪問標(biāo)記置為1表示已訪問i//依次搜索Vi+1的鄰接點//找Vi+1的下一個鄰接點42/62精品資料精品學(xué)習(xí)資料第42頁，共62頁描述從頂點7出發(fā)的深度優(yōu)先搜索遍歷，其中實線表示下一層遞歸，虛線表示遞歸返回，箭頭旁邊數(shù)字表示調(diào)用的步驟。從頂點7出發(fā)的深度優(yōu)先搜索遍歷序列：7,3,1,2,4,8,5,6。2.廣度優(yōu)先搜索遍歷(BFS) 首先訪問頂點i，并將其訪問標(biāo)志置為已被訪問，即visited[i]=1； //從頂點Vk+1出發(fā)廣度優(yōu)先搜索圖g，圖g用鄰接矩陣表示，visited為訪問標(biāo)志向量inti,j;ULLQvisited[k]=1;ENQUEUE(Q,K);while(!EMPTY(Q)){i=DEQUEUE(Q);//設(shè)置空隊列Q//訪問出發(fā)點Vk+1//標(biāo)記置1表示已經(jīng)訪問//已訪問過的頂點入隊列//隊頭元素出隊列for(j=0;j<n;j++)if((g.arcs[i][j]==1)&&(!visited[j])){tedj}}}43/62精品資料精品學(xué)習(xí)資料第43頁，共62頁若從頂點1出發(fā)，廣度優(yōu)先搜索序列為：1，2，3，4，5，6，7，8若從頂點3出發(fā)，廣度優(yōu)先搜索序列為：3，1，6，7，2，8，4，5 voidbfsl(intk){odepvisited[k]=1;ENQUEUE(Q,k);while(!EMPTY(Q)){i=DEQUEUE(Q);ilinkwhile(p!=NULL){if(!visited[p->adjvex]){//設(shè)置空隊列Q//隊頭元素出隊列取Vk+1的邊表頭指針//依次搜索Vk+1的鄰接點dpadjvexENQUEUE(Q,p->adjvex);//訪問過的頂點入隊}ext}}}Vi+1的下一個鄰接點1出發(fā)，廣度優(yōu)先搜索序列為：1，2，3，4，5，6，7，87出發(fā)，廣度優(yōu)先搜索序列為：7，3，8，1，6，4，5，2最小生成樹連通圖G的一個極小連通子圖，它含有圖中n個頂點，但只有n-1條邊。由深度優(yōu)先搜索遍廣度優(yōu)先生成樹(BFS生成樹)。44/62精品資料精品學(xué)習(xí)資料第44頁，共62頁V出發(fā))0 ②必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點； 45/62精品資料精品學(xué)習(xí)資料第45頁，共62頁： (3)克魯斯卡爾Kruskar算法①假設(shè)G=<V,E>是連通圖，則令最小生成樹的初始狀態(tài)為只有n個頂點而無邊的非連通圖T=<V,{}>。T46/62精品資料精品學(xué)習(xí)資料第46頁，共62頁路徑定義：給定一個出發(fā)點(單源點)和一個有向網(wǎng)G=(V,E),求出源點到其它各頂點之間的最短路徑。 ②按最短路徑長度遞增的順序逐個把W中的頂點加到S中，直到S中包含全部頂點，而W為W④此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，W中的頂?shù)木嚯x從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度點 ②從U中選取一個距離最小的頂點k，把k加入到S中。 ∞∞∞∞∞∞47/62精品資料精品學(xué)習(xí)資料第47頁，共62頁VSvvvvvvvvvv,v5>vvv4,v3,v5} ①設(shè)置一個n*n的矩陣A(k)，其中除對角線的元素都等于0外，其他元素a(k)[i][j]表示頂點i到頂點。 ①第一步，讓所有邊上加入②第二步，讓所有邊上加入③如此進行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為所求的結(jié)果，A(n)[i][j]表示頂點i到頂點j的OV網(wǎng)AOVij存在一條有向路徑，稱頂點i是頂點j的前驅(qū)，或者稱頂點j給出有向圖G=(V,E)，對于V中的頂點的線性序列(vi1,vi2,...,vin)，如果滿足如下條件：若在G中從頂點vi到vj有一條路經(jīng)，則在序列中頂點vi必在頂點vj之前；則稱該序列為G的一個拓撲序列為 0的頂點v且輸出之；48/62精品資料精品學(xué)習(xí)資料第48頁，共62頁 (1)C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8(2)C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8注：一個AOV網(wǎng)的拓撲序列不是唯一的OE網(wǎng)表示活動的網(wǎng)絡(luò)，簡稱AOE網(wǎng)。以上方右圖為計算過程，關(guān)鍵路徑為：V1tV2tV5tV7tV9V1tV2tV5tV8tV9 7.8例題例1：有8個結(jié)點的無向圖最多有28條邊，最少有7條邊。 (注：無向圖最多需要n(n-1)/2條邊，最少需要n條邊。有向圖最多n(n-1)條邊。)49/62精品資料精品學(xué)習(xí)資料第49頁，共62頁。 (注：生成樹不唯一，但最小生成樹唯一)例5：用普里姆(Prim)算法求具有n個頂點e條邊的圖的最小生成樹的時間復(fù)雜度為Kruskal是O(elog2e)。 (1)每個頂點的入/出度； On；用克Dijkstraa他各頂點間的最短路徑，50/62精品資料精品學(xué)習(xí)資料第50頁，共62頁 ( (1)試著找出網(wǎng)G的最小生成樹，畫出其邏輯結(jié)構(gòu) 用兩種不同的表示法畫出網(wǎng)G的存儲結(jié)構(gòu) (2)鄰接矩陣表示和鄰接表表示。1244898696abcdefg→→→→→→→babcabc49→→→→→→→ecdgbed486^→→^→^egf8→f9^6^51/62精品資料精品學(xué)習(xí)資料第51頁，共62頁)。AB的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這排序voidinsert_sort(inta[],intfor(i=1;i<n;a[i];j=i-1;while((j>=0)&&tempajaj1]=a[j];j--;}aj+1]=temp;}分別進行分別進行tintspan;//增量for(m=0;m<numOfD;m++){span=d[m];//span個小組52/62精品資料精品學(xué)習(xí)資料第52頁，共62頁for(k=0;k<span;k++){for(i=k;i<n-span;i+=span)spanj=i;while(j>-1&&val<a[j])panajj=j-span;}a[j+span]=val;}}}}交換排序voidbublle_sort(inta[],intn){forj=0;j<n-1;j++)foriin1-j;i++)tempai];a[i]=a[i+1];a[i+1]=temp;}}元素只剩一個。此時便為有序序列了。前提：voidquick_sort(inta[],intninti,j=n-1;順序存儲結(jié)構(gòu)。while(i<j){for(;j>i;j--)for(;i<j;i++)}ivala[i]=a[j];break;a[j]=a[i];break;53/62精品資料精品學(xué)習(xí)資料第53頁，共62頁quicksorta,i);quick_sort(a+i+1,n-1-i);}}擇排序圍直至全部記錄voidselect_sort(inta[],intn){for(i=0;i<n-1;i++){min=i;for(j=i+1;j<n;j++)ifa[min]>a[j])min=j;//交換ifmini{t=a[min];amina[i];t}}} n個元素的序列{k1,k2,,kn}，當(dāng)且僅當(dāng)滿足下列關(guān)系時，稱之為堆(Heap)。①ki≤k2i②ki≥k2iki≤k2i+1ki≥k2i+1 voidheap_sort(intdata[],intlength){for(i=(length>>1)-1;i>=0;i--)thforjlengthj0;--j){tempdataj//初始化一個堆54/62精品資料精品學(xué)習(xí)資料第54頁，共62頁dataj=data[0];data]=temp;stdataj}}voidheap_ajust(intdata[],inti,intlength){intnChildnTempfor(nTemp=data[i];2*i+1<length;i=nChild){if(nChild<length-1&&data[nChild+1]>data[nChild])tanChilddatai=data[nChild];datanChild=nTemp;}}//如果比自己的最大的孩子小，就交換//如果比最大的孩子還大，就不交換.4歸并排序voidmerge_sort(inta[],intlow,inthigh){highgesortalowmidmergesortamidhigh;gealowmidhigh}}voidmerge(intarr[],intlow,intmid,inthigh){kint*tmp=(int*)malloc((high-low+1)*sizeof(int));lowghmidintrightlowmid+1;ighhighfor(k=0;left_low<=left_high&&right_low<=right_high;k++){ifarrleftlowarrrightlowtmp[k]=arr[left_low++];tmp[k]=arr[right_low++];55/62精品資料精品學(xué)習(xí)資料第55頁，共62頁if(left_low<=left_high)//若第一個序列有剩余，直接復(fù)制出來粘到合并序列尾for(i=left_low;i<=left_high;i++)tmp[k++]=arr[i];if(right_low<=right_high)//若第二個序列有剩余，直接復(fù)制出來粘到合并序列尾for(i=right_low;i<=right_high;i++)tmp[k++]=arr[i];for(i=0;i<high-low+1;i++)rrlowitmpifree(tmp);}}基數(shù)排序voidradix_sort(int*a,intn,intd){for(i=0;i<=d;i++)count_sort(a,n,i);}intcount_sort(int*array,intn,intd){intk[MAXK]={0};ttempbtemp=(int*)malloc(sizeof(int)*n);b=(int*)malloc(sizeof(int)*n);if(NULL==temp)return0;for(i=0;i<n;i++)b[i]=get_value(array[i],d);for(i=0;i<n;i++)ifor(i=1;i<10;i++)k[i]+=k[i-1];for(i=n-1;i>=0;i--)temp[--k[b[i]]]=array[i];for(i=0;i<n;i++)array[i]=temp[i];free(temp);free(b);}//記錄與數(shù)組下標(biāo)相等的數(shù)值的個數(shù)//儲存自己數(shù)組下標(biāo)數(shù)值在目標(biāo)數(shù)組對應(yīng)的位置//將原數(shù)組按大小順序儲存到另一個數(shù)組tvalueintaintd56/62精品資料精品學(xué)習(xí)資料第56頁，共62頁for(;d>0&&a>0;d--)}8.6例題冒泡排序一趟掃描的結(jié)果是HCQPAMSRDFXY；初始步長為4的希爾(shell)排序一趟的結(jié)果是PACSQDFXRHMY；二路歸并排序一趟掃描的結(jié)果是HQCYAPMSDRFX；快速排序一趟掃描的結(jié)果是FHCDPAMQRSYX；堆排序初始建堆的結(jié)果是ADCRFQMSYPHX。t