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

目錄 第1章緒論第2章線性表第3章棧和隊(duì)列第4章串第5章數(shù)組第6章樹(shù)第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é)籍檔案類(lèi)問(wèn)題 設(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)系 這種表通常稱(chēng)為線性表 數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱(chēng)為線性結(jié)構(gòu) 其主要操作有檢索 查找 插入或刪除等 又如 對(duì)于學(xué)院的行政機(jī)構(gòu) 可以把該學(xué)院的名稱(chēng)看成樹(shù)根 把下設(shè)的若干個(gè)系看成它的樹(shù)枝中間結(jié)點(diǎn) 把每個(gè)系分出的若干專(zhuān)業(yè)方向看成樹(shù)葉 這樣就形成一個(gè)樹(shù)型結(jié)構(gòu) 如圖1 1所示 圖1 1專(zhuān)業(yè)設(shè)置 樹(shù)中的每個(gè)結(jié)點(diǎn)可以包含較多的信息 結(jié)點(diǎn)之間的關(guān)系不再是順序的 而是分層 分叉的結(jié)構(gòu) 樹(shù)型結(jié)構(gòu)的主要操作有遍歷 查找 插入或刪除等 最后分析交通問(wèn)題 如果把若干個(gè)城鎮(zhèn)看成若干個(gè)頂點(diǎn) 再把城鎮(zhèn)之間的道路看成邊 它們可以構(gòu)成一個(gè)網(wǎng)狀的圖 如圖1 2所示 這種關(guān)系稱(chēng)為圖型結(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)查一次 試問(wèn)調(diào)查路線怎樣設(shè)計(jì)才能以最高的效率完成此項(xiàng)工作 這是一個(gè)圖論方面的問(wèn)題 交通圖的存儲(chǔ)和管理確實(shí)不屬于單純的數(shù)值計(jì)算問(wèn)題 而是一種非數(shù)值的信息處理問(wèn)題 圖1 2交通示意圖 1 1 2數(shù)據(jù)結(jié)構(gòu)有關(guān)概念及術(shù)語(yǔ)一般來(lái)說(shuō) 數(shù)據(jù)結(jié)構(gòu)研究的是一類(lèi)普通數(shù)據(jù)的表示及其相關(guān)的運(yùn)算操作 數(shù)據(jù)結(jié)構(gòu)是一門(mén)主要研究怎樣合理地組織數(shù)據(jù) 建立合適的數(shù)據(jù)結(jié)構(gòu) 提高計(jì)算機(jī)執(zhí)行程序所用的時(shí)間效率和空間效率的學(xué)科 1968年 美國(guó)的D E Knuth教授開(kāi)創(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ī)專(zhuān)業(yè)的一門(mén)專(zhuān)業(yè)基礎(chǔ)課 它為操作系統(tǒng) 數(shù)據(jù)庫(kù)原理 編譯原理等后繼專(zhuān)業(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ī)處理的信息的總稱(chēng) 除了數(shù)字 字符之外 還有用英文 漢字或其他語(yǔ)種字母組成的詞組 語(yǔ)句 以及表示圖形 圖像和聲音等的信息 這些也可稱(chēng)為數(shù)據(jù) 數(shù)據(jù)元素 DataElement 是數(shù)據(jù)的基本單位 在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理 例如 圖1 1 專(zhuān)業(yè)設(shè)置樹(shù) 中的一個(gè)專(zhuān)業(yè) 圖1 2 交通圖 中的一個(gè)城鎮(zhèn)都可稱(chēng)為一個(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í)也稱(chēng)為字段 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)系 稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu) 常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有前文所介紹的線性結(jié)構(gòu) 樹(shù)型結(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è)備中的映像被稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 也可以說(shuō)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn) 又稱(chēng)物理結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是依賴(lài)于計(jì)算機(jī)的 常見(jiàn)的存儲(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ǔ)空間的開(kāi)銷(xiāo)和運(yùn)行時(shí)間的效率 因此 數(shù)據(jù)結(jié)構(gòu) 課程不僅講授數(shù)據(jù)信息在計(jì)算機(jī)中的組織和表示方法 同時(shí)也訓(xùn)練學(xué)生高效地解決復(fù)雜問(wèn)題程序設(shè)計(jì)的能力 1 2算法描述與分析 1 2 1什么是算法在解決實(shí)際問(wèn)題時(shí) 當(dāng)確定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之后 需進(jìn)一步研究與之相關(guān)的一組操作 也稱(chēng)運(yùn)算 主要有插入 刪除 排序 查找等 為了實(shí)現(xiàn)某種操作 如查找 常常需要設(shè)計(jì)一種算法 算法 Algorithm 是對(duì)特定問(wèn)題求解步驟的一種描述 是指令的有限序列 描述算法需要一種語(yǔ)言 可以是自然語(yǔ)言 數(shù)學(xué)語(yǔ)言或者是某種計(jì)算機(jī)語(yǔ)言 算法一般具有下列5個(gè)重要特性 1 輸入 一個(gè)算法應(yīng)該有零個(gè) 一個(gè)或多個(gè)輸入 2 有窮性 一個(gè)算法必須在執(zhí)行有窮步驟之后正常結(jié)束 而不能形成無(wú)窮循環(huán) 3 確定性 算法中的每一條指令必須有確切的含義 不能產(chǎn)生多義性 4 可行性 算法中的每一個(gè)指令必須是切實(shí)可執(zhí)行的 即原則上可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn) 5 輸出 一個(gè)算法應(yīng)該至少有一個(gè)輸出 這些輸出是同輸入有某種特定關(guān)系的量 1 2 2算法描述工具 C語(yǔ)言如何選擇描述數(shù)據(jù)結(jié)構(gòu)和算法的語(yǔ)言是十分重要的問(wèn)題 傳統(tǒng)的描述方法是用PASCAL語(yǔ)言 在Windows環(huán)境下涌現(xiàn)出一系列功能強(qiáng)大 面向?qū)ο蟮拿枋龉ぞ?如VisualC BorlandC VisualBasic VisualFoxPro等 近年來(lái)在計(jì)算機(jī)科學(xué)研究 系統(tǒng)開(kāi)發(fā) 教學(xué)以及應(yīng)用開(kāi)發(fā)中 C語(yǔ)言的使用越來(lái)越廣泛 因此 本教材采用C語(yǔ)言進(jìn)行算法描述 為了能夠簡(jiǎn)明扼要地描述算法 突出算法的思路 而不拘泥于語(yǔ)言語(yǔ)法的細(xì)節(jié) 本書(shū)有以下約定 1 問(wèn)題的規(guī)模尺寸用MAXSIZE表示 約定在宏定義中已經(jīng)預(yù)先定義過(guò) 例如 defineMAXSIZE100 2 數(shù)據(jù)元素的類(lèi)型一般寫(xiě)成ELEMTP 可以認(rèn)為在宏定義中預(yù)先定義過(guò) 例如 defineELEMTPint在上機(jī)實(shí)驗(yàn)時(shí)根據(jù)需要 可臨時(shí)用其他某個(gè)具體的類(lèi)型標(biāo)識(shí)符來(lái)代替 3 一個(gè)算法要以函數(shù)形式給出 類(lèi)型標(biāo)識(shí)符函數(shù)名 帶類(lèi)型說(shuō)明的形參表 語(yǔ)句組 例如 intadd inta intb intc c a b return c 除了形參類(lèi)型說(shuō)明放在圓括號(hào)中之外 在描述算法的函數(shù)中其他變量的類(lèi)型說(shuō)明一般省略不寫(xiě) 這樣使算法的處理過(guò)程更加突出明了 4 關(guān)于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類(lèi)型定義以及全局變量的說(shuō)明等均應(yīng)在寫(xiě)算法之前進(jìn)行說(shuō)明 下面的例子給出了書(shū)寫(xiě)算法的一般步驟 例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) 程序 由此可見(jiàn) 數(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à) 或稱(chēng)空間復(fù)雜性 是指當(dāng)問(wèn)題的規(guī)模以某種單位由1增至n時(shí) 解決該問(wèn)題的算法實(shí)現(xiàn)所占用的空間也以某種單位由1增至f n 并稱(chēng)該算法的空間代價(jià)是f n 2 時(shí)間 1 語(yǔ)句頻度 FrequencyCount 指的是在一個(gè)算法中該語(yǔ)句重復(fù)執(zhí)行的次數(shù) 2 算法的漸近時(shí)間復(fù)雜度 AsymptoticTimeComplexity 算法中基本操作重復(fù)執(zhí)行的次數(shù)依據(jù)算法中最大語(yǔ)句頻度來(lái)估算 它是問(wèn)題規(guī)模n的某個(gè)函數(shù)f n 算法的時(shí)間量度記作T n O f n 表示隨著問(wèn)題規(guī)模n的增大 算法執(zhí)行時(shí)間的增長(zhǎng)率和f n 的增長(zhǎng)率相同 稱(chēng)作算法的漸近時(shí)間復(fù)雜度 簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度 時(shí)間復(fù)雜度往往不是精確的執(zhí)行次數(shù) 而是估算的數(shù)量級(jí) 它著重體現(xiàn)的是隨著問(wè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 由此可見(jiàn) 隨著問(wèn)題規(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à)無(wú)窮小 現(xiàn)在來(lái)分析例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í)行頻度來(lái)估算 忽略輸出部分 則記為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 試寫(xiě)一算法 自大至小依次輸出順序讀入的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 分析并寫(xiě)出下面的各語(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)或姓名查詢(xún)學(xué)生成績(jī) 表2 1報(bào)名登記表 2 2線性表的定義和基本運(yùn)算 2 2 1線性表的概念線性表是指n n 0 個(gè)具有相同類(lèi)型數(shù)據(jù)元素 或稱(chēng)結(jié)點(diǎn) 的有限序列 可表示為 a1 a2 ai an 其中 ai代表一個(gè)數(shù)據(jù)元素 a1稱(chēng)為表頭 或頭結(jié)點(diǎn) an稱(chēng)為表尾 或尾結(jié)點(diǎn) ai 0 i n 稱(chēng)為ai 1的直接前驅(qū) ai 1稱(chēng)為ai的直接后繼 線性表中數(shù)據(jù)元素的個(gè)數(shù)稱(chēng)為線性表的長(zhǎng)度 長(zhǎng)度為0的線性表稱(chēng)為空表 記為 在不同的問(wèn)題中 數(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ù)元素常稱(chēng)為記錄 含有大量記錄的線性表稱(chēng)為文件 2 2 2表的基本運(yùn)算線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu) 對(duì)其數(shù)據(jù)元素可以進(jìn)行各種運(yùn)算 操作 如對(duì)表2 1 應(yīng)不僅能查詢(xún)成績(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 理解在具體問(wèn)題中各種運(yùn)算的具體含義 2 3線性表的順序存儲(chǔ)結(jié)構(gòu) 2 3 1向量的存儲(chǔ)特點(diǎn)在計(jì)算機(jī)內(nèi) 線性表可以用不同的方式來(lái)存儲(chǔ) 其中最簡(jiǎn)單 最常用的方式就是順序存儲(chǔ) 即用一組連續(xù)的存儲(chǔ)單元依次存放線性表中的元素 這種順序存儲(chǔ)的線性表稱(chēng)為順序表 又叫向量 假設(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è)線性表的起始位置 或稱(chēng)基址 是Loc a1 因每個(gè)元素所占用的空間大小相同 則元素ai的存放位置為 Loc ai Loc a1 s i 1 由此可見(jiàn) 線性表的順序存儲(chǔ)結(jié)構(gòu)是用數(shù)據(jù)元素在計(jì)算機(jī)內(nèi) 物理位置相鄰 來(lá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ù)組來(lái)描述向量 definemaxsizeN 設(shè)置線性表的最大長(zhǎng)度為N N為整數(shù) typedefstruct datatypedata maxsize 1 datatype為元素的數(shù)據(jù)類(lèi)型 它可是TurboC中 允許的任何數(shù)據(jù)類(lèi)型 intlast 記錄當(dāng)前表中元素的個(gè)數(shù) Sqlist 上述描述方法 將線性表順序存儲(chǔ)結(jié)構(gòu)中的信息封裝隱藏在類(lèi)型Sqlist結(jié)構(gòu)中 data數(shù)組描述了線性表中數(shù)據(jù)元素占用的空間 數(shù)組中第i個(gè)分量就是線性表中第i個(gè)數(shù)據(jù)元素 last描述了當(dāng)前表中數(shù)據(jù)元素的個(gè)數(shù)即表長(zhǎng) 說(shuō)明 在C語(yǔ)言中 數(shù)組的下標(biāo)是從0開(kāi)始的 但為了算法描述方便 本書(shū)中凡涉及數(shù)組的算法 規(guī)定下標(biāo)從1開(kāi)始 這樣 讀者可不必考慮下標(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ù)的 來(lái)存儲(chǔ)線性表的數(shù)據(jù)元素 為表示相鄰數(shù)據(jù)元素之間的邏輯關(guān)系 將每個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩個(gè)域 數(shù)據(jù)域用來(lái)存放一個(gè)數(shù)據(jù)元素的自身信息 指針域用來(lái)存放該數(shù)據(jù)元素直接后繼的存儲(chǔ)位置 這樣 可以通過(guò)指針域中存放的信息 稱(chēng)為指針或鏈 將n個(gè)結(jié)點(diǎn)連接成一個(gè)鏈表 即成為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 由于這種存儲(chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)只有一個(gè)指針域 故又將其稱(chēng)為線性單鏈表或單向鏈表 圖2 2給出了線性表 A B C D 的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 由于最后一個(gè)元素沒(méi)有直接后繼 則其結(jié)點(diǎn)的指針域應(yīng)為 空 NULL 另外 由圖2 2可以看出 頭指針指向鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置 每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的指針域中 因此 單向鏈表的存取必須從頭指針開(kāi)始 它是一種非隨機(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í)際位置 因此 為了分析方便 把鏈表畫(huà)成用箭頭相連接的結(jié)點(diǎn)的序列 結(jié)點(diǎn)之間的箭頭表示鏈域中的指針 如圖2 2可畫(huà)成圖2 3所示的形式 圖2 3單向鏈表的邏輯狀態(tài)圖 根據(jù)上述分析 單向鏈表可由頭指針惟一確定 故在C語(yǔ)言中可用指針數(shù)據(jù)類(lèi)型來(lái)描述 TypedefstructNode Datatypedata structNode next Node LList 一個(gè)單向鏈表對(duì)應(yīng)一個(gè)頭指針head head是一個(gè)LList類(lèi)型的變量 即它是一個(gè)指向Node類(lèi)型結(jié)點(diǎn)的指針變量 并指向單向鏈表的第1個(gè)結(jié)點(diǎn) 通過(guò)它可以訪問(wèn)該單向鏈表 若頭指針為 空 即head NULL 則表示一個(gè)空表 一般在單向鏈表中附加一個(gè)頭結(jié)點(diǎn) 其指針域指向鏈表的第一個(gè)結(jié)點(diǎn) 而其數(shù)據(jù)域可以存儲(chǔ)一些如鏈表長(zhǎng)度之類(lèi)的附加信息 也可以什么都不存儲(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)開(kāi)始 順著后繼指針向后尋找第i個(gè)元素 若存在第i個(gè)元素 即1 i Length L 則通過(guò)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)的地址將丟失 鏈表 斷開(kāi) 待插結(jié)點(diǎn)將無(wú)法與第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)修改其指針使它跳過(guò)第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知訪問(wèn)結(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)的過(guò)程就是一個(gè)動(dòng)態(tài)生成鏈表的過(guò)程 即從 空表 的初始狀態(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 說(shuō)明 上面算法中分別引用了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)的指針可很容易地訪問(wèn)其后諸結(jié)點(diǎn) 但若要訪問(wèn)某結(jié)點(diǎn)的直接前驅(qū) 前驅(qū)雖與該結(jié)點(diǎn)相鄰卻無(wú)法直達(dá) 此時(shí)需從表頭出發(fā) 且尋訪時(shí)要記錄相關(guān)信息 為克服單向鏈表這種訪問(wè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ī)中 線性表有兩類(lèi)不同的存儲(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ù)組來(lái)描述 有以下三方面的缺點(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)指針 來(lái)描述 它克服了順序表上述的三個(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)式相加問(wèn)題 1 存儲(chǔ)結(jié)構(gòu)的選取任一一元多項(xiàng)式可表示為Pn x P0 P1x P2x2 Pnxn 顯然 由其n 1個(gè)系數(shù)可惟一確定該多項(xiàng)式 故一元多項(xiàng)式可用一個(gè)僅存儲(chǔ)其系數(shù)的線性表來(lái)表示 多項(xiàng)式指數(shù)i隱含于Pi的序號(hào)中 P P0 P1 P2 Pn 若采用順序存儲(chǔ)結(jié)構(gòu)來(lái)存儲(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的線性表來(lái)表示 而表中僅有三個(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)行訪問(wè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)來(lái)實(shí)現(xiàn)多項(xiàng)加法運(yùn)算 無(wú)非是前述單向鏈表基本運(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 試寫(xiě)出一個(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)的單鏈表中 寫(xiě)一個(gè)算法 求出該線性表中值為x的元素的序號(hào) 如果x不存在 則輸出序號(hào)為0 6 寫(xiě)一個(gè)算法將一單鏈表逆置 要求操作在原鏈表上進(jìn)行 7 設(shè)有兩個(gè)鏈表A B 它們的數(shù)據(jù)元素分別為 x1 x2 xm 和 y1 y2 yn 寫(xiě)一個(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的元素 使插入后的線性仍為非遞減有序 試分別用向量和單鏈表編寫(xiě)算法 9 寫(xiě)一個(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ī)的求值過(guò)程 必須先研究棧的性質(zhì) 3 2棧 3 2 1棧的定義和基本運(yùn)算棧是限定只能在表尾進(jìn)行插入和刪除的線性表 并將表尾稱(chēng)為棧頂 表頭稱(chēng)為棧底 圖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í)例形象說(shuō)明 例如每次只能容一個(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ù)組來(lái)描述 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織形式和單鏈表類(lèi)似 其類(lèi)型說(shuō)明如下TyoedefstructNode Datatypedata structNode next Node LStack 一個(gè)鏈棧由其棧頂指針唯一確定 設(shè)TOP是LStack形變量 則TOP指向棧頂元素 圖3 3為鏈棧示意圖 top NULL為判斷棧空的條件 對(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)先出 的線性表 他只允許再表的一端 稱(chēng)表尾 插入元素 在表的另一端 表頭 刪除元素 隊(duì)列和日常生活中的排隊(duì)是一致的 最早進(jìn)入隊(duì)列的元素最早得到服務(wù) 圖3 4給出可隊(duì)列示意圖 圖3 4隊(duì)列示意圖 隊(duì)列的操作與棧的操作類(lèi)似 不同的是刪除運(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)和棧類(lèi)似 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)用一個(gè)向量來(lái)存儲(chǔ)隊(duì)列中的元素 不過(guò)還需兩個(gè)指針來(lái)指示隊(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 用它來(lái)分析一下圖3 5所示的隊(duì)列狀態(tài) 此時(shí) maxsize 5 Q front 3 Q rear 5 顯然不能作入隊(duì)操作 但隊(duì)列中實(shí)際元素個(gè)數(shù)并未達(dá)到maxsize 這種現(xiàn)象稱(chēng)之為假溢出 解決這一問(wè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ì)列示意圖 從上圖不難看出 無(wú)論空隊(duì)還是滿隊(duì)都有Q front Q rear 從而無(wú)法判斷屬于那一種情況 為此可少用一個(gè)元素空間 而以隊(duì)尾指針加1等于頭指針來(lái)作為滿隊(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á)式的求值問(wèn)題 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