軟件技術(shù)基礎(chǔ)教學(xué)緒論

1、第一章第一章 軟件技術(shù)基礎(chǔ)軟件技術(shù)基礎(chǔ) 軟件設(shè)計能力是大學(xué)生的一種基本能力軟件設(shè)計能力是大學(xué)生的一種基本能力 科研需要：現(xiàn)有工具軟件并不總能滿足科研需要：現(xiàn)有工具軟件并不總能滿足 要求要求 工作需要：現(xiàn)代工業(yè)離不開自動化設(shè)備，工作需要：現(xiàn)代工業(yè)離不開自動化設(shè)備， 自動化設(shè)備離不開計算機的控制，計算自動化設(shè)備離不開計算機的控制，計算 機的靈魂是軟件。機的靈魂是軟件。 對于一個非計算機專業(yè)的人來說，對于一個非計算機專業(yè)的人來說，“如如 何學(xué)、學(xué)什么何學(xué)、學(xué)什么”是學(xué)習(xí)計算機技術(shù)的重是學(xué)習(xí)計算機技術(shù)的重 要問題。要問題。 為什么學(xué)習(xí) 這門課？ 如何學(xué)、學(xué)什么 n如何學(xué)如何學(xué) 興趣興趣 +實踐實踐 n

2、學(xué)什么學(xué)什么 將本專業(yè)和計算機的應(yīng)用聯(lián)系起來。在學(xué)習(xí)將本專業(yè)和計算機的應(yīng)用聯(lián)系起來。在學(xué)習(xí) 中應(yīng)該掌握尺度，并非每一門課都做到中應(yīng)該掌握尺度，并非每一門課都做到“完完 全透徹全透徹”。但也不能什么都一知半解，要有。但也不能什么都一知半解，要有 一個一個“拳頭拳頭”方向。方向。 n必要的準(zhǔn)備必要的準(zhǔn)備 熟悉應(yīng)用開發(fā)平臺上的常用工具熟悉應(yīng)用開發(fā)平臺上的常用工具 至少掌握一種程序設(shè)計語言至少掌握一種程序設(shè)計語言 注重分析：分析問題、解決問題注重分析：分析問題、解決問題 課程內(nèi)容課程內(nèi)容 1.算法 2.數(shù)據(jù)結(jié)構(gòu) 3.查找與排序技術(shù) 4.操作系統(tǒng) 5.數(shù)據(jù)庫技術(shù) 6.計算機網(wǎng)絡(luò) 7.軟件工程 課程特點

3、重點分散 難度集中 廣而不深 雜而不亂 學(xué)習(xí)方法 重視基礎(chǔ)原理 理解思維方式 實踐、實踐再實踐 善于自學(xué)，善于利 用電子資源 軟件改變了我們的生活 n工作 n生活 n娛樂 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件無所不在 軟件無所不在 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件無所不在 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件無所不在 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件無所不在 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)

4、基礎(chǔ) 軟件無所不在 軟件無處不在 n電力調(diào)度系統(tǒng) n火車調(diào)度系統(tǒng) n民航調(diào)度系統(tǒng) n天氣預(yù)報系統(tǒng) n地震預(yù)警系統(tǒng) n核試驗?zāi)M系統(tǒng) 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 看不見的軟件-嵌入式軟件 n戰(zhàn)斗機飛控系統(tǒng) n坦克火控系統(tǒng) n導(dǎo)彈彈上控制系統(tǒng) n工業(yè)控制系統(tǒng) n核反應(yīng)堆控制系統(tǒng) 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 什么是軟件 n軟件軟件（software）是一系列按照特定順是一系列按照特定順 序組織的計算機的數(shù)據(jù)和指令的集合。序組織的計算機的數(shù)據(jù)和指令的集合。 n軟件并不只是包括可以在計算機上運行軟件并不只是包括可以在計算機上運行 的程序，與這些電腦程序相關(guān)

5、的文檔，的程序，與這些電腦程序相關(guān)的文檔， 一般也被認(rèn)為是軟件的一部分。簡單的一般也被認(rèn)為是軟件的一部分。簡單的 說軟件就是程序加文檔的集合體。說軟件就是程序加文檔的集合體。 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 什么是軟件 n軟件軟件（software）是程序、數(shù)據(jù)及相關(guān)是程序、數(shù)據(jù)及相關(guān) 文檔的集合文檔的集合 程序程序：指示計算機完成指定任務(wù)的命令序列 數(shù)據(jù)數(shù)據(jù)：程序操作的對象，也是操作的結(jié)果 文檔文檔：軟件開發(fā)、維護與使用的相關(guān)圖文材 料,是對程序與數(shù)據(jù)的描述。 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件和硬件的關(guān)系 n硬件是基礎(chǔ)硬件是基礎(chǔ) n軟件是靈魂軟件是

6、靈魂 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件的分類 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 操作系統(tǒng) 數(shù)據(jù)庫技術(shù) 開發(fā)工具 計算機 軟件 系統(tǒng)軟件 中間件 用戶軟件 辦公軟件 專業(yè)軟件 娛樂 軟件的分類 n中間件 在操作系統(tǒng)、網(wǎng)絡(luò)和數(shù)據(jù)庫之上，應(yīng)用軟件的在操作系統(tǒng)、網(wǎng)絡(luò)和數(shù)據(jù)庫之上，應(yīng)用軟件的 下層，總的作用是為處于自己上層的應(yīng)用軟件下層，總的作用是為處于自己上層的應(yīng)用軟件 提供運行與開發(fā)的環(huán)境，幫助用戶靈活、高效提供運行與開發(fā)的環(huán)境，幫助用戶靈活、高效 地開發(fā)和集成復(fù)雜的應(yīng)用軟件。地開發(fā)和集成復(fù)雜的應(yīng)用軟件。 nidc表述：中間件是一種獨立的系統(tǒng)軟件或服表述：中

7、間件是一種獨立的系統(tǒng)軟件或服 務(wù)程序，分布式應(yīng)用軟件借助這種軟件在不同務(wù)程序，分布式應(yīng)用軟件借助這種軟件在不同 的技術(shù)之間共享資源，中間件位于客戶機服務(wù)的技術(shù)之間共享資源，中間件位于客戶機服務(wù) 器的操作系統(tǒng)之上，管理計算資源和網(wǎng)絡(luò)通信器的操作系統(tǒng)之上，管理計算資源和網(wǎng)絡(luò)通信。 軟件學(xué)科 n軟件理論軟件理論 算法理論算法理論 數(shù)據(jù)理論數(shù)據(jù)理論 n軟件系統(tǒng)軟件系統(tǒng) 操作系統(tǒng)操作系統(tǒng) 數(shù)據(jù)庫數(shù)據(jù)庫 開發(fā)工具（編譯原理）開發(fā)工具（編譯原理） n軟件開發(fā)軟件開發(fā) 軟件工程軟件工程 軟件 n軟件是程序+說明信息 （從內(nèi)容上說） n軟件是具有使用性能的程序 （從性能上說） n軟件是商品 （從本質(zhì)上說）。 與

8、其他商品比較，研制開發(fā)是主要的生產(chǎn)方式。 （軟件工程） n軟件只有過時而無“損耗”的商品。注重軟件 的柔性或有機性。 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件開發(fā)項目結(jié)構(gòu)組成 項 目 總 監(jiān) 質(zhì) 量 控 制 經(jīng) 理 航 空 公 司 專 家 系 統(tǒng) 總 工 程 師 項 目 總 體 組 機 務(wù) 業(yè) 務(wù) 專 家 系 統(tǒng) 工 程 專 家 系 統(tǒng) 需 求 組 數(shù) 據(jù) 庫 分 析 人 員 軟 件 分 析 人 員 程 序 員 文 檔 管 理 人 員 系 統(tǒng) 開 發(fā) 組 測 試 經(jīng) 理 測 試 人 員 用 戶 業(yè) 務(wù) 代 表 培 訓(xùn) 經(jīng) 理 培 訓(xùn) 人 員 測 試 培 訓(xùn) 組 項 目 實 施

9、規(guī) 劃 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 軟件開發(fā)文檔 l 系統(tǒng)建設(shè)可行性研究報告 l 系統(tǒng)現(xiàn)狀調(diào)研報告 l 項目開發(fā)計劃 l 系統(tǒng)及軟件需求說明書； l 數(shù)據(jù)要求說明書 l 概要設(shè)計說明書 l 詳細(xì)設(shè)計說明書 l 數(shù)據(jù)庫設(shè)計說明書 l 用戶操作手冊 l 測試計劃； l 測試分析報告； l 模塊開發(fā)卷宗； l 開發(fā)進度月報 l 項目開發(fā)總結(jié)報告 軟件開發(fā)和程序設(shè)計(編程) n軟件開發(fā)軟件開發(fā): 根據(jù)用戶要求建造出軟件系統(tǒng)或者根據(jù)用戶要求建造出軟件系統(tǒng)或者 系統(tǒng)中軟件部分的一個產(chǎn)品開發(fā)的過程。軟件系統(tǒng)中軟件部分的一個產(chǎn)品開發(fā)的過程。軟件 開發(fā)是一項包括需求獲取、開發(fā)規(guī)劃、需求分

10、開發(fā)是一項包括需求獲取、開發(fā)規(guī)劃、需求分 析和設(shè)計、編程實現(xiàn)、軟件測試、版本控制的析和設(shè)計、編程實現(xiàn)、軟件測試、版本控制的 系統(tǒng)工程。系統(tǒng)工程。 n程序設(shè)計程序設(shè)計，是指編寫和維護源代碼的過程。是，是指編寫和維護源代碼的過程。是 軟件開發(fā)過程的一小部分，有時也用來指狹義軟件開發(fā)過程的一小部分，有時也用來指狹義 的軟件開發(fā)。的軟件開發(fā)。 n軟件一般是通過某種或數(shù)種程序設(shè)計語言、在軟件一般是通過某種或數(shù)種程序設(shè)計語言、在 特定的計算機平臺上實現(xiàn)的。通常采用軟件開特定的計算機平臺上實現(xiàn)的。通常采用軟件開 發(fā)工具進行開發(fā)發(fā)工具進行開發(fā)。 合格軟件開發(fā)人員的素養(yǎng) n團隊精神和協(xié)作能力團隊精神和協(xié)作能力

11、n文檔習(xí)慣文檔習(xí)慣 n規(guī)范化，標(biāo)準(zhǔn)化的代碼編寫習(xí)慣規(guī)范化，標(biāo)準(zhǔn)化的代碼編寫習(xí)慣 n需求理解能力需求理解能力 n復(fù)用性，模塊化思維能力復(fù)用性，模塊化思維能力 n測試習(xí)慣測試習(xí)慣 n學(xué)習(xí)和總結(jié)的能力學(xué)習(xí)和總結(jié)的能力 軟件設(shè)計的一些問題 n這么多的程序設(shè)計語言，我究竟該選哪這么多的程序設(shè)計語言，我究竟該選哪 一種？一種？ n是不是懂得的計算機語言越多，就表示是不是懂得的計算機語言越多，就表示 計算機水平越高？計算機水平越高？ n怎樣才能學(xué)好軟件設(shè)計？怎樣才能學(xué)好軟件設(shè)計？ 開發(fā)語言的選擇 c 語言編寫的語言編寫的 hello, world 程序程序 void main() printf(“hello

12、, world !n”); pascal 語言編寫的語言編寫的 hello, world 程序程序 program main; begin writeln(hello, world!); end 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 根據(jù)具體的應(yīng)用選擇程序設(shè)計語言，沒有必要反根據(jù)具體的應(yīng)用選擇程序設(shè)計語言，沒有必要反 復(fù)爭論哪種語言好（如復(fù)爭論哪種語言好（如 vc+ 與與 delphi 之爭之爭,注意注意 開發(fā)工具和語言本身的區(qū)別）開發(fā)工具和語言本身的區(qū)別） （1）通訊軟件（實時系統(tǒng)、嵌入式系統(tǒng)）：匯編、c、java （2）數(shù)據(jù)庫管理軟件：delphi、vb （3）計算機游戲：v

13、c+（網(wǎng)絡(luò)游戲）、java（手機游戲） （4）web 設(shè)計：asp、jsp、php + mysql、python （5）特定平臺：.net c# （6）科學(xué)仿真：matlab （7）數(shù)值計算：fortran （8）特征領(lǐng)域：人工智能（lisp） 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 熟悉基本的程序設(shè)計原理和相關(guān)知識（如數(shù)據(jù)結(jié)熟悉基本的程序設(shè)計原理和相關(guān)知識（如數(shù)據(jù)結(jié) 構(gòu)），精通最常用構(gòu)），精通最常用 1 2 門語言（如門語言（如c+，java 等）等） 程序設(shè)計語言是相通的，程序設(shè)計語言是相通的，高手使用任何語言都高手使用任何語言都 能夠設(shè)計出高質(zhì)量的程序。關(guān)鍵不在于語言本能夠設(shè)

14、計出高質(zhì)量的程序。關(guān)鍵不在于語言本 身，而在于程序設(shè)計理念與方法，以及大量的身，而在于程序設(shè)計理念與方法，以及大量的 項目經(jīng)驗。項目經(jīng)驗。 是否要掌握多種語言 怎樣提高軟件設(shè)計水平 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n熟悉應(yīng)用開發(fā)平臺上的常用工具。熟悉應(yīng)用開發(fā)平臺上的常用工具。 n至少掌握一種程序設(shè)計語言。請注意，程序語言只是至少掌握一種程序設(shè)計語言。請注意，程序語言只是 表達工具，重要的是學(xué)會分析問題和解決問題的方法表達工具，重要的是學(xué)會分析問題和解決問題的方法 ，不要以為學(xué)會，不要以為學(xué)會c+就會用就會用oo范型編制范型編制oo軟件了。軟件了。 n注重分析：從某種意義上來

15、講，軟件開發(fā)其實就是用注重分析：從某種意義上來講，軟件開發(fā)其實就是用 程序語言來描述解決問題的方法和步驟。所以分析用程序語言來描述解決問題的方法和步驟。所以分析用 戶的需求得到需要解決的問題，分析問題得到解決的戶的需求得到需要解決的問題，分析問題得到解決的 方法步驟。分析是軟件開發(fā)中最基本的一環(huán)。方法步驟。分析是軟件開發(fā)中最基本的一環(huán)。 n寫文檔，軟件開發(fā)其實是一個問題驅(qū)動的基于文檔的寫文檔，軟件開發(fā)其實是一個問題驅(qū)動的基于文檔的 開發(fā)過程。應(yīng)把寫文檔看作是應(yīng)用開發(fā)的主要工作，開發(fā)過程。應(yīng)把寫文檔看作是應(yīng)用開發(fā)的主要工作， 這是最容易被忽視的工作也是現(xiàn)代軟件工程最為強調(diào)這是最容易被忽視的工作也

16、是現(xiàn)代軟件工程最為強調(diào) 的一點。的一點。 怎樣提高軟件設(shè)計水平 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n從來沒有那個高手是培訓(xùn)成功的。成為軟件開發(fā)高從來沒有那個高手是培訓(xùn)成功的。成為軟件開發(fā)高 手的路只有一條：自學(xué)！軟件開發(fā)中需要大量的編手的路只有一條：自學(xué)！軟件開發(fā)中需要大量的編 程實踐和獨立思考，只有在此過程中，你才能夠逐程實踐和獨立思考，只有在此過程中，你才能夠逐 步成長起來。學(xué)院里面能夠培養(yǎng)出軟件開發(fā)經(jīng)理更步成長起來。學(xué)院里面能夠培養(yǎng)出軟件開發(fā)經(jīng)理更 是十足的謊言，軟件項目經(jīng)理更強調(diào)從實際中學(xué)習(xí)是十足的謊言，軟件項目經(jīng)理更強調(diào)從實際中學(xué)習(xí) 軟件。軟件。 第一章第一章 計算

17、機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2012-8 編程語言排名top20 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) long term trends gnu/linux windows 能干而 linux 干不了的事情，那 就是不需要干的事情。 ngnu是“gnus not unix”的遞歸縮寫 自由自在 永遠(yuǎn)免費 資源眾多 沒有病毒 unix nunix元年 1970 n兩個人 ken thompson dennis ritchie nunix is basically a simple operating system, but you have to be a genius to

18、 understand the simplicity.- dennis ritchie n兩大陣營 at&t的unix uc berkeley的bsd 對抗霸權(quán)的gun n“革奴計劃”的精神領(lǐng)袖richard stallman gnu 工程 開始於一九八四年，旨在發(fā)展 一個類似 unix ，且為自由軟件的完整操 作系統(tǒng)： gnu 系統(tǒng)。 n兩種思潮 “大教堂”：集權(quán)、封閉、受控、保密 “集市”：分權(quán)、公開、精細(xì)的同僚復(fù) 審 nopen source 距開源越近就越繁榮。任何將unix專有 化的企圖，只能陷入停滯和衰敗。 ngnu general public license (gpl) n到了

19、1990年，gnu計劃已經(jīng)開發(fā)出的軟 件包括了一個功能強大的文字編輯器 emacs、c語言編譯器gcc以及大部分 unix系統(tǒng)的程序庫和工具。 n唯一依然沒有完成的重要組件，就是操 作系統(tǒng)的內(nèi)核 網(wǎng)絡(luò)時代的英雄linux n比爾蓋茨的頭號對手linus torvalds n1990年，芬蘭赫爾辛基大學(xué)的一名學(xué)生linus torvalds發(fā)布了與unix兼容的linux內(nèi)核 n“hello,this is linus torvalds and i pronounce linux as linux” top 5 distributions 5 4 3 2 全人類的linux： ubuntu nm

20、ark shuttleworth 1969年，生于南非小鎮(zhèn)。大學(xué)畢業(yè)后創(chuàng)辦了以及信息安 全公司，1999年以5.75億美元的價格賣出。在30歲時成 為南非最年輕有為的本土富翁。 2002年他自費3百萬英鎊乘坐俄羅斯聯(lián)盟號飛船，在國 際空間站中度過了8天的時光。當(dāng)時他不知道他是否能 回到遙遠(yuǎn)而又真實的地球。所以他決定如果能順利回到 地球，一定為人類做一件有意義的事。 結(jié)束太空之行之后，mark shuttleworth創(chuàng)立了ubuntu社 區(qū)。 nubuntu發(fā)行版光盤，免費索取 發(fā)展簡介 1.4.10 . warty warthhog. (長疣的疣豬) 2004-10 2.5.04 . hoa

21、ry hedgehog. (灰白的刺猬) 2005-04 3.5.10 breezy badger. (愉快的獾) 2005-10 4.6.06 dapper drake. (lts)(漂亮的鴨子)2006-6 5.6.10 edgy eft. (躁動的蜥蜴)2006-10 6.7.04 feisty fawn. (活潑的小花鹿) 2007-4 7.7.10 . gutsy gibbon.(勇敢的長臂猿) 2007-10 8.8.04 . hardy heron. (lts)(強壯的蒼鷺) 2008-4 9.8.10. intrepid ibex (無畏的山羊) 2008-10 10.9.04

22、. jaunty jackalope (活潑的兔子 )2009-4 11.9.10. karmic koala (命運的考拉 )2009-10 12.10.04 lucid lynx (lts)(清醒的猞猁 )2010-4 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1算法算法 所謂算法是指解題方案的準(zhǔn)確而完整的描述。所謂算法是指解題方案的準(zhǔn)確而完整的描述。 2算法的基本特征算法的基本特征 （1）可行性）可行性 （2）確定性）確定性 （3）有窮性）有窮性 （4）擁有足夠的情報）擁有足夠的情報 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 計算機軟件技術(shù)基

23、礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 3算法的基本要素算法的基本要素 一個算法通常由兩種基本要素組成：一是對數(shù)據(jù)一個算法通常由兩種基本要素組成：一是對數(shù)據(jù) 對象的運算和操作，二是算法的控制結(jié)構(gòu)。對象的運算和操作，二是算法的控制結(jié)構(gòu)。 （1）算法中對數(shù)據(jù)的運算和操作）算法中對數(shù)據(jù)的運算和操作 基本的運算和操作有以下四類：基本的運算和操作有以下四類： 算術(shù)運算：主要包括加、減、乘、除等運算。算術(shù)運算：主要包括加、減、乘、除等運算。 邏輯運算：主要包括邏輯運算：主要包括“與與”、“或或”、“非非” 等運算。等運算。 關(guān)系運算：主要包括關(guān)系運算：主要包括“大于大于”、“小于小于”、 “等于等于”、“不等于不等于”等運

24、算：等運算： 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) （2）算法的控制結(jié)構(gòu)）算法的控制結(jié)構(gòu) 算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅 決定了算法中各操作的執(zhí)行順序，而且也直接決定了算法中各操作的執(zhí)行順序，而且也直接 反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述 算法的工具通常有傳統(tǒng)流程圖、算法的工具通常有傳統(tǒng)流程圖、n-s結(jié)構(gòu)化流程結(jié)構(gòu)化流程 圖、算法描述

25、語言等。一個算法一般都可以用圖、算法描述語言等。一個算法一般都可以用 順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。順序、選擇、循環(huán)三種基本控制結(jié)構(gòu)組合而成。 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 4算法設(shè)計基本方法算法設(shè)計基本方法 （1 1）列舉法）列舉法 根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定根據(jù)提出的問題，列舉所有可能的情況，并用問題中給定 的條件檢驗?zāi)男┦切枰模男┦遣恍枰摹５臈l件檢驗?zāi)男┦切枰?，哪些是不需要的?（2 2）歸納法）歸納法 通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān)通過列

26、舉少量的特殊情況，經(jīng)過分析，最后找出一般的關(guān) 系。系。 （3 3）遞推）遞推 所謂遞推，是指從已知的初始條件出發(fā)，逐次推出所要求所謂遞推，是指從已知的初始條件出發(fā)，逐次推出所要求 的各中間結(jié)果和最后結(jié)果。其中初始條件或是問題本身的各中間結(jié)果和最后結(jié)果。其中初始條件或是問題本身 已經(jīng)給定，或是通過對問題的分析與化簡而確定。已經(jīng)給定，或是通過對問題的分析與化簡而確定。 （4 4）遞歸）遞歸 （5 5）減半遞推技術(shù)）減半遞推技術(shù) 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) q對算法的分析主要是對算法的時間復(fù)雜度和空對算法的分析主

27、要是對算法的時間復(fù)雜度和空 間復(fù)雜度的分析。間復(fù)雜度的分析。 q1時間復(fù)雜度時間復(fù)雜度 一個算法的時間復(fù)雜度是該算法的時間耗費，一個算法的時間復(fù)雜度是該算法的時間耗費， 即算法執(zhí)行過程中所需要的基本運算次數(shù)。即算法執(zhí)行過程中所需要的基本運算次數(shù)。 一個算法所耗費的時間一個算法所耗費的時間=算法中每條語句的執(zhí)行算法中每條語句的執(zhí)行 時間之和。每條語句的執(zhí)行時間時間之和。每條語句的執(zhí)行時間=語句的執(zhí)行次語句的執(zhí)行次 數(shù)數(shù)語句執(zhí)行一次所需時間。語句執(zhí)行一次所需時間。 q2空間復(fù)雜度空間復(fù)雜度 一個算法的空間復(fù)雜度為該算法在執(zhí)行過程中一個算法的空間復(fù)雜度為該算法在執(zhí)行過程中 所需要的存儲空間。所需要的

28、存儲空間。 算法的時間復(fù)雜度和空間復(fù)雜度合稱為算法的算法的時間復(fù)雜度和空間復(fù)雜度合稱為算法的 復(fù)雜度。復(fù)雜度。 1.3 1.3 算法及算法分析算法及算法分析 二、算法分析二、算法分析 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1線性表的邏輯定義線性表的邏輯定義 線性表（線性表（linear list）是由）是由n（n0）個數(shù)據(jù)元素（結(jié)點）個數(shù)據(jù)元素（結(jié)點） a1，a2，an組成的有限序列。組成的有限序列。 數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)n定義為表的長度（定義為表的長度（n=0時稱為空表）。時稱為空表）。 將非空的線性表（將非空的線性表（n0）記作：（）記作：（a1，a2，an） 數(shù)據(jù)元

29、素數(shù)據(jù)元素ai（1 i n）只是個抽象符號，其具體含義在）只是個抽象符號，其具體含義在 不同情況下可以不同。不同情況下可以不同。 如學(xué)生成績表中，每個學(xué)生及其成績是一個數(shù)據(jù)元素，如學(xué)生成績表中，每個學(xué)生及其成績是一個數(shù)據(jù)元素， 其中數(shù)據(jù)元素由學(xué)號、姓名、各科成績等數(shù)據(jù)項組成。其中數(shù)據(jù)元素由學(xué)號、姓名、各科成績等數(shù)據(jù)項組成。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 一、線性表一、線性表 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2線性表的邏輯結(jié)構(gòu)特征線性表的邏輯結(jié)構(gòu)特征 對于非空的線性表對于非空的線性表: 有且僅有一個開始結(jié)點有且僅有一個開始結(jié)點a1，沒有直接前趨，有，沒有直

30、接前趨，有 且僅有一個直接后繼且僅有一個直接后繼a2； 有且僅有一個終結(jié)結(jié)點有且僅有一個終結(jié)結(jié)點an，沒有直接后繼，有，沒有直接后繼，有 且僅有一個直接前趨且僅有一個直接前趨an-1； 其余的內(nèi)部結(jié)點其余的內(nèi)部結(jié)點ai（2in1）都有且僅有一）都有且僅有一 個直接前趨個直接前趨ai-1和一個直接后繼和一個直接后繼ai1。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 一、線性表一、線性表 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 3線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu) 有順序存儲和鏈?zhǔn)酱鎯煞N有順序存儲和鏈?zhǔn)酱鎯煞N 順序存儲方法即把線性表的結(jié)點按邏輯次序依順序存儲方法即把線

31、性表的結(jié)點按邏輯次序依 次存放在一組地址連續(xù)的存儲單元里的方法。次存放在一組地址連續(xù)的存儲單元里的方法。 用順序存儲方法存儲的線性表簡稱為順序表。用順序存儲方法存儲的線性表簡稱為順序表。 在順序表中，每個結(jié)點在順序表中，每個結(jié)點ai的存儲地址是該結(jié)點的存儲地址是該結(jié)點 在表中的位置在表中的位置i的線性函數(shù)。只要知道基地址和的線性函數(shù)。只要知道基地址和 每個結(jié)點的大小，就可在相同時間內(nèi)求出任一每個結(jié)點的大小，就可在相同時間內(nèi)求出任一 結(jié)點的存儲地址。結(jié)點的存儲地址。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 一、線性表一、線性表 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 4常見

32、的線性表的基本運算常見的線性表的基本運算 （1）initlist(l)：構(gòu)造一個空的線性表：構(gòu)造一個空的線性表l，即表的，即表的 初始化。初始化。 （2）listlength(l)：求線性表：求線性表l中的結(jié)點個數(shù)，中的結(jié)點個數(shù)， 即求表長。即求表長。 （3）getnode(l,i) ：取線性表：取線性表l中的第中的第i個結(jié)點，個結(jié)點， 這里要求這里要求1 i listlength(l)。 （4）locatenode(l,x)：在：在l中查找值為中查找值為x 的結(jié)點，的結(jié)點， 并返回該結(jié)點在并返回該結(jié)點在l中的位置。若中的位置。若l中有多個結(jié)點中有多個結(jié)點 的值和的值和x 相同，則返回首次找到

33、的結(jié)點位置；若相同，則返回首次找到的結(jié)點位置；若 l中沒有結(jié)點的值為中沒有結(jié)點的值為x，則返回一個特殊值表示，則返回一個特殊值表示 查找失敗。查找失敗。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 一、線性表一、線性表 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) （5）insertlist(l,x,i)：在線性表：在線性表l的第的第i個位置上個位置上 插入一個值為插入一個值為x 的新結(jié)點，使得原編號為的新結(jié)點，使得原編號為i，i 1，n的結(jié)點變?yōu)榫幪枮榈慕Y(jié)點變?yōu)榫幪枮閕1，i2，n 1的結(jié)點。這里的結(jié)點。這里1 i n1，而，而n是原表是原表l的長的長 度。插入后，表度。插入后，

34、表l的長度加的長度加1。 （6）deletelist(l,i)：刪除線性表：刪除線性表l的第的第i個結(jié)點，個結(jié)點， 使得原編號為使得原編號為i1，i2，n的結(jié)點變成編的結(jié)點變成編 號為號為i，i1，n1的結(jié)點。這里的結(jié)點。這里1 i n， 而而n是原表是原表l的長度。刪除后表的長度。刪除后表l的長度減的長度減1。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 一、線性表一、線性表 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1棧的定義棧的定義 棧（棧（stack）是限制僅在表的一端進行插入和）是限制僅在表的一端進行插入和 刪除運算的線性表。棧的示意圖如圖刪除運算的線性表。棧的示意圖

35、如圖1-4所示：所示： （1）通常稱插入、刪除的這一端為棧頂，另一端）通常稱插入、刪除的這一端為棧頂，另一端 稱為棧底。稱為棧底。 （2）當(dāng)表中沒有元素時稱為空棧。）當(dāng)表中沒有元素時稱為空棧。 （3）棧為后進先出（）棧為后進先出（last in first out）的線性表，）的線性表， 簡稱為簡稱為lifo表。表。 棧的修改是按后進先出的原則進行。棧的修改是按后進先出的原則進行。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 二、棧二、棧 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2棧的基本運算棧的基本運算 （1）initstack(s)：構(gòu)造一個空棧：構(gòu)造一個空棧s。 （2）

36、stackempty(s)：判?？?。若：判?？铡Ｈ魋為空棧，則返回為空棧，則返回true， 否則返回否則返回false。 （3）stackfull(s)：判棧滿。若：判棧滿。若s為滿棧，則返回為滿棧，則返回true， 否則返回否則返回false。注意：該運算只適用于棧的順序存儲。注意：該運算只適用于棧的順序存儲 結(jié)構(gòu)。結(jié)構(gòu)。 （4）push(s,x)：進棧。若棧：進棧。若棧s不滿，則將元素不滿，則將元素x插入插入s的棧的棧 頂。頂。 （5）pop(s)：退棧。若棧：退棧。若棧s非空，則將非空，則將s的棧頂元素刪去，的棧頂元素刪去， 并返回該元素。并返回該元素。 （6）stacktop(s)：取

37、棧頂元素。若棧：取棧頂元素。若棧s非空，則返回棧頂非空，則返回棧頂 元素，但不改變棧的狀態(tài)。元素，但不改變棧的狀態(tài)。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 二、棧二、棧 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1定義定義 只允許在一端進行插入，而在另一端進行刪只允許在一端進行插入，而在另一端進行刪 除的運算受限的線性表。除的運算受限的線性表。 （1）允許刪除的一端稱為隊頭（）允許刪除的一端稱為隊頭（front）。）。 （2）允許插入的一端稱為隊尾（）允許插入的一端稱為隊尾（rear）。）。 （3）當(dāng)隊列中沒有元素時稱為空隊列。）當(dāng)隊列中沒有元素時稱為空隊列。 （4）隊列

38、亦稱作先進先出（）隊列亦稱作先進先出（first in first out） 的線性表，簡稱為的線性表，簡稱為fifo表。表。 隊列的修改是依先進先出的原則進行的。隊列的修改是依先進先出的原則進行的。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 三、隊列三、隊列 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2隊列的基本邏輯運算隊列的基本邏輯運算 （1）initqueue(q)：置空隊。構(gòu)造一個空隊列：置空隊。構(gòu)造一個空隊列q。 （2）queueempty(q)：判隊空。若隊列：判隊空。若隊列q為空，則返回為空，則返回 真值，否則返回假值。真值，否則返回假值。 （3）queuefu

39、ll(q)：判隊滿。若隊列：判隊滿。若隊列q為滿，則返回真值，為滿，則返回真值， 否則返回假值。否則返回假值。 注意：注意：此操作只適用于隊列的順序存儲結(jié)構(gòu)。此操作只適用于隊列的順序存儲結(jié)構(gòu)。 （4）enqueue(q,x)：若隊列：若隊列q非滿，則將元素非滿，則將元素x插入插入q的的 隊尾。此操作簡稱入隊。隊尾。此操作簡稱入隊。 （5）dequeue(q)：若隊列：若隊列q非空，則刪去非空，則刪去q的隊頭元素，的隊頭元素， 并返回該元素。此操作簡稱出隊。并返回該元素。此操作簡稱出隊。 （6）queuefront(q)：若隊列：若隊列q非空，則返回隊頭元素，非空，則返回隊頭元素， 但不改變隊列

40、但不改變隊列q的狀態(tài)。的狀態(tài)。 1.4 1.4 線性表、棧和隊列線性表、棧和隊列 三、隊列三、隊列 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 以鏈接方式存儲的線性表簡稱為鏈表。以鏈接方式存儲的線性表簡稱為鏈表。 1鏈表的具體存儲表示為：鏈表的具體存儲表示為： 用一組任意的存儲單元來存放線性表的結(jié)點用一組任意的存儲單元來存放線性表的結(jié)點 （這組存儲單元既可以是連續(xù)的，也可以是不（這組存儲單元既可以是連續(xù)的，也可以是不 連續(xù)的）。連續(xù)的）。 鏈表中結(jié)點的邏輯次序和物理次序不一定相鏈表中結(jié)點的邏輯次序和物理次序不一定相 同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存同。為了能正確表示結(jié)點間的邏輯

41、關(guān)系，在存 儲每個結(jié)點值的同時，還必須存儲指示其后繼儲每個結(jié)點值的同時，還必須存儲指示其后繼 結(jié)點的地址（或位置）信息（稱為指針或鏈結(jié)點的地址（或位置）信息（稱為指針或鏈)。 1.5 1.5 線性鏈表線性鏈表 一、線性鏈表的概念一、線性鏈表的概念 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2鏈表的結(jié)點結(jié)構(gòu)鏈表的結(jié)點結(jié)構(gòu) 1.5 1.5 線性鏈表線性鏈表 一、線性鏈表的概念一、線性鏈表的概念 datanext data域域存放結(jié)點值的數(shù)據(jù)域。存放結(jié)點值的數(shù)據(jù)域。 next域域存放結(jié)點的直接后繼的地址的指針域。存放結(jié)點的直接后繼的地址的指針域。 其中：其中： 鏈表通過每個結(jié)點的鏈域?qū)⒕€性

42、表的鏈表通過每個結(jié)點的鏈域?qū)⒕€性表的n 個結(jié)點按其邏輯順序鏈接在一起的。個結(jié)點按其邏輯順序鏈接在一起的。 每個結(jié)點只有一個鏈域的鏈表稱為單鏈表。每個結(jié)點只有一個鏈域的鏈表稱為單鏈表。 每個結(jié)點有兩個鏈域的鏈表，既指出該數(shù)據(jù)元每個結(jié)點有兩個鏈域的鏈表，既指出該數(shù)據(jù)元 素的后繼素的后繼,指出前驅(qū)，則這種鏈表稱為雙鏈表。指出前驅(qū)，則這種鏈表稱為雙鏈表。 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 在單鏈表中增加一個表頭結(jié)點，指針域指向線在單鏈表中增加一個表頭結(jié)點，指針域指向線 形表的第一個元素的結(jié)點，令最后一個結(jié)點的形表的第一個元素的結(jié)點，令最后一個結(jié)點的 指針域指向表頭結(jié)點，即構(gòu)成了循環(huán)鏈

43、表，指針域指向表頭結(jié)點，即構(gòu)成了循環(huán)鏈表，在在 循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀 鏈。鏈。 1.5 1.5 線性鏈表線性鏈表 一、線性鏈表的概念一、線性鏈表的概念 a1aiai+1an 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n線性鏈表的基本運算主要有以下幾個：線性鏈表的基本運算主要有以下幾個： （1）在線性鏈表中包含指定元素的結(jié)點之前插入）在線性鏈表中包含指定元素的結(jié)點之前插入 一個新元素一個新元素 （2）在線性鏈表中刪除包含指定元素的結(jié)點）在線性鏈表中刪除包含指定元素的結(jié)點 （3）將兩個線性鏈表按要求合并成一個線性鏈表）將兩個線性

44、鏈表按要求合并成一個線性鏈表 （4）將一個線性鏈表按要求進行分解。）將一個線性鏈表按要求進行分解。 （5）逆轉(zhuǎn)線性鏈表）逆轉(zhuǎn)線性鏈表 （6）復(fù)制線性鏈表）復(fù)制線性鏈表 （7）線性鏈表的排序）線性鏈表的排序 （8）線性鏈表的查找）線性鏈表的查找 1.5 1.5 線性鏈表線性鏈表 二、二、線性鏈表的基本運算線性鏈表的基本運算 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1.插入運算插入運算 思想方法思想方法:插入運算是將值為插入運算是將值為x的新結(jié)點插入的新結(jié)點插入 到表的第到表的第i個結(jié)點的位置上，即插入到個結(jié)點的位置上，即插入到ai與與ai1 之間。之間。 具體步驟：具體步驟： （1）

45、找到）找到ai存儲位置存儲位置p； （2）生成一個數(shù)據(jù)域為）生成一個數(shù)據(jù)域為x的新結(jié)點的新結(jié)點ax； （3）令結(jié)點）令結(jié)點*p的指針域指向新結(jié)點；的指針域指向新結(jié)點； （4）新結(jié)點的指針域指向結(jié)點）新結(jié)點的指針域指向結(jié)點ai1。 1.5 1.5 線性鏈表線性鏈表 二、二、線性鏈表的基本運算線性鏈表的基本運算 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2.刪除運算刪除運算 思想方法思想方法:刪除運算是將表的第刪除運算是將表的第i個結(jié)點刪去。個結(jié)點刪去。 具體步驟：具體步驟： （1）找到）找到ai-1的存儲位置的存儲位置p（因為在單鏈表中結(jié)點（因為在單鏈表中結(jié)點 ai的存儲地址是在其直接

46、前趨結(jié)點的存儲地址是在其直接前趨結(jié)點ai-1的指針域的指針域 next中）；中）； （2）令）令pnext指向指向ai的直接后繼結(jié)點（即把的直接后繼結(jié)點（即把ai 從鏈上摘下）；從鏈上摘下）； （3）釋放結(jié)點）釋放結(jié)點ai的空間，將其歸還給的空間，將其歸還給“存儲池存儲池”。 1.5 1.5 線性鏈表線性鏈表 二、二、線性鏈表的基本運算線性鏈表的基本運算 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)樹形結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹形結(jié)構(gòu) 是結(jié)點之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。是結(jié)點之間有分支，并具有層次關(guān)系的結(jié)構(gòu)。 如家譜、行政組織機構(gòu)都可

47、用樹形象地表示。如家譜、行政組織機構(gòu)都可用樹形象地表示。 1.6 1.6 樹樹 一、什么是樹一、什么是樹 經(jīng)濟管理學(xué)經(jīng)濟管理學(xué) 院院 經(jīng)濟信息系經(jīng)濟信息系計劃統(tǒng)計系計劃統(tǒng)計系外貿(mào)系外貿(mào)系 信息處理信息處理 教研室教研室 經(jīng)濟數(shù)學(xué)經(jīng)濟數(shù)學(xué) 教研室教研室 計劃學(xué)計劃學(xué) 教研室教研室 統(tǒng)計學(xué)統(tǒng)計學(xué) 教研室教研室 外語外語 教研室教研室 國際貿(mào)易國際貿(mào)易 教研室教研室 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2樹結(jié)構(gòu)的基本術(shù)語樹結(jié)構(gòu)的基本術(shù)語 在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為在樹結(jié)構(gòu)中，每一個結(jié)點只有一個前件，稱為 父結(jié)點。父結(jié)點。 沒有前件的結(jié)點只有一個，稱為樹的根結(jié)點。沒有前件

48、的結(jié)點只有一個，稱為樹的根結(jié)點。 每一個結(jié)點可以有多個后件，都稱為該結(jié)點的每一個結(jié)點可以有多個后件，都稱為該結(jié)點的 子結(jié)點。子結(jié)點。 沒有后件的結(jié)點稱為葉子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。 一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。 一棵樹的度是指該樹中結(jié)點的最大度數(shù)。一棵樹的度是指該樹中結(jié)點的最大度數(shù)。 1.6 1.6 樹樹 一、什么是樹一、什么是樹 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 結(jié)點的層數(shù)結(jié)點的層數(shù)(level)：從根起算，根的層數(shù)為：從根起算，根的層數(shù)為1， 其余結(jié)點的層數(shù)等于其雙親結(jié)點的層數(shù)加其余結(jié)點的層數(shù)等于其雙親結(jié)點的層

49、數(shù)加1。 樹中結(jié)點的最大層數(shù)稱為樹的高度樹中結(jié)點的最大層數(shù)稱為樹的高度(height)或深或深 度度(depth)。 a c b hdf ij ge 1.6 1.6 樹樹 一、什么是樹一、什么是樹 圖中，樹的根結(jié)點圖中，樹的根結(jié)點a度為度為2， 結(jié)點結(jié)點b的度為的度為3，結(jié)點，結(jié)點i的度為的度為 0，樹的度為，樹的度為3，結(jié)點，結(jié)點a在第一在第一 層，結(jié)點層，結(jié)點b，c在第二層，結(jié)在第二層，結(jié) 點點d,e,f,g,h在第三層在第三層,結(jié)點結(jié)點i,j 在第四層。在第四層。 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n森林森林(forest)是是m(m0)棵互不相交的樹的棵互不相交的樹的

50、 集合。集合。 n樹和森林的概念相近。刪去一棵樹的根，樹和森林的概念相近。刪去一棵樹的根， 就得到一個森林；反之，加上一個結(jié)點就得到一個森林；反之，加上一個結(jié)點 作樹根，森林就變?yōu)橐豢脴?。作樹根，森林就變?yōu)橐豢脴洹?1.6 1.6 樹樹 一、什么是樹一、什么是樹 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1.二叉樹的特點二叉樹的特點 （1）非空二叉樹只有一個根結(jié)點。）非空二叉樹只有一個根結(jié)點。 （2）每一個結(jié)點最多有兩棵子樹，稱為該結(jié)點的）每一個結(jié)點最多有兩棵子樹，稱為該結(jié)點的 左子樹和右子樹。左子樹和右子樹。 如算術(shù)運算式如算術(shù)運算式3 * 5 6 / 2 8就可用二叉樹表就可用二

51、叉樹表 示。示。 1.6 1.6 樹樹 二、二、二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) + * 8 35 62 / 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 2.二叉樹具有以下重要性質(zhì)：二叉樹具有以下重要性質(zhì)： 性質(zhì)性質(zhì)1 二叉樹第二叉樹第i層上的結(jié)點數(shù)目最多為層上的結(jié)點數(shù)目最多為2i1(i1)。 性質(zhì)性質(zhì)2 深度為深度為k的二叉樹至多有的二叉樹至多有2k1個結(jié)點個結(jié)點(k1)。 性質(zhì)性質(zhì)3 在任意一棵二叉樹中，若終端結(jié)點的個數(shù)在任意一棵二叉樹中，若終端結(jié)點的個數(shù) 為為n0，度為，度為2的結(jié)點數(shù)為的結(jié)點數(shù)為n2，則，則no=n21。 性質(zhì)性質(zhì)4 具有具有n個結(jié)點的完全二叉樹的深度為：個結(jié)點

52、的完全二叉樹的深度為： （或（或 ）。）。 1lgn 1.6 1.6 樹樹 二、二、二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 1lgn 1lgn ) 1lg(n 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 3.滿二叉樹和完全二叉樹是二叉樹滿二叉樹和完全二叉樹是二叉樹 （1）滿二叉樹）滿二叉樹(fullbinarytree) 一棵深度為一棵深度為k且有且有2k1個結(jié)點的二叉樹稱為滿二個結(jié)點的二叉樹稱為滿二 叉樹。叉樹。 滿二叉樹的特點：滿二叉樹的特點： 每一層上的結(jié)點數(shù)都達到最大值。即對給定的每一層上的結(jié)點數(shù)都達到最大值。即對給定的 高度，它是具有最多結(jié)點數(shù)的二叉樹。高度，它是具有最多結(jié)點數(shù)的二

53、叉樹。 滿二叉樹中不存在度數(shù)為滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)的結(jié)點，每個分支結(jié) 點均有兩棵高度相同的子樹，且樹葉都在最下點均有兩棵高度相同的子樹，且樹葉都在最下 一層上。一層上。 1.6 1.6 樹樹 二、二、二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) （2）完全二叉樹）完全二叉樹(complete binarytree) 若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可若一棵二叉樹至多只有最下面的兩層上結(jié)點的度數(shù)可 以小于以小于2，并且最下一層上的結(jié)點都集中在該層最左邊，并且最下一層上的結(jié)點都集中在該層最左邊 的若干位置上，則此二叉樹稱為完

54、全二叉樹。的若干位置上，則此二叉樹稱為完全二叉樹。 完全二叉樹的特點：完全二叉樹的特點： 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。 在滿二叉樹的最下一層，從最右邊開始連續(xù)刪去若干結(jié)在滿二叉樹的最下一層，從最右邊開始連續(xù)刪去若干結(jié) 點后得到的二叉樹仍然是一棵完全二叉樹。點后得到的二叉樹仍然是一棵完全二叉樹。 在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒 有右孩子，即該結(jié)點必是葉結(jié)點。有右孩子，即該結(jié)點必是葉結(jié)點。 1.6 1.6 樹樹 二、二、二叉樹的基本性質(zhì)二叉樹的基本性質(zhì) 第一章第

55、一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n鏈接的方法是它最自然的存儲表示方法。鏈接的方法是它最自然的存儲表示方法。 n每個結(jié)點有一個數(shù)據(jù)域，兩個指針域。數(shù)據(jù)域每個結(jié)點有一個數(shù)據(jù)域，兩個指針域。數(shù)據(jù)域 存儲數(shù)據(jù)元素的值，兩個指針分別指向該數(shù)據(jù)存儲數(shù)據(jù)元素的值，兩個指針分別指向該數(shù)據(jù) 元素的左子女和右子女。當(dāng)某個子女不存在時，元素的左子女和右子女。當(dāng)某個子女不存在時， 相應(yīng)的指針為空指針。結(jié)點形式如下：相應(yīng)的指針為空指針。結(jié)點形式如下： 1.6 1.6 樹樹 三、三、二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) llinkinforlink 一棵二叉樹的所有這樣形式的結(jié)點，再加上一個一棵二叉樹的所有這樣形

56、式的結(jié)點，再加上一個 指向根的指針，就構(gòu)成此二叉樹的存儲表示。這指向根的指針，就構(gòu)成此二叉樹的存儲表示。這 種存儲表示法稱為種存儲表示法稱為llink-rlink表示法或稱為二叉鏈表示法或稱為二叉鏈 表。表。 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n遍歷一棵二叉樹實際上是對二叉樹的結(jié)點進遍歷一棵二叉樹實際上是對二叉樹的結(jié)點進 行一次掃描，是將二叉樹的結(jié)點放入一個線性行一次掃描，是將二叉樹的結(jié)點放入一個線性 序列的過程，或者說把二叉樹進行線性化。遍序列的過程，或者說把二叉樹進行線性化。遍 歷運算是二叉樹的一種最基本的運算。歷運算是二叉樹的一種最基本的運算。 遍歷二叉樹有三種主要的方

57、法：前序法、中遍歷二叉樹有三種主要的方法：前序法、中 序法和后序法。序法和后序法。 前序法，其操作如下：前序法，其操作如下： 訪問根；訪問根； 按前序遍歷左子樹；按前序遍歷左子樹； 按前序遍歷右子樹。按前序遍歷右子樹。 1.6 1.6 樹樹 四、四、二叉樹的運算二叉樹的運算 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 中序法，其操作如下：中序法，其操作如下： 按中序遍歷左子樹；按中序遍歷左子樹； 訪問根；訪問根； 按中序遍歷右子樹。按中序遍歷右子樹。 后序法，其操作如下：后序法，其操作如下： 按后序遍歷左子樹；按后序遍歷左子樹； 按后序遍歷右子樹；按后序遍歷右子樹； 訪問根。訪問根。

58、1.6 1.6 樹樹 四、四、二叉樹的運算二叉樹的運算 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) + * 8 35 6 2 / 1.6 1.6 樹樹 四、四、二叉樹的運算二叉樹的運算 對于圖中的二叉樹，它的對于圖中的二叉樹，它的 三種方法遍歷結(jié)果是：三種方法遍歷結(jié)果是： 前序序列：前序序列： * 3 5 6 2 8 中序序列：中序序列： 3 * 5 6 2 8 后序序列：后序序列： 3 5 * 6 2 8 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) n順序查找又稱順序搜索。順序查找一般是指在線性表中順序查找又稱順序搜索。順序查找一般是指在線性表中 查找指定的元素，其基本方法如

59、下：查找指定的元素，其基本方法如下： n從線性表的第一個元素開始，依次將線性表中的元素與從線性表的第一個元素開始，依次將線性表中的元素與 被查元素進行比較，若相等則表示找到（即查找成功被查元素進行比較，若相等則表示找到（即查找成功)； 若線性表中所有的元素都與被查元素進行了比較但都不若線性表中所有的元素都與被查元素進行了比較但都不 相等，則表示線性表中沒有要找的元素相等，則表示線性表中沒有要找的元素(即查找失敗即查找失敗)。 n在下列兩種情況下也只能采用順序查找：在下列兩種情況下也只能采用順序查找： (1)如果線性表為無序表如果線性表為無序表(即表中元素的排列是無序的即表中元素的排列是無序的)

60、，則，則 不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序 查找。查找。 (2)即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用 順序查找。順序查找。 1.7 1.7 查找技術(shù)查找技術(shù) 一、順序查找一、順序查找 第一章第一章 計算機軟件技術(shù)基礎(chǔ)計算機軟件技術(shù)基礎(chǔ) 1.7 1.7 查找技術(shù)查找技術(shù) 二、二分法查找二、二分法查找 n二分法查找只適用于順序存儲的有序表。二分法查找只適用于順序存儲的有序表。 設(shè)有序線性表的長度為設(shè)有序線性表的長度為n，被查元素為，被查元素為x，則對二，則對二 分查找的方法如