應(yīng)用數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)術(shù)語(yǔ)應(yīng)用數(shù)據(jù)結(jié)構(gòu)01數(shù)據(jù)結(jié)構(gòu)解決表達(dá)式中括號(hào)匹配問(wèn)題數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)目錄030204基本信息應(yīng)用數(shù)據(jù)結(jié)構(gòu)（applicationdatastructure）是數(shù)據(jù)結(jié)構(gòu)在很多軟件數(shù)據(jù)庫(kù)等都是必不可少的一種具有一定邏輯關(guān)系，在計(jì)算機(jī)中應(yīng)用某種存儲(chǔ)結(jié)構(gòu)，并且封裝了相應(yīng)操作的數(shù)據(jù)元素的集合。它包含三方面的內(nèi)容，邏輯關(guān)系、存儲(chǔ)關(guān)系以及操作。數(shù)據(jù)結(jié)構(gòu)概念背景數(shù)據(jù)結(jié)構(gòu)背景計(jì)算機(jī)處理的信息和數(shù)據(jù)不僅包括數(shù)字，而且包括字符、表格、圖形、圖像、聲音、動(dòng)畫等復(fù)雜問(wèn)題，這些信息不只是簡(jiǎn)單、孤立的數(shù)據(jù)，而是存在某些關(guān)系的數(shù)據(jù)。獨(dú)立的數(shù)據(jù)往往是毫無(wú)意義的，只有將它們組織在一起才能賦予它們確切的含義。如何組織、處理這些信息，就是數(shù)據(jù)結(jié)構(gòu)的基本問(wèn)題。數(shù)據(jù)結(jié)構(gòu)就是指數(shù)據(jù)之間的結(jié)構(gòu)層次關(guān)系。例如，給定二個(gè)點(diǎn)的坐標(biāo)，計(jì)算機(jī)可以將它們連成一個(gè)三角形.也可以過(guò)這三個(gè)點(diǎn)作一個(gè)圓或畫一段圓弧。但是，如果事先并沒(méi)有確定這三個(gè)點(diǎn)之間的繪圖關(guān)系，亦即如何組織利用這三個(gè)點(diǎn)進(jìn)行畫線、畫圓或畫圓弧，那么計(jì)算機(jī)就不能完成相應(yīng)的動(dòng)作。只有當(dāng)點(diǎn)的坐標(biāo)和繪圖關(guān)系確定之后，計(jì)算機(jī)才能畫出我們所希望的圖形。因此，數(shù)據(jù)及其結(jié)構(gòu)層次關(guān)系在計(jì)算機(jī)中的表達(dá)，是影響應(yīng)用軟件成敗及效率高低的關(guān)鍵。概念數(shù)據(jù)結(jié)構(gòu)是一種具有一定邏輯關(guān)系，在計(jì)算機(jī)中應(yīng)用某種存儲(chǔ)結(jié)構(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)是除了開頭和最后一個(gè)節(jié)點(diǎn)外，其他的任意一個(gè)節(jié)點(diǎn)都只有一個(gè)直接前驅(qū)節(jié)點(diǎn)后后繼節(jié)點(diǎn)。線性結(jié)構(gòu)主要包括有線性表、棧和隊(duì)列。樹、集合、圖都是非線性結(jié)構(gòu)，其中樹形結(jié)構(gòu)模擬層次，圖形結(jié)構(gòu)模擬對(duì)稱和非對(duì)稱關(guān)系。研究數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的需要，是為了使得程序設(shè)計(jì)更加的健壯、高效，使得程序的開發(fā)更加的方便。數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)分析步驟建立數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)分析步驟其分析步驟為:建立數(shù)據(jù)結(jié)構(gòu)生活中所要處理的數(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ò)程采用將硬幣分析兩組或者三組，分別使用天平比較的方式來(lái)判斷。這一判斷過(guò)程可以用一個(gè)樹形圖來(lái)表示，所以可以將該問(wèn)題抽象為判定樹，構(gòu)建樹形結(jié)構(gòu)。存儲(chǔ)結(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ǔ)空間。從運(yùn)算效率上來(lái)對(duì)比，如果線性表需要進(jìn)行大量的插入和刪除操作的話，那么鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)從執(zhí)行效率上來(lái)講要占有優(yōu)勢(shì)。而如果線性表要反復(fù)進(jìn)行查詢操作的話，順序存儲(chǔ)結(jié)構(gòu)具備隨機(jī)讀寫的特點(diǎn)，就比較適合這種情況。設(shè)計(jì)確定數(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)生預(yù)期的正確的結(jié)果;能夠在有窮的步驟內(nèi)執(zhí)行完程序;能夠用最簡(jiǎn)短的語(yǔ)句最高效的完成任務(wù)。解決表達(dá)式中括號(hào)匹配問(wèn)題抽象數(shù)據(jù)的邏輯結(jié)構(gòu)算法描述選用存儲(chǔ)數(shù)據(jù)的物理結(jié)構(gòu)解決表達(dá)式中括號(hào)匹配問(wèn)題抽象數(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ù)的需求。選用存儲(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ù)元素稱為棧頂元素，用指針TOP標(biāo)志。順序棧的基本操作包括:創(chuàng)建一個(gè)空棧、判斷棧是否為滿、判斷棧是否為空、得出棧的長(zhǎng)度、入棧、出棧、返回棧頂元素。如圖1所示:圖1順序棧入棧操作的實(shí)現(xiàn)步驟為:

判斷如果棧己滿，返回false，不允許入棧順序棧出棧操作的實(shí)現(xiàn)步驟為:算法描述關(guān)于括號(hào)匹配的操作是這樣進(jìn)行的:(1)將輸入的表達(dá)式按序存入數(shù)組，掃描整個(gè)數(shù)組，遇到左括號(hào)都進(jìn)行棧(2)遇到右括號(hào)①先進(jìn)行判空，若是空棧，則一個(gè)右括號(hào)入棧后一定是不匹配的②如果判空后不是空棧，那么就把棧里的括號(hào)彈出并與遇到的第一個(gè)右括號(hào)進(jìn)行匹配判斷，若匹配則繼續(xù)執(zhí)行步驟1.2，若不匹配則整個(gè)表達(dá)式也不匹配。(3)當(dāng)進(jìn)行完上面得操作后，如果棧不為空，那就說(shuō)明肯定還有括號(hào)留在棧中，那一定就是不匹配了。若整個(gè)表達(dá)式掃描完畢，棧也為空，則說(shuō)明表達(dá)式中括號(hào)匹配。

為設(shè)計(jì)資料的數(shù)據(jù)描述提供依據(jù)適合應(yīng)用軟件為數(shù)據(jù)檢索提供條件為數(shù)據(jù)通信提供條件為設(shè)計(jì)資料的數(shù)據(jù)描述提供依據(jù)從嚴(yán)格意義上來(lái)講，應(yīng)用程序中對(duì)任何一個(gè)變量的定義、對(duì)任何一個(gè)數(shù)據(jù)文件的存取都涉及到數(shù)據(jù)結(jié)構(gòu)的問(wèn)題。定義數(shù)據(jù)結(jié)構(gòu)應(yīng)遵循的一個(gè)基本原則是:數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、邏輯關(guān)系明確清晰、便于操作、存取速度快、運(yùn)行效率高、占用存儲(chǔ)空間少。對(duì)簡(jiǎn)單意義的變量一般可以用常量、單變量來(lái)定義；對(duì)較為復(fù)雜的數(shù)據(jù)一般可以用一維數(shù)組、多維數(shù)組、結(jié)構(gòu)變量或指針來(lái)定義。

適合應(yīng)用軟件適合應(yīng)用軟件作業(yè)中對(duì)設(shè)計(jì)模型作實(shí)時(shí)修改的需要。如增加、刪除、修改記錄等。應(yīng)根據(jù)實(shí)際情況，對(duì)線性結(jié)構(gòu)的數(shù)據(jù)和非線性結(jié)構(gòu)的數(shù)據(jù)構(gòu)造不同的數(shù)據(jù)結(jié)構(gòu)，以便于提高數(shù)據(jù)操作的效率。順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，它們適合于不同的場(chǎng)合，因而選用時(shí)應(yīng)權(quán)衡考慮。為數(shù)據(jù)檢索提供條件在設(shè)計(jì)中常常需要根據(jù)設(shè)計(jì)對(duì)象的某些特征、屬性來(lái)檢索一些數(shù)據(jù)以供設(shè)計(jì)之用，為此就必須利用數(shù)據(jù)結(jié)構(gòu)來(lái)提供條件。如一部機(jī)器可能由很多個(gè)零件組成，應(yīng)用軟件作業(yè)中可能需要根據(jù)零件的名稱、材料、標(biāo)準(zhǔn)件或非標(biāo)準(zhǔn)件等條件進(jìn)行檢