數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與應(yīng)用

1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)與應(yīng)用史娜(黑龍江林業(yè)職業(yè)技術(shù)學(xué)院信息工程系，黑龍江牡丹江157011)摘要：數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)、物理存儲(chǔ)結(jié)構(gòu)及算法的封裝，本文從這三個(gè)方面討論如何應(yīng)用數(shù)據(jù)結(jié)構(gòu)解決非數(shù)值計(jì)算的實(shí)際問(wèn)題，并用具體實(shí)例說(shuō)明數(shù)據(jù)結(jié)構(gòu)的應(yīng)用。關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；棧；邏輯結(jié)構(gòu)中圖分類號(hào)：TP31112文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1007—9599(2013)06—0197—021什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一種具有一定邏輯關(guān)系，在計(jì)算機(jī)中應(yīng)用某種存儲(chǔ)結(jié)

2、構(gòu)，并且封裝了相應(yīng)操作的數(shù)據(jù)元素的集合。它包含三方面的內(nèi)容，邏輯關(guān)系、存儲(chǔ)關(guān)系以及操作。數(shù)據(jù)的邏輯結(jié)構(gòu)大致上可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，其特點(diǎn)是除了開(kāi)頭和最后一個(gè)節(jié)點(diǎn)外，其他的任意一個(gè)節(jié)點(diǎn)都只有一個(gè)直接前驅(qū)節(jié)點(diǎn)后后繼節(jié)點(diǎn)。線性結(jié)構(gòu)主要包括有線性表、棧和隊(duì)列。樹(shù)、集合、圖都是非線性結(jié)構(gòu)，其中樹(shù)形結(jié)構(gòu)模擬層次，圖形結(jié)構(gòu)模擬對(duì)稱和非對(duì)稱關(guān)系。研究數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的需要，是為了使得程序設(shè)計(jì)更加的健壯、

3、高效，使得程序的開(kāi)發(fā)更加的方便。2如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)應(yīng)用數(shù)據(jù)結(jié)構(gòu)解決生活中的問(wèn)題的首要前提是研究應(yīng)用什么數(shù)據(jù)結(jié)構(gòu)解決生活中的問(wèn)題。其分析步驟為：首先分析任務(wù)中的操作對(duì)象，即找出任務(wù)中涉及到的數(shù)據(jù)，從中總結(jié)和抽象出操作對(duì)象，并且分析操作對(duì)象之間的邏輯關(guān)系；其次根據(jù)任務(wù)中對(duì)操作對(duì)象的操作，研究應(yīng)用何種存儲(chǔ)方式來(lái)存儲(chǔ)數(shù)據(jù)才能高效的執(zhí)行程序并且占用較小的存儲(chǔ)空間。選擇數(shù)據(jù)結(jié)構(gòu)的接口要最接近軟件的需求。通常當(dāng)有多個(gè)滿足需要的接口數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)時(shí)

4、，可以根據(jù)比較他們的接口操作的運(yùn)行時(shí)間以及數(shù)據(jù)結(jié)構(gòu)消耗的空間來(lái)進(jìn)行選擇，有的時(shí)候時(shí)間和空間可以相互轉(zhuǎn)換，比如可以用空間來(lái)交換操作的效率；最后在物理存儲(chǔ)方式的基礎(chǔ)上設(shè)計(jì)正確的算法實(shí)現(xiàn)操作，完成任務(wù)。生活中所要處理的數(shù)據(jù)之間可以抽象出來(lái)不同的邏輯關(guān)系，建立不同的數(shù)據(jù)結(jié)構(gòu)，但是針對(duì)實(shí)際問(wèn)題要從中選取能夠準(zhǔn)確描述問(wèn)題的基本特性并且易于實(shí)現(xiàn)的邏輯結(jié)構(gòu)。例如八枚硬幣中其中有一枚硬幣是較為輕的，要求用一個(gè)天平將這枚輕的硬幣判斷出來(lái)，判斷的過(guò)程采用將硬

5、幣分析兩組或者三組，分別使用天平比較的方式來(lái)判斷。這一判斷過(guò)程可以用一個(gè)樹(shù)形圖來(lái)表示，所以可以將該問(wèn)題抽象為判定樹(shù)，構(gòu)建樹(shù)形結(jié)構(gòu)。根據(jù)選定的數(shù)據(jù)結(jié)構(gòu)可以用不同的存儲(chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。不同類型的數(shù)據(jù)結(jié)構(gòu)常用的存儲(chǔ)結(jié)構(gòu)為順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)及索引存儲(chǔ)結(jié)構(gòu)。不同的存儲(chǔ)結(jié)構(gòu)具有不同的特點(diǎn)，大致上存在的差異在存儲(chǔ)空間和運(yùn)算效率兩個(gè)方面。例如線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在存儲(chǔ)空間上來(lái)對(duì)比，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)顯然要多占用一部分存儲(chǔ)空間。

6、從運(yùn)算效率上來(lái)對(duì)比，如果線性表需要進(jìn)197lComputerCDSoftwareandApplications行大量的插入和刪除操作的話，那么鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)從執(zhí)行效率上來(lái)講要占有優(yōu)勢(shì)。而如果線性表要反復(fù)進(jìn)行查詢操作的話，順序存儲(chǔ)結(jié)構(gòu)具備隨機(jī)讀寫的特點(diǎn)，就比較適合這種情況。確定數(shù)據(jù)的邏輯關(guān)系與存儲(chǔ)結(jié)構(gòu)的情況下，可以設(shè)計(jì)出不同的算法來(lái)實(shí)現(xiàn)應(yīng)用。設(shè)計(jì)的算法應(yīng)該是正確的算法。正確的算法的含義是：能夠解決實(shí)際問(wèn)題，輸入的所有可能的合法的輸入都能產(chǎn)生

7、預(yù)期的正確的結(jié)果；能夠在有窮的步驟內(nèi)執(zhí)行完程序；能夠用最簡(jiǎn)短的語(yǔ)句最高效的完成任務(wù)。3應(yīng)用數(shù)據(jù)結(jié)構(gòu)解決表達(dá)式中括號(hào)匹配問(wèn)題31抽象數(shù)據(jù)的邏輯結(jié)構(gòu)在此問(wèn)題中操作對(duì)象為表達(dá)式的括號(hào)，括號(hào)的匹配的表達(dá)式都具有這樣的特點(diǎn)：在從左至右掃描表達(dá)式的過(guò)程中，最先掃描到的右括號(hào)必定與之前最后掃描到的左括號(hào)相匹配。根據(jù)這特點(diǎn)及棧的先進(jìn)后出的特點(diǎn)可以將表達(dá)式抽象成棧，表達(dá)式中的左、右括號(hào)為棧中的數(shù)據(jù)元素。并且該邏輯結(jié)構(gòu)具有出棧及入棧的操作能夠滿足任務(wù)的需求

8、。32選用存儲(chǔ)數(shù)據(jù)的物理結(jié)構(gòu)順序棧占用存儲(chǔ)空間小，不浪費(fèi)空間，同時(shí)進(jìn)棧與出棧操作程序執(zhí)行效率高。所以解決該問(wèn)題可采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)棧。順序棧的特點(diǎn)是：用一組連續(xù)的空間存放自棧底到棧頂?shù)臄?shù)據(jù)元素。數(shù)據(jù)元素之間存在線性關(guān)系，第一個(gè)入棧的數(shù)據(jù)元素稱為棧底元素，最后一個(gè)入棧的數(shù)據(jù)元素稱為棧項(xiàng)元素，用指針TOP標(biāo)志。順序棧的基本操作包括：創(chuàng)建一個(gè)空棧、判斷棧是否為滿、判斷棧是否為空、得出棧的長(zhǎng)度、入棧、出棧、返回棧頂元素。如圖所示：：f棧頂一a

9、ntop棧s=(a1，a2，’a)I～—a2棧a1棧順序棧入棧操作的實(shí)現(xiàn)步驟為：判斷如果棧已滿，返回false，不允許入棧(下轉(zhuǎn)第199頁(yè))CCDSAA存本學(xué)年的課表文檔。根據(jù)排課系統(tǒng)的需求，結(jié)合各個(gè)院’系班級(jí)的情況以及任課老師的分配，由于錄入數(shù)據(jù)比較龐大，因此需要在系統(tǒng)中裝載數(shù)據(jù)模塊，完成了這個(gè)預(yù)備工作后在開(kāi)始執(zhí)行程序語(yǔ)言運(yùn)行。排課系統(tǒng)需要涵蓋班級(jí)、教師、用戶管理多個(gè)模塊，而且需要在每一個(gè)大的功能模塊下分派數(shù)目不等的子模塊，以此來(lái)減少

10、教務(wù)人員工作的難度，同時(shí)也可以方便用戶隨時(shí)在互聯(lián)網(wǎng)上查詢或下載課表。41基本信息設(shè)置模塊(1)班級(jí)設(shè)置模塊?！鞍嗉?jí)設(shè)置”模塊負(fù)責(zé)維護(hù)班級(jí)信息。班級(jí)信息設(shè)置模塊包括班級(jí)所在院系，班級(jí)每學(xué)年課程節(jié)數(shù)，班級(jí)學(xué)生人數(shù)，班級(jí)班主任基本情況等。(2)課程設(shè)置模塊?！罢n程設(shè)置”模塊負(fù)責(zé)維護(hù)學(xué)校的課程信息，課程信息設(shè)置項(xiàng)包括專業(yè)課程名稱，課程每學(xué)年安排多少個(gè)課時(shí)，每周有多少節(jié)，是否分單雙周上課，任課教師情況等。(3)教師設(shè)置模塊。計(jì)算機(jī)系統(tǒng)對(duì)教師設(shè)置模

11、塊的設(shè)計(jì)主要解決教師信息維護(hù)的問(wèn)題，包括任課老師的姓名、電話、郵箱等基本信息，以及任課時(shí)間與地點(diǎn)的統(tǒng)計(jì)。此版塊的功能同樣可以根據(jù)需要添加或是刪除信息等。42用戶管理設(shè)置模塊用戶管理設(shè)置板塊是編寫用戶的基本信息，包括用戶身份認(rèn)證、名稱、類別、密碼等。用戶管理模塊的作用是保證用戶信息添加、刪除、修改的維護(hù)工作，此外用戶管理要對(duì)對(duì)不同用戶權(quán)限做出審查，同時(shí)，判斷該用戶是對(duì)數(shù)據(jù)庫(kù)的訪問(wèn)權(quán)限達(dá)到限制額，這樣做的目的是保證用戶在使用過(guò)程中的信息安全

12、。用戶管理是對(duì)用戶信息進(jìn)行添加、修改、刪除和查看，并對(duì)用戶信息的這些方面進(jìn)行維護(hù)?；静僮髁鞒蹋菏紫?，點(diǎn)擊添加新用戶，填寫用戶信息點(diǎn)擊提交，添加新用戶成功。其次，刪除選擇要?jiǎng)h除的用戶，點(diǎn)擊確定，刪除用戶。再次，修改用戶信息，點(diǎn)擊修改用戶信息，選擇要修改的用戶，點(diǎn)擊確定，提交修改。5結(jié)論高校各個(gè)學(xué)年開(kāi)課之前必然需要排好課表，排課任務(wù)重要并且復(fù)雜，是高校教務(wù)管理工作的難題。排課的目的在于保證學(xué)生上課有合適的地點(diǎn)，老師有互不沖突的教學(xué)時(shí)間，從

13、而使每學(xué)期的教學(xué)工作能夠有秩序的展開(kāi)。在計(jì)算機(jī)系統(tǒng)廣泛應(yīng)用之前，處理數(shù)據(jù)以及管理排課日程由教務(wù)人員手工操作，任務(wù)繁瑣，容易出錯(cuò)，出錯(cuò)之后難以及時(shí)更改，造成各種麻煩，嚴(yán)重影響教學(xué)效率。面向?qū)ο缶幊陶Z(yǔ)言VBNET，不僅十分輕松的完成編寫任務(wù)，在代碼輸入上也大大簡(jiǎn)化了工作程序，并且這種語(yǔ)言完全面向?qū)ο?，代碼維護(hù)方便容易，解決原先不能及時(shí)更改錯(cuò)誤的難題。本文的主要工作是基于面向?qū)ο缶幊陶Z(yǔ)言VBNET，以設(shè)計(jì)高校課程安排管理系統(tǒng)的需求為目的，設(shè)計(jì)

14、并實(shí)現(xiàn)了包括教室安排、班級(jí)管理、課程設(shè)置、教師設(shè)置、用戶管理四個(gè)功能模塊的高校排課管理系統(tǒng)，該系統(tǒng)的實(shí)現(xiàn)有利于提高工作效率，實(shí)現(xiàn)排課系統(tǒng)管理的信息化和標(biāo)準(zhǔn)。參考文獻(xiàn)：[1]李英杰VBNET2005程序設(shè)計(jì)實(shí)例教程嗍天津：天津大學(xué)出版社，2008，11f2】郭瑞軍，王松VisualBasicNET數(shù)據(jù)庫(kù)開(kāi)發(fā)實(shí)例精粹[M】北京：電子工業(yè)出版社，2006(5)：34—59[3]孫雪蓮，馮毅夫基于B／S模式下的高校食堂管理系統(tǒng)設(shè)計(jì)吉林師范大學(xué)學(xué)

15、報(bào)(自然科學(xué)版)，2005，11[4]李春葆VBNET2005程序設(shè)計(jì)教程北京：清華大學(xué)出版社，2009，2[5]龔輝鋒，趙玉意，秦立公基于vB6與Excel的物流軟件的開(kāi)發(fā)構(gòu)想中國(guó)管理信息化Ⅱ】2008，12(上接第197頁(yè))若棧不滿，將棧頂指針top1數(shù)據(jù)element存入top所指的空間中操作成功返回true順序棧出棧操作的實(shí)現(xiàn)步驟為：判斷順序棧狀態(tài)，如果棧已空，不允許出棧若棧不空，取出棧頂指針top所指的內(nèi)容棧頂指針top1，指

16、向下一個(gè)元素返回出棧數(shù)據(jù)3_3算法描述關(guān)于括號(hào)匹配的操作是這樣進(jìn)行的：(1)將輸入的表達(dá)式按序存入數(shù)組，掃描整個(gè)數(shù)組，遇到左括號(hào)都進(jìn)行棧(2)遇到右括號(hào)①先進(jìn)行判空，若是空棧，則一個(gè)右括號(hào)入棧后一定是不匹配的199lComputerCDSoftwareandApplications②如果判空后不是空棧，那么就把棧里的括號(hào)彈出并與遇到的第一個(gè)右括號(hào)進(jìn)行匹配判斷，若匹配則繼續(xù)執(zhí)行步驟1、2，若不匹配則整個(gè)表達(dá)式也不匹配。(3)當(dāng)進(jìn)行完上面得

17、操作后，如果棧不為空，那就說(shuō)明肯定還有括號(hào)留在棧中，那一定就是不匹配了。若整個(gè)表達(dá)式掃描完畢，棧也為空，則說(shuō)明表達(dá)式中括號(hào)匹配。參考文獻(xiàn)：【1]李素萍，郭純真數(shù)據(jù)結(jié)構(gòu)的分析與應(yīng)用U]北京教育學(xué)院學(xué)報(bào)(自然科學(xué)版)，2006，10[2]王瑜數(shù)據(jù)結(jié)構(gòu)中向量、棧的應(yīng)用Ⅱ】德宏教育學(xué)院學(xué)報(bào)，20101[作者簡(jiǎn)介]史娜(19801118)，女，漢族，黑龍江雞西地區(qū)虎林縣人，黑龍江林業(yè)職業(yè)技術(shù)學(xué)院教師，講師，哈爾濱工程大學(xué)軟件工程專業(yè)碩士學(xué)位，研究