【正文】 上面的陳述，實(shí)現(xiàn)下面的功能：由計(jì)算機(jī)根據(jù)數(shù)據(jù)分布的規(guī)律自動(dòng)產(chǎn)生 5張卡片上的數(shù)字；? 隨機(jī)的抽取一個(gè)數(shù)字，顯示這個(gè)數(shù)字所在的卡片號(hào)，讓用戶猜這個(gè)數(shù)字是多少；? 在用戶提交所猜數(shù)字后，給出正確與否，并亮出所猜卡片上的數(shù)字 。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )數(shù)組是由 n(n≧ 1)個(gè)相同類型的數(shù)據(jù)元素組成的有限序列，數(shù)組中的每一個(gè)數(shù)據(jù)通常為數(shù)據(jù)元素 數(shù)組中的元素可以通過下標(biāo)隨機(jī)訪問，其中下標(biāo)的個(gè)數(shù)由組數(shù)的維數(shù)決定。認(rèn)識(shí)數(shù)組 ——分析數(shù)組的邏輯結(jié)構(gòu)1. 數(shù)組的定義2. 數(shù)組的特點(diǎn)數(shù)組中的數(shù)據(jù)元素?cái)?shù)目確定。數(shù)組中的每個(gè)數(shù)據(jù)元素都和一組唯一的下標(biāo)值對應(yīng)；數(shù)組是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)，可隨機(jī)存取數(shù)組中的任意數(shù)據(jù)元素 。Length{get。：獲取數(shù)組元素的個(gè)數(shù)。int{：獲取數(shù)組的秩（維數(shù)）。voidarray,index,length)：將數(shù)組設(shè)置為零、 false voidsourceArray,destinationArray,length)：從第一個(gè)元素開始復(fù)制數(shù)組中的一系列元素到另一數(shù)組中。CopyTo(ArrayintIntdimension)：獲取數(shù)組指定維中的元素?cái)?shù)staticSort(Array 這產(chǎn)生了兩種存儲(chǔ)方式：一種是以行序?yàn)橹餍颍ㄏ刃泻罅校┑捻樞虼娣?，另一種是以列序?yàn)橹餍颍ㄏ攘泻笮校┑捻樞虼娣?。二維數(shù)組的兩種存放方式示意圖如下所示 :C 所有數(shù)組都可以使用 認(rèn)識(shí)數(shù)組 ——編程實(shí)現(xiàn)數(shù)組的基本操作數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )代碼請參見 P113114頁 認(rèn)識(shí)數(shù)組 ——用數(shù)組解決數(shù)學(xué)魔術(shù)游戲的編程數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )學(xué)習(xí)情境 ——用特殊矩陣解決查詢城市間的距離的編程 [問題描述 ]　 　考察佛羅里達(dá)州的六個(gè)城市 Gainesville,Miami,將這六個(gè)城市從 1～ 6進(jìn)行編號(hào)。矩陣的第 i行和第 i列代表第 i(i,)和城市 j下圖給出了相應(yīng)的矩陣。和 j， (i,distancei數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )學(xué)習(xí)情境 ——用線性表解決學(xué)生成績表的編程[問題描述 ](續(xù) )根據(jù)該矩陣的特點(diǎn)，編程實(shí)現(xiàn)下面的功能：兩個(gè)城市間的距離只存儲(chǔ)一次，自己到自己的距離不要存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )對那些具有相同值元素或零元素在矩陣中分布具有一定規(guī)律的矩陣，被稱之為特殊矩陣。ignl）： M是一個(gè)對角矩陣當(dāng)且僅當(dāng) i≠jj)0。所示。tiignl）： M是一個(gè)三對角矩陣當(dāng)且僅當(dāng) ||1j=如圖 ? 下三角矩陣（ lower時(shí)有 Mj=如圖 上三角矩陣（ upper時(shí)有 Mj=如圖 對稱矩陣（ smerc）： M是一個(gè)對稱矩陣當(dāng)且僅當(dāng)對于所有的 i有 Mj=Mi如圖 認(rèn)識(shí)特殊矩陣 ——分析特殊矩陣的邏輯結(jié)構(gòu)1. 特殊矩陣的定義數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )由于對稱矩陣中的元素關(guān)于主對角線對稱，為了節(jié)省空間，可以為每一對稱元素只分配一個(gè)存儲(chǔ)空間，存儲(chǔ)時(shí)只存儲(chǔ)對稱矩陣中的上三角或下三角中的元素 假設(shè)以行序?yàn)橹鬟M(jìn)行壓縮存儲(chǔ)，可以用一個(gè)一維數(shù)組 b(n(n+1)/2)作為 n階對稱矩陣 a的存儲(chǔ)結(jié)構(gòu)，則 b[k]和矩陣元素 aij之間存在如下一對應(yīng)關(guān)系： 為了完成這項(xiàng)研究，收集了 1000個(gè)顧客的購物數(shù)據(jù)，這些數(shù)據(jù)被組織成一個(gè)矩陣 purchases，其中 purchasesj)所購買的商品 i的數(shù)量。代表商品 i矩陣spent=purchasesT根據(jù)上面的描述，編程實(shí)現(xiàn)下面的功能：尋找一種節(jié)省空間的方式，將矩陣存儲(chǔ)到內(nèi)存中；? 當(dāng)超市管理人員輸入一顧客編號(hào)，即算出該顧客所花費(fèi)的購物金額；? 可以實(shí)現(xiàn)矩陣的轉(zhuǎn)置，使得行表示顧客，列表示產(chǎn)品。認(rèn)識(shí)稀疏矩陣 ——分析 稀疏矩陣的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )由于稀疏矩陣中非零元素較少，零元素較多，因此可以采用只存儲(chǔ)非零元素的方法來進(jìn)行壓縮存儲(chǔ) 三元組可以采用順序表示方法，也可以采用鏈?zhǔn)奖硎痉椒ǎ@樣就產(chǎn)生了對稀疏矩陣的不同壓縮存儲(chǔ)方式 若把稀疏矩陣的三元組線性表按順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，則稱為稀疏矩陣的三元組順序表。順序表中除了存儲(chǔ)三元組外，還應(yīng)該存儲(chǔ)矩陣行數(shù)、列數(shù)和總的非零元素?cái)?shù)目，這樣才能唯一的確定一個(gè)矩陣 十字鏈表結(jié)點(diǎn)分為三類 表結(jié)點(diǎn)，它由五個(gè)域組成，其中 i和 j存儲(chǔ)的是結(jié)點(diǎn)所在的行和列，right和 down存儲(chǔ)的是指向十字鏈表中該結(jié)點(diǎn)所有行和列的下一個(gè)結(jié)點(diǎn)的指針， v用于存放元素值 總表頭結(jié)點(diǎn)，這類結(jié)點(diǎn)與表頭結(jié)點(diǎn)的結(jié)構(gòu)和形式一樣，只是它的 i和 j存放的是矩陣的行和列數(shù) ? 十字鏈表中的每一行和每一列鏈表都是一個(gè)循環(huán)鏈表，都有一個(gè)表頭結(jié)點(diǎn) 這里僅討論最簡單的矩陣轉(zhuǎn)置運(yùn)算算法。(0≤i≤m1,0≤j≤n1)認(rèn)識(shí)稀疏矩陣 ——編程實(shí)現(xiàn) 稀疏矩陣的基本運(yùn)算數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )第一步：根據(jù) M矩陣的行數(shù)、列數(shù)和非零元總數(shù)確定 N矩陣的列數(shù)、行數(shù)和非零元總數(shù) 認(rèn)識(shí)稀疏矩陣 ——編程實(shí)現(xiàn) 稀疏矩陣的基本運(yùn)算三元組表表示轉(zhuǎn)置矩陣的具體方法是：數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )代碼請參見 P125128頁 認(rèn)識(shí)稀疏矩陣 ——用 稀疏矩陣實(shí)現(xiàn)超市物品購買數(shù)據(jù)的編程數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)在本章中，你已經(jīng)學(xué)到：數(shù)組是由 n(n≧ 1)個(gè)相同類型的數(shù)據(jù)元素組成的有限序列，數(shù)組中的數(shù)據(jù)是按順序存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中 ；需要進(jìn)行壓縮存儲(chǔ)的矩陣通常有兩種類型： 特殊矩陣和稀疏矩陣 在存儲(chǔ)稀疏矩陣的三元組線性表時(shí)，可以用稀疏矩陣的三元組順序表存儲(chǔ)，也可以用十字鏈表存儲(chǔ) ；十字鏈表為稀疏矩陣的每一行設(shè)置一個(gè)單獨(dú)的鏈表，為每一列也設(shè)置了一個(gè)單獨(dú)的鏈表，稀疏矩陣的每一個(gè)非零元素同時(shí)包含在兩個(gè)鏈表中，十字鏈表的頭指針指向鏈表的頭結(jié)點(diǎn) 為了方便對表 (a)的記錄進(jìn)行增、刪、改、查，一般需要建立索引表 (b)。 Tree）是 n(n≥0)個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根 (root)的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成。在二叉樹中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。 結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。 度為 0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。 度不為 0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。（ 4） 左孩子、右孩子、雙親。這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親。（ 5） 路徑、路徑長度。這條路徑的長度是 k1。 在樹中，如果有一條路徑從結(jié)點(diǎn) M到結(jié)點(diǎn) N，那么 M就稱為 N的祖先，而 N稱為 M的子孫。 規(guī)定樹的根結(jié)點(diǎn)的層數(shù)為 1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加 1。 樹中所有結(jié)點(diǎn)的最大層數(shù)稱為樹的深度。 樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。 在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )認(rèn)識(shí)二叉樹 ——分析二叉樹的邏輯結(jié)構(gòu)３、二叉樹的相關(guān)術(shù)語 （ 11） 完全二叉樹。完全二叉樹的特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。Create（ x， lbt， rbt）：生成一棵以 x為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹 lbt和 rbt為左子樹和右子樹的二叉樹。如果結(jié)點(diǎn) parent原來有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn) parent原來的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn) x的左孩子結(jié)點(diǎn)。如果結(jié)點(diǎn) parent原來有右孩子結(jié)點(diǎn)，則將結(jié)點(diǎn) parent原來的右孩子結(jié)點(diǎn)作為結(jié)點(diǎn) x的右孩子結(jié)點(diǎn)。DeleteR（ bt， parent）：在二叉樹 bt中刪除結(jié)點(diǎn) parent的右子樹。Traverse（ bt）：按某種方式遍歷二叉樹 bt的全部結(jié)點(diǎn)。 性質(zhì) 3對于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為 n0，度數(shù)為 2的結(jié)點(diǎn)數(shù)為 n2，則有 :n0＝ n2＋ 1。性質(zhì) 4具有 n個(gè)結(jié)點(diǎn)的完全二叉樹的深度 k為 [log2n]+1。（ 2）如果 2i≤n，則序號(hào)為 i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為 2i；如果 2in，則序號(hào)為 i的結(jié)點(diǎn)無左孩子。 一般是按照二叉樹結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。圖 (a)數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用順序存儲(chǔ)結(jié)構(gòu)表示二叉樹 對于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點(diǎn)順序存儲(chǔ)在一維數(shù)組中，則數(shù)組元素下標(biāo)之間的關(guān)系不能夠反映二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點(diǎn)，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲(chǔ)。 圖 (a)給出了圖 (b)所示的一棵二叉樹的二叉鏈表示。 parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。圖 (b)所示的一棵二叉樹的三叉鏈表示。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)的二叉樹的基本操作216。 public LinkBiTree(T val, NodeT lp, NodeT rp) 216。 public NodeT Root()216。 public NodeT GetRChild(NodeT p)216。 public void InsertR(T val, NodeT p)216。 public NodeT DeleteR(NodeT p)216。 public bool IsLeaf(NodeT p)具體操作參與 P140143數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實(shí)現(xiàn) 二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹。如果限定先左后右，則只有前三種方式，即 DLR（稱為先序遍歷）、 LDR（稱為中序遍歷）和 LRD（稱為后序遍歷）。否則，　　 (1)先序遍歷根結(jié)點(diǎn)的左子樹；　　 (3)　 publicpreorder(NodeT(IsEmpty()){(Treeempty)。}if!=+preorder()。}}數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實(shí)現(xiàn) 2．中序遍歷（ LDR）中序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。publicinorder(NodeT{if{(Treeempty)。}if!=()。}}數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實(shí)現(xiàn) 3．后序遍歷（ LRD）后序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。（ 3）訪問根結(jié)點(diǎn)； publicpostorder(NodeT(IsEmpty(isreturn。(ptrnull){postorder()。(+}}數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )二叉樹的遍歷與實(shí)現(xiàn) 4．層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。 } //設(shè)置一個(gè)隊(duì)列保存層序遍歷的結(jié)點(diǎn) CSeqQueueNodeT sq = new CSeqQueueNodeT(50)。 while (!()) {//隊(duì)列非空，結(jié)點(diǎn)沒有處理完 NodeT tmp = ()。 //處理當(dāng)前結(jié)點(diǎn) if ( != null) { ()。 //將當(dāng)前結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì) } } }數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )用二叉搜索樹解決快速搜索磁盤文件中記錄的問題 在二叉樹中，如果一個(gè)結(jié)點(diǎn)的左子結(jié)點(diǎn)的值永遠(yuǎn)小于該結(jié)點(diǎn)的值，而右子結(jié)點(diǎn)的值永遠(yuǎn)大于該結(jié)點(diǎn)的值，這樣的二叉樹為二叉搜索樹。為基于圖 (b)所示的索引表建立的二叉搜索樹，用二叉搜索樹解決快速搜磁盤文件記錄代碼 參見 P147150數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )問題描述：統(tǒng)計(jì)出二叉樹中葉子結(jié)點(diǎn)的數(shù)目 設(shè)二叉樹具有 n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長度與相應(yīng)葉結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為：例： 4個(gè)葉結(jié)點(diǎn)，其權(quán)值分別為 1， 3， 5， 7，可構(gòu)造出形狀不同的多個(gè)二叉樹。圖 5個(gè)不同形狀的二叉樹。葉結(jié)點(diǎn)權(quán)值集合為W＝ {1， 3， 5， 7}的哈夫曼樹的構(gòu)造過程。Tree）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根 (root)的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成二叉樹中的相關(guān)概念：結(jié)點(diǎn)的度，葉結(jié)點(diǎn)，分枝結(jié)點(diǎn)，左孩子、右孩子、雙親，路徑、路徑長度，祖先、子孫，結(jié)點(diǎn)的層數(shù)，樹的深度，樹的度，滿二叉樹，完全二叉樹。性質(zhì) 1一棵非空二叉樹的第 i層上最多有 2i1個(gè)結(jié)點(diǎn)（ i≥1）。性質(zhì) 3對于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為 n0，度數(shù)為 2的結(jié)點(diǎn)數(shù)為 n2，則有 :n0＝ n2＋ 1。數(shù)據(jù)結(jié)構(gòu)和算法簡介數(shù)據(jù)結(jié)構(gòu) (C描述 )小結(jié)（續(xù)）性質(zhì) 5對于