離散數學與數據結構的教學銜接方法研究
2017-05-12 11:40:07魏洪偉王博王建華
計算機教育 2017年4期
魏洪偉+王博+王建華
（1.哈爾濱師范大學 計算機科學與信息工程學院，黑龍江 哈爾濱 150025；2.哈爾濱市人才市場，黑龍江 哈爾濱 150800）
摘 要：針對計算機專業離散數學與數據結構這兩門課程的教學銜接問題，分析兩門課程的內在聯系，提出離散數學是數據結構的數學基礎與理論依據、數據結構是對離散數學的應用與拓展，闡述如何在教學中進行相互滲透與銜接，使學生在牢固掌握理論的基礎上將其應用于計算機實踐。
關鍵詞：離散數學；數據結構；教學銜接
0 引 言
離散數學和數據結構這兩門課程都是重要的計算機專業基礎課，在計算機科學體系中有著舉足輕重的地位。這兩門課程之間相輔相成，離散數學是數據結構的數學基礎與理論依據，數據結構是對離散數學的應用與拓展。離散數學研究的主要是數據的數學結構，也就是元素之間的邏輯關系；數據結構研究的主要是數據的存儲結構，即在保證邏輯關系不變的前提下如何將數據存儲到計算機中并進行高效處理。
正因為這兩門課程之間相輔相成，所以在教學過程中二者必須有效銜接，才能使學生更好地掌握這兩門課程并將其應用于實踐。對計算機專業的學生來說學習離散數學決不能單純地學習數學理論，了解離散數學知識在計算機科學中的應用并能夠學以致用才是學習離散數學的最終目的；在學習數據結構時，較好的離散數學基礎則能夠幫助學生更好地理解數據存儲和處理的方法。因此，在離散數學的教學中，教師必須滲透數學理論在計算機科學特別是數據結構中的應用，在講解數據結構時，也有必要引導學生回顧相應的數學知識以加深理解。
離散數學知識滲透到計算機科學領域的方方面面，為十幾門計算機專業課提供數學基礎與理論依據，對數據結構的貢獻尤為顯著。離散數學對數據結構的貢獻主要體現在兩方面：一是提供數學模型；二是提供解決問題的方法。解決問題的方法主要是指在數據結構中利用離散數學中的定義、定理、推理方法、證明方法、計算方法等來設計算法；數學模型主要包括4種：序列、集合、樹、圖；數據結構的課程設置也主要是圍繞這幾種數學模型的存儲和處理展開的。
1 序 列
DISCRETE MATHEMATICAL STRUCTURES這本書對序列的定義是：序列就是把對象按照一定的順序列舉出來[1]。比如，S：a1， a2， a3，… an，就代表一個長度為n（有n個元素）的序列，其中S為該序列的名稱，a1，a2，a3，…an表示序列的n個元素。離散數學中的序列就是數據結構中線性表的數學模型。
從數學的角度看，序列中的元素存在著一對一的邏輯關系，除了第一個元素和最后一個元素外，每個元素都有一個直接前驅和一個直接后繼，序列中元素的前后位置如果發生改變，那么序列就發生了改變。所以要將序列這種數學模型存儲到計算機中，就必須保障元素之間原有的前后邏輯關系保持不變。數據結構中利用線性表來存儲序列，線性表主要分為順序表和鏈表。
順序表是利用一組地址連續的存儲單元來存儲數據元素，存儲地址的前后順序與元素在數學上的邏輯順序一致。也正因如此，在順序表中只要知道了第一個數據元素的存儲地址和每個數據元素占用的存儲單元數就可以計算出表中任意一個元素的存儲地址，所以在順序表中可以隨機存取，如圖1所示。在鏈表中，每一個存儲單元由數據域和指針域兩部分組成，如圖2所示。鏈表與順序表不同，存儲單元的地址是不連續的，所以利用數據域來存儲數據的同時還要利用指針域來存儲元素的直接后繼地址，這樣就保障了數據元素之間在數學上的一對一邏輯關系不變。在鏈表中，因為后繼元素的地址必須通過它的直接前驅才能找到，要找到鏈表中的第n個元素就必須找到前n-1個元素，所以鏈表的存取方式是順序存取而不是隨機存取。
由序列與線性表之間的關系可以看出，數學上的邏輯關系直接影響了元素的存儲方式，而針對不同的存儲方式就要采取不同的操作方式對元素進行處理，進而衍生出了不同的算法。要理解數據結構中紛繁復雜的算法，首要任務就是要理解元素間的數學邏輯關系，因此離散數學與數據結構的教學必須有效銜接。在離散數學中講解序列這部分內容時，簡要介紹如何利用順序表和鏈表對序列進行存儲和處理，有助于學生理解序列在計算機科學中的應用，把抽象的數學知識具體化、實用化；而在數據結構中講解線性表時簡要回顧序列的數學性質，能讓學生更好地理解線性表的存儲依據、存儲原理及算法的處理方式。清楚了序列與線性表之間的關系，學生對這兩門課的學習也就由抽象變得更具體，再將線性表這種一維線性關系拓展到二維（矩陣）、多維（n維數組）也就不那么難以理解了。
2 集 合
在數據結構中，查找表是由同一類型的數據元素構成的集合[2]，查找表的數學模型就是集合。在數學上，集合中的元素除了同屬于一個集合外沒有其他的邏輯關系，集合是最為松散的一種數學結構，所以查找表也是一種很靈便的數據結構。對于查找表的操作主要有4種：查詢、檢索、插入、刪除。在數學上，元素與集合的關系即“屬于”關系，所以在查找表中可以查詢某一個元素是否在表中，即判斷元素是否屬于該集合；如果查詢到了，自然可以對元素的各種屬性進行檢索；在集合中可以添加或刪除元素，所以在查找表中也可以進行插入或刪除的操作。
盡管從數學的角度來看查找表的數學模型是集合，但從存儲的角度來看，要把查找表中的元素一一輸入到計算機中進行存儲也是必須按照一定順序的，計算機只能接受順序輸入并按照一定的地址順序進行存儲。所以，嚴格來說，集合在計算機中也只能像序列一樣進行順序存儲或鏈式存儲，要做到完全“松散、無序”基本是不可能的。
3 樹
樹是離散數學中最重要的數學模型之一，也是數據結構中最重要的存儲結構之一，尤其是二叉樹。樹在數學上的定義是，令A是一個集合，T是基于集合A的關系，若在集合A中存在唯一的一個點V0使得從V0到除它本身之外的各個點之間都有唯一的一條路，那么稱T為樹，V0為樹根。樹中的元素存在著一對多的邏輯關系，每個父結點都可以對應多個子結點。若一個父結點至多有2個子結點則稱該樹為二叉樹。二叉樹的結構如圖3所示。
二叉樹是在計算機科學中應用最多的一種樹，本身也具有很多特殊性質，相關公式在離散數學課中應該詳細介紹。比如一棵二叉樹的第i層中至多有2i-1個結點、深度為k的二叉樹至多有2k-1個結點[3]等。盡管這些內容數據結構教材中也會提到，但如果離散數學授課教師能夠從數學的角度給出詳細的講解與證明，則會使學生加深對二叉樹的理解，更易于將二叉樹這種數學結構轉化為數據結構，減輕數據結構授課教師的負擔，提高教學效率。
因為二叉樹存在特有的一對二的邏輯關系，所以這種邏輯結構很容易轉化成存儲結構，數據結構中二叉樹的鏈式存儲結構是完全仿照離散數學中二叉樹的有向圖設計的（圖3是某二叉樹的有向圖，圖4是圖3對應的鏈式存儲結構）。因為在二叉樹的有向圖中除葉子節點外每個節點都有兩條有向邊指向其左右子結點，所以為了保障該結點和左右子結點間的對應關系，二叉樹的鏈式存儲結構中每個結點由3部分組成：用來存儲數據的數據域、用來指向左右子存儲地址的左指針域和右指針域。由圖3圖4可以看出，二叉樹的鏈式存儲結構與二叉樹的有向圖的結構是完全相同的，所以說，離散數學是數據結構的重要數學依據和基礎。
離散數學中的二叉樹除了為數據結構提供數學模型和數學依據外，還提供了很多解決問題的方法。比如數據結構中二叉樹的遍歷算法就是直接從數學上的遍歷方法中衍生出來的，離散數學中對二叉樹的遍歷方法有3種：前序遍歷、中序遍歷、后序遍歷。“前、中、后”指的是對根結點的訪問順序，左右子樹按照先左后右的順序進行訪問。以前序遍歷為例，離散數學中前序遍歷的順序是：根結點、左子樹、右子樹，對于左右子樹依然按照同樣的順序進行訪問，所以數據結構中對于二叉樹的前序遍歷的遞歸算法就完全按照該方法進行設計，算法的類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]
有了離散數學所提供的數學模型和數學依據，數據結構就可以更好地將二叉樹這種數學結構應用于計算機實踐，如二叉排序樹、哈夫曼樹都是利用二叉樹所特有的數學性質進行設計和解決實際問題的，所以說，數據結構是離散數學的應用與延伸。
4 圖
在數學上圖具有多對多的邏輯關系，是最復雜的一種數學結構，所以它的存儲結構也最為復雜。圖的存儲結構主要包括：數組（鄰接矩陣）表示法、鄰接表、十字鏈表、鄰接多重表，其中最直觀的存儲結構就是鄰接矩陣存儲法，這也是直接從離散數學中得到的一種存儲方法。
在離散數學中，假設如圖5所示的有向圖表示一個基于集合A的多對多關系R，集合A={1，2，3，4}，關系R={（1，2）， （1，4）， （3，1）， （4，3）}，那么該關系也可以用矩陣來表示，如圖6所示。要將該關系存儲到計算機中，最簡單直觀的方法就是利用二維數組來存儲矩陣，也就是鄰接矩陣存儲法。
在數據結構中圖的數組（鄰接矩陣）存儲表示法如下所示：
typedef struct ArcCell {
VRType adj； //VRType是頂點關系類型。對無權圖，用1或0表示相鄰否； 對帶權圖
//則為權值類型；在無向網中存儲權值
} ArcCell， AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]；
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]； // 存儲頂點的數組
AdjMatrix arcs； // 鄰接矩陣
int vexnum， arcnum； // 圖的當前頂點數和弧（邊）數
GraphKind kind； // 圖的種類標志
} MGraph； [3]
學生在離散數學中學到了相關的數學基礎，在數據結構中學習圖這部分內容時，就能夠很容易理解為什么可以用鄰接矩陣來存儲圖，也就很容易讀懂以上算法中對鄰接矩陣的定義了。
除了為圖提供存儲依據外，離散數學也為數據結構中的圖的相關算法提供數學依據。比如，圖的最小生成樹問題就是以離散數學為依據來解決的，高速公路最低造價問題是最小生成樹問題的一個應用。具體描述如下：要在幾個城市之間建立高速公路的幾種可選擇方案如圖7所示，圖中每一個頂點代表一座城市，邊的權值代表兩座城市之間的高速公路的造價，高速公路最低造價問題就是要在圖7中選擇最少的邊（但要保障各點連通）并使這些邊的權值之和最小，選出的方案就是該圖的最小生成樹，如圖8所示。
關于最小生成樹問題，數據結構課的教學側重點是如何設計算法并應用于實踐，所以為了使學生更好地理解該問題，在離散數學中就應該給學生講解清楚為什么最小生成樹的造價最低。首先需要證明的是圖的生成樹具有能夠連接n個結點的最小邊數n-1，即生成樹恰好能連接n個點。在數學上生成樹具有的兩個性質是：①生成樹是連通圖；②生成樹中不存在回路。在圖8所示的生成樹中若任意刪掉一條邊（即邊數
除最小生成樹問題外，圖的拓撲排序問題、關鍵路徑問題、最短路徑問題等都以離散數學中關系的性質為數學依據。所以說離散數學為數據結構中圖的相關問題提供了數學依據、存儲依據和算法依據。
5 結 語
以上提到的幾點只是離散數學與數據結構教學銜接的幾個方面，這兩門課程之間有著千絲萬縷的關聯，盡管“剪不斷”，但絕不會“理還亂”。只要認真梳理，就會理清這兩門課程之間的聯系。目前的離散數學教材和數據結構教材往往自成一個體系，對二者的關聯與銜接介紹的并不是很詳細，但無論是離散數學還是數據結構都是計算機科學領域中的一部分，授課教師將兩門課程有效銜接才能夠使學生加深對計算機科學的整體化認識與理解，并將其應用于實踐。
基金項目：智能教育與信息工程黑龍江省高校重點實驗室開放課題“移動學習研究與實踐”（SEIE2014-04）。
第一作者簡介：魏洪偉，女，講師，研究方向為移動學習、算法研究，weihongwei999@163.com。
參考文獻：
[1]Bernard K， Robert C B ， Sharon C R . Discrete mathematical structures [M]. 6th ed. 北京： 高等教育出版社， 2012： 13， 271.
[2]嚴蔚敏， 李冬梅， 吳偉民. 數據結構（C語言版）[M]. 北京： 人民郵電出版社， 2011： 164.
[3]嚴蔚敏， 吳偉民. 數據結構（C語言版）[M]. 北京： 高等教育出版社， 2003： 129.
（編輯： 郭田珍 ）
