摘要：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的核心課程之一，它在計(jì)算機(jī)專業(yè)人才培養(yǎng)中起著舉足輕重的作用。數(shù)據(jù)結(jié)構(gòu)也是一門被公認(rèn)的難、廣、多的課程，作者針對(duì)數(shù)據(jù)結(jié)構(gòu)課程的特點(diǎn)，提出了以問題為導(dǎo)向、以實(shí)際問題為原型的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)式

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

困擾學(xué)生的問題

“數(shù)據(jù)結(jié)構(gòu)”是一門被公認(rèn)的難、廣、多的課程，其中的“難”表示理解難，“廣”表示算法廣，“多”表示內(nèi)容多。對(duì)于初學(xué)者來說，往往有一系列的問題困擾著他們，如什么是數(shù)據(jù)，如何表示數(shù)據(jù)，數(shù)據(jù)之間存在哪些邏輯關(guān)聯(lián)，如何利用數(shù)據(jù)元素之間的邏輯關(guān)聯(lián)關(guān)系組織數(shù)據(jù)以便高效地對(duì)數(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ì)算機(jī)程序的實(shí)質(zhì)是對(duì)信息的處理，也就是對(duì)數(shù)據(jù)進(jìn)行處理。在現(xiàn)實(shí)世界中，數(shù)據(jù)往往以文字的形式呈現(xiàn)出來，而在計(jì)算機(jī)的世界里，數(shù)據(jù)是以信號(hào)的形式呈現(xiàn)出來的，如電信號(hào)、光信號(hào)或脈沖信號(hào)等，用信號(hào)的不同狀態(tài)之間的組合來表示不同的數(shù)據(jù)。二進(jìn)制信號(hào)是馮·諾依曼計(jì)算機(jī)體系結(jié)構(gòu)中數(shù)據(jù)的表示形式，二進(jìn)制信號(hào)是最容易產(chǎn)生的信號(hào)形式，如用高電平表示0，低電平表示1，或者用有光信號(hào)表示1，沒光信號(hào)表示0等。根據(jù)馮·諾依曼計(jì)算機(jī)體系結(jié)構(gòu)，首先需要將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)的內(nèi)存中，計(jì)算機(jī)內(nèi)存中表示數(shù)據(jù)的方式是使用線性的二值位串，如“0100100011110110”到底表示了幾個(gè)數(shù)據(jù)、表示什么數(shù)據(jù)，需要進(jìn)行事先約定。如果規(guī)定用每8位二進(jìn)制數(shù)表示一個(gè)英文字母，那這8位二進(jìn)制數(shù)據(jù)就能表示256個(gè)英文字母，而英文字母大小寫一起才52個(gè)，因此，用8位來表示英文字母足夠了。如果用8位來表示數(shù)值數(shù)據(jù)，顯然就不夠了。因此，對(duì)不同的數(shù)據(jù)就要指定不同的表示方法，于是就有了計(jì)算機(jī)程序中不同的數(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é)號(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í)問題中的數(shù)據(jù)元素之間的組織可能存在一定的內(nèi)在關(guān)系，這些關(guān)系是數(shù)據(jù)元素之間固有的，稱之為邏輯關(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)，如圖1所示。還有一些數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，如朋友圈中的成員之間就存在著多對(duì)多的網(wǎng)狀關(guān)系（如圖2）。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)一般可以在二維平面上用點(diǎn)和邊的形式抽象出來。其中的點(diǎn)就是數(shù)據(jù)元素，邊就是數(shù)據(jù)元素之間存在的某種關(guān)聯(lián)。這種用點(diǎ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)的原因

圖書館的書為什么是按照某種次序排列的？因?yàn)閳D書館的書很多，而且要對(duì)書進(jìn)行頻繁的借閱、歸還和增加書籍等操作，而個(gè)人書架本身書不多，對(duì)書進(jìn)行的相關(guān)操作也比較少。由此可見，當(dāng)數(shù)據(jù)量比較大，而且要對(duì)這些數(shù)據(jù)進(jìn)行大量操作時(shí)，有必要對(duì)數(shù)據(jù)進(jìn)行組織。那么，如何進(jìn)行組織？這就需要分析數(shù)據(jù)元素之間存在哪些邏輯關(guān)系。例如，圖書有類別、書名、作者、出版時(shí)間等屬性，根據(jù)圖書的這些屬性，對(duì)圖書進(jìn)行組織，如根據(jù)圖書的類別可以按層次結(jié)構(gòu)組織，按書名、作者、出版時(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)系表示出來。然而，根據(jù)馮·諾依曼體系結(jié)構(gòu)的原理[3]，計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)是一種線性結(jié)構(gòu)，如何將二維的拓?fù)浣Y(jié)構(gòu)映射到一維的計(jì)算機(jī)存儲(chǔ)器是數(shù)據(jù)結(jié)構(gòu)這門課程研究的一個(gè)重要課題。在已有的研究結(jié)果中，映射的方式主要有四種，分別是順序映射、鏈?zhǔn)接成洹⑺饕成浜凸Ｓ成?。根?jù)不同的映射方式，得到數(shù)據(jù)在內(nèi)存中的不同存儲(chǔ)結(jié)構(gòu)，分別稱為順序存儲(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ǔ)地址。這里的指針屬性就類似于拓?fù)浣Y(jié)構(gòu)中的邊。

索引映射是指專門使用一個(gè)表格記錄每個(gè)數(shù)據(jù)元素的關(guān)鍵字以及這個(gè)數(shù)據(jù)元素在內(nèi)存中的存儲(chǔ)地址。數(shù)據(jù)元素的關(guān)鍵字要求具有唯一性，能唯一地代表一個(gè)數(shù)據(jù)元素。與鏈?zhǔn)接成漕愃频氖?，索引映射方式下，?shù)據(jù)元素在內(nèi)存中的存儲(chǔ)位置也是任意的。與鏈?zhǔn)接成涞姆绞讲煌氖牵饕成涫菃为?dú)用一個(gè)表格來對(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ù)被稱為哈希函數(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ù)元素存儲(chǔ)在這塊內(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)存中合理地對(duì)數(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ī)存儲(chǔ)器中，最終的目的是為了能夠?qū)@些數(shù)據(jù)元素進(jìn)行高效的操作。程序設(shè)計(jì)語言是具體工作的執(zhí)行者，它負(fù)責(zé)在計(jì)算機(jī)上申請(qǐng)內(nèi)存，將數(shù)據(jù)元素存儲(chǔ)到內(nèi)存中的某個(gè)位置上，然后編寫相關(guān)的操作函數(shù)來實(shí)現(xiàn)對(duì)這組數(shù)據(jù)的操作。

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

如果把編寫一個(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è)公式來總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系，那就是“數(shù)據(jù)結(jié)構(gòu)+算法=程序”。[4]

PBL教學(xué)方法

PBL（Proble Based Learning）是一種從實(shí)際問題出發(fā)，運(yùn)用教學(xué)內(nèi)容中的知識(shí)和技能，一步一步解決實(shí)際問題的教學(xué)方法。國際和國內(nèi)的部分高校采用PBL教學(xué)方法以后，在教學(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ù)對(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);最后，用一種編程語言編寫計(jì)算機(jī)程序，將拓?fù)浣Y(jié)構(gòu)圖映射到計(jì)算機(jī)的存儲(chǔ)器上，并實(shí)現(xiàn)相關(guān)的算法對(duì)數(shù)據(jù)進(jìn)行操作，最終完成解決實(shí)際問題的目的。

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

第一步，闡明問題。N個(gè)人圍成一個(gè)環(huán)，給每個(gè)人進(jìn)行編號(hào)，從1到N，并且給每個(gè)人的手上寫上一個(gè)正整數(shù)作為該人的密碼。取出編號(hào)為1的人的密碼m，從編號(hào)為1的人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將它的密碼作為新的m值，從它的順時(shí)針方向的下一個(gè)人開始重新從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)。問題中指出從順時(shí)針方向報(bào)數(shù)，并且涉及大量的移除操作，因此選擇單向環(huán)形鏈表作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（如圖3）。

第五步，設(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。

m = node-> elem.pwd

print（node-> elem .id）

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

List_prior（&node，&prior）;

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

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

如果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)對(duì)問題的求解過程。

參考文獻(xiàn)：

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

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

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

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

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