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

序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的 (1)邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。 (2)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。 (3)操作：數(shù)據(jù)的運(yùn)算(檢索、排序、插入、刪除、修改)。 (1)計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算(如表、樹(shù)、圖等)則要依靠數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)結(jié)構(gòu)來(lái)表示，運(yùn)算效率可能有明顯的差異。 設(shè)計(jì)一個(gè)好的算法。而好的算法在 構(gòu)及存儲(chǔ)方式。 (2)電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找(算法)的效率。 (1)一個(gè)程序不一定滿足有窮性，但算法一定。 (3)一個(gè)算法若用機(jī)器可執(zhí)行的語(yǔ)言來(lái)描述，則它就是一個(gè)程序。/62精品資料精品學(xué)習(xí)資料第1頁(yè)，共62頁(yè)算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n)，記作T(n)=O(f(n))，稱(chēng)O(f(n))為算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度。算法效率的度量，采用時(shí)n)22n立方階O(n3)k次方階O(nk)for(i=1;i<n;i++){y=y+1;//語(yǔ)句1forjjnj)//語(yǔ)句21頻度為(n-1)；語(yǔ)句2頻度為(n-1)*(2n+1)=2n2-n-1，因此時(shí)間復(fù)雜度T(n)=2n2-2=O(n2)。i=1;//語(yǔ)句1while(i<=n)i=i*2;//語(yǔ)句2因此時(shí)間復(fù)雜度T(n)=1+log2n=O(log2n)。2/62精品資料精品學(xué)習(xí)資料第2頁(yè)，共62頁(yè)線性表的概念和運(yùn)算對(duì)于非空的線性表，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)；開(kāi)始結(jié)點(diǎn)沒(méi)有直接前趨，有且僅有一個(gè)端結(jié)點(diǎn)沒(méi)有直接后繼，有且僅有一個(gè)直接前趨；其余任何結(jié)點(diǎn)有且僅有一個(gè)直接前趨和一個(gè)(1)置空表SETNULL(L)：將線性表L置為空表。(2)求長(zhǎng)度LENGTH(L)：返回是線性表L中結(jié)點(diǎn)的個(gè)數(shù)。(3)取結(jié)點(diǎn)GET(L,i)：當(dāng)1≤i≤LENGTH(L)時(shí)，返回線性表L中的第i個(gè)結(jié)點(diǎn)，否則返回(4)定位LOCATE(L,x)：當(dāng)線性表L中存在一個(gè)值為x的結(jié)點(diǎn)時(shí)，結(jié)果是該結(jié)點(diǎn)的位置；若表L中存在多個(gè)值為x的結(jié)點(diǎn)，則返回首次找到的結(jié)點(diǎn)位置；若表L中不存在值為x的結(jié)點(diǎn)，則返回一個(gè)特殊值表示值為x的結(jié)點(diǎn)不存在。(5)插入INSERT(L,x,i)：在線性表L的第i個(gè)位置插入一個(gè)值為x的新結(jié)點(diǎn)。這里1≤i≤n+1，n是原表L的長(zhǎng)度。性表的存儲(chǔ)結(jié)構(gòu) (1)定義：把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰。 a長(zhǎng)度)為L(zhǎng)字節(jié)，則地址計(jì)算公式：LOC(ai)=LOC(a1)+(i-1)*L。 #defineMAXSIZE1024typedefintdatatype;typedefstruct{//線性表的最大長(zhǎng)度//線性表數(shù)據(jù)元素類(lèi)型atypeequenlistdata[MAXSIZE];//指示線性表的終端結(jié)點(diǎn)在表中的下標(biāo)值3/62精品資料精品學(xué)習(xí)資料第3頁(yè)，共62頁(yè) 元存放邏輯上相鄰的元素，每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息。 頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn))的指針，單鏈表可由一個(gè)頭指針唯一確定。頭結(jié)點(diǎn)是在鏈表的開(kāi)始結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長(zhǎng)等信息；開(kāi)始結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。 針域?yàn)榭諘r(shí)表示空表。 typedefintdatatype;//線性表數(shù)據(jù)元素類(lèi)型typedefstructnode{datatypedata據(jù)域structnode*next;//指針域linklist 順序存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一)；要求內(nèi)存中可用存儲(chǔ)單元的地址 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沒(méi)有找到\n");} voidinsert(Linklist*head,intx){4/62精品資料精品學(xué)習(xí)資料第4頁(yè)，共62頁(yè)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頁(yè)，共62頁(yè)2.3例題設(shè)存儲(chǔ)數(shù)組元素M[O]的第一個(gè)字節(jié)的地址是98，則M[3]的第一個(gè)字節(jié)的地址是113。niinni個(gè)元素(或刪除第i個(gè)元素，需要向前移動(dòng)n-i個(gè)元素)。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是棧頂指針，它唯一地確定一個(gè)鏈棧。 intEMPTY(seqstack*s){return(!s–>top>=0);6/62精品資料精品學(xué)習(xí)資料第6頁(yè)，共62頁(yè)} 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頁(yè)，共62頁(yè){printf(“underflow”);returnNULL;}epreturntop;/*返回新棧頂指針*/}ue先進(jìn)先出(FIFO)的特點(diǎn)。 #defineMAXSIZE100typedefstructtypedefstruct{queuenode{datatypdatatypedata[MAXSIZE];edata;intfront;structqueuenode*next;intrear;}QueueNode;}sequeue;typedefstruct{sequeuesqQueueNode*front;QueueNode*rear; 無(wú)法重新利用。盡管隊(duì) 8/62精品資料精品學(xué)習(xí)資料第8頁(yè)，共62頁(yè)sq->front=(sq->front+1)%maxSizesqrear-sq->front+maxSize)%maxSize ①檢查隊(duì)列是否已滿，若隊(duì)滿，則進(jìn)行溢出錯(cuò)誤處理。②將隊(duì)尾指針后移一個(gè)位置(即加1)，指向下一單元。StatusEnQueue(SqQueue*Q,ElemTypee){if((Q->rear+1)%MAXQSIZE==Q->front)return(ERROR);//隊(duì)滿上溢earQrearMAXQSIZEQ->data[Q->rear]=e;} ①檢查隊(duì)列是否為空，若隊(duì)空，則進(jìn)行下溢錯(cuò)誤處理。②將隊(duì)首指針后移一個(gè)位置(即加1)。atusDeQueueSqQueueQifQrearQ>front)returnNULL/隊(duì)空下溢ntQfrontMAXQSIZE} Q->front=Q->rear=MAXQSIZE-1; datatypeGetHead(SqQueue*Q){if(Q->front==Q->rear)return(NULL);//隊(duì)空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頁(yè)，共62頁(yè)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);}和隊(duì)列的應(yīng)用CTintnreturn(n*FACT(n-1));}/62精品資料精品學(xué)習(xí)資料第10頁(yè)，共62頁(yè) (1)中綴表示法計(jì)算機(jī)系統(tǒng)在處理表達(dá)式時(shí)，從左到右依次讀出表達(dá)式中的各個(gè)符號(hào)(操作ch是操作數(shù)，則將其壓入操作數(shù)棧ch繼續(xù)與OPTR棧頂元素入素 (2)波蘭表示法和逆波蘭表示法以5+(6–4/2)*3為例，波蘭表示法：+5*-6/423逆波蘭表示法：5642/-3*+?？稍O(shè)置一個(gè)棧，從左到右掃，每讀到一個(gè)操作數(shù)就將其壓入棧中；每讀到一個(gè)運(yùn)算符時(shí)，則從棧頂取出兩個(gè)操#include<stdio.h>#definemaxsize100typedefintdatatype;typedefstruct{datatypedatamaxsizetatypetoptackqstacksvoidbuild();voidpush();voidpop();intcheck(charss[]);voidmain(){harssmaxsizeprintf("請(qǐng)輸入要測(cè)試的算數(shù)表達(dá)式:");scanf("%s",ss);if(check(ss)==-1)printf("算數(shù)表達(dá)式匹配!");}voidbuild(){s=(seqstack*)malloc(sizeof(seqstack));s->top=-1;}11/62精品資料精品學(xué)習(xí)資料第11頁(yè)，共62頁(yè)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("隊(duì)列已滿，無(wú)法入隊(duì)\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("堆棧為空，無(wú)法出棧\n");xit}/62精品資料精品學(xué)習(xí)資料第12頁(yè)，共62頁(yè)returnstkdatastktop];}voidpush(stack*stk,charvalue){if(isfull_stack(stk)){printf("堆棧已滿，無(wú)法入棧\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例題解：和普通線性表相比，對(duì)插入、刪除運(yùn)算加以限制。一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的空位置，為了解決這種問(wèn)題，就要引入循環(huán)隊(duì)列。/62精品資料精品學(xué)習(xí)資料第13頁(yè)，共62頁(yè)第四章串4.1串的基本概念tring空白串和空串g“”4.2串的存儲(chǔ)結(jié)構(gòu)#defineMAXSTRLEN256chars[MAXSTRLEN];typedefstruct{char*ch;//若是非空串,則按串長(zhǎng)分配存儲(chǔ)區(qū),否則ch為NULLintlength;//串長(zhǎng)度}HString; intstrlen(HStrings){returns.length;} Statusclearstring(HStrings){/62精品資料精品學(xué)習(xí)資料第14頁(yè)，共62頁(yè){free(s.ch);s.ch=NULL;}length} //生成一個(gè)其值等于串常量chars的串trsfree(t.ch);//釋放原空間i=strlen(chars);//求串長(zhǎng){t.ch=NULL;t.length=0;}//空串//申請(qǐng)存儲(chǔ)sizeof//申請(qǐng)存儲(chǔ)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個(gè)字符起長(zhǎng)度為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頁(yè)，共62頁(yè){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];//可由用戶(hù)定義的塊大小，實(shí)際中根據(jù)需要設(shè)置大小//結(jié)點(diǎn)結(jié)構(gòu)structChunk*next;typedefstruct{l//串的當(dāng)前長(zhǎng)度4.3串的基本運(yùn)算值：strassign(S,T)，表示將T串的值賦給S串。2.聯(lián)接：strcat(T1,T2)，表示將T1串和T2串聯(lián)接起來(lái)，組成一個(gè)新的T1串。T4.子串：substr(S,i,len)，表示截取S串中從第i個(gè)字符開(kāi)始連續(xù)len個(gè)字符，構(gòu)成一個(gè)新串(顯然該新串是S串的子串插入：strinsert(S,i,T)，在S串的第i個(gè)位置插入T串。indexSTTS中首次出現(xiàn)的位置，若T串不是S串的子串，則位置為9.串替換：replace(S,T1,T2)，用串T2替換串S中出現(xiàn)的所有子串T1。配1.BF算法/62精品資料精品學(xué)習(xí)資料第16頁(yè)，共62頁(yè) 相等。返回將主串的第pos個(gè)字符和模式的第1相等。返回的下一字符(pos+1)起，重新與第一個(gè)字符比較。直到主串的一個(gè)連續(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;串類(lèi)型為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頁(yè)，共62頁(yè)typedefelemtypearray1[n];typedefarray1array2[m];組的存儲(chǔ)方式①開(kāi)始結(jié)點(diǎn)的存放地址(即基地址)。②維數(shù)和每維的上、下界。每③個(gè)數(shù)組元素所占用的單元數(shù)L。設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。殊矩陣 在一個(gè)n階方陣A中，若元素滿足下述性質(zhì)： aa21a22a31a32a33n1n2n3nnn1n2n3nnnnn若i≥j，則aij在下三角矩陣中。aij之前的i行(從第0行到第i-1行)一共有1+2++i=i*(i+1)/2個(gè)元素，在第i行上aij之前恰有j個(gè)元素(即ai0,ai1,ai2,,aij-1)，因此：可 以主對(duì)角線劃分，三角矩陣有上三角和下三角。上三角矩陣：它的下三角(不包括主對(duì)角線)中的/62資料精品學(xué)習(xí)資料第18頁(yè)，共62頁(yè) 三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有n(n+1)/2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)到向量sa[0..n(n+1)/2]中，其中c存放在向量的最后一個(gè)分量中。時(shí)，aij在上三角部分中，前面共有i行，共有n+n-1+n-2++n-(i-1)=i*n-i*(i-1)/2=i*(2n-i+1)/2下三角矩陣的存儲(chǔ)和對(duì)稱(chēng)矩陣用下三角存儲(chǔ)類(lèi)似，a00=sa[0],a10=sa[1],a11=sa[2],，3.對(duì)角矩陣(三對(duì)角矩陣為例) 非零元素僅出現(xiàn)在主對(duì)角線(aii,0≤i≤n-1)上，緊鄰主對(duì)角線上面的那條對(duì)角線上(aii+1,0≤i≤n-2)和緊鄰主對(duì)角線下面的那條對(duì)角線上(ai+1i,0≤i≤n-2)。顯然，當(dāng)|i-j|>1時(shí)，元素aij=0。在一個(gè)n*n的三對(duì)角矩陣中，只有(n-1)+n+(n-1)個(gè)非零元素，故只需3n-2個(gè)存儲(chǔ)單元，零元已不占用存aij陣及存儲(chǔ)為e≤0.05時(shí)稱(chēng)矩陣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頁(yè)，共62頁(yè)假設(shè)以順序存儲(chǔ)結(jié)構(gòu)來(lái)表示三元組表，則可得到稀疏矩陣的一種壓縮存儲(chǔ)方法——三元順序表。其定#definemaxsize1000typedefintdatatype;typedefstruct{inti,j;/*datatypev/*riplettypedefstruct{tripletdata[maxsize];}tripletable;/*稀疏矩陣類(lèi)型*/ijv01122920-3Mi62532415053-73.三元組順序表的轉(zhuǎn)置B是一個(gè)n×m的矩陣，且a[i][j]=b[j][i]a.data置換為表B的三元組表b.data，如果只是簡(jiǎn)單地交換a.data 即按mb中三元組次序依次ma中找到相應(yīng)的三元組進(jìn)行轉(zhuǎn)置。為找M中每一列所有非零元素，是序。20/62精品資料精品學(xué)習(xí)資料第20頁(yè)，共62頁(yè)TnOMntOnttm*n同數(shù)量級(jí)，則T(n)=O(m*n)。由此可見(jiàn)，進(jìn)行轉(zhuǎn)置運(yùn)算時(shí)，雖然節(jié)省了存儲(chǔ)單元，卻大大增加了時(shí)間復(fù)雜度。 個(gè)即按ma中三元組次序個(gè)Mcpot[col]colMcol元個(gè)數(shù)。 typedefstructnode{intcol;intval;structnode*link;typedefstructnode*TD;21/62精品資料精品學(xué)習(xí)資料第21頁(yè)，共62頁(yè)5.十字鏈表 一個(gè)非零元。 tpedefstructnode{introw,col,val;structnode*down,*right;5.5廣義表原子)。廣義表是n≥0個(gè)元素a0,a1,,an-1的有限序列，其中每一個(gè)ai或者是原子，或者是一個(gè)廣義。稱(chēng)第一個(gè)元素a0為廣義表GL的表頭，其余部分(a1,...an-1)為GL的表尾，分別記作：head(GL)=a0，tail(GL)=(a1,...an-1)。廣義表是多層次結(jié)構(gòu)。舉例，，，，A為空表，長(zhǎng)度為0。，B是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為廣義表。，C是長(zhǎng)度為3的廣義表，每一項(xiàng)都是原子。D是長(zhǎng)度為2的廣義表，每一項(xiàng)都是上面提到的廣義表。E是長(zhǎng)度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。 head(LS)=a1。取表頭運(yùn)算得到的結(jié)果，head(((a1,a2),(a3,a4),a5))=(a1,a2)。22/62精品資料精品學(xué)習(xí)資料第22頁(yè)，共62頁(yè)若廣義表LS=(a1,a2,,an)，則tail(LS)=(a2,a3,,an)。即取表尾運(yùn)算得到的結(jié)果是除表 ①.GetTail【(b,k,p,h)】＝(k,p,h);【((a,b),(c,d))】＝(a,b);④.GetTail【((a,b),(c,d))】＝((c,d));【(())】＝();。廣義表的存儲(chǔ)結(jié)構(gòu)通常采用鏈接存儲(chǔ)方法來(lái)存儲(chǔ)廣義表中元素，并稱(chēng)之為廣義鏈表。1.結(jié)點(diǎn)的表示Tagdata/sublistlink若tag=0表示該結(jié)點(diǎn)為原子結(jié)點(diǎn)，第二個(gè)域data存放相應(yīng)原子元素的信息。若tag=1為子表結(jié)點(diǎn)，第二個(gè)域?yàn)閟ublist存放相應(yīng)子表第一個(gè)元素對(duì)應(yīng)的結(jié)點(diǎn)的地址。link存放本元素同一層的下一個(gè)元素所在鏈結(jié)點(diǎn)的地址。efstructstructnode*sublist;chardatastructnode*link;E k 的鏈接方法，這種鏈接方法在進(jìn)行元素的5.7例題A[0..8]23/62精品資料精品學(xué)習(xí)資料第23頁(yè)，共62頁(yè)單元中，則元素a[5][5]的地址為。aA]的元素起始地址是LOC(A[0][0])=4000，每個(gè)元素占2個(gè)字節(jié)，則按行優(yōu)先次序存儲(chǔ)時(shí)LOC(A[3][3])為多少？，tail[B]=((c,d))，head[head[head[tail[C]]]]=a。6.1樹(shù)Tm(1)在非空樹(shù)中至少有一個(gè)結(jié)點(diǎn)——根結(jié)點(diǎn)的度：分支個(gè)數(shù)(結(jié)點(diǎn)擁有的子樹(shù)個(gè)數(shù))。結(jié)點(diǎn)的層次：假設(shè)根結(jié)點(diǎn)的層次為1，根的孩子就在第2層，一個(gè)結(jié)點(diǎn)在第l層，則其子樹(shù)的根結(jié)24/62精品資料精品學(xué)習(xí)資料第24頁(yè)，共62頁(yè)有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。二叉樹(shù)二叉樹(shù)是n(nN0)個(gè)結(jié)點(diǎn)的有限集，1)每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn))。右之分，且其次序不能任意顛倒。3.性質(zhì) (1)在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(iN1)。 (3)任何一棵二叉樹(shù)，若葉子結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則必存在關(guān)系式：n0=n2+1。 (4)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1。 (5)若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：有②若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，如果2i<n，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)。③若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子，如果2i+1<n，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。 25/62精品資料精品學(xué)習(xí)資料第25頁(yè)，共62頁(yè)定義：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。 定義：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至 typedefstructnode{datatypedata;structnode*lchild,*rchild;reetypedefstruct{datatypedata;detypedefstruct{pNodetnode[MAXSIZE];ee26/62精品資料精品學(xué)習(xí)資料第26頁(yè)，共62頁(yè)typedefstructnode{intchild;//孩子結(jié)點(diǎn)序號(hào)structnode*next;//孩子鏈表結(jié)點(diǎn)ktypedefstructtnode{datatypedata;//樹(shù)結(jié)點(diǎn)數(shù)據(jù)域link*headptr;//孩子鏈表頭指針treectreeT[MAXSIZE];弟結(jié)點(diǎn)。typedefstructnode{fsondatanextdatatypedata;structnode*fson,*next;叉樹(shù)和線索二叉樹(shù)遍歷一棵非空二叉樹(shù)，可分解為：訪問(wèn)根結(jié)點(diǎn)D；遍歷左子樹(shù)L；遍歷右子樹(shù)R。因此有三種遍歷方法，分別是先序(根)遍歷(DLR)、中序(根)遍歷(LDR)和后序(根)遍歷(LRD)。 voidpreorder(bitree*t){iftNULL{27/62精品資料精品學(xué)習(xí)資料第27頁(yè)，共62頁(yè)printfdtt>data);rdertlchildrdertrchild}} voidpreorderbitree*t){}} voidpreorderbitree*t){}} 28/62精品資料精品學(xué)習(xí)資料第28頁(yè)，共62頁(yè) 遍歷序列。遍歷二叉樹(shù)是以一定的規(guī)則將二叉樹(shù)中的結(jié)點(diǎn)排列成一個(gè)線性序列,這實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)fb但是，當(dāng)以二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)時(shí)，要找到結(jié)點(diǎn)的前驅(qū)或后繼就不方便了。為此，引入線索二叉樹(shù)。我們發(fā)現(xiàn)，在含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)中有n-1條邊指向其左、右孩子，意味著n個(gè)結(jié)點(diǎn)的二叉nnn針域是空的?？沙浞掷眠@些空指針來(lái)存放結(jié)點(diǎn)的線 兩個(gè)相鄰的結(jié)點(diǎn)互稱(chēng)為前驅(qū)與后繼。。：對(duì)二叉樹(shù)按某種遍歷次序使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫線索化。 ①若結(jié)點(diǎn)有左子樹(shù)，則其lchild域指向其左孩子，否則令lchild域指向其直接前驅(qū)；②若結(jié)點(diǎn)有右子樹(shù)，則其rchild域指向其右孩子，否則令rchild域指向其直接后繼。 typedefstructnode{datatypedata;lchildltaggrtagrchild29/62精品資料精品學(xué)習(xí)資料第29頁(yè)，共62頁(yè)agltag=1structnode*lchild,ghptrrtag=16.6樹(shù)(森林)與二叉樹(shù)的轉(zhuǎn)換30/62精品資料精品學(xué)習(xí)資料第30頁(yè)，共62頁(yè)31/62精品資料精品學(xué)習(xí)資料第31頁(yè)，共62頁(yè)32/62精品資料精品學(xué)習(xí)資料第32頁(yè)，共62頁(yè)33/62精品資料精品學(xué)習(xí)資料第33頁(yè)，共62頁(yè)曼樹(shù)及哈夫曼編碼 個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)間的路徑。 (2)路徑長(zhǎng)度：路徑上的分支數(shù)。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為 (3)結(jié)點(diǎn)的路徑長(zhǎng)度：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。 (4)樹(shù)的路徑長(zhǎng)度：樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 (5)結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)到樹(shù)根的路徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積。 (6)樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和(其中Wk為權(quán)值，lk為結(jié)點(diǎn)到根的路徑長(zhǎng)度路徑長(zhǎng)度)WPLWL。KKKk樹(shù)(最優(yōu)二叉樹(shù))。W1,W2,,Wn的二叉樹(shù)中，帶權(quán)路徑長(zhǎng)度曼。WPL=7*1+5*2+2*3+4*3=35。(1)將w1,w2,,wn看成是有2)在森林中選出兩個(gè)根結(jié)點(diǎn)的刪除選取的兩棵樹(shù)n棵樹(shù)的森林(每棵樹(shù)僅有一個(gè)結(jié)點(diǎn))；權(quán)值最小的樹(shù)合并，作為一棵新樹(shù)的左、右子樹(shù)；，且新樹(shù)的根結(jié)34/62精品資料精品學(xué)習(xí)資料第34頁(yè)，共62頁(yè))步，直到森林中只剩一棵樹(shù)為止，該樹(shù)即為我們所求得的哈夫曼樹(shù)。假設(shè)給定的葉子結(jié)點(diǎn)的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹(shù)過(guò)程如下所示：6.9例題一。nmm2結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)數(shù)-1)例3：在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為6個(gè)。(公式：度數(shù)之和=結(jié)點(diǎn)數(shù)+1)35/62精品資料精品學(xué)習(xí)資料第35頁(yè)，共62頁(yè)LDR:BFJDGKACHELIM為為B，左子樹(shù)的右子樹(shù)的中序GEC，右子樹(shù)的左子樹(shù)的中序HF (注：首先將二叉樹(shù)分割為孤立的二叉樹(shù)，再將每個(gè)孤立的二叉樹(shù)轉(zhuǎn)換為樹(shù))36/62精品資料精品學(xué)習(xí)資料第36頁(yè)，共62頁(yè) (注：所有兄弟之間連線，然后刪除除左孩子之間的連線以外的所有其他連線) 左孩子，則指向左孩子，否則指向直接前驅(qū)；如果存在右孩子，則指向右孩子，W并求其37/62精品資料精品學(xué)習(xí)資料第37頁(yè)，共62頁(yè)第七章圖1.圖圖G由一個(gè)非空項(xiàng)點(diǎn)集V和一個(gè)頂點(diǎn)間的關(guān)系集合E(邊的集合)組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元有向邊也稱(chēng)為弧,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頁(yè)，共62頁(yè)例如上圖v1tv2tv5與v1tv4tv3tv5是從頂點(diǎn)v1到頂點(diǎn)v5的兩條路徑，路徑長(zhǎng)度分別為2和3。例如上圖atctdta為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。通分量無(wú)向圖的極大連通子圖稱(chēng)為G的連通分vi到頂點(diǎn)vjvi到頂點(diǎn)vj連12023(a)有向圖G中的極大強(qiáng)連通子圖稱(chēng)為G的強(qiáng)連通分量。顯然，強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即本G的生成樹(shù)，是G的包含其全n個(gè)頂占的一個(gè)極小連通子圖。它必定包含且僅包含G的n-1在非連通圖G中，由每個(gè)連通分量都可以得到一個(gè)極小連通子圖~一棵生成樹(shù)。這些連通分量的生成生成森林。圖的存儲(chǔ) 表示ij元素值為1，否則為0。39/62精品資料精品學(xué)習(xí)資料第39頁(yè)，共62頁(yè) #definen6#definee8/*typedefcharvextype;/*typedeffloatadjtype;typedefstruct{vextypevexs[n];adjtypearcsn][n];O(n×n)O(n×n)/*圖的頂點(diǎn)數(shù)*//*圖的邊數(shù)*/頂點(diǎn)的數(shù)據(jù)類(lèi)型*//*權(quán)值類(lèi)型*//*存儲(chǔ)頂點(diǎn)信息*/~存儲(chǔ)邊的信息*/*圖的定義*/ 40/62精品資料精品學(xué)習(xí)資料第40頁(yè)，共62頁(yè)所示。 鄰接矩陣方便。 typedefcharvextype;typedefstructtadjvexstructnode*next;dgenodetypedefstruct{vertypevertex;edgenode*link;vexnodegan];/*頂點(diǎn)的數(shù)據(jù)類(lèi)型*//*鄰接點(diǎn)域*//*權(quán)值域*//*頂點(diǎn)表結(jié)點(diǎn)*//*/*3.比較 鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。 頂點(diǎn)編號(hào)無(wú)關(guān))。On復(fù)雜度為O(n+e)。 圖的遍歷記錄每個(gè)頂visited[0..n-141/62]來(lái)標(biāo)志某個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)，未訪問(wèn)的值精品資料精品學(xué)習(xí)資料第41頁(yè)，共62頁(yè)。 首先訪問(wèn)頂點(diǎn)vi，并將其訪問(wèn)標(biāo)志置為訪問(wèn)過(guò)，即visited[i]=1；visitedj1，然后從vj開(kāi)始重復(fù)此過(guò)程；若vj已訪問(wèn)，再看與vi有邊相連的其它頂點(diǎn)； voiddfs(inti)tjvisit(i);visited[i]=1;//從頂點(diǎn)i出發(fā)遍歷//輸出訪問(wèn)頂點(diǎn)//全局?jǐn)?shù)組訪問(wèn)標(biāo)記置1表示已經(jīng)訪問(wèn)for(j=1;j<=n;j++)if((A[i][j]==1)&&(!visited[j]))fsj}1出發(fā)的深度優(yōu)先搜索遍歷過(guò)程，其中實(shí)線表示下一層遞歸調(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);}}//輸出訪問(wèn)頂點(diǎn)//全局?jǐn)?shù)組訪問(wèn)標(biāo)記置為1表示已訪問(wèn)i//依次搜索Vi+1的鄰接點(diǎn)//找Vi+1的下一個(gè)鄰接點(diǎn)42/62精品資料精品學(xué)習(xí)資料第42頁(yè)，共62頁(yè)描述從頂點(diǎn)7出發(fā)的深度優(yōu)先搜索遍歷，其中實(shí)線表示下一層遞歸，虛線表示遞歸返回，箭頭旁邊數(shù)字表示調(diào)用的步驟。從頂點(diǎn)7出發(fā)的深度優(yōu)先搜索遍歷序列：7,3,1,2,4,8,5,6。2.廣度優(yōu)先搜索遍歷(BFS) 首先訪問(wèn)頂點(diǎn)i，并將其訪問(wèn)標(biāo)志置為已被訪問(wèn)，即visited[i]=1； //從頂點(diǎn)Vk+1出發(fā)廣度優(yōu)先搜索圖g，圖g用鄰接矩陣表示，visited為訪問(wèn)標(biāo)志向量inti,j;ULLQvisited[k]=1;ENQUEUE(Q,K);while(!EMPTY(Q)){i=DEQUEUE(Q);//設(shè)置空隊(duì)列Q//訪問(wèn)出發(fā)點(diǎn)Vk+1//標(biāo)記置1表示已經(jīng)訪問(wèn)//已訪問(wèn)過(guò)的頂點(diǎn)入隊(duì)列//隊(duì)頭元素出隊(duì)列for(j=0;j<n;j++)if((g.arcs[i][j]==1)&&(!visited[j])){tedj}}}43/62精品資料精品學(xué)習(xí)資料第43頁(yè)，共62頁(yè)若從頂點(diǎn)1出發(fā)，廣度優(yōu)先搜索序列為：1，2，3，4，5，6，7，8若從頂點(diǎn)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è)置空隊(duì)列Q//隊(duì)頭元素出隊(duì)列取Vk+1的邊表頭指針//依次搜索Vk+1的鄰接點(diǎn)dpadjvexENQUEUE(Q,p->adjvex);//訪問(wèn)過(guò)的頂點(diǎn)入隊(duì)}ext}}}Vi+1的下一個(gè)鄰接點(diǎn)1出發(fā)，廣度優(yōu)先搜索序列為：1，2，3，4，5，6，7，87出發(fā)，廣度優(yōu)先搜索序列為：7，3，8，1，6，4，5，2最小生成樹(shù)連通圖G的一個(gè)極小連通子圖，它含有圖中n個(gè)頂點(diǎn)，但只有n-1條邊。由深度優(yōu)先搜索遍廣度優(yōu)先生成樹(shù)(BFS生成樹(shù))。44/62精品資料精品學(xué)習(xí)資料第44頁(yè)，共62頁(yè)V出發(fā))0 ②必須使用且僅使用n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)； 45/62精品資料精品學(xué)習(xí)資料第45頁(yè)，共62頁(yè)： (3)克魯斯卡爾Kruskar算法①假設(shè)G=<V,E>是連通圖，則令最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T=<V,{}>。T46/62精品資料精品學(xué)習(xí)資料第46頁(yè)，共62頁(yè)路徑定義：給定一個(gè)出發(fā)點(diǎn)(單源點(diǎn))和一個(gè)有向網(wǎng)G=(V,E),求出源點(diǎn)到其它各頂點(diǎn)之間的最短路徑。 ②按最短路徑長(zhǎng)度遞增的順序逐個(gè)把W中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而W為W④此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，W中的頂?shù)木嚯x從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度點(diǎn) ②從U中選取一個(gè)距離最小的頂點(diǎn)k，把k加入到S中。 ∞∞∞∞∞∞47/62精品資料精品學(xué)習(xí)資料第47頁(yè)，共62頁(yè)VSvvvvvvvvvv,v5>vvv4,v3,v5} ①設(shè)置一個(gè)n*n的矩陣A(k)，其中除對(duì)角線的元素都等于0外，其他元素a(k)[i][j]表示頂點(diǎn)i到頂點(diǎn)。 ①第一步，讓所有邊上加入②第二步，讓所有邊上加入③如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為所求的結(jié)果，A(n)[i][j]表示頂點(diǎn)i到頂點(diǎn)j的OV網(wǎng)AOVij存在一條有向路徑，稱(chēng)頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，或者稱(chēng)頂點(diǎn)j給出有向圖G=(V,E)，對(duì)于V中的頂點(diǎn)的線性序列(vi1,vi2,...,vin)，如果滿足如下條件：若在G中從頂點(diǎn)vi到vj有一條路經(jīng)，則在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前；則稱(chēng)該序列為G的一個(gè)拓?fù)湫蛄袨?0的頂點(diǎn)v且輸出之；48/62精品資料精品學(xué)習(xí)資料第48頁(yè)，共62頁(yè) (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注：一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏腛E網(wǎng)表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)AOE網(wǎng)。以上方右圖為計(jì)算過(guò)程，關(guān)鍵路徑為：V1tV2tV5tV7tV9V1tV2tV5tV8tV9 7.8例題例1：有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多有28條邊，最少有7條邊。 (注：無(wú)向圖最多需要n(n-1)/2條邊，最少需要n條邊。有向圖最多n(n-1)條邊。)49/62精品資料精品學(xué)習(xí)資料第49頁(yè)，共62頁(yè)。 (注：生成樹(shù)不唯一，但最小生成樹(shù)唯一)例5：用普里姆(Prim)算法求具有n個(gè)頂點(diǎn)e條邊的圖的最小生成樹(shù)的時(shí)間復(fù)雜度為Kruskal是O(elog2e)。 (1)每個(gè)頂點(diǎn)的入/出度； On；用克Dijkstraa他各頂點(diǎn)間的最短路徑，50/62精品資料精品學(xué)習(xí)資料第50頁(yè)，共62頁(yè) ( (1)試著找出網(wǎng)G的最小生成樹(shù)，畫(huà)出其邏輯結(jié)構(gòu) 用兩種不同的表示法畫(huà)出網(wǎng)G的存儲(chǔ)結(jié)構(gòu) (2)鄰接矩陣表示和鄰接表表示。1244898696abcdefg→→→→→→→babcabc49→→→→→→→ecdgbed486^→→^→^egf8→f9^6^51/62精品資料精品學(xué)習(xí)資料第51頁(yè)，共62頁(yè))。AB的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱(chēng)這排序voidinsert_sort(inta[],intfor(i=1;i<n;a[i];j=i-1;while((j>=0)&&tempajaj1]=a[j];j--;}aj+1]=temp;}分別進(jìn)行分別進(jìn)行tintspan;//增量for(m=0;m<numOfD;m++){span=d[m];//span個(gè)小組52/62精品資料精品學(xué)習(xí)資料第52頁(yè)，共62頁(yè)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;}}元素只剩一個(gè)。此時(shí)便為有序序列了。前提：voidquick_sort(inta[],intninti,j=n-1;順序存儲(chǔ)結(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頁(yè)，共62頁(yè)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個(gè)元素的序列{k1,k2,,kn}，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱(chēng)之為堆(Heap)。①ki≤k2i②ki≥k2iki≤k2i+1ki≥k2i+1 voidheap_sort(intdata[],intlength){for(i=(length>>1)-1;i>=0;i--)thforjlengthj0;--j){tempdataj//初始化一個(gè)堆54/62精品資料精品學(xué)習(xí)資料第54頁(yè)，共62頁(yè)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頁(yè)，共62頁(yè)if(left_low<=left_high)//若第一個(gè)序列有剩余，直接復(fù)制出來(lái)粘到合并序列尾for(i=left_low;i<=left_high;i++)tmp[k++]=arr[i];if(right_low<=right_high)//若第二個(gè)序列有剩余，直接復(fù)制出來(lái)粘到合并序列尾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ù)值的個(gè)數(shù)//儲(chǔ)存自己數(shù)組下標(biāo)數(shù)值在目標(biāo)數(shù)組對(duì)應(yīng)的位置//將原數(shù)組按大小順序儲(chǔ)存到另一個(gè)數(shù)組tvalueintaintd56/62精品資料精品學(xué)習(xí)資料第56頁(yè)，共62頁(yè)for(;d>0&&a>0;d--)}8.6例題冒泡排序一趟掃描的結(jié)果是HCQPAMSRDFXY；初始步長(zhǎng)為4的希爾(shell)排序一趟的結(jié)果是PACSQDFXRHMY；二路歸并排序一趟掃描的結(jié)果是HQCYAPMSDRFX；快速排序一趟掃描的結(jié)果是FHCDPAMQRSYX；堆排序初始建堆的結(jié)果是ADCRFQMSYPHX。t