【正文】 ，年份越久越醇香濃烈；真誠是焰火，在高處綻放才愈顯美麗；真誠是鮮花，送之于人，手有余香。 本文由小風HCF貢獻 doc文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機查看。 天驕現(xiàn)代考前沖刺資料 公共基礎(chǔ)知識 第一章 數(shù)據(jù)結(jié)構(gòu)與算法 算法 算法：是指解題方案的準確而完整的描述。 算法 ：是指解題方案的準確而完整的描述。 算法不等于程序，也不等計算機方法，程序的 編制不可能優(yōu)于算法的設(shè)計。 算法的基本特征： 是一組嚴謹?shù)囟x運算順序 的規(guī)則，每一個規(guī)則都是有效的，是明確的， 此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括： （1）可行性； （2）確定性，算法中每一步驟都必須有明確 定義，不充許有模棱兩可的解釋，不允許有多 義性； （3）有窮性，算法必須能在有限的時間內(nèi)做 完，即能在執(zhí)行有限個步驟后終止，包括合理 的執(zhí)行時間的含義； （4）擁有足夠的情報。 算法的基本要素： 一是對數(shù)據(jù)對象的運算和操 一是對數(shù)據(jù)對象的運算和操 二是算法的控制結(jié)構(gòu)。 作；二是算法的控制結(jié)構(gòu)。 指令系統(tǒng)： 一個計算機系統(tǒng)能執(zhí)行的所有指令 的集合。 算術(shù)運算、 基本運算包括：算術(shù)運算、邏輯運算、關(guān)系運 算術(shù)運算 邏輯運算、 數(shù)據(jù)傳輸。 算、數(shù)據(jù)傳輸。 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、 算法的控制結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán) 結(jié)構(gòu)。 結(jié)構(gòu) 。 算法基本設(shè)計方法：列舉法、歸納法、遞推、 遞歸、減斗遞推技術(shù)、回溯法。 算法復(fù)雜度： 算法時間復(fù)雜度和 算法復(fù)雜度 ： 算法時間復(fù)雜度 和 算法空間復(fù) 雜度。 雜度 。 算法時間復(fù)雜度是指執(zhí)行算法所需要的 計算工作量。 計算工作量。 算法空間復(fù)雜度是指執(zhí)行這個算 法所需要的內(nèi)存空間。 法所需要的內(nèi)存空間。 數(shù)據(jù)結(jié)構(gòu)的基本基本概念 數(shù)據(jù)結(jié)構(gòu)研究的三個方面： 數(shù)據(jù)結(jié)構(gòu)研究的三個方面： （1）數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏 輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)； 數(shù)據(jù)的邏輯結(jié)構(gòu)； 數(shù)據(jù)的邏輯結(jié)構(gòu) （2）在對數(shù)據(jù)進行處理時，各數(shù)據(jù)元素在計 算機中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)； 數(shù)據(jù)的存儲結(jié)構(gòu)； 數(shù)據(jù)的存儲結(jié)構(gòu) （3）對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 數(shù)據(jù)的邏輯結(jié)構(gòu)包含： （1）表示數(shù)據(jù)元素的信息； （2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。 數(shù)據(jù)的存儲結(jié)構(gòu)有順序、鏈接、索引等。 線性結(jié)構(gòu)條件： 線性結(jié)構(gòu)條件： （2） （1）有且只有一個根結(jié)點； ）每一個結(jié)點 ）有且只有一個根結(jié)點； （ 1 最多有一個前件，也最多有一個后件。 最多有一個前件， 也最多有一個后件。 非線性結(jié)構(gòu)： 非線性結(jié)構(gòu) ： 不滿足線性結(jié)構(gòu)條件的數(shù)據(jù)結(jié) 構(gòu)。 1．3 線性表及其順序存儲結(jié)構(gòu) 線性表是由一組數(shù)據(jù)元素構(gòu)成 數(shù)據(jù)元素的位 素構(gòu)成， 線性表 是由一組數(shù)據(jù)元素構(gòu)成， 置只取決于自己的序號， 置只取決于自己的序號， 元素之間的相對位置 是線性的。 是線性的。 在復(fù)雜線性表中， 由若干項數(shù)據(jù)元素組成的數(shù) 據(jù)元素稱為記錄 而由多個記錄構(gòu)成的線性表 記錄， 記錄 又稱為文件 文件。 文件 非空線性表的結(jié)構(gòu)特征： （1）且只有一個根結(jié)點 a1，它無前件； （2）有且只有一個終端結(jié)點 an，它無后件； （3）除根結(jié)點與終端結(jié)點外，其他所有結(jié)點 有且只有一個前件，也有且只有一個后件。結(jié) 點個數(shù) n 稱為線性表的長度 線性表的長度，當 n=0 時，稱 線性表的長度 為空表 空表。 空表 線性表的順序存儲結(jié)構(gòu)具有以下兩個基本特 點： （1）線性表中所有元素的所占的存儲空間是 ） 連續(xù)的； 連續(xù)的； （2）線性表中各數(shù)據(jù)元素在存儲空間中是按 ）線性表中各數(shù)據(jù)元素在存儲空間中是按 邏輯順序依次存放的。 邏輯順序依次存放的。 ai 的存儲地址為： ADR(ai)=ADR(a1)+(i1)k, ， ADR(a1) 為 第一個元素的地址，k 代表每個元素占的字節(jié) 數(shù)。 順序表的運算：插入、刪除。 1．4 棧和隊列 是限定在一端進行插入與刪除的線性表， 棧 是限定在一端進行插入與刪除的線性表， 允 許插入與刪除的一端稱為棧頂， 許插入與刪除的一端稱為棧頂， 不允許插入與 刪除的另一端稱為棧底。 刪除的另一端稱為棧底。 棧按照“先進后出 先進后出”（ 后進先出” 棧按照 先進后出 （ FILO）或 “后進先出 ） 后進先出 組織數(shù)據(jù)， 棧具有記憶作用。 用 （LIFO） ） 組織數(shù)據(jù)， 棧具有記憶作用。 top 表示棧頂位置，用 bottom 表示棧底。 棧的基本運算： （1）插入元素稱為入棧運算； （2）刪除元素稱為退棧運算； （3）讀棧頂元 素是將棧頂元素賦給一個指定的變量， 此時指 針無變化。 隊列是指允許在一端 隊尾）進入插入， 是指允許在一端（ 隊列 是指允許在一端（隊尾）進入插入，而在 另一端（隊頭）進行刪除的線性表。 另一端（隊頭）進行刪除的線性表。Rear 指 針指向隊尾， 指針指向隊頭。 針指向隊尾，front 指針指向隊頭。 隊列是“先進行出 先進行出”（ 后進后出” 隊列是 先進行出 （ FIFO）或 “后進后出 ） 后進后出 （LILO）的線性表。 ）的線性表。 隊列運算包括（1）入隊運算：從隊尾插入一 個元素； （2） 退隊運算： 從隊頭刪除一個元素。 天驕現(xiàn)代考前沖刺資料 循 環(huán) 隊 列 ： s=0 表 示 隊 列 空 ， s=1 且 front=rear 表示隊列滿 1．5 線性鏈表 數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點對應(yīng)于一個存儲單 這種存儲單元稱為存儲結(jié)點，簡稱結(jié)點 結(jié)點。 元，這種存儲單元稱為存儲結(jié)點，簡稱 結(jié)點 。 結(jié)點由兩部分組成： 1） （ 用于存儲數(shù)據(jù)元素值， 稱為數(shù)據(jù)域 （2）用于存放指針，稱為指針 數(shù)據(jù)域； 數(shù)據(jù)域 指針 域 ，用于指向前一個或后一個結(jié)點。 在鏈式存儲結(jié)構(gòu)中， 存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間 可以不連續(xù)， 各數(shù)據(jù)結(jié)點的存儲順序與數(shù)據(jù)元 素之間的邏輯關(guān)系可以不一致， 而數(shù)據(jù)元素之 間的邏輯關(guān)系是由指針域來確定的。 鏈式存儲方式即可用于表示線性結(jié)構(gòu)， 鏈式存儲方式即可用于表示線性結(jié)構(gòu)， 也可用 于表示非線性結(jié)構(gòu)。 于表示非線性結(jié)構(gòu)。 線性鏈表， HEAD 稱為頭指針， HEAD=NULL （或 0）稱為空表 空表，如果是兩指針：左指針 空表 左指針 （Llink）指向前件結(jié)點，右指針 右指針（Rlink）指 右指針 向后件結(jié)點。 線性鏈表的基本運算：查