摘要：本文針對數(shù)據(jù)結(jié)構(gòu)課程的特點(diǎn)，提出了以問題為導(dǎo)向、以實(shí)際問題為原型的PBL教學(xué)方法。同時(shí)提出，相對于傳統(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)式;PBL;算法

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

困擾學(xué)生的問題

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

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

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

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

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

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

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

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

總之，當(dāng)數(shù)據(jù)量很大，而且對這些數(shù)據(jù)要進(jìn)行大量的增、刪、改、查等操作時(shí)，合理地對數(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)的原理[2]，計(jì)算機(jī)的存儲結(jié)構(gòu)是一種線性結(jié)構(gòu)，如何將二維的拓?fù)浣Y(jié)構(gòu)映射到一維的計(jì)算機(jī)存儲器是數(shù)據(jù)結(jié)構(gòu)這門課程研究的一個(gè)重要課題。在已有的研究結(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)接成涫侵笧槊總€(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)存中的存儲地址。這里的指針屬性就類似于拓?fù)浣Y(jié)構(gòu)中的邊。

索引映射是指專門使用一個(gè)表格記錄每個(gè)數(shù)據(jù)元素的關(guān)鍵字以及這個(gè)數(shù)據(jù)元素在內(nèi)存中的存儲地址。數(shù)據(jù)元素的關(guān)鍵字要求具有唯一性，能唯一地代表一個(gè)數(shù)據(jù)元素。與鏈?zhǔn)接成漕愃频氖?，在索引映射方式下，?shù)據(jù)元素在內(nèi)存中的存儲位置也是任意的。與鏈?zhǔn)接成浞绞讲煌氖牵饕成涫菃为?dú)用一個(gè)表格來對數(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ù)被稱為哈希函數(shù)，通過這個(gè)哈希函數(shù)將這組整數(shù)均勻地映射到一個(gè)指定的整數(shù)范圍內(nèi)（這個(gè)范圍與數(shù)據(jù)元素個(gè)數(shù)相關(guān)，一般為數(shù)據(jù)元素個(gè)數(shù)的1.5倍），如[0，1.5n）這樣的閉開區(qū)間，其中n為數(shù)據(jù)元素的個(gè)數(shù)。在內(nèi)存上開辟一塊大小為1.5n的連續(xù)的內(nèi)存空間，按照哈希函數(shù)映射出來的數(shù)字，將每個(gè)數(shù)據(jù)元素存儲在這塊內(nèi)存空間的一個(gè)確定的位置上。

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

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

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)語言的關(guān)系類似于設(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ī)存儲器中，最終的目的是能夠?qū)@些數(shù)據(jù)元素進(jìn)行高效地操作。程序設(shè)計(jì)語言是具體工作的執(zhí)行者，它負(fù)責(zé)在計(jì)算機(jī)上申請內(nèi)存，將數(shù)據(jù)元素存儲到內(nèi)存中的某個(gè)位置上，然后編寫相關(guān)的操作函數(shù)來實(shí)現(xiàn)對這組數(shù)據(jù)的操作。

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

如果把編寫一個(gè)計(jì)算機(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í)行效率決定了一個(gè)程序的成敗，這里引用著名計(jì)算機(jī)科學(xué)家N.Writh提出的一個(gè)公式來總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，那就是“數(shù)據(jù)結(jié)構(gòu)+算法=程序”。[3]

PBL教學(xué)方法

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

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

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

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

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

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

第四步，分析存儲結(jié)構(gòu)。問題中指出從順時(shí)針方向報(bào)數(shù)，并且涉及大量的移除操作，因此選擇單向環(huán)形鏈表作為數(shù)據(jù)存儲結(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é)束。

第六步，使用一種編程語言進(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ì)語言之間以及數(shù)據(jù)結(jié)構(gòu)與算法之間存在的關(guān)系。在幫助學(xué)生理解數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的基礎(chǔ)上，利用PBL教學(xué)方法，從實(shí)際問題出發(fā)，分析實(shí)際問題中的邏輯模型和數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)的算法，利用程序設(shè)計(jì)語言實(shí)現(xiàn)對問題的求解過程。

參考文獻(xiàn)：

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

[2]李杰，青小渠，任堰牛.對比教學(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.

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