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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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