傳智播客C和C++與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義

1、傳智播客C和C+丐數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)講義傳智掃地僧1、數(shù)據(jù)結(jié)構(gòu)概念1.1 數(shù)據(jù)結(jié)構(gòu)相關(guān)概念1.1.1 疑惑1、我學(xué)完了C語言，可是現(xiàn)在感覺還是寫不出代碼。2、為什么會(huì)有各種各樣的程序存在？3、程序的本質(zhì)是什么？程序是為了具體問題而存在的程序需要圍繞問題的解決進(jìn)行設(shè)計(jì)同一個(gè)問題可以有多種解決方案如何追求程序的“性價(jià)比”？是否有可量化的方法判別程序的好壞？1.1.2 數(shù)據(jù)結(jié)構(gòu)起源計(jì)算機(jī)從解決數(shù)值計(jì)算問題到解決生活中的問題現(xiàn)實(shí)生活中的問題涉及不同個(gè)體間的復(fù)雜聯(lián)系需要在計(jì)算機(jī)程序中描述生活中個(gè)體間的聯(lián)系數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算程序問題中的操作對(duì)象以及它們之間的關(guān)系不是研究復(fù)雜的算法1.1.3 數(shù)據(jù)結(jié)構(gòu)中的

2、基本概念數(shù)據(jù)-程序的操作對(duì)象，用于描述客觀事物(inta,intb,)數(shù)據(jù)的特點(diǎn)：可以輸入到計(jì)算機(jī)可以被計(jì)算機(jī)程序處理int， float ， char數(shù)據(jù)是一個(gè)抽象的概念，將其進(jìn)行分類后得到程序設(shè)計(jì)語言中的類型。如：數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位數(shù)據(jù)項(xiàng)：一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成數(shù)據(jù)對(duì)象-性質(zhì)相同的數(shù)據(jù)元素的集合(比如：數(shù)組，鏈表)友情提示，來自結(jié)構(gòu)體課堂代碼/聲明一個(gè)結(jié)構(gòu)體類型struct_MyTeacher/一種數(shù)據(jù)類型charname32;chartile32;intage;charaddr128;；intmain21()struct_MyTeachert1;/數(shù)據(jù)元素struct_M

3、yTeachertArray30;/數(shù)據(jù)對(duì)象memset(&t1,0,sizeof(tl);strcpy(,"name");數(shù)據(jù)項(xiàng)strcpy(t1.addr,"addr");/數(shù)據(jù)項(xiàng)strcpy(t1.tile,"addr");/數(shù)據(jù)項(xiàng)t1.age=1;數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系，這些關(guān)系即結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)對(duì)象中數(shù)據(jù)元素之間的關(guān)系如：數(shù)組中各個(gè)元素之間存在固定的線性關(guān)系編寫一個(gè)“好”的程序之前，必須分析待處理問題中各個(gè)對(duì)象的特性，以及對(duì)象之間的關(guān)系?；靖拍羁偨Y(jié)：78 / 731.1.4數(shù)據(jù)的邏輯

4、結(jié)構(gòu)天其它關(guān)指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。邏輯結(jié)構(gòu)可細(xì)分為4類：1.1.5 數(shù)據(jù)的物理結(jié)構(gòu)答：物理結(jié)構(gòu)亦稱.是數(shù)據(jù)的邏枳結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（或映像）口它Sni"TbJnl3.1yT*"wo存儲(chǔ)結(jié)構(gòu)可分為大類：廉序.健武去人散對(duì)電常用的存儲(chǔ)結(jié)構(gòu)為：順廳存儲(chǔ)結(jié)構(gòu)借助元麥在存儲(chǔ)器中的和對(duì)位直來表示I數(shù)據(jù)元-麓間的更輯關(guān)系O鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系數(shù)據(jù)的邏精給構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)算法設(shè)計(jì)邏輯造物茸法實(shí)現(xiàn)1.1.6 數(shù)據(jù)的運(yùn)算：什金JL-據(jù)操作或處理昔：在數(shù)據(jù)的逗輯結(jié)構(gòu)上定義的操作

5、，它最常用的數(shù)據(jù)運(yùn)算有5種：括入、刪除修改.查找,林方1.2、 算法1.2.1 算法概念算法是特定問題求解步驟的描述在計(jì)算機(jī)中表現(xiàn)為指令的有限序列算法是獨(dú)立存在的一種解決問題的方法和思想。對(duì)于算法而言，語言并不重要，重要的是思想。1.2.2 算法和數(shù)據(jù)結(jié)構(gòu)區(qū)別數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)和選擇算法=程序至據(jù)z構(gòu)+算法總結(jié)：算法是為了解決實(shí)際問題而設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體數(shù)據(jù)結(jié)構(gòu)與算法相輔相成1.2.3 算法特性輸入算法具有0個(gè)或多個(gè)輸入輸出算法至少有1個(gè)或多個(gè)輸出有窮性算法在有限的步驟之后會(huì)自動(dòng)結(jié)束而不會(huì)無限循環(huán)確定性算法中的每一

6、步都有確定的含義，不會(huì)出現(xiàn)二義性可行性算法的每一步都是可行的1.2.4 算法效率的度量1、事后統(tǒng)計(jì)法比較不同算法對(duì)同一組輸入數(shù)據(jù)的運(yùn)行處理時(shí)間缺陷為了獲得不同算法的運(yùn)行時(shí)間必須編寫相應(yīng)程序運(yùn)行時(shí)間嚴(yán)重依賴硬件以及運(yùn)行時(shí)的環(huán)境因素算法的測(cè)試數(shù)據(jù)的選取相當(dāng)困難事后統(tǒng)計(jì)法雖然直觀，但是實(shí)施困難且缺陷多算法效率的度量事前分析估算依據(jù)統(tǒng)計(jì)的方法對(duì)算法效率進(jìn)行估算影響算法效率的主要因素算法采用的策略和方法問題的輸入規(guī)模編譯器所產(chǎn)生的代碼計(jì)算機(jī)執(zhí)行速度算法最終編譯成具體的計(jì)算機(jī)指令每一個(gè)指令，在具體的計(jì)算機(jī)上運(yùn)行速度固定通過具體的n的步驟，就可以推導(dǎo)出算法的復(fù)雜度longsum1(intn)longret=

7、0;int*array=(int*)malloc(n*sizeof(int);inti=0;for(i=0;i<n;i+)arrayi=i+1;for(i=0;i<n;i+)ret+=arrayi;free(array);returnret;longsum2(intn)longret=0;inti=0;for(i=1;i<=n;i+)ret+=i;returnret;longsum3(intn)longret=0;if(n>0)ret=(1+n)*n/2;returnret;intmain()printf("%dn",sum1(100);printf

8、("%dn",sum2(100);printf("%dn",sum3(100);return0;intfunc(inta口，intlen)inti=0;intj=0;ints=0;for(i=0;i<len;i+)nfor(j=0;j<len;j+)ns+=i*j;/n*nreturns;/n*n2、大O表不法算法效率嚴(yán)重依賴于操作(Operation)數(shù)量在判斷時(shí)首先關(guān)注操作數(shù)量的最高次項(xiàng)操作數(shù)量的估算可以作為時(shí)間復(fù)雜度的估算0(5)=0(1)0(2n+1)=0(2n)=0(n)0(n2+n+1)=0(n2)O(3n3+1)=O(3n3)=

9、0(n3)常見時(shí)間復(fù)雜度執(zhí)行次貼函時(shí)1»1r堂正木水12110(1)1京做階2n-+-310(/3)喊初階3nJ+2n+10(/)千方階51njn+20O(1ogo)1時(shí)救階2n+3rde19O(rrio-gA)nlo-gn階601-+in1-*'3n+4j'0方暗2"i0(2")居林階關(guān)系0(1)<O(1og/I)<O(w)<O(nogn)<O(n2)<0(/)<0(21)<0(訊)<0(nn)3、算法的空間復(fù)雜度算法的空間復(fù)雜度通過計(jì)算算法的存儲(chǔ)空間實(shí)現(xiàn)S(n)=O(f(n)其中，n為問題規(guī)模，f

10、(n)為在問題規(guī)模為n時(shí)所占用存儲(chǔ)空間的函數(shù)大O表示法同樣適用于算法的空間復(fù)雜度當(dāng)算法執(zhí)行時(shí)所需要的空間是常數(shù)時(shí)，空間復(fù)雜度為0(1)空間與時(shí)間的策略多數(shù)情況下，算法執(zhí)行時(shí)所用的時(shí)間更令人關(guān)注如果有必要，可以通過增加空間復(fù)雜度來降低時(shí)間復(fù)雜度同理，也可以通過增加時(shí)間復(fù)雜度來降低空間復(fù)雜度練習(xí)1:分析sumlsum2sum3函數(shù)的空間復(fù)雜度O(4n+12)0(8)=0(1)0(4)=0(1)總結(jié)：實(shí)現(xiàn)算法時(shí)，需要分析具體問題，對(duì)執(zhí)行時(shí)間和空間的要求。練習(xí)2:時(shí)間換空間/*問題：在一個(gè)由自然數(shù)1-1000中某些數(shù)字所組成的數(shù)組中，每個(gè)數(shù)字可能出現(xiàn)零次或者多次。設(shè)計(jì)一個(gè)算法，找出出現(xiàn)次數(shù)最多的數(shù)字。

11、*/方法1：排序，然后找出出現(xiàn)次數(shù)最多的數(shù)字方法2:voidsearch(inta口，intlen)intsp1000=0;inti=0;intmax=0;for(i=0;i<len;i+)intindex=ai-1;spindex+;for(i=0;i<1000;i+)if(max<spi)max=spi;for(i=0;i<1000;i+)if(max=spi)printf("%dn",i+1);intmain()intarray口=1,1,3,4,5,6,6,6,2,3;search(array,sizeof(array)/sizeof(*ar

12、ray);return0;把每個(gè)數(shù)字出現(xiàn)的次數(shù)的中間結(jié)果，緩存下來；在緩存的結(jié)果中求最大值。UiX義ONJ,UJ.JL數(shù)字n出現(xiàn)的次數(shù)放在新開辟的內(nèi)存空間的式51的位置把每一個(gè)數(shù)字的中間結(jié)果給堞存下來.2、線性表2.1 線性表基本概念2.1.1 線性表定義線性表(List)是零個(gè)或多個(gè)數(shù)據(jù)元素的集合線性表中的數(shù)據(jù)元素之間是有順序的線性表中的數(shù)據(jù)元素個(gè)數(shù)是有限的線性表中的數(shù)據(jù)元素的類型必須相同先來一個(gè)大家最感興趣的，一年里的星座列表，是不是線性表呢？如圖3-2-2所白金雙巨獅處天射摩水雙羊牛,子蟹子女秤手,羯瓶,魚2.1.2 數(shù)學(xué)定義線性表是具有相同類型的n(>0)個(gè)數(shù)據(jù)元素的有限序列(a

13、1,a2,，an)ai是表項(xiàng)，n是表長(zhǎng)度。2.1.3 性質(zhì)a0為線性表的第一個(gè)元素，只有一個(gè)后繼an為線性表的最后一個(gè)元素，只有一個(gè)前驅(qū)除a0和an外的其它元素ai,既有前驅(qū)，又有后繼線性表能夠逐項(xiàng)訪問和順序存取2.1.4 練習(xí)下面的關(guān)系中可以用線性表描述的是A.班級(jí)中同學(xué)的友誼關(guān)系N:NB.公司中的上下級(jí)關(guān)系1:NC冬天圖書館排隊(duì)占座關(guān)系D.花名冊(cè)上名字之間的關(guān)系1:12.2.5線性表的操作創(chuàng)建線性表銷毀線性表清空線性表將元素插入線性表將元素從線性表中刪除獲取線性表中某個(gè)位置的元素獲取線性表的長(zhǎng)度線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型線性表的操作在程序中的表現(xiàn)為一組函數(shù)c語言描述=線性表的設(shè)

14、計(jì)與實(shí)現(xiàn)ADT抽象層數(shù)據(jù)Z勾(C語言版).嚴(yán)蔚敏_吳偉民.掃描版.pdfp44頁人生財(cái)富庫積累#ifndef_WBM_LIST_H_#define_WBM_LIST_H_typedefvoidList;typedefvoidListNode;/創(chuàng)建并且返回一個(gè)空的線性表List*List_Create();/銷毀一個(gè)線性表listvoidList_Destroy(List*list);將一個(gè)線性表list中的所有元素清空，線性表回到創(chuàng)建時(shí)的初始狀態(tài)voidList_Clear(List*list);/返回一個(gè)線性表list中的所有元素個(gè)數(shù)intList_Length(List*list);/向

15、一個(gè)線性表list的pos位置處插入新元素nodeintList_Insert(List*list,ListNode*node,intpos);/獲取一個(gè)線性表list的pos位置處的元素ListNode*List_Get(List*list,intpos);/刪除一個(gè)線性表list的pos位置處的元素返回值為被刪除的元素，NULL表示刪除失敗ListNode*List_Delete(List*list,intpos);#endif注意：intListInsert(List*list,ListNode*node,intpos);(重點(diǎn)：分離思想)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1基本概念34

16、1順序存儲(chǔ)定義說這么多的稅性表,我們來看看線性及的胸牌枷理結(jié)梅的第種順序存儲(chǔ)站構(gòu).線性衰的序存佛結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元儂次存儲(chǔ)場(chǎng)性表的觸據(jù)元*口線性衣閏C的順序存儲(chǔ)示意圖如下：2.2.2設(shè)計(jì)與實(shí)現(xiàn)插入元素算法判斷線性表是否合法判斷插入位置是否合法把最后一個(gè)元素到插入位置的元素后移一個(gè)位置將新元素插入線性表長(zhǎng)度加1獲取元素操作判斷線性表是否合法判斷位置是否合法直接通過數(shù)組下標(biāo)的方式獲取元素刪除元素算法判斷線性表是否合法判斷刪除位置是否合法將元素取出將刪除位置后的元素分別向前移動(dòng)一個(gè)位置線性表長(zhǎng)度減1鏈表順序存儲(chǔ)插入算法和刪除算法*股垠序存他:語表的答民和短表的實(shí)阮無縣出商戶工司網(wǎng)酒

17、主叵匚立zu口口耳二口口劇索空閭外呼一I-*/d662)"Gm演郊|/1”后移為1鼻=1詠時(shí)口；irWE；1)jLU-川工I=aUJ/j73.缽九元聿2.2.3優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：無需為線性表中的邏輯關(guān)系增加額外的空間可以快速的獲取表中合法位置的元素缺點(diǎn)：插入和刪除操作需要移動(dòng)大量元素當(dāng)線性表長(zhǎng)度變化較大時(shí)難以確定存儲(chǔ)空間的容量2.3線性表的鏈?zhǔn)酱鎯?chǔ)2.3.1基本概念鏈?zhǔn)酱鎯?chǔ)定義為了表示每個(gè)數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系,的信息外，還需要存儲(chǔ)指示其直接后繼的信息。每個(gè)元素除了存儲(chǔ)本身n個(gè)結(jié)點(diǎn)Qi的存儲(chǔ)映像）鏈結(jié)成一個(gè)鏈表，即為線性表（au正，a.）的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)

18、結(jié)點(diǎn)中只包含一個(gè)指針域，所以叫做單鏈表.單橙表正是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元裁按其邏輯次序鏈接在一起，如圖352所示*表頭結(jié)點(diǎn)鏈表中的第一個(gè)結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針以及鏈表自身的一些信息數(shù)據(jù)結(jié)點(diǎn)鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，包含指向下一個(gè)數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息尾結(jié)點(diǎn)鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，其下一元素指針為空，表示無后繼。2.3.2鏈表技術(shù)領(lǐng)域推演修統(tǒng)域悒2.3.2設(shè)計(jì)與實(shí)現(xiàn)鏈表鏈?zhǔn)酱鎯?chǔ)_api實(shí)現(xiàn)分析在c語言中可以用結(jié)構(gòu)體來定義鏈表中的指針域鏈表中的表頭結(jié)點(diǎn)也可以用結(jié)構(gòu)體實(shí)現(xiàn)typedefstruct_tagLinkListHodeLiniLislHode;strud

19、tawLinkListHode(LinkListNode*fieut：站點(diǎn)指針域定義typedefstruct_tag_LinkLiff't(LinkListNodeheader：intlength.TLinkList：義站點(diǎn)定義structValueLinlrListNodeheader;intv,數(shù)據(jù)元案定義示例插入元素操作currentciirr«nt'>nftTtaiH2J1nndrnbde-current->next；currezlt，-'next=node;nodeint pos)帶頭結(jié)點(diǎn)、位置從0的單鏈表返回鏈表中第3個(gè)位置處，元素的

20、值LinkListNode*LinkList_Get(LinkList*list,inti=0;TLinkList*tList=(TLinkList*)list;LinkListNode*current=NULL;LinkListNode*ret=NULL;if(list=NULL11Pos<0|pos>=tList->length)returnNULL;current=(LinkListNode*)tList;for(i=0;i<pos;i+)current=current->next;ret=current->next;returnret;返回第三個(gè)位置

21、的移動(dòng)pos次以后，當(dāng)前指針指向哪里？答案：指向位置2,所以需要返回ret=current->next;備注：循環(huán)遍歷時(shí)，遍歷第1次，指向位置0遍歷第2次，指向位置1遍歷第3次，指向位置2遍歷第n次，指向位置n-1;所以如果想返回位置n的元素的值，需要怎么做ret=current->next;此問題是：指向頭結(jié)點(diǎn)的指針移動(dòng)n次和第n個(gè)元素之間的關(guān)系?刪除元素current->next=ret->next;重要技術(shù)場(chǎng)景圖鏈表鏈?zhǔn)酱鎯?chǔ)插入專UTTEEitLijudcSiuEit=4UTETnl->r詛工I,2tunent->Mxt-g;b;1將丈指向惟就把址他地

22、址賦始拒針2分精董健表的操作邏楫和輔助指針變量之間的美桑鏈表鏈?zhǔn)酱鎯?chǔ)刪除2.3.3優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：無需一次性定制鏈表的容量插入和刪除操作無需移動(dòng)數(shù)據(jù)元素缺點(diǎn)：數(shù)據(jù)元素必須保存后繼元素的位置信息獲取指定數(shù)據(jù)的元素操作需要順序訪問之前的元素2.4循環(huán)鏈表2.4.1基本概念循環(huán)鏈表的定義：將單鏈表中最后一個(gè)數(shù)據(jù)元素的next指針指向第一個(gè)元素循環(huán)鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長(zhǎng)度清空鏈表獲取第pos個(gè)元素操作插入元素到位置pos刪除位置pos處的元素新增功能：游標(biāo)的定義在循環(huán)鏈表中可以定義一個(gè)“當(dāng)前”歷鏈表中的所有兀素。指針，這個(gè)指針通常稱為游標(biāo)，可以通過這個(gè)游標(biāo)來遍天結(jié)點(diǎn)尾結(jié)直游

23、標(biāo)glider循環(huán)鏈表新操作將游標(biāo)重置指向鏈表中的第一個(gè)數(shù)據(jù)元素CircleListNode*CircleList_Reset(CircleList*list);獲取當(dāng)前游標(biāo)指向的數(shù)據(jù)元素CircleListNode*CircleList_Current(CircleList*list);將游標(biāo)移動(dòng)指向到鏈表中的下一個(gè)數(shù)據(jù)元素CircleListNode*CircleList_Next(CircleList*list);直接指定刪除鏈表中的某個(gè)數(shù)據(jù)元素CircleListNode*CircleList_DeleteNode(CircleList*list,CircleListNode*node

24、);/根據(jù)元素的值刪除元素pk根據(jù)元素的位置刪除元素2.4.2循環(huán)鏈表的應(yīng)用證明循環(huán)鏈表打印兩次。約瑟夫問題求解約瑟夫問題-循環(huán)鏈表典型應(yīng)用n個(gè)人圍成一個(gè)圓圈，首先第1個(gè)人從1開始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人,令其出列。然后再從下一個(gè)人開始從1順時(shí)針報(bào)數(shù)，報(bào)到第m個(gè)人，再令其出列，如此下去，求出列順序。大話數(shù)據(jù)結(jié)構(gòu)3.16結(jié)尾：寫書的人，也很累；臨界點(diǎn)在六十年代出生的人應(yīng)該也就是我們父母那一基，當(dāng)年計(jì)倒經(jīng)濟(jì)制度下他們的生活被社會(huì)安排好心先科員再科后處長(zhǎng)再局長(zhǎng)，混到哪算哪；學(xué)徒、技工、高級(jí)技_L;敦新-中領(lǐng)教帥一高級(jí)教師，總之無論喙個(gè)行業(yè)榭論蟋排羋.這怦的生活

25、如何讓人奮發(fā)勇力,所以經(jīng)濟(jì)發(fā)展緩慢.就像我們的線性表的順序存儲(chǔ)結(jié)構(gòu)一樣，位就是排好的，一切都得慢慢來.可見，舒適環(huán)境是很唯培養(yǎng)出堅(jiān)強(qiáng)品格,被安排好的人生，也很雁做出偉大事業(yè)”市場(chǎng)經(jīng)濟(jì)社會(huì)下，機(jī)會(huì)就大多了，你可以從社會(huì)的任何一個(gè)位置開始起步，只要你真有決心.沒有人可以攔著你.書實(shí)也證明，無論出身是什么之前是凄苦還是富足，都有出入頭他的一天當(dāng)然，這也就意味著，面臨的競(jìng)爭(zhēng)也是空ft烈的，一不小心，你的位就可能被人嫡足，甚至你就得out山叮。這也塞像我線性友的蛀式存儲(chǔ)結(jié)構(gòu)，任何位置都可以插入和刪除.a不怕苫，吃苦半輩F,怕吃苦，吃苦一般干.如果你覺得上學(xué)讀書是受罪，假設(shè)你可以活到日。歲.其實(shí)你楠多也就

26、吃了20年苦口用人生四分之一的時(shí)間來換取其余時(shí)同的幸福生活.這點(diǎn)苦不算啥，再說了跟著我學(xué)習(xí)，這也能算是吃苦？好了，今天課就到這，下課.2.4.3 設(shè)計(jì)與實(shí)現(xiàn) 循環(huán)鏈表插入元素的分析1)普通插入元素(和單鏈表是一樣的)2)尾插法(和單鏈表是一樣的，單鏈表的寫法支持尾插法；因：輔助指針向后跳length次，指向最后面那個(gè)元素)CircleList_Insert(list,(CircleListNode*)&v1,CircleList_Length(list);CircleList_Insert(list,(CircleListNode*)&v1,CircleList_

27、Length(list);3)頭插法(要進(jìn)行頭插法，需要求出尾結(jié)點(diǎn)，和單鏈表不一樣的地方，保證是循環(huán)鏈表)第一次插入元素時(shí)，讓游標(biāo)指向0號(hào)結(jié)點(diǎn)CircleList_Insert(list,(CircleListNode*)&v1,0);CircleList_Insert(list,(CircleListNode*)&v1,0);4）第一次插入元素 循環(huán)鏈表插入綜合場(chǎng)景分析圖1蘭建插入工希（和年經(jīng)表是一甘左）4、無到有的國(guó)航抽入和運(yùn)蹲表是一咻彷HULL41插法，駐要求出玩相汴點(diǎn)?od 循環(huán)鏈表刪除結(jié)點(diǎn)分析1、刪除普通結(jié)點(diǎn)2、刪除頭結(jié)點(diǎn)(刪除0號(hào)位置處元

28、素)，需要求出尾結(jié)點(diǎn)2.4.4 優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：功能強(qiáng)了。循環(huán)鏈表只是在單鏈表的基礎(chǔ)上做了一個(gè)加強(qiáng)循環(huán)鏈表可以完全取代單鏈表的使用循環(huán)鏈表的Next和Current操作可以高效的遍歷鏈表中的所有元素缺點(diǎn)：代碼復(fù)雜度提高了大話數(shù)據(jù)結(jié)構(gòu)3.16結(jié)尾：寫書的人，也很累；臨界點(diǎn)2.5雙向鏈表2.5.1 基本概念請(qǐng)思考：為什么需要雙向鏈表？單鏈表的結(jié)點(diǎn)都只有一個(gè)指向下一個(gè)結(jié)點(diǎn)的指針單鏈表的數(shù)據(jù)元素?zé)o法直接訪問其前驅(qū)元素逆序訪問單鏈表中的元素是極其耗時(shí)的操作!len=LinkList_Length(list);for(i=len-1;len>=0;i+)O(n)LinkListNode*p=Link

29、List_Get(list,i);O(n)訪問數(shù)據(jù)元素p中的元素/雙向鏈表的定義在單鏈表的結(jié)點(diǎn)中增加一個(gè)指向其前驅(qū)的pre指針雙向鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長(zhǎng)度清空鏈表獲取第pos個(gè)元素操作插入元素到位置pos刪除位置pos處的元素2.5.2 設(shè)計(jì)與實(shí)現(xiàn)循環(huán)鏈表一般操作插入操作currentnext *t 1、一nodecurrent->next=node;node->next=next;next->pi:e=node;node->pre=current:插入操作異常處理插入第一個(gè)元素異常處理在0號(hào)位置處插入元素；刪除操作current->n

30、ext=next;next*>pre=current;刪除操作異常處理雙向鏈表的新操作獲取當(dāng)前游標(biāo)指向的數(shù)據(jù)元素將游標(biāo)重置指向鏈表中的第一個(gè)數(shù)據(jù)元素將游標(biāo)移動(dòng)指向到鏈表中的下一個(gè)數(shù)據(jù)元素將游標(biāo)移動(dòng)指向到鏈表中的上一個(gè)數(shù)據(jù)元素直接指定刪除鏈表中的某個(gè)數(shù)據(jù)元素DLinkListNode*DLinkList_DeleteNode(DLinkList*list,DLinkListNode*node);DLinkListNode*DLinkList_Reset(DLinkList*list);DLinkListNode*DLinkList_Current(DLinkList*list);DLink

31、ListNode*DLinkList_Next(DLinkList*list);DLinkListNode*DLinkList_Pre(DLinkList*list);大家一定要注意：教科書不會(huì)告訴你項(xiàng)目上如何用；哪些點(diǎn)是項(xiàng)目的重點(diǎn)；做一個(gè)企業(yè)級(jí)的財(cái)富庫，完成你人生開發(fā)經(jīng)驗(yàn)的積累，是我們的學(xué)習(xí)重點(diǎn)，要注意!雙向鏈表重要技術(shù)場(chǎng)景循環(huán)鏈表插入結(jié)點(diǎn)技術(shù)場(chǎng)景U通植入c urz- ETlt與性人第一個(gè)早點(diǎn)r E要判斷 七問梯作nas r-L-ijrr&nt -3、atGUTTEt-An乎- nnd«nade ->pre - turrent, nCTt->pre - nodn

32、在尼爾崎，元臬普通話人代碼潮足循環(huán)鏈表刪除結(jié)點(diǎn)技術(shù)場(chǎng)景2.5.3 優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：雙向鏈表在單鏈表的基礎(chǔ)上增加了指向前驅(qū)的指針功能上雙向鏈表可以完全取代單鏈表的使用雙向鏈表的Next,Pre和Current操作可以高效的遍歷鏈表中的所有元素缺點(diǎn)：代碼復(fù)雜3、棧tack和隊(duì)列queue3.1棧stack3.1.1Stack基本概念棧是一種特殊的線性表?xiàng)H能在線性表的一端進(jìn)行操作棧頂(Top):允許操作的一端棧底(Bottom):不允許操作的一端首先它是一個(gè)稅性表,也就是說,錢元素具有線性美系，即前解后繼美系,只不過它是一種將殊的統(tǒng)性表而已,定義中說是在線性表的表尾進(jìn)行插入和刪除操作，這里表尾是指

33、棧頂.而不是榭在口它的特殊之處就在于限制了這個(gè)我性我的插人和冽除位置，它始絳只在炭頂進(jìn)行這也就使得：根底是固定的,最先進(jìn)棧的只能在枝底.棧的插入操祚，叫作進(jìn)根，也稱壓棧，入棧u類似彈入彈夾，如圖42由所示.棧的JM除操作,叫作出棧，也有的叫作彈棧.如同彈夾中的子彈出火.如圖4233.1.2Stack的常用操作創(chuàng)建棧銷毀棧清空棧進(jìn)棧出棧獲取棧頂元素獲取棧的大小c語言描述=棧的設(shè)計(jì)與實(shí)現(xiàn)人生財(cái)富庫積累#ifndef_MY_STACK_H_#define_MY_STACK_H_typedefvoidStack;Stack*Stack_Create();voidStack_Destroy(Stack*

34、stack);voidStack_Clear(Stack*stack);intStackPush(Stack*stack,void*item);void*Stack_Pop(Stack*stack);void*Stack_Top(Stack*stack);intStack_Size(Stack*stack);#endif/MYSTACKH3.1.3棧模型和鏈表模型關(guān)系分析統(tǒng)性恚的順序耳盲來漠刁抬4 在尾拿蛀成普麗兀器不會(huì)替班別覺 組但兀手”是¥刻，防口：生粒咽足型插入JH聯(lián)元.于匕找等用魁我內(nèi)鋌式壽金來 摸故怪的些性有特 斫如在碓亮狙部插人削解弟希比粒好sn 工，r3.1.4棧的順序

35、存儲(chǔ)設(shè)計(jì)與實(shí)現(xiàn)基本概念枝有兩個(gè)元素.至核，(CFfTiJtop«U設(shè)計(jì)與實(shí)現(xiàn)頭文件#ifndef_MY_SEQLIST_H_#define_MY_SEQLIST_H_typedefvoidSeqList;typedefvoidSeqListNode;SeqList*SeqStack_Create(intcapacity);voidSeqStack_Destroy(SeqStack*list);voidSeqStack_Clear(SeqStack*list);intSeqStack_Length(SeqStack*list);intSeqStack_Capacity(SeqStack

36、*list);intSeqStack_Insert(SeqStack*list,SeqListNode*node,intpos);SeqListNode*SeqList_Get(SeqList*list,intpos);SeqListNode*SeqListDelete(SeqList*list,intpos);#endif_MY_SEQLIST_H_3.1.5棧的鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)與實(shí)現(xiàn)基本概念講完哎的順序存隔結(jié)構(gòu)，我們筑在來看狗棧的鏈?zhǔn)酱鎯?chǔ)結(jié)溝，筒稱為鏈找.想想行.棧只是桎頂來做插入和惻除操作.棧頂放棄鉆去的頭部還旱尾部呢？由于單縫去行頭指針，而覆頂指針也是必紈的，那干嗎不讓它倆合二為一呢，所以

37、比較好的辦法是把棧頂放在單樁表的頭部（如圖4&1所示）*另外，都已豌有了錢頂在頭部了，單鏈表中二轉(zhuǎn)常用的頭轉(zhuǎn)點(diǎn)也就失去了意義，通常豺干鏤愧來說，是不需襄頭結(jié)點(diǎn)的&A住底設(shè)計(jì)與實(shí)現(xiàn)頭文件#ifndef_MY_LINKSTACK_H_#define_MY_LINKSTACK_H_typedefvoidLinkStack;LinkStack*LinkStack_Create();voidLinkStackDestroy(LinkStack*stack);voidLinkStack_Clear(LinkStack*stack);intLinkStack_Push(LinkStack*s

38、tack,void*item);void*LinkStack_Pop(LinkStack*stack);void*LinkStack_Top(LinkStack*stack);intLinkStack_Size(LinkStack*stack);#endif_MY_LINKSTACK_H_3.1.6棧的應(yīng)用案例1：就近匹配應(yīng)用1：就近匹配幾乎所有的編譯器都具有檢測(cè)括號(hào)是否匹配的能力如何實(shí)現(xiàn)編譯器中的符號(hào)成對(duì)檢測(cè)？#include<stdio.h>intmain()inta44;int(*p)4;p=a0;return0;算法思路從第一個(gè)字符開始掃描當(dāng)遇見普通字符時(shí)忽略，當(dāng)遇見左符號(hào)

39、時(shí)壓入棧中當(dāng)遇見右符號(hào)時(shí)從棧中彈出棧頂符號(hào)，并進(jìn)行匹配匹配成功：繼續(xù)讀入下一個(gè)字符匹配失?。毫⒓赐Ｖ?，并報(bào)錯(cuò)結(jié)束：成功：所有字符掃描完畢，且棧為空失?。浩ヅ涫』蛩凶址麙呙柰戤叺珬７强债?dāng)需要檢測(cè)成對(duì)出現(xiàn)但又互不相鄰的事物時(shí)可以使用?！昂筮M(jìn)先出”的特性棧非常適合于需要“就近匹配”的場(chǎng)合計(jì)算機(jī)的本質(zhì)工作就是做數(shù)學(xué)運(yùn)算，那計(jì)算機(jī)可以讀入字符串“9+(3-1)*5+8/2”并計(jì)算值嗎？案例2:中綴表達(dá)式和后綴表達(dá)式應(yīng)用2:中綴后綴計(jì)算機(jī)的本質(zhì)工作就是做數(shù)學(xué)運(yùn)算，那計(jì)算機(jī)可以讀入字符串“9+(3-1)*5+8/2”并計(jì)算值嗎？后綴表達(dá)式=?符合計(jì)算機(jī)運(yùn)算波蘭科學(xué)家在20世紀(jì)50年代提出了一種將運(yùn)算符放

40、在數(shù)字后面的后綴表達(dá)式對(duì)應(yīng)的,我們習(xí)慣的數(shù)學(xué)表達(dá)式叫做中綴表達(dá)式=»符合人類思考習(xí)慣實(shí)例：5+4=>54+1+2*3=>123*+8+(3-1)*5=>831-5*+中綴表達(dá)式符合人類的閱讀和思維習(xí)慣后綴表達(dá)式符合計(jì)算機(jī)的“運(yùn)算習(xí)慣”如何將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式？中綴轉(zhuǎn)后綴算法：遍歷中綴表達(dá)式中的數(shù)字和符號(hào)對(duì)于數(shù)字：直接輸出對(duì)于符號(hào)：左括號(hào)：進(jìn)棧運(yùn)算符號(hào)：與棧頂符號(hào)進(jìn)行優(yōu)先級(jí)比較若棧頂符號(hào)優(yōu)先級(jí)低：此符合進(jìn)棧(默認(rèn)棧頂若是左括號(hào)，左括號(hào)優(yōu)先級(jí)最低)若棧頂符號(hào)優(yōu)先級(jí)不低：將棧頂符號(hào)彈出并輸出，之后進(jìn)棧右括號(hào)：將棧頂符號(hào)彈出并輸出，直到匹配左括號(hào)遍歷結(jié)束：將棧中的所

41、有符號(hào)彈出并輸出中綴轉(zhuǎn)后綴whil*( eKp(i ，= j )if( expli為數(shù)字)(trarisform(exp)(電低控S;Output(e»p|il);elself(expli)向符號(hào))(wHiUspill優(yōu)先場(chǎng)<=極預(yù)苻號(hào)優(yōu)先照)output；pop(s)；1Push之印)；elseift*p|i為左括號(hào))(Push(工exp(i)；tls«iffexp(i)為右推號(hào))(mile筏型存號(hào)不為在括號(hào)>output(335Pop(S)；從S甲牌出左括號(hào)一else<根檔.停止循環(huán)；1+:whi.le(Sie(S)>卜3(expi)Output

42、崔項(xiàng)布號(hào));P叩S);計(jì)算機(jī)是如何基于后綴表達(dá)式計(jì)算的?831-5*+遍歷后綴表達(dá)式中的數(shù)字和符號(hào)對(duì)于數(shù)字：進(jìn)棧對(duì)于符號(hào)：從棧中彈出右操作數(shù)從棧中彈出左操作數(shù)根據(jù)符號(hào)進(jìn)行運(yùn)算將運(yùn)算結(jié)果壓入棧中遍歷結(jié)束：棧中的唯一數(shù)字為計(jì)算結(jié)果compute(exp)包建糧S;1 =0;while!expi!空y)if(expi為野字)(Pushexpil;elseif(expi為符號(hào))1從柱中彈出右寸蜃作熱；2 .從柱中彈左操作數(shù)；3 .概據(jù)符號(hào)進(jìn)行運(yùn)苒；4 .Push(stack,結(jié)果)；)else(報(bào)格,停止循環(huán)；1+十；)if(Size(5)-L)&&(expi=,oi)橫甲唯一的數(shù)字為

43、運(yùn)算縮果；返回結(jié)果;)棧的神奇！中綴表達(dá)式是人習(xí)慣的表達(dá)方式后綴表達(dá)式是計(jì)算機(jī)喜歡的表達(dá)方式通過棧可以方便的將中綴形式變換為后綴形式中綴表達(dá)式的計(jì)算過程類似程序編譯運(yùn)行的過程擴(kuò)展：給你一個(gè)字符串，計(jì)算結(jié)果1+2*(66/(2*3)+7)”1字符串解析詞法語法分析優(yōu)先級(jí)分析數(shù)據(jù)結(jié)本選型=»棧還是樹？3.2隊(duì)列queue3.2.1queue基本概念隊(duì)列是一種特殊的線性表隊(duì)列僅在線性表的兩端進(jìn)行操作隊(duì)頭(Front):取出數(shù)據(jù)元素的一端隊(duì)尾(Rear):插入數(shù)據(jù)元素的一端隊(duì)列不允許在中間部位進(jìn)行操作！AM石條咬和善服手班卬.都是座用廣懺釵瘠結(jié)帶來實(shí)現(xiàn)剛才提至I的先迸先山的排隊(duì)功能，這就是隊(duì)

44、列.隊(duì)列，queue是只允許在一端進(jìn)行播入讖作.而在另一第進(jìn)行除操作的線性衰隊(duì)列是一種先進(jìn)先出(FirstInFirstOut)的線性表，筒稱FIFO.允許插入的一端稱為隊(duì)尾，允許刪除的T稱為隊(duì)頭.假設(shè)隊(duì)列是q=(也，事，*Ah那么<1就是隊(duì)員元素，而斯是隊(duì)尾元素.這樣我們就可以刪除時(shí)，總是從*開始,而播人時(shí)，列在最后，這也比較符合我們逋常生活中的習(xí)慣，排在第一個(gè)的優(yōu)先出列，最后來的當(dāng)熱排在隊(duì)伍最后，如圖4T0-1所示.隊(duì)頭|鼠尾I3a2a3匹11ffl4-10-1隊(duì)列在程序設(shè)計(jì)中用4WE常頻鬟.前面我們巳經(jīng)舉了兩個(gè)例子.再比如用鍵盤進(jìn)行各種字扉或數(shù)字的愉入.到顯示器上如記事本軟件上的輸

45、出,其實(shí)就是隊(duì)列的典型3.2.2queue常用操作銷毀隊(duì)列清空隊(duì)列進(jìn)隊(duì)列出隊(duì)列獲取隊(duì)頭元素獲取隊(duì)列的長(zhǎng)度c語言描述=隊(duì)列的設(shè)計(jì)與實(shí)現(xiàn)人生財(cái)富庫積累#ifndef_MY_QUEUE_H_#define_MY_QUEUE_H_typedefvoidQueue;Queue*Queue_Create();voidQueue_Destroy(Queue*queue);voidQueue_Clear(Queue*queue);intQueue_Append(Queue*queue,void*item);void*Queue_Retrieve(Queue*queue);void*Queue_Header(Q

46、ueue*queue);intQueue_Length(Queue*queue);#endif/MYQUEUEH3.2.3 隊(duì)列模型和鏈表模型關(guān)系分析用象里來摸息a劑；從致幻的足煞入m列隊(duì)抵蛆的口號(hào)位考出隊(duì)列I.口頭F口目國(guó)口需要把隊(duì)列給點(diǎn)=力豌表年占=入錐表庫用靜表兼模皿認(rèn)到.出總到的星器人覬列從畸表的。號(hào)也曾出隊(duì)列不費(fèi)忘記讓所有菇點(diǎn)出隊(duì)列，然后評(píng)兼結(jié)點(diǎn)的內(nèi)存3.2.4 隊(duì)列的順序存儲(chǔ)設(shè)計(jì)與實(shí)現(xiàn)1基本概念隊(duì)列也是一種特殊的線性表；可以用線性表順序存儲(chǔ)來模擬隊(duì)列。2設(shè)計(jì)與實(shí)現(xiàn)#ifndef_MY_SEQQUEUE_H_#define_MY_SEQQUEUE_H_typedefvoidSeqQu

47、eue;SeqQueue*SeqQueue_Create(intcapacity);voidSeqQueue_Destroy(SeqQueue*queue);voidSeqQueue_Clear(SeqQueue*queue);intSeqQueue_Append(SeqQueue*queue,void*item);void*SeqQueue_Retrieve(SeqQueue*queue);void*SeqQueue_Header(SeqQueue*queue);intSeqQueue_Length(SeqQueue*queue);intSeqQueue_Capacity(SeqQueue*

48、queue);#endif/MYSEQQUEUEH3.2.5 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)與實(shí)現(xiàn)1基本概念隊(duì)列也是一種特殊的線性表；可以用線性表鏈?zhǔn)酱鎯?chǔ)來模擬隊(duì)列的鏈?zhǔn)酱鎯?chǔ)。2設(shè)計(jì)與實(shí)現(xiàn)#ifndef_MY_LINKQUEUE_H_#define_MY_LINKQUEUE_H_typedefvoidLinkQueue;LinkQueue*LinkQueueCreate();voidLinkQueue_Destroy(LinkQueue*queue);voidLinkQueue_Clear(LinkQueue*queue);intLinkQueue_Append(LinkQueue*queue,void*

49、item);void*LinkQueue_Retrieve(LinkQueue*queue);void*LinkQueue_Header(LinkQueue*queue);intLinkQueue_Length(LinkQueue*queue);#endifMYLINKQUEUEH4、樹專題4.1 樹基本概念基礎(chǔ)講義：參考數(shù)據(jù)結(jié)構(gòu)_樹A.ppt»參考數(shù)據(jù)結(jié)構(gòu)_樹B.ppt非線性結(jié)構(gòu)，一個(gè)直接前驅(qū)，但可能有多個(gè)直接后繼（1n）樹的定義1）具有遞歸性，即樹中還有樹2）m顆互不相交的集合根葉子森林有序樹無序樹雙親孩子兄弟堂兄弟祖先子孫結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的層次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度所有結(jié)點(diǎn)度中

50、的最大值（Max各結(jié)點(diǎn)的度樹的深度指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次（或高度）4.2 樹的表示法圖形表示法廣義表表示法左孩子-右兄弟表示法雙親孩子表示法4.3 樹的邏輯結(jié)構(gòu)一對(duì)多（1：n）,有多個(gè)直接后繼（如家譜樹、目錄樹等等），但只有一個(gè)根結(jié)點(diǎn)，且子樹之間互不相交。廣義表表示法左孩子一右兄弟表示法4.4 二叉樹概念4.4.1 基本概念二叉樹的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)可以證明，所有樹都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹，不失一般性定義：是n（n>0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成二叉樹性質(zhì)性質(zhì)1:在二叉機(jī)勺第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i&

51、gt;0）性質(zhì)2:深度為k的二叉樹至多有2k-i個(gè)結(jié)點(diǎn)（k>0）性質(zhì)3:對(duì)于任何一棵二叉樹，若2度的結(jié)點(diǎn)數(shù)有n2個(gè)，則葉子數(shù)（no）必定為n2+1（即no=n2+1）滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。（特點(diǎn)：每層都“充滿”了結(jié)點(diǎn)）完全二叉樹：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k"¥滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)對(duì)應(yīng)。理解：（k-1層與滿二叉樹完全相同，第k層結(jié)點(diǎn)盡力靠左）數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：數(shù)據(jù)Z構(gòu)（C語言版）.嚴(yán)蔚敏吳偉民.掃描版.pdfp124數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：數(shù)據(jù)Z構(gòu)（C語言版）.嚴(yán)蔚敏吳偉民.掃描版.pdfp127性質(zhì)4:具有n

52、個(gè)結(jié)點(diǎn)的完全二叉樹的深度必為log2n+1性質(zhì)5:對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i的結(jié)點(diǎn)，其左孩子編號(hào)必為2i,其右孩子編號(hào)必為2i+1;其雙親的編號(hào)必為i/2（i=1時(shí)為根，除外）二叉樹的存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。答：一律轉(zhuǎn)為完全二叉樹！討論：不是完全二叉樹怎么辦？方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上虛結(jié)點(diǎn)”，其內(nèi)容為空二、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)4.4.2 二叉樹的表示二叉樹表示法P127頁/*typedefstructBiTNodeintdata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;*/structBiTNodeintdata;structBiTNode*lchild,*rchild;typedefst