數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版.ppt

目錄 第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組第6章樹第7章圖第8章查找第9章排序第10章文件 第1章緒論 1 1數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)1 2算法描述與分析1 3實(shí)習(xí) 常用算法實(shí)現(xiàn)及分析習(xí)題1 1 1數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 1 1 1引例首先分析學(xué)籍檔案類問題 設(shè)一個(gè)班級(jí)有50個(gè)學(xué)生 這個(gè)班級(jí)的學(xué)籍表如表1 1所示 表1 1學(xué)籍表 我們可以把表中每個(gè)學(xué)生的信息看成一個(gè)記錄 表中的每個(gè)記錄又由7個(gè)數(shù)據(jù)項(xiàng)組成 該學(xué)籍表由50個(gè)記錄組成 記錄之間是一種順序關(guān)系 這種表通常稱為線性表 數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為線性結(jié)構(gòu) 其主要操作有檢索 查找 插入或刪除等 又如 對(duì)于學(xué)院的行政機(jī)構(gòu) 可以把該學(xué)院的名稱看成樹根 把下設(shè)的若干個(gè)系看成它的樹枝中間結(jié)點(diǎn) 把每個(gè)系分出的若干專業(yè)方向看成樹葉 這樣就形成一個(gè)樹型結(jié)構(gòu) 如圖1 1所示 圖1 1專業(yè)設(shè)置 樹中的每個(gè)結(jié)點(diǎn)可以包含較多的信息 結(jié)點(diǎn)之間的關(guān)系不再是順序的 而是分層 分叉的結(jié)構(gòu) 樹型結(jié)構(gòu)的主要操作有遍歷 查找 插入或刪除等 最后分析交通問題 如果把若干個(gè)城鎮(zhèn)看成若干個(gè)頂點(diǎn) 再把城鎮(zhèn)之間的道路看成邊 它們可以構(gòu)成一個(gè)網(wǎng)狀的圖 如圖1 2所示 這種關(guān)系稱為圖型結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 在實(shí)際應(yīng)用中 假設(shè)某地區(qū)有5個(gè)城鎮(zhèn) 有一調(diào)查小組要對(duì)該地區(qū)每個(gè)城鎮(zhèn)進(jìn)行調(diào)查研究 并且每個(gè)城鎮(zhèn)僅能調(diào)查一次 試問調(diào)查路線怎樣設(shè)計(jì)才能以最高的效率完成此項(xiàng)工作 這是一個(gè)圖論方面的問題 交通圖的存儲(chǔ)和管理確實(shí)不屬于單純的數(shù)值計(jì)算問題 而是一種非數(shù)值的信息處理問題 圖1 2交通示意圖 1 1 2數(shù)據(jù)結(jié)構(gòu)有關(guān)概念及術(shù)語(yǔ)一般來說 數(shù)據(jù)結(jié)構(gòu)研究的是一類普通數(shù)據(jù)的表示及其相關(guān)的運(yùn)算操作 數(shù)據(jù)結(jié)構(gòu)是一門主要研究怎樣合理地組織數(shù)據(jù) 建立合適的數(shù)據(jù)結(jié)構(gòu) 提高計(jì)算機(jī)執(zhí)行程序所用的時(shí)間效率和空間效率的學(xué)科 1968年 美國(guó)的D E Knuth教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系 他的名著 計(jì)算機(jī)程序設(shè)計(jì)技巧 較為系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作 數(shù)據(jù)結(jié)構(gòu) 是計(jì)算機(jī)專業(yè)的一門專業(yè)基礎(chǔ)課 它為操作系統(tǒng) 數(shù)據(jù)庫(kù)原理 編譯原理等后繼專業(yè)課程的學(xué)習(xí)奠定了基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)涉及到各方面的知識(shí) 如計(jì)算機(jī)硬件范圍中的存儲(chǔ)裝置和存取方法 計(jì)算機(jī)軟件范圍中的文件系統(tǒng) 數(shù)據(jù)的動(dòng)態(tài)存儲(chǔ)與管理 信息檢索 數(shù)學(xué)范圍中的許多算法知識(shí) 在計(jì)算機(jī)科學(xué)中 數(shù)據(jù) Data 是描述客觀事物的數(shù)字 字符以及所有能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)處理的信息的總稱 除了數(shù)字 字符之外 還有用英文 漢字或其他語(yǔ)種字母組成的詞組 語(yǔ)句 以及表示圖形 圖像和聲音等的信息 這些也可稱為數(shù)據(jù) 數(shù)據(jù)元素 DataElement 是數(shù)據(jù)的基本單位 在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理 例如 圖1 1 專業(yè)設(shè)置樹 中的一個(gè)專業(yè) 圖1 2 交通圖 中的一個(gè)城鎮(zhèn)都可稱為一個(gè)數(shù)據(jù)元素 數(shù)據(jù)元素除了可以是一個(gè)數(shù)字或一個(gè)字符串以外 它也可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成 例如 表1 1中每個(gè)學(xué)生的學(xué)籍信息作為一個(gè)數(shù)據(jù)元素 在表中占一行 每個(gè)數(shù)據(jù)元素由序號(hào) 學(xué)號(hào) 姓名 性別 英語(yǔ)成績(jī)等7個(gè)數(shù)據(jù)項(xiàng)組成 數(shù)據(jù)項(xiàng) DataItem 是有獨(dú)立含義的數(shù)據(jù)的最小單位 有時(shí)也稱為字段 Field 數(shù)據(jù)對(duì)象 DataObject 是具有相同性質(zhì)的數(shù)據(jù)元素的集合 是數(shù)據(jù)的一個(gè)子集 例如 整數(shù)數(shù)據(jù)對(duì)象是集合N 0 1 2 字母字符數(shù)據(jù)對(duì)象是集合C A B Z 本節(jié)表1 1中的學(xué)籍表也可看成一個(gè)數(shù)據(jù)對(duì)象 數(shù)據(jù)結(jié)構(gòu) DataStructure 是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合 它是指數(shù)據(jù)元素之間的相互關(guān)系 即數(shù)據(jù)的組織形式 我們把數(shù)據(jù)元素間的邏輯上的聯(lián)系 稱為數(shù)據(jù)的邏輯結(jié)構(gòu) 常見的數(shù)據(jù)結(jié)構(gòu)有前文所介紹的線性結(jié)構(gòu) 樹型結(jié)構(gòu) 圖型結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)體現(xiàn)數(shù)據(jù)元素間的抽象化相互關(guān)系 并不涉及數(shù)據(jù)元素在計(jì)算機(jī)中具體的存儲(chǔ)方式 是獨(dú)立于計(jì)算機(jī)的 然而 討論數(shù)據(jù)結(jié)構(gòu)的目的是為了在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)數(shù)據(jù)的操作 因此還需要研究如何在計(jì)算機(jī)中表示數(shù)據(jù) 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)設(shè)備中的映像被稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 也可以說數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn) 又稱物理結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是依賴于計(jì)算機(jī)的 常見的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)等 關(guān)于它們的詳細(xì)解釋將在以后的章節(jié)中逐步給出 通常所謂的 數(shù)據(jù)結(jié)構(gòu) 是指數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)以及定義在它們之上的一組運(yùn)算 不論是存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì) 還是運(yùn)算的算法設(shè)計(jì) 都必須考慮存儲(chǔ)空間的開銷和運(yùn)行時(shí)間的效率 因此 數(shù)據(jù)結(jié)構(gòu) 課程不僅講授數(shù)據(jù)信息在計(jì)算機(jī)中的組織和表示方法 同時(shí)也訓(xùn)練學(xué)生高效地解決復(fù)雜問題程序設(shè)計(jì)的能力 1 2算法描述與分析 1 2 1什么是算法在解決實(shí)際問題時(shí) 當(dāng)確定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之后 需進(jìn)一步研究與之相關(guān)的一組操作 也稱運(yùn)算 主要有插入 刪除 排序 查找等 為了實(shí)現(xiàn)某種操作 如查找 常常需要設(shè)計(jì)一種算法 算法 Algorithm 是對(duì)特定問題求解步驟的一種描述 是指令的有限序列 描述算法需要一種語(yǔ)言 可以是自然語(yǔ)言 數(shù)學(xué)語(yǔ)言或者是某種計(jì)算機(jī)語(yǔ)言 算法一般具有下列5個(gè)重要特性 1 輸入 一個(gè)算法應(yīng)該有零個(gè) 一個(gè)或多個(gè)輸入 2 有窮性 一個(gè)算法必須在執(zhí)行有窮步驟之后正常結(jié)束 而不能形成無窮循環(huán) 3 確定性 算法中的每一條指令必須有確切的含義 不能產(chǎn)生多義性 4 可行性 算法中的每一個(gè)指令必須是切實(shí)可執(zhí)行的 即原則上可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn) 5 輸出 一個(gè)算法應(yīng)該至少有一個(gè)輸出 這些輸出是同輸入有某種特定關(guān)系的量 1 2 2算法描述工具 C語(yǔ)言如何選擇描述數(shù)據(jù)結(jié)構(gòu)和算法的語(yǔ)言是十分重要的問題 傳統(tǒng)的描述方法是用PASCAL語(yǔ)言 在Windows環(huán)境下涌現(xiàn)出一系列功能強(qiáng)大 面向?qū)ο蟮拿枋龉ぞ?如VisualC BorlandC VisualBasic VisualFoxPro等 近年來在計(jì)算機(jī)科學(xué)研究 系統(tǒng)開發(fā) 教學(xué)以及應(yīng)用開發(fā)中 C語(yǔ)言的使用越來越廣泛 因此 本教材采用C語(yǔ)言進(jìn)行算法描述 為了能夠簡(jiǎn)明扼要地描述算法 突出算法的思路 而不拘泥于語(yǔ)言語(yǔ)法的細(xì)節(jié) 本書有以下約定 1 問題的規(guī)模尺寸用MAXSIZE表示 約定在宏定義中已經(jīng)預(yù)先定義過 例如 defineMAXSIZE100 2 數(shù)據(jù)元素的類型一般寫成ELEMTP 可以認(rèn)為在宏定義中預(yù)先定義過 例如 defineELEMTPint在上機(jī)實(shí)驗(yàn)時(shí)根據(jù)需要 可臨時(shí)用其他某個(gè)具體的類型標(biāo)識(shí)符來代替 3 一個(gè)算法要以函數(shù)形式給出 類型標(biāo)識(shí)符函數(shù)名 帶類型說明的形參表 語(yǔ)句組 例如 intadd inta intb intc c a b return c 除了形參類型說明放在圓括號(hào)中之外 在描述算法的函數(shù)中其他變量的類型說明一般省略不寫 這樣使算法的處理過程更加突出明了 4 關(guān)于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義以及全局變量的說明等均應(yīng)在寫算法之前進(jìn)行說明 下面的例子給出了書寫算法的一般步驟 例1 1有n個(gè)整數(shù) 將它們按由大到小的順序排序 并且輸出 分析 n個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)是線性表 a1 a2 a3 an 選用一維數(shù)組作存儲(chǔ)結(jié)構(gòu) 每個(gè)數(shù)組元素有兩個(gè)域 一個(gè)是數(shù)據(jù)的序號(hào)域 一個(gè)是數(shù)據(jù)的值域 structnode intnum 序號(hào)域 intdata 值域 算法描述1 1 voidsimsort structnodea MAXSIZE intn 數(shù)組a的數(shù)據(jù)由主函數(shù)提供 inti j m for i 1 i n i for j 1 j n j if a i data a j data m a i a i a j a j m for i i i n i printf 8d 8d 10d n i a i num a j data 1 2 3算法分析技術(shù)初步著名的計(jì)算機(jī)科學(xué)家N 沃思提出了一個(gè)有名的公式 算法 數(shù)據(jù)結(jié)構(gòu) 程序 由此可見 數(shù)據(jù)結(jié)構(gòu)和算法是程序的兩大要素 二者相輔相成 缺一不可 一種數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣是在實(shí)現(xiàn)其各種運(yùn)算的算法中體現(xiàn)的 對(duì)數(shù)據(jù)結(jié)構(gòu)的分析實(shí)質(zhì)上也就是對(duì)實(shí)現(xiàn)其多種運(yùn)算的算法的分析 評(píng)價(jià)一個(gè)算法應(yīng)從四個(gè)方面進(jìn)行 正確性 簡(jiǎn)單性 運(yùn)行時(shí)間 占用空間 但主要看這個(gè)算法所要占用機(jī)器資源的多少 而在這些資源中時(shí)間和空間是兩個(gè)最主要的方面 因此算法分析中最關(guān)心的也就是算法所需的時(shí)間代價(jià)和空間代價(jià) 1 空間所謂算法的空間代價(jià) 或稱空間復(fù)雜性 是指當(dāng)問題的規(guī)模以某種單位由1增至n時(shí) 解決該問題的算法實(shí)現(xiàn)所占用的空間也以某種單位由1增至f n 并稱該算法的空間代價(jià)是f n 2 時(shí)間 1 語(yǔ)句頻度 FrequencyCount 指的是在一個(gè)算法中該語(yǔ)句重復(fù)執(zhí)行的次數(shù) 2 算法的漸近時(shí)間復(fù)雜度 AsymptoticTimeComplexity 算法中基本操作重復(fù)執(zhí)行的次數(shù)依據(jù)算法中最大語(yǔ)句頻度來估算 它是問題規(guī)模n的某個(gè)函數(shù)f n 算法的時(shí)間量度記作T n O f n 表示隨著問題規(guī)模n的增大 算法執(zhí)行時(shí)間的增長(zhǎng)率和f n 的增長(zhǎng)率相同 稱作算法的漸近時(shí)間復(fù)雜度 簡(jiǎn)稱時(shí)間復(fù)雜度 時(shí)間復(fù)雜度往往不是精確的執(zhí)行次數(shù) 而是估算的數(shù)量級(jí) 它著重體現(xiàn)的是隨著問題規(guī)模的增大 算法執(zhí)行時(shí)間增長(zhǎng)的變化趨勢(shì) 1 3實(shí)習(xí) 常用算法實(shí)現(xiàn)及分析 例如 在下列三個(gè)程序段中 a x x 1 b for i 1 i n i x x 1 c for j 1 j n j for k 1 k n k x x 1 語(yǔ)句x x 1的頻度分別為1 n和n2 則 a b c 的時(shí)間復(fù)雜度分別是O 1 O n O n2 由此可見 隨著問題規(guī)模的增大 其時(shí)間消耗也在增大 下面以 c 程序段為例 進(jìn)行時(shí)間復(fù)雜度的分析 步驟1 先把所有語(yǔ)句改為基本操作 j 1 1a ifj nn 1 k 1 n 1b ifk nn n 1 x x 1 n nk n ngotob j n 1gotoa 步驟2 分析每一條語(yǔ)句的語(yǔ)句頻度 標(biāo)到每條語(yǔ)句后邊 如上 步驟3 統(tǒng)計(jì)總的語(yǔ)句頻度 1 n 1 n n n 1 n2 n2 n 3n2 4n 2 步驟4 判斷最大語(yǔ)句頻度為n2 所以時(shí)間復(fù)雜度為O n2 其中O表示等價(jià)無窮小 現(xiàn)在來分析例1 1中算法1 1的時(shí)間復(fù)雜度 算法中有一個(gè)二重循環(huán) if語(yǔ)句的執(zhí)行頻度為 n n 1 n 2 3 2 1 數(shù)量級(jí)為O n2 算法中輸出語(yǔ)句的頻度為n 數(shù)量級(jí)為O n 該算法的時(shí)間復(fù)雜度以if語(yǔ)句的執(zhí)行頻度來估算 忽略輸出部分 則記為O n2 算法還可能呈現(xiàn)的時(shí)間復(fù)雜度有指數(shù)階O lbn 等 習(xí)題1 1 簡(jiǎn)述下列術(shù)語(yǔ) 數(shù)據(jù)元素 數(shù)據(jù) 數(shù)據(jù)對(duì)象 數(shù)據(jù)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 2 試寫一算法 自大至小依次輸出順序讀入的3個(gè)整數(shù)x y和z的值 分析算法的元素比較次數(shù)和元素移動(dòng)次數(shù) 3 舉出一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子 敘述其邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) 運(yùn)算等三方面的內(nèi)容 4 敘述算法的定義及其重要特性 5 分析并寫出下面的各語(yǔ)句組所代表的算法的時(shí)間復(fù)雜度 1 for i 1 i n i for j 1 j i j for k 1 k j k s i k printf d s 2 i 1 k 0 while i n 1 k k 10 i i 3 i 1 k 0 n 100 do k k 10 i i while i n 4 i 1 j 0 while i jj j elsei 5 x n n 1 y 0 while x y 1 y 1 y 6 m 91 n 100 while n 0 if m 0 m m 1 n elsem 第2章線性表 2 1線性表引例2 2線性表的定義和基本運(yùn)算2 3線性表的順序存儲(chǔ)結(jié)構(gòu)2 4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2 5循環(huán)鏈表和雙向鏈表2 6實(shí)習(xí) 線性表的應(yīng)用實(shí)例習(xí)題2 2 1線性表引例 例2 1某大學(xué)欲進(jìn)行一次數(shù)學(xué)競(jìng)賽 約有200名學(xué)生報(bào)名參賽 現(xiàn)將報(bào)名登記表 如表2 1所示 存入計(jì)算機(jī)以便完成如下工作 1 能正確錄入學(xué)生記錄 2 按成績(jī)對(duì)該表進(jìn)行重新排序 3 按學(xué)號(hào)或姓名查詢學(xué)生成績(jī) 表2 1報(bào)名登記表 2 2線性表的定義和基本運(yùn)算 2 2 1線性表的概念線性表是指n n 0 個(gè)具有相同類型數(shù)據(jù)元素 或稱結(jié)點(diǎn) 的有限序列 可表示為 a1 a2 ai an 其中 ai代表一個(gè)數(shù)據(jù)元素 a1稱為表頭 或頭結(jié)點(diǎn) an稱為表尾 或尾結(jié)點(diǎn) ai 0 i n 稱為ai 1的直接前驅(qū) ai 1稱為ai的直接后繼 線性表中數(shù)據(jù)元素的個(gè)數(shù)稱為線性表的長(zhǎng)度 長(zhǎng)度為0的線性表稱為空表 記為 在不同的問題中 數(shù)據(jù)元素代表的具體含義不同 它可以是一個(gè)數(shù)字 一個(gè)字符 也可以是一句話 甚至其他更復(fù)雜的信息 例如 線性表L1 12 58 45 2 45 46 其元素為數(shù)字 線性表L2 a g r d s t 其元素為字母 表2 1也是一個(gè)線性表 其數(shù)據(jù)元素較為復(fù)雜 每個(gè)學(xué)生的學(xué)號(hào) 姓名 性別 成績(jī)構(gòu)成一個(gè)數(shù)據(jù)元素 這種由若干數(shù)據(jù)項(xiàng)構(gòu)成的數(shù)據(jù)元素常稱為記錄 含有大量記錄的線性表稱為文件 2 2 2表的基本運(yùn)算線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu) 對(duì)其數(shù)據(jù)元素可以進(jìn)行各種運(yùn)算 操作 如對(duì)表2 1 應(yīng)不僅能查詢成績(jī) 還能根據(jù)需要增加或刪除學(xué)生記錄 下面給出線性表一些基本運(yùn)算的含義 這些運(yùn)算的實(shí)現(xiàn)算法后面將具體討論 1 Initiate L 初始化運(yùn)算 該函數(shù)用于設(shè)定一個(gè)空的線性表L 2 Length L 求長(zhǎng)度函數(shù) 該函數(shù)返回給定線性表L中數(shù)據(jù)元素的個(gè)數(shù) 3 Get L i 取元素操作 若1 i Length L 則函數(shù)值為給定線性表中第i個(gè)數(shù)據(jù)元素 否則為空元素NULL 4 Prior L x 求前驅(qū)函數(shù) 當(dāng)x在線性表L中 且其位序大于1 則函數(shù)值為x的直接前驅(qū) 否則為空元素 5 Next L x 求后繼函數(shù) 當(dāng)x在線性表L中 且其位序小于Length L 則函數(shù)值為x的直接后繼 否則為空元素 6 Locate L x 定位操作 如線性表中存在和x相等的數(shù)據(jù)元素 則返回該數(shù)據(jù)元素的位序 若滿足條件的元素不惟一 則返回最小的位序 7 Insert L i x 前插操作 若1 i Length L 1 則在線性表L中第i個(gè)元素之前插入新結(jié)點(diǎn)x 8 Delete L i 刪除操作 若1 i Length L 則刪除線性表L中第i個(gè)元素 9 Empty L 判空函數(shù) 若L為空表 則返回值為1 表示 真 否則返回值為0 表示 假 10 Clear L 置空操作 將線性表L值為空表 利用這些基本運(yùn)算還可實(shí)現(xiàn)對(duì)線性表的各種復(fù)雜操作 如將兩個(gè)線性表進(jìn)行合并 重新復(fù)制一個(gè)線性表 對(duì)線性表中的元素按某個(gè)數(shù)據(jù)項(xiàng)遞增 或遞減 的順序進(jìn)行重新排序等 讀者可將以上基本運(yùn)算應(yīng)用于表2 1 理解在具體問題中各種運(yùn)算的具體含義 2 3線性表的順序存儲(chǔ)結(jié)構(gòu) 2 3 1向量的存儲(chǔ)特點(diǎn)在計(jì)算機(jī)內(nèi) 線性表可以用不同的方式來存儲(chǔ) 其中最簡(jiǎn)單 最常用的方式就是順序存儲(chǔ) 即用一組連續(xù)的存儲(chǔ)單元依次存放線性表中的元素 這種順序存儲(chǔ)的線性表稱為順序表 又叫向量 假設(shè)線性表每個(gè)元素占s個(gè)存儲(chǔ)單元 并以其所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置 則線性表中第i 1個(gè)元素的存儲(chǔ)位置Loc ai 1 和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc ai 之間滿足下列關(guān)系 Loc ai 1 Loc ai s 設(shè)線性表的起始位置 或稱基址 是Loc a1 因每個(gè)元素所占用的空間大小相同 則元素ai的存放位置為 Loc ai Loc a1 s i 1 由此可見 線性表的順序存儲(chǔ)結(jié)構(gòu)是用數(shù)據(jù)元素在計(jì)算機(jī)內(nèi) 物理位置相鄰 來表示數(shù)據(jù)元素之間的邏輯相鄰關(guān)系 其特點(diǎn)是向量中邏輯上相鄰的結(jié)點(diǎn)在計(jì)算機(jī)的存儲(chǔ)結(jié)構(gòu)中也相鄰 如圖2 1所示 而且 只要知道了向量的基地址 由上式即可確定向量中任一數(shù)據(jù)元素的地址 從而對(duì)其可隨機(jī)存取 圖2 1線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 在C語(yǔ)言中 可以用一維數(shù)組來描述向量 definemaxsizeN 設(shè)置線性表的最大長(zhǎng)度為N N為整數(shù) typedefstruct datatypedata maxsize 1 datatype為元素的數(shù)據(jù)類型 它可是TurboC中 允許的任何數(shù)據(jù)類型 intlast 記錄當(dāng)前表中元素的個(gè)數(shù) Sqlist 上述描述方法 將線性表順序存儲(chǔ)結(jié)構(gòu)中的信息封裝隱藏在類型Sqlist結(jié)構(gòu)中 data數(shù)組描述了線性表中數(shù)據(jù)元素占用的空間 數(shù)組中第i個(gè)分量就是線性表中第i個(gè)數(shù)據(jù)元素 last描述了當(dāng)前表中數(shù)據(jù)元素的個(gè)數(shù)即表長(zhǎng) 說明 在C語(yǔ)言中 數(shù)組的下標(biāo)是從0開始的 但為了算法描述方便 本書中凡涉及數(shù)組的算法 規(guī)定下標(biāo)從1開始 這樣 讀者可不必考慮下標(biāo)為0的數(shù)組元素 2 3 2向量中基本運(yùn)算的實(shí)現(xiàn)1 定位操作Locate L x 定位操作返回線性表L中值和x相同的第一個(gè)元素的位置 算法如下 算法描述2 1 IntLocate SqlistL Datatypex inti 1 while i L last 也可按數(shù)據(jù)元素的某個(gè)關(guān)鍵數(shù)據(jù)項(xiàng)進(jìn)行數(shù)據(jù)元素的定位 例如 表2 1所示的學(xué)生成績(jī)表可按學(xué)號(hào)或姓名進(jìn)行定位 只需將上面算法中data i 和x換成相應(yīng)數(shù)據(jù)項(xiàng)即可 請(qǐng)讀者參閱后面實(shí)例 算法描述2 1的基本操作是 進(jìn)行兩個(gè)元素之間的比較 若線性表L中存在值和x相等的數(shù)據(jù)元素ai 則需進(jìn)行i 1 i L last 次比較 否則 進(jìn)行L last次比較 直至i超出表長(zhǎng) 所以該算法的時(shí)間復(fù)雜度為O n 2 向量的插入運(yùn)算Insert L i x 線性表的插入操作是指在線性表的第i 1個(gè)元素和第i元素之間插入一個(gè)新的數(shù)據(jù)元素 使長(zhǎng)度為n的線性表 a1 a2 ai ai 1 an 變成長(zhǎng)度為n 1的線性表 a1 a2 ai x ai 1 an 1 顯然數(shù)據(jù)元素ai和ai 1的邏輯關(guān)系發(fā)生了變化 對(duì)向量而言 邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰 因此 必須將第i i n 1 至第n個(gè)元素依次向后移一個(gè)位置 空出位置放入x 才能反映這個(gè)邏輯關(guān)系上的變化 其具體算法如下 算法描述2 2 voidInsert SqlistL inti Datatypex intj if iL last printf infeasibleposition n else if L last 1 maxsize printf overflow n else for j L last j i j L data j 1 L data j L data i x L last 3 向量的刪除運(yùn)算Delete L x 與向量的插入運(yùn)算道理相同 當(dāng)刪除線性表中第i個(gè)元素時(shí) 也改變了原數(shù)據(jù)間的邏輯關(guān)系 故需將第i 1 iL last printf infeasible n else for j i j L last j L data j L data j 1 L last 從算法2 2和2 3可以看出 在向量中某個(gè)位置插入或刪除一個(gè)數(shù)據(jù)元素時(shí) 其時(shí)間主要耗費(fèi)在移動(dòng)元素上 故應(yīng)將移動(dòng)元素的操作作為預(yù)估算法時(shí)間復(fù)雜度的基本操作 假定在線性表中任意位置插入元素的概率相等 即p 1 n 1 那么在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為 同理 在線性表中刪除任意一個(gè)元素時(shí)所需移動(dòng)元素的平均次數(shù)為 Edelete pd n i 1 n i 1 所以 對(duì)于長(zhǎng)度為n的線性表 算法Insert和算法Delete的時(shí)間復(fù)雜度均為O n 2 4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2 4 1線性鏈表與線性表的順序存儲(chǔ)結(jié)構(gòu)不同 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元 可以是連續(xù)的 也可以是不連續(xù)的 來存儲(chǔ)線性表的數(shù)據(jù)元素 為表示相鄰數(shù)據(jù)元素之間的邏輯關(guān)系 將每個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩個(gè)域 數(shù)據(jù)域用來存放一個(gè)數(shù)據(jù)元素的自身信息 指針域用來存放該數(shù)據(jù)元素直接后繼的存儲(chǔ)位置 這樣 可以通過指針域中存放的信息 稱為指針或鏈 將n個(gè)結(jié)點(diǎn)連接成一個(gè)鏈表 即成為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 由于這種存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)只有一個(gè)指針域 故又將其稱為線性單鏈表或單向鏈表 圖2 2給出了線性表 A B C D 的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 由于最后一個(gè)元素沒有直接后繼 則其結(jié)點(diǎn)的指針域應(yīng)為 空 NULL 另外 由圖2 2可以看出 頭指針指向鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置 每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的指針域中 因此 單向鏈表的存取必須從頭指針開始 它是一種非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu) 用線性鏈表表示線性表時(shí) 數(shù)據(jù)元素之間的邏輯關(guān)系由結(jié)點(diǎn)中的指針指示 故邏輯上相鄰的數(shù)據(jù)元素其物理位置不要求緊鄰 這與線性表的順序存儲(chǔ)結(jié)構(gòu)完全不同 圖2 2單向鏈表的存儲(chǔ)結(jié)構(gòu)示意圖 我們?cè)谑褂面湵頃r(shí)往往只關(guān)心它所表示的數(shù)據(jù)元素之間的邏輯順序 而不是每個(gè)元素在存儲(chǔ)器中的實(shí)際位置 因此 為了分析方便 把鏈表畫成用箭頭相連接的結(jié)點(diǎn)的序列 結(jié)點(diǎn)之間的箭頭表示鏈域中的指針 如圖2 2可畫成圖2 3所示的形式 圖2 3單向鏈表的邏輯狀態(tài)圖 根據(jù)上述分析 單向鏈表可由頭指針惟一確定 故在C語(yǔ)言中可用指針數(shù)據(jù)類型來描述 TypedefstructNode Datatypedata structNode next Node LList 一個(gè)單向鏈表對(duì)應(yīng)一個(gè)頭指針head head是一個(gè)LList類型的變量 即它是一個(gè)指向Node類型結(jié)點(diǎn)的指針變量 并指向單向鏈表的第1個(gè)結(jié)點(diǎn) 通過它可以訪問該單向鏈表 若頭指針為 空 即head NULL 則表示一個(gè)空表 一般在單向鏈表中附加一個(gè)頭結(jié)點(diǎn) 其指針域指向鏈表的第一個(gè)結(jié)點(diǎn) 而其數(shù)據(jù)域可以存儲(chǔ)一些如鏈表長(zhǎng)度之類的附加信息 也可以什么都不存儲(chǔ) 這樣 鏈表的頭指針將指向頭結(jié)點(diǎn) 如圖2 4所示 表空的條件是頭結(jié)點(diǎn)的指針域?yàn)?空 即head next NULL 圖2 4帶表頭的單鏈表 2 4 2單向鏈表基本運(yùn)算的實(shí)現(xiàn)1 取單鏈表中元素Get L i 該函數(shù)返回線性表L中第i個(gè)數(shù)據(jù)元素的值 算法思路 從頭指針出發(fā) 借用指針p 從第1個(gè)結(jié)點(diǎn)開始 順著后繼指針向后尋找第i個(gè)元素 若存在第i個(gè)元素 即1 i Length L 則通過p返回該元素的值 算法描述2 4 DatatypeGetLList LListL inti LListp intj 1 p L next while p NULL 該算法的基本操作是比較j和i并后移指針 若第i個(gè)元素存在 則需執(zhí)行基本操作i 1次 否則執(zhí)行n次 故算法2 4的時(shí)間復(fù)雜度均為O n 2 定位函數(shù)Locate L x 該函數(shù)在線性鏈表中尋找值與x相等的數(shù)據(jù)元素 若有 則返回其存儲(chǔ)位置 否則返回NULL 其算法2 5思路與算法2 4相似 其時(shí)間復(fù)雜度均也為O n 算法描述2 5 LListLocate LListL Datatypex LListp p L next while p NULL 3 單鏈表的插入Insert L i x 該函數(shù)在線性鏈表第i個(gè)元素之前插入一個(gè)數(shù)據(jù)元素x 算法思路 先生成一個(gè)包含數(shù)據(jù)元素x的新結(jié)點(diǎn) 用s指向它 再找到鏈表中第i 1個(gè)結(jié)點(diǎn) 用p指向它 修改這兩個(gè)結(jié)點(diǎn)的指針即可 指針修改如圖2 5所示 用語(yǔ)句描述為 s next p next p next s 注意 修改指針的順序 若先修改第i 1個(gè)結(jié)點(diǎn)的指針 使其指向待插結(jié)點(diǎn) 那么 第i個(gè)結(jié)點(diǎn)的地址將丟失 鏈表 斷開 待插結(jié)點(diǎn)將無法與第i個(gè)結(jié)點(diǎn)鏈接 圖2 5單向鏈表中插入結(jié)點(diǎn)時(shí)指針的變化情況 a 插入前 b 插入后 算法描述2 6 voidInsetLList LListL inti Datatypex LListp s intj 0 p L while p NULL 4 單鏈表的刪除Delete L i 該函數(shù)刪除線性鏈表中第i個(gè)數(shù)據(jù)結(jié)點(diǎn) 顯然 只要找到第i 1個(gè)結(jié)點(diǎn)修改其指針使它跳過第i個(gè)結(jié)點(diǎn) 而直接指向第i 1個(gè)結(jié)點(diǎn)即可 但要注意 刪除的結(jié)點(diǎn)應(yīng)及時(shí)向系統(tǒng)釋放 以便系統(tǒng)再次利用 指針變化如圖2 6所示 語(yǔ)句描述為p next p next next 圖2 6單向鏈表中刪除結(jié)點(diǎn)時(shí)指針的變化情況 其具體算法描述如下 算法描述2 7 voidDelete LListL inti LListp q intj 0 p L while p NULL 由于在單向鏈表中插入和刪除結(jié)點(diǎn)時(shí) 僅需修改相應(yīng)結(jié)點(diǎn)的指針 而不需移動(dòng)元素 該程序的執(zhí)行時(shí)間主要耗費(fèi)在查找結(jié)點(diǎn)上 由算法2 4知訪問結(jié)點(diǎn)的時(shí)間復(fù)雜度為O n 所以算法2 6和算法2 7的時(shí)間復(fù)雜度均為O n 5 單鏈表的建立Crt LList L n 建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程 即從 空表 的初始狀態(tài)起 依次建立各元素結(jié)點(diǎn) 并逐個(gè)插入鏈表 下面是一個(gè)從表尾到表頭建立單鏈表的算法 其時(shí)間復(fù)雜度是O n 算法描述2 8 voidCrt LList LListh intn LListp q inti h LList malloc sizeof Node h next NULL p h for i 1 idata q next NULL p next q p q 說明 上面算法中分別引用了TurboC語(yǔ)言的兩個(gè)標(biāo)準(zhǔn)函數(shù)malloc 和free 設(shè)p為L(zhǎng)List型變量 則執(zhí)行p LList malloc sizeof Node 的作用是向系統(tǒng)申請(qǐng)一個(gè)Node型的結(jié)點(diǎn) 同時(shí)讓p指向該結(jié)點(diǎn) 執(zhí)行free p 的作用是向系統(tǒng)釋放一個(gè)由p所指的Node型的結(jié)點(diǎn) 已釋放的空間可供系統(tǒng)再次使用 2 5循環(huán)鏈表和雙向鏈表 2 5 1循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 其特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn) 整個(gè)鏈表呈環(huán)狀 從表中任意結(jié)點(diǎn)出發(fā)都可到達(dá)其他結(jié)點(diǎn) 如圖2 7所示為單循環(huán)鏈表 圖2 7單循環(huán)鏈表 a 非空表 b 空表 循環(huán)鏈表和單鏈表算法實(shí)現(xiàn)基本相同 差別僅在于前者算法中的循環(huán)條件是判p或p next是否為空 而后者是判它們是否等于頭指針 有時(shí)為了簡(jiǎn)化某些操作在鏈表中設(shè)立尾指針 而不是頭指針 例如 將兩個(gè)用循環(huán)鏈表存儲(chǔ)的線性表合并成一個(gè)線性表 此時(shí)僅需將一個(gè)表的表尾和另一個(gè)表的表頭相連即可 指針變化如圖2 8所示 用語(yǔ)句描述為 p A next A next B next next B next p 操作只改變了兩個(gè)指針值 其算法的時(shí)間復(fù)雜度均為O 1 圖2 8循環(huán)鏈表合并示意圖 a 合并前 b 合并后 2 5 2雙向鏈表單向鏈表的結(jié)點(diǎn)只有一個(gè)指示其直接后繼的指針域 順著某結(jié)點(diǎn)的指針可很容易地訪問其后諸結(jié)點(diǎn) 但若要訪問某結(jié)點(diǎn)的直接前驅(qū) 前驅(qū)雖與該結(jié)點(diǎn)相鄰卻無法直達(dá) 此時(shí)需從表頭出發(fā) 且尋訪時(shí)要記錄相關(guān)信息 為克服單向鏈表這種訪問方式的單向性 特設(shè)計(jì)了雙向鏈表 如圖2 9 b 所示 顯然 在雙向鏈表的結(jié)點(diǎn)中應(yīng)有兩個(gè)指針域 一個(gè)指向直接后繼 一個(gè)指向直接前驅(qū) 如圖2 9 a 所示 雙向鏈表在TurboC語(yǔ)言中可描述如下 typedefstructdnode datatypedata structdnode prior structdnode next DNode DList 圖2 9雙向鏈表示例 a 結(jié)點(diǎn)結(jié)構(gòu) b 雙向鏈表 圖2 10雙向循環(huán)鏈表示例 a 空表 b 非空表 在雙向鏈表中 Length L Get L i Locate L x 等操作僅涉及一個(gè)方向的指針 其算法描述與單鏈表相同 但插入和刪除操作有所不同 在雙向鏈表中需同時(shí)修改兩個(gè)方向的指針 圖2 11和圖2 12分別顯示了刪除和插入結(jié)點(diǎn)時(shí)指針的修改情況 其具體算法讀者可自己完成 圖2 11雙向鏈表中刪除結(jié)點(diǎn)時(shí)指針的修改情況 圖2 12雙向鏈表中插入結(jié)點(diǎn)時(shí)指針的修改情況 在雙向鏈表中刪除結(jié)點(diǎn)時(shí)指針的變化用語(yǔ)句描述為 p prior next p next p next prior p prior free p 在雙向鏈表中插入結(jié)點(diǎn)時(shí)指針的變化用語(yǔ)句描述為 s prior p prior p prior next s s next p p prior s 2 5 3線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的比較在計(jì)算機(jī)中 線性表有兩類不同的存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 它們各有特點(diǎn) 順序表的特點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中也相鄰 它是一種可隨機(jī)存取存儲(chǔ)結(jié)構(gòu) 在C語(yǔ)言中 用一維數(shù)組來描述 有以下三方面的缺點(diǎn) 1 在插入和刪除結(jié)點(diǎn)時(shí) 需移動(dòng)大量元素 2 在對(duì)長(zhǎng)度較大的線性表預(yù)先分配空間時(shí) 必須按最大空間分配 從而使存儲(chǔ)空間得不到充分利用 3 表的容量難以擴(kuò)充 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素其物理位置不要求緊鄰 它是一種非隨機(jī)存取存儲(chǔ)結(jié)構(gòu) 在C語(yǔ)言中用 結(jié)點(diǎn)指針 來描述 它克服了順序表上述的三個(gè)缺點(diǎn) 但卻不具備像順序表那樣隨機(jī)存取的優(yōu)點(diǎn) 在實(shí)踐中應(yīng)仔細(xì)分析 根據(jù)不同研究對(duì)象的特點(diǎn)和經(jīng)常進(jìn)行的操作選擇合適的存儲(chǔ)結(jié)構(gòu) 2 6實(shí)習(xí) 線性表的應(yīng)用實(shí)例 實(shí)例1 利用順序表實(shí)現(xiàn)例2 1的完整C語(yǔ)言程序 defmaxsize250typedefstruct structstudent intnum char name chargender floatscore data maxsize 1 intlast Sqlist include stdio h voidInitiate L SqlistL L last 0 intLocate L x SqlistL intx inti 1 while ix i if i L last return i elsereturn 0 voidsort L SqlistL inti j studentx for i 2 i L last i L data 0 L data 1 j i 1 x L data i num while x L data j num L data j 1 L data j j j 1 L data j 1 L data 0 main SqlistL inti 1 num Initiate L printf inputdata please 1 end n scanf num d printf doyouwanttofindastudent y n while getchar y printf inputthenumberofthestudent scanf d 實(shí)例2 多項(xiàng)式相加問題 1 存儲(chǔ)結(jié)構(gòu)的選取任一一元多項(xiàng)式可表示為Pn x P0 P1x P2x2 Pnxn 顯然 由其n 1個(gè)系數(shù)可惟一確定該多項(xiàng)式 故一元多項(xiàng)式可用一個(gè)僅存儲(chǔ)其系數(shù)的線性表來表示 多項(xiàng)式指數(shù)i隱含于Pi的序號(hào)中 P P0 P1 P2 Pn 若采用順序存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)這個(gè)線性表 那么多項(xiàng)式相加的算法實(shí)現(xiàn)十分容易 同位序元素相加即可 但當(dāng)多項(xiàng)式的次數(shù)很高而且變化很大時(shí) 采用這種順序存儲(chǔ)結(jié)構(gòu)極不合理 例如 多項(xiàng)式S x 1 3x 12x999需用一長(zhǎng)度為1000的線性表來表示 而表中僅有三個(gè)非零元素 這樣將大量浪費(fèi)內(nèi)存空間 此時(shí)可考慮另一種表示方法 如線性表S x 可表示成S 1 0 3 1 12 999 其元素包含兩個(gè)數(shù)據(jù)項(xiàng) 系數(shù)項(xiàng)和指數(shù)項(xiàng) 這種表示方法在計(jì)算機(jī)內(nèi)對(duì)應(yīng)兩種存儲(chǔ)方式 當(dāng)只對(duì)多項(xiàng)式進(jìn)行訪問 求值等不改變多項(xiàng)式指數(shù) 即表的長(zhǎng)度不變化 的操作時(shí) 宜采用順序存儲(chǔ)結(jié)構(gòu) 當(dāng)要對(duì)多項(xiàng)式進(jìn)行加法 減法 乘法等改變多項(xiàng)式指數(shù)的操作時(shí) 宜采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2 一元多項(xiàng)加法運(yùn)算的實(shí)現(xiàn)采用單鏈表結(jié)構(gòu)來實(shí)現(xiàn)多項(xiàng)加法運(yùn)算 無非是前述單向鏈表基本運(yùn)算的綜合應(yīng)用 其數(shù)據(jù)結(jié)構(gòu)描述如下 typedefstuctPnode floatcoef intexp structpnode next Pnode Ploytp 圖2 13給出了多項(xiàng)式A x 15 6x 9x7 3x18和B x 4x 5x6 16x7的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 設(shè)一元多項(xiàng)式均按升冪形式存儲(chǔ) 首指針為 1 圖2 13一元多項(xiàng)式的存儲(chǔ) 若上例A B結(jié)果仍存于A中 根據(jù)一元多項(xiàng)式相加的運(yùn)算規(guī)則 其實(shí)質(zhì)是將B逐項(xiàng)按指數(shù)分情況合并于 和多項(xiàng)式 A中 設(shè)p q分別指向A B的第一個(gè)結(jié)點(diǎn) 如圖2 14所示 其算法思路如下 1 p expexp 應(yīng)使指針后移p p next 如圖2 14 a 所示 2 p exp q exp 將兩個(gè)結(jié)點(diǎn)系數(shù)相加 若系數(shù)和不為零 則修改p ceof 并借助s釋放當(dāng)前q結(jié)點(diǎn) 而使q指向多項(xiàng)式B的下一個(gè)結(jié)點(diǎn) 如圖2 14 b 所示 若系數(shù)和為零 則應(yīng)借助s釋放p q結(jié)點(diǎn) 而使p q分別指向多項(xiàng)式A B的下一個(gè)結(jié)點(diǎn) 3 p exp q exp 將q結(jié)點(diǎn)在p結(jié)點(diǎn)之前插入A中 并使q指向多項(xiàng)式B的下一個(gè)結(jié)點(diǎn) 如圖2 14 c 所示 直到q NULL為止或p NULL 將B的剩余項(xiàng)鏈到A尾為止 最后釋放B的頭結(jié)點(diǎn) 圖2 14多項(xiàng)式相加運(yùn)算示例 下面給出從接收多項(xiàng)式到完成多項(xiàng)式相加運(yùn)算的完整C語(yǔ)言程序 include stdio h voidCrt Polytp h n Polytph intn Polytp q inti h Polytp malloc sizeof Pnode h next NULL p h for i 1 iceof intCmp a b floata b if ab return 1 voidAddPoly pa pb pc Polytppa pb pc Polytpp q pre s p pa next q pb next pre pa pc pa while p NULL qNULL w cmp p exp q exp switch w case 1 pre p p p next break case0 sum p coef q coef if sum0 p coef sum pre p else pre next p next free p p pre next s q q q next free s break case1 s q next q next p pre next q pre q q s break if pbNULL pre next q free pb main Ploytppa pb pc q intn1 n2 printf inputthelengthofpaandpb scanf n1 d n2 d Crt Polytp pa n1 Crt Polytp pb n2 AddPolytp pa pb pc p pc next printf pc pa pb while pNULL printf f d p ceof p exp p p next 習(xí)題2 1 判斷下列概念的正確性 1 線性表在物理存儲(chǔ)空間中也一定是連續(xù)的 2 鏈表的物理存儲(chǔ)結(jié)構(gòu)具有與鏈表一樣的順序 3 鏈表的刪除算法很簡(jiǎn)單 因?yàn)楫?dāng)刪去鏈表中某個(gè)結(jié)點(diǎn)后 計(jì)算機(jī)會(huì)自動(dòng)地將后繼的各個(gè)單元向前移動(dòng) 2 試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn) 3 試寫出一個(gè)計(jì)算鏈表中數(shù)據(jù)元素結(jié)點(diǎn)個(gè)數(shù)的算法 其中指針p指向該鏈表的第一個(gè)結(jié)點(diǎn) 4 試設(shè)計(jì)實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)的算法 5 有一個(gè)性表 a1 a2 an 它存儲(chǔ)在有附加表頭結(jié)點(diǎn)的單鏈表中 寫一個(gè)算法 求出該線性表中值為x的元素的序號(hào) 如果x不存在 則輸出序號(hào)為0 6 寫一個(gè)算法將一單鏈表逆置 要求操作在原鏈表上進(jìn)行 7 設(shè)有兩個(gè)鏈表A B 它們的數(shù)據(jù)元素分別為 x1 x2 xm 和 y1 y2 yn 寫一個(gè)算法將它們合并為一個(gè)線性表C 使得 當(dāng)m n時(shí) C xl y1 x2 y2 xn yn xm 當(dāng)m n時(shí) C yl xl y2 x2 ym xm yn 8 在一個(gè)非遞減有序線性表中 插入一個(gè)值為x的元素 使插入后的線性仍為非遞減有序 試分別用向量和單鏈表編寫算法 9 寫一個(gè)算法將值為b的結(jié)點(diǎn)插在鏈表中值為a的結(jié)點(diǎn)之后 如果值為a的結(jié)點(diǎn)不存在 則插入在表尾 第3章棧和隊(duì)列 3 1棧和隊(duì)列引例3 2棧3 3順序棧的存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn)3 4鏈?zhǔn)綏? 5隊(duì)列3 6實(shí)習(xí) 棧的應(yīng)用實(shí)例習(xí)題3 3 1棧和隊(duì)列引例 任一表達(dá)式都可看成是由操作數(shù) 運(yùn)算符和界限符組成的一個(gè)串 其中 操作數(shù)可以是常數(shù)也可以是變量或常量的標(biāo)識(shí)符 運(yùn)算符可以是算術(shù)運(yùn)算符 關(guān)系運(yùn)算符和邏輯運(yùn)算符等 界限符包括左右括號(hào)和表達(dá)式結(jié)束符等 例表達(dá)式7 4 8 3 計(jì)算機(jī)要完成表達(dá)式的求值 必須正確的解釋表達(dá)式 將其翻譯成正確的機(jī)器指令序列 要了解計(jì)算機(jī)的求值過程 必須先研究棧的性質(zhì) 3 2棧 3 2 1棧的定義和基本運(yùn)算棧是限定只能在表尾進(jìn)行插入和刪除的線性表 并將表尾稱為棧頂 表頭稱為棧底 圖3 1給出了非空棧s A B C D 的示意圖 圖3 1非空棧示意圖 由于限定只能在棧頂進(jìn)行操作 所以棧中元素必按A B C D次序進(jìn)棧 按D C B A次序出棧 即按 后進(jìn)先出 或 先進(jìn)后出 的原則進(jìn)行操作的 這一特點(diǎn)可用生活中的實(shí)例形象說明 例如每次只能容一個(gè)人進(jìn)出的死胡同就相當(dāng)一個(gè)棧 胡同口相當(dāng)于棧頂 而胡同的另一端則為棧底 3 2 2棧的基本運(yùn)算 1 判?？誆mpty S 若棧為空則返回 真 否則返回 假 2 入棧操作 壓棧 Push S x 將新元素壓入棧中 使其成為棧頂元素 3 出棧操作 彈棧 Pop S x 若棧不空則返回棧頂元素 并從棧中刪除棧頂元素 否則返回NULL 4 取棧頂元素Pettop s x 若棧不空則返回棧頂元素 否則返回NULL 5 置空棧Clear s 將當(dāng)前棧設(shè)定為空棧 6 求元素個(gè)數(shù)CurrenSize s 求當(dāng)前棧中元素的個(gè)數(shù) 3 3順序棧的存儲(chǔ)結(jié)構(gòu)及算法實(shí)現(xiàn) 3 3 1順序棧順序棧利用一組連續(xù)的存儲(chǔ)單元存放從棧底到棧頂?shù)闹T元素 同時(shí)用一指針top指示當(dāng)前棧頂元素的位置 C語(yǔ)言中用一維數(shù)組來描述 definemaxsizeNtypedefstruct Datatypedata maxsize 1 inttop Stack a 空棧 b 一般情況 c 滿棧圖3 2棧中元素和棧頂指針之間的關(guān)系 3 3 2順序棧的基本運(yùn)算的實(shí)現(xiàn)判棧空 置空棧 求元素個(gè)數(shù)算法容易實(shí)現(xiàn) 只要判斷或改變s top的值即可 下面僅給出進(jìn)棧 出棧 取棧頂元素等函數(shù)的算法實(shí)現(xiàn) 1 壓棧 算法描述3 1 intPush StackS Datatypex if S top maxsize printf overflow n return 0 S data S top x return 1 2 出棧 算法描述3 2 intPop Stacks Datatypex if S top 0 printf nudertflow n return 0 x S data S top S top return 1 3 取棧頂元素 算法描述3 3 intGettop StackS Datatypex if S top 0 printf nodata N return 0 x S data top return 1 3 4鏈?zhǔn)綏?鏈?zhǔn)綏５慕M織形式和單鏈表類似 其類型說明如下TyoedefstructNode Datatypedata structNode next Node LStack 一個(gè)鏈棧由其棧頂指針唯一確定 設(shè)TOP是LStack形變量 則TOP指向棧頂元素 圖3 3為鏈棧示意圖 top NULL為判斷?？盏臈l件 對(duì)鏈棧除非整個(gè)可用空間都被占滿 否則不會(huì)出現(xiàn)棧滿的情形 其操作是線性鏈表操作的特例 易實(shí)現(xiàn) 請(qǐng)讀者自行補(bǔ)充 圖3 3鏈棧示意圖 3 5隊(duì)列 3 5 1隊(duì)列的定義和運(yùn)算和棧相反 隊(duì)列是一種 先進(jìn)先出 的線性表 他只允許再表的一端 稱表尾 插入元素 在表的另一端 表頭 刪除元素 隊(duì)列和日常生活中的排隊(duì)是一致的 最早進(jìn)入隊(duì)列的元素最早得到服務(wù) 圖3 4給出可隊(duì)列示意圖 圖3 4隊(duì)列示意圖 隊(duì)列的操作與棧的操作類似 不同的是刪除運(yùn)算是在表頭進(jìn)行 1 判隊(duì)空EmptyQueue Q 若隊(duì)列為空則返回 真 否則返回 假 2 入隊(duì)InQueue Q x 將新元素x插入到隊(duì)尾 3 出隊(duì)OutQueue Q x 若隊(duì)列不空則返回隊(duì)首的第一個(gè)元素元素 并從隊(duì)列中刪除該元素 否則返回NULL 4 置空隊(duì)列InitQueue Q 將當(dāng)隊(duì)列設(shè)定為空隊(duì)列 5 求元素個(gè)數(shù)CurrentSize Q 返回當(dāng)前隊(duì)列中元素的個(gè)數(shù) 3 5 2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其算法實(shí)現(xiàn)和棧類似 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)用一個(gè)向量來存儲(chǔ)隊(duì)列中的元素 不過還需兩個(gè)指針來指示隊(duì)頭元素和對(duì)尾元素在隊(duì)列中的當(dāng)前位置 C語(yǔ)言描述如下 definemaxsizeNtypedefstuct Datatypeadta maxsize 1 intfront rear Queue a 滿隊(duì) b 一般情況 c 空隊(duì)圖3 5順序隊(duì)列示意圖 3 5 3順序隊(duì)列的基本運(yùn)算 1 判隊(duì)空 算法描述3 4 intEmptyQueue QueueQ if Q front Q rear return 1 elsereturn 0 入隊(duì) 算法描述3 5 intInQueue QueueQ Datatypex if Q rear maxsize printf overflow return 0 Q rear Q data Q rear x return 1 3 出隊(duì) 算法描述3 6 intOutQueue QueueQ Datatypex if EmptyQueue Q printf underflow return 0 x Q data Q front 1 Q front if EmptyQueue Q Q front 0 Q rear 0 return 1 3 5 4循環(huán)隊(duì)列上述算法中判隊(duì)列滿的條件為Q rear maxsize 用它來分析一下圖3 5所示的隊(duì)列狀態(tài) 此時(shí) maxsize 5 Q front 3 Q rear 5 顯然不能作入隊(duì)操作 但隊(duì)列中實(shí)際元素個(gè)數(shù)并未達(dá)到maxsize 這種現(xiàn)象稱之為假溢出 解決這一問題的一個(gè)辦法是在發(fā)生假溢出時(shí)將隊(duì)列中全部元素向前移動(dòng)指頭指針為零 但這樣很浪費(fèi)時(shí)間 另一種辦法是設(shè)想一個(gè)循環(huán)隊(duì)列 假想Q data 1 接在Q data maxsize 之后 如圖3 6所示 由于循環(huán)隊(duì)列的特點(diǎn) 隊(duì)列中的元素可以存放在數(shù)組中下標(biāo)從0到maxsize 1的共maxsize各位置 a 空隊(duì) b 非空隊(duì) c 滿隊(duì)圖3 6循環(huán)隊(duì)列示意圖 從上圖不難看出 無論空隊(duì)還是滿隊(duì)都有Q front Q rear 從而無法判斷屬于那一種情況 為此可少用一個(gè)元素空間 而以隊(duì)尾指針加1等于頭指針來作為滿隊(duì)的標(biāo)志 即 隊(duì)空 Q front Q rear 隊(duì)滿 Q front Q rear 1 maxsize 循環(huán)隊(duì)列的置空算法和非循環(huán)隊(duì)列的置空算法相同 其入隊(duì)和出隊(duì)算法如下 1 入隊(duì) 算法描述3 7 intInQueue QueueQ Datatypex if Q rear 1 maxsize Q front printf overflow return 0 Q rear Q rear maxsizeQ data Q rear x Return 1 2 出隊(duì) 算法描述3 8 ntOutQueue QueueQ Datatypex if EmptyQueue Q printf underflow return 0 Q front Q front maxsizex Q data Q front return 1 3 6實(shí)習(xí) 棧的應(yīng)用實(shí)例 1 表達(dá)式的構(gòu)成任一表達(dá)式都可看成是由操作數(shù) 運(yùn)算符和界限符組成的一個(gè)串 其中 操作數(shù)可以是常數(shù)也可以是變量或常量的標(biāo)識(shí)符 運(yùn)算符可以是算術(shù)運(yùn)算符 關(guān)系運(yùn)算符和邏輯運(yùn)算符等 界限符包括左右括號(hào)和表達(dá)式結(jié)束符等 例表達(dá)式7 4 8 3 為論述方便 這里僅介紹簡(jiǎn)單算術(shù)表達(dá)式的求值問題 2 算符的優(yōu)先關(guān)系要對(duì)表達(dá)式正確求值 必須正確的解釋表達(dá)式 將其翻譯成正確的機(jī)器指令序列 例如 要對(duì)表達(dá)式3 7 2 求值 首先要了解算術(shù)運(yùn)算的規(guī)則 即1 從左到右 2 先括號(hào)內(nèi) 后括號(hào)外 3