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