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