《C#數(shù)據(jù)結(jié)構(gòu)》PPT課件VIP

數(shù)據(jù)：描述客觀事物的信息（數(shù)，字符，符號等）的集合，是程序處理的對象。,數(shù)據(jù)結(jié)構(gòu)基本概念,數(shù)據(jù)元素：是數(shù)據(jù)集合中的個體，是構(gòu)成數(shù)據(jù)對象的基本單位，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。,數(shù)據(jù)項：是數(shù)據(jù)的最小單位。一組數(shù)據(jù)元素具有某種結(jié)構(gòu)形式。,對象,對象的屬性,數(shù)據(jù)結(jié)構(gòu)定義,數(shù)據(jù)結(jié)構(gòu)：描述了一組性質(zhì)相同的數(shù)據(jù)元素及元素間的相互關(guān)系。,都是學(xué)生,D:一幫學(xué)生,R:按學(xué)號排序,數(shù)據(jù)結(jié)構(gòu)概念的三要素定義,數(shù)據(jù)元素之間的邏輯關(guān)系,數(shù)據(jù)元素在計算機中的存儲方式,在這些數(shù)據(jù)元素上定義的運算的集合,數(shù)據(jù)結(jié)構(gòu)的基本分類,兩大類：(一)線性結(jié)構(gòu)（線性表）數(shù)據(jù)元素之間的邏輯關(guān)系可以用一個線性序列簡單地表示出來。線性表是典型的線性結(jié)構(gòu)，它的數(shù)據(jù)元素只按先后次序聯(lián)接。表、棧、隊列、字串、數(shù)組和文件等方式。,(二）非線性結(jié)構(gòu)（樹，圖）不滿足線性結(jié)構(gòu)特點的數(shù)據(jù)結(jié)構(gòu)稱為非線性結(jié)構(gòu)。樹、圖等是非線性結(jié)構(gòu)。樹中的數(shù)據(jù)元素是分層次的縱向聯(lián)接。圖中的數(shù)據(jù)元素則有各種各樣復(fù)雜聯(lián)接。其它種類的數(shù)據(jù)結(jié)構(gòu)由這三種基本結(jié)構(gòu)派生的。,數(shù)據(jù)存儲結(jié)構(gòu)的基本方式,最常用的二種方式是：順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)。,數(shù)據(jù)元素按某種順序存放在存儲器的連續(xù)存儲單元中。邏輯相鄰，物理上相鄰，數(shù)據(jù)元素之間的關(guān)系由存儲單元的鄰接關(guān)系唯一確定。例如數(shù)組就是這種存儲方式,順序存儲結(jié)構(gòu),學(xué)生名單(邏輯結(jié)構(gòu))順序物理結(jié)構(gòu)(數(shù)組student),順序存儲結(jié)構(gòu)特點,結(jié)點中只有自身信息域，沒有連接信息域。存儲密度大，存儲空間利用率高；,可以通過計算直接確定數(shù)據(jù)結(jié)構(gòu)中第i個結(jié)點的存儲地址。即可以對記錄直接進行存??；,插入、刪除運算會引起大量結(jié)點的移動；,要求存儲在一片連續(xù)的地址中。,這種存儲方式主要用于線性的數(shù)據(jù)結(jié)構(gòu)。,存儲數(shù)據(jù)結(jié)構(gòu)的內(nèi)存空間可以不連續(xù)，數(shù)據(jù)元素之間的關(guān)系由指針來確定。,鏈式存儲結(jié)構(gòu),主要特點是：結(jié)點由兩類域組成：數(shù)據(jù)域和指針域。,鏈式存儲結(jié)構(gòu)特點,邏輯上相鄰的結(jié)點物理上不必鄰接，既可實現(xiàn)線性數(shù)據(jù)結(jié)構(gòu)，又可用于表示非線性數(shù)據(jù)結(jié)構(gòu)。,插入，刪除操作靈活方便，不必移動結(jié)點，只要改變結(jié)點中的指針值即可。,特點：表中的每個元素呈線性關(guān)系，除第一個外，都有一個直接前趨(predecessor)，除最后一個元素外，都僅有一個后繼(successor)。,線性表最簡單，最常用的數(shù)據(jù)結(jié)構(gòu),線性表的邏輯結(jié)構(gòu)線性表L用符號表示為：L=(a1，a2，a3，.ai.，an),線性表的存儲結(jié)構(gòu),存儲結(jié)構(gòu):順序存儲結(jié)構(gòu)和鏈接存儲結(jié)構(gòu)。,具有順序存儲結(jié)構(gòu)的線性表稱為順序表用數(shù)組儲線性表中的每個數(shù)據(jù)元素。,具有鏈接存儲結(jié)構(gòu)的線性表稱為線性鏈表。用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。通常亦稱為鏈表。常用的鏈表有單鏈表、循環(huán)鏈表和雙向鏈表。,順序表類設(shè)計分析,對象的屬性：自己現(xiàn)有的數(shù)據(jù)：存放在一個數(shù)組中現(xiàn)有數(shù)據(jù)的個數(shù)：長度能存放多少數(shù)據(jù)：容量,動作(Method)構(gòu)造方法：傳遞表的容量，創(chuàng)建一個空表，有效長度=0插入：新數(shù)據(jù)插入后，數(shù)據(jù)還是有序的，長度增1增加：在表的尾部增加一個數(shù)據(jù)，長度增1查找：根據(jù)鍵值，找到數(shù)據(jù)在表中的位置，并返回，找不到返回-1更新：用指定的值更新表中指定位置的元素的值排序：將表中元素按從小到大排序。獲得某位置元素的值：獲得線性表的長度,類型dataintlengthIntvolume,?能為每個方法作定義嗎？名字，形參表，返回類型,確定表中的元素,publicclassStudentpublicstringno,name;publicdoublemath,eng,computer;publicStudent().,?這個類有點怪，屬性都是public沒其他方法,這種類稱為數(shù)據(jù)類,去重,返回類型問題,是重新生成一個？還是直接刪除,應(yīng)該是：ArrayList,應(yīng)該是：重新生成一個不破壞原來的數(shù)據(jù),去重的思維,你是怎么思維的？,擴展思維,數(shù)據(jù)不斷添加，順序表滿了后，能否自動長大？,原來,變更后，原來的2倍,Studentdata,Studenttemp,length?volume?,for()tempi=datai,單鏈表線性表的另一種存儲方式,一鏈表的基本組成元素,由表頭指針決定通過移動指針遍歷鏈表，遇到null結(jié)束組成要素：節(jié)點，節(jié)點中包含數(shù)據(jù)鏈表的屬性定義：,null,單鏈表,一鏈表的基本組成元素節(jié)點,publicclassNode/定義節(jié)點類publicintdata;publicNodenext;publicNode(inti)data=i;next=null;,鏈表的逆轉(zhuǎn),先生成一個空新鏈表遍歷原鏈表每取一個節(jié)點，向新表的表頭插入新節(jié)點直到原表遍歷結(jié)束,去重的原理,生成一個新鏈表遍歷原表，每取一個節(jié)點，判斷它在新表中是否存在，如果重復(fù)就不加。直到原表結(jié)束,限定在一端進行插入與刪除的線性表。允許操作的一端稱為棧頂，而不允許操作的一端為棧底。給定棧(a1,an-1）稱a1為棧底元素，an為棧頂元素。特點后進先出(LIFOLastInFirstOut)或先進后出（FILO)的線性表。元素的插入稱為進棧，元素的刪除稱為出棧。,堆棧及邏輯結(jié)構(gòu),屬性棧頂指針棧的容量,棧的屬性和方法,方法出棧：棧頂元素出棧，指針下移進棧：新元素放棧頂，指針上移判斷?？?用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,順序存儲的棧,指針top指示棧頂元素的位置。,用Volume表示棧的容量,用一維數(shù)組stackvolume表示棧，指針top指向棧頂元素.stack0為最早進入棧的元素，stacktop為最遲進入棧的元素。當top=volume-1時，為滿棧.,初始化top=-1,數(shù)據(jù)元素和棧頂指針之間的對應(yīng)關(guān)系,鏈式存儲的棧,關(guān)鍵點,只需一個屬性，它就是棧頂指針top基本元素與鏈表中的一個節(jié)點一樣，參見Node類定義棧初始化時，讓top指針為null實現(xiàn)其push，pop和isEmpty方法主程序保持順序存儲堆棧的界面和功能,壓棧過程,19,top,2,8,10,node,將新給定值形成節(jié)點將新節(jié)點連接到棧頂,彈出,top,2,8,10,保存棧頂值，棧頂指針指向下一個節(jié)點返回棧頂值,隊列（Queue）操作受限的線性表先進先出(FIFO)的線性表.(a1,a2,an)允許在表的一端插入，在表的另一端刪除，插入的一端叫隊尾（rear），刪除的一端稱隊頭（front）。,隊列,順序存儲隊列,何時滿,順序隊列的屬性,頭、尾、存儲數(shù)據(jù)的數(shù)組。,構(gòu)造函數(shù)：設(shè)置頭、尾，都是0；申請數(shù)據(jù)存儲空間的數(shù)組,隊空front=rear,滿(rear+1)%volume=front進隊rear=(rear+1)%volume;queuerear=x;出列front=(front+1)%volume;x=queuefront,出列，booloutQueue(outintx)/ref關(guān)鍵字為把x的值返回給調(diào)用函數(shù)入列，voidinQueue(intx)判斷隊列是否為空，boolisEmpty(),鏈式隊列,只有append方法的鏈表就是隊列增加一個出列的方法,采用鏈式存儲結(jié)構(gòu)的隊列稱為鏈隊列。一個鏈隊列需要隊頭和隊尾的兩個指針才能唯一確定。,head,tail,二叉樹,定義為：或為空，或由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的二叉樹組成。,二叉樹不是樹的特殊情況。二叉樹的結(jié)點子樹要區(qū)分為左子樹和右子樹，即使在結(jié)點只有一棵子樹的情況下，也要明確指出該子樹是左子樹還是右子樹。二叉樹允許空.而一般的樹至少有一個結(jié)點。,滿二叉樹：深度為K，有2K-1個結(jié)點的二叉樹稱為滿二叉樹。每一層上的結(jié)點數(shù)都是該層上的最大結(jié)點數(shù)。,特殊的二叉樹,特殊的二叉樹,完全二叉樹：樹高為k，除第k層外，其它各層(1k-1)的結(jié)點數(shù)都達到最大個數(shù)，第k層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹如果對一棵高為K,具有n個結(jié)點的完全二叉樹或高為K的滿二叉樹從根結(jié)點開始，從上到下，從左到右進行連續(xù)編號，則位置編號與結(jié)點的編號相同。,第K層少一個,完全二叉樹,二叉樹圖例,滿二叉樹,性質(zhì)1在二叉樹中,第i層最多有2i-1個結(jié)點。i=1性質(zhì)2在深度為K的二叉樹中,結(jié)點總數(shù)最多為2K-1個，K1性質(zhì)3對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2,則n0=n2+1。,二叉樹性質(zhì),推導(dǎo)：設(shè)n1為二叉樹T度為1的結(jié)點數(shù)。因為二叉樹T中結(jié)點的度數(shù)均小于或等于2，所以其結(jié)點總數(shù)為:n=n0+n1+n2(1)設(shè)m為二叉樹T中總的分支數(shù)目。因為除根結(jié)點外，其余結(jié)點都有一個分支進入，所以m=n-1。但這些分支是由度為1或2的結(jié)點射出的，所以m=n1+2n2,于是得n=n1+2n2+1(2)由(1)式和(2)式得n0=n2+1,性質(zhì)4具有n個結(jié)點的完全二叉樹的深度為log2n+1。,性質(zhì)4,推導(dǎo)過程：假設(shè)樹的深度為K。則根據(jù)性質(zhì)2和完全二叉樹的定義，有2K-1-1n2k-1或2K-1nn，結(jié)點i無左孩子(此時結(jié)點i為葉子)；否則其左孩子是結(jié)點2i。,如果2i+1n,結(jié)點i無右孩子；否則其孩子是結(jié)點2i+1。,A,B,D,E,C,F,G,A,B,C,D,E,F,G,/,/,/,/,/,/,/,/,root,二叉樹的鏈式存儲,二叉樹節(jié)點設(shè)計,publicclassTreeNodepublicchardata;publicTreeNodeleftChild;publicTreeNoderightChild;publicTreeNode(charc)data=c;leftChild=null;rightChild=null;,節(jié)點類,C,/,/,TreeNoden=newTreeNode(C);,n,定義：樹的每個結(jié)點按某種規(guī)律恰好被訪問一次的過程。,二叉樹的編歷,從二叉樹的遞歸定義可知，二叉樹是由三個基本單元組成，即根結(jié)點(D)，左子樹(L)，右子樹(R)。因此，若能依次遍歷這三部分，便是遍歷了整個二叉樹。,根據(jù)排列組合，共有六種方案，即DLR，LDR，LRD，DRL，RDL，RLD。太麻煩,限定對左右子樹的訪問次序：先左后右，則只有前三種情況，分別稱為先序遍歷，中序遍歷和后序遍歷。,遍歷后可以從非線性結(jié)構(gòu)的二叉樹得到各個結(jié)點的線性排列。先序遍歷(1)處理根(2)按先序遍歷左子樹(3)按先序遍歷右子樹中序遍歷(1)按中序遍歷左子樹(2)處理根(3)按中序遍歷右子樹后序遍歷(1)按后序遍歷左子樹(2)按后序遍歷右子樹(3)處理根,A,B,D,E,F,G,C,H,I,遍歷的例子,先序：ABDEHICFG,中序：DBHEIAFCG,后序：DHIEBFGCA,二叉樹類設(shè)計,publicclassBiTreeprivateTreeNoderoot;privatestringtreeStr;/記錄用于創(chuàng)建二叉樹的字符串privateinti=0;/創(chuàng)建二叉樹時，用變量i索引創(chuàng)建的字符串/創(chuàng)建二叉樹時使用，用來引用treeStr串中的一個字符privatestringresult;/先、中、后遍歷時，得到的結(jié)果記錄在這里publicBiTree()root=null;privatevoidsetTreeStr(strings)/設(shè)置用來構(gòu)造二叉樹的字符串treeStr=s;this.i=0;,創(chuàng)建樹時，需要提供字符串。,二叉樹先序編歷已知樹根,voidpreOrder(TreeNodet)/遞歸先序遍歷if(t!=null)this.result+=+t.data;/先序遍歷的結(jié)果，保存在類屬性resultpreOrder(t.leftChild);preOrder(t.rightChild);,publicTreeNodegetRoot()returnthis.root;,從類外(窗體類)看二叉樹類1如何調(diào)用？2如何獲取結(jié)果？,無法操作樹根！因為root是私有的,主窗體中：TreeNodetn=tree.getRoot();tree.preOrder(tn);,結(jié)果保存在result屬性中，私有解決辦法：為BiTree類中增加辦法,二叉樹先序編歷存在的問題,每次調(diào)用preOrder前，需要獲得樹根還需要將result變量初始化，否則下次遍歷的結(jié)果就不對遍歷結(jié)束后，還要記住去取結(jié)果。,灰常不方便,二叉樹先序編歷更好的辦法,publicstringpreOrder()/先序遍歷this.result=;/每次調(diào)用前，result初始化preOrder(this.root);/類內(nèi)，直接用rootreturnthis.result;/返回遍歷結(jié)果,利用OOP的重載,原來的定義voidpreOrder(TreeNodet),重載：同一個類中，方法名相同，形參和返回類型不一樣,主窗體中：Stringans=tree.preOrder();輸出ans,重載的2方法一個private一個public,二叉樹的創(chuàng)建-輔助工作,privateTreeNodecreateThisTree()TreeNodet;charc;c=this.treeStrthis.i+;/從字符串中取第i個字符，i是類中定義的變量，全局if(c=#)return(null);elset=newTreeNode(c);t.leftChild=createThisTree();t.rightChild=createThisTree();return(t);,publicvoidcreateTree(stringtreeStr)/給定的字符串，創(chuàng)建二叉樹this.setTreeStr(treeStr);root=createThisTree();,還是用重載一個private一個public,/給定的字符串，以#代表樹葉,主函數(shù)中的調(diào)用1獲得創(chuàng)建樹字符串str2tree.createTree(str);,創(chuàng)建二叉樹,A,B,C,AB#C#,A,B,AB#,A,C,A#C#,從遍歷結(jié)果推導(dǎo)樹,給出一棵二叉樹的先序遍歷結(jié)果和中序遍歷結(jié)果，或者給出后序遍歷結(jié)果和中序遍歷結(jié)果，就可畫出該二叉樹；,只給出二叉樹先序遍歷結(jié)果和后序遍歷結(jié)果，則無法畫出該二叉樹。,有兩棵二叉樹T1和T2，它們的先序和后序遍歷結(jié)果完全相同。顯然只憑先序和后序遍歷結(jié)果無法確定到底是哪一棵二叉樹。,先序為ABCDEFGHI中序為BCAEDGHFI,根據(jù)遍歷解結(jié)果推導(dǎo)樹-例子,原則：根據(jù)先序定義：A必為根結(jié)點。根據(jù)中序定義：A前的結(jié)點為左子樹A后的結(jié)點為右子樹。,A,B,E,F,C,D,I,G,H,查找,在數(shù)據(jù)結(jié)構(gòu)中找出滿足某種條件的數(shù)據(jù)元素,若在數(shù)據(jù)結(jié)構(gòu)中找到了這樣的元素，則稱查找成功否則稱查找失敗。,順序查找法,從表的第一個元素開始，將給定的值與表中各元素的關(guān)鍵字逐個進行比較，一直到找到相等的關(guān)鍵字，則查找成功；否則就是表中沒有要找的元素，查找失敗。,順序查找法,publicintsearch(intkeyValue)inti=0；while(datai!=keyValue,publicintsearch(intkeyValue)inti=0；for(;ithis.length;i+)if(datai=keyValue)returni;elsereturn-1;,哪兒錯了？,線性查找法,適用于有序線性表,二分查找法,以順序方式存放的有序表的查找可采用對半查找。,18,21,31,37,43,46,52,57,63,96,63,data0,data9,m=(0+9)/2=4,datam,m=(5+9)/2=7,datam,m=(8+9)/2=8,datam,線性查找法,publicintbinSearch(charkeyValue)intlow,high,mid;/low,high,mid分別代表當前查找的表的下限、上限和中間位置low=0;/初始化下限為數(shù)據(jù)的第一個元素的位置high=length-1;/上限為最后一個元素的位置while(low=high)mid=(low+high)/2;/確定中間位置if(datamid=keyValue)return(mid);if(datamidkeyValue)low=mid+1;elsehigh=mid-1;return(-1);,二分查找法代碼,二叉排序樹查找,二分查找法特別適合于從已排序的結(jié)點中尋找給定值。,若線性表中的結(jié)點需要經(jīng)常插入和刪除，最好設(shè)計成結(jié)合鏈表和二分法的查找方法。,二叉排序樹定義,（1）左子樹不空,則左子樹上所有的關(guān)鍵字均小于它的根結(jié)點的關(guān)鍵字；,（2）右子樹不空，則右子樹上所有的關(guān)鍵字均大于或等于它的根結(jié)點的關(guān)鍵字；,（3）它的左、右子樹也是二叉排序樹。,92,69,21,89,93,99,97,78,91,二叉排序樹-查找算法,在給定的二叉排序樹t中查找給定待查關(guān)鍵字K：,1.如果樹t為空，那么查找失敗。算法結(jié)束；否則，轉(zhuǎn)2。,2.如果t.data=K，則查找成功。算法結(jié)束。否則轉(zhuǎn)3。,3.如果Kt.data，那么t=t.lchild，轉(zhuǎn)（1）。否則t=t.rchild，轉(zhuǎn)（1）。,二叉排序查找,publicTreeNodebanSearch(doublek)TreeNodep=this.root;while(p!=null),代碼重建二叉樹,節(jié)點的數(shù)據(jù)類型改成double,92,69,21,89,93,99,97,78,91,k=100查找返回的結(jié)果是什么？,二叉排序創(chuàng)建,92,69,21,89,93,99,97,78,91,79,p,q,找啊找啊找位置，結(jié)束的條件是什么。,二叉排序創(chuàng)建,publicvoidinsBTree(doublek)TreeNodep,q;q=newTreeNode(k);if(root=null)root=q;return;p=root;while(p.leftChild!=q)elsep.leftChild=q;/*插入到左子樹*/elseif(p.rightChild!=null)p=p.rightChild;elsep.rightChild=q;/*插入到右子樹*/endofwhile,二叉排序樹類,publicclassBiSortTreeprivateTreeNoderoot;publicBiSortTree()root=null;publicBiSortTree(TreeNoderoot)this.root=root;publicvoidinsBTree(doublek)publicTreeNodebanSearch(doublek),這2個方法的代碼在前面,記得數(shù)據(jù)類型用double,選擇排序-快速排序,基本思想：通過一趟分割將線性表分成兩部分，其中前一部分的所有元素值均不大于后一部分中的每一元素值；,對每一部分再進行分割，直到整個線性表有序為止。,快速排序-分割步驟,設(shè)置兩個指針i和j，初態(tài)分別指向序列中第一個記錄和最后一個記錄。將第一個記錄移向輔助變量x中，再從j所指位置起向前搜索第一個小于x的記錄，找到后，將aj移至ai的位置；i+,從i所指向位置開始后搜索第一個關(guān)鍵字大于x的記錄，找到后，將ai移至aj的位置；重復(fù)這兩步過程，直至i=j，最后將x送至ai中去。至此一趟排序完成，序列劃分為兩個子文件。,數(shù)據(jù)舉例,初始狀態(tài)433328175263326Xij一次交換263328175263326ij二次交換263328175263352ij三次交換26332817363352ij四次交換263328173636352ij263328173436352i=j,數(shù)據(jù)舉例,(a)一趟排序初始狀態(tài)4521341952603424第一趟242134193445