數(shù)據(jù)結(jié)構(gòu)程序庫(kù)建設(shè)

代文征 楊勇 蔣文娟

摘要：針對(duì)數(shù)據(jù)結(jié)構(gòu)綜合程序庫(kù)建設(shè)的內(nèi)容匱乏問(wèn)題，分析數(shù)據(jù)結(jié)構(gòu)課程的特點(diǎn)，提出基于經(jīng)典的數(shù)據(jù)結(jié)構(gòu)形式以及采用兩種基本的存儲(chǔ)方式實(shí)現(xiàn)相關(guān)基礎(chǔ)算法，實(shí)現(xiàn)擴(kuò)展的綜合項(xiàng)目程序，并通過(guò)實(shí)踐結(jié)果驗(yàn)證構(gòu)建綜合程序庫(kù)的教學(xué)效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；程序庫(kù)；實(shí)踐

背景

隨著網(wǎng)絡(luò)和信息技術(shù)的不斷普及，人們的生活及生產(chǎn)活動(dòng)產(chǎn)生的數(shù)據(jù)正在呈指數(shù)級(jí)增長(zhǎng)。對(duì)海量數(shù)據(jù)進(jìn)行處理及應(yīng)用，是衡量現(xiàn)代化國(guó)家信息技術(shù)能力的一個(gè)重要標(biāo)準(zhǔn)，是一個(gè)國(guó)家信息技術(shù)發(fā)展程度的展板。因此，讓學(xué)生認(rèn)識(shí)數(shù)據(jù)的重要性、樹(shù)立數(shù)據(jù)處理的計(jì)算思維是很重要的。數(shù)據(jù)結(jié)構(gòu)是高校計(jì)算機(jī)、信息類專業(yè)的重要專業(yè)基礎(chǔ)必修課，是培養(yǎng)學(xué)生計(jì)算思維的基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)有助于程序員更有效地組織數(shù)據(jù)、設(shè)計(jì)高效的算法、完成高質(zhì)量的程序，以滿足錯(cuò)綜復(fù)雜的實(shí)際需要。

數(shù)據(jù)結(jié)構(gòu)課程涵蓋了各種基本數(shù)據(jù)結(jié)構(gòu)，其目的是使學(xué)生掌握并熟練應(yīng)用各種基本數(shù)據(jù)結(jié)構(gòu)及復(fù)雜數(shù)據(jù)結(jié)構(gòu)來(lái)解決實(shí)際的數(shù)據(jù)處理問(wèn)題。在實(shí)際教學(xué)中，由于沒(méi)有較好的案例，學(xué)生無(wú)法將基礎(chǔ)算法規(guī)律化，更無(wú)法將其應(yīng)用到實(shí)際問(wèn)題上。

2數(shù)據(jù)結(jié)構(gòu)內(nèi)容與特點(diǎn)

數(shù)據(jù)結(jié)構(gòu)課程主要介紹基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、算法及算法在存儲(chǔ)結(jié)構(gòu)體上的實(shí)現(xiàn)，并擴(kuò)展了基本數(shù)據(jù)結(jié)構(gòu)。學(xué)生要重點(diǎn)掌握基本數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)方式及算法實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)課程的基本內(nèi)容比較多，需要學(xué)生深刻理解并掌握。在眾多的教學(xué)內(nèi)容中存在著某種可遵循的規(guī)律，也就是“算法公式化”。學(xué)生需要不斷地閱讀并動(dòng)手編寫算法程序，才能從中找到這些規(guī)律。學(xué)生切身體會(huì)并掌握基本規(guī)律后，就能夠輕松簡(jiǎn)單地進(jìn)行相關(guān)數(shù)據(jù)結(jié)構(gòu)算法程序的編寫及應(yīng)用。因此，課程教學(xué)內(nèi)容以基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)為切入點(diǎn)，講解如何分析邏輯結(jié)構(gòu)和基本算法，并在兩種基本的存儲(chǔ)方式下進(jìn)行相關(guān)算法程序的編寫。數(shù)據(jù)結(jié)構(gòu)課程的主要特點(diǎn)如下：

（1）數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)多。針對(duì)線性結(jié)構(gòu)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)形式包括線性表、棧、隊(duì)列、串等，非線性結(jié)構(gòu)的包括樹(shù)、二叉樹(shù)、圖（有向圖，無(wú)向圖）等。

（2）算法實(shí)現(xiàn)思想多。針對(duì)不同的數(shù)據(jù)結(jié)構(gòu)形式有兩種基本的存儲(chǔ)方式：順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)，而每種數(shù)據(jù)結(jié)構(gòu)的常見(jiàn)操作（如插入、刪除、查找、排序、修改等）算法的實(shí)現(xiàn)又與存儲(chǔ)結(jié)構(gòu)有關(guān)。

（3）知識(shí)關(guān)聯(lián)性多。數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)需要線性代數(shù)、離散數(shù)學(xué)、概率統(tǒng)計(jì)等數(shù)學(xué)知識(shí)，還需要具有相關(guān)的程序語(yǔ)言基礎(chǔ)。

（4）實(shí)踐性強(qiáng)。數(shù)據(jù)結(jié)構(gòu)需要學(xué)生動(dòng)手使用程序語(yǔ)言實(shí)現(xiàn)相關(guān)的抽象算法，來(lái)驗(yàn)證算法的正確性及可行性，即最終的目的不是掌握算法，而是使用程序語(yǔ)言具體實(shí)現(xiàn)算法。

3構(gòu)建程序庫(kù)

簡(jiǎn)單的課程講解和實(shí)驗(yàn)實(shí)踐并不能讓學(xué)生真正了解和掌握該課程所要求的知識(shí)。因此，需要建立一個(gè)基礎(chǔ)程序及應(yīng)用程序庫(kù)，幫助學(xué)生更好地掌握數(shù)據(jù)結(jié)構(gòu)的算法及具體程序?qū)崿F(xiàn)，為學(xué)生進(jìn)行創(chuàng)新學(xué)習(xí)打下一定的算法及實(shí)現(xiàn)基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)程序及應(yīng)用程序庫(kù)包含以下幾方面。

（1）數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)算法及程序：典型的數(shù)據(jù)結(jié)構(gòu)基本操作算法及相關(guān)存儲(chǔ)體上的具體實(shí)現(xiàn)程序庫(kù)。

（2）數(shù)據(jù)結(jié)構(gòu)應(yīng)用程序庫(kù)。典型的數(shù)據(jù)結(jié)構(gòu)在大中型項(xiàng)目中的具體使用及相關(guān)操作算法實(shí)現(xiàn)，例如購(gòu)票系統(tǒng)、多通道病人就醫(yī)系統(tǒng)、旅游引導(dǎo)系統(tǒng)等，讓學(xué)生了解這些系統(tǒng)的具體實(shí)現(xiàn)，幫助學(xué)生樹(shù)立知識(shí)應(yīng)用的思想，增強(qiáng)學(xué)生的學(xué)習(xí)興趣。

（3）在線互動(dòng)平臺(tái)和資源庫(kù)。構(gòu)建針對(duì)各項(xiàng)目的在線資源和答疑區(qū)，鍛煉學(xué)生的組織能力、溝通能力和協(xié)作能力。

（4）課程內(nèi)容庫(kù)。針對(duì)數(shù)據(jù)結(jié)構(gòu)課程的各個(gè)數(shù)據(jù)結(jié)構(gòu)形式，建設(shè)相應(yīng)的課程內(nèi)容，方便學(xué)生自主學(xué)習(xí)。

（5）數(shù)據(jù)結(jié)構(gòu)文檔庫(kù)。讓學(xué)生使用文檔模板記錄開(kāi)發(fā)過(guò)程中的各個(gè)元素，規(guī)范學(xué)生的文檔寫作。

4程序庫(kù)更新、維護(hù)及代碼復(fù)用

構(gòu)建的程序庫(kù)隨著算法研究的發(fā)展，可以根據(jù)需要在服務(wù)端進(jìn)行相關(guān)案例及算法的更新和維護(hù)。程序庫(kù)的管理操作是由程序庫(kù)管理平臺(tái)來(lái)實(shí)現(xiàn)的，用戶只有使用權(quán)，但用戶可以反饋?zhàn)约涸谑褂弥邪l(fā)現(xiàn)的問(wèn)題及對(duì)程序庫(kù)的意見(jiàn)，程序庫(kù)管理系統(tǒng)收集用戶的反饋信息進(jìn)行針對(duì)性的維護(hù)。

構(gòu)建程序庫(kù)系統(tǒng)前，首先對(duì)系統(tǒng)進(jìn)行用例模型、領(lǐng)域知識(shí)模型的分析，然后采用正向工程，生成系統(tǒng)需要設(shè)計(jì)的相關(guān)對(duì)象，從而保證功能代碼的復(fù)用，方便后期進(jìn)行系統(tǒng)維護(hù)。

5程序庫(kù)實(shí)施與使用

課程共安排64課時(shí)，包括52課時(shí)的理論教學(xué)和12課時(shí)的實(shí)驗(yàn)教學(xué)，基本保證了知識(shí)點(diǎn)的傳授和實(shí)際項(xiàng)目的鍛煉。另外，在52課時(shí)的理論教學(xué)課程中，有4課時(shí)的討論時(shí)間。基礎(chǔ)理論授課時(shí)，將基礎(chǔ)程序庫(kù)中的部分算法進(jìn)行現(xiàn)場(chǎng)的編程實(shí)現(xiàn)，如果學(xué)生想在課后進(jìn)行強(qiáng)化的自學(xué)，可以到程序庫(kù)中進(jìn)行檢索。在構(gòu)建程序庫(kù)時(shí)，要求函數(shù)名能夠體現(xiàn)程序功能，學(xué)生在課后自主學(xué)習(xí)進(jìn)行程序庫(kù)檢索時(shí)，需要提供基本的功能名，系統(tǒng)進(jìn)行粗糙匹配、相似度評(píng)價(jià)，在半監(jiān)督的方式下由學(xué)生進(jìn)行精確定位算法函數(shù)。

為幫助學(xué)生學(xué)習(xí)，我們已經(jīng)建立了校內(nèi)在線學(xué)習(xí)系統(tǒng)，將主講教師的講課錄像及相關(guān)課程庫(kù)發(fā)布到移動(dòng)互聯(lián)網(wǎng)中。此外，還為學(xué)生開(kāi)放了相關(guān)實(shí)驗(yàn)室，幫助學(xué)生研究一些開(kāi)放性問(wèn)題，激發(fā)學(xué)生利用移動(dòng)互聯(lián)網(wǎng)尋求問(wèn)題的答案，培養(yǎng)學(xué)生解決問(wèn)題、撰寫文檔的能力。

6結(jié)語(yǔ)

目前，數(shù)據(jù)結(jié)構(gòu)算法及案例庫(kù)研究和構(gòu)建非常匱乏。由于學(xué)生的興趣點(diǎn)不同，案例庫(kù)應(yīng)提供不同關(guān)注點(diǎn)的項(xiàng)目案例，使學(xué)生有更多的選擇，在達(dá)到同樣的教學(xué)目的的同時(shí)，能夠滿足學(xué)生不同的興趣需要。因此，構(gòu)建一個(gè)完整的自成體系的綜合項(xiàng)目案例庫(kù)是很有必要的。將該程序庫(kù)應(yīng)用到學(xué)校計(jì)算機(jī)信息類專業(yè)的數(shù)據(jù)結(jié)構(gòu)教學(xué)中后，經(jīng)過(guò)4個(gè)學(xué)期的效果對(duì)比，教學(xué)效果較好，相關(guān)成果獲得了河南省教育廳教學(xué)成果二等獎(jiǎng)。