學(xué)時安授課34+上機(jī)章章1278268圖234944串45262 數(shù)硬第一 C1.11.1數(shù)值計數(shù)學(xué)模型數(shù)學(xué)模型→選擇計算機(jī)語言→編出程序→測試→終解答。數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？程序設(shè)計 比較關(guān)注程序設(shè)計的技巧。非數(shù)值計加以描間的相互關(guān)系一般無法用數(shù) 1女2男1.21.2研究數(shù)據(jù)元間的客觀聯(lián)系

邏輯結(jié)研究具有某種邏輯關(guān)系的數(shù)據(jù)在計算器內(nèi)的方式 結(jié)算由數(shù)據(jù)元素的有限集合及所有數(shù)據(jù)元間的關(guān)系Data_Structure={D,所有數(shù)據(jù)元間的關(guān)系的有限集合樹形結(jié)構(gòu)圖狀結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)SETK={01,02,03,04,05,06,07,08,09,10}R={}數(shù)據(jù)結(jié)K={01,02,03,04,05,06,07,08,09,10R={<05,01>,<01,03>,<03,08>,<08,02>,<07,04>,<04,06>,<06,09>,<09,10>數(shù)據(jù)元間的聯(lián)系數(shù)據(jù)結(jié)TREE=（K,R）K={01,02,03,04,05,06,07,08,09,10R={<03,08>,<03,09>,<04,10>

數(shù)據(jù)之間的聯(lián)系Graph=(D,RD={1,2,3,4,5,6,7,8,9R={數(shù)據(jù)之間的聯(lián)系 結(jié)構(gòu)（StorageStructure):數(shù)據(jù)在計算機(jī)中的表示(或稱映象）稱為數(shù)據(jù)的結(jié)構(gòu)，又稱為物理結(jié)四種基本 方法 結(jié)構(gòu)索 方散 方同一種邏輯結(jié)構(gòu)可采用不同的方法（以上四種結(jié)構(gòu):間的邏輯關(guān)系鏈鏈結(jié)構(gòu)：在每一個數(shù)據(jù)元素中增存放地址的指針，用此指針來表示數(shù)據(jù)的邏輯關(guān)系間線性結(jié)數(shù)據(jù)的邏輯結(jié)

隊串及數(shù)樹形結(jié)數(shù)據(jù) 結(jié)

非線性結(jié)散

圖形結(jié)數(shù)據(jù)的運(yùn)算查找、排序 、刪除、修改1.31.3算法算法是用來解決某個特定問題的指令的集合2程序設(shè)計語言形式（如C語言等輸入性有0輸出性有一個或多個輸出(處理結(jié)果)確定性有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束；整個指令序可行性（有效性）算法中的每一個步驟都應(yīng)當(dāng)能55時間復(fù)雜度空間復(fù)雜度

一個程序在計算機(jī)中運(yùn)行時間的多少與諸多因問題的規(guī)模程序中語句的執(zhí)行次數(shù)T(n)/f(n)為一不等于零的實常數(shù)，則f(n)為T(n)的稱O(f(n))例 /*3n+24nforn2*/ /*10n2+4n+211n2forn5*/ /*6*2n+n27*2nforn4常用的計算規(guī)則加T(n)=T1(n)+T2(n)=O(f1(n))+=O(max(f1(n),乘T(n)=T1(n)×T2(n)=O(f1(n))=復(fù)雜復(fù)雜度復(fù)雜度注空間復(fù)雜度S(n)按數(shù)量級遞增順序也與上表類例2例例例n1/2-例x=91;if(x>100){x=x-10;y--else例inti,j,k,x=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)2100,(3/2)n,(2/3)n,nn,n0.5,n!,2n,lgnnlgn、(3/2)n、2nn(2/3)n<2100<lgn<n0.5<n3/2<nlgn<(3/2)n<2n<n!<1、數(shù)據(jù)結(jié)構(gòu)是指計算機(jī)處理的①的組織形式以及它們相互之間的②。①.數(shù)據(jù)元B.計算方C.邏輯D.數(shù)據(jù)映②A.結(jié).關(guān)C.運(yùn)D.算 結(jié)構(gòu)關(guān)系、組織形C.數(shù)據(jù)元素、數(shù)據(jù)對D.數(shù)據(jù)復(fù)雜性、程序復(fù)雜空間復(fù)雜3、衡量算法好壞的兩個主要空間復(fù)雜的時間復(fù)雜度 4、下面程序段的時間復(fù)雜度是O(n) {}5、算法的時間復(fù)雜度僅與問題的規(guī)關(guān)。*

（）6、下面程序段A[i][j]=0執(zhí)行次n(n+1)/2,

作業(yè)：P251-1，1-2，1－3，復(fù)習(xí) C語言的數(shù)據(jù)類 short;long; float;double;long

int33i

33

指針變量的定intint*i_pointer; *5x5{int

{int

6x6}

voidFunction1(int{}

voidFunction1(int{(*px)++;}數(shù)組類int &a[0], a[0], ‘‘\0’為字chara[40]=“Iamastrlen(a為5.定義結(jié)構(gòu)體類型變量定義結(jié)構(gòu)體類型

struct{charname[10];intage;float定義結(jié)構(gòu)體類型變量structstudentstudent1;structstudentstructstudent6.typedefcharelemtype;typedefstructstudent{charname[10];intage;float}stu;elemtypea;stustudent1;數(shù)據(jù)數(shù)據(jù)元 數(shù)據(jù)數(shù)據(jù)元學(xué) 籍 出生年 住 06048002楊 例例民其劉曉男漢…男回…男壯………………女漢…邏輯邏輯結(jié)結(jié) …… 鏈?zhǔn)浇Y(jié)… ∧…100元錢買100只雞，母雞每只5求解：設(shè)母雞、公雞、小雞各為i,j,k只，則有只需要解出本方程就可以得到答案方法1：用三重for(i=0;i<=100;i++)for(j=0;j<=100;j++)for(k=0; if(k%3==0&&(i+j+k)==100&&(5*i+3*j+k/3)==100)printf(“%d,%d,%d\n”,i,j,k);}方法2、3：用兩重循因總共買100只雞，所以小雞的數(shù)目可以由母雞數(shù)和公雞數(shù)得到。for(i=0;i<100;i++)for(j=0;j<100;j++){forfor{k=100-i-jif(k%3==0&&(5*i+3*j+k/3)==100)}方法4：用一重循和 合并為個和 合并為個 ,,j,}Chapter Linear要點回數(shù)據(jù)結(jié)構(gòu)課程——涉及數(shù)學(xué)、計算機(jī)硬件和計算數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合用D_S=DRS=(D表示數(shù)據(jù)結(jié)構(gòu)內(nèi)容——數(shù)據(jù)的邏輯結(jié)構(gòu)、結(jié)構(gòu)和算算法效率指標(biāo)——時間效率和空間效數(shù)據(jù)的結(jié)

邏輯結(jié)構(gòu)唯邏輯結(jié)構(gòu)唯結(jié)結(jié)構(gòu)數(shù)據(jù)的運(yùn) 、刪除、修改、查找、排序運(yùn)算的運(yùn)算的實現(xiàn)線性表的順序結(jié)線性表的鏈?zhǔn)浇Y(jié)構(gòu)（單鏈表線性結(jié)構(gòu)的若結(jié)構(gòu)是非空有限集，則有且僅有一個開始結(jié)可表示為：（a0, , an-線性結(jié)構(gòu)的結(jié)點和一個尾結(jié)點其他結(jié)點只有一個直接前驅(qū)和一線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最典型最常用的是------線性表的定義：用數(shù)據(jù)元素的有限序列表（a0,a1…ai- ai＋1，…,an-線性起（首結(jié)點

數(shù)據(jù)元ai的直接前趨ai的直接后n=0時稱為空

線性終（尾點n為元素總數(shù)，即表例 分析26個英文字母組成的英文（A,B,C,D, ,數(shù)據(jù)元素都是字母 元間的關(guān)系是線性例 分析學(xué)生情況登記學(xué)班女微電何仕男微電王女微電男微電：：：：：每個數(shù)據(jù)元素由5個數(shù)據(jù)項組成;元間的關(guān)系是線性Initia 初始化操作。建立一個空線性表L Insert(L,i,x)前插 ai之 線性表的順序結(jié)構(gòu)—順序一、順序用一組地址連續(xù)的單元線性表的各個數(shù)據(jù)元素，稱作線性表的順序結(jié)構(gòu)，簡稱 若已知表中首元素在器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)，參見 結(jié)構(gòu)示意圖）。線性表的順序結(jié)構(gòu)示意邏輯地 數(shù)據(jù)元 地址數(shù)據(jù)元……1每個元 占K字i…

……… 每個數(shù)組元素用相鄰的５個字節(jié)。器按字節(jié)編址，設(shè)數(shù)組元素Ｍ[０]的第節(jié)的地址是113解：地址計算通式為 =LOC(a0)+L因此：LOC(M[3]985#defineMaxlen100typedefstruct{charname[10];charsex;int

/*順序表最大長度MF}

elemtype

intnum=-

/*當(dāng)前數(shù)據(jù)元素下標(biāo)typedef{typedef{elemtypeList[Maxlen];intnum;}……s-s- s-SeqLista;SeqListSeqLista;SeqList二、順序表的基本操初始化ListInitiavoidListInitiate(SeqList{L->num=- intintListLength(SeqList{return}intListGet(SeqListL,inti,elemtype{{printf(“ERROR!\n”);return0;} return1;}（在第i個（0<=i<=n）數(shù)據(jù)元前……an-1…Maxlen-

……an-…n…Maxlen-

…x…an-…n…Maxlen-

是否滿足是否滿足表長加表長加用c語言描述算intListInsert(SeqList*L,inti,elemtype{intif(i<0||i>L->num+1 printf(“error\n”);return0; if(L->num)>=Maxlen-1) for(j=L->num;j>=i;j--L->list[j+1]＝L-

判斷iL-L->num＝L-return}

Eis

nn一個元素所需平均移動次數(shù)1一個元素所需平均移動次數(shù)1ni0 Eis

n

(ni0

i)

n

ni0

n

i0n

n

n(n1) 因此因此,該算法的時間復(fù)雜度為O(n)……an-1 …Maxlen-

……an-…Maxlen-YNYi？NYNYi？N表長減a[j-1]=a[j];用c語言描述刪除算intListDelete(SeqList*L,inti,elemtype{intif(L- printf(“\nThelistisreturn

元素,并將其保存在x中elseifi<0||i>L- printf(“\nthepositionisinvalid”);return0; {*x=L-

for(j=i+1;j<=L->num;j++)L->list[j-1]=L-return1;}}

Edl

Edl：刪除Edl：刪除一個元素所需平均移動次1i0

(ni)

1(ni1ni0（ n（

n1 i0

i0(n

1)

1n(n1)n因此,該算法的時因此,該算法的時間復(fù)雜度為O(n)順序表時間效率分析 T(n)=O(移動元素次數(shù)順序表空間效率分析順序表的空間復(fù)雜度三、順序結(jié)構(gòu)的特可以方便地隨機(jī)存取

作業(yè)：P552-82-14第二章性邏輯結(jié)構(gòu)

結(jié)構(gòu)：順序、鏈缺點 線性表的鏈?zhǔn)浇Y(jié)構(gòu)—鏈

單鏈表的基本概 線性表鏈?zhǔn)浇Y(jié)構(gòu)的一種。用一組不一定連續(xù)的單元來存放數(shù)據(jù)元數(shù)據(jù)數(shù)據(jù)

a1^a1^指針單鏈表 結(jié)typedefstructNode DataTypedata;structNode*next;}SLNode；

單鏈結(jié)點的定義……第2……第2第3第1第1第3……邏輯示意第2第2第1鏈表結(jié)構(gòu)示意頭結(jié)頭結(jié)

首元結(jié)

^^^結(jié)點的單鏈表^ 結(jié)點的空單鏈表^^

不結(jié)點的單鏈 head==NULL 不結(jié)點的空單鏈何謂頭指針、頭結(jié)點和首元結(jié)點頭指 頭結(jié)點首元結(jié) 例：一個線性表的邏輯結(jié)構(gòu)為，其結(jié)構(gòu)用單鏈表表示如下，請問其地數(shù)據(jù)指針171地數(shù)據(jù)指針171777∴頭指針的值是 ②H區(qū)別：無頭結(jié)有頭結(jié)動態(tài)內(nèi)存分設(shè)計根據(jù)具體問題的具體需要，在程序運(yùn)行時

##includeMemoryMemory函數(shù)原型：void*mallocunsigned用于向系統(tǒng)動態(tài)申請size個字節(jié)的內(nèi)存單元空sizeof運(yùn)算符 功能：

voidfreevoid*函數(shù)功能：用于動態(tài)分配的內(nèi)存空間強(qiáng)制類型轉(zhuǎn)typedefstructtypedefstructnodetype intdata;structnodetype}SLNode;SLNode*p;p=(SLNode*)malloc(sizeof(SLNode)p

…一級指一級指 二級二級指

單鏈表的操作實（1）

{SLNode*

頭結(jié)

ListInitiate}intListInitiate(SLNode**head{if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}…求當(dāng)…1p1p

intListLength(SLNode SLNode*p=head;intsize=0; size++;}return}

pp

^an-^an-while(p-{p=p-j++;

*x=p-intListGet(SLNode*head,inti,DataType SLNode*p;intj=0;{p＝p-

if

{printf(“取元素位置參數(shù)錯！”);return0; return1;}

/*將數(shù)據(jù)元素值賦給運(yùn)算（前插，即在ai之 一個數(shù)據(jù)素

an-an-ai-xx xx步驟:（1）

：1

2、ai-1結(jié)點的指針域指向x

…

…

p{

^an-ai-^an-ai-

x}

s=(SLNode*)malloc(sizeof(SLNode));s->next=p-p-用c語言實現(xiàn)的單鏈表算intListInsert(SLNode*head,inti,DataType{SLNode*p,intj;

{p=p->next;}

{printf(“\n return0;}if((s=(SLNode*

return0;return1;

單鏈表的刪除（刪除第i(i>=0)個結(jié)點

……sai-p{p=p->next;}

s=p-用c語言實現(xiàn)的單鏈表刪除算ListDelete(SLNode*head,inti,DataTypeSLNodeSLNodeintwhile(p->next!=NULL&&p->next->next!=0&&j<i- if(j!=i- printf(“\n刪除位置不合理!”}s=p-p->next=p->next-

將ai除return1;}

#include<stdio.h>#defineMAXLEN100typedefintdatatype;typedefstruct{datatypeList[MAXLEN];intnum;函數(shù)void{case1:調(diào)用初始化函數(shù);break;case2:調(diào)用函數(shù);break;case3:調(diào)用刪除函數(shù);break;case4:調(diào)用輸出函數(shù);break;case5:break;｝(6尾接p{if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;鏈表創(chuàng)建結(jié)束鏈表創(chuàng)建結(jié)束YNintCreatL1(SLNode**h,DataTypea[],int inti,j;if(i==0)return0;{if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;p=s;}return (6hh{if((s=(SLNode*return}鏈表創(chuàng)建結(jié)束Y鏈表創(chuàng)建結(jié)束YNintCreatL2(SLNode**h,DataTypea[],int{SLNode*s;inti,j;if(i==0)return0;{if((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)return0;(*h)->next=s;}return}2.3.52.3.5

空 >next==head 2.3.6雙向循環(huán)鏈

typedefstruct{DataTypestructNode}要點線性表的鏈?zhǔn)健渾?：線性表的邏輯結(jié)構(gòu)特點是什么？其順序答性表邏輯結(jié)構(gòu)特點是，只有一個首結(jié)點和尾結(jié)點；除首尾結(jié)點外其他結(jié)點只有一個直接前驅(qū)和一個直接后繼。簡言鏈?zhǔn)綍r，相鄰數(shù)據(jù)元素可隨意存放，但所占空間問2：順序和鏈?zhǔn)礁饔心男﹥?yōu)缺點 鏈?zhǔn)降膬?yōu)點是或刪除元素時很方便，使事實上，鏈表、刪除運(yùn)算的快捷是以空間問3：在什么情況下用順序表比鏈答：順序表適宜于做查找這樣的靜態(tài)操作；鏈表于 若線性表的長度變化較大，且其主要操作是、是查找 和刪除主要發(fā)生應(yīng)用實例#defineMAX100typedefintDataType;typedefstruct{DataTypeintnum/*最后一個數(shù)據(jù)元素的下標(biāo)voidDeleteSeqList(SeqList*la,DataTypex intj,kfor(j=0;j<=la->num;j++ if(la->List for(k=j;k<la-la->List[k]=la->List[k+1];}}}應(yīng)用實例刪除順序表a中第i(i>=0)個元素起的k。#defineMAX100typedefintDataType;typedefstruct{DataTypeintnum;/*最后一個數(shù)據(jù)元素的下標(biāo)intDeleteK(SeqList*a,inti,int{intif(a-

{printf(“順序表已空！\n”);return0; elseif(i<0||k<0||i+k-1>a->num)return0;{for(j=i;j<=a->num-k;j++)a->num=a->num-k;return1;}}

應(yīng)用實例在有序順序表中值為x的數(shù)據(jù)元素以保持順序表的有序性。#defineMAX100typedefintDataType;typedefstruct{DataTypeintnum;/*最后一個數(shù)據(jù)元素的下標(biāo)intOrderlnsert(SeqList*L,DataTypex{intiif(L->num==Max-{printf順序表已滿”);return0;}{for(i=L->num;i>=0 ;i--)L->List[i+1]=L->List[i];return1; }應(yīng)用實例實現(xiàn)單鏈表的就地逆序。設(shè)其頭結(jié)點的指針為，編寫一個算法將單鏈表逆置a2a2q單鏈表的逆voidreverse(SLNode{SLNode*p,*q;p=head-head->next=NULL;while(p!=NULL){q=p=p-q->next=head->next;head->next=q;}}應(yīng)用實例LaLa=(3,5,8,11Lb=(2,6,8,9,11,15,20合并結(jié)果Lc2,3,5,6,8,8,9,11,11,15,20順序表結(jié)typedef{elemtypeList[maxlen];intnum;}intmergeql(qltypela,qltypelb,qltype{inti,j,k;{printf(“\n數(shù)組下界溢出return}{}while(i<=la.num)lc->list[k++]=la.list[i++];while(j<=lb.num)lc->list[k++]=lb.list[j++];return}單鏈表結(jié)typedefstruct{elemtypedata;structslnode*next;}Pa、Pb用于搜索La和Lb，Pc指向新鏈表當(dāng)前結(jié)358^358^8282996^6…532 …532^intmergesl(slnodetype*la,slnodetype*lb,{slnodetype*pa,if(*lc=(slnodetype{printf(“\n分配內(nèi)存失??！”);return0;}{if(pc->next=(slnodetype{printf(“\n分配內(nèi)存失?。　?;return0; if(pa->data<=pb-{pc->data=pa->data; {pc->data=pb->data;pb=pb->next;}{ifpc->next=(slnodetype{printf(“\n分配內(nèi)存失??！”);return0; {ifpc->next=(slnodetype{printf(“\n分配內(nèi)存失??！”); return0; pc->next=NULL;return思考1、不用1、不用，直接把a(bǔ)表插到b表中；或者把b表插到a表中，如何編程？2、要求不能有重復(fù)的數(shù)據(jù)元素，如何編程了解線性表的定義和線性結(jié)構(gòu)的特點 會用單鏈表編寫、刪除等有關(guān)算法作業(yè)： 2-14(單鏈表）2- intListInitiate(SLNode**head{if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}Chapter Stackand3.1堆棧 3.2隊列定邏輯結(jié)結(jié)運(yùn)算規(guī)實現(xiàn)方

定邏輯結(jié)結(jié)運(yùn)算規(guī)實現(xiàn)方定堆棧是限定只能在表的一端進(jìn)行和刪除的入和刪除的一端叫做頂(top)；表的另一端則叫做棧底(base)。

an-an-…an-

LastLast *堆棧與一般線性表的比較一般線性邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：例一個棧的輸入序列為123，若在入棧的過程中允答：可以通過窮舉所有可能性來求解①1入12入2出，3入3出即②1入12、3入，3、2出即③1、2入，23入3出，1即④1、2入，2、1出，3入3出即⑤1、2、3入，3、2、1出即合計有5種可能性*二、堆棧的操1、初始2、進(jìn)3、退4、取5、判棧是否非三、棧的順序表示——順序堆

maxlen-43210順序棧的定typedefint#definemaxlen100/*順序堆棧數(shù)組最大單元個數(shù)typedefstruct/*順序棧定義{DataTypestack[maxlen];/*順序堆棧存放數(shù)據(jù)元素的數(shù)組*/inttop; } 2初始voidinistack(seqstack{s->top=- /*順序堆棧數(shù)組的當(dāng)前棧頂位置參數(shù)：S功能：判斷S是否為空，為空返回1，否則返回intempty(seqstack{return1;return}入intpush(seqstack*s,DataType{if(s->top==maxlen-{printf(“\nStackisfull”);return入棧入棧return}

出功能：彈出順序堆棧s的棧頂數(shù)據(jù)元素值到參數(shù)d，intpop(seqstack*s,DataType{if(s->top==-棧{printf("\nStackisempty!");return0; 棧{*d=s->stack[s->top--return tk[ t tk[ t] 棧頂下標(biāo)減取棧頂元intgettop(seqstacks,DataType{{printf(“\nStackisempty!”);return0;}{return1;}}順序棧的C語言描述：typedefint#definemaxlen10typedefstruct{elemtypestack[maxlen];inttop;兩個堆棧共享空間目的：節(jié)省空 ……… 兩個堆棧共享空間的運(yùn)算：初始出數(shù)據(jù)結(jié)構(gòu)定義 typedef{intLeftTop;intvoid{s-}intPushDqstack(dqstack*s,charWhichStack,DataTypereturn0;}if(WhichStack!=‘L’&&WhichStackreturn0;}if(WhichStack==‘L’)s->stack[++s->LeftTop]=x;return進(jìn)棧進(jìn)棧算共用堆棧的算法練習(xí)共用堆棧的算法練習(xí)四、棧的鏈?zhǔn)浇Y(jié)^

typedefintDataType;typedefstructsnode{DataTypedata;structsnode*next;} {LSNodeif((p=(LSNode*)if((p=(LSNode*){printf(“\n失敗”)returnp-

xhead- xreturn1;∧∧ intPopStack(LSNode*head,DataType鏈棧的出棧算鏈棧的出棧算ifif{printf(“underflow\n”);return*d=p- ∧∧return1;}p1：括號匹配問題（參考P66例3-2：數(shù)制轉(zhuǎn)換（十轉(zhuǎn) （Hanoi）4：表達(dá)式求N=(Ndivd)×d+Nmod例如：（1348)10=(2504)8 Ndiv8 Nmod8 將余數(shù)依次進(jìn)棧，再出（Hanoi）zyxzyxnn可以使用任一柱子 3321 表達(dá)式計后綴表達(dá)式：例例：A+B→中綴表達(dá)式：AB–CD)棧頂棧頂運(yùn)算符＋—×／()#＋>><<<>>—>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=步中綴表達(dá)輸1#2#A3#A4#A5#6#7#8#9#步中綴表達(dá)輸##ABCD/#ABCD/#＋ABCD/##＋ABCD/##ABCD/－E##ABCD/－E×T1←T2←B–T3←T2×T4←A+ABCD/

ABCD/

DCDCBAABCD/EEAT3=T2

BAT2=BBAABCD/AT4=A 作業(yè)：p873-6,3-一、隊列的基本概定 隊列又稱先進(jìn)先出 Out,FIFO)表1、初始化隊2、判定隊列是否為34、入隊列（將新元素隊尾5、出隊列（隊列頭元素出隊三、隊列的順序結(jié)#definemaxlen100typedefintDataType;typedefstruct{DataType, ,}隊隊列的進(jìn)隊和出隊543

FED入隊rear指示位置加入，rear=rear+1FED出隊front的元素取出，front=front+1。問：如何解決答：在順序隊列中，當(dāng)

FEDCFEDC 1 10如何實現(xiàn)用求模運(yùn)算0120123N-0123..隊頭指針進(jìn)隊頭指針進(jìn)1:frontfront1)隊尾指針進(jìn)1:rearrear1)隊列初始化：front=0&&rear隊空和隊滿的判斷665 4312

隊列隊滿:front＝＝rear&&tag＝＝1；隊空front＝＝rear&&tag＝＝0；隊滿:count>0&&front＝＝rear； 單元隊空voidiniqueue(sequeue*sq){sq->front=0;sq->rear=0;}

intaddqueue(sequeue*sq,DataType{if(sq->front==(sq->rear+1)%maxlen){printf(“\nQueueisfull”);return}sq->queue[sq->rear]=x;sq->rear=(sq->rear+1)%maxlen;return1;}intdelqueue(sequeue*sq,DataType{if(sq->front==sq->rear){printf("\nQueueisempty!");return0;}*d=sq->queue[sq->front];

sq->front=(sq->front+1)%maxlen;return1;}四、隊列的鏈?zhǔn)浇Y(jié)

^

隊列的鏈?zhǔn)浇Y(jié)隊頭在鏈頭，隊尾在鏈尾front>next鏈隊列的結(jié)構(gòu)體定typedefstruct{DataTypedata;structslnode*next;}

typedef{LQNode*front;LQNode*rear;}初始intInitiateSLQueue(LQueue{if((q-{printf(“\n申請空間失??！”);return0;return1;}

ifif((p=(LQNode*malloc(sizeof(LQNode)))==NULL)intaddq(LQueue*q,DataType{LQNode{printf(“\intaddq(LQueue*q,DataType{LQNodep-p-p->next=NULL;XpXp∧q->rear=p;∧returnreturn1;ppintdelqueue(LQueue*q,DataType{LQNodeif(q->front->next==NULL)returnpp=q->front- p∧*d=p-∧q->front->next=p->next;free(p);return}1>n可由用戶自定義2>3> 1>Panduan(charstr[],int2>EnterStr(charstr[],int*n)3>main() #defineMAXNUM80typedefchartypedef elemtypestack[MAXNUM];inttop;}typedef elemtypequeue[MAXNUM];intfront,rear; {charch,str[MAXNUM];intn;printf("\n是否繼續(xù)?(y/n): elsebreak;}}voidvoidEnterStr(charstr[],int{}intintPanduan(charstr[],int{qstypemyStack;typemyQueue;charx,y;inti;{}while(QueueNotEmpty(&myQueue)==1while(QueueNotEmpty(&myQueue)==1&&{QueueDelete(&myQueue,&x);{printf(“不是回文 return0;}return1;}StackInitiate(qstypeStackInitiate(qstype{{}intStackPush(qstype*s,elemtype if(s->top>=MAXNUM-1)return0;else{s->stack[++(s- return}}intStackPopintStackPop(qstype*s,elemtype{ (s->top)--;return1;}intintStackNotEmpty(qstype{if(s->top<0)returnreturn}{q->rear=}typeintQueueAppend type*q,elemtype{if(q->rear>=MAXNUM-1)return0;q->queue[(q->rear)++]=x;return}intintQueueDelete{type*q,elemtype*x=q->queue[(q->front)return}intintQueueNotEmpty{typeif(q->rear==q->front)returnreturn}：： 相同點：相同點：邏輯結(jié)構(gòu)相同，都是線性的；都可以用順序存儲或鏈表限的線性表（；棧和隊列是兩種特殊的線性表，即、刪除運(yùn)算加以限制）①運(yùn)算規(guī)則不同，線性表為隨機(jī)存取，而棧是只允許在 隊列是只允許在一端進(jìn)行 、另一端進(jìn)行刪除運(yùn)算，用途不同，線性表比較通用；堆棧用于元素的保存次 作業(yè)：p883-2,3-Chapter 數(shù)組的結(jié)一、數(shù)組的定 一維數(shù)組隨機(jī)存取結(jié)二維數(shù)

a0 a0 a0n-a1 a1 a1n- am-1 am-1 am-1n-Am×n=A=(a0a1…am-其中，ai=(ai0ai1…ain-數(shù)組中的數(shù)據(jù)元素數(shù)目固定數(shù)組中的數(shù)據(jù)元素具有相同的數(shù)據(jù)類型數(shù)組是一種隨機(jī)結(jié)構(gòu)，可隨機(jī)存取數(shù)組int

數(shù)組的結(jié)通常采用順序結(jié)以二維數(shù)組Amn為…a0(n-…a1(n-…a(m-a(m-…

…a(m-…a(m-…a(m-1)…a0(n-a1(n-…對于二維數(shù)組floata[5][4解：（1）5×4＝20（2）=2000+(3×4+2)：壓縮矩陣中非零元素的個數(shù)較少（一般小于 0i,j 則稱Aa0a1 a18926302517061389263025170613an-1 an-11an-12…an-1n-對稱矩陣的壓

1)2

j(j1)

21222212222502220613n階上（下）三角矩陣是指矩陣的矩陣B的結(jié)構(gòu)，則B中任一元素bij和sb[k]之間ik

i2

當(dāng)

當(dāng)i三、稀疏矩陣的壓縮 例：寫出下圖所示稀疏矩陣的壓縮形式0129000000000-30000–700方法1：用線性表表示((0,1,12)，(0,2,9)，(2,0,-3)，(3,2,24)，(4,1,18)，(5,0,15)，(5,3,-方法2：用三元組矩陣表示

0129000000000-300067678010292025053–700001200000001200000000-3007601h7601

–700020220-53-2553-25vji方法4：用鏈表表示vji用途：方法：每個非0元素占用5個域。

00000-300000-3000

–700

①每行非零元素成帶表頭結(jié)點的循環(huán)鏈表②每列非零元素也成帶表頭結(jié)點的循環(huán)鏈表。是列循環(huán)鏈表中的一個結(jié)點，即呈鏈狀。9201920100014#definemaxsize10000typedefin typedefstruct{

inti,j;elemtyped;typedefstruct{

/*ijtupletypeint

20 0 30 0

4440003

M

000000-000000000-000000000-00 -(0,1,(0,1,(0,2,9(2,0,-(2,4,(3,2,(4,1,(5,0,(5,3,-

(0,(0,2,-(0,5,(1,0,(1,4,(2,0,(2,3,(3,5,-(4,2,提問答：肯定不正確除了：（1）每個元素的行下標(biāo)和列下標(biāo)互換（即三元組中還應(yīng)該：（2）T的總行數(shù)md和總列數(shù)nd與M值不同（互換思路：反復(fù)掃描a.data中的列序，從小到大依次進(jìn)行轉(zhuǎn)置(0,1(0,19(2,(2,4,10(5,3,- 組 ④②⑦

(0(0,2,-(0,5,(1,0,(1,4,(2,0,(2,3,(3,5,-(4,2,voidtrantup(tabletypea,tabletype{intif(b-{

//q為b.datafor{

//col為掃描bifa.data[p].j==col)//p為a.data b-b- }}}}

演 23P1295-9，5-Chapter TreeandBinary樹5.1adfhijadfhij樹是由樹是由n(n0)個結(jié)點組成的有限集合。如果n=0，稱為空樹；如果n>0，則有一個特定的稱之為除根以外的其它結(jié)點劃分為m(m0)個互不相交的有限集合T0T1Tm-1，每個集合又是一棵樹，并且稱之為根的(SubTree)。每棵的根結(jié)點有且僅有一個直接前驅(qū)，但可以aabcdefghij除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點樹結(jié)構(gòu)除根結(jié)點之外的所有結(jié)點有且只有一個前驅(qū)結(jié)點，根結(jié)點沒有前驅(qū)結(jié)點樹結(jié)構(gòu)描述的是層次關(guān)abcdefghabfcdegh非樹結(jié) AABCDEFGHID:D=;空樹 R={<Root,ri>,i=1,2,…m}D;D={Root}DF Root:樹的根結(jié)DF:樹的根結(jié)點Root的集DFD1D2D3 并且DiDj(ij;i=1,2,…m;j=1,2,…m主要用于樹的屏幕和顯示abdefc hddbiejafgcha(b(d,e(i,j),f),c(g,h)ABCDEFGHIABCDEFGHI擁有的的個數(shù)。孩子、兄弟、雙親：樹中一個結(jié)點的的根結(jié)有序樹和無序樹：如果一棵樹中結(jié)點的各從左到右是有次序的，即若交換某結(jié)點各的相對位置A

葉子結(jié)：：：：結(jié)點A：：：：結(jié)點B的

樹的

結(jié)點M的 ：：結(jié)點B的孩：：

結(jié)點M的層：：：：結(jié)點L的：：：：

樹的深331、初始化6、將一棵樹到另一樹的指定結(jié)點為它的子7、刪除指定結(jié)點的某一delete(t,x,i) 雙親表示孩子表示孩子兄弟表示雙親孩子表示雙親表示（順 ABCDEFABCDEFGA-B0C0D0E2F2G51234566雙親表示法－－c#defineMAXNODE32typedefstructdatatypedata;int }ptree

孩子表示法（多重鏈表法 D∧BD∧BA

C∧∧E∧F∧E∧F∧∧∧I∧J∧DCBAJIHGEDCBAJIHGEFFtypedeftypedefstruct{{intstructTreeNdoe}}

孩子結(jié)點指針孩子結(jié)點指針ABCDEFGHIJABCDEFGHIJAB0C0D0E1∧F1∧G2∧H3∧I3∧J3∧0123∧145∧263789∧456789DFECDFEC4、孩子兄弟表示法（二重鏈表法兄弟結(jié)點指針ABABC兄弟結(jié)點指針ABABCDEFGG孩子兄弟表示—C語言描 typedeftypedefstruct{elemtypestructTreeNode*son;structTreeNode*next;}一棵二叉樹是結(jié)點的一個有限集合該集合或者為空，或者是由一個根結(jié)點加上兩分別稱為 和 的、互不相交的二叉組成

二叉左右左右左右左右 (2)殊二叉ABCDABCDEFGABCDEF行二叉，為i(0≤i≤n-1)的結(jié)點與為完全二叉樹為i的結(jié)點位置相同，則此樹 ABCDEF二叉排序樹：若為非空二叉樹根結(jié)點的都小于根結(jié)點關(guān)鍵字值，所有結(jié)點的關(guān)鍵字結(jié)點的關(guān)鍵字值都大于或等于根結(jié)所關(guān)鍵字值。一棵二叉排序樹和又分別123、 結(jié)4、 結(jié)56 性質(zhì)性質(zhì)1若二叉樹的層次從0開始i2i個結(jié)點。(i證明：i0時，有2i=20=1，成假定：ik時性質(zhì)成立；即有2k個結(jié)點當(dāng)ik+1時，第k+1的結(jié)點至多是第k層結(jié)點的兩倍，即總的結(jié)點個數(shù)至多為2×2k=2k+1故命題性質(zhì)性質(zhì)2若規(guī)定空樹的深度為-1，則深度為k2k+1-1個結(jié)點。(k-有2-1+1-1=020+21+22+23+…+2k=2k+1－性質(zhì)3對任何一棵二叉樹n0,度為2n2,為2的結(jié)點：n=n0+n1+n22、另一方面，二叉樹中一度結(jié)點有一個孩子，二度結(jié)n=n1+2n213n0=n2+性質(zhì)性質(zhì)4具有nlog2（n+1)-(“”表示上取整證明：設(shè)完全二叉樹的高度為h，則0123456789 2h-10123456789 2h<n+1<=h<log2(n+1)<=性質(zhì)5如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié) 0,1,…,n-1，然后按此結(jié)將樹中各結(jié)點順序地存放于一個一維數(shù)組中0i若i0,i若i0,i的雙親為(i若2*i+1ni的左孩子為2*i+1；否則(2*i+1>沒有左孩子，必定是葉子結(jié)若2*i+2<n,則i的右孩子為2*i+2；否則，i0

例1：i=5,2*i+1<n=17左兄弟：4，右兄弟：6例2：i=8,2*i+1=n二叉樹 結(jié) 順序結(jié) 完全二叉 010123456789ABCDEFGHIJAABCDEFGH010123456789ABCDEFGH情況樣，可能會浪費(fèi)很多空間，單支樹情況單支 順序二叉樹結(jié)點的c#defineMAXNODE elemtype^G^^H^鏈?zhǔn)浇Y(jié)^G^^H^鏈?zhǔn)浇Y(jié)構(gòu)形象化描述(不結(jié)點AA CABCDABCDEFGH ^E^ 鏈?zhǔn)浇Y(jié)構(gòu)形象化描述 )頭結(jié)ABCDEFABCDEFGH ^E^ ^E^^G^G^^H^typedef

左孩右孩typedefstruct{elemtypedata;structnode*Lchild；structnode*Rchild;}

intInitiate(bitree

頭結(jié)點{if((*bt=(bitree*)malloc(sizeof(bitree)))==NULL)return0;return1;}二叉樹的創(chuàng)px FCBD^^FCBD^^^E^^^G^G^^H^bitree*Create(elemtypex,bitree*lbt,bitree{bitree*p;returnNULL;return}二叉樹的ADADBparentEFGxHBACxEFDHGACBACB^^E^^Fp^E^^Fx^H^ACFB^ ACFB^xx^E^^^D^D^^H^二叉二叉 算bitree*InsertL(elemtypex,bitree{bitree*p;returnreturnNULL;xx

if(parent->Lchild==NULL)}刪除二叉樹bt中結(jié)點parentABABCDFGHABCEFHFFApABB^C^E^E^^^H^bitree (bitree*bt,bitree{bitreeif(parent==NULL||parent->Lchild==NULLprintf(“return}

p=parent->Lchild;

return }二叉排序樹的生生成一棵二叉排序樹,過程如下①若二叉排序樹為空，則令待插結(jié)點為根結(jié)點②若二叉排序樹非空，則比較待插結(jié)點(k)和根結(jié)點(k)的數(shù)據(jù)值。若1<k0,則將其到左中；否則，將其到右 中.③結(jié)點二叉排序樹的左、右過程同上2828二叉排序樹生成算法步驟（非遞歸{k0,k1,k2,…,kn-K0 ；若有ki>=kj且結(jié)點 二叉排序樹生成算法描#defineNbitree*creat_bstree(elemtype{intbitree*bt,*s,*p,*q;forif(bt==NULL){p=bt;{

if(s->data<p->data)ifif(s->data<q-q-return}}}二叉樹的遍一、二叉樹的遍二叉樹的遍歷是指按照某種順序二叉樹中的每個結(jié)點，使每個結(jié)點被一次且只被訪組成單元是：根結(jié)點D、左L和右R根}{}根}{}Postorder（后序{中序遍中序遍若二叉樹為空，則空操作 根結(jié)點；（2）前序遍歷左 A

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– P-> voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– P-> voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–P->P->BCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–AP->AP->CDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–AA CDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–AABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–}

C voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)if(p–>Rchild!=NULL)}D

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– NULLvoidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– P-> 中序遍歷若二叉樹為空，則空操作（1）中序遍歷左；（2）根結(jié)點（3）中序遍歷 C

voidinorder(treenode{if(bt==NULL)if(bt->lchild!=NULL)inorder(bt-printf(“%d”,bt-if(bt->rchild!=NULL)inorder(bt-}后序遍歷若二叉樹為空，則空操作 ；（2）后序遍歷右 根結(jié)點

后序遍歷算法voidpostorder(treenode{if(bt==NULL)if(bt->lchild!=NULL)postorder(bt->lchild);if(bt->rchild!=NULL)postorder(bt->rchild);printf(“%d”,bt->data);}的順序逐點。 AC

A

ABCGHIDJEKF前序：ABCDEFGHIJK中序：BDEFCAHGJKI后序：FEDCBHKJIGA層序：ABABCGHIDJEKF樹

遍歷（前序、中序、后序、層序前序遍歷算法執(zhí)行過程AAvoidPreorder(bitree{if(p==NULL)if(p–>Lchild!=NULL)if(p–>Rchild!=NULL)}^B^B^^C^A→B1100-1100- →C1200-1200-END 中序遍 后序遍voidInorder(treenode{if(bt==NULL)return;printf(“%d”,bt->data);}

voidPostorder(treenode{if(bt==NULL)return;printf(“%d”,bt-}{a1，…，am}和{b1，…若中序序列中與后序序列am相同的元素為bjA.j=1時，二叉樹無 ，由{a1，…，am-1}{b2，…，bm}可以唯一的確定二叉樹的 B.j=m時，二叉樹無 ，由{a1，…，am-1}{b1，…，bm-1}可以唯一的確定二叉樹的 若am{a1，a2…，ajaj+1 后個數(shù)相{b1，，bj-1，bj，bj+1，，bm 中唯一的確定 唯一的確定例1：后序序列{HDFBKGCEAHBDFAEKCG{HDFBKGCEA {HBDFAEKCGAA

E

CA

E {a1，…，am}和{b1，…若中序序列中與前序序列a若中序序列中與前序序列a1相同的元素為bjj=1時，二叉樹無 ，由{a2，…，am}{b2，…，bm}可以唯一的確定二叉樹的 j=m時，二叉樹無 ，由{a2，…，am}{b1，…，bm-1}可以唯一的確定二叉樹的 2<=j<=m-1，則子序列{a2，…，aj}和{b1，，bj-1}唯一的確定二叉樹的 ；子序列…，am}和{bj+1，…，bm各左、 進(jìn)行如上操作若a1{a1，a2…，ajaj+1 前{b1，…，{b1，…，bj-，bj+1，，bm 中唯一的確定 唯一的確定例例2：前序序列ABHFDECKGHBDFAEKCG前序序列：1，2，3，4，5，6，7，8，9中序序列中序遍歷的結(jié)果后序遍歷的結(jié)果該二叉樹并寫該二叉樹并寫遍歷結(jié)5.5樹、森林與二叉樹的轉(zhuǎn)對樹中不是雙親結(jié)點 個 保留新添加的

子結(jié)點連線位于左孩子指針位置，使

A 連 抹

整理CE FGABABCDEFGHABDCEGFH 連請做練習(xí)將如圖所示的森林轉(zhuǎn)換成二叉樹ABCDABCDEFGHIJKABCGHIDJEKF

刪除原二叉樹中所有雙親結(jié)點 連線點位于相同層次高度。ABABCDEFG DFGABABDCEGFHABCDEFGHABABCDEFGABCDEFG ABABCDEFGABCDEFG ABCDEFG ABCDEFG練習(xí)請給出該樹的先根、后根和層序遍歷結(jié)ABCDEFGH先根：ABECFABCDEFGHEBFCGHD層序：ABCDEFG作業(yè)p1957-4，7-10，7-11，補(bǔ)充題1、樹:(最優(yōu)二叉樹是一種帶權(quán)路徑最短的于信息檢索、判定樹、編碼等。樹（Huffman樹（HuffmanTree路徑長度：結(jié)點的帶權(quán)路徑長度。WPL。WPLwinWPL=7*3+9*3+5*2+6*2+2*=WPL=2*1+6*3+7*4+9*4+5*=WPL=6*2+7*2+5*3+2*3+=WPL=2*1+5*3+7*3+9*3+=WPL的二叉樹，其中具有最小WPL的二叉樹稱為樹（或最優(yōu)棵樹。每棵樹只有一根結(jié)點。將這些樹

編另一個字符的編碼的前綴，這種編碼稱為前綴編碼CASTCASTSATATA字符集合是{C,A,S,TW＝2,7,4,5A: T: C: S:2+7+4+5*22/18,7/18,4/18,5/18為{2,7,4,5}。2,7,45夫曼樹。左分支賦0，右分支賦1，得A: T: C: S:7*1+5*2+(2+4)*3= 5.7.2二叉排序樹的生二叉排序樹生成算法步驟（非遞歸{k0,k1,k2,…,kn- ；若有ki>=kj且結(jié)點 二叉排序樹生成算法描#defineNbitree*creat_bstree(elemtype{intbitree*bt,*s,*p,*q;forif(bt==NULL){p=bt;{

if(s->data<p->data)ifif(s->data<q-q-return}}}

先序遍 后序遍

結(jié) 遍樹

2 結(jié)

鏈?zhǔn)浇Y(jié)森 二叉

先序遍樹樹

中序遍層序遍編 bitree*findnode(bitree*bt,elemtype{bitreeif(bt==NULL)returnNULL;if(bt->data==x)returnbt;if(bt->Lchild!=NULL){p=findnode(bt-if(p!=NULL)returnp; if(bt->Rchild!=NULL){p=findnode(bt->Rchild,x);if(p!=NULL)return returnNULL;

空查找不成typedefstruct{ structnodebnode*b；/*指向根結(jié)點的指針intcounter=0；/*記結(jié)點個數(shù)，全局變量voidcountleaf(bnode/*counter{if(b==NULL)if(b->L==NULL&&b->R=counter=elseprintf(“%d”,b->data);}typedefstruct{ structnodebnode*b；/*指向根結(jié)點的指針intcounter=0；/*記結(jié)點個數(shù)，全局變量voidbitree(bnode{if{if((b->L!=NULL)&&(b- }}}typedefintelemtype;typedefstructbtreenode{elemtypestructbtreenode*Lchild；structbtreenode*Rchild;}intcount=0*計數(shù)變量，全局變量作業(yè)p195 性質(zhì)性質(zhì)1若二叉樹的層次從0開始i2i個結(jié)點。(i性質(zhì)性質(zhì)2若規(guī)定空樹的深度為-1，則深度為k2k+1-1個結(jié)點。(k-性質(zhì)3對任何一棵二叉樹n0,度為2n2,性質(zhì)性質(zhì)4具有nlog2（n+1)- (“”表示上取整性質(zhì)5如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié) 0,1,…,n-1，然后按此結(jié)將樹中各結(jié)點順序地存放于一個一維數(shù)組中0i若i0,i若i0,i的雙親為(i若2*i+1ni的左孩子為2*i+1；否則(2*i+1>沒有左孩子，必定是葉子結(jié)若2*i+2<n,則i的右孩子為2*i+2；否則，i#defineMAXNODE typedefintelemtype;elemtypebt[MAXNODE];typedefin typedefstructnode{elemtypedata;structnode*Lchild；structnode*Rchild;}二叉樹的ADADBparentEFGxHBACxEFDHG二叉二叉 算bitree*InsertL(elemtypex,bitree{bitree*p;returnreturnNULL;xx

if(parent->Lchild==NULL)returnp;}刪除二叉樹bt中結(jié)點parentABABCDFGHABCEFHbitree (bitree*bt,bitree{bitreeif(parent==NULL||parent->Lchild==NULLprintf(“return}

p=parent->Lchild;

return }前（先）序遍歷若二叉樹為空，則空操作 根結(jié)點；（2）前序遍歷左 ABCDEFGHABCDEFGH ABCDEFGHABCDEFGHvoidpreorder(bitree{if(bt==NULL)printf(“%d”,bt-if(bt->Lchild!=NULL)preorder(bt->Lchild);if(bt->Rchild!=NULL)preorder(bt->Rchild);}中序遍歷若二叉樹為空，則空操作（1）中序遍歷左；（2）根結(jié)點（3）中序遍歷 C

voidinorder(bitree{if(bt==NULL)if(bt->Lchild!=NULL)inorder(bt-printf(“%d”,bt-if(bt->Rchild!=NULL)inorder(bt-}后序遍歷若二叉樹為空，則空操作后序遍歷 ；（2）后序遍歷右 根結(jié)點

后序遍歷算法voidpostorder(bitree{if(bt==NULL)if(bt->Lchild!=NULL)postorder(bt->Lchild);if(bt->Rchild!=NULL)postorder(bt->Rchild);printf(“%d”,bt->data);}

整 連 抹

C B

A D GWPLWPLwinCASTCASTSATATAC,A,S,TW＝2,7,4,52,7,45樹。左分支賦0，右分支賦1，得 A:T:C:S:二叉排序樹的生③結(jié)點二叉排序樹的左、右過程同上2828二叉排序樹生成算法描#defineNbitree*creat_bstree(elemtype{intbitree*bt,*s,*p,*q;forif(bt==NULL){p=bt;{

if(s->data<p->data)ifif(s->data<q-q-return}}}第六 Chapter 圖的基本概圖的結(jié)圖的遍圖的定義圖是由一個非空的頂點集合和一描述頂點之間關(guān)系——邊（或者?。┑?/p>