數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題課件

概述模塊1：線性結(jié)構(gòu)模塊2：樹型結(jié)構(gòu)模塊3：圖型結(jié)構(gòu)模塊4：其他數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)概述數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)11.數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)→數(shù)據(jù)元素→數(shù)據(jù)項(xiàng)

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系（或關(guān)系）。包括：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。（3）施加在該數(shù)據(jù)上的運(yùn)算。

概述1.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)→數(shù)據(jù)元素→數(shù)據(jù)項(xiàng)數(shù)2

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱為映象），它是依賴于計(jì)算機(jī)語言的。

數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，每種邏輯結(jié)構(gòu)都有一組相應(yīng)的運(yùn)算。但運(yùn)算的實(shí)現(xiàn)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。程序＝數(shù)據(jù)結(jié)構(gòu)＋算法概述數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無3（1）線性結(jié)構(gòu)（2）樹形結(jié)構(gòu)（3）圖形結(jié)構(gòu)概述邏輯結(jié)構(gòu)主要有三大類：（1）線性結(jié)構(gòu)概述邏輯結(jié)構(gòu)主要有三大類：4存儲(chǔ)結(jié)構(gòu)分為如下四種：（1）順序存儲(chǔ)方法（2）鏈?zhǔn)酱鎯?chǔ)方法（3）索引存儲(chǔ)方法（4）散列存儲(chǔ)方法

概述存儲(chǔ)結(jié)構(gòu)分為如下四種：（1）順序存儲(chǔ)方法概述52.算法

算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列。概述2.算法算法是對(duì)特定問題求解步驟的一種描述，它是指6算法的五個(gè)重要的特性：（1）有窮性（2）確定性（3）可行性（4）有輸入（5）有輸出

概述算法的五個(gè)重要的特性：概述7

算法的時(shí)間復(fù)雜度：是指其基本運(yùn)算在算法中重復(fù)執(zhí)行的次數(shù)。

算法中基本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))記號(hào)“O”讀作“大O”，它表示隨問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同。

概述算法的時(shí)間復(fù)雜度：是指其基本運(yùn)算在算法中重復(fù)8例分析以下程序段的時(shí)間復(fù)雜度。i=1;while(i<=n)i=i*2;

解：上述算法中基本操作是語句i=i*2，設(shè)其頻度為T(n)，則有：2T(n)≤n即T(n)≤log2n=O(log2n)。所以，該程序段的時(shí)間復(fù)雜度為O(log2n)。例分析以下程序段的時(shí)間復(fù)雜度。解：上述算法中基9

算法空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小的量度。

對(duì)于空間復(fù)雜度為O(1)的算法稱為原地工作或就地工作算法。

概述算法空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的10■遞歸定義3.算法設(shè)計(jì)方法：遞歸

在定義一個(gè)算法時(shí)出現(xiàn)調(diào)用本算法的成分，稱之為遞歸。概述■遞歸定義3.算法設(shè)計(jì)方法：遞歸11■遞歸模型由遞歸出口和遞歸體組成例如，求二叉樹所有結(jié)點(diǎn)個(gè)數(shù)：f(b)=0 b=NULLf(b)=f(b->lchild)+f(b->rchild)+1b≠NULL概述■遞歸模型由遞歸出口和遞歸體組成例如，求二叉樹所有結(jié)點(diǎn)個(gè)12■遞歸算法設(shè)計(jì)①對(duì)原問題f(s)進(jìn)行分析，假設(shè)出合理的“較小問題”f(s');②假設(shè)f(s')是可解的，在此基礎(chǔ)上確定f(s)的解，即給出f(s)與f(s')之間的關(guān)系；③確定一個(gè)特定情況（如f(1)或f(0)）的解，由此作為遞歸出口.概述■遞歸算法設(shè)計(jì)①對(duì)原問題f(s)進(jìn)行分13bb->rchildb->lchild

①假設(shè)出合理的“較小問題”：假設(shè)左右子樹的結(jié)點(diǎn)個(gè)數(shù)可求②求出f(s)與f(s‘)之間的關(guān)系：f(b)=f(b->lchild)+f(b->rchild)+1③確定遞歸出口：f(NULL)=0概述bb->rchildb->lchild①假設(shè)出合理14intf(BTNode*b){if(b==NULL)return(0);elsereturn(f(b->lchild)+f(b->rchild)+1);}求解算法：概述intf(BTNode*b)求解算法：概述15例、假設(shè)非空二叉樹bt采用二叉鏈存儲(chǔ)，其中所有節(jié)點(diǎn)數(shù)據(jù)域?yàn)檎麛?shù)，設(shè)計(jì)一個(gè)遞歸算法求其中的最大值。遞歸模型如下：f(bt)=0 若bt為空

f(bt)=bt->data 若bt是葉子節(jié)點(diǎn)f(bt)=MAX3(bt->data,f(bt->lchild),f(bt->rchild))其他情況例、假設(shè)非空二叉樹bt采用二叉鏈存儲(chǔ)，其中所有節(jié)點(diǎn)數(shù)據(jù)域16intf(BTNode*bt){intm,n;if(bt==NULL) return0;if(bt->lchild==NULL&&bt->rchild==NULL) returnbt->data;else{m=f(bt->lchild); //求左子樹中的最大值 n=f(bt->rchild); //求右子樹中的最大值 if(m<=n) m=n; //左、右子樹中的最大值放在m中 if(m>bt->data) returnm; else returnbt->data;}}intf(BTNode*bt)17

例設(shè)計(jì)求f(n)=1+2+...+n的遞歸算法解：f(n)為前n項(xiàng)之和，則f(n-1)=1+2+...+(n-1)假設(shè)f(n-1)可求，則f(n)=f(n-1)+n，所以：f(n)=1 當(dāng)n=1f(n)=f(n-1)+n當(dāng)n>1對(duì)應(yīng)的遞歸算法如下：例設(shè)計(jì)求f(n)=1+2+...+n的遞歸算法18intf(intn){if(n==1)return(1);elsereturn(f(n-1)+n));}intf(intn)191.一般線性表

線性表：具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。不是集合。元素之間是一對(duì)一的關(guān)系。模塊1：線性結(jié)構(gòu)邏輯結(jié)構(gòu)1.一般線性表模塊1：線性結(jié)構(gòu)邏輯結(jié)構(gòu)20（1）順序表

typedefstruct{ ElemTypeelem[MaxSize]; /*存放順序表元素*/ intlength; /*存放順序表的長度*/}SqList;存儲(chǔ)結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)（1）順序表typedefstruct存儲(chǔ)結(jié)構(gòu)21順序表基本運(yùn)算的實(shí)現(xiàn)

插入數(shù)據(jù)元素算法：元素移動(dòng)的次數(shù)不僅與表長n有關(guān)；插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)n/2。平均時(shí)間復(fù)雜度為O(n)。

模塊1：線性結(jié)構(gòu)順序表基本運(yùn)算的實(shí)現(xiàn) 插入數(shù)據(jù)元素算法：元素移動(dòng)的次數(shù)不僅22

刪除數(shù)據(jù)元素算法:元素移動(dòng)的次數(shù)也與表長n有關(guān)。刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為(n-1)/2。刪除算法的平均時(shí)間復(fù)雜度為O(n)。模塊1：線性結(jié)構(gòu) 刪除數(shù)據(jù)元素算法:元素移動(dòng)的次數(shù)也與表長n有關(guān)。刪除一個(gè)23例、在一個(gè)長度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)

個(gè)元素。A.n B.i-1 C.n-i D.n-i+1例、在一個(gè)長度為n的順序表中刪除第i個(gè)元素（1≤i24例、設(shè)線性表有n個(gè)元素，以下操作中，

在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1≤i≤n）個(gè)元素值B.交換第1個(gè)元素與第2個(gè)元素的值C.順序輸出這n個(gè)元素的值D.輸出與給定值x相等的元素在線性表中的序號(hào)例、設(shè)線性表有n個(gè)元素，以下操作中，在順序表上25例．已知長度為n的線性表L采用順序存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，刪除其中所有元素值在[x,y]之間的所有元素。解法一：對(duì)應(yīng)的算法如下：voiddelxy1(SqList&L,ElemTypex,ElemTypey){intk=0,i; //k記錄不滿足條件的元素個(gè)數(shù)for(i=0;i<L.length;i++)

if(!(L.data[i]>=x&&L.data[i]<=y)) {L.data[k]=L.data[i]; k++; //不滿足條件的元素個(gè)數(shù)增1 } L.length=k; //順序表L的長度等于k}例．已知長度為n的線性表L采用順序存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)在26解法二：對(duì)應(yīng)的算法如下：voiddelnode2(SqList&L,ElemTypex,ElemTypey){intk=0,i=0; //k記錄滿足條件的元素個(gè)數(shù)while(i<L.length){ if(L.data[i]>=x&&L.data[i]<=y) k++; else L.data[i-k]=L.data[i]; //當(dāng)前元素前移k個(gè)位置

i++;}L.length=L.length-k; //順序表L的長度遞減}解法二：對(duì)應(yīng)的算法如下：27（2）鏈表

定義單鏈表結(jié)點(diǎn)類型:typedefstructLNode{ElemTypedata;structLNode*next; /*指向后繼結(jié)點(diǎn)*/}LinkList;存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)（2）鏈表定義單鏈表結(jié)點(diǎn)類型:存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)28定義雙鏈表結(jié)點(diǎn)類型:typedefstructDNode {ElemTypedata;structDNode*prior; /*指向前驅(qū)結(jié)點(diǎn)*/structDNode*next; /*指向后繼結(jié)點(diǎn)*/}DLinkList;模塊1：線性結(jié)構(gòu)定義雙鏈表結(jié)點(diǎn)類型:模塊1：線性結(jié)構(gòu)29

■單鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：（1）頭插法建表和尾插法建表算法，它是很多算法設(shè)計(jì)的基礎(chǔ)；（2）查找、插入和刪除操作。模塊1：線性結(jié)構(gòu)■單鏈表基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：（1）頭插法建表和30

頭插法建表

該方法從一個(gè)空表開始,讀取字符數(shù)組a中的字符,生成新結(jié)點(diǎn),將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:模塊1：線性結(jié)構(gòu)頭插法建表模塊1：線性結(jié)構(gòu)31voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結(jié)點(diǎn)*/

L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];s->next=L->next;

/*將*s插在原開始結(jié)點(diǎn)之前,頭結(jié)點(diǎn)之后*/

L->next=s;}}模塊1：線性結(jié)構(gòu)voidCreateListF(LinkList*&32

尾插法建表

頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點(diǎn)的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上,為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。采用尾插法建表的算法如下:模塊1：線性結(jié)構(gòu)尾插法建表模塊1：線性結(jié)構(gòu)33voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點(diǎn)*/

r=L;/*r始終指向終端結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/

s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}

r->next=NULL; /*終端結(jié)點(diǎn)next域置為NULL*/}voidCreateListR(LinkList*&34例、設(shè)一個(gè)整數(shù)線性表采用帶頭節(jié)點(diǎn)的hc單鏈表存放，設(shè)計(jì)一個(gè)算法在不破壞原有單鏈表的前提下，創(chuàng)建兩個(gè)單鏈表ha和hb，前者由hc中值為奇數(shù)的節(jié)點(diǎn)構(gòu)成，后者由hc中值為偶數(shù)的節(jié)點(diǎn)構(gòu)成。例、設(shè)一個(gè)整數(shù)線性表采用帶頭節(jié)點(diǎn)的hc單鏈表存放，設(shè)計(jì)一35voidsplit(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb,*s;ha=(LinkList*)malloc(sizeof(LinkList));

ra=ha;hb=(LinkList*)malloc(sizeof(LinkList));

rb=hb;while(p!=NULL){ if(p->data%2==1) //奇數(shù)節(jié)點(diǎn) {s=(LinkList*)malloc(sizeof(LinkList)); s->data=p->data; //復(fù)制產(chǎn)生節(jié)點(diǎn)*s

ra->next=s; //將*s節(jié)點(diǎn)鏈接到ha尾部 ra=s; } else //偶數(shù)節(jié)點(diǎn) {s=(LinkList*)malloc(sizeof(LinkList)); s->data=p->data; //復(fù)制產(chǎn)生節(jié)點(diǎn)*s

rb->next=s; //將*s節(jié)點(diǎn)鏈接到hb尾部 rb=s; } p=p->next;}

ra->next=rb->next=NULL; //兩鏈表尾節(jié)點(diǎn)next均置為NULL}voidsplit(LinkList*hc,LinkL36

■雙鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：插入和刪除結(jié)點(diǎn)的算法。模塊1：線性結(jié)構(gòu)■雙鏈表基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：插入和刪除結(jié)點(diǎn)的算法。37

■循環(huán)鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：判斷最后一個(gè)結(jié)點(diǎn)。模塊1：線性結(jié)構(gòu)■循環(huán)鏈表基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：判斷最后一個(gè)結(jié)點(diǎn)。模塊382.棧

（1）棧的定義棧是一種先進(jìn)后出表。插入刪除受限的線性表。棧的基本運(yùn)算:進(jìn)棧，出棧。邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)2.棧邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)39（2）順序棧typedefstruct{ElemTypedata[MaxSize];inttop; /*棧頂指針*/}SqStack;存儲(chǔ)結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)（2）順序棧typedefstruct存儲(chǔ)結(jié)構(gòu)之一模塊140?？諚l件:s.top==-1棧滿條件:s.top==MaxSize-1進(jìn)棧:top++;s.data[s.top]=e;出棧:e=s.data[s.top];s.top—;順序棧的4要素:模塊1：線性結(jié)構(gòu)?？諚l件:s.top==-1順序棧的4要素:模塊1：線41（3）鏈棧

typedefstructlinknode{ElemTypedata; /*數(shù)據(jù)域*/structlinknode*next; /*指針域*/}LiStack;存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)（3）鏈棧typedefstructlinknode存42帶頭結(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)(也可不帶頭結(jié)點(diǎn))?？諚l件:s->next==NULL棧滿條件:?模塊1：線性結(jié)構(gòu)帶頭結(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)(也可不帶頭結(jié)點(diǎn))?？諚l件:s->ne433.隊(duì)列

（1）隊(duì)列的定義

隊(duì)列是一種先進(jìn)先出表。插入刪除受限的線性表。隊(duì)列的基本運(yùn)算:進(jìn)隊(duì),出隊(duì)邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)3.隊(duì)列（1）隊(duì)列的定義邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)44（2）順序隊(duì)typedefstruct{ElemTypedata[MaxSize]；intfront,rear；/*隊(duì)首和隊(duì)尾指針*/}SqQueue；

存儲(chǔ)結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)（2）順序隊(duì)typedefstruct存儲(chǔ)結(jié)構(gòu)之一模45隊(duì)空:q.front==q.rear隊(duì)滿:(q.rear+1)%MaxSize==q.front進(jìn)隊(duì):q.rear=(q.rear+1)％MaxSize;q.data[q.rear]=e;出隊(duì):q.front=(q.front+1)％MaxSize;e=q.data[q.front];環(huán)形隊(duì)列的4要素:模塊1：線性結(jié)構(gòu)隊(duì)空:q.front==q.rear環(huán)形隊(duì)列的4要素:46（3）鏈隊(duì)structqnode/*數(shù)據(jù)結(jié)點(diǎn)*/{ElemTypedata;structqnode*next;}QNode;typedefstruct/*頭結(jié)點(diǎn)*/{QNode*front;QNode*rear;}LiQueue;存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)（3）鏈隊(duì)structqnode/*數(shù)據(jù)結(jié)點(diǎn)*/存儲(chǔ)結(jié)47（2）順序串

（3）鏈串

（4）串的模式匹配算法：BF、KMP4.串（1）串的定義

串、子串、串相等、空串、空格串模塊1：線性結(jié)構(gòu)（2）順序串（3）鏈串（4）串的模式匹配算法：BF、KM485.數(shù)組和稀疏矩陣

（1）數(shù)組的定義相同類型數(shù)據(jù)元素、有限序列模塊1：線性結(jié)構(gòu)5.數(shù)組和稀疏矩陣模塊1：線性結(jié)構(gòu)49（2）數(shù)組的存儲(chǔ)結(jié)構(gòu)

以行序?yàn)橹餍?LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k

以列序?yàn)橹餍騆OC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k

以數(shù)組A[c1..d1,c2..d2]為例模塊1：線性結(jié)構(gòu)（2）數(shù)組的存儲(chǔ)結(jié)構(gòu)以行序?yàn)橹餍?以列序?yàn)橹餍蛞詳?shù)組50（3）特殊矩陣的壓縮存儲(chǔ)■對(duì)稱矩陣

若一個(gè)n階方陣A[n][n]中的元素滿足ai,j=aj,i（0≤i，j≤n-1），則稱其為n階對(duì)稱矩陣。

A[0..n-1][0..n-1]

B[0..n(n+1)/2]

i(i+1)/2+j 當(dāng)i≥j時(shí)k=j(j+1)/2+i 當(dāng)i＜j時(shí)模塊1：線性結(jié)構(gòu)（3）特殊矩陣的壓縮存儲(chǔ)■對(duì)稱矩陣A[0..n-1][051■三角矩陣

采用類似的壓縮方法.模塊1：線性結(jié)構(gòu)■三角矩陣采用類似的壓縮方法.模塊1：線性結(jié)構(gòu)52（4）稀疏矩陣存儲(chǔ)結(jié)構(gòu)：■三元組表示■十字鏈表表示

各種表示的基本思路。非零元素遠(yuǎn)小于元素總數(shù)。模塊1：線性結(jié)構(gòu)（4）稀疏矩陣存儲(chǔ)結(jié)構(gòu)：非零元素遠(yuǎn)小于元素總數(shù)。模塊1：線53

■一個(gè)廣義表中所含元素的個(gè)數(shù)稱為它的長度.6.廣義表GL=(a,(a),(a,b,c,d),())長度為4。模塊1：線性結(jié)構(gòu)■一個(gè)廣義表中所含元素的個(gè)數(shù)稱為它的長度.54

■一個(gè)廣義表中括號(hào)嵌套的最大次數(shù)為它的深度.GL=(a,(a),(a,b,c,d),())深度為2。模塊1：線性結(jié)構(gòu)■一個(gè)廣義表中括號(hào)嵌套的最大次數(shù)為它的深度.GL55

■表的第一個(gè)元素a1為廣義表GL的表頭，其余部分(a2，…，ai，ai+1，…，an)為GL的表尾.

GL=(a,(a),(a,b,c,d),())表頭為a，表尾為((a),(a,b,c,d),())模塊1：線性結(jié)構(gòu)■表的第一個(gè)元素a1為廣義表GL的表頭，其余56模塊2：樹形結(jié)構(gòu)

（1）樹的定義遞歸定義適合于表示層次結(jié)構(gòu)的數(shù)據(jù)1.樹模塊2：樹形結(jié)構(gòu)（1）樹的定義1.樹57（2）樹的表示法（邏輯表示方法）■樹形表示法■文氏圖表示法■凹入表示法■括號(hào)表示法模塊2：樹形結(jié)構(gòu)

（2）樹的表示法（邏輯表示方法）■樹形表示法模塊2：樹58（3）樹的遍歷■先根遍歷算法■后根遍歷算法模塊2：樹形結(jié)構(gòu)

（3）樹的遍歷■先根遍歷算法模塊2：樹形結(jié)構(gòu)59（4）樹和二叉樹的相互轉(zhuǎn)換■樹二叉樹■二叉樹樹模塊2：樹形結(jié)構(gòu)

（4）樹和二叉樹的相互轉(zhuǎn)換■樹二叉樹模塊2：602.二叉樹

（1）二叉樹的定義根、左子樹、右子樹完全二叉樹,滿二叉樹的定義模塊2：樹形結(jié)構(gòu)

2.二叉樹（1）二叉樹的定義模塊2：樹形結(jié)構(gòu)61

性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。即n0=n2+1.

性質(zhì)2非空二叉樹上第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。（2）二叉樹性質(zhì)模塊2：樹形結(jié)構(gòu)

性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)62

性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)（h≥1）。

性質(zhì)4完全二叉樹的性質(zhì)。

性質(zhì)5具有n個(gè)（n＞0）結(jié)點(diǎn)的完全二叉樹的高度為log2(n+1)或log2n+1。（2）二叉樹性質(zhì)模塊2：樹形結(jié)構(gòu)

性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)結(jié)63

例、將一棵有98個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為

。

A.98B.99C.50D.不存在模塊2：樹形結(jié)構(gòu)

例、將一棵有98個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層64

例深度為5的二叉樹至多有

個(gè)結(jié)點(diǎn)。

A.16B.32C.31D.10

答：相同滿度時(shí)滿二叉樹結(jié)點(diǎn)最多，h=5的滿二叉樹結(jié)點(diǎn)個(gè)數(shù)=25-1=31。C。模塊2：樹形結(jié)構(gòu)

例深度為5的二叉樹至多有個(gè)結(jié)點(diǎn)。65（3）二叉樹存儲(chǔ)結(jié)構(gòu)

■二叉樹的順序存儲(chǔ)結(jié)構(gòu)模塊2：樹形結(jié)構(gòu)

ABCDEF1234567891011121314ABCDEF（3）二叉樹存儲(chǔ)結(jié)構(gòu)■二叉樹的順序存儲(chǔ)結(jié)構(gòu)模塊2：樹66i2i2i+1左孩子右孩子i2i2i+1左孩子右孩子67■二叉鏈存儲(chǔ)結(jié)構(gòu)

typedefstructnode{ ElemTypedata; /*數(shù)據(jù)元素*/ structnode*lchild;/*指向左孩子*/ structnode*rchild;/*指向右孩子*/}BTNode;■二叉鏈存儲(chǔ)結(jié)構(gòu)68ABC左孩子右孩子ABC左孩子右孩子69（4）二叉樹的遍歷

■先序遍歷■中序遍歷■后序遍歷■層次遍歷通常用遞歸算法實(shí)現(xiàn)模塊2：樹形結(jié)構(gòu)

（4）二叉樹的遍歷■先序遍歷通常用遞歸算法實(shí)現(xiàn)模塊270例、若二叉樹的中序遍歷序列是abcdef，且c為根節(jié)點(diǎn)，則

。A.節(jié)點(diǎn)c有兩個(gè)孩子B.二叉樹有兩個(gè)度為0的節(jié)點(diǎn)C.二叉樹的高度為5D.以上都不對(duì)例、若二叉樹的中序遍歷序列是abcdef，且c為根節(jié)點(diǎn)，71例、

的先序序列和后序序列正好相反。A.二叉排序樹 B.3個(gè)節(jié)點(diǎn)的二叉樹C.平衡二叉樹 D.無右孩子的二叉樹例、的先序序列和后序序列正好相反。72例、在任何一棵二叉樹中，如果節(jié)點(diǎn)a有左孩子b、右孩子c，則在節(jié)點(diǎn)的先序序列、中序序列、后序序列中，

。A.節(jié)點(diǎn)b一定在節(jié)點(diǎn)a的前面B.節(jié)點(diǎn)a一定在節(jié)點(diǎn)c的前面

C.節(jié)點(diǎn)b一定在節(jié)點(diǎn)c的前面D.節(jié)點(diǎn)a一定在節(jié)點(diǎn)b的前面例、在任何一棵二叉樹中，如果節(jié)點(diǎn)a有左孩子b、右孩子c，則73例、設(shè)n、m為一棵二叉樹上的兩個(gè)節(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是

。A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孫例、設(shè)n、m為一棵二叉樹上的兩個(gè)節(jié)點(diǎn)，在中序遍歷時(shí)，n在m74例、假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。解：輸出一棵二叉樹的所有葉子結(jié)點(diǎn)的遞歸模型f()如下：f(b)：不做任何事件 若b=NULLf(b)：輸出*b結(jié)點(diǎn)的data域若*b為葉子結(jié)點(diǎn)f(b)：f(b->lchild);f(b->rchild) 其他情況模塊2：樹形結(jié)構(gòu)

例、假設(shè)二叉樹采用二叉鏈存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)75

voidDispLeaf(BTNode*b){if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL) printf("%c",b->data); DispLeaf(b->lchild); DispLeaf(b->rchild);}}模塊2：樹形結(jié)構(gòu)

先序遍歷思想voidDispLeaf(BTNode*b)模塊2762.哈夫曼樹（1）哈夫曼樹的定義WPL最小，沒有單分支結(jié)點(diǎn)即n1=0模塊2：樹形結(jié)構(gòu)

2.哈夫曼樹（1）哈夫曼樹的定義WPL最小，沒有單分支77（2）哈夫曼樹的構(gòu)造過程（3）哈夫曼編碼的構(gòu)造過程模塊2：樹形結(jié)構(gòu)

（2）哈夫曼樹的構(gòu)造過程（3）哈夫曼編碼的構(gòu)造過程模塊2：78例、設(shè)哈夫曼編碼的長度不超過4，若已經(jīng)對(duì)兩個(gè)字符編碼為1和01，則最多還可以對(duì)

個(gè)字符編碼。A.2 B.3 C.4 D.5例、設(shè)哈夫曼編碼的長度不超過4，若已經(jīng)對(duì)兩個(gè)字符編碼為1和79■頂點(diǎn)的度、入度和出度■完全圖■子圖■路徑和路徑長度■連通、連通圖和連通分量■強(qiáng)連通圖和強(qiáng)連通分量■權(quán)和網(wǎng)

模塊3：圖形結(jié)構(gòu)（1）圖的基本概念■頂點(diǎn)的度、入度和出度模塊3：圖形結(jié)構(gòu)（1）圖的基本概80（2）圖的存儲(chǔ)結(jié)構(gòu)■鄰接矩陣存儲(chǔ)方法

掌握兩種存儲(chǔ)方法的優(yōu)缺點(diǎn)，同一種功能在不同存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)算法。■鄰接表存儲(chǔ)方法模塊3：圖形結(jié)構(gòu)（2）圖的存儲(chǔ)結(jié)構(gòu)■鄰接矩陣存儲(chǔ)方法81（3）圖的遍歷

■深度優(yōu)先搜索遍歷

離初始點(diǎn)越遠(yuǎn)越優(yōu)先訪問。1267354訪問序列：1，2，3，4，5，6，7模塊3：圖形結(jié)構(gòu)（3）圖的遍歷■深度優(yōu)先搜索遍歷離初始點(diǎn)越遠(yuǎn)越優(yōu)先訪82voidDFS(ALGraph*G,intv){ArcNode*p;Visited[v]=1;/*置已訪問標(biāo)記*/printf("%d",v); /*輸出被訪問頂點(diǎn)的編號(hào)*/p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0) DFS(G,p->adjvex);p=p->nextarc; }}模塊3：圖形結(jié)構(gòu)voidDFS(ALGraph*G,intv)模塊831267354■廣度優(yōu)先搜索遍歷

離初始點(diǎn)越近越優(yōu)先訪問。訪問序列：1，2，6，7，3，5，4模塊3：圖形結(jié)構(gòu)1267354■廣度優(yōu)先搜索遍歷離初始點(diǎn)越近越優(yōu)先訪問。84voidBFS(ALGraph*G,intv){ ArcNode*p; intqueue[MAXV],front=0,rear=0; intvisited[MAXV];intw,i; for(i=0;i<G->n;i++)visited[i]=0; printf("%2d",v); visited[v]=1; /*置已訪問標(biāo)記*/ rear=(rear+1)%MAXV; queue[rear]=v;/*v進(jìn)隊(duì)*/模塊3：圖形結(jié)構(gòu)voidBFS(ALGraph*G,intv)85 while(front!=rear)/*若隊(duì)列不空時(shí)循環(huán)*/ { front=(front+1)%MAXV; w=queue[front];/*出隊(duì)并賦給w*/ p=G->adjlist[w].firstarc; while(p!=NULL) {if(visited[p->adjvex]==0) {printf("%2d",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc; } }}模塊3：圖形結(jié)構(gòu) while(front!=rear)/*若隊(duì)86（4）最小生成樹■普里姆算法給定起始點(diǎn)；算法過程；O(n2)模塊3：圖形結(jié)構(gòu)（4）最小生成樹■普里姆算法模塊3：圖形結(jié)構(gòu)87■克魯斯卡爾算法不給定起始點(diǎn)；算法過程；O(elog2e)模塊3：圖形結(jié)構(gòu)■克魯斯卡爾算法模塊3：圖形結(jié)構(gòu)88（5）最短路徑■狄克斯特拉算法過程■弗洛伊德算法過程模塊3：圖形結(jié)構(gòu)（5）最短路徑■狄克斯特拉算法過程模塊3：圖形結(jié)構(gòu)89（1）線性表的查找模塊4：其他1.查找在順序表上進(jìn)行。方法有：■順序查找（過程和算法）■二分查找（過程和算法）■分塊查找(過程)（1）線性表的查找模塊4：其他1.查找在順序表上進(jìn)行。方90（2）樹表的查找▲二叉排序樹■定義■查找（過程和算法）■插入和刪除（過程）與堆的區(qū)別模塊4：其他性質(zhì)：二叉排序樹的中序序列是一個(gè)有序序列（2）樹表的查找▲二叉排序樹■定義與堆的區(qū)91▲平衡二叉樹■定義■查找（過程和算法）■調(diào)整（過程）模塊4：其他▲平衡二叉樹■定義模塊4：其他92（3）哈希表查找■哈希函數(shù)主要有除留余數(shù)法?！龉_突解決方法主要有線性探查法、拉鏈法模塊4：其他（3）哈希表查找■哈希函數(shù)■哈希沖突解決方法模塊932.內(nèi)排序

■插入排序 （1）直接插入排序 （2）希爾排序模塊4：其他2.內(nèi)排序■插入排序模塊4：其他94

■交換排序 （1）冒泡排序 （2）快速排序■交換排序95

■選擇排序 （1）簡單選擇排序 （2）堆排序■選擇排序96

■歸并排序

■基數(shù)排序■歸并排序97

例、在待排序的元素序列基本有序的前提下，效率最高的排序方法是

。

A.直接插入排序 B.選擇排序C.快速排序 D.歸并排序例、在待排序的元素序列基本有序的前提下，效率最高98

例快速排序在最壞情況下時(shí)間復(fù)雜度是O(n2)，比

的性能差。

A.堆排序 B.冒泡排序C.直接選擇排序 D.直接插入排序例快速排序在最壞情況下時(shí)間復(fù)雜度是O(n2)，比99強(qiáng)調(diào)各種排序方法的比較是否需要比較排序方法的區(qū)別時(shí)間復(fù)雜度空間復(fù)雜度強(qiáng)調(diào)各種排序方法的比較1003.外排序

外排序的過程。磁盤排序：置換選擇算法、敗者樹、最佳平衡歸并樹。3.外排序外排序的過程。101學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)對(duì)于求解問題的思路。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的幾點(diǎn)提示學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)對(duì)于求解問題的思路。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的幾點(diǎn)提示102注重算法的關(guān)聯(lián)性。如較高效算法是如何提高效率的，如何從問題中找出“啟發(fā)”信息的？注重算法的關(guān)聯(lián)性。如較高效算法是如何提高效率的，如何從問題中103順序查找算法二分查找算法利用了數(shù)據(jù)的有序性示例1順序查找算法二分查找算法利用了數(shù)據(jù)的有序性示例1104串簡單匹配算法串KMP匹配算法利用子串中部分匹配特性示例2串簡單匹配算法串KMP匹配算法利用子串中部分匹配特性示例2105簡單選擇排序算法堆選擇排序算法利用了連續(xù)多次查找最大記錄的特性示例3簡單選擇排序算法堆選擇排序算法利用了連續(xù)多次查找最大記錄的特106算法的作用。一些復(fù)雜的問題的基礎(chǔ)可能就是一個(gè)“簡單”的算法。算法的作用。一些復(fù)雜的問題的基礎(chǔ)可能就是一個(gè)“簡單”的算法。107示例：機(jī)器人規(guī)劃問題AB找路徑：ABABAB膨脹所有物體。將路徑搜索轉(zhuǎn)換為圖的頂點(diǎn)搜索。示例：機(jī)器人規(guī)劃問題AB找路徑：ABABAB膨脹所有物體。108概述模塊1：線性結(jié)構(gòu)模塊2：樹型結(jié)構(gòu)模塊3：圖型結(jié)構(gòu)模塊4：其他數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)概述數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)1091.數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)→數(shù)據(jù)元素→數(shù)據(jù)項(xiàng)

數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系（或關(guān)系）。包括：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)。（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。（3）施加在該數(shù)據(jù)上的運(yùn)算。

概述1.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)→數(shù)據(jù)元素→數(shù)據(jù)項(xiàng)數(shù)110

數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱為映象），它是依賴于計(jì)算機(jī)語言的。

數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，每種邏輯結(jié)構(gòu)都有一組相應(yīng)的運(yùn)算。但運(yùn)算的實(shí)現(xiàn)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有關(guān)。程序＝數(shù)據(jù)結(jié)構(gòu)＋算法概述數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無111（1）線性結(jié)構(gòu)（2）樹形結(jié)構(gòu)（3）圖形結(jié)構(gòu)概述邏輯結(jié)構(gòu)主要有三大類：（1）線性結(jié)構(gòu)概述邏輯結(jié)構(gòu)主要有三大類：112存儲(chǔ)結(jié)構(gòu)分為如下四種：（1）順序存儲(chǔ)方法（2）鏈?zhǔn)酱鎯?chǔ)方法（3）索引存儲(chǔ)方法（4）散列存儲(chǔ)方法

概述存儲(chǔ)結(jié)構(gòu)分為如下四種：（1）順序存儲(chǔ)方法概述1132.算法

算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列。概述2.算法算法是對(duì)特定問題求解步驟的一種描述，它是指114算法的五個(gè)重要的特性：（1）有窮性（2）確定性（3）可行性（4）有輸入（5）有輸出

概述算法的五個(gè)重要的特性：概述115

算法的時(shí)間復(fù)雜度：是指其基本運(yùn)算在算法中重復(fù)執(zhí)行的次數(shù)。

算法中基本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))記號(hào)“O”讀作“大O”，它表示隨問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同。

概述算法的時(shí)間復(fù)雜度：是指其基本運(yùn)算在算法中重復(fù)116例分析以下程序段的時(shí)間復(fù)雜度。i=1;while(i<=n)i=i*2;

解：上述算法中基本操作是語句i=i*2，設(shè)其頻度為T(n)，則有：2T(n)≤n即T(n)≤log2n=O(log2n)。所以，該程序段的時(shí)間復(fù)雜度為O(log2n)。例分析以下程序段的時(shí)間復(fù)雜度。解：上述算法中基117

算法空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小的量度。

對(duì)于空間復(fù)雜度為O(1)的算法稱為原地工作或就地工作算法。

概述算法空間復(fù)雜度：是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的118■遞歸定義3.算法設(shè)計(jì)方法：遞歸

在定義一個(gè)算法時(shí)出現(xiàn)調(diào)用本算法的成分，稱之為遞歸。概述■遞歸定義3.算法設(shè)計(jì)方法：遞歸119■遞歸模型由遞歸出口和遞歸體組成例如，求二叉樹所有結(jié)點(diǎn)個(gè)數(shù)：f(b)=0 b=NULLf(b)=f(b->lchild)+f(b->rchild)+1b≠NULL概述■遞歸模型由遞歸出口和遞歸體組成例如，求二叉樹所有結(jié)點(diǎn)個(gè)120■遞歸算法設(shè)計(jì)①對(duì)原問題f(s)進(jìn)行分析，假設(shè)出合理的“較小問題”f(s');②假設(shè)f(s')是可解的，在此基礎(chǔ)上確定f(s)的解，即給出f(s)與f(s')之間的關(guān)系；③確定一個(gè)特定情況（如f(1)或f(0)）的解，由此作為遞歸出口.概述■遞歸算法設(shè)計(jì)①對(duì)原問題f(s)進(jìn)行分121bb->rchildb->lchild

①假設(shè)出合理的“較小問題”：假設(shè)左右子樹的結(jié)點(diǎn)個(gè)數(shù)可求②求出f(s)與f(s‘)之間的關(guān)系：f(b)=f(b->lchild)+f(b->rchild)+1③確定遞歸出口：f(NULL)=0概述bb->rchildb->lchild①假設(shè)出合理122intf(BTNode*b){if(b==NULL)return(0);elsereturn(f(b->lchild)+f(b->rchild)+1);}求解算法：概述intf(BTNode*b)求解算法：概述123例、假設(shè)非空二叉樹bt采用二叉鏈存儲(chǔ)，其中所有節(jié)點(diǎn)數(shù)據(jù)域?yàn)檎麛?shù)，設(shè)計(jì)一個(gè)遞歸算法求其中的最大值。遞歸模型如下：f(bt)=0 若bt為空

f(bt)=bt->data 若bt是葉子節(jié)點(diǎn)f(bt)=MAX3(bt->data,f(bt->lchild),f(bt->rchild))其他情況例、假設(shè)非空二叉樹bt采用二叉鏈存儲(chǔ)，其中所有節(jié)點(diǎn)數(shù)據(jù)域124intf(BTNode*bt){intm,n;if(bt==NULL) return0;if(bt->lchild==NULL&&bt->rchild==NULL) returnbt->data;else{m=f(bt->lchild); //求左子樹中的最大值 n=f(bt->rchild); //求右子樹中的最大值 if(m<=n) m=n; //左、右子樹中的最大值放在m中 if(m>bt->data) returnm; else returnbt->data;}}intf(BTNode*bt)125

例設(shè)計(jì)求f(n)=1+2+...+n的遞歸算法解：f(n)為前n項(xiàng)之和，則f(n-1)=1+2+...+(n-1)假設(shè)f(n-1)可求，則f(n)=f(n-1)+n，所以：f(n)=1 當(dāng)n=1f(n)=f(n-1)+n當(dāng)n>1對(duì)應(yīng)的遞歸算法如下：例設(shè)計(jì)求f(n)=1+2+...+n的遞歸算法126intf(intn){if(n==1)return(1);elsereturn(f(n-1)+n));}intf(intn)1271.一般線性表

線性表：具有相同特性的數(shù)據(jù)元素的一個(gè)有限序列。不是集合。元素之間是一對(duì)一的關(guān)系。模塊1：線性結(jié)構(gòu)邏輯結(jié)構(gòu)1.一般線性表模塊1：線性結(jié)構(gòu)邏輯結(jié)構(gòu)128（1）順序表

typedefstruct{ ElemTypeelem[MaxSize]; /*存放順序表元素*/ intlength; /*存放順序表的長度*/}SqList;存儲(chǔ)結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)（1）順序表typedefstruct存儲(chǔ)結(jié)構(gòu)129順序表基本運(yùn)算的實(shí)現(xiàn)

插入數(shù)據(jù)元素算法：元素移動(dòng)的次數(shù)不僅與表長n有關(guān)；插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)n/2。平均時(shí)間復(fù)雜度為O(n)。

模塊1：線性結(jié)構(gòu)順序表基本運(yùn)算的實(shí)現(xiàn) 插入數(shù)據(jù)元素算法：元素移動(dòng)的次數(shù)不僅130

刪除數(shù)據(jù)元素算法:元素移動(dòng)的次數(shù)也與表長n有關(guān)。刪除一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為(n-1)/2。刪除算法的平均時(shí)間復(fù)雜度為O(n)。模塊1：線性結(jié)構(gòu) 刪除數(shù)據(jù)元素算法:元素移動(dòng)的次數(shù)也與表長n有關(guān)。刪除一個(gè)131例、在一個(gè)長度為n的順序表中刪除第i個(gè)元素（1≤i≤n）時(shí)，需向前移動(dòng)

個(gè)元素。A.n B.i-1 C.n-i D.n-i+1例、在一個(gè)長度為n的順序表中刪除第i個(gè)元素（1≤i132例、設(shè)線性表有n個(gè)元素，以下操作中，

在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高。A.輸出第i（1≤i≤n）個(gè)元素值B.交換第1個(gè)元素與第2個(gè)元素的值C.順序輸出這n個(gè)元素的值D.輸出與給定值x相等的元素在線性表中的序號(hào)例、設(shè)線性表有n個(gè)元素，以下操作中，在順序表上133例．已知長度為n的線性表L采用順序存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，刪除其中所有元素值在[x,y]之間的所有元素。解法一：對(duì)應(yīng)的算法如下：voiddelxy1(SqList&L,ElemTypex,ElemTypey){intk=0,i; //k記錄不滿足條件的元素個(gè)數(shù)for(i=0;i<L.length;i++)

if(!(L.data[i]>=x&&L.data[i]<=y)) {L.data[k]=L.data[i]; k++; //不滿足條件的元素個(gè)數(shù)增1 } L.length=k; //順序表L的長度等于k}例．已知長度為n的線性表L采用順序存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)在134解法二：對(duì)應(yīng)的算法如下：voiddelnode2(SqList&L,ElemTypex,ElemTypey){intk=0,i=0; //k記錄滿足條件的元素個(gè)數(shù)while(i<L.length){ if(L.data[i]>=x&&L.data[i]<=y) k++; else L.data[i-k]=L.data[i]; //當(dāng)前元素前移k個(gè)位置

i++;}L.length=L.length-k; //順序表L的長度遞減}解法二：對(duì)應(yīng)的算法如下：135（2）鏈表

定義單鏈表結(jié)點(diǎn)類型:typedefstructLNode{ElemTypedata;structLNode*next; /*指向后繼結(jié)點(diǎn)*/}LinkList;存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)（2）鏈表定義單鏈表結(jié)點(diǎn)類型:存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)136定義雙鏈表結(jié)點(diǎn)類型:typedefstructDNode {ElemTypedata;structDNode*prior; /*指向前驅(qū)結(jié)點(diǎn)*/structDNode*next; /*指向后繼結(jié)點(diǎn)*/}DLinkList;模塊1：線性結(jié)構(gòu)定義雙鏈表結(jié)點(diǎn)類型:模塊1：線性結(jié)構(gòu)137

■單鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：（1）頭插法建表和尾插法建表算法，它是很多算法設(shè)計(jì)的基礎(chǔ)；（2）查找、插入和刪除操作。模塊1：線性結(jié)構(gòu)■單鏈表基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：（1）頭插法建表和138

頭插法建表

該方法從一個(gè)空表開始,讀取字符數(shù)組a中的字符,生成新結(jié)點(diǎn),將讀取的數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中,然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上,直到結(jié)束為止。采用頭插法建表的算法如下:模塊1：線性結(jié)構(gòu)頭插法建表模塊1：線性結(jié)構(gòu)139voidCreateListF(LinkList*&L,ElemTypea[],intn){LinkList*s;inti;L=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建頭結(jié)點(diǎn)*/

L->next=NULL;for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/s->data=a[i];s->next=L->next;

/*將*s插在原開始結(jié)點(diǎn)之前,頭結(jié)點(diǎn)之后*/

L->next=s;}}模塊1：線性結(jié)構(gòu)voidCreateListF(LinkList*&140

尾插法建表

頭插法建立鏈表雖然算法簡單,但生成的鏈表中結(jié)點(diǎn)的次序和原數(shù)組元素的順序相反。若希望兩者次序一致,可采用尾插法建立。該方法是將新結(jié)點(diǎn)插到當(dāng)前鏈表的表尾上,為此必須增加一個(gè)尾指針r,使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。采用尾插法建表的算法如下:模塊1：線性結(jié)構(gòu)尾插法建表模塊1：線性結(jié)構(gòu)141voidCreateListR(LinkList*&L,ElemTypea[],intn){LinkList*s,*r;inti;L=(LinkList*)malloc(sizeof(LinkList)); /*創(chuàng)建頭結(jié)點(diǎn)*/

r=L;/*r始終指向終端結(jié)點(diǎn),開始時(shí)指向頭結(jié)點(diǎn)*/for(i=0;i<n;i++){s=(LinkList*)malloc(sizeof(LinkList));/*創(chuàng)建新結(jié)點(diǎn)*/

s->data=a[i];r->next=s;/*將*s插入*r之后*/r=s;}

r->next=NULL; /*終端結(jié)點(diǎn)next域置為NULL*/}voidCreateListR(LinkList*&142例、設(shè)一個(gè)整數(shù)線性表采用帶頭節(jié)點(diǎn)的hc單鏈表存放，設(shè)計(jì)一個(gè)算法在不破壞原有單鏈表的前提下，創(chuàng)建兩個(gè)單鏈表ha和hb，前者由hc中值為奇數(shù)的節(jié)點(diǎn)構(gòu)成，后者由hc中值為偶數(shù)的節(jié)點(diǎn)構(gòu)成。例、設(shè)一個(gè)整數(shù)線性表采用帶頭節(jié)點(diǎn)的hc單鏈表存放，設(shè)計(jì)一143voidsplit(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb,*s;ha=(LinkList*)malloc(sizeof(LinkList));

ra=ha;hb=(LinkList*)malloc(sizeof(LinkList));

rb=hb;while(p!=NULL){ if(p->data%2==1) //奇數(shù)節(jié)點(diǎn) {s=(LinkList*)malloc(sizeof(LinkList)); s->data=p->data; //復(fù)制產(chǎn)生節(jié)點(diǎn)*s

ra->next=s; //將*s節(jié)點(diǎn)鏈接到ha尾部 ra=s; } else //偶數(shù)節(jié)點(diǎn) {s=(LinkList*)malloc(sizeof(LinkList)); s->data=p->data; //復(fù)制產(chǎn)生節(jié)點(diǎn)*s

rb->next=s; //將*s節(jié)點(diǎn)鏈接到hb尾部 rb=s; } p=p->next;}

ra->next=rb->next=NULL; //兩鏈表尾節(jié)點(diǎn)next均置為NULL}voidsplit(LinkList*hc,LinkL144

■雙鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：插入和刪除結(jié)點(diǎn)的算法。模塊1：線性結(jié)構(gòu)■雙鏈表基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：插入和刪除結(jié)點(diǎn)的算法。145

■循環(huán)鏈表基本運(yùn)算的實(shí)現(xiàn)

重點(diǎn)：判斷最后一個(gè)結(jié)點(diǎn)。模塊1：線性結(jié)構(gòu)■循環(huán)鏈表基本運(yùn)算的實(shí)現(xiàn)重點(diǎn)：判斷最后一個(gè)結(jié)點(diǎn)。模塊1462.棧

（1）棧的定義棧是一種先進(jìn)后出表。插入刪除受限的線性表。棧的基本運(yùn)算:進(jìn)棧，出棧。邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)2.棧邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)147（2）順序棧typedefstruct{ElemTypedata[MaxSize];inttop; /*棧頂指針*/}SqStack;存儲(chǔ)結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)（2）順序棧typedefstruct存儲(chǔ)結(jié)構(gòu)之一模塊1148?？諚l件:s.top==-1棧滿條件:s.top==MaxSize-1進(jìn)棧:top++;s.data[s.top]=e;出棧:e=s.data[s.top];s.top—;順序棧的4要素:模塊1：線性結(jié)構(gòu)?？諚l件:s.top==-1順序棧的4要素:模塊1：線149（3）鏈棧

typedefstructlinknode{ElemTypedata; /*數(shù)據(jù)域*/structlinknode*next; /*指針域*/}LiStack;存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)（3）鏈棧typedefstructlinknode存150帶頭結(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)(也可不帶頭結(jié)點(diǎn))?？諚l件:s->next==NULL棧滿條件:?模塊1：線性結(jié)構(gòu)帶頭結(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)(也可不帶頭結(jié)點(diǎn))?？諚l件:s->ne1513.隊(duì)列

（1）隊(duì)列的定義

隊(duì)列是一種先進(jìn)先出表。插入刪除受限的線性表。隊(duì)列的基本運(yùn)算:進(jìn)隊(duì),出隊(duì)邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)3.隊(duì)列（1）隊(duì)列的定義邏輯結(jié)構(gòu)模塊1：線性結(jié)構(gòu)152（2）順序隊(duì)typedefstruct{ElemTypedata[MaxSize]；intfront,rear；/*隊(duì)首和隊(duì)尾指針*/}SqQueue；

存儲(chǔ)結(jié)構(gòu)之一模塊1：線性結(jié)構(gòu)（2）順序隊(duì)typedefstruct存儲(chǔ)結(jié)構(gòu)之一模153隊(duì)空:q.front==q.rear隊(duì)滿:(q.rear+1)%MaxSize==q.front進(jìn)隊(duì):q.rear=(q.rear+1)％MaxSize;q.data[q.rear]=e;出隊(duì):q.front=(q.front+1)％MaxSize;e=q.data[q.front];環(huán)形隊(duì)列的4要素:模塊1：線性結(jié)構(gòu)隊(duì)空:q.front==q.rear環(huán)形隊(duì)列的4要素:154（3）鏈隊(duì)structqnode/*數(shù)據(jù)結(jié)點(diǎn)*/{ElemTypedata;structqnode*next;}QNode;typedefstruct/*頭結(jié)點(diǎn)*/{QNode*front;QNode*rear;}LiQueue;存儲(chǔ)結(jié)構(gòu)之二模塊1：線性結(jié)構(gòu)（3）鏈隊(duì)structqnode/*數(shù)據(jù)結(jié)點(diǎn)*/存儲(chǔ)結(jié)155（2）順序串

（3）鏈串

（4）串的模式匹配算法：BF、KMP4.串（1）串的定義

串、子串、串相等、空串、空格串模塊1：線性結(jié)構(gòu)（2）順序串（3）鏈串（4）串的模式匹配算法：BF、KM1565.數(shù)組和稀疏矩陣

（1）數(shù)組的定義相同類型數(shù)據(jù)元素、有限序列模塊1：線性結(jié)構(gòu)5.數(shù)組和稀疏矩陣模塊1：線性結(jié)構(gòu)157（2）數(shù)組的存儲(chǔ)結(jié)構(gòu)

以行序?yàn)橹餍?LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k

以列序?yàn)橹餍騆OC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k

以數(shù)組A[c1..d1,c2..d2]為例模塊1：線性結(jié)構(gòu)（2）數(shù)組的存儲(chǔ)結(jié)構(gòu)以行序?yàn)橹餍?以列序?yàn)橹餍蛞詳?shù)組158（3）特殊矩陣的壓縮存儲(chǔ)■對(duì)稱矩陣

若一個(gè)n階方陣A[n][n]中的元素滿足ai,j=aj,i（0≤i，j≤n-1），則稱其為n階對(duì)稱矩陣。

A[0..n-1][0..n-1]

B[0..n(n+1)/2]

i(i+1)/2+j 當(dāng)i≥j時(shí)k=j(j+1)/2+i 當(dāng)i＜j時(shí)模塊1：線性結(jié)構(gòu)（3）特殊矩陣的壓縮存儲(chǔ)■對(duì)稱矩陣A[0..n-1][0159■三角矩陣

采用類似的壓縮方法.模塊1：線性結(jié)構(gòu)■三角矩陣采用類似的壓縮方法.模塊1：線性結(jié)構(gòu)160（4）稀疏矩陣存儲(chǔ)結(jié)構(gòu)：■三元組表示■十字鏈表表示

各種表示的基本思路。非零元素遠(yuǎn)小于元素總數(shù)。模塊1：線性結(jié)構(gòu)（4）稀疏矩陣存儲(chǔ)結(jié)構(gòu)：非零元素遠(yuǎn)小于元素總數(shù)。模塊1：線161

■一個(gè)廣義表中所含元素的個(gè)數(shù)稱為它的長度.6.廣義表GL=(a,(a),(a,b,c,d),())長度為4。模塊1：線性結(jié)構(gòu)■一個(gè)廣義表中所含元素的個(gè)數(shù)稱為它的長度.162

■一個(gè)廣義表中括號(hào)嵌套的最大次數(shù)為它的深度.GL=(a,(a),(a,b,c,d),())深度為2。模塊1：線性結(jié)構(gòu)■一個(gè)廣義表中括號(hào)嵌套的最大次數(shù)為它的深度.GL163

■表的第一個(gè)元素a1為廣義表GL的表頭，其余部分(a2，…，ai，ai+1，…，an)為GL的表尾.

GL=(a,(a),(a,b,c,d),())表頭為a，表尾為((a),(a,b,c,d),())模塊1：線性結(jié)構(gòu)■表的第一個(gè)元素a1為廣義表GL的表頭，其余164模塊2：樹形結(jié)構(gòu)

（1）樹的定義遞歸定義適合于表示層次結(jié)構(gòu)的數(shù)據(jù)1.樹模塊2：樹形結(jié)構(gòu)（1）樹的定義1.樹165（2）樹的表示法（邏輯表示方法）■樹形表示法■文氏圖表示法■凹入表示法■括號(hào)表示法模塊2：樹形結(jié)構(gòu)

（2）樹的表示法（邏輯表示方法）■樹形表示法模塊2：樹166（3）樹的遍歷■先根遍歷算法■后根遍歷算法模塊2：樹形結(jié)構(gòu)

（3）樹的遍歷■先根遍歷算法模塊2：樹形結(jié)構(gòu)167（4）樹和二叉樹的相互轉(zhuǎn)換■樹二叉樹■二叉樹樹模塊2：樹形結(jié)構(gòu)

（4）樹和二叉樹的相互轉(zhuǎn)換■樹二叉樹模塊2：1682.二叉樹

（1）二叉樹的定義根、左子樹、右子樹完全二叉樹,滿二叉樹的定義模塊2：樹形結(jié)構(gòu)

2.二叉樹（1）二叉樹的定義模塊2：樹形結(jié)構(gòu)169

性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加1。即n0=n2+1.

性質(zhì)2非空二叉樹上第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。（2）二叉樹性質(zhì)模塊2：樹形結(jié)構(gòu)

性質(zhì)1非空二叉樹上葉結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)170

性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)（h≥1）。

性質(zhì)4完全二叉樹的性質(zhì)。

性質(zhì)5具有n個(gè)（n＞0）結(jié)點(diǎn)的完全二叉樹的高度為log2(n+1)或log2n+1。（2）二叉樹性質(zhì)模塊2：樹形結(jié)構(gòu)

性質(zhì)3高度為h的二叉樹至多有2h-1個(gè)結(jié)171

例、將一棵有98個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為

。

A.98B.99C.50D.不存在模塊2：樹形結(jié)構(gòu)

例、將一棵有98個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層172

例深度為5的二叉樹至多有

個(gè)結(jié)點(diǎn)。

A.16B.32C.31D.10