以問題為導向的數據結構課程PBL教學方法研究

摘要：數據結構是計算機專業的核心課程之一，它在計算機專業人才培養中起著舉足輕重的作用。數據結構也是一門被公認的難、廣、多的課程，作者針對數據結構課程的特點，提出了以問題為導向、以實際問題為原型的PBL教學方法。與傳統的教學方法相比，以問題為導向的數據結構課程PBL教學方法能夠更好地培養學生分析問題和解決問題的能力，能夠有效地提高學生的學習興趣和編程能力。

關鍵詞：數據結構;教學方法;引導式

中圖分類號：G642 ?文獻標識碼：B ?論文編號：1674-2117（2021）05-0103-04

困擾學生的問題

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

1.數據的表示

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

數據結構中的數據元素是指同一種數據類型中的單個數據，如整數1是整數數據類型中的一個數據元素，某個學生是“學生”數據類型中的一個數據元素，因此，數據元素是數據結構處理的基本數據單位。

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

2.數據元素之間的邏輯結構

現實問題中的數據元素之間的組織可能存在一定的內在關系，這些關系是數據元素之間固有的，稱之為邏輯關系。有一些數據元素之間存在一對一的線性關系，如一個班的學生信息一般采用線性表的形式進行管理，如下表所示。

有一些數據元素之間存在一對多的層次結構關系，如家譜中的成員一般呈現出一對多的層次結構，如圖1所示。還有一些數據元素之間存在著多對多的關系，如朋友圈中的成員之間就存在著多對多的網狀關系（如圖2）。數據元素之間的邏輯結構一般可以在二維平面上用點和邊的形式抽象出來。其中的點就是數據元素，邊就是數據元素之間存在的某種關聯。這種用點和邊抽象出來的二維結構圖形稱為數據元素的拓撲結構。根據拓撲結構劃分，常見的數據邏輯結構有線性結構、樹型結構和圖型結構。[2]

3.分析數據邏輯結構的原因

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

總之，當數據量很大，而且要對這些數據進行大量的增、刪、改、查等操作時，對數據進行合理的組織可以大大提高操作的效率，而分析數據元素之間的邏輯結構是對數據進行合理組織的基礎。

4.數據的映射方式

拓撲圖可以非常直觀地在二維平面上將數據元素及數據元素之間的關系表示出來。然而，根據馮·諾依曼體系結構的原理[3]，計算機的存儲結構是一種線性結構，如何將二維的拓撲結構映射到一維的計算機存儲器是數據結構這門課程研究的一個重要課題。在已有的研究結果中，映射的方式主要有四種，分別是順序映射、鏈式映射、索引映射和哈希映射。根據不同的映射方式，得到數據在內存中的不同存儲結構，分別稱為順序存儲結構、鏈式存儲結構、索引存儲結構和哈希存儲結構。

順序映射是將拓撲圖上的元素先按照一定的規則排列成一維線性結構，然后將這組線性化以后的數據元素按順序存儲在一塊連續的內存空間上。

鏈式映射是指為每個數據元素增加一個指向與其相關聯的元素的指針（一種屬性），每個元素在內存中的存放位置可以隨意選擇，但是每次存放一個數據元素時，都要在這個數據元素的指針上記錄與它關聯的數據元素在內存中的存儲地址。這里的指針屬性就類似于拓撲結構中的邊。

索引映射是指專門使用一個表格記錄每個數據元素的關鍵字以及這個數據元素在內存中的存儲地址。數據元素的關鍵字要求具有唯一性，能唯一地代表一個數據元素。與鏈式映射類似的是，索引映射方式下，數據元素在內存中的存儲位置也是任意的。與鏈式映射的方式不同的是，索引映射是單獨用一個表格來對數據元素之間的關系進行管理的，而不是為每個數據元素設置一個指針。

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

綜上所述，數據結構的本質內涵是研究現實問題中的數據和數據之間的邏輯關系，利用這些關系在計算機內存中合理地對數據進行組織，以便實現高效的算法。

5.數據結構與程序設計語言的關系

數據結構與程序設計語言的關系類似于設計師與工程師的關系。數據結構的重點是分析事物之間存在的關聯，將事物及它們之間的關聯抽象成數據元素和關系，設計出拓撲結構圖，進而研究如何將拓撲結構圖映射到計算機存儲器中，最終的目的是為了能夠對這些數據元素進行高效的操作。程序設計語言是具體工作的執行者，它負責在計算機上申請內存，將數據元素存儲到內存中的某個位置上，然后編寫相關的操作函數來實現對這組數據的操作。

6.數據結構與算法的關系

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

PBL教學方法

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

實踐證明，在數據結構課程中，運用PBL教學方法能夠更好地培養學生分析問題和解決問題的能力，能夠有效提高學生的學習和編程的興趣。

在數據結構課程中運用PBL教學方法的過程為：首先，為每種數據結構類型設計一個以上現實問題的原型，引導學生找出問題原型中數據對象和數據元素，結合要實現的操作，分析和挖掘出數據元素之間存在的邏輯關系，并將這些數據元素和它們之間的邏輯關系抽象成一個拓撲結構圖;然后，結合操作的要求，選擇一種數據存儲結構;最后，用一種編程語言編寫計算機程序，將拓撲結構圖映射到計算機的存儲器上，并實現相關的算法對數據進行操作，最終完成解決實際問題的目的。

下面筆者以約瑟夫環為例，說明數據結構課程中運用PBL教學方法的過程。

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

第二步，分析數據元素。把環中的每個人抽象成一個數據元素。

第三步，分析數據元素之間的邏輯關系。每個數據元素有一個前驅和一個后繼，即一對一的線性關系。

第四步，分析存儲結構。問題中指出從順時針方向報數，并且涉及大量的移除操作，因此選擇單向環形鏈表作為數據存儲結構（如圖3）。

第五步，設計算法。

①創建約瑟夫環L。

List_create（）

②定位到m處的結點node。

List_RetrieveNode（&p，m，&

node）;

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

m = node-> elem.pwd

print（node-> elem .id）

④查找node的前驅。

List_prior（&node，&prior）;

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

重復執行（2）-（5）

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

⑥使用一種編程語言進行實現。

總結

本文從數據結構的本質內涵出發，剖析了數據的含義及表示方式，分析了數據元素之間、數據結構與程序設計語言之間以及數據結構與算法之間的關系。在幫助學生理解數據結構內涵的基礎上，利用PBL教學方法，從實際問題出發，分析實際問題中的邏輯模型和數據結構，設計相應的算法，利用程序設計語言實現對問題的求解過程。

參考文獻：

[1]王紹強.應用型本科計算機網絡教學改革的研究與實踐[J].計算機教育，2009（18）：16-18.

[2]沈良.試論關于高校計算機網絡課程教學改革的探討[J].企業導報，2012（11）：194-195.

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

[4]李志華.本科《計算機網絡》課程的教學改革實踐[J].教育教學論壇，2012（01）：164-165.

作者簡介：劉福泉（1981.12—），女，講師，浙江農林大學暨陽學院，研究方向為計算機網絡、大數據、機器學習。