軟件技術(shù)基礎(chǔ)復(fù)習(xí)總結(jié)1

軟件技術(shù)基礎(chǔ)復(fù)習(xí)總結(jié)1第一章數(shù)據(jù)結(jié)構(gòu)1、什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)是爭論計算機(jī)系統(tǒng)中數(shù)據(jù)的組織形式及其相互關(guān)系。*在計算機(jī)系統(tǒng)中數(shù)據(jù)不僅包含了通常數(shù)值的概念，還包括將客觀事物采用計算機(jī)進(jìn)行識別，存儲和加工所進(jìn)行的描述。2、爭論數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容：(1)數(shù)據(jù)元素之間的規(guī)律關(guān)系(2)選用什么樣的存儲結(jié)構(gòu)(3)用算法效率最高的操作3、數(shù)據(jù)結(jié)構(gòu)的基本概念：通常把運(yùn)用數(shù)據(jù)結(jié)構(gòu)來描述數(shù)據(jù)元素之間的規(guī)律關(guān)系，數(shù)據(jù)在計算機(jī)系統(tǒng)中的存儲方式和數(shù)據(jù)的運(yùn)算抽象成數(shù)據(jù)結(jié)構(gòu)的三個層次：數(shù)據(jù)的規(guī)律結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)操作集合。數(shù)據(jù)規(guī)律結(jié)構(gòu)：線性結(jié)構(gòu)(有且僅有一個開頭數(shù)據(jù)元素和一個終點(diǎn)數(shù)據(jù)元素，且全部數(shù)據(jù)元素僅有一個直接前驅(qū)和一個直接后繼)非線性結(jié)構(gòu)(多個直接前驅(qū)和后繼)數(shù)據(jù)的存儲方法：挨次存儲方法、鏈接存儲法、索引存儲法、散列存儲法常用的數(shù)據(jù)處理與運(yùn)算：遍歷、插入、更新、刪除、查找、排序。4、算法的基本概念與算法效率一個算法必需具備有窮性、確定性，數(shù)據(jù)輸入、信息輸出、可行性五項基本特征。算法效率包括時間效率和空間效率。程序二算法+數(shù)據(jù)結(jié)構(gòu)5、線性結(jié)構(gòu)：線性表、堆棧、隊列、數(shù)組、串線性結(jié)構(gòu)特點(diǎn)是數(shù)據(jù)元素有序并有限。6、線性表,挨次表單向鏈表線性鏈表雙鏈表循環(huán)鏈表7、挨次表：設(shè)在挨次表中每個元素占用k個存儲單元，索引號為1的數(shù)據(jù)元素a1的內(nèi)存地址為Log(a1),則索引號為i的數(shù)據(jù)元素ai的內(nèi)存地址為：Loc(a1)-Log(a1)+(i+1)*k存儲地址是該元素在表中索引號的線性函數(shù)。挨次表的存儲結(jié)構(gòu)是一種可以隨機(jī)存取數(shù)據(jù)元素的結(jié)構(gòu)，這樣的存儲結(jié)構(gòu)適合用數(shù)組表征。由于挨次表的隨機(jī)存取特性，使得挨次表中對每一個元素的存儲時間都很短，并且與其位置無關(guān)。挨次表的插入和刪除操作所耗費(fèi)的主要時間是在移動元素上。缺點(diǎn)：運(yùn)算效率低，數(shù)據(jù)元素最大個數(shù)需要預(yù)先確定。8、單向鏈表：單向鏈表的每個數(shù)據(jù)元素都由兩部分組成：存儲元素值的數(shù)據(jù)域(data)和存儲直接后繼元素存儲地址的指針域(next)。datanextdata可以加頭結(jié)點(diǎn)h由于是以鏈接方式存儲，全部數(shù)據(jù)元素是離散存放，可以充分采用存放空間，提高了處理速度，但需要從頭節(jié)點(diǎn)訪問。9、雙鏈表：雙鏈表在單鏈表的基礎(chǔ)上在節(jié)點(diǎn)處增加了一個指向表中每個元素的直接前驅(qū)的指針域，這樣可以實現(xiàn)從后向前搜尋，實現(xiàn)雙向查找PriorDataNext知道任一節(jié)點(diǎn)的指針可以訪問整個鏈表。已占用較大的內(nèi)存空間來給計算帶來便利。10、循環(huán)鏈表：單鏈表或雙鏈表的最終一個節(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，形成循環(huán)鏈表或雙向循環(huán)鏈表。11、棧僅限在一端實現(xiàn)線性表的插入和刪除。通常稱插入和刪除的這一端稱為棧頂，另一端稱為棧底。保持后進(jìn)先出的原則。有挨次棧和鏈?zhǔn)酱鎯Y(jié)構(gòu)的棧。12、隊列只允許在線性表的一端進(jìn)行數(shù)據(jù)元素的插入操作，在另一端進(jìn)行數(shù)據(jù)元素的刪除操作。其中，允許插入的一端稱為隊尾，另一端稱為隊頭。需要兩個隊列指針來說明，一個隊頭指針，總是指向隊頭元素的前一個位置，另一個是隊尾指針，總是指向隊尾元素所在的存儲位置。保持先進(jìn)先出的特性挨次隊列在進(jìn)行入隊操作時會消失假逸現(xiàn)象，解決方法是采納循環(huán)隊列，首尾相接。13、棧和隊列的運(yùn)用依據(jù)處理數(shù)據(jù)的需要，假如處理的數(shù)據(jù)具有FIFO(先來的先處理)特性,則用隊列結(jié)構(gòu)，假如具有LIFO(后來的先處理)特性，則用棧結(jié)構(gòu)。棧結(jié)構(gòu)的典型運(yùn)用：程序設(shè)計中子程序調(diào)用與返回的斷點(diǎn)和現(xiàn)場數(shù)據(jù)的處理。遞歸算法14、數(shù)組數(shù)組中兩種最基本的操作：(1)給定一組下標(biāo)，找到與之相應(yīng)的數(shù)據(jù)元素。(2)給定一組下標(biāo)，存取或修改與其相對應(yīng)的數(shù)據(jù)元素中某個數(shù)據(jù)項的值。數(shù)組的存儲結(jié)構(gòu)：(1)挨次存儲結(jié)構(gòu)設(shè)每個數(shù)組元素占S個存儲單元，在行優(yōu)先存儲中，二維數(shù)組的每個元素的存儲地址可用以下公式求出：Log(aij)=Ioc(a11)+((i7)*n+(j-1))*S在列優(yōu)先挨次存儲中，每個元素的存儲地址可用以下公式求出：Loc(aij)-Ioc(a11)+((j-1)*m+(i-1))*S優(yōu)點(diǎn)是可以便利地隨機(jī)存取數(shù)組的數(shù)據(jù)元素。缺點(diǎn)是(2)壓縮存儲結(jié)構(gòu)特別矩陣的壓縮存儲：對稱矩陣，只要存儲矩陣中上三角或下三角的元素，讓每一對對稱的元素共享一個存儲空間。這樣能節(jié)省一半的存儲空間。這種方式同樣適合三角矩陣。稀疏矩陣，設(shè)A是一個m*n的稀疏矩陣，其中非零元素個數(shù)為I,三元存儲法可采納一個(1+1)*3的T來存儲A。矩陣T的第一行是m,n,I;后面的每一行對應(yīng)A矩陣中的一個非零元素，如某一行為i,j,x則對應(yīng)A中第i行，第j列的值為x的非零元素。15、字符串由零到多個字符組成的連續(xù)有限序列一個串中任意多個連續(xù)的字符組成的子序列稱為該串的子串，包含該子串的串稱為主串，一個字符在串中的序號稱為該字符在串