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

輕松入門實戰(zhàn)應(yīng)用僧1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)概念1.1.1疑惑C碼。程序是為了具體問題而存在的程序需要圍繞問題的解決進(jìn)行設(shè)計同一個問題可以有多種解決方案1.1.2數(shù)據(jù)結(jié)構(gòu)起源計算機(jī)從解決數(shù)值計算問題到解決生活中的問題現(xiàn)實生活中的問題涉及不同個體間的復(fù)雜聯(lián)系需要在計算機(jī)程序中描述生活中個體間的聯(lián)系數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計算程序問題中的操作對象以及它們之間的關(guān)系不是研究復(fù)雜的算法1.1.3數(shù)據(jù)結(jié)構(gòu)中的基本概念數(shù)據(jù)–程序的操作對象，用于描述客觀事物(inta,intb,)可以輸入到計算機(jī)可以被計算機(jī)程序處理數(shù)據(jù)元素：組成數(shù)據(jù)的基本單位數(shù)據(jù)對象–性質(zhì)相同的數(shù)據(jù)元素的集合(比如：數(shù)組，鏈表)輕松入門實戰(zhàn)應(yīng)用////友情提示，來自結(jié)構(gòu)體課堂代碼//聲明一個結(jié)構(gòu)體類型struct_MyTeacher//一種數(shù)據(jù)類型{charname[32];chartile[32];intage;charaddr[128];intmain21(){struct_MyTeachert1;//數(shù)據(jù)元素struct_MyTeachertArray[30];//數(shù)據(jù)對象memset(&t1,0,sizeof(t1));strcpy(,"name");//數(shù)據(jù)項strcpy(t1.addr,"addr");//數(shù)據(jù)項strcpy(t1.tile,"addr");//數(shù)據(jù)項t1.age=1;}數(shù)據(jù)元素之間不是獨(dú)立的，存在特定的關(guān)系，這些關(guān)系即結(jié)構(gòu)如：數(shù)組中各個元素之間存在固定的線性關(guān)系的輕松入門實戰(zhàn)應(yīng)用1.1.4數(shù)據(jù)的邏輯結(jié)構(gòu)輕松入門實戰(zhàn)應(yīng)用1.1.5數(shù)據(jù)的物理結(jié)構(gòu)1.1.6數(shù)據(jù)的運(yùn)算輕松入門實戰(zhàn)應(yīng)用1.2.1算法概念算法是特定問題求解步驟的描述在計算機(jī)中表現(xiàn)為指令的有限序列算法是獨(dú)立存在的一種解決問題的方法和思想。對于算法而言，語言并不重要，重要的是思想。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è)計和選擇算法===今程序=數(shù)據(jù)結(jié)構(gòu)+算法算法是為了解決實際問題而設(shè)計的數(shù)據(jù)結(jié)構(gòu)是算法需要處理的問題載體數(shù)據(jù)結(jié)構(gòu)與算法相輔相成1.2.3算法特性輸入輸出有窮性算法在有限的步驟之后會自動結(jié)束而不會無限循環(huán)確定性算法中的每一步都有確定的含義，不會出現(xiàn)二義性可行性算法的每一步都是可行的1.2.4算法效率的度量比較不同算法對同一組輸入數(shù)據(jù)的運(yùn)行處理時間輕松入門實戰(zhàn)應(yīng)用缺陷為了獲得不同算法的運(yùn)行時間必須編寫相應(yīng)程序運(yùn)行時間嚴(yán)重依賴硬件以及運(yùn)行時的環(huán)境因素算法的測試數(shù)據(jù)的選取相當(dāng)困難事后統(tǒng)計法雖然直觀，但是實施困難且缺陷多算法效率的度量事前分析估算依據(jù)統(tǒng)計的方法對算法效率進(jìn)行估算影響算法效率的主要因素算法采用的策略和方法編譯器所產(chǎn)生的代碼計算機(jī)執(zhí)行速度//算法最終編譯成具體的計算機(jī)指令//每一個指令，在具體的計算機(jī)上運(yùn)行速度固定//通過具體的n的步驟，就可以推導(dǎo)出算法的復(fù)雜度longsum1(intn){longret0;int*array=(int*)malloc(n*sizeof(int));ntifor(i=0;i<n;i++){array[i]=i+1;}for(i=0;i<n;i++){rrayi}freearray);et}longsum2(intn){ongretfor(i=1;i<=n;i++){輕松入門實戰(zhàn)應(yīng)用reti;}}longsum3(intn){ongretif(n>0){ret=(1+n)*n/2;}}ntmain{printf("%d\n",sum1(100));printf("%d\n",sum2(100));printf("%d\n",sum3(100));}intfunc(inta[],intlen){jsfor(i=0;i<len;i++)n{for(j=0;j<len;j++)n{s+=i*j;//n*n}}s}//n*n輕松入門實戰(zhàn)應(yīng)用注意注意1：判斷一個算法的效率時，往往只需要關(guān)注操作數(shù)量的最高次項，其它次要項和常數(shù)特殊說明時，我們所分析的算法的時間復(fù)雜度都是指最壞時間復(fù)雜度。算算法效率嚴(yán)重依賴于操作(Operation)數(shù)量在判斷時首先關(guān)注操作數(shù)量的最高次項操作數(shù)量的估算可以作為時間復(fù)雜度的估算O(5)=O(1)O(2n+1)=O(2n)=O(n)O(n2+n+1)=O(n2)O(3n3+1)=O(3n3)=O(n3)常見時間復(fù)雜度輕松入門實戰(zhàn)應(yīng)用3、算法的空間復(fù)雜度算法的空間復(fù)雜度通過計算算法的存儲空間實現(xiàn)S(n)=O(f(n))n大O表示法同樣適用于算法的空間復(fù)雜度當(dāng)算法執(zhí)行時所需要的空間是常數(shù)時，空間復(fù)雜度為O(1)空間與時間的策略多數(shù)情況下，算法執(zhí)行時所用的時間更令人關(guān)注如果有必要，可以通過增加空間復(fù)雜度來降低時間復(fù)雜度同理，也可以通過增加時間復(fù)雜度來降低空間復(fù)雜度O(4n+12)O(8)=O(1)O(4)=O(1)總結(jié)：實現(xiàn)算法時，需要分析具體問題，對執(zhí)行時間和空間的要求。/*設(shè)計一個算法，找出出現(xiàn)次數(shù)最多的數(shù)字。排序，然后找出出現(xiàn)次數(shù)最多的數(shù)字voidsearch(inta[],intlen){intsp[1000]={0};intmax0;for(i=0;i<len;i++){intindex=a[i]-1;sp[index]++;}for(i=0;i<1000;i++){if(max<sp[i])輕松入門實戰(zhàn)應(yīng)用{axspi}}for(i=0;i<1000;i++){if(max==sp[i]){printf("%d\n",i+1);}}}ntmain{intarray[]={1,1,3,4,5,6,6,6,2,3};arraysizeofarraysizeofarray}把每個數(shù)字出現(xiàn)的次數(shù)的中間結(jié)果，緩存下來；在緩存的結(jié)果中求最大值。輕松入門實戰(zhàn)應(yīng)用2.1線性表基本概念2.1.1線性表定義線性表(List)是零個或多個數(shù)據(jù)元素的集合線性表中的數(shù)據(jù)元素之間是有順序的線性表中的數(shù)據(jù)元素個數(shù)是有限的線性表中的數(shù)據(jù)元素的類型必須相同2.1.2數(shù)學(xué)定義線性表是具有相同類型的n(≥0)個數(shù)據(jù)元素的有限序列(a1,a2,…,an)2.1.3性質(zhì)a0為線性表的第一個元素，只有一個后繼an為線性表的最后一個元素，只有一個前驅(qū)線性表能夠逐項訪問和順序存取2.1.4練習(xí)下面的關(guān)系中可以用線性表描述的是A.班級中同學(xué)的友誼關(guān)系N:NB.公司中的上下級關(guān)系1:NC.冬天圖書館排隊占座關(guān)系D.花名冊上名字之間的關(guān)系1::1輕松入門實戰(zhàn)應(yīng)用2.2.5線性表的操作創(chuàng)建線性表銷毀線性表清空線性表將元素插入線性表將元素從線性表中刪除獲取線性表中某個位置的元素獲取線性表的長度線性表在程序中表現(xiàn)為一種特殊的數(shù)據(jù)類型線性表的操作在程序中的表現(xiàn)為一組函數(shù)C語言描述=====》線性表的設(shè)計與實現(xiàn)人生財富庫積累#ifndef_WBM_LIST_H_#define_WBM_LIST_H_typedefvoidList;typedefvoidListNode;//創(chuàng)建并且返回一個空的線性表istListCreatevoidList_Destroy(List*list);//將一個線性表list中的所有元素清空,線性表回到創(chuàng)建時的初始狀態(tài)voidList_Clear(List*list);//返回一個線性表list中的所有元素個數(shù)intList_Length(List*list);intList_Insert(List*list,ListNode*node,intpos);ListNode*List_Get(List*list,intpos);ListNode*List_Delete(List*list,intpos);#endif鏈表順序存儲插入算法和刪除算法輕松入門實戰(zhàn)應(yīng)用注意:intList_Insert(List*list,ListNode*node,intpos);(重點(diǎn):分離思想)2.2線性表的順序存儲結(jié)構(gòu)2.2.1基本概念2.2.2設(shè)計與實現(xiàn)插入元素算插入元素算法判斷線性表是否合法判斷插入位置是否合法把最后一個元素到插入位置的元素后移一個位置將新元素插入獲取元素操作判斷線性表是否合法判斷位置是否合法直接通過數(shù)組下標(biāo)的方式獲取元素刪除元素算法判斷線性表是否合法判斷刪除位置是否合法將元素取出將刪除位置后的元素分別向前移動一個位置輕松入門實戰(zhàn)應(yīng)用2.2.3優(yōu)點(diǎn)和缺點(diǎn)無需為線性表中的邏輯關(guān)系增加額外的空間可以快速的獲取表中合法位置的元素插入和刪除操作需要移動大量元素當(dāng)線性表長度變化較大時難以確定存儲空間的容量2.3線性表的鏈?zhǔn)酱鎯?.3.1基本概念鏈?zhǔn)酱鎯Χx存儲本身的信息外，還需要存儲指示其直接后繼的信息。輕松入門實戰(zhàn)應(yīng)用表頭結(jié)點(diǎn)鏈表中的第一個結(jié)點(diǎn)，包含指向第一個數(shù)據(jù)元素的指針以及鏈表自身的一些信息數(shù)據(jù)結(jié)點(diǎn)鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，包含指向下一個數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息尾結(jié)點(diǎn)鏈表中的最后一個數(shù)據(jù)結(jié)點(diǎn)，其下一元素指針為空，表示無后繼。2.3.2鏈表技術(shù)領(lǐng)域推演輕松入門實戰(zhàn)應(yīng)用2.3.2設(shè)計與實現(xiàn)鏈表鏈?zhǔn)酱鎯api實現(xiàn)分析在C語言中可以用結(jié)構(gòu)體來定義鏈表中的指針域鏈表中的表頭結(jié)點(diǎn)也可以用結(jié)構(gòu)體實現(xiàn)返回鏈表中第3個位置處，元素的值LinkListNodeLinkListGetLinkListlistintpos){TLinkListtList(TLinkList*)list;kListNodecurrentNULL重要技術(shù)場景圖輕松入門實戰(zhàn)應(yīng)用nkListNoderetNULL{NULL}ListNodetListforiipos;i++){rrentnext}retcurrent>next;returnret;}返回第三個位置的答案：指向位置2，所以需要返回ret=current->next;所以如果想返回位置n的元素的值，需要怎么做ret=current->next;刪除元素輕松入門實戰(zhàn)應(yīng)用表鏈?zhǔn)酱鎯插入表鏈?zhǔn)酱鎯刪除2.3.3優(yōu)點(diǎn)和缺點(diǎn)無需一次性定制鏈表的容量輕松入門實戰(zhàn)應(yīng)用插入和刪除操作無需移動數(shù)據(jù)元素數(shù)據(jù)元素必須保存后繼元素的位置信息獲取指定數(shù)據(jù)的元素操作需要順序訪問之前的元素2.4循環(huán)鏈表2.4.1基本概念循環(huán)鏈表的定義：將單鏈表中最后一個數(shù)據(jù)元素的next指針指向第一個元素循環(huán)循環(huán)鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長度清空鏈表循環(huán)鏈表新操作將游標(biāo)重置指向鏈表中的第一個數(shù)據(jù)元素CircleListNode*CircleList_Reset(CircleList*list);獲取當(dāng)前游標(biāo)指向的數(shù)據(jù)元素CircleListNode*CircleList_Current(CircleList*list);輕松入門實戰(zhàn)應(yīng)用將游標(biāo)移動指向到鏈表中的下一個數(shù)據(jù)元素CircleListNode*CircleList_Next(CircleList*list);直接指定刪除鏈表中的某個數(shù)據(jù)元素CircleListNode*CircleList_DeleteNode(CircleList*list,CircleListNode*node);//根據(jù)元素的值刪除元素pk根據(jù)元素的位置刪除元素2.4.2循環(huán)鏈表的應(yīng)用證明循環(huán)鏈表約瑟夫問題求解約瑟約瑟夫問題-循環(huán)鏈表典型應(yīng)用令其出列。然后再從下一個人開始從1順時針報數(shù)，報到第m個人，再令其出列，…，此下去，求出列順序。大話數(shù)據(jù)結(jié)構(gòu)3.16結(jié)尾：寫書的人，也很累；臨界點(diǎn)輕松入門實戰(zhàn)應(yīng)用2.4.3設(shè)計與實現(xiàn)循環(huán)鏈表插入元素的分析1)普通插入元素(和單鏈表是一樣的)2)尾插法(和單鏈表是一樣的，單鏈表的寫法支持尾插法；length次，指向最后面那個元素)CircleList_Insert(list,(CircleListNode*)&v1,CircleList_Length(list));CircleListInsertlistCircleListNodevCircleListLength(list));3)頭插法(要進(jìn)行頭插法，需要求出尾結(jié)點(diǎn)，和單鏈表不一樣的地方，保證是循環(huán)鏈表)第一次插入元素時，讓游標(biāo)指向0號結(jié)點(diǎn)輕松入門實戰(zhàn)應(yīng)用CircleListInsertlistCircleListNode)&v1,0);CircleListInsertlistCircleListNode)&v1,0);循環(huán)鏈表插入綜合場景分析圖輕松入門實戰(zhàn)應(yīng)用循環(huán)鏈表刪除結(jié)點(diǎn)分析2、刪除頭結(jié)點(diǎn)(刪除0號位置處元素)，需要求出尾結(jié)點(diǎn)2.4.4優(yōu)點(diǎn)和缺點(diǎn)循環(huán)鏈表只是在單鏈表的基礎(chǔ)上做了一個加強(qiáng)循環(huán)鏈表可以完全取代單鏈表的使用NextCurrent可以高效的遍歷鏈表中的所有元素代碼復(fù)雜度提高了大話數(shù)據(jù)結(jié)構(gòu)3.16結(jié)尾：寫書的人，也很累；臨界點(diǎn)2.5雙向鏈表2.5.1基本概念單鏈表單鏈表的結(jié)點(diǎn)都只有一個指向下一個結(jié)點(diǎn)的指針單鏈表的數(shù)據(jù)元素?zé)o法直接訪問其前驅(qū)元素逆序訪問單鏈表中的元素是極其耗時的操作！len=LinkList_Length(list);for(i=len-1;len>=0;i++)//O(n){LinkListNode*p=LinkList_Get(list,i);//O(n)問數(shù)據(jù)元素p中的元素輕松入門實戰(zhàn)應(yīng)用///}雙向鏈表的定義在單鏈表的結(jié)點(diǎn)中增加一個指向其前驅(qū)的pre指針雙向鏈表擁有單鏈表的所有操作創(chuàng)建鏈表銷毀鏈表獲取鏈表長度清空鏈表2.5.2設(shè)計與實現(xiàn)一般操作插入操作插入操作輕松入門實戰(zhàn)應(yīng)用插入操作異常處理插入第一個元素異常處理刪除操作刪除操作異常處理雙向鏈表的新操作獲取當(dāng)前游標(biāo)指向的數(shù)據(jù)元素將游標(biāo)重置指向鏈表中的第一個數(shù)據(jù)元素將游標(biāo)移動指向到鏈表中的下一個數(shù)據(jù)元素將游標(biāo)移動指向到鏈表中的上一個數(shù)據(jù)元素輕松入門實戰(zhàn)應(yīng)用直接直接指定刪除鏈表中的某個數(shù)據(jù)元素DLinkListNode*DLinkList_DeleteNode(DLinkList*list,DLinkListNode*node);DLinkListNode*DLinkList_Reset(DLinkList*list);DLinkListNode*DLinkList_Current(DLinkList*list);DLinkListNode*DLinkList_Next(DLinkList*list);DLinkListNode*DLinkList_Pre(DLinkList*list);//大家一定要注意：教科書不會告訴你項目上如何用；哪些點(diǎn)是項目的重點(diǎn)；做一個企業(yè)級的財富庫，完成你人生開發(fā)經(jīng)驗的積累，是我們的學(xué)習(xí)重點(diǎn)，要注意！雙向鏈表重要技術(shù)場景循環(huán)鏈表插入結(jié)點(diǎn)技術(shù)場景輕松入門實戰(zhàn)應(yīng)用循環(huán)鏈表刪除結(jié)點(diǎn)技術(shù)場景2.5.3優(yōu)點(diǎn)和缺點(diǎn)優(yōu)點(diǎn)：雙向鏈表在單鏈表的基礎(chǔ)上增加了指向前驅(qū)的指優(yōu)點(diǎn)：雙向鏈表在單鏈表的基礎(chǔ)上增加了指向前驅(qū)的指針功能上雙向鏈表可以完全取代單鏈表的使用缺點(diǎn)：代碼復(fù)雜3.1.1Stack基本概念棧是一種特殊的線性表棧僅能在線性表的一端進(jìn)行操作棧頂(Top)：允許操作的一端棧底(Bottom)：不允許操作的一端輕松入門實戰(zhàn)應(yīng)用3.1.2Stack的常用操作創(chuàng)建棧銷毀棧清空棧進(jìn)棧獲取棧頂元素獲取棧的大小CC語言描述=====》棧的設(shè)計與實現(xiàn)人生財富庫積累defMYSTACKHineMYSTACKHackckCreateoidStackDestroyStackstackvoidStackClearStackstack;stackvoiditem輕松入門實戰(zhàn)應(yīng)用voidvoidStackPopStackstack);voidStackTopStackstack);ndifMYSTACKH3.1.3棧模型和鏈表模型關(guān)系分析輕松入門實戰(zhàn)應(yīng)用3.1.4棧的順序存儲設(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*list);intSeqStack_Insert(SeqStack*list,SeqListNode*node,intpos);SeqListNode*SeqList_Get(SeqList*list,intpos);SeqListNode*SeqList_Delete(SeqList*list,intpos);輕松入門實戰(zhàn)應(yīng)用##endif//__MY_SEQLIST_H__3.1.5棧的鏈?zhǔn)酱鎯υO(shè)計與實現(xiàn)頭文件#ifndef_MY_LINKSTACK_H_#define_MY_LINKSTACK_H_typedefvoidLinkStack;LinkStack*LinkStack_Create();voidLinkStack_Destroy(LinkStack*stack);輕松入門實戰(zhàn)應(yīng)用voidLinkStack_Clear(LinkStack*stack);intLinkStack_Push(LinkStack*stack,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)用幾乎所有的編譯器都具有檢測括號是否匹配的能力算法思路從第一個字符開始掃描當(dāng)遇見左符號時壓入棧中當(dāng)遇見右符號時從棧中彈出棧頂符號，并進(jìn)行匹配匹配成功：繼續(xù)讀入下一個字符匹配失敗：立即停止，并報錯成功:所有字符掃描完畢，且棧為空失?。浩ヅ涫』蛩凶址麙呙柰戤叺珬７强债?dāng)需要檢測成對出現(xiàn)但又互不相鄰的事物時可以使用?！昂筮M(jìn)先出”的特性棧非常適合于需要“就近匹配”的場合以讀入字符串“9+(3-1)*5+8/2”并計算值嗎？輕松入門實戰(zhàn)應(yīng)用計算機(jī)的本質(zhì)工作就是做數(shù)學(xué)運(yùn)算，那計算機(jī)可以讀入字符串運(yùn)算符放在數(shù)字后面的后綴表達(dá)式對應(yīng)的，我們習(xí)慣的數(shù)學(xué)表達(dá)式叫做中綴表達(dá)式===》符合人類思考習(xí)慣5+4=>54+1+2*3=>123*+8+(31)*5=>8315*+中綴表達(dá)式符合人類的閱讀和思維習(xí)慣后綴表達(dá)式符合計算機(jī)的“運(yùn)算習(xí)慣”遍歷中綴表達(dá)式中的數(shù)字和符號對于數(shù)字：直接輸出左括號：進(jìn)棧運(yùn)算符號：與棧頂符號進(jìn)行優(yōu)先級比較若棧頂符號優(yōu)先級不低：將棧頂符號彈出并輸出，之后進(jìn)棧右括號：將棧頂符號彈出并輸出，直到匹配左括號遍歷結(jié)束：將棧中的所有符號彈出并輸出輕松入門實戰(zhàn)應(yīng)用8315*+遍歷后綴表達(dá)式中的數(shù)字和符號對于數(shù)字：進(jìn)棧從棧中彈出右操作數(shù)從棧中彈出左操作數(shù)根據(jù)符號進(jìn)行運(yùn)算將運(yùn)算結(jié)果壓入棧中遍歷結(jié)束：棧中的唯一數(shù)字為計算結(jié)果隊列是一種特殊的線性表輕松入門實戰(zhàn)應(yīng)用中綴表達(dá)式是人習(xí)慣的表達(dá)方式后綴表達(dá)式是計算機(jī)喜歡的表達(dá)方式通過?？梢苑奖愕膶⒅芯Y形式變換為后綴形式中綴表達(dá)式的計算過程類似程序編譯運(yùn)行的過程擴(kuò)展：給你一個字符串，計算結(jié)果1+2*(66/(2*3)+7)1字符串解析詞法語法分析優(yōu)先級分析3.2.1queue基本概念輕松入門實戰(zhàn)應(yīng)用隊列僅在線性表的兩端進(jìn)行操作隊頭(Front)：取出數(shù)據(jù)元素的一端隊尾(Rear)：插入數(shù)據(jù)元素的一端列不允許在中間部位進(jìn)行操作！3.2.2queue常用操作銷毀隊列清空隊列進(jìn)隊列獲取隊頭元素獲取隊列的長度C語言描述=====》隊列的設(shè)計與實現(xiàn)人生財富庫積累efMYQUEUEHneMYQUEUEHeeQueueCreatedQueueDestroyQueuequeue輕松入門實戰(zhàn)應(yīng)用voidvoidQueueClearQueuequeueeuequeuevoiditemoidQueueRetrieveQueuequeueidQueueHeaderQueuequeuendifMYQUEUEH3.2.3隊列模型和鏈表模型關(guān)系分析3.2.4隊列的順序存儲設(shè)計與實現(xiàn)隊列也是一種特殊的線性表；可以用線性表順序存儲來模擬隊列。輕松入門實戰(zhàn)應(yīng)用2設(shè)計與實現(xiàn)##ifndef_MY_SEQQUEUE_H_#define_MY_SEQQUEUE_H_typedefvoidSeqQueue;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*queue);#endif//_MY_SEQQUEUE_H_3.2.5隊列的鏈?zhǔn)酱鎯υO(shè)計與實現(xiàn)隊列也是一種特殊的線性表；可以用線性表鏈?zhǔn)酱鎯砟M隊列的鏈?zhǔn)酱鎯Α?設(shè)計與實現(xiàn)##ifndef_MY_LINKQUEUE_H_#define_MY_LINKQUEUE_H_typedefvoidLinkQueue;LinkQueue*LinkQueue_Create();輕松入門實戰(zhàn)應(yīng)用voidLinkQueue_Destroy(LinkQueue*queue);voidLinkQueue_Clear(LinkQueue*queue);intLinkQueue_Append(LinkQueue*queue,void*item);void*LinkQueue_Retrieve(LinkQueue*queue);void*LinkQueue_Header(LinkQueue*queue);intLinkQueue_Length(LinkQueue*queue);#endif//_MY_LINKQUEUE_H_4、樹專題4.1樹基本概念非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼(1:n)1)具有遞歸性，即樹中還有樹m的集合葉子森林孩子兄弟堂兄弟祖先子孫次終端結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度所有結(jié)點(diǎn)度中的最大值(Max{各結(jié)點(diǎn)的度}樹的深度指所有結(jié)點(diǎn)中最大的層數(shù)(Max{各結(jié)點(diǎn)的層次}4.2樹的表示法廣義表表示法左孩子－右兄弟表示法雙親孩子表示法輕松入門實戰(zhàn)應(yīng)用4.3樹的邏輯結(jié)構(gòu)一對多(1:n)，有多個直接后繼(如家譜樹、目錄樹等等)，但只有一個根結(jié)點(diǎn)，且子樹之廣義表表示法左孩子－右兄弟表示法4.4二叉樹概念4.4.1基本概念二二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性定義：是n(n≥0)個結(jié)點(diǎn)的有限集合，由一個根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成二叉樹性質(zhì)性質(zhì)1:在二叉樹的第i層上至多有2i-1個結(jié)點(diǎn)(i>0)性質(zhì)2:深度為k的二叉樹至多有2k-1個結(jié)點(diǎn)(k>0)nnn＋1(即n=n+1)(特點(diǎn)：每層都“充滿”了結(jié)點(diǎn))理解：(k-1層與滿二叉樹完全相同，第k層結(jié)點(diǎn)盡力靠左)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：[數(shù)據(jù)結(jié)構(gòu)(C語言版)].嚴(yán)蔚敏_吳偉民.掃描版.pdfp124數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)：[數(shù)據(jù)結(jié)構(gòu)(C語言版)].嚴(yán)蔚敏_吳偉民.掃描版.pdfp12720202輕松入門實戰(zhàn)應(yīng)用性質(zhì)5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結(jié)點(diǎn)，其左孩子編號必二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)自上而下、從左至右編號，用一組連續(xù)的存儲單元存儲。答：一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上虛結(jié)點(diǎn)，其內(nèi)容為空二、鏈?zhǔn)酱鎯Y(jié)構(gòu)24.4.2二叉樹的表示二叉樹表示法P127頁/*typedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;BiTNodeBiTree;structBiTNode{intdata;structBiTNode*lchild,*rchild;typedefstructBPTree輕松入門實戰(zhàn)應(yīng)用typedefstructBiTNodeBiTNode;typedefstructBiTNode*BiTree;樹的三叉鏈表表示//三叉鏈表typedefstructTriTNode{//左右孩子指針structTriTNode*lchild,*rchild;structTriTNode*parent;e雙親鏈表法//雙親鏈表#defineMAX_TREE_SIZE100typedefstructBPTNode{intparentPosition;//指向雙親的指針//數(shù)組下標(biāo)charLRTag;//左右孩子標(biāo)志域}BPTNode;輕松入門實戰(zhàn)應(yīng)用{BPTNodenodes[100];//因為節(jié)點(diǎn)之間是分散的，需要把節(jié)點(diǎn)存儲到數(shù)組中intnum_node;//節(jié)點(diǎn)數(shù)目introot;//根結(jié)點(diǎn)的位置//注意此域存儲的是父親節(jié)點(diǎn)在數(shù)組的下標(biāo)4.4.3二叉樹的遍歷樹的遍歷本質(zhì)剖樹的遍歷本質(zhì)剖析輕松入門實戰(zhàn)應(yīng)用4.5二叉樹編程實踐基本操作typedeftypedefstructnode{intdata;structnode*lchild,*rchild；}NODE;NODErootDLR(NODE*root){if(root)//非空二叉樹{DLR(root->lchild);//遞歸遍歷左子樹DLR(root->rchild);//遞歸遍歷右子樹}}LDR(NODE*root)輕松入門實戰(zhàn)應(yīng)用{{if(root!=NULL){LDR(root->lchild);printf(“%d”,rata);LDR(root->rchild);}}后序遍歷算法LRD(NODE*root){if(root!=NULL){LRD(root->lchild);LRDrootrchild;printf(“%d”,rata);}}intsum=0;//全局變量DLR_CountLeafNum(NODE*root)//采用中序遍歷的遞歸算法{if(root)//非空二叉樹條件，還可寫成if(root!=NULL){if(!root->lchild&&!root->rchild)//是葉子結(jié)點(diǎn)則統(tǒng)計并打印{sum++;printf("%d\n",root->data);}DLR_CountLeafNum(root->lchild);//遞歸遍歷左子樹，直到葉子處；DLR_CountLeafNum(root->rchild);}//遞歸遍歷右子樹，直到葉子處；}return(0);}思想：1)求根結(jié)點(diǎn)左子樹的葉子結(jié)點(diǎn)個數(shù)，累計到sum中，求根結(jié)點(diǎn)右子樹的葉子結(jié)點(diǎn)2)若左子樹還是樹，重復(fù)步驟1；若右子樹還是樹，重復(fù)步驟1。3)全局變量轉(zhuǎn)成函數(shù)參數(shù)4)按照先序、中序、后序方式計算葉子結(jié)點(diǎn)，同。思想：1)求根結(jié)點(diǎn)左子樹高度，根結(jié)點(diǎn)右子樹高度，比較的子樹最大高度，再+1。2)若左子樹還是樹，重復(fù)步驟1；若右子樹還是樹，重復(fù)步驟1。2)拷貝左子樹，拷貝右子樹，讓新結(jié)點(diǎn)連接左子樹，右子樹輕松入門實戰(zhàn)應(yīng)用3)若左子樹還是樹，重復(fù)步驟1、2；若右子樹還是樹，重復(fù)步驟1、2。案例4：樹的非遞歸遍歷(中序遍歷)中序遍歷的幾種情況分析1：什么時候訪問根、什么時候訪問左子樹、什么訪問右子樹當(dāng)左子樹為空或者左子樹已經(jīng)訪問完畢以后，再訪問根訪問完畢根以后，再訪問右子樹。分析2：非遞歸遍歷樹，訪問結(jié)點(diǎn)時，為什么是棧，而不是其他模型(比如說是隊列)。先走到的后訪問、后走到的先訪問，顯然是棧結(jié)構(gòu)樹，該結(jié)點(diǎn)入棧；如果結(jié)點(diǎn)沒有左子樹，訪問該結(jié)點(diǎn)；如果結(jié)點(diǎn)沒有右子樹(結(jié)點(diǎn)訪問完畢)，根據(jù)棧頂指示回退，訪問棧頂元素，并訪如果棧為空，表示遍歷結(jié)束。注意：入棧的結(jié)點(diǎn)表示，本身沒有被訪問過，同時右子樹也沒有被訪問過。分析4：有一個一直往左走入棧的操作，中序遍歷的起點(diǎn)輕松入門實戰(zhàn)應(yīng)用作業(yè)：自己編寫堆棧函數(shù)原型，實現(xiàn)中序遍歷非遞歸算作業(yè)：自己編寫堆棧函數(shù)原型，實現(xiàn)中序遍歷非遞歸算法4.6二叉樹的創(chuàng)建4.6.1中序和先序創(chuàng)建樹請思考，會有多少種形狀。輕松入門實戰(zhàn)應(yīng)用通過中序遍歷和后續(xù)遍歷可以確定一個樹通過先序遍歷和后序遍歷確定不了一個樹。單獨(dú)先序遍歷：能求解根，但不能求解左子樹什么時候結(jié)束、右子樹什么時候開始。3、根據(jù)先序和中序結(jié)果畫樹1、通過先序遍歷找到根結(jié)點(diǎn)A，再通過A在中序遍歷的位置找出左子樹，右子樹2、在A的左子樹中，找左子樹的根結(jié)點(diǎn)(在先序中找)，轉(zhuǎn)步驟13、在A的右子樹中，找右子樹的根結(jié)點(diǎn)(在先序中找)，轉(zhuǎn)步驟14、學(xué)習(xí)算法可借助工具、動畫4.6.2#號法創(chuàng)建樹1、什么是#號法創(chuàng)建樹#創(chuàng)建樹，讓樹的每一個節(jié)點(diǎn)都變成度數(shù)為2的樹輕松入門實戰(zhàn)應(yīng)用2#創(chuàng)建樹練習(xí)要清楚的確定左子樹什么結(jié)束，右子樹什么時候開始。利用前序遍歷來建樹(結(jié)點(diǎn)值陸續(xù)從鍵盤輸入，用DLR為宜)ateBTpre{charch;scanf(“%c”,&ch);if(ch==’#’)T=NULL;{T=(Bintree)malloc(sizeof(BinTNode));輕松入門實戰(zhàn)應(yīng)用T->data=ch;T->lchild=createBTpre();Trchild=createBTpre();}}//后序遍歷銷毀一個樹voidBiTree_Free(BiTNode*T){BiTNode*tmp=NULL;if(T!=NULL){if(T->rchild!=NULL)BiTree_Free(T->rchild);if(T->lchild!=NULL)BiTree_Free(T->lchild);if(T!=NULL){free(T);T=NULL;}}}4.7二叉線索樹4.7.1線索化概念藤摸個樹了。輕松入門實戰(zhàn)應(yīng)用中序遍歷這棵樹===》轉(zhuǎn)換成鏈表訪問2線索化思想輕松入門實戰(zhàn)應(yīng)用結(jié)論：線索化過程就是在遍歷過程(假設(shè)是中序遍歷)中修改空指針的過程：輕松入門實戰(zhàn)應(yīng)用3線索化思想訓(xùn)練1)右空指針線索化：2)左空指針線索化3)總結(jié)輕松入門實戰(zhàn)應(yīng)用4.7.2線索化的實現(xiàn)1)線索化樹結(jié)點(diǎn)typedefstructBiThrNode/*二叉線索存儲結(jié)點(diǎn)結(jié)構(gòu)*/{chardata;/*結(jié)點(diǎn)數(shù)據(jù)*/structBiThrNode*lchild,*rchild;/*左右孩子指針*/intRTag;/*左右標(biāo)志*/}BiThrNode,*BiThrTree;2)線索化思想分析線索化的本質(zhì)：讓前后結(jié)點(diǎn)，建立關(guān)系；1)兩個輔助指針變量形成差值后：后繼結(jié)點(diǎn)的左孩子指向前驅(qū)結(jié)點(diǎn)，前驅(qū)結(jié)點(diǎn)的右孩子指輕松入門實戰(zhàn)應(yīng)用2)賦值指針變量和業(yè)務(wù)操作的邏輯關(guān)系4)二叉樹線索化樹的遍歷/*中序遍歷二叉線索樹T(頭結(jié)點(diǎn))的非遞歸算法*/intInOrderTraverse_Thr(BiThrNode*T){BiThrNode*p;輕松入門實戰(zhàn)應(yīng)用p=T->lchild;/*p指向根結(jié)點(diǎn)*/while(p!=T){/*空樹或遍歷結(jié)束時,p==T*/whilepLTag==Link)p=p->lchild;printf("%c",p->data);while(p->RTag==Thread&&p->rchild!=T){pp->rchild;printf("%c",p->data);}pprchild;}}4.8霍夫曼樹4.8.1概念組建一個網(wǎng)絡(luò)，耗費(fèi)最小WPL最小；這個方法是霍夫曼想出來的，稱為霍夫曼樹輕松入門實戰(zhàn)應(yīng)用4.8.2霍夫曼樹的構(gòu)造對于文本”對于文本”BADCADFEED”的傳輸而言，因為重復(fù)出現(xiàn)的只有輕松入門實戰(zhàn)應(yīng)用在戰(zhàn)爭年代，這種編碼方式對于情報的發(fā)送和接受是很低效且容易出錯的。要提高效率，必然要從編碼方式的改進(jìn)入手，要避免每個字符都占用相同的bit位準(zhǔn)則：任一字符的編碼都不是另一個字符編碼的前綴！也就是說：每一個字符的編碼路徑，都不包含另外一個字符的路徑?；舴蚵鼧?.給定n個數(shù)值{v1,v2,…,vn}