第3章-數(shù)據結構(編輯修改稿)
2024-09-01 19:42 本頁面
【文章內容簡介】 ? 表是一組有序的數(shù)據元素 ? 每一數(shù)據元素包含一個或多個數(shù)據項 ? 每一數(shù)據元素與唯一的關鍵字相關聯(lián) 學號 姓名 性別 年齡 系別 19808801 趙仁 男 28 計算機系 19901023 錢廣 男 23 數(shù)學系 19701001 李惠 女 25 數(shù)學系 行：數(shù)據元素 關鍵字 23 167。 表 二、運算 ? 求出一個表所含數(shù)據元素個數(shù) ? 對于給定關鍵字，查找表中相應數(shù)據元素 ? 在表中指定位置上插入一個數(shù)據元素 ? 刪除表中指定位置上的數(shù)據元素 ? 按某種要求對表中數(shù)據元素重新排序 24 167。 表 三、存儲方式 ? 順序存放 ? 把表中元素依次存放在一組連續(xù)的單元內 ? 訪問方便快捷，更新操作復雜 ? 設表的基地址為 addr(a1)，假定每個數(shù)據元素占用k 個存儲單元，則的存儲單元的首地址為 addr[ai] = addr(a1) + (i 1) ? k 25 167。 表 ? 鏈式存放 ? 表的每一記錄增設一個指針，指明后繼元素的存儲單元的首地址 ? 特點 ? 無須連續(xù)和順序排放 ? 更新簡單 ? 增加空間開銷 ? 檢索必須從鏈頭開始，效率低 26 167。 棧 一、定義 二、特性 三、存儲 四、操作 27 167。 棧 一、定義 ? 棧是一種操作受限的線性表 ? 對于棧的插入和刪除操作都限制在表的末端進行 ? 將表的末端稱為棧頂，起始位置稱為棧底 二、特性 ? 每次刪除的總是最后插入的表目，而最先插入的表目則放在棧的底部，要到最后才能刪除，因此棧是“后進先出表”或下推表 ? 食堂里的一疊盤子 ? 算術表達式、遞歸 28 167。 棧 三、存儲 ?用向量（由相同數(shù)據類型組成的線性序列）表示棧，并用指針指示棧頂?shù)奈恢? ai ai1 … … a2 a1 棧底 棧頂 棧頂指示器 ?i 29 167。 棧 四、操作 ? push(ST, X)：往棧 ST中壓入一個值為 X的表目 ? pop(ST)：從棧 ST中彈出一個表目 ? top(ST, X)：把棧頂表目的值讀到變量 X中，棧保持不變 ? sempty(ST)：判斷棧是否為空 ? ?？臻g大小是預先設定的，稱為棧容量，如果棧已存滿，再進行 push操作，則棧將上溢出(overflow)；如果棧里已沒有表目，再進行 pop操作，則棧將下溢出 (underflow) 30 167。 隊列 一、定義 二、存儲 三、操作 31 167。 隊列 一、定義 ? 隊列是一種操作受限的線性表 ? 對于隊列的插入在表的一端進行，刪除操作在表的另一端進行 ? 進行刪除的一端稱為隊列的頭，進行插入的一端稱為隊列的尾 ? 新來的成員總是加入到隊尾，每次離開的總是隊頭上的元素 (先進先出 ) 32 167。 隊列 二、存儲 ? 用順序表實現(xiàn)，分配一塊連續(xù)存儲區(qū)域存放隊列中的元素，用兩個指針分別指向隊列的頭尾 ? 當隊列首尾指針相連時，發(fā)生隊列溢出 … ai ai+1 … aj 頭指針 尾指針 … an1 an 頭指針 尾指針 假溢出 33 167。 隊列 三、操作 ? enq(QU, X)：往隊列 QU中插入一個值為 X的表目 ? deq(QU)：從隊列 QU中刪除一個表目
教學課件相關推薦
鄂ICP備17016276號-1