福建專升本數(shù)據(jù)結(jié)構(gòu)講解

一、會：基本概念，基本思想二、懂：思想證明三、寫：C代碼第一章引論一、算法：若干指令組成的有限序列。五個特征：輸入、輸出、確定性、有限性、可行性。二、數(shù)據(jù)結(jié)構(gòu)=邏輯結(jié)構(gòu)，物理結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu)(頂層)：三種，線性、層次(樹)、圖邏輯結(jié)構(gòu)是：成分?jǐn)?shù)據(jù)+成分?jǐn)?shù)據(jù)之間關(guān)系數(shù)據(jù)元素(成分?jǐn)?shù)據(jù))：一個同學(xué)檔案數(shù)據(jù)項：姓名、生日、學(xué)號 數(shù)據(jù)物理結(jié)構(gòu)(底層，存儲結(jié)構(gòu))：兩種，順序(數(shù)組)、非順序(鏈表)同一個邏輯結(jié)構(gòu)可以在不同的物理結(jié)構(gòu)中實現(xiàn)，但是各種操作算法的具體實現(xiàn)代碼不同(比如在數(shù)組插入，在鏈表中插入算法不同)涉及題目：05年二(1,3)三、 復(fù)雜度=占用資源的多少，時間、空間O(...)，表示數(shù)量級O(1)<O(log2n)<O(n)<O(n*logn)〈0(n"k)〈0(2"n)1、時間復(fù)雜度相對時間，一條指令(語句)運行時間為1計算：非遞歸=主要循環(huán)(最費時)執(zhí)行的次數(shù)遞歸=結(jié)果中的常數(shù)(0)和系數(shù)(1)，低階全部去掉(0)3n+7+0.5*n*n=0(n*n)復(fù)雜度類型：最好、最壞、平均2、空間復(fù)雜度：輔助數(shù)據(jù)空間,如果沒有,則是0(1)涉及題目：08年2,3,9,1207年15四、 結(jié)構(gòu)類型、變量、指針(抽象數(shù)據(jù)類型不會考)：1、什么是類型？類型是模板，用于定義變量intdoublefloatchar...如果不定義變量，類型沒用intx;x占2字節(jié)doubley;y占8字節(jié)說法：int占2字節(jié)，double占8字節(jié)實際上x,y占字節(jié)二居室模板圖紙規(guī)劃類型intdouble主臥20平方小臥10平方客廳20平方廚房10廁所4陽臺4總計68平方房子蓋好 intx;張三家是二居室 x是整型變量類型：名字，大小，不占內(nèi)存變量：名字，大小，占內(nèi)存C語言允許程序員自己定義類型？因為C語言原來的類型太少！比如要存儲處理學(xué)生檔案數(shù)據(jù)學(xué)號：整數(shù)姓名：字符串8個字符性別：字符,M,F地址：字符串40個字符分?jǐn)?shù)：浮點數(shù)組[30]定義結(jié)構(gòu)類型intnum;charname[8];charsex;charaddr[40];floatscore;typedefstructstudent{intnum;2成員charname[8];8charsex;1charaddr[40];40floatscore;4}STUDENT;定義一個結(jié)構(gòu)類型！名字sturctstudent或者STUDENT,大小55字節(jié)定義結(jié)構(gòu)變量structstudentstudent1,student2，stu[100],*p;或者STUDENTstudent1,student2，stu[100],*p;p自己占4個字節(jié)，管65字節(jié)p里只存一個地址，;intx,y;x=8;注意：類型名不能用作變量名以下代碼大錯?。canf("%d，%s，%c，%s,%f",&student1)；printf("%d，%s，%c，%s,%f",student1)；引用結(jié)構(gòu)體變量中成員的方式為結(jié)構(gòu)體變量名.成員名student1.num=101;[0]='T';[1]='o';[2]='m';[3]='\0';student1.sex='M';student1.score=80.5;張三家.廚房李四家.廚房student2.score=student1.score;sum=student1.score+student2.score;student1.age++;++student2.age;scanf("%d，%s，%c，%s,%f",&student1.num,&,&student1.sex,&student1.addr,&student1.score)；printf("%d，%s，%c，%s,%f",student1.num,,student1.sex,student1.addr,student1.score)；stu[0].num=103;數(shù)組名[下標(biāo)].成員名三個問題：結(jié)構(gòu)類型定義，結(jié)構(gòu)變量定義，結(jié)構(gòu)變量引用簡單寫法1：結(jié)構(gòu)類型定義和結(jié)構(gòu)變量定義寫在一起structstudent{ intnum；charname[20]；charsex；intage；floatscore；charaddr[30]；}studentl,student2；簡單寫法2：結(jié)構(gòu)類型定義和結(jié)構(gòu)變量定義寫在一起省略類型名字struct{ intnum；charname[20]；charsex；intage；floatscore；charaddr[30]；}studentl,student2；保留字：不能用作變量名,數(shù)組名，函數(shù)名指向結(jié)構(gòu)體類型數(shù)據(jù)的指針structstudent*p;或者STUDENT*p;p自己占4個字節(jié)，管65字節(jié)p里只存一個地址，;

p=&student1;把student1的第一個字節(jié)的地址存到p中。能不能通過p來訪問student1的成員？可以。方式1:p->num就是student1.nump->name就是p->name0]就是0]p->name1]就是1]p->birthday.month就是student1.birthday.month方式2:不常用(*p).num就是student1.num(*p).name就是p++加65*(p+2).num等價(p+2)->num(p++)->num(++p)->num(p++)->num(++p)->num*(p++).num類型定義：typedef例子：typedefstructx*YYY;//*表示指針變量類型，類型名是YYY,x表示YYY是指向x模板的類型typedefstructx{inta;intb;charc;}ListItem;voidmain(){ListItemy;y.a=6;//y家a房間住6YYYp;p=&y;//y家地址保存在p中p->a=7;}五、指針6、 typedefstructx*YYY;//*表示指針變量類型，類型名是YYY,x表示YYY是指向x模板的類型typedefstructx{inta;intb;charc;}ListItem;voidmain(){ListItemy;//y是結(jié)構(gòu)變量，//y是a,b,c變量的總名字，y.a=6;//一旦有了y,則a,b,c不能//單獨被訪問，y.b=7;//必須在y.之后被訪問y.c='a';//一旦分了房子，不能單獨說//廚房漏水，要說張三家廚房漏水YYYp;//p是另外一個變量，而且//是另外一個類型p=&y;//p與y不是一個變量，也不//是一個類型，p中存放y首字節(jié)地址。//p管理y的所有字節(jié)p->a=7;//可以通過p來訪問y的a,b,cp->b=6;//因為p是指向y類型的指//針，p-〉b會自動跳過a所//占的字節(jié)(不止一個字節(jié))，//取得b所占的字節(jié)(不止一個),//這就是指針類型的必要性。p-〉c='b';}p++相當(dāng)于p加上sizeof(y),即y變量占用的字節(jié)數(shù)第二章線性表線性表概念：p18同一類型元素的有限序列，a1,a2,...an前驅(qū)，后繼，長度，空表一、順序表(線性表存在數(shù)組中)假定數(shù)組是inta[n];1、 順序表查詢：給定一個關(guān)鍵字，在數(shù)組中順序比較for(i=0;i<n;i++)if(key==a[i])break;查詢最好復(fù)雜度：0(1),第一個a[0]就是查詢最壞復(fù)雜度：0(n),最后一個a[n-1]才是查詢每個元素需要比較次數(shù)之和查詢平均復(fù)雜度= 元素個數(shù)1+2+3+...+nn*(n+1)2 n+1 = =0.5n+0.5=0(n)n 2查詢平均復(fù)雜度=(每個元素查詢次數(shù)*該元素查詢概率)之和=第1個元素的查詢次數(shù)*該元素查詢概率+第2個元素的查詢次數(shù)*該元素查詢概率+...++第n個元素的查詢次數(shù)*該元素查詢概率111=1*---+2* +...+n* =0(n)

假設(shè)每個元素的查詢概率相同，1/n2、 順序表插入元素：插入元素key到a[i]for(j=n-1;j>=i;j--)a[j+1]=a[j];//從后向前移動元素a[i]=key;插入最好復(fù)雜度：0(1),插在最后元素a[n-1]之后插入最壞復(fù)雜度：0(n),插在第一個元素a[0]之前插入每個元素移動次數(shù)之和插入平均復(fù)雜度= 元素個數(shù)0+1+2+3+...+nn+1n*(n+1)/2 n= = =0.5n=0(n)n+1 2=(每個位置被插入的移動次數(shù)*該位置被插入的概率)之和=第1個位置被插入的移動次數(shù)*該位置插入概率+第2個位置被插入的移動次數(shù)*該位置插入概率+...++第n+1個位置被插入的移動次數(shù)*該位置插入概率TOC\o"1-5"\h\z1 11=n* +(n-1)* +...+0* =0(n)n+1 n+1 n+1假設(shè)每個位置被插入的概率相同，1/(n+1)插入在位置k之后k=0,1,2,...,nk=0，插入在位置1 table[0_k=1，插入在位置2 table[1_k=2，插入在位置3 table[2_k=n，插入在位置n+1 table[n]因此table[k]=x是正確的3、 順序表刪除元素：刪除元素a[i]for(j=i;j<n;j++)a[j]=a[j+1];//從前向后移動元素刪除最好復(fù)雜度：0(1),刪除最后一個a[n-1]刪除最壞復(fù)雜度：0(n),刪除第一個a[0]刪除平均復(fù)雜度= 刪除平均復(fù)雜度= =0(n)元素個數(shù)0+1+...+(n-1) n*(n-1)/2 n-1= = = =0(n)n n 2注意：平均！=最壞涉及題目：08年1307年4,11,22,2806年一(5)05年一(2)，二(7)，四(2)二、鏈表1、 鏈表類型：單鏈表，循環(huán)單鏈表雙鏈表，循環(huán)雙鏈表頭指針:一定要有不是循環(huán)鏈表，一定要有頭指針是循環(huán)鏈表，頭指針/尾指針：要有一個。頭結(jié)點：可有（簡單）可無（麻煩），是否有頭結(jié)點影響到算法的具體實現(xiàn)2、類型定義代碼typedefstructnode*link;//指針類型定義typedefstructnode{//鏈表實現(xiàn)ListItemelement;linknext;}Node;//鏈表結(jié)點類型定義Ielement|nextlinkfirst;//頭指針first!1 m1 m1 1""111II-III*1II…-I?1 1—11 i—ii i—i13、 創(chuàng)建鏈表，略去malloc(n):在內(nèi)存中分配一片連續(xù)空間，長度是n個字節(jié)將首字節(jié)地址返回。4、 遍歷鏈表intListLength(linkL){intlen=0;linkp;p=L;while(p!=NULL){len++;p=p->next;}returnlen;}調(diào)用length=ListLength(first);遍歷程序?qū)懛ǎ簂inkp;p=first;while(p!=NULL){

p=p->next;5、鏈表插入p26,假定將新節(jié)點X插入到節(jié)點i之后。新節(jié)點最用情它的指針用表它的指針p來表示。指針調(diào)整代碼是：q->next=p->next;p->next=q;插入前pIriI]I mIIIi i—irxI]f插入后pmIII—I5.2、如果節(jié)點i需要通過掃描得到，假定位置是第i個節(jié)點(從1開始)需要鏈表遍歷intk;linkp;p=first;k=1;while(p!=0&&k<i){p=p->next;i++;}5.3如果需要建立存儲待插入元素x的新結(jié)點linkq;q=(link)malloc(sizeof(Node));q->element=x;5.4插入在鏈表最開頭。q->next=first;first=q;5.5空表插入。(創(chuàng)建鏈表)if(first==NULL){first=q;q->next=NULL;}6、 節(jié)點刪除將節(jié)點i刪除,p是指向i節(jié)點指針變量6.1、最簡單情況：q是指向i的前驅(qū)節(jié)點指針變量指針調(diào)整代碼是：q->next=p->next;free(p);或者q->next=q->next->next刪除前qTOC\o"1-5"\h\zI I~I I I~I I~I II 一 li I— i+1 II LJ I LJ LJf刪除后IriIri mIIIi i—ii m rI i II -i+1 II LJ Lf(回收)6.2、 i是鏈表最開頭的節(jié)點。first=first->next;6.3、 如果節(jié)點i需要通過掃描得到，假定位置是第i個節(jié)點(從1開始)找到指向第i-1個結(jié)點的指針qq=first;for(k=1;k<i-1&&q!=NULL;i++)q=q->next;涉及題目：08年6,2507年5,19,2006年一(1,6)，二(18,19)05年一(1,12)，第三章堆棧Stack堆棧是特殊的線性表，只能在堆棧頂插入刪除元素一、用鏈表實現(xiàn)，進(jìn)出棧時插入刪除結(jié)點，不存在取之不盡的問題，注意盡量地減少進(jìn)出棧的時間復(fù)雜度，棧頂設(shè)在鏈表開頭。二、用數(shù)組data實現(xiàn)，長度為n，存在取之不盡的問題因此設(shè)置棧頂指針。棧頂指針top：int,存儲棧頂元素的下標(biāo)指向非空位置，除非棧為空。如果空棧，top=-l如果滿棧，top=n-1進(jìn)棧：將元素x進(jìn)棧如果棧滿，無法進(jìn)棧否則：data[++top]=x先調(diào)整top，然后放置元素x出棧：將棧頂出棧，放置在x中如果?？?，無法出棧否則：x=data[top--]先取走元素，存入x再調(diào)整topdata數(shù)組涉及題目：08年107年2,306年一(9)05年一(4)，三(4)第四章隊列Queue隊列是特殊的線性表，只能在隊尾插入元素，在隊頭刪除元素一、 用鏈表實現(xiàn)，進(jìn)出隊時插入刪除結(jié)點，注意盡量減少進(jìn)出隊的時間復(fù)雜度0(1),設(shè)置兩個指針，隊頭指針和隊尾指針，二、 用數(shù)組實現(xiàn)，長度為n,循環(huán)隊列(充分利用數(shù)組空間)循環(huán)隊列方案11、 maxsize=n,數(shù)組長度是n2、 隊頭指針front(整型，存數(shù)組下標(biāo))，指向空位置，無論隊是否為空3、 隊尾指針rear(整型，存數(shù)組下標(biāo))，指向非空位置，除非隊空4、 隊空：rear==front,初始化front=rear=0,0個元素。5、 隊滿：(rear+1)%n==front,犧牲一個單元，隊滿只儲存n-1個元素(為了區(qū)分隊空和隊滿)6、進(jìn)隊：隊是否滿？滿則不進(jìn)，否則rear=(rear+1)%n,放新元素在rear位置(先調(diào)整指針，后處理元素)7、出隊：隊是否空？空則不出，否則front=(front+1)%n,取front位置元素(先調(diào)整指針，后處理元素)f012345n=6cdeabr循環(huán)隊列方案2:帶'的與方案1相反1、maxsize二n,數(shù)組長度是n2'、隊頭整型指針front,指向非空位置，除非隊空3'、隊尾整型指針rear，指向空位置4、 隊空：rear==front,初始化f=r=05、 隊滿：(rear+1)%n==front,犧牲一個單元6'、進(jìn)隊：放新元素在rear位置rear=(rear+1)%n,7'、出隊：取front位置元素front=(front+1)%n,f012345 n=6Ar涉及題目：08年7,1606年一(10,20)05年一(3,5)，二(2)第五章遞歸寫遞歸程序：有時很容易(數(shù)學(xué)公式存在)。有時很難(沒有現(xiàn)成數(shù)學(xué)公式)運行原理：堆棧，編程時看不見。遞歸程序一定可以寫成非遞歸。對應(yīng)的非遞歸一般使用堆棧。遞歸變成非遞歸有時候很難，對問題的理解不夠。比如Ackerman函數(shù)，寫成遞歸很容易，變成非遞歸很難。遞歸算法復(fù)雜度分析有時候很難(生成函數(shù))。同樣一個問題有時候用遞歸很容易解決，用非遞歸不容易解決同樣一個問題有時候用非遞歸很容易解決，用遞歸不容易解決同樣一個問題有時候用非遞歸，用遞歸都不容易解決如果沒有數(shù)學(xué)公式，簡單遞歸程序?qū)懛?、寫出遞歸函數(shù)的定義:函數(shù)名，參數(shù)，結(jié)果（返回值類型和意義）、處理邊界情況、按照遞歸函數(shù)的定義（利用低一級結(jié)果，得到本級的結(jié)果）自己調(diào)用自己,自圓其說寫非遞歸寫遞歸|-1(無定義),n<0n!=n*...*2*1=|-1,0<=n<=1|-n*(n-1)!,n>1//非遞歸：0(n)intf(intn){//f(n)計算n!inti,j;if(n<=1)return1;j=1;for(i=1;i<=n;i++)j=j*i;returnj;}//遞歸intF(intn){//寫出函數(shù)定義：F(n)算出n!if(n<=1)return1;//處理邊界情況returnn*F(n-1); //自己調(diào)用自己，}//同時滿足結(jié)果voidmain(){intx,y;x=F(5);y=f(5);printf("%d%d",x,y);}設(shè)F(n)的時間復(fù)雜度是T(n)則F(n-1)的時間復(fù)雜度是T(n-l)T(1)=1T(n)=1+T(n-1)T(n-1)=1+T(n-2)T(n)=1+T(n-1)=1+1+T(n-2)=2+T(n-2)=3+T(n-3)=1+1+...+T(1)=n-1+T(1)=1+1+...+1=n=O(n)T(n)=k+T(n-1)=k+k+T(n-2)=2k+T(n-2)=3k+T(n-3)=nk=O(n)Ackerman(n,m)函數(shù)A(1,0)=2, n=1,m=0A(0,m)=1 n=0,m>=0A(n,0)=n+2 n>=2,m=0A(n,m)=A(A(n-1,m),m-1)n,m>=1intA(intn,intm){if(n==1&&m==0)return2;if(n==0&&m>=0)return1;if(n>=2&&m==0)returnn+2;if(n>=1&&m>=1)returnA(A(n-1,m),m-1);}voidmain(){intx;x=A(9,4);printf("%d",x);}假定A(n,m)的時間復(fù)雜度T(n,m)T(n,m)=1+T(A(n-1,m),m-1)+T(n-1,m)斐氏數(shù)列1123581321345589 TOC\o"1-5"\h\z|-1 n=0F(n)=|-1 n=1|-F(n-1)+F(n-2) n>1//遞歸:F(n)算出F(n),//時間復(fù)雜度是T(n)intF(intn){if(n<=1)return1;returnF(n-1)+F(n-2);}T(n)=1+T(n-1)+T(n-2)=1+1+T(n-2)+T(n-3)+1+T(n-3)+T(n-4)生成函數(shù)來算。//非遞歸:H(n)算出F(n),O(n)intH(intn){inti,x,y,z;if(n<=1)return1;x=1;y=1;for(i=2;i<=n;i++){z=x+y;x=y;y=z;}}main(){intx,yx=F(13000);y=H(4);printf("%d%d",x,y);}涉及題目：08年2507年2706年四(25)05年四(1)第六章排序線性序：數(shù)字＜，字符串字典序，姓氏筆畫整數(shù)數(shù)字排序，從小到大排序，數(shù)字放在數(shù)組里頭穩(wěn)定：對于key相同者ai和aj,如果原來ai在aj之前，排序后，保證ai還在aj之前,則稱為穩(wěn)定,否則叫做不穩(wěn)定（不保證ai還在aj之前）。（!=保證ai不在aj之前）。最好最壞 平均 穩(wěn)定插入：O(n)O(n*n)O(n*n)Yes折半插入：O(n*logn)O(n*logn)O(n*logn)Yes選擇：O(n*n)O(n*n)O(n*n)Yes歸并：O(n+m)O(n+m)O(n+m)Yes歸并：O(nlogn)O(nlogn)O(nlogn)Yes快速：O(n*logn)O(n*n)O(n*logn)NO堆： O(n*logn)O(n*logn)O(n*logn)NO一、冒泡：BubbleSort0、執(zhí)行多遍每一遍：1、指定一個方向：從前到后(大數(shù)下沉)，或從后到前(小數(shù)上升)均可但是只能選擇一個方向。2、相鄰數(shù)據(jù)比較3、次序不對就交換選定：從前到后,263754第一遍：236754236754236574236547第2遍：236547235647235467第3遍：235467234|57第4遍：234|5671234564、每遍之后，數(shù)組變短1、一旦沒有交換就不要下一遍(停止)。否則進(jìn)行下一遍123456n-1遍n-1次比較n-2次比較n-3次比較n-4次比較第一遍：n-1次比較3654|7一遍后最大的數(shù)字在最后第二遍：n-2次比較35467兩遍后次大的數(shù)字在次后第三遍：n-3次234|567三遍后第三大的數(shù)字在第三后第四遍：沒有交換234|567不需要第五遍最后一遍,n-l遍 1次最好時間復(fù)雜度=0(n),只有一遍最壞時間復(fù)雜度，n-1遍=n-1+n-2+n-3+...+2+1=n*(n-1)/2=O(n*n)平均時間復(fù)雜度=0(n*n)(n-1

+n-1+n-2+n-1+n-2+n-3+ +n-1+n-2+...+1)/n=O(n*n)最壞：最多n-1遍第1遍：n-1次比較第2遍：n-2次比較+第n-1遍：1次比較n*(n-1) =O(n*n)2最好：1遍O（n）第1遍：n-1次比較代碼：voidbubble(inta[],intn){inti,j;for(i=1;i<=n;i++)for(j=i;j>0;j--)比較交換(aj-1],aj]);}運行情況如下：i=1;j=1 比較交換(a[0],a[1]);i=2j=2 比較交換(a[1],a[2]);j=1 比較交換(a[o],a[1]);i=3j=3 比較交換(a[2],a[3]);j=2 比較交換(a[1],a[2]);j=1 比較交換(a[o],a[1]);i=4j=4j=3j=2j=1比較父換（a3],a4])比較父換（a2],a3])比較父換（a1],a2])比較父換（a0],a1])二、插入排序：直接插入1、插入方向：2種，一般選擇從后向前2、利用原來的數(shù)組，排好序的部分放在數(shù)組前面。最開始的時候，只有第一個元素是排好序的。3、移動數(shù)據(jù)可以逐個（臨時單元記憶待查入元素，書本上用）也可以成批。4、復(fù)雜度：n-1遍最壞最好TOC\o"1-5"\h\z第1遍： 1次 1第2遍： 2 次 1第3遍： 3 次 1+第n-1遍：n-1次1最好O(n*n)O(n)最好選定：從后向前最壞33.545|6v=3.5

963第一遍：9|6369|3第2963第一遍：9|6369|3第2遍：69|3369第3遍：367第4遍：367345tmp=4444444555555495||7961次比較1次比較1次比較1次比較1次比較1次比較1次比較1次比較2|63754A-/r- 、0第二遍：23|6754v=3AA- 、0第三遍：236|754v=7第四遍：2356|74v=5弟i遍：/*第一遍是第二遍是第三遍是a[0],a[第i遍是將a[i]插入到a[0],...,a[i-1]1次比較1次比較2次比較11次比較1次比較2次比較1次比較3次比較1次比較4次比較1次比較i次比較1次比較將a[1]插入到a[0]將a[2]插入到a[0],a[1]將a[3]插入到1],a[2]a[0],...,a[n-2]insert(a,i):將a[i]插入到a[O],...,a[i-l]中*/代碼：voidinsertion(inta[],intn){inti;for(i=1;i<n;i++)insert(a,i);//n-1遍}voidinsert(inta[],inti){//將a[i]插入到a[O],...,a[i-l]中intv=a[i];while(i>0&&v<a[i-1]){a[i]=a[i-1];i--;//從后向前}a[i]=v;}插入方法：直接插入，三、折半插入:從中間向兩邊走O(n*logn)a0,a1,...ai,|ai+1hl012345678910112345678910111213|4.5m=(l+h)/2=(0+11)/2=5h=m-1m=(0+4)/2=2l=m+1m=(3+4)/2=3h=m-1=24.5在5前面n-1遍,比較次數(shù)第1遍log1第2遍log2第3遍log3第4遍log4?、0-1?第i遍logi第n-1遍logn-1log1+log2+log3+..+log(n-1)=log(n-1)!<=O(n*logn)四、選擇排序：O(n*n)1、 選擇最小關(guān)鍵字者，放在原來數(shù)組里頭，與a[0]交換2、 選擇次小關(guān)鍵字者放在原來數(shù)組里頭，與a[1]交換共選n-1次，第1次從n個里面選，a[0]到a[n-1]n-1第2次從n-1個里面選，a[1]到a[n-1]n-2第3次從n-2個里面選，a[2]到a[n-1]第i次從n-i+1個里面選，a[i-1]到a[n-1]第n-1次從2個里面選，a[n-2]到a[n-1]如何選擇最小者？記錄當(dāng)前最小元素的下標(biāo)代碼：intmini(inta[],inti,intn){//從a[i]到a[n-1]中選出最小元素下標(biāo)intj,min=i;//min是到現(xiàn)在為止最小元素的下標(biāo)for(j=i+1;j<n;j++)if(a[j]<a[min])min=j;returnmin;}voidselection(inta[],intn){inti;for(i=0;i<n-1;i++){//n-1遍j=mini(a,i,n);//從a[i]到a[n-1]中選出最小者a[j]交換a[i]和a[j];}}n-1+n-2+...+2+1=O(n*n)五、快速排序:最好平均O(n*logn)最壞O(n*n)不穩(wěn)定l ra[l] a[r]

v=a[r]另外開2個數(shù)組（浪費空間）b放比v小的c放比v大的在同一個數(shù)組內(nèi)劃分，增加難度v=a[r]基準(zhǔn)元素最后放在a[i]處[l i-1]<i<[i+1...r]第一部分第二部分第三部分挑選基準(zhǔn)元素會導(dǎo)致最好、最壞方案1:L r v=a[r]ij代碼：L r v=a[r]ij代碼：//將a[L]..a[r]分成三個部分，v=a[r]//v在中間，v左邊的比v小，v右邊的比v大//v最后所在的下標(biāo)存儲在變量i中inti=L-1;j=r;intv=a[r];for(;;){//O(n)while(a[++i]<v);while(a[--j]>v)if(j==L)break;if(i>=j)break;交換(a[i],aj]);}//兩頭夾攻，中間會師，就停止。//O(n)，i往后，j往前交換(a[i],a[r]);returni;}L rv=a[r]=41234567ij方案2:L rv=a[L]i jL rv=a[L]i j代碼：intpartition(inta[],intL,intr){//將a[L]..a[r]分成三個部分，v=a[L]//v在中間，V左邊的比V小,v右邊的比V大//v最后所在的下標(biāo)存儲在變量j中inti=L;j=r+1;intV=a[L];for(;;){//O(n)while(a[++i]<V);while(a[--j]>V)if(j==L)break;if(i>=j)break;交換(a[i],aj]);}//兩頭夾攻，中間會師，就停止。//O(n)，i往后，j往前交換(aj],a[L]);returnj;}VoidQuickSort(inta[],intL,intr){if(L>=r)return;//處理邊界情況i=partition(a,L,r);//O(n)QuickSort(a,L,i-l);//v左邊進(jìn)行排序自己調(diào)用自己QuickSort(a,i+l,r);//v右邊進(jìn)行排序}main(){inta[]={2,5,1,7,9}；QuickSort(a,0,4);}T(n):快速排序時間復(fù)雜度最好：T(n)二n+2*T(n/2)T(n/2)=n/2+2*T(n/4)T(n)=n+2*T(n/2)=n+2*(n/2+2*T(n/4))=n+n+4*T(n/4)=n+n+n+8*T(n/8)=n*logn=O(n*logn)最壞：T(n)=n+T(n-1)=n+(n-1)+T(n-2)=n+n-1+n-2+T(n-3)=O(n*n)六、堆排序：在二叉樹中講七、歸并排序內(nèi)部排序：在內(nèi)存中進(jìn)行外部排序：在內(nèi)存和外存中進(jìn)行，因為元素太多，無法一次全部裝入內(nèi)存，只好借助外存。比如歸并排序用于外部排序n個b2b3b4b5b6b7a2a3a4a5m個a1b1O（n+m）a1a2b1涉及題目：08年15,17,2007年1,806年一(2,8)，三(22)，四(26)05年三(2)，四(3)第七章樹線性表：先后樹：上下圖：沒先沒后，沒上沒下一、基本概念：度（孩子個數(shù)），葉子節(jié)點，內(nèi)部節(jié)點，樹根，高度（層數(shù)）有序樹，無序樹，二叉樹二、性質(zhì)p131定理：如果二叉樹的葉結(jié)點數(shù)為n0，則具有雙分支的結(jié)點數(shù)n2=n0-1證明：假設(shè)二叉樹結(jié)點總數(shù)為n,單分支（度為1）的結(jié)點數(shù)n1于是n=n0+n1+n2 （1）假設(shè)二叉樹邊總數(shù)為b,往上看，每條邊是一個結(jié)點的天線只有一個結(jié)點（根）沒有天線，其他結(jié)點都只有一個天線往下看，每條邊是一個結(jié)點的地線葉子無地線，單分支結(jié)點有一條地線雙分支結(jié)點有兩條地線b=0*n0+1*n1+2*n2（3）=n1+2*n2b=n-1=n0+n1+n2-1=n1+2*n2

n0+n1+n2-1=n1+2*n2

n2=n0-1[證畢]三、二叉樹節(jié)點數(shù)與高度關(guān)系1、樹的高度=人至少h個結(jié)點四世同堂：至少要四個人爺爺

|爸爸

|兒子

|孫子1、樹的高度廿最多能有 個結(jié)點?滿二叉樹的概念1A/\2BC\

G1A/\2BC\

G/\/D3當(dāng)前層2個節(jié)點總共2'2=4-1個節(jié)點當(dāng)前層4個節(jié)點總共2'3=8-1個節(jié)點當(dāng)前層2'（h-1）個節(jié)點總共21-1個節(jié)點高度=h四、完全二叉樹滿二叉樹右下角開始從右到左，從下到上，刪除一些結(jié)點。涉及題目：08年4五、父親數(shù)組表示法1/\TOC\o"1-5"\h\z2 3/\ /\5 910/|\678下標(biāo)012345678910數(shù)組a?0112255533給定i,求i的父親=a[i]給定i,打印i的兒子六、左兒子右兄弟表示法=一般樹存儲在二叉鏈表中關(guān)鍵：把一般樹轉(zhuǎn)換成二叉樹：將父親管理兒子方式改為父親管理大兒子，大兒子管理二兒子（二兒子變成大兒子的右孩子）二兒子管理三兒子（三兒子變成二兒子的右孩子）/E\FA|C/E\FA|CA/B-C-D//E-FG-H/I-JB/ED\/GB/ED\/GF\/I涉及題目：06年一（7，12），三（21）05年一（6）七、樹遍歷：對樹中每個結(jié)點訪問一次，且僅訪問一次。1、 樹（二叉樹）遍歷：前根（先根，中根（中序）后根（后序）層次：1、 樹（二叉樹）遍歷：前根（先根，中根（中序）后根（后序）層次：ABD\FB/E先序，前序）:ABEFIJDGHEBIFJAGDHEIJFBGDHAEFGHIJA\D/\GHJ2、性質(zhì)由一棵二叉樹的前序和 中序___可唯一確定這棵二叉樹的結(jié)構(gòu)。由一棵二叉樹的后序和 中序 可唯一確定這棵二叉樹的結(jié)構(gòu)。由一棵二叉樹的前序和 后序 不能唯一確定這棵二叉樹的結(jié)構(gòu)只有一個序不行有三個序肯定可以涉及題目：08年2205年三（3）、已知一棵二叉樹的中序序列BDCEAFHG后序序列DECBHGFA，請畫出該二叉樹。再求出前序。F\F\A/B\G/H\\C/A/\中序序列BDCEFHG后序序列DECBHGFA/\BF\\中序序列DCEHG后序序列DECHG中序：BDCEAFHG后序：DECBHGFA，層次：ABFCGDEH前序：ABCDEFGH八、二叉樹以二叉鏈表為存儲結(jié)構(gòu)，類型聲明如下，寫出二叉樹中遍歷遞歸算法。typedefstructnode{datatypedata； //elementstructnode*Lchild；//leftstructnode*Rchild；//right}BinaTree；[Lchild|data|Rchild]1、 前序voidPreOrder(BinaTree*t){//t是指向根的指針變量//函數(shù)定義：前序遍歷t為根的二叉樹if(t==NULL)return;//處理邊界情況訪問t指向的結(jié)點;//打印該結(jié)點的元素PreOrder(t->Lchild);PreOrder(t->Rchild);}2、 中序voidInOrder(BinaTree*t){if(t==NULL)return;InOrder(t->Lchild);訪問t指向的結(jié)點;//打印該結(jié)點的元素InOrder(t->Rchild);}3、 后序voidPostOrder(BinaTree*t){if(t==NULL)return;PostOrder(t->Lchild);PostOrder(t->Rchild);訪問t指向的結(jié)點;//打印該結(jié)點的元素}4、計算結(jié)點個數(shù)intf(BinaTree*t){//t是指向根的指針變量//函數(shù)定義：計算t為根的二叉樹結(jié)點數(shù)if(t==NULL)return0;//邊界情況：如果是空樹，結(jié)點數(shù)為0returnf(t->Lchild)+f(t->Rchild)+1;//自圓其說：左子樹結(jié)點數(shù)+右子樹結(jié)點數(shù)+根數(shù)1}5、計算葉子結(jié)點個數(shù)intg(BinaTree*t){//t是指向根的指針變量//函數(shù)定義：計算t為根的二叉樹葉子結(jié)點數(shù)if(t==NULL)return0;//邊界情況：如果是空樹，結(jié)點數(shù)為0if(t->Lchild==NULL&&t->Rchild==NULL)return1;//邊界情況：如果只有根，葉子結(jié)點數(shù)為1returng(t->Lchild)+g(t->Rchild);//自圓其說：葉子結(jié)點數(shù)=左子樹葉子結(jié)點數(shù)+右子樹結(jié)點數(shù)}6、計算高度inth(BinaTree*t){//t是指向根的指針變量//函數(shù)定義：計算t為根的二叉樹高度if(t==NULL)return0;//邊界情況：如果是空樹，高度0returnmax{h(t->Lchild),h(t->Rchild)}+1;//自圓其說：max{左子樹高度，右子樹高度}+1}7、 遍歷非遞歸算法：不要求voidPreOrder(BinaTree*t){intn=0;if(t==NULL)return;棧$=空；將t進(jìn)棧；while(S!=空){將S頂出棧，記作x；n++;if(x->Rchild!=NULL)將x->Rchild進(jìn)棧if(x->Lchild!=NULL)將x->Lchild進(jìn)棧}}S的兀素、t、x類型相同！！BinaTree*S[100];BinaTree*x;8、層次遍歷算法(不要求)//錯誤的遞歸算法voidLevelOrder(BinaTree*t){//t是指向根的指針變量//函數(shù)定義：層次遍歷t為根的二叉樹if(t==NULL)return;//處理邊界情況訪問t指向的結(jié)點;//打印該結(jié)點的兀素LevelOrder(t->Lchild);LevelOrder(t->Rchild);}正確的非遞歸算法voidLevelOrder(BinaTree*t){//t是指向根的指針變量//函數(shù)定義：層次遍歷t為根的二叉樹intn=0;if(t==NULL)return;隊列Q=空；將t進(jìn)隊；while(Q!=空){將Q隊頭出隊，記作x；n++;if(x->Lchild!=NULL)將x->Lchild進(jìn)隊if(x->Rchild!=NULL)將x->Rchild進(jìn)隊}//whileprintf("%d",n);}Q兀素，x,t類型一樣，BinaTree*.涉及題目：08年10,2507年9,10,14,17,18,24,2706年四(25),二(13)05年四(1),二(4)、三(3)、九、書本第10章p175二叉搜索樹：把關(guān)鍵字儲存在二叉樹的結(jié)點上，左子樹的關(guān)鍵字比根小，右子樹的關(guān)鍵字比根大，中序遍歷得到關(guān)鍵字的遞增序列15/\1416/\/\1314.515.518新插入的結(jié)點一定是葉子刪除結(jié)點比較麻煩涉及題目：08年1106年三(23)05年一(7)七、Huffman樹(第11章)：不唯一，編碼不唯一a000b001c010d011e100f101n個logn位000001011100101001000011100101000001010頻率高用短編碼，頻率低用長編碼縮短整篇文章的編碼長度TOC\o"1-5"\h\z100 a：0/0\1 b：100a (55) c：101(45)/0 \1 d：110/ (30) e：1110/ /0\1 f：1111(25)d(14)/0\1(16)/0\1bc ef(13)(12)(9)(5)010001010111000011110111abacf5e9a45b13c12d16/055100\1a45a：1/0\1b：01030\c：011/0\1\d：000d161425e:0011/0\1/0\1f:0010f5e9b13c12特點：沒有度為1的結(jié)點，葉子數(shù)=內(nèi)結(jié)點數(shù)+1總結(jié)點數(shù)=葉子數(shù)+內(nèi)結(jié)點數(shù)=2*葉子數(shù)-1=2*內(nèi)結(jié)點數(shù)+129=2*葉子數(shù)-1涉及題目：08年1407年1806年二(17)八、pl99堆：排序，在數(shù)組中進(jìn)行。把數(shù)組中的數(shù)字看成完全二叉樹。存儲方法按照P134圖7.15窮堆：左子樹的關(guān)鍵字和右子樹的關(guān)鍵字都比根大左子樹的關(guān)鍵字和右子樹的關(guān)鍵字大小關(guān)系無所謂對于任意結(jié)點，它比左右孩子窮-小(不用)富堆：左子樹的關(guān)鍵字和右子樹的關(guān)鍵字都比根小堆排序：O(n*logn)反復(fù)地建堆(n-1次)、取根，直到堆中只剩下一個元素為止。每次建堆，元素減少一個，平均時間O(logn)。根取走后放在原來數(shù)組的后面，交換。步驟1：建堆1、從最后一個有孩子的結(jié)點開始，從后向前建2、 讓該結(jié)點和它的孩子中最窮的當(dāng)父親3、 不合格的父親不斷一直下沉4、 堆建完后，樹根肯定最小(窮)。34681299/\(8)(6)/\/\(5)(4)(3)(2)/(1)步驟2：排序：取根1、 將根取走，放在原來數(shù)組的最后(與數(shù)組最后元素交換，原來的最后元素作為根)之后最小數(shù)不再參加排序。數(shù)組縮短2、 堆被破壞，重新建堆(將根下沉即可)。涉及題目：06年一(8)第九章符號表--Hash雜湊散列表散列表：存儲、查詢、插入、刪除元素以往查找：用比較運算實現(xiàn)。查找：知道元素的位置，最好0(1)時間查到插入：最好0(1)時間刪除：最好0(1)時間一、 開散列：用(數(shù)組+鏈表)實現(xiàn)查找一個Hash桶可以放無數(shù)元素，用一個鏈表實現(xiàn)一個hash桶二、 閉散列Hash:用數(shù)組實現(xiàn)查找1、 數(shù)組a-電影院，長度是n，Hash表2、數(shù)組元素二人 座位=Hash桶元素下標(biāo)=座位號碼3、 關(guān)鍵字：=人的名字4、 Hash函數(shù)=用名字算座位號用關(guān)鍵字算出下標(biāo)下標(biāo)i=h(x)排號：姓筆畫數(shù)，號數(shù)：名的筆畫數(shù)丁一2排1號5、 x保存在a[i]探查：保存數(shù)據(jù)前先看位置是否為空？6、 沖突：x1!=x2但是h(x1)=h(x2)不同的名字算出相同的座位號7、 解決沖突：重新散列，坐在旁邊位置8、 查找x：起點：hash函數(shù)，過程：按照重新散列函數(shù)終點：空位置8、 Hash函數(shù)例子：假定x是整數(shù)，h1(x)=x%n，9、 重新散列例子：x1!=x2i=h(x1)=h(x2),a[i]保存x1,a[(i+1)%n]存x2ii+1i+2i+3 ii+1i-1i+4i-4i+9i-9i+16i-16 10、 刪除：state狀態(tài)數(shù)組p1652排2號2排3號2排4號丁二丁丁丁十涉及題目：08年2107年2,6,2606年二(16)第13章圖線性表：先后樹：上下圖：沒先沒后，沒上沒下一、基本概念頂點，邊，有向邊：<1,2>，無向邊：(1,2)無向圖(所有的邊無向)，有向圖(所有的邊有向)，加權(quán)圖（所有的邊有權(quán)）頂點的度（入度，出度）完全圖連通圖子圖例子G=(V,E)V={1,2,3,4,5}E={(1,2),(1,3),(3,4),(3,5)}G'=(V',E')V'={3,4,5}E'={(1,3),(3,4)}涉及題目：05年18，1905年二（8）二、圖的鄰接矩陣表示法1、對于無權(quán)圖，不論有向圖還是無向圖有邊=1，無邊=0<—|一||—/|\/X1 >21一一一2///3//\3< 4451234101100101020001101013A1=0100A2=01011400101010001100主對角線=0無向圖的鄰接矩陣關(guān)于主對角線對稱，1的個數(shù)=邊數(shù)*2第i行的和=結(jié)點i的度第i列的和=結(jié)點i的度有向圖的鄰接矩陣不關(guān)于主對角線對稱1的個數(shù)=邊數(shù)第i行的和=結(jié)點i的出度第i列的和=結(jié)點i的入度2、對于有權(quán)圖，不論有向圖還是無向圖有邊=權(quán)值，無邊=無窮大，主對角線=03A B9/\C DABCDEA035OOOOB30649C5602OODOO4207EOO9OO70涉及題目：08年506年二(14)05年一(10)三、鄰接表：