數(shù)據(jù)結(jié)構(gòu)的小論文

數(shù)據(jù)結(jié)構(gòu)的小論文作者學(xué)號(hào)

名稱解釋〔1〕數(shù)據(jù)是信息的載體，是對(duì)客觀事物的符號(hào)表示。通俗的說(shuō)，但凡能被計(jì)算機(jī)識(shí)別、存取和加工處理的符號(hào)、字符、圖形、圖象、聲音、視頻信號(hào)等一切信息都可以稱為數(shù)據(jù)?！?〕數(shù)據(jù)結(jié)構(gòu)是相互之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。簡(jiǎn)言之，數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)之間的關(guān)系，即數(shù)據(jù)的組織形式?！?〕數(shù)據(jù)元素之間的邏輯關(guān)系，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)?！?〕數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。〔5〕線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在“一對(duì)一”關(guān)系的邏輯結(jié)構(gòu)。〔6〕非線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在“一對(duì)一”或“一對(duì)多”關(guān)系的邏輯結(jié)構(gòu)。〔除了線性結(jié)構(gòu)以外的樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)等統(tǒng)稱為非線性結(jié)構(gòu)〕。二、名詞解釋〔1〕線性表——線性表是具有相同數(shù)據(jù)類型的n〔n>=0〕個(gè)數(shù)據(jù)元素的有限序列。其邏輯特征反映了結(jié)點(diǎn)間一對(duì)一的關(guān)系，是一種線性結(jié)構(gòu)?！?〕順序表——用一組地址連續(xù)的存儲(chǔ)單元依次順序存儲(chǔ)線性表的數(shù)據(jù)元素〔相鄰結(jié)點(diǎn)存放在相鄰的物理位置〕，稱為順序表。它是一種隨機(jī)存取結(jié)構(gòu)，可以通過(guò)公式來(lái)計(jì)算結(jié)點(diǎn)的存取地址?！?〕單鏈表——單鏈表的每個(gè)結(jié)點(diǎn)都有兩個(gè)域，一個(gè)數(shù)據(jù)域和一個(gè)指針域，稱之為單鏈表?！?〕雙鏈表——以鏈表形式存儲(chǔ)的線性表，其結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)域和兩個(gè)指針域，稱之為雙鏈表。〔5〕循環(huán)鏈表——假設(shè)線性鏈表的最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，使得鏈表頭尾結(jié)點(diǎn)相連，就構(gòu)成了循環(huán)鏈表?！?〕存儲(chǔ)密度——存儲(chǔ)密度定義為結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量與結(jié)點(diǎn)結(jié)構(gòu)實(shí)際分配的存儲(chǔ)量的比值。順序表的存儲(chǔ)密度等于1；鏈表結(jié)構(gòu)存儲(chǔ)密度小于1。三.名詞解釋〔1〕棧只允許在一端進(jìn)行插入或刪除操作的線性表稱為棧。其最大的特點(diǎn)是“后進(jìn)先出”?！?〕順序棧采用順序存儲(chǔ)結(jié)構(gòu)的棧稱為順序棧?！?〕鏈棧采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧稱為鏈棧。四.名詞解釋〔1〕隊(duì)列只允許在一端進(jìn)行插入，另一端進(jìn)行刪除操作的線性表稱為隊(duì)列。其最大的特點(diǎn)是“先進(jìn)先出”?！?〕順序隊(duì)列采用順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列稱為順序隊(duì)列。〔3〕鏈隊(duì)列采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的稱隊(duì)列為鏈隊(duì)列?！?〕循環(huán)隊(duì)列為了解決順序隊(duì)列中“假溢出”現(xiàn)象，將隊(duì)列的存儲(chǔ)空間想象為一個(gè)首尾相鏈的環(huán)〔即把隊(duì)頭元素與對(duì)尾元素鏈結(jié)起來(lái)〕，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列。五、名詞解釋〔1〕字符串由零個(gè)或多個(gè)字符組成的有限序列稱為字符串〔簡(jiǎn)稱串〕。〔2〕空白串由一個(gè)或多個(gè)空格組成的串稱為空白串〔也稱為空格串〕。〔3〕空串長(zhǎng)度為零的字符串稱為空串?！舱?qǐng)注意空串和空白串的區(qū)別〕〔4〕順序串串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。〔5〕鏈?zhǔn)酱逆準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈?zhǔn)酱??！?〕模式匹配子串的定位運(yùn)算又稱為模式匹配。六、名詞解釋〔1〕結(jié)點(diǎn)——樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)及假設(shè)干指向其子樹(shù)的分支?！?〕結(jié)點(diǎn)的度——結(jié)點(diǎn)所擁有的子樹(shù)數(shù)稱為該結(jié)點(diǎn)的度?！?〕樹(shù)的度——樹(shù)中各結(jié)點(diǎn)度的最大值稱為該樹(shù)的度?！?〕二叉樹(shù)——一棵非空的二叉樹(shù)，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)，分別稱為左子樹(shù)和右子樹(shù)，左、右子樹(shù)的次序不能任意交換，且左右子樹(shù)又分別是一棵二叉樹(shù)?！?〕哈夫曼樹(shù)——帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，即最優(yōu)二叉樹(shù)，也稱為哈夫曼樹(shù)。七．名稱解釋〔1〕有向圖——在一個(gè)圖中，如果每條邊都有方向，那么稱該圖有向圖。〔2〕無(wú)向圖——在一個(gè)圖中，如果每條邊都沒(méi)有方向，那么稱該圖為無(wú)向圖?！?〕完全有向圖——在一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，那么稱該圖為有向完全圖?！苍谝粋€(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條弧。〕〔4〕最小生成樹(shù)——假設(shè)無(wú)向連通圖是一個(gè)網(wǎng)，那么它的所有生成樹(shù)中必有一棵邊的權(quán)值之和為最小的生成樹(shù)，簡(jiǎn)稱為最小生成樹(shù)。建立一個(gè)好的C語(yǔ)言數(shù)據(jù)課程設(shè)計(jì)的要求是：可讀性較強(qiáng)：〔1〕、結(jié)構(gòu)嚴(yán)謹(jǐn)，都采用模塊化設(shè)計(jì)采用了多文件結(jié)構(gòu)，不同的文件實(shí)現(xiàn)了不同的功能，最好能夠?qū)⒚總€(gè)模塊的函數(shù)都在相應(yīng)的頭文件中聲明并帶有功能注解?！?〕、較詳細(xì)的注釋使得程序更容易閱讀。在每個(gè)函數(shù)、每種數(shù)據(jù)類型的定義、每條關(guān)鍵語(yǔ)句都不得有相應(yīng)的注釋?！?〕、書寫標(biāo)準(zhǔn)：在輸入編輯源程序時(shí)我們力爭(zhēng)使程序語(yǔ)句更標(biāo)準(zhǔn)〔用上面提到的格式標(biāo)準(zhǔn)〕。〔4〕標(biāo)識(shí)符〔如函數(shù)名、變量名、數(shù)據(jù)類型名〕命名有講究：采用操作_對(duì)象的命名規(guī)那么，如creat_train);表示創(chuàng)立火車鏈表之意，盡量使標(biāo)識(shí)符“詞能達(dá)意”，增強(qiáng)可讀性。容易維護(hù)：很強(qiáng)的健壯性：支持?jǐn)?shù)據(jù)更新：功能比擬完善：比擬友好的界面：數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)根底課，是十分重要的核心課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運(yùn)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言是難以應(yīng)付眾多復(fù)雜的課題的。要想有效地使用計(jì)算機(jī)、充分發(fā)揮計(jì)算機(jī)的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)。打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的扎實(shí)根底，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫(kù)管理系統(tǒng)、軟件工程、人工智能等都是十分有益的。有關(guān)概念和術(shù)語(yǔ)在系統(tǒng)地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)之前，先對(duì)一些根本概念和術(shù)語(yǔ)賦予確切的含義。數(shù)據(jù)〔Data〕是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。它是計(jì)算機(jī)程序加工的原料，應(yīng)用程序處理各種各樣的數(shù)據(jù)。計(jì)算機(jī)科學(xué)中，所謂數(shù)據(jù)就是計(jì)算機(jī)加工處理的對(duì)象，它可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)是一些整數(shù)、實(shí)數(shù)或復(fù)數(shù)，主要用于工程計(jì)算、科學(xué)計(jì)算和商務(wù)處理等；非數(shù)值數(shù)據(jù)包括字符、文字、圖形、圖像、語(yǔ)音等。數(shù)據(jù)元素〔DataElement〕是數(shù)據(jù)的根本單位。在不同的條件下，數(shù)據(jù)元素又可稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。例如，學(xué)生信息檢索系統(tǒng)中學(xué)生信息表中的一個(gè)記錄、八皇后問(wèn)題中狀態(tài)樹(shù)的一個(gè)狀態(tài)、教學(xué)方案編排問(wèn)題中的一個(gè)頂點(diǎn)等，都被稱為一個(gè)數(shù)據(jù)元素。有時(shí)，一個(gè)數(shù)據(jù)元素可由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)〔DataItem〕組成，例如，學(xué)籍管理系統(tǒng)中學(xué)生信息表的每一個(gè)數(shù)據(jù)元素就是一個(gè)學(xué)生記錄。它包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、出生年月、成績(jī)等數(shù)據(jù)項(xiàng)。這些數(shù)據(jù)項(xiàng)可以分為兩種：一種叫做初等項(xiàng)，如學(xué)生的性別、籍貫等，這些數(shù)據(jù)項(xiàng)是在數(shù)據(jù)處理時(shí)不能再分割的最小單位；另一種叫做組合項(xiàng)，如學(xué)生的成績(jī)，它可以再劃分為數(shù)學(xué)、物理、化學(xué)等更小的項(xiàng)。通常，在解決實(shí)際應(yīng)用問(wèn)題時(shí)是把每個(gè)學(xué)生記錄當(dāng)作一個(gè)根本單位進(jìn)行訪問(wèn)和處理的。數(shù)據(jù)對(duì)象〔DataObject〕或數(shù)據(jù)元素類〔DataElementClass〕是具有相同性質(zhì)的數(shù)據(jù)元素的集合。在某個(gè)具體問(wèn)題中，數(shù)據(jù)元素都具有相同的性質(zhì)〔元素值不一定相等〕，屬于同一數(shù)據(jù)對(duì)象〔數(shù)據(jù)元素類〕，數(shù)據(jù)元素是數(shù)據(jù)元素類的一個(gè)實(shí)例。例如，在交通咨詢系統(tǒng)的交通網(wǎng)中，所有的頂點(diǎn)是一個(gè)數(shù)據(jù)元素類，頂點(diǎn)A和頂點(diǎn)B各自代表一個(gè)城市，是該數(shù)據(jù)元素類中的兩個(gè)實(shí)例，其數(shù)據(jù)元素的值分別為A和B。數(shù)據(jù)結(jié)構(gòu)〔DataStructure〕是指互相之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合。在任何問(wèn)題中，數(shù)據(jù)元素之間都不會(huì)是孤立的，在它們之間都存在著這樣或那樣的關(guān)系，這種數(shù)據(jù)元素之間的關(guān)系稱為結(jié)構(gòu)。根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常有以下四類根本的結(jié)構(gòu)：⑴集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。⑵線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。⑶樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。⑷圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)與數(shù)學(xué)、計(jì)算機(jī)硬件和軟件有十分密切的關(guān)系。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件之間的一門計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的核心課程，是高級(jí)程序設(shè)計(jì)語(yǔ)言、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫(kù)、人工智能等課程的根底。同時(shí)，數(shù)據(jù)結(jié)構(gòu)技術(shù)也廣泛應(yīng)用于信息科學(xué)、系統(tǒng)工程、應(yīng)用數(shù)學(xué)以及各種工程技術(shù)領(lǐng)域。數(shù)據(jù)結(jié)構(gòu)課程集中討論軟件開(kāi)發(fā)過(guò)程中的設(shè)計(jì)階段、同時(shí)設(shè)計(jì)編碼和分析階段的假設(shè)干根本問(wèn)題。此外，為了構(gòu)造出好的數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)，還需考慮數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)的評(píng)價(jià)與選擇。因此，數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個(gè)層次的五個(gè)“要素”，如圖1.5所示。數(shù)據(jù)結(jié)構(gòu)的核心技術(shù)是分解與抽象。通過(guò)分解可以劃分出數(shù)據(jù)的三個(gè)層次；再通過(guò)抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類似地，通過(guò)分解將處理要求劃分成各種功能，再通過(guò)抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到運(yùn)算的定義。上述兩個(gè)方面的結(jié)合使我們將問(wèn)題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)從具體〔即具體問(wèn)題〕到抽象〔即數(shù)據(jù)結(jié)構(gòu)〕的過(guò)程。然后，通過(guò)增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)。這是一個(gè)從抽象〔即數(shù)據(jù)結(jié)構(gòu)〕到具體〔即具體實(shí)現(xiàn)〕的過(guò)程。熟練地掌握這兩個(gè)過(guò)程是數(shù)據(jù)結(jié)構(gòu)課程在專業(yè)技能培養(yǎng)方面的根本目標(biāo)。數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國(guó)外是從1968年才開(kāi)始的，但在此之前其有關(guān)內(nèi)容已散見(jiàn)于編譯原理及操作系統(tǒng)之中。20世紀(jì)60年代中期，美國(guó)的一些大學(xué)開(kāi)始設(shè)立有關(guān)課程，但當(dāng)時(shí)的課程名稱并不叫數(shù)據(jù)結(jié)構(gòu)。1968年美國(guó)唐.歐.克努特教授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《根本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們?cè)絹?lái)越重視數(shù)據(jù)結(jié)構(gòu)。從70年代中期到80年代，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。目前，數(shù)據(jù)結(jié)構(gòu)的開(kāi)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問(wèn)題的數(shù)據(jù)結(jié)構(gòu)得到研究和開(kāi)展，如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點(diǎn)來(lái)討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢(shì)，越來(lái)越被人們所重視。算法特性算法〔Algorithm〕是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。一個(gè)算法應(yīng)該具有以下特性：⑴有窮性。一個(gè)算法必須在有窮步之后結(jié)束，即必須在有限時(shí)間內(nèi)完成。⑵確定性。算法的每一步必須有確切的定義，無(wú)二義性。算法的執(zhí)行對(duì)應(yīng)著的相同的輸入僅有唯一的一條路經(jīng)。⑶可行性。算法中的每一步都可以通過(guò)已經(jīng)實(shí)現(xiàn)的根本運(yùn)算的有限次執(zhí)行得以實(shí)現(xiàn)。⑷輸入。一個(gè)算法具有零個(gè)或多個(gè)輸入，這些輸入取自特定的數(shù)據(jù)對(duì)象集合。⑸輸出。一個(gè)算法具有一個(gè)或多個(gè)輸出，這些輸出同輸入之間存在某種特定的關(guān)系。經(jīng)典例題——迷宮數(shù)字迷宮求解求迷宮中從入口到出口的所有路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問(wèn)題。如圖1示:圖1在此介紹如何使用棧的方式來(lái)完成。為防止檢查迷宮邊界的麻煩,事先將迷宮的四周用上了墻壁。在程序中我們可以用二維數(shù)組來(lái)表示迷宮,其中1代表墻壁,0代表通路如圖2示:此時(shí),從入口出發(fā),順某一方向向前探索,假設(shè)能走通。那么繼續(xù)往前走,否那么沿原路退回,換一個(gè)方向再繼續(xù)探索,直到所有可能的通路都探索到為止。在探索下一通路時(shí),為保證每一方向都能遍歷到,我們按圖示東、南、西、北的順序進(jìn)行,在程序中用0、1、2、3來(lái)表示四個(gè)方向,仍然用數(shù)組來(lái)存放方向,坐標(biāo)變化在圖中巳標(biāo)出。在以試錯(cuò)法一遍又一遍查找可行路徑時(shí),必須利用棧的特性,將剛走過(guò)的位置,也就是由現(xiàn)有位置(i,j)移至新位置(g,h)時(shí),就先將(i,j)存入棧里,以備無(wú)路前進(jìn)時(shí)后退之用,另外,有一重要數(shù)據(jù)也必須一起存入棧里,就是當(dāng)由(g,h)位置退回至(i,j)位置時(shí),要重新查找新路時(shí)的新方向d,因此存入棧的數(shù)據(jù)有i,j,d,為了防止在由(i,j)走到(g,h)時(shí),又由(g,h)走回(i,j),但凡走過(guò)的點(diǎn),其迷宮值將由0變成2,在后退時(shí)又得將2復(fù)原成0。具體算法如下:#defineSIZE7#defineCOL5#defineROW5#include<stdio.h>intmaze[SIZE][SIZE];/*存放迷宮*/typedefstruct{intvert;inthoriz;}offsets;offsetsmove[4]={{0,1},{1,0},{0,-1},{-1,0}};/*存放四個(gè)方向的坐標(biāo)修改值*/typedefstructstack{intx;inty;intz;structstack*next;}STACK;voidpush(STACK**stk1,inti,intj,intd){STACK*top;top=(STACK*)malloc(sizeof(STACK));top->x=i;top->y=j;top->z=d;top->next=*stk1;3stk1=top;}/*入棧函數(shù)*/voidpop(STACK**stk1,int*p1,int*p2,int*p3){STACK*top;if(*stk1==NULL)printf("stackunderflow!");else{*p1=(*stk1)->x;*p2=(*stk1)->y;*p3=(*stk1)->z;top=*stk1;*stk1=(*3stk1)->next;free(top);}}/*出棧函數(shù)*/voidprint_ants()/*打印迷宮*/{inti,j;for(i=1;i<SIZE-1;i++,printf("\n"))for(j=1;j<SIZE-1;j++)printf("%3d",maze[i][j]);printf("