【文章內(nèi)容簡介】 ?線性表中各元素在存儲空間中 按邏輯順序依次存放 ,即線性表的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)相 一致 。 線性表通常采用 順序存儲結(jié)構(gòu) 或 鏈式存儲結(jié)構(gòu) 。 順序表 鏈表 由此可以看出 : 在線性表的順序存儲結(jié)構(gòu)中 ,其前后兩個元素在存儲空間中是 緊鄰 的 ， 前件元素一定存放在后件元素的前面 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 35/82 例如： 線性結(jié)構(gòu) {a1， a2， a3}，其中每個數(shù)據(jù)元素占 2個存儲空間，假設存儲 a1的首地址為 2022。 2022 a1 占 2個字節(jié) a2 a3 2022 2022 占 2個字節(jié) 占 2個字節(jié) 存儲地址： 結(jié)論： 假設一個數(shù)據(jù)元素占用 d個字節(jié) ,線性表的首地址 Addr(a1)為 K， 則存儲任意一個數(shù)據(jù)元素 ai的首地址為 : Addr(ai)= Addr(a1)+(i1) d=K+(i1) d 其中 1≤ i ≤n 優(yōu)點： 可以方便地隨機讀取表中任意元素 缺點： 插入和刪除運算需要移動大量元素，浪費大 量時間，時間效率較低。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 36/82 線性表的鏈式存儲 用一組存儲單元 (可以連續(xù) ， 也可以不連續(xù) )存儲線性表中數(shù)據(jù)元素 。 為了反映數(shù)據(jù)元素之間的 邏輯關系 ， 每個數(shù)據(jù)元素由兩部分組成： 1用于存放數(shù)據(jù)元素 (數(shù)據(jù)域 ) 2用于存放前件或后件的存儲地 址 (指針域 ) 數(shù)據(jù)域 指針域 結(jié)點之間邏輯關系由 指針域 來確定 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 37/82 單鏈表 定義： 每個結(jié)點只有 一個 指針域的鏈表 a1 a2 a3 a4 a5 ^ head ?每個單鏈表都有一個 頭指針 ， 存放表中第一個結(jié)點的存儲地址 。 ?每個結(jié)點指針域存放 后件 結(jié)點的存儲地址 ，最后一個結(jié)點無后件結(jié)點 ， 指針域為空 ，用 NULL或 ^ 表示 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 38/82 循環(huán)鏈表 循環(huán)鏈表中增設一個 表頭結(jié)點 ，其數(shù)據(jù)域的值可以任意或根據(jù)情況來設臵，指針域指向 第一個 結(jié)點 。 將單鏈表最后一個結(jié)點的空指針域改為指向該鏈表的第一個結(jié)點，即 首尾相連 。 head 空循環(huán)鏈表 a1 a2 … .. head an 注意頭指針和表頭結(jié)點的區(qū)別 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 39/82 循環(huán)鏈表特點： ?從表中任一結(jié)點出發(fā) ， 均可以找到其它所有結(jié)點； ?在任何情況下 ， 帶有表頭結(jié)點的循環(huán)鏈表中至少有一個結(jié)點存在 ， 從而使空表和非空表運算統(tǒng)一 。 循環(huán)鏈表運算與單鏈表區(qū)別： ?對單鏈表進行操作時 ， 要判斷是否是表尾 ，即指針是否為 NULL； ?而對循環(huán)鏈表操作時 ， 要判斷是否是頭指針 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 40/82 棧 定義：棧是只能在表的一端進行插入和刪除運算的 線性表 。 通常將允許插入和刪除運算的一端稱為 棧頂 (top)，另一端稱為 棧底 (bottom) 不含元素的棧稱為 空棧 。 向棧中插入元素稱為 入棧 。 從棧中刪除元素稱為 出棧 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 41/82 設有一個棧 S={a1,a2,… ,an}，入棧順序是a a2… 最后是 an。棧的狀態(tài)如圖所示： a1 a2 an … 棧底 bottom 棧頂 top 入棧 出棧 棧特點： 后進先出 。 故也稱為 “ 先進后出 ” 表或“ 后進先出 ” 表 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 42/82 棧的基本運算 ? 棧初始化： 構(gòu)造一個空棧。 ? 空棧判斷： 判斷棧是否為空。 ? 入棧： 在棧頂插入一個元素。 ? 出棧： 在棧頂刪除一個元素。 ? 讀棧： 僅讀取棧頂數(shù)據(jù)，并不刪除元素。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 43/82 棧的順序存儲 設用變量 top表示棧頂位臵，用 n表示棧中最多能容納元素的個數(shù)。 棧順序存儲結(jié)構(gòu)是用一塊連續(xù)存儲區(qū)域存放棧中元素。連續(xù)區(qū)域的 低地址 一端作為 棧底 ，棧底 固定不變 。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 44/82 入棧運算 S1： 如果 top=n， 則棧已滿 ， 提示入棧失敗(棧 “ 上溢 ” 錯誤 )， 并結(jié)束入棧； S2： top+1 ? top； S3： 將新元素放在當前棧頂位臵 (top)上 。 a1 a2 a3 bottom top a4 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 45/82 出棧運算 S1： 如果 top=0， 則棧為空 ， 提示出棧失敗(棧 “ 下溢 ” 錯誤 )， 并結(jié)束出棧； S2： 將當前棧頂 (top)元素賦給一個變量； S3： top – 1 ? top。 a3 top a1 a2 bottom 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 46/82 例如，容量為 6的棧中已有 3個元素 ,如圖所示： 1 2 3 4 5 6 A C B bottom top X、 Y兩個元素先后入棧 X Y 元素 Y出棧 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 47/82 隊 列 允許在一端進行插入 、 而在另一端進行刪除的 線性表 ， 允許插入的一端稱為 隊尾 ， 允許刪除的一端稱為 隊頭 。 入隊 退隊 隊尾 a b c 隊頭 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 48/82 隊列的基本運算 ?初始化隊列 ?空隊列判斷 ?入隊運算 ?出隊運算 ?讀隊頭元素 ?隊列長度 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 49/82 隊列順序存儲及其常用運算 隊列的特點 : ?先進先出 ?入隊和出隊運算時隊頭和隊尾位臵要發(fā)生變化 隊頭 — front(指向第一個元素的前一個單元位臵 ) 隊尾 — rear(指向最后一個元素的位臵 ) 隊列中容納元素個數(shù)為 n 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 50/82 創(chuàng)建一個空隊列 ,并令 front= rear=1 front 1 2 0 1 rear 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 51/82 2. 入隊運算 S1： 如果 rear=n1， 則隊列已滿 ， 提示入隊失敗 (隊列 “ 上溢 ” 錯誤 )， 并結(jié)束入隊； S2： rear+1 ?rear； S3： 將新元素放在當前隊列位臵 (rear)上 front rear 1 2 0 1 A B C 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 52/82 3. 退隊運算 S1： 如果 front=rear，則隊列已空 ,提示退隊失敗 (隊列 “ 下溢 ” 錯誤 ),并結(jié)束退隊； S2： front+1 ?front。 S3： 取 front所指元素 front rear 1 2 0 1 A B C 此時雖然隊列有空位置，但也不能插入新結(jié)點。 第六章 算法與數(shù)據(jù)結(jié)構(gòu)基礎 吉林大學公共計算機教學與研究中心制作 53/82 循環(huán)隊列 將隊列存儲空間的最后一個位臵繞到第一個位臵 ， 形成 邏輯上 的環(huán)狀空間 ，這樣可以把退隊的空間