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

摘要：本文針對(duì)數(shù)據(jù)結(jié)構(gòu)課程的特點(diǎn)，提出了以問(wèn)題為導(dǎo)向、以實(shí)際問(wèn)題為原型的PBL教學(xué)方法。同時(shí)提出，相對(duì)于傳統(tǒng)的教學(xué)方法，以問(wèn)題為導(dǎo)向的數(shù)據(jù)結(jié)構(gòu)課程PBL教學(xué)方法能夠更好地培養(yǎng)學(xué)生分析問(wèn)題和解決問(wèn)題的能力，能夠有效地提高學(xué)生的學(xué)習(xí)興趣和編程能力。

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

中圖分類(lèi)號(hào)：G434? 文獻(xiàn)標(biāo)識(shí)碼：A? 論文編號(hào)：1674-2117（2022）14-0090-03

困擾學(xué)生的問(wèn)題

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)的核心課程之一，也是一門(mén)被公認(rèn)的難、廣、多的課程，其中的“難”表示理解難，“廣”表示算法廣，“多”表示內(nèi)容多。對(duì)初學(xué)者來(lái)說(shuō)，往往有一系列的問(wèn)題困擾著他們，如什么是數(shù)據(jù)、如何表示數(shù)據(jù)、數(shù)據(jù)之間存在哪些邏輯關(guān)聯(lián)等。筆者認(rèn)為，要想讓學(xué)生學(xué)好這門(mén)課程，首先須幫助學(xué)生解開(kāi)這些疑問(wèn)。

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

數(shù)據(jù)是信息的表示形式，在現(xiàn)實(shí)世界中，數(shù)據(jù)往往以文字的形式呈現(xiàn)出來(lái)，而在計(jì)算機(jī)的世界里，數(shù)據(jù)是以信號(hào)的形式呈現(xiàn)出來(lái)的，如電信號(hào)、光信號(hào)或脈沖信號(hào)等，用信號(hào)的不同狀態(tài)之間的組合來(lái)表示不同的數(shù)據(jù)。在數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素是指同一種數(shù)據(jù)類(lèi)型中的單個(gè)數(shù)據(jù)，如整數(shù)1是整數(shù)數(shù)據(jù)類(lèi)型中的一個(gè)數(shù)據(jù)元素，某個(gè)學(xué)生是“學(xué)生”數(shù)據(jù)類(lèi)型中的一個(gè)數(shù)據(jù)元素，因此數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)處理的基本數(shù)據(jù)單位。

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

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

現(xiàn)實(shí)問(wèn)題中的數(shù)據(jù)元素之間的組織存在一定的內(nèi)在關(guān)系，這些關(guān)系是數(shù)據(jù)元素之間固有的，被稱(chēng)為邏輯關(guān)系。例如，有一些數(shù)據(jù)元素之間存在一對(duì)一的線性關(guān)系，如一個(gè)班的學(xué)生信息一般采用線性表的形式進(jìn)行管理;有一些數(shù)據(jù)元素之間存在一對(duì)多的層次結(jié)構(gòu)關(guān)系，如家譜中的成員一般呈現(xiàn)出一對(duì)多的層次結(jié)構(gòu);還有一些數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，如朋友圈中的成員之間就存在著多對(duì)多的網(wǎng)狀關(guān)系。根據(jù)拓?fù)浣Y(jié)構(gòu)劃分，常見(jiàn)的數(shù)據(jù)邏輯結(jié)構(gòu)有線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)。[1]

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

為什么要分析數(shù)據(jù)元素之間存在的邏輯結(jié)構(gòu)呢？這里先來(lái)看一個(gè)簡(jiǎn)單的例子。相信每個(gè)人都有去圖書(shū)館借書(shū)的經(jīng)歷，只要觀察就能夠發(fā)現(xiàn)，圖書(shū)館的書(shū)是按照某種次序排列的。為什么會(huì)這樣呢？因?yàn)閳D書(shū)館的書(shū)很多，而且要對(duì)書(shū)進(jìn)行頻繁的借閱、歸還和增加書(shū)籍等操作。當(dāng)數(shù)據(jù)量比較大，而且要對(duì)這些數(shù)據(jù)進(jìn)行大量操作時(shí)，就有必要對(duì)數(shù)據(jù)進(jìn)行組織。那么，如何進(jìn)行組織呢？這就要分析數(shù)據(jù)元素之間存在哪些邏輯關(guān)系。對(duì)于圖書(shū)來(lái)說(shuō)，圖書(shū)有類(lèi)別、書(shū)名、作者、出版時(shí)間等屬性，可根據(jù)圖書(shū)的這些屬性對(duì)圖書(shū)進(jìn)行組織，如根據(jù)圖書(shū)的類(lèi)別可以按層次結(jié)構(gòu)組織，根據(jù)書(shū)名、作者、出版時(shí)間可以按線性結(jié)構(gòu)組織。

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

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

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

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

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

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

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

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

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

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

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

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

PBL教學(xué)方法

PBL是Proble Based Learning的首字母縮寫(xiě)，它是一種從實(shí)際問(wèn)題出發(fā)，運(yùn)用教學(xué)內(nèi)容中的知識(shí)和技能，一步一步解決實(shí)際問(wèn)題的教學(xué)方法。

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

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

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

第一步，闡明問(wèn)題。N個(gè)人圍成一個(gè)環(huán)，給每個(gè)人進(jìn)行編號(hào)，從1到N，并且給每個(gè)人的手上寫(xiě)上一個(gè)正整數(shù)作為該人的密碼。取出編號(hào)為1的人的密碼m，從編號(hào)為1的人開(kāi)始按順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將它的密碼作為新的m值，從它的順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直至全部人出列為止。最后按照出列的順序輸出每個(gè)人的編號(hào)。

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

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

第四步，分析存儲(chǔ)結(jié)構(gòu)。問(wèn)題中指出從順時(shí)針?lè)较驁?bào)數(shù)，并且涉及大量的移除操作，因此選擇單向環(huán)形鏈表作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，代碼如圖1所示。

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

①創(chuàng)建約瑟夫環(huán)L：List_create（）;

②定位到m處的結(jié)點(diǎn)node：List_RetrieveNode（&p，m，&node）;

③將node結(jié)點(diǎn)的密碼賦值給m，并輸出node結(jié)點(diǎn)的id（如圖2）;

④查找node的前驅(qū)：List_prior（&node，&prior）;

⑤如果prior！=node，則大于1個(gè)結(jié)點(diǎn)，刪除node，重復(fù)執(zhí)行②到⑤;如果prior==node，則該結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)，程序結(jié)束。

第六步，使用一種編程語(yǔ)言進(jìn)行實(shí)現(xiàn)。

總結(jié)

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

參考文獻(xiàn)：

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

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

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

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