以問題為導(dǎo)向的數(shù)據(jù)結(jié)構(gòu)課程PBL教學(xué)方法研究

摘要：數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的核心課程之一，它在計算機(jī)專業(yè)人才培養(yǎng)中起著舉足輕重的作用。數(shù)據(jù)結(jié)構(gòu)也是一門被公認(rèn)的難、廣、多的課程，作者針對數(shù)據(jù)結(jié)構(gòu)課程的特點，提出了以問題為導(dǎo)向、以實際問題為原型的PBL教學(xué)方法。與傳統(tǒng)的教學(xué)方法相比，以問題為導(dǎo)向的數(shù)據(jù)結(jié)構(gòu)課程PBL教學(xué)方法能夠更好地培養(yǎng)學(xué)生分析問題和解決問題的能力，能夠有效地提高學(xué)生的學(xué)習(xí)興趣和編程能力。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);教學(xué)方法;引導(dǎo)式

中圖分類號：G642 ?文獻(xiàn)標(biāo)識碼：B ?論文編號：1674-2117（2021）05-0103-04

困擾學(xué)生的問題

“數(shù)據(jù)結(jié)構(gòu)”是一門被公認(rèn)的難、廣、多的課程，其中的“難”表示理解難，“廣”表示算法廣，“多”表示內(nèi)容多。對于初學(xué)者來說，往往有一系列的問題困擾著他們，如什么是數(shù)據(jù)，如何表示數(shù)據(jù)，數(shù)據(jù)之間存在哪些邏輯關(guān)聯(lián)，如何利用數(shù)據(jù)元素之間的邏輯關(guān)聯(lián)關(guān)系組織數(shù)據(jù)以便高效地對數(shù)據(jù)進(jìn)行操作，如何將數(shù)據(jù)和數(shù)據(jù)的關(guān)聯(lián)關(guān)系映射到內(nèi)存，數(shù)據(jù)結(jié)構(gòu)與編程語言以及數(shù)據(jù)結(jié)構(gòu)與算法有什么關(guān)系等。要想讓學(xué)生學(xué)好這門課程，首先必須幫助學(xué)生解開這些疑問。

1.數(shù)據(jù)的表示

數(shù)據(jù)是信息的表示形式，是信息的載體。[1]計算機(jī)程序的實質(zhì)是對信息的處理，也就是對數(shù)據(jù)進(jìn)行處理。在現(xiàn)實世界中，數(shù)據(jù)往往以文字的形式呈現(xiàn)出來，而在計算機(jī)的世界里，數(shù)據(jù)是以信號的形式呈現(xiàn)出來的，如電信號、光信號或脈沖信號等，用信號的不同狀態(tài)之間的組合來表示不同的數(shù)據(jù)。二進(jìn)制信號是馮·諾依曼計算機(jī)體系結(jié)構(gòu)中數(shù)據(jù)的表示形式，二進(jìn)制信號是最容易產(chǎn)生的信號形式，如用高電平表示0，低電平表示1，或者用有光信號表示1，沒光信號表示0等。根據(jù)馮·諾依曼計算機(jī)體系結(jié)構(gòu)，首先需要將數(shù)據(jù)存儲在計算機(jī)的內(nèi)存中，計算機(jī)內(nèi)存中表示數(shù)據(jù)的方式是使用線性的二值位串，如“0100100011110110”到底表示了幾個數(shù)據(jù)、表示什么數(shù)據(jù)，需要進(jìn)行事先約定。如果規(guī)定用每8位二進(jìn)制數(shù)表示一個英文字母，那這8位二進(jìn)制數(shù)據(jù)就能表示256個英文字母，而英文字母大小寫一起才52個，因此，用8位來表示英文字母足夠了。如果用8位來表示數(shù)值數(shù)據(jù)，顯然就不夠了。因此，對不同的數(shù)據(jù)就要指定不同的表示方法，于是就有了計算機(jī)程序中不同的數(shù)據(jù)類型。

數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素是指同一種數(shù)據(jù)類型中的單個數(shù)據(jù)，如整數(shù)1是整數(shù)數(shù)據(jù)類型中的一個數(shù)據(jù)元素，某個學(xué)生是“學(xué)生”數(shù)據(jù)類型中的一個數(shù)據(jù)元素，因此，數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)處理的基本數(shù)據(jù)單位。

在數(shù)據(jù)結(jié)構(gòu)中還有一個基本術(shù)語就是數(shù)據(jù)項。一個數(shù)據(jù)元素可能由多個數(shù)據(jù)項組成，如一個學(xué)生數(shù)據(jù)元素包含了學(xué)號、姓名等數(shù)據(jù)項。數(shù)據(jù)項是數(shù)據(jù)結(jié)構(gòu)中處理的最小數(shù)據(jù)單位。

2.數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)

現(xiàn)實問題中的數(shù)據(jù)元素之間的組織可能存在一定的內(nèi)在關(guān)系，這些關(guān)系是數(shù)據(jù)元素之間固有的，稱之為邏輯關(guān)系。有一些數(shù)據(jù)元素之間存在一對一的線性關(guān)系，如一個班的學(xué)生信息一般采用線性表的形式進(jìn)行管理，如下表所示。

有一些數(shù)據(jù)元素之間存在一對多的層次結(jié)構(gòu)關(guān)系，如家譜中的成員一般呈現(xiàn)出一對多的層次結(jié)構(gòu)，如圖1所示。還有一些數(shù)據(jù)元素之間存在著多對多的關(guān)系，如朋友圈中的成員之間就存在著多對多的網(wǎng)狀關(guān)系（如圖2）。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)一般可以在二維平面上用點和邊的形式抽象出來。其中的點就是數(shù)據(jù)元素，邊就是數(shù)據(jù)元素之間存在的某種關(guān)聯(lián)。這種用點和邊抽象出來的二維結(jié)構(gòu)圖形稱為數(shù)據(jù)元素的拓?fù)浣Y(jié)構(gòu)。根據(jù)拓?fù)浣Y(jié)構(gòu)劃分，常見的數(shù)據(jù)邏輯結(jié)構(gòu)有線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。[2]

3.分析數(shù)據(jù)邏輯結(jié)構(gòu)的原因

圖書館的書為什么是按照某種次序排列的？因為圖書館的書很多，而且要對書進(jìn)行頻繁的借閱、歸還和增加書籍等操作，而個人書架本身書不多，對書進(jìn)行的相關(guān)操作也比較少。由此可見，當(dāng)數(shù)據(jù)量比較大，而且要對這些數(shù)據(jù)進(jìn)行大量操作時，有必要對數(shù)據(jù)進(jìn)行組織。那么，如何進(jìn)行組織？這就需要分析數(shù)據(jù)元素之間存在哪些邏輯關(guān)系。例如，圖書有類別、書名、作者、出版時間等屬性，根據(jù)圖書的這些屬性，對圖書進(jìn)行組織，如根據(jù)圖書的類別可以按層次結(jié)構(gòu)組織，按書名、作者、出版時間可以按線性結(jié)構(gòu)組織。

總之，當(dāng)數(shù)據(jù)量很大，而且要對這些數(shù)據(jù)進(jìn)行大量的增、刪、改、查等操作時，對數(shù)據(jù)進(jìn)行合理的組織可以大大提高操作的效率，而分析數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)是對數(shù)據(jù)進(jìn)行合理組織的基礎(chǔ)。

4.數(shù)據(jù)的映射方式

拓?fù)鋱D可以非常直觀地在二維平面上將數(shù)據(jù)元素及數(shù)據(jù)元素之間的關(guān)系表示出來。然而，根據(jù)馮·諾依曼體系結(jié)構(gòu)的原理[3]，計算機(jī)的存儲結(jié)構(gòu)是一種線性結(jié)構(gòu)，如何將二維的拓?fù)浣Y(jié)構(gòu)映射到一維的計算機(jī)存儲器是數(shù)據(jù)結(jié)構(gòu)這門課程研究的一個重要課題。在已有的研究結(jié)果中，映射的方式主要有四種，分別是順序映射、鏈?zhǔn)接成洹⑺饕成浜凸Ｓ成?。根?jù)不同的映射方式，得到數(shù)據(jù)在內(nèi)存中的不同存儲結(jié)構(gòu)，分別稱為順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲結(jié)構(gòu)和哈希存儲結(jié)構(gòu)。

順序映射是將拓?fù)鋱D上的元素先按照一定的規(guī)則排列成一維線性結(jié)構(gòu)，然后將這組線性化以后的數(shù)據(jù)元素按順序存儲在一塊連續(xù)的內(nèi)存空間上。

鏈?zhǔn)接成涫侵笧槊總€數(shù)據(jù)元素增加一個指向與其相關(guān)聯(lián)的元素的指針（一種屬性），每個元素在內(nèi)存中的存放位置可以隨意選擇，但是每次存放一個數(shù)據(jù)元素時，都要在這個數(shù)據(jù)元素的指針上記錄與它關(guān)聯(lián)的數(shù)據(jù)元素在內(nèi)存中的存儲地址。這里的指針屬性就類似于拓?fù)浣Y(jié)構(gòu)中的邊。

索引映射是指專門使用一個表格記錄每個數(shù)據(jù)元素的關(guān)鍵字以及這個數(shù)據(jù)元素在內(nèi)存中的存儲地址。數(shù)據(jù)元素的關(guān)鍵字要求具有唯一性，能唯一地代表一個數(shù)據(jù)元素。與鏈?zhǔn)接成漕愃频氖?，索引映射方式下，?shù)據(jù)元素在內(nèi)存中的存儲位置也是任意的。與鏈?zhǔn)接成涞姆绞讲煌氖?，索引映射是單?dú)用一個表格來對數(shù)據(jù)元素之間的關(guān)系進(jìn)行管理的，而不是為每個數(shù)據(jù)元素設(shè)置一個指針。

哈希映射是指先將每個數(shù)據(jù)元素映射成一個唯一的整數(shù)，然后為這組整數(shù)設(shè)計一個數(shù)學(xué)函數(shù)，這個數(shù)學(xué)函數(shù)被稱為哈希函數(shù)，通過這個哈希函數(shù)將這組整數(shù)均勻地映射到一個指定的整數(shù)范圍內(nèi)（這個范圍與數(shù)據(jù)元素個數(shù)相關(guān)，一般為數(shù)據(jù)元素個數(shù)的1.5倍），如[0，1.5n）這樣的閉開區(qū)間，其中n為數(shù)據(jù)元素的個數(shù)。在內(nèi)存上開辟一塊大小為1.5n的連續(xù)的內(nèi)存空間，按照哈希函數(shù)映射出來的數(shù)字，將每個數(shù)據(jù)元素存儲在這塊內(nèi)存空間的一個確定的位置上。

綜上所述，數(shù)據(jù)結(jié)構(gòu)的本質(zhì)內(nèi)涵是研究現(xiàn)實問題中的數(shù)據(jù)和數(shù)據(jù)之間的邏輯關(guān)系，利用這些關(guān)系在計算機(jī)內(nèi)存中合理地對數(shù)據(jù)進(jìn)行組織，以便實現(xiàn)高效的算法。

5.數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計語言的關(guān)系

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計語言的關(guān)系類似于設(shè)計師與工程師的關(guān)系。數(shù)據(jù)結(jié)構(gòu)的重點是分析事物之間存在的關(guān)聯(lián)，將事物及它們之間的關(guān)聯(lián)抽象成數(shù)據(jù)元素和關(guān)系，設(shè)計出拓?fù)浣Y(jié)構(gòu)圖，進(jìn)而研究如何將拓?fù)浣Y(jié)構(gòu)圖映射到計算機(jī)存儲器中，最終的目的是為了能夠?qū)@些數(shù)據(jù)元素進(jìn)行高效的操作。程序設(shè)計語言是具體工作的執(zhí)行者，它負(fù)責(zé)在計算機(jī)上申請內(nèi)存，將數(shù)據(jù)元素存儲到內(nèi)存中的某個位置上，然后編寫相關(guān)的操作函數(shù)來實現(xiàn)對這組數(shù)據(jù)的操作。

6.數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系

如果把編寫一個計算機(jī)程序比作一場戰(zhàn)役的話，其中的槍支彈藥等武器好比程序中的數(shù)據(jù)，士兵們在戰(zhàn)斗中的作戰(zhàn)方法好比程序中的算法，武器的擺放結(jié)構(gòu)會影響士兵的作戰(zhàn)效率，而士兵的作戰(zhàn)效率最終影響戰(zhàn)役的成敗。因此，數(shù)據(jù)結(jié)構(gòu)的好壞會影響算法的執(zhí)行效率，而算法的執(zhí)行效率決定了一個程序的成敗，這里引用著名計算機(jī)科學(xué)家N·Writh提出的一個公式來總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，那就是“數(shù)據(jù)結(jié)構(gòu)+算法=程序”。[4]

PBL教學(xué)方法

PBL（Proble Based Learning）是一種從實際問題出發(fā)，運(yùn)用教學(xué)內(nèi)容中的知識和技能，一步一步解決實際問題的教學(xué)方法。國際和國內(nèi)的部分高校采用PBL教學(xué)方法以后，在教學(xué)中取得了較好的效果。

實踐證明，在數(shù)據(jù)結(jié)構(gòu)課程中，運(yùn)用PBL教學(xué)方法能夠更好地培養(yǎng)學(xué)生分析問題和解決問題的能力，能夠有效提高學(xué)生的學(xué)習(xí)和編程的興趣。

在數(shù)據(jù)結(jié)構(gòu)課程中運(yùn)用PBL教學(xué)方法的過程為：首先，為每種數(shù)據(jù)結(jié)構(gòu)類型設(shè)計一個以上現(xiàn)實問題的原型，引導(dǎo)學(xué)生找出問題原型中數(shù)據(jù)對象和數(shù)據(jù)元素，結(jié)合要實現(xiàn)的操作，分析和挖掘出數(shù)據(jù)元素之間存在的邏輯關(guān)系，并將這些數(shù)據(jù)元素和它們之間的邏輯關(guān)系抽象成一個拓?fù)浣Y(jié)構(gòu)圖;然后，結(jié)合操作的要求，選擇一種數(shù)據(jù)存儲結(jié)構(gòu);最后，用一種編程語言編寫計算機(jī)程序，將拓?fù)浣Y(jié)構(gòu)圖映射到計算機(jī)的存儲器上，并實現(xiàn)相關(guān)的算法對數(shù)據(jù)進(jìn)行操作，最終完成解決實際問題的目的。

下面筆者以約瑟夫環(huán)為例，說明數(shù)據(jù)結(jié)構(gòu)課程中運(yùn)用PBL教學(xué)方法的過程。

第一步，闡明問題。N個人圍成一個環(huán)，給每個人進(jìn)行編號，從1到N，并且給每個人的手上寫上一個正整數(shù)作為該人的密碼。取出編號為1的人的密碼m，從編號為1的人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將它的密碼作為新的m值，從它的順時針方向的下一個人開始重新從1報數(shù)，如此下去，直至全部人出列為止。最后，按照出列的順序輸出每個人的編號。

第二步，分析數(shù)據(jù)元素。把環(huán)中的每個人抽象成一個數(shù)據(jù)元素。

第三步，分析數(shù)據(jù)元素之間的邏輯關(guān)系。每個數(shù)據(jù)元素有一個前驅(qū)和一個后繼，即一對一的線性關(guān)系。

第四步，分析存儲結(jié)構(gòu)。問題中指出從順時針方向報數(shù)，并且涉及大量的移除操作，因此選擇單向環(huán)形鏈表作為數(shù)據(jù)存儲結(jié)構(gòu)（如圖3）。

第五步，設(shè)計算法。

①創(chuàng)建約瑟夫環(huán)L。

List_create（）

②定位到m處的結(jié)點node。

List_RetrieveNode（&p，m，&

node）;

③將node結(jié)點的密碼賦值給m，并輸出node結(jié)點的id。

m = node-> elem.pwd

print（node-> elem .id）

④查找node的前驅(qū)。

List_prior（&node，&prior）;

⑤如果prior！=node，則大于1個結(jié)點，刪除node。

重復(fù)執(zhí)行（2）-（5）

如果prior==node，則該結(jié)點為最后一個結(jié)點，程序結(jié)束。

⑥使用一種編程語言進(jìn)行實現(xiàn)。

總結(jié)

本文從數(shù)據(jù)結(jié)構(gòu)的本質(zhì)內(nèi)涵出發(fā)，剖析了數(shù)據(jù)的含義及表示方式，分析了數(shù)據(jù)元素之間、數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計語言之間以及數(shù)據(jù)結(jié)構(gòu)與算法之間的關(guān)系。在幫助學(xué)生理解數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的基礎(chǔ)上，利用PBL教學(xué)方法，從實際問題出發(fā)，分析實際問題中的邏輯模型和數(shù)據(jù)結(jié)構(gòu)，設(shè)計相應(yīng)的算法，利用程序設(shè)計語言實現(xiàn)對問題的求解過程。

參考文獻(xiàn)：

[1]王紹強(qiáng).應(yīng)用型本科計算機(jī)網(wǎng)絡(luò)教學(xué)改革的研究與實踐[J].計算機(jī)教育，2009（18）：16-18.

[2]沈良.試論關(guān)于高校計算機(jī)網(wǎng)絡(luò)課程教學(xué)改革的探討[J].企業(yè)導(dǎo)報，2012（11）：194-195.

[3]李杰，青小渠，任堰牛.對比教學(xué)法在單片機(jī)課堂教學(xué)中的應(yīng)用[J].計算機(jī)教育，2014（08）：58-60.

[4]李志華.本科《計算機(jī)網(wǎng)絡(luò)》課程的教學(xué)改革實踐[J].教育教學(xué)論壇，2012（01）：164-165.

作者簡介：劉福泉（1981.12—），女，講師，浙江農(nóng)林大學(xué)暨陽學(xué)院，研究方向為計算機(jī)網(wǎng)絡(luò)、大數(shù)據(jù)、機(jī)器學(xué)習(xí)。