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

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