離散數(shù)學與數(shù)據(jù)結(jié)構(gòu)的教學銜接方法研究

魏洪偉+王博+王建華

（1.哈爾濱師范大學 計算機科學與信息工程學院，黑龍江 哈爾濱 150025；2.哈爾濱市人才市場，黑龍江 哈爾濱 150800）

摘 要：針對計算機專業(yè)離散數(shù)學與數(shù)據(jù)結(jié)構(gòu)這兩門課程的教學銜接問題，分析兩門課程的內(nèi)在聯(lián)系，提出離散數(shù)學是數(shù)據(jù)結(jié)構(gòu)的數(shù)學基礎(chǔ)與理論依據(jù)、數(shù)據(jù)結(jié)構(gòu)是對離散數(shù)學的應用與拓展，闡述如何在教學中進行相互滲透與銜接，使學生在牢固掌握理論的基礎(chǔ)上將其應用于計算機實踐。

關(guān)鍵詞：離散數(shù)學；數(shù)據(jù)結(jié)構(gòu)；教學銜接

0 引 言

離散數(shù)學和數(shù)據(jù)結(jié)構(gòu)這兩門課程都是重要的計算機專業(yè)基礎(chǔ)課，在計算機科學體系中有著舉足輕重的地位。這兩門課程之間相輔相成，離散數(shù)學是數(shù)據(jù)結(jié)構(gòu)的數(shù)學基礎(chǔ)與理論依據(jù)，數(shù)據(jù)結(jié)構(gòu)是對離散數(shù)學的應用與拓展。離散數(shù)學研究的主要是數(shù)據(jù)的數(shù)學結(jié)構(gòu)，也就是元素之間的邏輯關(guān)系；數(shù)據(jù)結(jié)構(gòu)研究的主要是數(shù)據(jù)的存儲結(jié)構(gòu)，即在保證邏輯關(guān)系不變的前提下如何將數(shù)據(jù)存儲到計算機中并進行高效處理。

正因為這兩門課程之間相輔相成，所以在教學過程中二者必須有效銜接，才能使學生更好地掌握這兩門課程并將其應用于實踐。對計算機專業(yè)的學生來說學習離散數(shù)學決不能單純地學習數(shù)學理論，了解離散數(shù)學知識在計算機科學中的應用并能夠?qū)W以致用才是學習離散數(shù)學的最終目的；在學習數(shù)據(jù)結(jié)構(gòu)時，較好的離散數(shù)學基礎(chǔ)則能夠幫助學生更好地理解數(shù)據(jù)存儲和處理的方法。因此，在離散數(shù)學的教學中，教師必須滲透數(shù)學理論在計算機科學特別是數(shù)據(jù)結(jié)構(gòu)中的應用，在講解數(shù)據(jù)結(jié)構(gòu)時，也有必要引導學生回顧相應的數(shù)學知識以加深理解。

離散數(shù)學知識滲透到計算機科學領(lǐng)域的方方面面，為十幾門計算機專業(yè)課提供數(shù)學基礎(chǔ)與理論依據(jù)，對數(shù)據(jù)結(jié)構(gòu)的貢獻尤為顯著。離散數(shù)學對數(shù)據(jù)結(jié)構(gòu)的貢獻主要體現(xiàn)在兩方面：一是提供數(shù)學模型；二是提供解決問題的方法。解決問題的方法主要是指在數(shù)據(jù)結(jié)構(gòu)中利用離散數(shù)學中的定義、定理、推理方法、證明方法、計算方法等來設(shè)計算法；數(shù)學模型主要包括4種：序列、集合、樹、圖；數(shù)據(jù)結(jié)構(gòu)的課程設(shè)置也主要是圍繞這幾種數(shù)學模型的存儲和處理展開的。

1 序 列

DISCRETE MATHEMATICAL STRUCTURES這本書對序列的定義是：序列就是把對象按照一定的順序列舉出來[1]。比如，S：a1， a2， a3，… an，就代表一個長度為n（有n個元素）的序列，其中S為該序列的名稱，a1，a2，a3，…an表示序列的n個元素。離散數(shù)學中的序列就是數(shù)據(jù)結(jié)構(gòu)中線性表的數(shù)學模型。

從數(shù)學的角度看，序列中的元素存在著一對一的邏輯關(guān)系，除了第一個元素和最后一個元素外，每個元素都有一個直接前驅(qū)和一個直接后繼，序列中元素的前后位置如果發(fā)生改變，那么序列就發(fā)生了改變。所以要將序列這種數(shù)學模型存儲到計算機中，就必須保障元素之間原有的前后邏輯關(guān)系保持不變。數(shù)據(jù)結(jié)構(gòu)中利用線性表來存儲序列，線性表主要分為順序表和鏈表。

順序表是利用一組地址連續(xù)的存儲單元來存儲數(shù)據(jù)元素，存儲地址的前后順序與元素在數(shù)學上的邏輯順序一致。也正因如此，在順序表中只要知道了第一個數(shù)據(jù)元素的存儲地址和每個數(shù)據(jù)元素占用的存儲單元數(shù)就可以計算出表中任意一個元素的存儲地址，所以在順序表中可以隨機存取，如圖1所示。在鏈表中，每一個存儲單元由數(shù)據(jù)域和指針域兩部分組成，如圖2所示。鏈表與順序表不同，存儲單元的地址是不連續(xù)的，所以利用數(shù)據(jù)域來存儲數(shù)據(jù)的同時還要利用指針域來存儲元素的直接后繼地址，這樣就保障了數(shù)據(jù)元素之間在數(shù)學上的一對一邏輯關(guān)系不變。在鏈表中，因為后繼元素的地址必須通過它的直接前驅(qū)才能找到，要找到鏈表中的第n個元素就必須找到前n-1個元素，所以鏈表的存取方式是順序存取而不是隨機存取。

由序列與線性表之間的關(guān)系可以看出，數(shù)學上的邏輯關(guān)系直接影響了元素的存儲方式，而針對不同的存儲方式就要采取不同的操作方式對元素進行處理，進而衍生出了不同的算法。要理解數(shù)據(jù)結(jié)構(gòu)中紛繁復雜的算法，首要任務(wù)就是要理解元素間的數(shù)學邏輯關(guān)系，因此離散數(shù)學與數(shù)據(jù)結(jié)構(gòu)的教學必須有效銜接。在離散數(shù)學中講解序列這部分內(nèi)容時，簡要介紹如何利用順序表和鏈表對序列進行存儲和處理，有助于學生理解序列在計算機科學中的應用，把抽象的數(shù)學知識具體化、實用化；而在數(shù)據(jù)結(jié)構(gòu)中講解線性表時簡要回顧序列的數(shù)學性質(zhì)，能讓學生更好地理解線性表的存儲依據(jù)、存儲原理及算法的處理方式。清楚了序列與線性表之間的關(guān)系，學生對這兩門課的學習也就由抽象變得更具體，再將線性表這種一維線性關(guān)系拓展到二維（矩陣）、多維（n維數(shù)組）也就不那么難以理解了。

2 集 合

在數(shù)據(jù)結(jié)構(gòu)中，查找表是由同一類型的數(shù)據(jù)元素構(gòu)成的集合[2]，查找表的數(shù)學模型就是集合。在數(shù)學上，集合中的元素除了同屬于一個集合外沒有其他的邏輯關(guān)系，集合是最為松散的一種數(shù)學結(jié)構(gòu)，所以查找表也是一種很靈便的數(shù)據(jù)結(jié)構(gòu)。對于查找表的操作主要有4種：查詢、檢索、插入、刪除。在數(shù)學上，元素與集合的關(guān)系即“屬于”關(guān)系，所以在查找表中可以查詢某一個元素是否在表中，即判斷元素是否屬于該集合；如果查詢到了，自然可以對元素的各種屬性進行檢索；在集合中可以添加或刪除元素，所以在查找表中也可以進行插入或刪除的操作。

盡管從數(shù)學的角度來看查找表的數(shù)學模型是集合，但從存儲的角度來看，要把查找表中的元素一一輸入到計算機中進行存儲也是必須按照一定順序的，計算機只能接受順序輸入并按照一定的地址順序進行存儲。所以，嚴格來說，集合在計算機中也只能像序列一樣進行順序存儲或鏈式存儲，要做到完全“松散、無序”基本是不可能的。

3 樹

樹是離散數(shù)學中最重要的數(shù)學模型之一，也是數(shù)據(jù)結(jié)構(gòu)中最重要的存儲結(jié)構(gòu)之一，尤其是二叉樹。樹在數(shù)學上的定義是，令A是一個集合，T是基于集合A的關(guān)系，若在集合A中存在唯一的一個點V0使得從V0到除它本身之外的各個點之間都有唯一的一條路，那么稱T為樹，V0為樹根。樹中的元素存在著一對多的邏輯關(guān)系，每個父結(jié)點都可以對應多個子結(jié)點。若一個父結(jié)點至多有2個子結(jié)點則稱該樹為二叉樹。二叉樹的結(jié)構(gòu)如圖3所示。

二叉樹是在計算機科學中應用最多的一種樹，本身也具有很多特殊性質(zhì)，相關(guān)公式在離散數(shù)學課中應該詳細介紹。比如一棵二叉樹的第i層中至多有2i-1個結(jié)點、深度為k的二叉樹至多有2k-1個結(jié)點[3]等。盡管這些內(nèi)容數(shù)據(jù)結(jié)構(gòu)教材中也會提到，但如果離散數(shù)學授課教師能夠從數(shù)學的角度給出詳細的講解與證明，則會使學生加深對二叉樹的理解，更易于將二叉樹這種數(shù)學結(jié)構(gòu)轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)，減輕數(shù)據(jù)結(jié)構(gòu)授課教師的負擔，提高教學效率。

因為二叉樹存在特有的一對二的邏輯關(guān)系，所以這種邏輯結(jié)構(gòu)很容易轉(zhuǎn)化成存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)中二叉樹的鏈式存儲結(jié)構(gòu)是完全仿照離散數(shù)學中二叉樹的有向圖設(shè)計的（圖3是某二叉樹的有向圖，圖4是圖3對應的鏈式存儲結(jié)構(gòu)）。因為在二叉樹的有向圖中除葉子節(jié)點外每個節(jié)點都有兩條有向邊指向其左右子結(jié)點，所以為了保障該結(jié)點和左右子結(jié)點間的對應關(guān)系，二叉樹的鏈式存儲結(jié)構(gòu)中每個結(jié)點由3部分組成：用來存儲數(shù)據(jù)的數(shù)據(jù)域、用來指向左右子存儲地址的左指針域和右指針域。由圖3圖4可以看出，二叉樹的鏈式存儲結(jié)構(gòu)與二叉樹的有向圖的結(jié)構(gòu)是完全相同的，所以說，離散數(shù)學是數(shù)據(jù)結(jié)構(gòu)的重要數(shù)學依據(jù)和基礎(chǔ)。

離散數(shù)學中的二叉樹除了為數(shù)據(jù)結(jié)構(gòu)提供數(shù)學模型和數(shù)學依據(jù)外，還提供了很多解決問題的方法。比如數(shù)據(jù)結(jié)構(gòu)中二叉樹的遍歷算法就是直接從數(shù)學上的遍歷方法中衍生出來的，離散數(shù)學中對二叉樹的遍歷方法有3種：前序遍歷、中序遍歷、后序遍歷?！扒?、中、后”指的是對根結(jié)點的訪問順序，左右子樹按照先左后右的順序進行訪問。以前序遍歷為例，離散數(shù)學中前序遍歷的順序是：根結(jié)點、左子樹、右子樹，對于左右子樹依然按照同樣的順序進行訪問，所以數(shù)據(jù)結(jié)構(gòu)中對于二叉樹的前序遍歷的遞歸算法就完全按照該方法進行設(shè)計，算法的類C語言描述如下所示：

Status PreorderTraverse（ BiTree T， Status（*Visit） （TELemType e）{

if（T）{

if（Visit（T—>data））

if（ PreorderTraverse（T—>Ichild， Visit））

if（PreorderTraverse（T—>rchild，Visit）） retrun OK；

return ERROR

}else return OK

}//PreOrderTraverse [3]

有了離散數(shù)學所提供的數(shù)學模型和數(shù)學依據(jù)，數(shù)據(jù)結(jié)構(gòu)就可以更好地將二叉樹這種數(shù)學結(jié)構(gòu)應用于計算機實踐，如二叉排序樹、哈夫曼樹都是利用二叉樹所特有的數(shù)學性質(zhì)進行設(shè)計和解決實際問題的，所以說，數(shù)據(jù)結(jié)構(gòu)是離散數(shù)學的應用與延伸。

4 圖

在數(shù)學上圖具有多對多的邏輯關(guān)系，是最復雜的一種數(shù)學結(jié)構(gòu)，所以它的存儲結(jié)構(gòu)也最為復雜。圖的存儲結(jié)構(gòu)主要包括：數(shù)組（鄰接矩陣）表示法、鄰接表、十字鏈表、鄰接多重表，其中最直觀的存儲結(jié)構(gòu)就是鄰接矩陣存儲法，這也是直接從離散數(shù)學中得到的一種存儲方法。

在離散數(shù)學中，假設(shè)如圖5所示的有向圖表示一個基于集合A的多對多關(guān)系R，集合A={1，2，3，4}，關(guān)系R={（1，2）， （1，4）， （3，1）， （4，3）}，那么該關(guān)系也可以用矩陣來表示，如圖6所示。要將該關(guān)系存儲到計算機中，最簡單直觀的方法就是利用二維數(shù)組來存儲矩陣，也就是鄰接矩陣存儲法。

在數(shù)據(jù)結(jié)構(gòu)中圖的數(shù)組（鄰接矩陣）存儲表示法如下所示：

typedef struct ArcCell {

VRType adj； //VRType是頂點關(guān)系類型。對無權(quán)圖，用1或0表示相鄰否； 對帶權(quán)圖

//則為權(quán)值類型；在無向網(wǎng)中存儲權(quán)值

} ArcCell， AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]；

typedef struct {

VertexType vexs[MAX_VERTEX_NUM]； // 存儲頂點的數(shù)組

AdjMatrix arcs； // 鄰接矩陣

int vexnum， arcnum； // 圖的當前頂點數(shù)和?。ㄟ叄?shù)

GraphKind kind； // 圖的種類標志

} MGraph； [3]

學生在離散數(shù)學中學到了相關(guān)的數(shù)學基礎(chǔ)，在數(shù)據(jù)結(jié)構(gòu)中學習圖這部分內(nèi)容時，就能夠很容易理解為什么可以用鄰接矩陣來存儲圖，也就很容易讀懂以上算法中對鄰接矩陣的定義了。

除了為圖提供存儲依據(jù)外，離散數(shù)學也為數(shù)據(jù)結(jié)構(gòu)中的圖的相關(guān)算法提供數(shù)學依據(jù)。比如，圖的最小生成樹問題就是以離散數(shù)學為依據(jù)來解決的，高速公路最低造價問題是最小生成樹問題的一個應用。具體描述如下：要在幾個城市之間建立高速公路的幾種可選擇方案如圖7所示，圖中每一個頂點代表一座城市，邊的權(quán)值代表兩座城市之間的高速公路的造價，高速公路最低造價問題就是要在圖7中選擇最少的邊（但要保障各點連通）并使這些邊的權(quán)值之和最小，選出的方案就是該圖的最小生成樹，如圖8所示。

關(guān)于最小生成樹問題，數(shù)據(jù)結(jié)構(gòu)課的教學側(cè)重點是如何設(shè)計算法并應用于實踐，所以為了使學生更好地理解該問題，在離散數(shù)學中就應該給學生講解清楚為什么最小生成樹的造價最低。首先需要證明的是圖的生成樹具有能夠連接n個結(jié)點的最小邊數(shù)n-1，即生成樹恰好能連接n個點。在數(shù)學上生成樹具有的兩個性質(zhì)是：①生成樹是連通圖；②生成樹中不存在回路。在圖8所示的生成樹中若任意刪掉一條邊（即邊數(shù)n-1）則會出現(xiàn)回路，不再是樹，如圖10所示。因此圖的生成樹應恰好具有n-1條邊。若這n-1條邊具有的權(quán)值之和最小，則為最小生成樹。也就是說要將圖7中的6個點連通起來構(gòu)造一棵生成樹恰好需要5條邊，圖8中所選出的5條邊權(quán)值之和最小，所以圖8是圖7的最小生成樹，按此方案建造的高速公路造價最低。數(shù)據(jù)結(jié)構(gòu)中求解最小生成樹的克魯斯卡爾（Kruskal）算法就完全遵循了生成樹的數(shù)學性質(zhì)?？唆斔箍査惴ǖ幕舅枷胧牵好看螐目蛇x擇方案中選擇一條權(quán)值最小的邊，但當前所選擇的邊與已選出的邊不能構(gòu)成回路，直至選出n-1條邊為止。根據(jù)克魯斯卡爾算法就可以在圖7中依次選出（v1，v3），（v4，v6），（v2，v5），（v3，v6），（v2，v3），最終得到圖8所示的最小生成樹。

除最小生成樹問題外，圖的拓撲排序問題、關(guān)鍵路徑問題、最短路徑問題等都以離散數(shù)學中關(guān)系的性質(zhì)為數(shù)學依據(jù)。所以說離散數(shù)學為數(shù)據(jù)結(jié)構(gòu)中圖的相關(guān)問題提供了數(shù)學依據(jù)、存儲依據(jù)和算法依據(jù)。

5 結(jié) 語

以上提到的幾點只是離散數(shù)學與數(shù)據(jù)結(jié)構(gòu)教學銜接的幾個方面，這兩門課程之間有著千絲萬縷的關(guān)聯(lián)，盡管“剪不斷”，但絕不會“理還亂”。只要認真梳理，就會理清這兩門課程之間的聯(lián)系。目前的離散數(shù)學教材和數(shù)據(jù)結(jié)構(gòu)教材往往自成一個體系，對二者的關(guān)聯(lián)與銜接介紹的并不是很詳細，但無論是離散數(shù)學還是數(shù)據(jù)結(jié)構(gòu)都是計算機科學領(lǐng)域中的一部分，授課教師將兩門課程有效銜接才能夠使學生加深對計算機科學的整體化認識與理解，并將其應用于實踐。

基金項目：智能教育與信息工程黑龍江省高校重點實驗室開放課題“移動學習研究與實踐”（SEIE2014-04）。

第一作者簡介：魏洪偉，女，講師，研究方向為移動學習、算法研究，weihongwei999@163.com。

參考文獻：

[1]Bernard K， Robert C B ， Sharon C R . Discrete mathematical structures [M]. 6th ed. 北京： 高等教育出版社， 2012： 13， 271.

[2]嚴蔚敏， 李冬梅， 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京： 人民郵電出版社， 2011： 164.

[3]嚴蔚敏， 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）[M]. 北京： 高等教育出版社， 2003： 129.

（編輯： 郭田珍 ）