二級(jí)公共基礎(chǔ)知識(shí)_圖文

1、123456 7 8 9 10 通過(guò)工作原理了解，熟悉計(jì)算機(jī)內(nèi)部執(zhí)行功能的基本意義。為理解程序打下基礎(chǔ)，特別理解計(jì)算機(jī)是機(jī)器。v 指令的集合。（解釋指令）v 通過(guò)硬件控制系統(tǒng)自動(dòng)完成某一功能。v 通過(guò)一系列代碼實(shí)現(xiàn)。11v 計(jì)算機(jī)本身僅能識(shí)別二進(jìn)制代碼“0”、“1”。v 編程最直接、最低級(jí)的就是機(jī)器語(yǔ)言。v 為解決機(jī)器語(yǔ)言難理解、記憶等問(wèn)題。出現(xiàn)符號(hào)語(yǔ)言。v 為使編程接近自然語(yǔ)言，出現(xiàn)高級(jí)語(yǔ)言。如C、PASCAL、FORTRAN等。v 為配合高級(jí)語(yǔ)言編程，出現(xiàn)了開(kāi)發(fā)工具，提高效率、減輕勞動(dòng)量。如VB、VC、PB、Delphi、VFP等。因此VFP不是編程語(yǔ)言。12v 不管什么形式編寫(xiě)代碼，最終

2、都應(yīng)將代碼翻譯成機(jī)器語(yǔ)言， 這就是編譯程序的工作。不同的語(yǔ)言有不同的編譯器。v 程序控制是一種邏輯控制。因此，嚴(yán)謹(jǐn)?shù)倪壿嬎季S是一個(gè) 程序員必備的基本素質(zhì)。v 用程序?qū)崿F(xiàn)某一功能。有許多方法。具體用哪種完全取決 于程序員個(gè)人的思維方式。因此，程序是腦力勞動(dòng)的結(jié)晶， 從某種意義上，編程又是一門(mén)藝術(shù)。v 程序的特殊性決定了程序的復(fù)雜性，且與實(shí)現(xiàn)功能的復(fù)雜 性密切相關(guān)成正比。因此為使復(fù)雜的、智力的編程工作規(guī) 范化、科學(xué)化，便出現(xiàn)了各種編程設(shè)計(jì)方法。如結(jié)構(gòu)化編 程方法、面向?qū)ο蟮某绦蛟O(shè)計(jì)方法等。13v 不管用什么方法編程，不管編程者智力程度如何，不管 采用什么樣的編程語(yǔ)言和方法，程序最終完成的功能穩(wěn) 定

3、、可靠、實(shí)用、易維護(hù)和安全等是程序的最終目標(biāo)， 也是程序員的追求。v 程序設(shè)計(jì)是一個(gè)復(fù)雜艱巨的過(guò)程。編寫(xiě)代碼僅是程序設(shè) 計(jì)的一部分。必須先有思想，再有方法，然后才是編寫(xiě) 代碼，且要經(jīng)過(guò)許多反復(fù)，不可急功近利。14v 程序設(shè)計(jì)語(yǔ)言指的是用來(lái)編寫(xiě)程序的語(yǔ)言。v 人與計(jì)算機(jī)交流要使用語(yǔ)言，以便讓計(jì)算機(jī)工作，計(jì)算 機(jī)也通過(guò)語(yǔ)言把結(jié)果告訴用計(jì)算機(jī)的人“人機(jī)對(duì) 話”。v 人與計(jì)算機(jī)交流的語(yǔ)言非平常人與人之間交流的語(yǔ)言， 是專門(mén)的語(yǔ)言程序設(shè)計(jì)語(yǔ)言。v 程序設(shè)計(jì)語(yǔ)言是計(jì)算機(jī)系統(tǒng)軟件的重要組成部分。15v 執(zhí)行程序設(shè)計(jì)的語(yǔ)言有很多，可分高級(jí)語(yǔ)言和低級(jí)語(yǔ)言， 區(qū)別在于接近自然語(yǔ)言的程度v 高級(jí)語(yǔ)言一般與具體的計(jì)算

4、機(jī)硬件無(wú)關(guān)，比較接近人類 自然語(yǔ)言的語(yǔ)法習(xí)慣及數(shù)學(xué)表達(dá)形式。v 用高級(jí)語(yǔ)言編寫(xiě)的源程序不能被機(jī)器直接執(zhí)行，需通過(guò) 編譯成解釋程序的翻譯才可被機(jī)器執(zhí)行（機(jī)器語(yǔ)言）。 16algorithm1 1、算法的基本概念、算法的基本概念 算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。它是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每一個(gè)規(guī)則都是有效的，且是明確的，此順序?qū)⒃谟邢薜拇螖?shù)下終止。算法具有有窮性有窮性、確定性確定性、可行性可行性、輸入輸入和輸出輸出（擁有足夠的情報(bào)）等個(gè)重要特性。172 2、算法的基本要素、算法的基本要素v 對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作： 算術(shù)運(yùn)算、邏

5、輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸 算法中各操作之間的執(zhí)行順序； 描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程 圖、算法描述語(yǔ)言等； 一個(gè)算法一般可以用順序、選擇、循環(huán)三種基本結(jié)構(gòu) 組合而成。v 算法的控制結(jié)構(gòu)： 183 3、算法設(shè)計(jì)的基本方法、算法設(shè)計(jì)的基本方法v 列舉法v 歸納法v 遞推v 遞歸（以簡(jiǎn)潔的形式設(shè)計(jì)和描述算法）v 減半遞推技術(shù)v 回溯法191 1、時(shí)間復(fù)雜度、時(shí)間復(fù)雜度v 依據(jù)算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間 來(lái)度量。通常有事后統(tǒng)計(jì)法和事前分析估算法。v 一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操 作構(gòu)成的，算法時(shí)間取決于兩者的綜合效果。v 算法中基本操作重復(fù)執(zhí)行次

6、數(shù)n和算法執(zhí)行時(shí)間同步 增長(zhǎng)，稱作算法的時(shí)間復(fù)雜度。202 2、空間復(fù)雜度、空間復(fù)雜度v 一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。v 一個(gè)算法所占用的存儲(chǔ)空間包括算法程序所占的空間、 輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間以及某種數(shù)據(jù)結(jié)構(gòu)所需 要的附加存儲(chǔ)空間。v 一個(gè)上機(jī)執(zhí)行的程序除了需要存儲(chǔ)空間來(lái)寄存本身所用 指令、常數(shù)、變量和輸入數(shù)據(jù)外，也需要一些對(duì)數(shù)據(jù)進(jìn) 行操作的工作單元和存儲(chǔ)一些為實(shí)現(xiàn)計(jì)算所需信息的輔 助空間。213 3、例題講解、例題講解v 算法的時(shí)間復(fù)雜度是指算法的時(shí)間復(fù)雜度是指( ( C C ) ) A A、執(zhí)行算法程序所需要的時(shí)間執(zhí)行算法程序所需要的時(shí)間 B B、算法程序的長(zhǎng)度算法程序的

7、長(zhǎng)度 C C、算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù) D D、算法程序中的指令條數(shù)算法程序中的指令條數(shù)v 算法的基本特征是可行性、確定性、算法的基本特征是可行性、確定性、 【1 1】和擁有足夠和擁有足夠 的情報(bào)。的情報(bào)。 【答案】【答案】: :有窮性有窮性v 算法的空間復(fù)雜度是指算法的空間復(fù)雜度是指( ( D D ) ) A) A) 算法程序的長(zhǎng)度算法程序的長(zhǎng)度 B) B) 算法程序中的指令條數(shù)算法程序中的指令條數(shù) C) C) 算法程序所占的存儲(chǔ)空間算法程序所占的存儲(chǔ)空間 D) D) 執(zhí)行過(guò)程中所需要的存儲(chǔ)空間執(zhí)行過(guò)程中所需要的存儲(chǔ)空間 22v 在計(jì)算機(jī)中，算法是

8、指（ B B ） A) 加工方法 B) B) 解題方案的準(zhǔn)確而完整的描述解題方案的準(zhǔn)確而完整的描述 C) 排序方法 D) 查詢方法v 算法分析的目的是( D D ) A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 找出算法中輸入和輸出之間的關(guān)系 C) 分析算法的易懂性和可靠性 D) D) 分析算法的效率以求改進(jìn)分析算法的效率以求改進(jìn)v 算法的工作量大小和實(shí)現(xiàn)算法所需的存儲(chǔ)單元多少分別稱 為算法的 【 1 1 】 ?！敬鸢浮俊敬鸢浮? :時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度和空間復(fù)雜度 23Data Structure1 1、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容、數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容v 當(dāng)今計(jì)算機(jī)應(yīng)用的特點(diǎn)： 1、所處理的數(shù)

9、據(jù)量大且具有一定的關(guān)系； 2、對(duì)其操作不再是單純的數(shù)值計(jì)算，而更多地是需 要對(duì)其進(jìn)行組織、管理和檢索。 對(duì)數(shù)據(jù)的討論不單單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與對(duì)數(shù)據(jù)的討論不單單是數(shù)據(jù)本身，還要包括數(shù)據(jù)與數(shù)據(jù)之間的關(guān)系。數(shù)據(jù)之間的關(guān)系。24 學(xué) 生 基 本 情 況 學(xué) 號(hào) 姓 名 性 別 出 生 年 月 . 99070101 李 軍 男 80 12 . 99070102 王 顏 霞 女 81 2 . 99070103 孫 濤 男 80 9 . 99070104 單 曉 宏 男 81 3 . . . . . . 特點(diǎn)： 每個(gè)學(xué)生的信息占據(jù)一行，所有學(xué)生的信息按學(xué)號(hào)順序依次排列構(gòu)成一張表格； 表中每個(gè)學(xué)生的信

10、息依據(jù)學(xué)號(hào)的大小存在著一種前后關(guān)系，這就是我們所說(shuō)的線性結(jié)構(gòu)； 對(duì)它的操作通常是插入某個(gè)學(xué)生的信息，刪除某個(gè)學(xué)生的信息，更新某個(gè)學(xué)生的信息，按條件檢索某個(gè)學(xué)生的信息等等。v 應(yīng)用舉例1學(xué)籍檔案管理假設(shè)一個(gè)學(xué)籍檔案管理系統(tǒng)應(yīng)包含如下表所示的學(xué)生信息。25v 應(yīng)用舉例2家庭血緣關(guān)系圖 表示家庭成員的輩分關(guān)系，使用下圖1-1所示的形式描述。3 1 21 3 21 2 31 23 2 12 3 12 1 32 11家庭血緣關(guān)系圖特點(diǎn)： 在求解過(guò)程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是我們 所說(shuō)的樹(shù)形結(jié)構(gòu)； 對(duì)它的操作有：建立樹(shù)形結(jié)構(gòu)，輸出最結(jié)點(diǎn)內(nèi)容等等。v 應(yīng)用舉例3制定教學(xué)計(jì)劃 在制定教學(xué)計(jì)劃時(shí)，需

11、要考慮各門(mén)課程的開(kāi)設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計(jì)算機(jī)專業(yè)課程的開(kāi)設(shè)情況如下表所示： 計(jì)算機(jī)專業(yè)學(xué)生的必修課程 課課程程編編號(hào)號(hào) 課課程程名名稱稱 需需要要的的先先導(dǎo)導(dǎo) 課課程程編編號(hào)號(hào) C 1 程序設(shè)計(jì)基礎(chǔ) 無(wú) C 2 離散數(shù)學(xué) C 1 C 3 數(shù)據(jù)結(jié)構(gòu) C 1 ，C 2 C 4 匯編語(yǔ)言 C 1 C 5 算法分析與設(shè)計(jì) C 3 ，C 4 C 6 計(jì)算機(jī)組成原理 C 1 1 C 7 編譯原理 C 5 ，C 3 C 8 操作系統(tǒng) C 3 ，C 6 C 9 高等數(shù)學(xué) 無(wú) C 1 0 線性代數(shù) C 9 C 1 1 普通物理 C 9 C 1

12、2 數(shù)值分析 C 9 ，C 1 0 ，C 1 26這種數(shù)據(jù)可以用下面的圖來(lái)表示：v 課程先后關(guān)系的圖形描形式：c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計(jì)算機(jī)專業(yè)必修課程開(kāi)設(shè)先后關(guān)系27 1 1、數(shù)據(jù)的、數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu) 2 2、數(shù)據(jù)的、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 3 3、數(shù)據(jù)的、數(shù)據(jù)的運(yùn)算運(yùn)算：檢索、排序、插入、刪除、修改等。：檢索、排序、插入、刪除、修改等。 A A線性結(jié)構(gòu)線性結(jié)構(gòu)B B非線性結(jié)構(gòu)非線性結(jié)構(gòu)A A順序存儲(chǔ)順序存儲(chǔ) B B鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ) 線性表線性表?xiàng)ｊ?duì)隊(duì)樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面(亦稱物理結(jié)構(gòu)亦稱物理結(jié)

13、構(gòu))數(shù)據(jù)結(jié)構(gòu)的主要研究問(wèn)題：282 2、基本概念和術(shù)語(yǔ)、基本概念和術(shù)語(yǔ) 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究組織組織、存儲(chǔ)存儲(chǔ)和運(yùn)算運(yùn)算的一般方法的學(xué)科。例：整數(shù)整數(shù)(1,2)、實(shí)數(shù)實(shí)數(shù)(1.1,1.2)字符串字符串(Beijing)、圖形圖形、聲音聲音。計(jì)算機(jī)管理圖書(shū)問(wèn)題 ： 在圖書(shū)館里有各種卡片：有按書(shū)名編排的、有按作者編排的、有按分類編排。如何將查詢圖書(shū)的這些信息存入計(jì)算機(jī)中既要考慮查詢時(shí)間短，又要考慮節(jié)省空間。最簡(jiǎn)單的辦法之一是建立一張表，每一本書(shū)的信息在表中占一行，如：29數(shù)據(jù)元素在計(jì)算機(jī)中的表示 數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究組織組織、存儲(chǔ)存儲(chǔ)和運(yùn)算運(yùn)算的一般方法的學(xué)科。如何將0,1,2,3,4,5,6,7,8

14、,9這10個(gè)數(shù)存放在計(jì)算機(jī)中能最快地達(dá)到你所需要的目的？ 目的不同，最佳的存儲(chǔ)方方法就不同。從大到小排列：9,8,7,6,5,4,3,2,1,0輸出偶數(shù)：0,2,4,6,8,1,3,5,7,9 對(duì)數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理對(duì)數(shù)據(jù)結(jié)構(gòu)中的節(jié)點(diǎn)進(jìn)行操作處理（插入、刪除、修改、查找、排序）（插入、刪除、修改、查找、排序）30v 數(shù)據(jù)元素?cái)?shù)據(jù)元素( (Data Element)Data Element) 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體。 有時(shí)一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(Data ItemData Item)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位。數(shù)據(jù)元素亦稱節(jié)點(diǎn)節(jié)點(diǎn)或記錄記錄。數(shù)據(jù)結(jié)構(gòu)可描

15、述為數(shù)據(jù)結(jié)構(gòu)可描述為 Group=Group=（D D，R R）有限個(gè)數(shù)據(jù)元素的集合有限個(gè)數(shù)據(jù)元素的集合有限個(gè)節(jié)點(diǎn)間關(guān)系的集合有限個(gè)節(jié)點(diǎn)間關(guān)系的集合3132數(shù)據(jù)結(jié)構(gòu)可描述為數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（D，R）l 例例1：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成：一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R） D=春，夏，秋，冬春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）（春，夏），（夏，秋），（秋，冬）l 例例2：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成：家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成B=（D，R）D=父親，兒子，女兒父親，兒子，女兒 R=（父親，兒子），（父親，女兒）（父親，兒子），（父親，女兒）冬冬春春夏夏秋秋父親父

16、親兒子兒子女兒女兒33數(shù)據(jù)結(jié)構(gòu)也可用圖形表示數(shù)據(jù)結(jié)構(gòu)也可用圖形表示l一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成一年四季的數(shù)據(jù)結(jié)構(gòu)可表示成l家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成家庭成員數(shù)據(jù)結(jié)構(gòu)可表示成冬冬春春夏夏秋秋父親父親兒子兒子女兒女兒（ 概念：結(jié)點(diǎn)、前件、后件、根結(jié)點(diǎn)、葉子 ）34v 樹(shù)形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式全校學(xué)生檔案管理的組織方式計(jì)算機(jī)程序管理系統(tǒng)也是典型的計(jì)算機(jī)程序管理系統(tǒng)也是典型的樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)。35HGFECDBA361 14 42 23 3 D=1 , 2 , 3 , 4 D=1 , 2 , 3 , 4R=(1,2),(1,3), R=(1,2),(1,3), (1,4),(2,3), (1,

17、4),(2,3), (3,4),(2,4) (3,4),(2,4) 2 21 13 3 D= 1 , 2 , 3 D= 1 , 2 , 3 R=(1,2),(2,3),(3,2),(1,3) R=(1,2),(2,3),(3,2),(1,3)v 圖形結(jié)構(gòu)圖形結(jié)構(gòu)節(jié)點(diǎn)間的連結(jié)是任意的節(jié)點(diǎn)間的連結(jié)是任意的373 3、例題講解、例題講解v 數(shù)據(jù)處理的最小單位是數(shù)據(jù)處理的最小單位是( ( C C ) ) A)A)數(shù)據(jù)數(shù)據(jù) B)B)數(shù)據(jù)元素?cái)?shù)據(jù)元素 C) C) 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) D) D) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)v 數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門(mén)學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門(mén)學(xué)科，主要研究數(shù)據(jù)的

18、邏輯結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及( ( A A ) ) A) A) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B) B) 計(jì)算方法計(jì)算方法 C) C) 數(shù)據(jù)映象數(shù)據(jù)映象 D) D) 邏輯存儲(chǔ)邏輯存儲(chǔ)v 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的 【4 4】 以及對(duì)數(shù)據(jù)的以及對(duì)數(shù)據(jù)的操作運(yùn)算。操作運(yùn)算。 【答案【答案】物理結(jié)構(gòu)（或存儲(chǔ)結(jié)構(gòu)）物理結(jié)構(gòu)（或存儲(chǔ)結(jié)構(gòu)）38v 線性結(jié)構(gòu)與非線性結(jié)構(gòu)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)：v 線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)線性結(jié)構(gòu)：有且只有一個(gè)根結(jié)點(diǎn)；每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。結(jié)點(diǎn)最多有一個(gè)前件，

19、也最多有一個(gè)后件。 如：一年四季，如：一年四季，2626個(gè)英文字母?jìng)€(gè)英文字母v非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。非線性結(jié)構(gòu)：線性以外的數(shù)據(jù)結(jié)構(gòu)。 如：反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu)如：反映家庭成員間輩分關(guān)系的數(shù)據(jù)結(jié)構(gòu) 394、線性表、線性表（Linear List）學(xué)學(xué) 生生 成成 績(jī)績(jī) 表表 ( (按成績(jī)排列按成績(jī)排列) )86胡孝臣986110395劉忠賞9861107100張卓9861109成 績(jī)姓 名學(xué) 號(hào)v 線性表線性表結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)：結(jié)點(diǎn)間是以線性關(guān)系聯(lián)結(jié)：v 線性表線性表：具有線性結(jié)構(gòu)的有限序列。 數(shù)據(jù)元素在線性表中的位置只取決于它們自己的序號(hào)，即數(shù)據(jù)元素之間的相對(duì)位置是

20、線性的。v 線性表的定義線性表的定義: : 線性表線性表是是n n個(gè)元素的有限序列，它們之間的關(guān)系可以排成個(gè)元素的有限序列，它們之間的關(guān)系可以排成一個(gè)線性序列：一個(gè)線性序列：a1a1，a2a2， ，aiai， ，anan 其中其中n n稱作表的稱作表的長(zhǎng)度長(zhǎng)度，當(dāng)，當(dāng)n=0n=0時(shí)，稱作時(shí)，稱作空表空表。v 線性表的特點(diǎn)：線性表的特點(diǎn)： 1 1、線性表中所有元素的性質(zhì)相同。、線性表中所有元素的性質(zhì)相同。 2 2、除第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且、除第一個(gè)和最后一個(gè)數(shù)據(jù)元素之外，其它數(shù)據(jù)元素有且 僅有一個(gè)前驅(qū)和一個(gè)后繼。第一個(gè)數(shù)據(jù)元素?zé)o前驅(qū)，最僅有一個(gè)前驅(qū)和一個(gè)后繼。第一個(gè)數(shù)據(jù)元

21、素?zé)o前驅(qū)，最 后一個(gè)數(shù)據(jù)元素?zé)o后繼。后一個(gè)數(shù)據(jù)元素?zé)o后繼。 3 3、數(shù)據(jù)元素在表中的位置只取決于它自身的序號(hào)。、數(shù)據(jù)元素在表中的位置只取決于它自身的序號(hào)。v 在線性表上常用的運(yùn)算有：在線性表上常用的運(yùn)算有： 初始化、求長(zhǎng)度、取元素、修改、前插、刪除、檢索、排序初始化、求長(zhǎng)度、取元素、修改、前插、刪除、檢索、排序4041v 線性表的線性表的 順序存儲(chǔ)結(jié)構(gòu) 及其及其 插入 與與 刪除 操作操作 特點(diǎn)：特點(diǎn)： 1 1、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲(chǔ)空間、線性表中數(shù)據(jù)元素類型一致，只有數(shù)據(jù)域，存儲(chǔ)空間 利用率高。利用率高。 2 2、所有元素所占的存儲(chǔ)空間是連續(xù)的。、所有元素所占的存儲(chǔ)空間是

22、連續(xù)的。 3 3、各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的、各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的 （a a）做插入、刪除時(shí)需移動(dòng)大量元素。做插入、刪除時(shí)需移動(dòng)大量元素。 （b b）空間估計(jì)不明時(shí)，按最大空間分配?？臻g估計(jì)不明時(shí)，按最大空間分配。42順順序序存存儲(chǔ)儲(chǔ)存儲(chǔ)地址存儲(chǔ)地址存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容元素元素n n.元素元素i i.元素元素2 2元素元素1 1L Lo o + + mL Lo o+(i-1)+(i-1)mLo+Lo+（n-1)n-1)mLoc(Loc(元素元素i)=Li)=Lo o+ +（i-1)i-1)m每個(gè)元素所占用每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)的存儲(chǔ)單元個(gè)數(shù)v 線性表

23、的線性表的 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：首地址首地址起始地址起始地址基地址基地址43元素元素a a1 1元素元素a a2 2.元素元素a ai+1i+1. 0 0 1 1i i 線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)可用可用C C語(yǔ)言中的一維數(shù)組來(lái)描述語(yǔ)言中的一維數(shù)組來(lái)描述. .第第i i個(gè)元素的個(gè)元素的a ai i存儲(chǔ)地址：存儲(chǔ)地址：Loc(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)* * m mVV VV ViViVm-1Vm-1 intint VM; VM; 其中：其中：V V是數(shù)組的名字，是數(shù)組的名字，M M是數(shù)組大小，是數(shù)組大小， 假設(shè)數(shù)組中的元素

24、是整型類型假設(shè)數(shù)組中的元素是整型類型v插入運(yùn)算插入運(yùn)算.a2a a1 1an.ai+1ai01i-1in-1a ai-1i-1.a a2 2a a1 1a alengthlength a ai+1i+1a ai i x x a ai-1i-1. a a2 2 a a1 1 X X a ai ia ai+1i+1.a alengtlength h 插入算法的分析 假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：1n1iis2n1)i(n1n1E44在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：分析結(jié)論

25、分析結(jié)論 順序存儲(chǔ)結(jié)構(gòu)表示的線性表，在做插入或刪除操作時(shí)，平均需要移動(dòng)大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且經(jīng)常要對(duì)其做插入或刪除操作時(shí)，這一點(diǎn)需要值得考慮。n1idl21ni)(nn1Ev刪除算法的分析刪除算法的分析45q 線性表的例題講解線性表的例題講解v 順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置順序存儲(chǔ)方法是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置 【1 1】 的存儲(chǔ)單元中。的存儲(chǔ)單元中。 【答案【答案】相鄰相鄰v 長(zhǎng)度為長(zhǎng)度為n n的順序存儲(chǔ)線性表中，當(dāng)在任何位置上插入一個(gè)元的順序存儲(chǔ)線性表中，當(dāng)在任何位置上插入一個(gè)元 素概率都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù)素概率

26、都相等時(shí)，插入一個(gè)元素所需移動(dòng)元素的平均個(gè)數(shù) 為為【2 2】 。 【答案【答案】 n/2n/2v 線性表線性表L=(a1,a2,a3,L=(a1,a2,a3,aiai，an)an)，下列說(shuō)法正確的是（下列說(shuō)法正確的是（D D） A) A) 每個(gè)元素都有一個(gè)直接前件和直接后件每個(gè)元素都有一個(gè)直接前件和直接后件 B) B) 線性表中至少要有一個(gè)元素線性表中至少要有一個(gè)元素 C) C) 表中諸元素的排列順序必須是由小到大或由大到小表中諸元素的排列順序必須是由小到大或由大到小 D) D) 除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一 個(gè)且只有一個(gè)直接

27、前件和直接后件個(gè)且只有一個(gè)直接前件和直接后件 4647v 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的( ( C C ) ) A) A) 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)B) B) 物理結(jié)構(gòu)物理結(jié)構(gòu) C) C) 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)D) D) 物理和存儲(chǔ)結(jié)構(gòu)物理和存儲(chǔ)結(jié)構(gòu) 下列敘述中，錯(cuò)誤的是（下列敘述中，錯(cuò)誤的是（ B B ） A) A) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率密切相關(guān) B) B) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率無(wú)關(guān)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)與數(shù)據(jù)處理的效率無(wú)關(guān) C) C) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中所占的空間不一定是連續(xù)的數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在

28、計(jì)算機(jī)中所占的空間不一定是連續(xù)的 D) D) 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（ B B ） A A）數(shù)據(jù)所占的存儲(chǔ)空間數(shù)據(jù)所占的存儲(chǔ)空間 B B）數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示 C C）數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式 D D）存儲(chǔ)在外存中的數(shù)據(jù)存儲(chǔ)在外存中的數(shù)據(jù) 根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成將數(shù)據(jù)結(jié)構(gòu)分成( ( C C ) ) A) A) 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)動(dòng)態(tài)結(jié)構(gòu)

29、和靜態(tài)結(jié)構(gòu) B) B) 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C) C) 線性結(jié)構(gòu)和非線性結(jié)構(gòu)線性結(jié)構(gòu)和非線性結(jié)構(gòu) D) D) 內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和數(shù)據(jù)的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)和 【2 2】?jī)纱箢?。兩大類。非線性結(jié)構(gòu)非線性結(jié)構(gòu) 當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)時(shí)，其主要特點(diǎn)是當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)時(shí)，其主要特點(diǎn)是【1】。 【答案【答案】邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰。邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲(chǔ)結(jié)構(gòu)中仍相鄰。485 5、堆棧和隊(duì)列、堆棧和隊(duì)列q 堆棧和隊(duì)列的定義堆棧和隊(duì)列的定義 棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時(shí)要受到是

30、兩種特殊的線性表，它們是運(yùn)算時(shí)要受到某些限制的線性表，故也稱為某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。限定性的數(shù)據(jù)結(jié)構(gòu)。v 堆棧的定義堆棧的定義堆棧：堆棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表, ,此種此種 結(jié)構(gòu)稱為結(jié)構(gòu)稱為后進(jìn)先出。后進(jìn)先出。設(shè)棧設(shè)棧s=s=（a a1 1，a a2 2，a ai i， ，a an n）, ,其中其中a a1 1是是棧底棧底元素，元素， a an n是是棧頂棧頂元素。元素。棧頂（棧頂（top)top)：允許插入和刪除的一端；允許插入和刪除的一端；約定約定toptop始終指向新數(shù)據(jù)元素將存放的位置。始終

31、指向新數(shù)據(jù)元素將存放的位置。棧底棧底（bottom):bottom):不允許插入和刪除的一端。不允許插入和刪除的一端。 a1 a2 . an進(jìn)棧進(jìn)棧出棧出棧棧頂棧頂棧底棧底49v 隊(duì)列的定義隊(duì)列的定義隊(duì)列：隊(duì)列：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入， 在表的另一端進(jìn)行刪除的線性表在表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為。此種結(jié)構(gòu)稱為先進(jìn)先進(jìn) 先出（先出（FIFO）表表。 a1 , a2 , a3 , a4 , an-1 , an隊(duì)隊(duì) 列列 示示 意意 圖圖隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾v 隊(duì)列的主要運(yùn)算隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插

32、入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；50q 堆棧和隊(duì)列的例題講解堆棧和隊(duì)列的例題講解v棧和隊(duì)列的共同特點(diǎn)是（棧和隊(duì)列的共同特點(diǎn)是（ C C ） A)A)都是先進(jìn)先出都是先進(jìn)先出 B) B) 都是先進(jìn)后出都是先進(jìn)后出 C) C) 只允許在端點(diǎn)處插入和刪除元素只允許在端點(diǎn)處插入和刪除元素 D) D) 沒(méi)有共同點(diǎn)沒(méi)有共同點(diǎn)v如果進(jìn)棧序列為如果進(jìn)棧序列為e1,e2,e3,e4e1,e2,e3,e4，則可能的出棧序列是（則可能的出棧序列是（ B B ） A) e3,e1,e4,e2 A) e3,e1,e4,e2 B) e4,e3,e2,e1B) e4,e3,e

33、2,e1 C) e3,e4,e1,e2 C) e3,e4,e1,e2 D) D) 任意順序任意順序v一些重要的程序語(yǔ)言一些重要的程序語(yǔ)言( (如如C C語(yǔ)言和語(yǔ)言和PascalPascal語(yǔ)言語(yǔ)言) ) 允許過(guò)程的允許過(guò)程的遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用（遞歸調(diào)用。而實(shí)現(xiàn)遞歸調(diào)用中的存儲(chǔ)分配通常用（ A A ） A) A) 棧棧 B) B) 堆堆 C) C) 數(shù)組數(shù)組 D) D) 鏈表鏈表 51v 棧底至棧頂依次存放元素棧底至棧頂依次存放元素A A、B B、C C、D D，在第五個(gè)元素在第五個(gè)元素E E 入棧前，棧中元素可以出棧，則出棧序列可能是（入棧前，棧中元素可以出棧，則出棧序

34、列可能是（ B B ） A) ABCEDA) ABCED B) DCBEAB) DCBEA C) DBCEA C) DBCEA D) CDABE D) CDABE v 棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（棧通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ A A ） A) A) 順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B) B) 散列方式和索引方式散列方式和索引方式 C) C) 鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 D) D) 線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)v 棧和隊(duì)列通常采用的存儲(chǔ)結(jié)構(gòu)是棧和隊(duì)列通常采用的存儲(chǔ)結(jié)構(gòu)是 【1 1】。 【答案【答案】鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)v

35、 下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（下列數(shù)據(jù)結(jié)構(gòu)中，按先進(jìn)后出原則組織數(shù)據(jù)的是（ B B ） A) A) 線性鏈表線性鏈表 B) B) 棧棧 C) C) 循環(huán)鏈表循環(huán)鏈表 D) D) 順序表順序表 52v 當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列當(dāng)循環(huán)隊(duì)列非空且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為已滿，不能進(jìn)行入隊(duì)運(yùn)算。這種情況稱為【2 2】。答案：答案：上溢上溢 v 由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是（由兩個(gè)棧共享一個(gè)存儲(chǔ)空間的好處是（ B B ） A) A) 減少存取時(shí)間，降低下溢發(fā)生的機(jī)率減少存取時(shí)間，降低下溢發(fā)生的機(jī)率 B) B)

36、 節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率節(jié)省存儲(chǔ)空間，降低上溢發(fā)生的機(jī)率 C) C) 減少存取時(shí)間，降低上溢發(fā)生的機(jī)率減少存取時(shí)間，降低上溢發(fā)生的機(jī)率 D) D) 節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率節(jié)省存儲(chǔ)空間，降低下溢發(fā)生的機(jī)率v 下列關(guān)于棧的敘述中正確的是（下列關(guān)于棧的敘述中正確的是（ D D ）) )在棧中只能插入數(shù)據(jù)在棧中只能插入數(shù)據(jù) B B）在棧中只能刪除數(shù)據(jù)在棧中只能刪除數(shù)據(jù)C C）棧是先進(jìn)先出的線性表?xiàng)Ｊ窍冗M(jìn)先出的線性表 D D）棧是后進(jìn)先出的線性表?xiàng)Ｊ呛筮M(jìn)先出的線性表v 下列關(guān)于隊(duì)列的敘述中正確的是（下列關(guān)于隊(duì)列的敘述中正確的是（ C C ）在隊(duì)列中只能插入數(shù)據(jù)）在隊(duì)列中只能插入數(shù)據(jù)

37、B B）在隊(duì)列中只能刪除數(shù)據(jù)在隊(duì)列中只能刪除數(shù)據(jù)C C）隊(duì)列是先進(jìn)先出的線性表隊(duì)列是先進(jìn)先出的線性表 D D）隊(duì)列是后進(jìn)先出的線性表隊(duì)列是后進(jìn)先出的線性表 53 順序存儲(chǔ)結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里。v 順序存儲(chǔ)結(jié)構(gòu)的三個(gè)缺點(diǎn)： 1.作插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。 2.長(zhǎng)度變化較大時(shí)，需按最大空間分配。 3.表的容量難以擴(kuò)充。存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容元素元素n n.元素元素i i.元素元素2 2元素元素1 154556 6、線性鏈表、線性鏈表v線性鏈表的基本概念：線性鏈表的基本概念： 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。 為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，

38、計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn)。將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部：v一部分稱為數(shù)據(jù)域，用于存儲(chǔ)數(shù)據(jù)元素的值；v另一部分稱為指針域，用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)結(jié)點(diǎn)的地址），也就是指向后件結(jié)點(diǎn). 線性鏈表中存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)如圖2.20所示56571、比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小 (每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針域組成，所以相同空間內(nèi)假設(shè)全存滿的話順序比鏈?zhǔn)酱鎯?chǔ)更多)。2、邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3、插入、刪除靈活 (不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。4、查找結(jié)點(diǎn)時(shí)鏈?zhǔn)酱鎯?chǔ)要比順序存儲(chǔ)慢。v 鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：5

39、8 指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針。 當(dāng)HEAD=NULL（或0）時(shí)稱為空表。 對(duì)于線性鏈表，可以從頭指針開(kāi)始，沿著各個(gè)結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。線性鏈表的邏輯結(jié)構(gòu)圖所示59596061v 線性鏈表的基本運(yùn)算：線性鏈表的基本運(yùn)算：線性鏈表的運(yùn)算主要有以下幾個(gè)：線性鏈表的運(yùn)算主要有以下幾個(gè)： 在線性鏈表中包含指定元素的結(jié)點(diǎn)之前在線性鏈表中包含指定元素的結(jié)點(diǎn)之前 插入插入一個(gè)新元素。一個(gè)新元素。 在線性鏈表中在線性鏈表中刪除刪除包含指定元素的結(jié)點(diǎn)。包含指定元素的結(jié)點(diǎn)。 將兩個(gè)線性鏈表按要求將兩個(gè)線性鏈表按要求合并合并成一個(gè)線性成一個(gè)線性 鏈表。鏈表。62 線性鏈表的線性鏈表

40、的 插入插入 運(yùn)算：運(yùn)算： 線性鏈表的插入線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。的線性表中插入一個(gè)新元素。 為了要在線性鏈表中插入一個(gè)新元素，為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，然后將存首先要給該元素分配一個(gè)新結(jié)點(diǎn)，然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。位置。636364 線性鏈表的刪除線性鏈表的刪除指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。線性表中刪除包含指定元素的結(jié)點(diǎn)。 為了在線性鏈表中刪除包含指定元素的為了在線性鏈表中刪除包含指定元素的結(jié)

41、點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。 線性鏈表的線性鏈表的 刪除刪除 運(yùn)算：運(yùn)算：6565 循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個(gè)特點(diǎn)：兩個(gè)特點(diǎn)： 循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。 在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。 圖圖2.292.29是循環(huán)鏈表的示意圖。是循環(huán)鏈表的示意圖。v循環(huán)鏈表：循環(huán)鏈表：6667 在實(shí)際應(yīng)用中，循環(huán)鏈表與線性單鏈表相

42、在實(shí)際應(yīng)用中，循環(huán)鏈表與線性單鏈表相比主要有以下兩個(gè)方面的優(yōu)點(diǎn)：比主要有以下兩個(gè)方面的優(yōu)點(diǎn)： 在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn) 的位置，就可以從它出發(fā)訪問(wèn)到表中其他所的位置，就可以從它出發(fā)訪問(wèn)到表中其他所 有的結(jié)點(diǎn)。有的結(jié)點(diǎn)。 由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因 此，在任何情況下，循環(huán)鏈表中至少有一個(gè)此，在任何情況下，循環(huán)鏈表中至少有一個(gè) 結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。v鏈表不具有的特點(diǎn)是（鏈表不具有的特點(diǎn)是（ B B ） A) A) 不必事先估計(jì)存儲(chǔ)空間不必

43、事先估計(jì)存儲(chǔ)空間 B) B) 可隨機(jī)訪問(wèn)任一元素可隨機(jī)訪問(wèn)任一元素 C) C) 插入刪除不需要移動(dòng)元素插入刪除不需要移動(dòng)元素 D) D) 所需空間與線性表長(zhǎng)度成正比所需空間與線性表長(zhǎng)度成正比v數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)，線性鏈表屬于 【1 1】 。 【答案【答案】存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)v線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是線性表的順序存儲(chǔ)結(jié)構(gòu)和線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是( ( B B ) )A) A) 順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)B) B) 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的存儲(chǔ)

44、結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)C) C) 隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)D) D) 任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)任意存取的存儲(chǔ)結(jié)構(gòu)、任意存取的存儲(chǔ)結(jié)構(gòu)q 線性鏈表的例題講解線性鏈表的例題講解68697 7、樹(shù)與二叉樹(shù)：、樹(shù)與二叉樹(shù)：v 樹(shù)的基本概念：樹(shù)的基本概念： 前面我們討論的線性表，棧、隊(duì)列和數(shù)組等都是線性結(jié)構(gòu)。而樹(shù)是一種非線性數(shù)據(jù)結(jié)構(gòu)，它的每一個(gè)結(jié)點(diǎn)，都可以有不止一個(gè)直接后繼，除根外的所有結(jié)點(diǎn)，都有且只有一個(gè)直接前趨。這些數(shù)據(jù)結(jié)點(diǎn)按分支關(guān)系組織起來(lái)，清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。 70現(xiàn)實(shí)世界中，能用樹(shù)的結(jié)構(gòu)表示的例子現(xiàn)實(shí)世界中，能

45、用樹(shù)的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。學(xué)校的行政關(guān)系、書(shū)的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。71717272 二叉樹(shù)(binary tree)是一種很有用的非線性結(jié)構(gòu)。 二叉樹(shù)具有以下兩個(gè)特點(diǎn)：（1）非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別 稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。v 二叉樹(shù)（二叉樹(shù)（Binary TreeBinary Tree）：）： 因?yàn)闃?shù)的每個(gè)結(jié)點(diǎn)的度不同，存儲(chǔ)困難，使對(duì)樹(shù)的處理算法很復(fù)雜。所以引出二叉樹(shù)的討論。737474性質(zhì)性質(zhì)1 1：在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn) （即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多 一個(gè)。例子例子1

46、1：某二叉樹(shù)中度為2的結(jié)點(diǎn)有18個(gè)，則 該二叉樹(shù)中有 19 19 個(gè)葉子結(jié)點(diǎn)。二叉樹(shù)的性質(zhì)：二叉樹(shù)的性質(zhì)： 特別要注意：二叉樹(shù)不是樹(shù)的特殊情況。a aa ab bb b兩棵不同的二叉樹(shù)7576性質(zhì)性質(zhì)2 2：二叉樹(shù)的第i層上至多有2 i-1（i 1）個(gè)結(jié)點(diǎn)二叉樹(shù)的性質(zhì)：二叉樹(shù)的性質(zhì)：423167891011121314155第三層上(i=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個(gè)節(jié)點(diǎn)。77二叉樹(shù)的性質(zhì)：二叉樹(shù)的性質(zhì)：性質(zhì)性質(zhì)3 3：深度為深度為h h的二叉樹(shù)中至多含有的二叉樹(shù)中至多含有2 2h h-1 -1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)423167891011121314155此樹(shù)的深度此

47、樹(shù)的深度h=4h=4，共有共有2 24 4-1=15-1=15個(gè)節(jié)點(diǎn)。個(gè)節(jié)點(diǎn)。78v滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)與完全二叉樹(shù) 滿二叉樹(shù)是指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。 完全二叉樹(shù)是指這樣的二叉樹(shù)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。 注意：滿二叉樹(shù)是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。79v 滿二叉樹(shù)的特點(diǎn)：滿二叉樹(shù)的特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。每一層上都含有最大結(jié)點(diǎn)數(shù)。7980v完全二叉樹(shù)的特點(diǎn)：完全二叉樹(shù)的特點(diǎn)：除最后一層外，每一層都取最大除最后一層外，每一層都取最大 結(jié)點(diǎn)數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置結(jié)點(diǎn)

48、數(shù)，最后一層結(jié)點(diǎn)都集中在該層最左邊的若干位置8081 對(duì)于對(duì)于完全二叉樹(shù)完全二叉樹(shù)而言而言如果它的結(jié)點(diǎn)個(gè)數(shù)為如果它的結(jié)點(diǎn)個(gè)數(shù)為偶偶數(shù)，則該二叉樹(shù)中：數(shù)，則該二叉樹(shù)中：葉子結(jié)點(diǎn)的個(gè)數(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)=非葉子結(jié)點(diǎn)的個(gè)數(shù)非葉子結(jié)點(diǎn)的個(gè)數(shù)如果它的結(jié)點(diǎn)個(gè)數(shù)為如果它的結(jié)點(diǎn)個(gè)數(shù)為奇奇數(shù)，則該二叉樹(shù)中：數(shù)，則該二叉樹(shù)中：葉子結(jié)點(diǎn)的個(gè)數(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)=非葉子結(jié)點(diǎn)的個(gè)數(shù)非葉子結(jié)點(diǎn)的個(gè)數(shù)+1+1（即葉子結(jié)點(diǎn)數(shù)比非葉子結(jié)點(diǎn)數(shù)（即葉子結(jié)點(diǎn)數(shù)比非葉子結(jié)點(diǎn)數(shù)多一個(gè)多一個(gè)）規(guī)律總結(jié)：規(guī)律總結(jié)：82v 例題講解例題講解1、設(shè)一棵完全二叉樹(shù)共有700個(gè)結(jié)點(diǎn)，則 在該二叉樹(shù)中有 350 350 個(gè)葉子結(jié)點(diǎn)。2、在深度為5的滿二叉樹(shù)中

49、，葉子結(jié)點(diǎn)的 個(gè)數(shù)為（ C C ） A) 32 B) 31 C) 16 D) 15 v二叉樹(shù)的遍歷二叉樹(shù)的遍歷 二叉樹(shù)的遍歷是指不重復(fù)地訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。 二叉樹(shù)的遍歷可以分為三種：前序前序遍歷、中中序序遍歷、后序后序遍歷。 設(shè)訪問(wèn)根結(jié)點(diǎn)記作設(shè)訪問(wèn)根結(jié)點(diǎn)記作V V；遍歷根的左子樹(shù)記作遍歷根的左子樹(shù)記作L L；遍歷根的右子樹(shù)記作遍歷根的右子樹(shù)記作R R； 前序：前序： VLRVLR（即即根根左右）左右） 中序：中序： LVRLVR（即左即左根根右）右） 后序：后序： LRVLRV（即左右即左右根根）838484851 1、設(shè)一棵二叉樹(shù)的中序遍歷結(jié)果為、設(shè)一棵二叉樹(shù)的中序遍歷結(jié)果為DBEAF

50、C,DBEAFC, 前序遍歷結(jié)果為前序遍歷結(jié)果為ABDECFABDECF，則后序遍歷結(jié)則后序遍歷結(jié) 果為：果為： DEBFCADEBFCA v 例題講解例題講解2 2、已知一棵二叉樹(shù)前序遍歷和中序遍歷分別、已知一棵二叉樹(shù)前序遍歷和中序遍歷分別 為為ABDEGCFHABDEGCFH和和DBGEACHFDBGEACHF，則該二叉樹(shù)則該二叉樹(shù) 的后序遍歷為（的后序遍歷為（ B B ） A) GEDHFBCA A) GEDHFBCA B) DGEBHFCAB) DGEBHFCA C) ABCDEFGH C) ABCDEFGH D) ACBFEDHG D) ACBFEDHG v具有具有3 3個(gè)結(jié)點(diǎn)的二叉

51、樹(shù)有（個(gè)結(jié)點(diǎn)的二叉樹(shù)有（ D D ） A) 2A) 2種形態(tài)種形態(tài) B) 4B) 4種形態(tài)種形態(tài) C) 7C) 7種形態(tài)種形態(tài) D) 5D) 5種形態(tài)種形態(tài) v 設(shè)有下列二叉樹(shù)：設(shè)有下列二叉樹(shù)： 對(duì)此二叉樹(shù)前序遍歷的結(jié)果為（對(duì)此二叉樹(shù)前序遍歷的結(jié)果為（ B B ） A) ZBTTCPXA A) ZBTTCPXA B) ATBZXCTP B) ATBZXCTP C) ZBTACTXP D) ATBZXCPT C) ZBTACTXP D) ATBZXCPT 86878 8、查找和排序：、查找和排序：v查找查找又稱為又稱為檢索檢索 查找算法的評(píng)價(jià)主要考慮算法的時(shí)間復(fù)雜查找算法的評(píng)價(jià)主要考慮算法的時(shí)間

52、復(fù)雜性，既可以采用數(shù)量級(jí)的形式表示，也可以采性，既可以采用數(shù)量級(jí)的形式表示，也可以采用平均檢索（查找）長(zhǎng)度，即在查找成功情況用平均檢索（查找）長(zhǎng)度，即在查找成功情況下的平均比較次數(shù)來(lái)表示。下的平均比較次數(shù)來(lái)表示。 查找可分為查找可分為順序查找順序查找和和二分法查找二分法查找兩種。兩種。88（a a）順序查找：順序查找： 順序查找順序查找又稱又稱線性查找線性查找。它是一種最簡(jiǎn)單、。它是一種最簡(jiǎn)單、最基本的查找方法?；舅枷胧牵簭谋碇械谝蛔罨镜牟檎曳椒??；舅枷胧牵簭谋碇械谝粭l記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值條記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較。若某個(gè)記錄的關(guān)鍵字和給定值相等，的

53、比較。若某個(gè)記錄的關(guān)鍵字和給定值相等，則查找成功；否則，若直至最后一個(gè)記錄，其則查找成功；否則，若直至最后一個(gè)記錄，其關(guān)鍵字和給定值都不相等，則表明表中沒(méi)有所關(guān)鍵字和給定值都不相等，則表明表中沒(méi)有所查記錄，查找不成功。查記錄，查找不成功。89 二分查找二分查找又稱又稱折半查找折半查找。作為二分查找對(duì)。作為二分查找對(duì)象的表必須是順序存儲(chǔ)的有序表，即各記錄的象的表必須是順序存儲(chǔ)的有序表，即各記錄的次序是按其關(guān)鍵字的大小順序（以下假定按從次序是按其關(guān)鍵字的大小順序（以下假定按從小到大的順序）排列的表。小到大的順序）排列的表。（b b）二分查找：二分查找：90 二分查找的二分查找的具體做法具體做法是是

54、: : 先取表先取表中間中間位置的記錄關(guān)位置的記錄關(guān)鍵字與給定值比較。若相等鍵字與給定值比較。若相等, , 則查找成功；否則則查找成功；否則, , 若給若給定值比該記錄的關(guān)鍵字小，則給定值必在表的前半部分。定值比該記錄的關(guān)鍵字小，則給定值必在表的前半部分。 在這前半部分中再取中間位置記錄的關(guān)鍵字進(jìn)行比較，在這前半部分中再取中間位置記錄的關(guān)鍵字進(jìn)行比較，就又可以排除這部分的一半。依次反復(fù)進(jìn)行，直到找到就又可以排除這部分的一半。依次反復(fù)進(jìn)行，直到找到給定值或找完全表而找不到為止。給定值或找完全表而找不到為止。 對(duì)于對(duì)于n n較大時(shí)，查找長(zhǎng)度可以近似地表示為較大時(shí)，查找長(zhǎng)度可以近似地表示為91 排序

55、排序是將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)是將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái)。律順次排列起來(lái)。 通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即由多個(gè)數(shù)通常數(shù)據(jù)對(duì)象有多個(gè)屬性域，即由多個(gè)數(shù)據(jù)成員組成據(jù)成員組成, , 其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象其中有一個(gè)屬性域可用來(lái)區(qū)分對(duì)象, , 作為排序依據(jù)。該域稱為作為排序依據(jù)。該域稱為關(guān)鍵字（關(guān)鍵字（keykey）。 排序的時(shí)間開(kāi)銷是衡量算法好壞的最重要排序的時(shí)間開(kāi)銷是衡量算法好壞的最重要的標(biāo)志。對(duì)于長(zhǎng)度為的標(biāo)志。對(duì)于長(zhǎng)度為n n的有序線性表，查找時(shí)最的有序線性表，查找時(shí)最壞情況只需比較壞情況只需比較 n n次。次。v 排序（排序（sortsort）92（a a）交

56、換類排序：交換類排序：交換類排序法：交換類排序法：冒泡排序法冒泡排序法：需要比較的次數(shù)為：需要比較的次數(shù)為n(n-1)/2n(n-1)/2快速排序法快速排序法：是對(duì)冒泡排序的改進(jìn)，是：是對(duì)冒泡排序的改進(jìn)，是目目 前內(nèi)部排序中速度最快的一種。前內(nèi)部排序中速度最快的一種。 93（b b）插入類排序：插入類排序： 插入類排序的插入類排序的基本方法基本方法是：每步將一個(gè)待是：每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已排序的對(duì)象，按其關(guān)鍵字大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止全部插入為止。簡(jiǎn)單插入排序法：簡(jiǎn)單插入排序法：

57、最壞情況需要最壞情況需要n(n-1)/2n(n-1)/2次比較；次比較；希爾排序法：希爾排序法：最壞情況需要最壞情況需要OO（n n ）次比較。次比較。94（c c）選擇類排序：選擇類排序： 選擇類排序的選擇類排序的思想思想是：每一趟（例如，第是：每一趟（例如，第i i趟，趟，i=0i=0，1 1，n n2 2）在后面在后面n ni i個(gè)待排序?qū)ο笾羞x個(gè)待排序?qū)ο笾羞x出關(guān)鍵字最?。ㄉ?，若為降序，選出最大關(guān)鍵出關(guān)鍵字最?。ㄉ?，若為降序，選出最大關(guān)鍵字）的對(duì)象，作為有序?qū)ο笮蛄械牡谧郑┑膶?duì)象，作為有序?qū)ο笮蛄械牡趇 i個(gè)對(duì)象。待個(gè)對(duì)象。待到第到第n n2 2趟作完，待排序?qū)ο笾皇Ｏ绿俗魍?，待?/p>

58、序?qū)ο笾皇Ｏ? 1個(gè)，不用再個(gè)，不用再選了，結(jié)束排序。選了，結(jié)束排序。簡(jiǎn)單選擇排序法簡(jiǎn)單選擇排序法，最壞情況需要，最壞情況需要n(n-1)/2n(n-1)/2次比較；次比較；堆排序法堆排序法，最壞情況需要，最壞情況需要OO（nlognlog2 2 n n）次比較。次比較。95（一）程序設(shè)計(jì)方法與風(fēng)格（一）程序設(shè)計(jì)方法與風(fēng)格 v 如何形成良好的程序設(shè)計(jì)風(fēng)格：如何形成良好的程序設(shè)計(jì)風(fēng)格： 1 1、源程序內(nèi)部文檔化；、源程序內(nèi)部文檔化； 選擇標(biāo)識(shí)符的名字選擇標(biāo)識(shí)符的名字 注釋（注釋（序言性序言性和和功能性功能性注釋）注釋） 程序的視覺(jué)組織程序的視覺(jué)組織一般位于模塊的一般位于模塊的首部，用于說(shuō)明首部，

59、用于說(shuō)明模塊的相關(guān)信息模塊的相關(guān)信息位于源程序位于源程序模塊內(nèi)部模塊內(nèi)部96 顯式地說(shuō)明一切變量顯式地說(shuō)明一切變量 數(shù)據(jù)說(shuō)明的次序應(yīng)該規(guī)范化數(shù)據(jù)說(shuō)明的次序應(yīng)該規(guī)范化 便于查找變量（按順序排列）便于查找變量（按順序排列） 對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說(shuō)明對(duì)復(fù)雜數(shù)據(jù)結(jié)構(gòu)應(yīng)注釋說(shuō)明 2 2、數(shù)據(jù)說(shuō)明、數(shù)據(jù)說(shuō)明3 3、語(yǔ)句的結(jié)構(gòu)、語(yǔ)句的結(jié)構(gòu) 每條語(yǔ)句簡(jiǎn)單明了 盡量不用或少用GOTO語(yǔ)句 盡量只采用3種基本控制結(jié)構(gòu)編程4 4、輸入和輸出、輸入和輸出 對(duì)所有輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查對(duì)所有輸入數(shù)據(jù)進(jìn)行校驗(yàn)和合理性檢查 輸入輸出格式保持一致輸入輸出格式保持一致 設(shè)計(jì)良好的輸出報(bào)表設(shè)計(jì)良好的輸出報(bào)表 輸入方式輸入方

60、式應(yīng)力求簡(jiǎn)單，盡量避免給用戶帶來(lái)不必要的麻煩；應(yīng)力求簡(jiǎn)單，盡量避免給用戶帶來(lái)不必要的麻煩；交互式輸入數(shù)據(jù)時(shí)應(yīng)有必要的提示信息交互式輸入數(shù)據(jù)時(shí)應(yīng)有必要的提示信息; ; 程序應(yīng)對(duì)輸入數(shù)據(jù)的程序應(yīng)對(duì)輸入數(shù)據(jù)的合法性進(jìn)行檢查合法性進(jìn)行檢查; ;若用戶輸入某些數(shù)據(jù)后可能產(chǎn)生嚴(yán)重后果若用戶輸入某些數(shù)據(jù)后可能產(chǎn)生嚴(yán)重后果, ,應(yīng)應(yīng)給用戶輸出必要的提示并要求用戶確認(rèn)；應(yīng)根據(jù)系統(tǒng)的特點(diǎn)和給用戶輸出必要的提示并要求用戶確認(rèn)；應(yīng)根據(jù)系統(tǒng)的特點(diǎn)和用戶的習(xí)慣設(shè)計(jì)出令用戶滿意的輸入方式。用戶的習(xí)慣設(shè)計(jì)出令用戶滿意的輸入方式。 輸出數(shù)據(jù)的格式輸出數(shù)據(jù)的格式應(yīng)清晰，美觀；輸出數(shù)據(jù)時(shí)要加上必要的應(yīng)清晰，美觀；輸出數(shù)據(jù)時(shí)要加上必