【正文】 女 … 記錄 3 記錄 4 第 24頁 線性表的順序存儲結(jié)構(gòu) 特點(diǎn)： 順序存儲結(jié)構(gòu)把 邏輯上相鄰 的數(shù)據(jù)元素存儲在 物理上相鄰的存儲單元里，順序存儲結(jié)構(gòu) 只存儲結(jié)點(diǎn)的值 ，不存儲結(jié)點(diǎn)間的關(guān)系，結(jié)點(diǎn)間的關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。 … a1 a2 … ai … an … 存儲地址 2022 2022 2022+4*(i1) 2022+4*(n1) … … 占 4個字節(jié) Loa（ ai） =Loa（ a1） +L*（ i1） 第 i個數(shù)的地址 第一個數(shù)的地址 L為該類型數(shù)所占的字節(jié) 線性表的存儲結(jié)構(gòu) 線性表的存儲結(jié)構(gòu)有兩種： ? 順序存儲結(jié)構(gòu) ? 鏈?zhǔn)酱鎯Y(jié)構(gòu) 第 25頁 ? 順序表的插入運(yùn)算 ? 順序表的刪除運(yùn)算 順序表的插入和刪除運(yùn)算 在線性表順序存儲情況下，要插入或刪除一個元素，都會由于數(shù)據(jù)元素的移動而消耗大量的處理時間，所以這種存儲方式對于小線性表或其中數(shù)據(jù)元素不經(jīng)常變動的線性表是合適的。 線性表的順序存儲結(jié)構(gòu)稱為順序表。 第 26頁 插入運(yùn)算 ai1 ….. a2 a1 alength … ai+1 ai x ai1 ….. a2 a1 alength … ai+1 ai X 插入算法的分析 : 假設(shè)線性表中含有 n個數(shù)據(jù)元素，在進(jìn)行插入操作時，若假定在 n+1個位置上插入元素的可能性均等，則平均移動元素的個數(shù)為： 第 27頁 刪除運(yùn)算 ai1 ….. a2 a1 alength … ai+1 ai ai1 ….. a2 a1 alength … ai+1 刪除算法的分析 : 在進(jìn)行刪除操作時，若假定刪除每個元素的可能性均等，則平均移動元素的個數(shù)為： 總結(jié) : 順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對其做插入或刪除操作時，這一點(diǎn)需要值得考慮。 ?????? n1idl 21ni)(nn1E第 28頁 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。 ? 鏈?zhǔn)酱鎯Y(jié)構(gòu)不要求邏輯上相鄰的數(shù)據(jù)元素物理位置也相鄰，而且各數(shù)據(jù)元素的存儲順序也是任意的。各數(shù)據(jù)元素的先后關(guān)系是由各結(jié)點(diǎn)的指針域指示。 ? 鏈?zhǔn)酱鎯Y(jié)構(gòu)的每一個存儲結(jié)點(diǎn)不僅存儲結(jié)點(diǎn)的值，而且存儲結(jié)點(diǎn)之間的關(guān)系： ?鏈?zhǔn)酱鎯Y(jié)構(gòu)分為單鏈表、雙向鏈表、循環(huán)鏈表 ?線性鏈表不能隨機(jī)存取 數(shù)據(jù)域 指針域 第 29頁 設(shè)線性表為 （ a1， a2， a3， a4， a5） 1 a2 9 2 3 a1 1 4 5 a4 10 6 7 8 9 a3 5 10 a5 0 HEAD 3 a1 a2 a5 a3 a4 HEAD 3 1 9 5 10 線性鏈表的邏輯狀態(tài) 線性鏈表 的物理狀態(tài) 1 a1 2 a2 3 a3 4 a4 5 a5 6 7 線性表的 順序存儲 結(jié)構(gòu) 注意 :1 2 3 此類編號不代表所在的地址單元的地址編碼 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 及其插入與刪除操作 第 30頁 zhao qian sun li zhou wu zheng wang / H 存儲地址 數(shù)據(jù) 1 7 13 19 25 31 37 43 li qian sun wang wu zhao zheng zhou 指針 43 13 1 null 37 7 19 25 31 頭指針 單鏈表 第 31頁 單鏈表的插入運(yùn)算 在 P所指向的結(jié)點(diǎn)之后插入新的結(jié)點(diǎn) 單鏈表 刪除運(yùn)算 P b a x S b a P La … ai an ^ … ai1 ai+1 要求 :刪除結(jié)點(diǎn) ai。 第 32頁 循環(huán)鏈表 : 首尾相接的鏈表 。 將最后一個結(jié)點(diǎn)的空指針改為指向頭結(jié)點(diǎn) ， 從任一結(jié)點(diǎn)出發(fā)均可找到其它結(jié)點(diǎn) 。 a1 a2 an ∧ a3 L ….. 帶頭結(jié)點(diǎn)的單鏈表 a1 a2 an a3 L ….. 循環(huán)單鏈表 特點(diǎn) : 可以從任何一個結(jié)點(diǎn)開始訪問鏈表的所有結(jié)點(diǎn) . 第 33頁 雙向鏈表的存儲結(jié)構(gòu) 在每個結(jié)點(diǎn)中設(shè)置兩個指針 ， 一個指向后繼 ， 一個指向前驅(qū) 。 可直接確定一個結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn) 。 可提高效率 。 HEAD 3 1 5 10 a2 a3 a4 a1 提問：單向鏈表的缺點(diǎn)是什么？ 提示：如何尋找結(jié)點(diǎn)的直接前趨。 雙向鏈表可以克服單鏈表的單向性的缺點(diǎn)。 在雙向鏈表的結(jié)點(diǎn)中有兩個指針域，其一指向直接后繼，另一指向直接前趨。 雙向循環(huán)鏈表 第 34頁 ? 線性表的應(yīng)用：應(yīng)用最廣的數(shù)據(jù)結(jié)構(gòu)。 ? .高級語言中的數(shù)組； ? 計算機(jī)的文件系統(tǒng)； ? 計算機(jī)的目錄系統(tǒng)； ? 電話號碼查詢系統(tǒng)（可采用順序表或單鏈表結(jié)構(gòu) ）； ? 各種事務(wù)處理（ 可采用順序表或單鏈表結(jié)構(gòu) ） 。 第 35頁 2. 棧和隊列 棧和隊列 是兩種特殊的線性表，它們是運(yùn)算時要受到某些限制的線性表，故也稱為 限定性的數(shù)據(jù)結(jié)構(gòu) 。 ? 棧（ Stack）及其基本運(yùn)算 ? 隊列（ Queue）及其基本運(yùn)算 ? 循環(huán)隊列及其基本運(yùn)算 第 36頁 1 .棧 棧 —— 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。 棧頂 —— 表尾。 棧底 —— 表頭。 空棧 —— 不含元素的空表。 … a1 a2 an 棧底 棧頂 進(jìn)棧 出棧 棧 s=(a1,a2,…,an) 后進(jìn)先出或先進(jìn)后出（ LIFO） 第 37頁 ?棧的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈表結(jié)構(gòu)。 ?下面討論順序存儲結(jié)構(gòu)中棧元素的插入和刪除運(yùn)算。 ? 順序棧的進(jìn)棧和出棧運(yùn)算 ? 棧的基本運(yùn)算有三種：入棧、退棧和讀棧頂元素 在順序棧中插入和刪除運(yùn)算不需要移動表中其他數(shù)據(jù)元素 。 第 38頁 2. 棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算 a2 a1 top 用順序存儲結(jié)構(gòu)表示的棧 : 順序棧用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示，設(shè)置一個簡單變量 top指示棧頂位置， 稱為 針棧頂指 ， 它始終指向待插入元素的位置。 基本運(yùn)算： 壓（進(jìn)）棧： PUSH 出棧： POP 讀棧頂元素： gettop 第 39頁 例子： top base EDCBA top base CBA base top A base top 空桟： top＝ base 非空桟： top始終在桟頂元素的后一個位置 桟的元素個數(shù)： topbase 上溢 下溢 第 40頁 隊列 定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在 表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（ FIFO）表。 a1 , a2 , a3 , a4 , ………… an1 , an 隊 列 示 意 圖 隊頭 隊尾 先進(jìn)先出后進(jìn)后出（ LIFO） 第 41頁 e3 e4 (c) (c) e1,e2出隊， e4入隊 隊 滿 rear =3 front e1 e2 e3 (b) rear front (b)e1,e2,e3入隊 隊列的順序存儲結(jié)構(gòu)及其基本運(yùn)算 3 2 1 0 (a) rear=front=1(隊空） rear front 空隊列 : 非空隊列 : 隊列元素個數(shù) : rear=front=1 front始終指向隊頭元素前一個位置，而 rear始終指向隊尾元素的位置 rearfront 第 42頁 隊列的物理存儲結(jié)構(gòu)可以用順序結(jié)構(gòu)，也可以用鏈?zhǔn)浇Y(jié)構(gòu)。 ? 順序隊列的運(yùn)算 棧有三種操作： 入棧＼出棧＼讀棧頂元素 隊列有三種操作：入隊＼出隊＼讀隊首元素 例：有入棧元素序列： ABCD，求可能的出棧序列． 如是隊列又是什么情況呢？ 第 43頁 ? 循環(huán)隊列 把隊列的存儲空間在邏輯上看作一個環(huán)，當(dāng) R指向存儲空間的末端后，就把它重新置于始端。 ? 循環(huán)隊列的運(yùn)算 隊列中進(jìn)行插入的一端稱做隊尾 (rear),進(jìn)行刪除的一端稱做隊首 (front)。 習(xí)題：數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，循環(huán)隊列屬于 【 】 結(jié)構(gòu)。（ 2022年 9月） 答案：存儲結(jié)構(gòu)。 第 44頁 … … front rear Maxsize1 0 1 e3 e4 rear =3 front 第 45頁 0 0 1 2 3 4 5 front A B C D E F rear 上溢 0 0 1 2 3 4 5 front rear 下溢 front=rear 隊滿 front=rear 隊空 第 46頁 數(shù)據(jù)存儲結(jié)構(gòu)方面的考題 1：數(shù)據(jù)的存儲結(jié)構(gòu)是指 （ 2022年 4月 ） A) 存儲在外存中的數(shù)據(jù) B) 數(shù)據(jù)所占的存儲空間量 C) 數(shù)據(jù)在計算機(jī)中的順序存儲方式 D) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示 2. 下列敘述中正確的是 （ 2022年 3月 ） A） 棧是 “ 先進(jìn)先出 ” 的線性表 B） 隊列是 “ 先進(jìn)后出 ” 的線性表 C） 循環(huán)隊列是非線性結(jié)構(gòu) D） 有序線性表既可以采用順序存儲結(jié)構(gòu) ， 也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 數(shù)據(jù)結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu) ， 帶鏈的隊列屬于 [ ]。 4. 下列數(shù)據(jù)結(jié)構(gòu)中 ， 屬于非線性結(jié)構(gòu)的是 A） 循環(huán)隊列 B) 帶鏈隊列 C) 二叉樹 D） 帶鏈棧 答案： D。 答案： D。 答案：線性結(jié)構(gòu)。 答案： c 第 47頁 5。 下列敘述中正確的是 （ ） 。 （ 2022年 9月 ） A） 順序存儲結(jié)構(gòu)的存儲一定是連續(xù)的 ， 鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲空間不一定是連續(xù)的 B） 順序存儲結(jié)構(gòu)只針對線性結(jié)構(gòu) ， 鏈?zhǔn)酱鎯Y(jié)構(gòu)只針對非線性結(jié)構(gòu) C） 順序存儲結(jié)構(gòu)能存儲有序表 ， 鏈?zhǔn)酱鎯Y(jié)構(gòu)不能存儲有序表 D） 鏈?zhǔn)酱鎯Y(jié)構(gòu)比順序存儲結(jié)構(gòu)節(jié)省存儲空間 答案： A。 6。下列關(guān)于棧的敘述正確的是 （ 2022年 4月） A）棧按 “ 先進(jìn)先出 ” 組織數(shù)據(jù) B)棧按 “ 先進(jìn)后出 ” 組織數(shù)據(jù) C）只能在棧底插入數(shù)據(jù) D）不能刪除數(shù)據(jù) 答案： B。 7. 一個隊列的初始狀態(tài)為空?，F(xiàn)將元素 A， B， C， D， E， F， 5， 4， 3，2， 1依次入隊，然后再依次退隊，則元素退隊的順序?yàn)? 【 1】 。（ 2022年 3月） 答案： A， B， C， D， E， F， 5， 4， 3， 2， 1 第 48頁 9. 設(shè)某循環(huán)隊列的容量為 50，如果頭指針 front=45(指向隊頭元素的前一位置 )，尾指針 rear=10(指向隊尾元素 )，則該循環(huán)隊列中共有 【 2】 個元素。 （ 2022年 3月） 8。假設(shè)用一個長度為 50的數(shù)組（數(shù)組元索的下標(biāo)從 0到 49）作為棧的存儲空間，棧底指針 bottom指間棧底元素，棧頂指針 top指向棧頂元素，如果 bottom=49，top=30（數(shù)組下標(biāo)），則棧中具有 【 】 個元素。 （ 2022年 3月） 答案： 19 答案： 15 46－ 50－ 1－ 10 ? 鏈表不具有的特點(diǎn)是 A) 不必事先估計存儲空間 B) 可隨機(jī)訪問任一元素 C) 插入刪除不需要移動元素 D) 所需空間與線性表長度成正比 ? 數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)，線性鏈表屬于 【 1】 。