版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、計算機二級公共基礎(chǔ)知識(全)1.1算法考點1算法的基本概念計算機解題的過程實際上是在實施某種算法,這種算法稱為計算機算法。算法(algorithm)是一組嚴謹?shù)刈罅x運算順序的規(guī)則,并且每一個規(guī)則都是有效的,同時 是明確的;此順序?qū)⒃谟邢薜拇螖?shù)后終止。算法是對特泄問題求解步驟的一種描述,它是指 令的有限序列,其中每一條指令表示一個或多個操作。1算法的基本特征可行性(effectiveness):針對實際問題而設(shè)計的算法,執(zhí)行后能夠得到滿意的結(jié)果。 確定性(definiteness):算法中的每一個步驟都必須有明確的泄義,不允許有模棱 兩可的解釋和多義性。(3) 有窮性(finiteness):算
2、法必需在有限時間內(nèi)做完,即算法必需能在執(zhí)行有限個步 驟之后終止。(4) 擁有足夠的情報:要使算法有效必需為算法提供足夠的情報當算法擁有足夠的 情報時,此算法才最有效的;而當提供的情報不夠時,算法可能無效。2算法的基本要素(1) 算法中對數(shù)據(jù)的運算和操作:每個算法實際上是按解題要求從環(huán)境能進行的所 有操作中選擇合適的操作所組成的一組指令序列。計算機可以執(zhí)行的基本操作是以指令的形式描述的。一個訃算機系統(tǒng)能執(zhí)行的所有指令 的集合,稱為該訃算機系統(tǒng)的指令系統(tǒng)。訃算機程序就是按解題要求從計算機指令系統(tǒng)中選 擇合適的指令所組成的指令序列在一般的汁算機系統(tǒng)中,基本的運算和操作有以下4類: 算術(shù)運算:主要包括
3、加、減、乘、除等運算; 邏輯運算:主要包括及”、“或”、“非”等運算: 關(guān)系運算:主要包括“大于”、“小于”、“等于”、“不等于”等運算: 數(shù)據(jù)傳輸:主要包括賦值、輸入、輸出等操作。(2) 算法的控制結(jié)構(gòu):一個算法的功能不僅僅取決于所選用的操作,而且還及各操 作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給岀了算法的基本框架,它不僅決泄了算法中各操作的執(zhí)行順序,而且 也直接反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié) 構(gòu)化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu) 組合而成。(3) 算法設(shè)計的
4、基本方法計算機算法不同于人工處理的方法,下而是工程上常用的幾種算法設(shè)計,在實際應(yīng)用時, 各種方法之間往往存在著一定的聯(lián)系。(1) 列舉法列舉法是計算機算法中的一個基礎(chǔ)算法。列舉法的基本思想是,根據(jù)提岀的問題,列舉 所有可能的情況,并用問題中給泄的條件檢驗?zāi)男┦切枰模男┦遣恍枰?。列舉法的特點是算法比較簡單。但當列舉的可能情況較多時,執(zhí)行列舉算法的工作量將 會很大。因此,在用列舉法設(shè)計算法時,使方案優(yōu)化,盡量減少運算工作量,是應(yīng)該重點注 意的。(2) 歸納法歸納法的基本思想是,通過列舉少量的特殊情況,經(jīng)過分析,最后找岀一般的關(guān)系。從 本質(zhì)上講,歸納就是通過觀察一些簡單而特殊的情況,最后總結(jié)出
5、一般性的結(jié)論。(3) 遞推遞推是指從已知的初始條件岀發(fā),逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初 始條件或是問題本身已經(jīng)給左,或是通過對問題的分析及化簡而確左。遞推本質(zhì)上也屬于歸 納法,工程上許多遞推關(guān)系式實際上是通過對實際問題的分析及歸納而得到的,因此,遞推 關(guān)系式往往是歸納的結(jié)果。對于數(shù)值型的遞推算法必須要注意數(shù)值計算的穩(wěn)定性問題。(4) 遞歸人們在解決一些復(fù)雜問題時,為了降低問題的復(fù)雜程度(如問題的規(guī)模等),一般總是將 問題逐層分解,最后歸結(jié)為一些最簡單的問題。這種將問題逐層分解的過程,實際上并沒有 對問題進行求解,而只是當解決了最后那些最簡單的問題后,再沿著原來分解的逆過程逐步 進
6、行綜合,這就是遞歸的基本思想。遞歸分為直接遞歸及間接遞歸兩種。(5) 減半遞推技術(shù)實際問題的復(fù)雜程度往往及問題的規(guī)模有著密切的聯(lián)系。因此,利用分治法解決這類實 際問題是有效的。工程上常用的分治法是減半遞推技術(shù)。所謂“減半”,是指將問題的規(guī)模減半,而問題的性質(zhì)不變;所謂“遞推”,是指重復(fù)“減 半”的過程。(6) 回溯法在工程上,有些實際問題很難歸納出一組簡單的遞推公式或直觀的求解步驟,并且也不 能進行無限的列舉。對于這類問題,一種有效的方法是試”。通過對問題的分析,找出一 個解決問題的線索,然后沿著這個線索逐步試探,若試探成功,就得到問題的解,若試探失 敗,就逐步回退,換別的路線再逐步試探。4算
7、法設(shè)計的要求通常一個好的算法應(yīng)達到如下目標:正確性(correctness)正確性大體可以分為以下4個層次: 程序不含語法錯誤: 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果: 程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得岀滿足規(guī)格說明要求 的結(jié)果; 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。(2) 可讀性(readability)算法主要是為了方便入的閱讀及交流,其次才是其執(zhí)行??勺x性好有助于用戶對算法的 理解:晦澀難懂的程序易于隱藏較多錯誤,難以調(diào)試和修改。(3) 健壯性(robustness)當輸入數(shù)據(jù)非法時,算法也能適當?shù)刈龀龇磻?yīng)或進行處理,而不會
8、產(chǎn)生莫名其妙的 輸出結(jié)果。(4) 效率及低存儲量需求效率指的是程序執(zhí)行時,對于同一個問題如果有多個算法可以解決,執(zhí)行時間短的 算法效率高;存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間考點2算法的復(fù)雜度1算法的時間復(fù)雜度算法的時間復(fù)雜度,是指執(zhí)行算法所需要的計算工作量。同一個算法用不同的語言 實現(xiàn),或者用不同的編譯程序進行編譯,或者在不同的汁算機上運行,效率均不同。這表明 使用絕對的時間單位衡量算法的效率是不合適的。撇開這些及汁算機硬件、軟件有關(guān)的因素, 可以認為一個特左算法“運行工作量”的大小,只依賴于問題的規(guī)模(通常用整數(shù)n表示), 它是問題的規(guī)模函數(shù)。即算法的工作雖=f(n)例如,在NX
9、N矩陣相乘的算法中,整個算法的執(zhí)行時間及該基本操作(乘法)重復(fù)執(zhí)行 的次數(shù)n3成正比,也就是時間復(fù)雜度為n3,即f(n)=O(n3)在有的情況下,算法中的基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。 例如在尼泡排序的算法中,當要排序的數(shù)組a初始序列為自小至大有序時,基本操作的執(zhí)行 次數(shù)為氏當初始序列為自大至小有序時,基本操作的執(zhí)行次數(shù)為n(n- 1)/2O對這類算法 的分析,可以采用以下兩種方法來分析。(1) 平均性態(tài)(Average Behavior)所謂平均性態(tài)是指各種特立輸入下的基本運算次數(shù)的加權(quán)平均值來度量算法的工作量。設(shè)x是所有可能輸入中的某個特定輸入,p(x)是x出現(xiàn)的槪
10、率(即輸入為x的概率),t(x) 是算法在輸入為x時所執(zhí)行的基本運算次數(shù),則算法的平均性態(tài)泄義為其中Dn表示當規(guī)模為n時,算法執(zhí)行的所有可能輸入的集合。(2)最壞情況復(fù)雜性(Worst-case Complexity)所謂最壞情況分析,是指在規(guī)模為n時,算法所執(zhí)行的基本運算的最大次數(shù)。2算法的空間復(fù)雜度算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間 以及算法執(zhí)行中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及 某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù),則稱該 算法
11、是原地(inplace)工作的。在許多實際問題中,為了減少算法所占的存儲空間,通常采用 壓縮存儲技術(shù),以便盡量減少不必要的額外空間??键c3數(shù)據(jù)結(jié)構(gòu)的泄義數(shù)據(jù)結(jié)構(gòu)(data structure)是指相互之間存在一種或多種特泄關(guān)系的數(shù)據(jù)元素的集合,即 數(shù)據(jù)的組織形式。數(shù)據(jù)結(jié)構(gòu)作為計算機的一門學科,主要研究和討論以下三個方而:數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu):(2) 在對數(shù)據(jù)元素進行處理時,各數(shù)據(jù)元素在計算機中的存儲關(guān)系,即數(shù)據(jù)的存儲 結(jié)構(gòu);(3) 對各種數(shù)據(jù)結(jié)構(gòu)進行的運算。討論以上問題的日的是為了提高數(shù)據(jù)處理的效率,所謂提髙數(shù)據(jù)處理的效率有兩個方 面:提高數(shù)據(jù)處理的速度:
12、(2) 盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機存儲空間。數(shù)據(jù)(data):是對客觀事物的符號表示,在計算機科學中是指所有能輸入到汁算機中并 被計算機程序處理的符號的總稱。數(shù)據(jù)元素(data element):是數(shù)據(jù)的基本單位,在計算機程序中通常作為一個整體進行考 慮和處理。數(shù)據(jù)對象(data object):是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的一個子集。在一般情況下,在具有相同特征的數(shù)據(jù)元素集合中,各個數(shù)拯元素之間存在有某種關(guān)系 (即連續(xù)),這種關(guān)系反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。在數(shù)據(jù)處理領(lǐng)域中,通4 / 35計算機二級公共基礎(chǔ)知識(全)常把數(shù)據(jù)元素之間這種固有的關(guān)系簡單地用前后件
13、關(guān)系(或直接前驅(qū)及直接后繼關(guān)系)來描 述。前后件關(guān)系是數(shù)據(jù)元素之間的一個基本關(guān)系,但前后件關(guān)系所表示的實際意義隨具體對 象的不同而不同。一般來說,數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。1數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的關(guān)系的數(shù)據(jù)元素集合的表示。更通俗地說,數(shù)拯結(jié)構(gòu) 是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。所謂結(jié)構(gòu)實際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方而信息:(1)表示數(shù)據(jù)元素的信息:(2)表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)的邏輯結(jié)果是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述。它可以用一嘎數(shù)據(jù)元素的集合和 定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性
14、結(jié)構(gòu)、樹型結(jié)構(gòu)和圖形結(jié)構(gòu)四種。線性結(jié)構(gòu):數(shù)據(jù)元素之間構(gòu)成一種順序的線性關(guān)系。樹型結(jié)構(gòu):數(shù)據(jù)元素之間形成一種樹型的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素:一是數(shù)據(jù)元素的集合,通常記為D;二是D上的關(guān)系,它 反映了數(shù)據(jù)元素之間的前后件關(guān)系,通常記為R。一個數(shù)據(jù)結(jié)構(gòu)可以表示成B= (C.R)苴中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各元素之間的前后件關(guān)系,一般用二元組來表示。 例如,復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu),在計算機科學中,復(fù)數(shù)可取如下建義:B= (C.R)其中,C是含有兩個實數(shù)的集合cl,c2 :R是泄義在集合C上的一種關(guān)系cl,c2, 其中有序偶cl,c2表示cl是復(fù)數(shù)的實部,c2是復(fù)數(shù)的虛部。2數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯
15、結(jié)構(gòu)在訃算機存儲空間中的存放形式,稱為數(shù)據(jù)的存儲結(jié)構(gòu)(也稱為數(shù)據(jù)的 物理結(jié)構(gòu))。由于數(shù)據(jù)元素在計算機存儲空間中的位置關(guān)系可能及邏輯關(guān)系不同,因此,為了表示存 放在計算機存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系(即前后件關(guān)系),在數(shù)據(jù)的存儲結(jié)構(gòu) 中,不僅要存放各數(shù)據(jù)元素的信息,還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu),常用的結(jié)構(gòu)有順序、鏈接、 索引等存儲結(jié)構(gòu)而采用不同的存儲結(jié)構(gòu),其數(shù)據(jù)處理的效率是不同的。因此,在進行數(shù)據(jù)處 理是,選擇合適的存儲結(jié)構(gòu)是很重要的。考點4數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外,還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的
16、圖形表示中,對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的 方框表示,一般稱之為數(shù)據(jù)結(jié)點,并簡稱為結(jié)點;為了進一步表示各數(shù)據(jù)元素之間的前后件 關(guān)系,對于關(guān)系R中的每一個二元組,用一條有向線段從前件結(jié)點指向后件結(jié)點。在數(shù)據(jù)結(jié)構(gòu)中,沒有前件的結(jié)點稱為根結(jié)點;沒有后件的結(jié)點稱為終端結(jié)點(也稱 為葉子結(jié)點)。一個數(shù)據(jù)結(jié)構(gòu)中的結(jié)點可能是在動態(tài)變化的。根據(jù)需要或在處理過程中,可以在一個數(shù) 據(jù)結(jié)構(gòu)中增加一個新結(jié)點(稱為插入運算),也可以刪除數(shù)據(jù)結(jié)構(gòu)中的某個結(jié)點(稱為刪除運 算)。插入及刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運算。除此之外,對數(shù)據(jù)結(jié)構(gòu)的運算還有查找、 分類、合并、分解、復(fù)制和修改等??键c5線性結(jié)構(gòu)及非
17、線性結(jié)構(gòu)如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有,則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。5 / 35計算機二級公共基礎(chǔ)知識(全)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度,一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類 型:線性結(jié)構(gòu)及非線性結(jié)構(gòu)。非空數(shù)據(jù)結(jié)構(gòu)滿足:有且只有一個根結(jié)點:(2) 每一個結(jié)點最多有一個前件,也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱為線性表。一個線性表是n個數(shù)據(jù)元 素的 有限序列。至于每個元素的具體含義,在不同的情況下各不相同,它可以是一個數(shù)或一個符 號,也可以是一頁書,甚至英他更復(fù)雜的信息。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu),稱之為非 線性結(jié)構(gòu)。線性結(jié)構(gòu)及非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)
18、構(gòu)。對于空的數(shù)據(jù)結(jié)構(gòu),如果對該數(shù) 拯結(jié)構(gòu)的運算是按線性結(jié)構(gòu)的規(guī)則來處理的,則屬于線性結(jié)構(gòu):否則屬于非線性結(jié)構(gòu)。1.3線性表及順序存儲結(jié)構(gòu)考點6線性表的泄義線性表是n(n0)個元素構(gòu)成的有限序列(al, a2,,an)。表中的每一個數(shù)據(jù)元素,除 了第一個外,有且只有一個前件,除了最后一個外,有且只有一個后件。即線性表是一個空 表,或可以表示為(al, a2,,an)貝中ai(i=l, 2,n)是屬于數(shù)據(jù)對象的元素,通常也稱其為線性表中的一個結(jié)點。貝中,每個元素可以簡單到是一個字母或是一個數(shù)據(jù),也可能是比較復(fù)雜的由多個數(shù)據(jù) 項組成的。在復(fù)雜的線性表中,由若T數(shù)據(jù)項組成的數(shù)據(jù)元素稱為記錄(recor
19、d),而由多個 記錄構(gòu)成的線性表又稱為文件(file)。在非空表中的每個數(shù)據(jù)元素都有一個確左的位苣,如 al是第一個元素,an是最后一個數(shù)據(jù)元素,ai是第i個數(shù)據(jù)元素,稱i為數(shù)據(jù)元素ai在線 性表中的位序。非空線性表有如下一些結(jié)構(gòu)特征:(1) 有且只有一個根結(jié)點al,它無前件:(2) 有且只有一個終端結(jié)點an,它無后件;(3) 除根結(jié)點及終端結(jié)點外,其他所有結(jié)點有且只有一個前件,也有且只有一個后件。線 性表中結(jié)點的個數(shù)n稱為線性表的長度。當n=0時稱為空表。考點7線性表的順序存儲結(jié)構(gòu)線性表的順序表指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)拯元素。線性表的順序存儲結(jié)構(gòu)具備如下兩個基本特征:
20、線性表中的所有元素所占的存儲空間是連續(xù)的:(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。假設(shè)線性表的每個元素需要占用k個存儲單元,并以所占的存儲位置ADR(ai+l)和第i 個數(shù)據(jù)元素的存儲位置ADR(ai)之間滿足下列關(guān)系:ADR(ai+l)=ADR(ai)+k線性表第i個元素ai的存儲位置為ADR(ai)=ADR(a 1 )+(i-l)Xk式中ADR(ai)是線性表的第一個數(shù)據(jù)元素a,的存儲位巻,通常稱做線性表的起始位巻 或基址。線性表的這種表示稱做線性表的順序存儲結(jié)構(gòu)或順序映像,這種存儲結(jié)構(gòu)的線性表為順 序表。表中每一個元素的存儲位巻都和線性表的起始位置相差一個和數(shù)據(jù)元素在
21、線性表中的 位序成正比例的常數(shù)。如圖1-4所示。由此只要確圧了存儲線性表的起始位置,線性表中任 一數(shù)據(jù)元素都可以隨機存取,所以線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)。 在程序設(shè)計語言中,通常泄義一個一維數(shù)組來表示線性表的順序存儲空間。在用一維數(shù)組存 放線性表時,該一維數(shù)組的長度通常要徒義得比線性表的實際長度大一些,以便對線性表進 行各種運算,特別是插入運算。任線性表的順序存儲結(jié)構(gòu)下,可以對線性表做以下運算:(1) 在線性表的指建位置處加入一個新的元素(即線性表的插入):(2) 在線性表中刪除指左的元素(即線性表的刪除);(3) 在線性表中査找某個(或某些)特左的元素(即線性表的查找):(
22、4) 對線性表中的元素進行整序(即線性表的排序);(5) 按要求將一個線性表分解成多個線性表(即線性表的分解):(6) 按要求將多個線性表合并成一個線性表(即線性表的合并);(7) 復(fù)制一個線性表(即線性表的復(fù)制):(8) 逆轉(zhuǎn)一個線性表(即線性表的逆轉(zhuǎn))等??键c8順序表的插入運算線性表的插入運算是指在表的第i(lWiWn+l)個位置上,插入一個新結(jié)點x,使長度為n 的線性表(al, ,ai-1, ai, ,an)變成長度為n+1的線性表(al,,ai-1, x, ait ,an)現(xiàn)在分析算法的復(fù)雜度。這里的問題規(guī)模是表的長度,設(shè)它的值為嘰該算法的時間主 要花費在循環(huán)結(jié)點后移語句上,該語句的執(zhí)
23、行次數(shù)(即移動結(jié)點的次數(shù))是n-i+lo由此可看 岀,所需移動結(jié)點的次數(shù)不僅依賴于表的長度,而且還及插入位置有關(guān)。當上n+1時,由于循環(huán)變呈:的終值大于初值,結(jié)點后移語句將不進行:這是最好情況, 其時間復(fù)雜度0(1);當i=l時,結(jié)點后移語句,將循環(huán)執(zhí)行n次,需移動表中所有結(jié)點,這是最壞情況,苴 時間復(fù)雜度為0(n)。由于插入可能在表中任何位置上進行,因此需分析算法的平均復(fù)雜度。在長度為n的線性表中第i個位宜上插入一個結(jié)點,令Eis ( n )表示移動結(jié)點的期望值(即 移動的平均次數(shù)),則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+K故 不失一般性,假設(shè)在表中任何位置(lWiWn+1)上插入
24、結(jié)點的機會是均等的,則pl=p2=p3=. ,=pn*l=l/(n+l)因此,在等概率插入的情況下,也就是說,在順序表上做插入運算,平均要移動表上一半的結(jié)點。當表長n較大時,算 法的效率相當?shù)汀km然Eis ( n )中n的的系數(shù)較小,但就數(shù)量級而言,它仍然是線性級的。 因此算法的平均時間復(fù)雜度為O(n)??键c9順序表的刪除運算線性表的刪除運算是指將表的第i(liWn)個結(jié)點刪除,使長度為n的線性表:(al, ,ai-1, ai, ai+1, ,an)變成長度為n-1的線性表(al ,ai-1 ai+1 ,an)該算法的時間分析及插入算法相似,結(jié)點的移動次數(shù)也是由表長n和位垃i決泄。若i=n,
25、則由于循環(huán)變量的初值大于終值,前移語句將不執(zhí)行,無需移動結(jié)點:若上1,則前移語句 將循環(huán)執(zhí)行n1次,需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復(fù)雜 度分別為0(1)和0(n)。刪除算法的平均性能分析及插入算法相似。在長度為n的線性表中刪除一個結(jié)點,令 Ede(n)表示所需移動結(jié)點的平均次數(shù),刪除表中第i個結(jié)點的移動次數(shù)為n-i,故式子中,pi表示刪除表中第i個結(jié)點的概率。在等概率的假設(shè)下,p 1 =p2=p3=. =pn= 1 /n由此可得:即在順序表上做刪除運算,平均要移動表中約一半的結(jié)點,平均時間復(fù)雜度也是0(n)。1.4棧和隊列考點10棧及其基本運算1什么是棧棧實際也是線性
26、表,只不過是一種特殊的線性表。棧(Stack)是只能在表的一端進行插入 和刪除運算配線性表,通常稱插入、刪除的這一端為棧頂(Top),另一端為棧底(Bottom)o當 表中沒有元素時稱為空棧(棧頂元素總是后被插入的元素,從而也是最先被刪除的元素:棧 底元素總是最先被插入的元素,從而也是最后才能被刪除的元素。假設(shè)棧S=(al, a2, a3,,an),則al,稱為棧底元素,an為棧頂元素。棧中元素按 al, a2, a3,,an的次序進棧,退棧的第一個元素應(yīng)為棧頂元素。換句話說,棧的修改是 按后進先出的原則進行的。因此,棧稱為先進后岀表(FILO, First In Last Out),或“后進
27、先 出”表(LIFO, Last In First Out),如圖 1-7 所示。2棧的順序存儲及其運算(1) 入棧運算:入棧運算是指在棧頂位垃插入一個新元素。首先將棧頂指針加一(即 top加1),然后將元素插入到棧頂指針指向的位置。當棧頂指針已經(jīng)指向存儲空間的最后一 個位巻時,說明??臻g已滿,不可能再進行入棧操作。這種情況稱為棧上溢”錯誤。如圖 1-8所示。(2) 退棧運算:退棧是指取出棧頂元素并賦給一個指泄的變量。首先將棧頂元素(棧頂指針指向的元素)賦給一個指定的變量,然后將棧頂指針減一(即t叩減1)。當棧頂指針為。 時,說明???,不可進行退棧操作。這種情況稱為棧的“下溢”錯誤。(3)讀棧
28、頂元素:讀棧頂元素是指將棧頂元素賦給一個指泄的變量。這個運算不刪除棧頂元素,只是將 它賦給一個變量,因此棧頂指針不會改變。當棧頂指針為0時,說明???,讀不到棧頂元素。 考點11隊列及其基本運算1什么是隊列隊列(queue)是只允許在一端刪除,在另一端插入的順序表,允許刪除的一端叫做隊頭 (front),允許插入的一端叫做隊尾(rear),當隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素al, a2,,an之后, al是隊頭元素,an是隊尾元素。顯然退岀隊列的次序也只能是al, a2,,an也就是說隊 列的修改是依先進先出的原則進行的。因此隊列亦稱作先進先出(HFO, First In Fi
29、rst Out)的 線性表,或后進后出(LILO, Last In Last Out)的線性表。往隊列隊尾插入一個元素稱為入隊 運算,從隊列的排頭刪除一個元素稱為退隊運算,如圖1-10所示。一個隊列幣。刪除個兒素后的隊列間插入元素E后的隊列2循環(huán)隊列及其運算在實際應(yīng)用中,隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。所謂循環(huán)隊列,就是將 隊列存儲空間的最后一個位垃繞到第一個位巻,形成邏輯上的環(huán)狀空間在循環(huán)隊列中,用隊尾指針rear指向隊列中的隊尾元素,用排頭指針front指向排頭 元素的前一個位置。因此,從排頭指針from指向的后一個位置直到隊尾指針rear指向的位 置之間所有的元素均為隊列中的元
30、素??梢詫⑾蛄靠臻g想象為一個首尾相接的圓環(huán),如圖1-12所示,并稱這種向量為循環(huán)向 量,存儲在英中的隊列稱為循環(huán)隊列(Circular Queue)。在循環(huán)隊列中進行岀隊、入隊操作時, 頭尾指針仍要加1,朝前移動。只不過當頭尾指針指向向量上界(Qucuesize-1)時,英加1操 作的結(jié)果是指向向量的下界0。由于入隊時尾指針向前追趕頭指針,出隊時頭指針向前追趕尾指針,故隊空和隊滿時頭 屋指針均相等。因此,我們無法通過fronArcar來判斷隊列“空”還是“滿”。在實際使用循環(huán)隊列時,為了能區(qū)分隊列滿還是隊列空,通常還需增加一個標志、,、值 的定義如下:當s=0時表示隊列空:當s=l時表示隊列非
31、空。入隊運算入隊運算是指在循環(huán)隊列的隊尾加入一個新元素。首先將隊尾指針進一(即rear=rear+l), 并當rear=m+l時置rcar=l:然后將新元素插入到隊尾指針指向的位置。當循環(huán)隊列非空(s=l) 且隊尾指針等于隊頭指針時,說明循環(huán)隊列已滿,不能進行入隊運算,這種情況稱為“上溢”。 (2)退隊運算退隊運算是指在循環(huán)隊列的隊頭位置退岀一個元素并賦給指左的變量。首先將隊頭指針 一進一(即from=front +1),并當front = m+1時,it front=l然后將排頭指針指向的元素賦給 指泄的變量。當循環(huán)隊列為空(s =0)時,不能進行退隊運算,這種情況稱為下溢”。轉(zhuǎn)貼于: 計算
32、機二級考址考試大【責編:daiy糾錯】1.5線性鏈表考點12線性單鏈表的結(jié)構(gòu)及其基本運算1什么是線性鏈表線性表順序存儲的缺點 在一般情況下,要在順序存儲的線性表中插入一個新元素或刪除一個元素時,為了保證插 入或刪除后的線性表仍然為順序存儲,則在插入或刪除過程中需要移動大量的數(shù)據(jù)元素。因 此采用順序存儲結(jié)構(gòu)進行插入或刪除的運算效率很低: 當為一個線性表分配順序存儲空間后,如果岀現(xiàn)線性表的存儲空間已滿,但還需要插入新 的元素時棧會發(fā)生“上溢”錯誤: 計算機空間得不到充分利用,并且不便于對存儲空間的動態(tài)分配。(2) 線性表鏈式的基本概念在左義的鏈表中,若只含有一個指針域來存放下一個元素地址,稱這樣的
33、鏈表為單鏈表 或線性鏈表。在鏈式存儲方式中,要求每個結(jié)點由兩部分組成:一部分用于存放數(shù)據(jù)元素值,稱為數(shù) 拯域:列一部分用于存放指針,稱為指針域。其中指針用于指向該結(jié)點的前一個或后一個結(jié) 點(即前件或后件)。如圖1-13所示。2線性單鏈表的存儲結(jié)構(gòu)用一組任意的存儲單元來依次存放線性表的結(jié)點,這組存儲單元既可以是連續(xù)的,也可 以是不連續(xù)的,甚至是零散分布在內(nèi)存中的任意位置上的。因此,鏈表中結(jié)點的邏輯次序和 物理次序不一左相同。為了能正確表示結(jié)點間的邏輯關(guān)系,在存儲每個結(jié)點值的同時,還必 須存儲指示其后件結(jié)點的地址(或位巻)信息,這個信息稱為指針(pointer)或鏈(link)。這兩部 分組成了鏈
34、表中的結(jié)點結(jié)構(gòu),鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起。由于上述 鏈表的每一個結(jié)點只有一個鏈域,故將這種鏈表稱為單鏈表(Single Linked)o顯然,單鏈表中每個結(jié)點的存儲地址是存放在其前驅(qū)結(jié)點Next域中,而開始結(jié)點無前 驅(qū),故應(yīng)設(shè)頭指針HEAD指向開始結(jié)點。同時,由于終端結(jié)點無后件,故終端結(jié)點的指針 域為空,即NULL。3帶鏈的棧及隊列(1) 棧也是線性表,也可以采用鏈式存儲結(jié)構(gòu)。在實際應(yīng)用中,帶鏈的??梢杂脕硎?集汁算機存儲空間中所有空閑的存儲結(jié)點,這種帶鏈的棧稱為可利用棧(2) 隊列也是線性表,也可以采用鏈式存儲結(jié)構(gòu), 考點13線性鏈表的基本運算線性鏈
35、表的運算主要有以下幾個:在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素;(2) 在線性鏈表中刪除包含指定元素的結(jié)點;(3) 將兩個線性鏈表按要求合并成一個線性表:(4) 將一個線性鏈表按要求進行分解;(5) 逆轉(zhuǎn)線性鏈表:(6) 復(fù)制線性鏈表:(7) 線性鏈表的排序:(8) 線性鏈表的査找。1在線性鍍表中査找指定元素在對線性鏈表進行插入或刪除的運算中,總是首先需要找到插入或刪除的位垃,這就需 要對線性鏈表進行掃描查找,在線性鏈表中尋找包含指左元素的前一個結(jié)點。在線性鏈表中,即使知道被訪問結(jié)點的序號a,也不能像順序表中那樣直接按序號i訪 問結(jié)點,而只能從鏈表的頭指針出發(fā),順鏈域Next逐個結(jié)點
36、往下搜索,直到搜索到第i個 結(jié)點為止。因此,鏈表不是隨機存取結(jié)構(gòu)。在鏈表中,査找是否有結(jié)點值等于給左值x的結(jié)點,若有的話,則返回首次找到的其值 為x的結(jié)點的存儲位置:否則返回NULL。查找過程從開始結(jié)點出發(fā),順著鏈表逐個將結(jié)點 的值和給定值x作比較。2線性鏈表的插入線性鏈表的插入是指在鏈式存儲結(jié)構(gòu)下的線性鏈表中插入一個新元素。插入運算是將值為X的新結(jié)點插入到表的第i個結(jié)點的位置上,即插入到ai-1,及ai 之間。因此,我們必須首先找到ai-l的存儲位置p,然后生成一個數(shù)據(jù)域為x的新結(jié)點*p, 并令結(jié)點,p的指針域指向新結(jié)點,新結(jié)點的指針域指向結(jié)點ai由線性鏈表的插入過程可以看岀,由于插入的新結(jié)
37、點取自于可利用棧,因此,只要可利 用棧不空,在線性鏈表插入時總能取到存儲插入元素的新結(jié)點,不會發(fā)生“上溢”的情況。 而且,由于可利用棧是公用的,多個線性鏈表可以共享它,從而很方便地實現(xiàn)了存儲空間的 動態(tài)分配。另外,線性鏈表在插入過程中不發(fā)生數(shù)據(jù)元素移動的現(xiàn)象,只要改變有關(guān)結(jié)點的 指針即可,從而提髙了插入的效率。3多線性鏈表的刪除線性鏈表的刪除是指在鏈式存儲結(jié)構(gòu)下的線性鏈表中刪除包含指泄元素的結(jié)點。刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點a的存儲地址是在英直接前趨 結(jié)點ai-1,的指針域Next中,所以我們必須首先找到ai-1的存儲位置p。然后令p-Next 指向ai的直接后件結(jié)點,即
38、把ai從鏈上摘下。最后釋放結(jié)點a的空間。從線性鏈表的刪除過程可以看出,從線性鏈表中刪除一個元素后,不需要移動表中的數(shù) 據(jù)元素,只要改變被刪除元素所在結(jié)點的前一個結(jié)點的指針域即可。另外,由于可利用棧是 用于收集汁算機中所有的空閑結(jié)點,因此,當從線性鏈表中刪除一個元素后,該元素的存儲 結(jié)點就變?yōu)榭臻e,應(yīng)將空閑結(jié)點送回到可利用棧??键c14線性雙向鏈表的結(jié)構(gòu)及其基本運算1什么是雙向鏈表在單鏈表中,從某個結(jié)點出發(fā)可以直接找到它的直接后件,時間復(fù)雜度為0(1),但無 法直接找到它的互接前件;在單循環(huán)鏈表中,從某個結(jié)點岀發(fā)可以直接找到它的直接后件, 時間復(fù)雜度仍為0(1),直接找到它的直接前件,時間復(fù)雜度為
39、0(n)。有時,希望能快速找 到一個結(jié)點的直接前件,這時,可以在單鏈表中的結(jié)點中增加一個指針域指向它的直接前件, 這樣的鏈表,就稱為雙向鏈表(一個結(jié)點中含有兩個指針)。如果每條鏈構(gòu)成一個循環(huán)鏈表, 則會得到雙向循環(huán)鏈表2雙向鏈表的基本運算插入:在HEAD為頭指針的雙向鏈表中,在值為Y的結(jié)點之后插入值為X的結(jié)點, 插入結(jié)點的指針變化。如圖1-20所示(若改為在值為Y的結(jié)點之前插入值為X的結(jié)點,可 以做類似分析)。(2)刪除:在以HEAD為頭指針的雙向鏈表中刪除值為X的結(jié)點,刪除算法的指針變 化,如圖1-21所示。考點15循環(huán)鏈表的結(jié)構(gòu)及其基本運算單鏈表上的訪問是一種順序訪問,從其中的某一個結(jié)點出
40、發(fā),可以找到它的直接后件, 但無法找到它的直接前件。在前而所討論的線性鏈表中,其插入及刪除的運算雖然比較方便,但還存在一個問題, 在運算過程中對于空表和對第一個結(jié)點的處理必須單獨考慮,使空表及非空表的運算不統(tǒng)因此,我們可以考慮建立這樣的鏈表,具有單鏈表的特征,但又不需要增加額外的存貯 空間,僅對表的鏈接方式稍做改變,使得對表的處理更加方便靈活。從單鏈表可知,最后一 個結(jié)點的指針域為NULL,表示單鏈表已經(jīng)結(jié)朿。如果將單鏈表最后一個結(jié)點的指針域改為 存放鏈表中頭結(jié)點(或第一個結(jié)點)的地址,就使得整個鏈表構(gòu)成一個環(huán),又沒有增加額外的 存儲空間 循環(huán)鏈表具有以下兩個特點:(1) 在循環(huán)鏈表中增加了一
41、個表頭結(jié)點,其數(shù)據(jù)域為任意或者根據(jù)需要來設(shè)置,指針域 指向線性表的第一個元素的結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點;(2) 循環(huán)鏈表中最后一個結(jié)點的指針域不是空,而是指向表頭結(jié)點。即在循環(huán)鏈表中, 所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。在循環(huán)鏈表中,只要指出表中任何一個結(jié)點的位置,就可以從它出發(fā)訪問到表中其他所 有的結(jié)點,而線性單鏈表做不到這一點。由于在循環(huán)鏈表中設(shè)置了一個表頭結(jié)點,因此,在任何情況下,循環(huán)鏈表中至少有一個 結(jié)點存在,從而使空表的運算統(tǒng)一。1.6樹及二叉樹考點16樹的定義樹是由n(nO)個結(jié)點組成的有限集合。若n =0,稱為空樹:若n0,貝嘰 有一個特左的稱為根(root)的結(jié)點。它只
42、有直接后件,但沒有直接前件: (2)除根結(jié)點以外的貝他結(jié)點可以劃分為m(mO)個互不相交的有限集合TO,T1,,Tm-1,每個集合Ti(i=0, 1,,in-1)又是一棵樹,稱為根的子樹,每棵子樹的根 結(jié)點有且僅有一個直接前件,但可以有0個或多個直接后件。樹型結(jié)構(gòu)具有如下特點:(1) 助每個結(jié)點只有一個前件,稱為父結(jié)點,沒有前件的結(jié)點只有一個,稱為樹的 根結(jié)點,簡稱為樹的根;(2) 每一個結(jié)點可以有多個后件,它們都稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱 為葉子結(jié)點:12 / 35計算機二級公共基礎(chǔ)知識(全)(3) 個結(jié)點所擁有的后件個數(shù)稱為樹的結(jié)點度:(4) 樹的最大層次稱為樹的深度。在計算機中
43、,可以用樹結(jié)構(gòu)來表示算術(shù)表達式,用樹來表示算術(shù)表達式的原則是:(1) 表達式中的每一個運算符在樹中對應(yīng)一個結(jié)點,稱為運算符結(jié)點:(2) 運算符的每一個運算對象在樹中為該運算符結(jié)點的子樹(在樹中的順序為從左到 右);(3) 運算對象中的單變量均為葉子結(jié)點。樹在計算機中通常用多重鏈表表示??键c17二叉樹的立義及苴基本性質(zhì)1什么是二叉樹二叉樹(binary tree)是由n(NO)個結(jié)點的有限集合構(gòu)成,此集合或者為空集,或者由一個 根結(jié)點及兩棵互不相交的左右子樹組成,并且左右子樹都是二叉樹。二叉樹可以是空集合, 根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況,它們是兩個概念。二叉樹具有如下兩
44、個特點:(1) 非空二叉樹只有一個根結(jié)點:(2) 每一個結(jié)點最多有兩棵子樹,且分別稱為該結(jié)點的左子樹及右子樹。二叉樹的每個結(jié)點最多有兩個孩子,或者說,在二叉樹中,不存在度大于2的結(jié)點,并 且二叉樹是有序樹(樹為無序樹),英子樹的順序不能顛倒,因此,二叉樹有5種不同的形態(tài) 在二叉樹中,一個結(jié)點可以只有左子樹而沒有右子樹,也可以只有右子樹而沒有左子 樹。當一個結(jié)點既沒有左子樹也沒有右子樹時,該結(jié)點即是葉子結(jié)點)2二叉樹的基本性質(zhì)性質(zhì)1:在二叉樹的第入層上至多有2k-l個結(jié)點(k21)。性質(zhì)2:深度為m的二叉樹至多有2m-1個結(jié)點。深度為m的二叉樹的最大的結(jié)點數(shù)是為二叉樹中每層上的最大結(jié)點數(shù)之和,由
45、性質(zhì)1 得到最大結(jié)點數(shù)。性質(zhì)3:對任何一棵二叉樹,度為0的結(jié)點(即葉子結(jié)點)總是比度為2的結(jié)點多一個。 如果葉子結(jié)點nO,度為2的結(jié)點數(shù)為n2,則nO=n2+L設(shè)二叉樹中度為1的結(jié)點數(shù)為nl,二叉樹中總結(jié)點數(shù)為N,因為二叉樹中所有結(jié)點均 小于或等于2,所以有N=nO+nl+n (1)再看二叉樹中的分支數(shù),除根結(jié)點外,其余結(jié)點都有一個進入分支,設(shè)m為二叉樹中 的分支總數(shù),則有N=m+1(2)又由于二叉樹中這m個分支是分別由非葉子結(jié)點射出的。其中度為1的每個結(jié)點射岀1 個分支,度為2的每個結(jié)點射岀2個分支。因此,二叉樹中所有度為1及度為2的結(jié)點射岀 的分支總數(shù)為nl+2n2 ,而在二叉樹中,總的射
46、出分支數(shù)應(yīng)及總的進入分支數(shù)相等,即ni=n 1 +2n2(3)將代入式有N=nl+2n2+l比較和并化簡得nO=n2+l性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度至少為log2n+ 1,其中l(wèi)og2n表示Iog2n的 整數(shù)部分。3滿二叉樹及完全二叉樹滿二叉樹滿二叉樹是指這樣的一種二叉樹:除最后一層外,每一層上的所有結(jié)點都有兩個子結(jié)點。 深度為k的二叉樹具有2k-l個結(jié)點。即在滿二叉樹的第k層上有2k-l個結(jié)點。從上而滿二叉樹泄義可知,必須是二叉樹的每一層上的結(jié)點數(shù)都達到最大,否則就不是 滿二叉樹。深度為m的滿二叉樹有個結(jié)點。(2)完全二叉樹完全二叉樹是指這樣的二叉樹:除最后一層外,每一層上的結(jié)點數(shù)
47、均達到最大值;在最 后一層上只缺少右邊的若干結(jié)點。轉(zhuǎn)貼于:計算機二級考試一考試大【責編:daiy糾錯】 如果一棵具有n個結(jié)點的深度為k的二叉樹,它的每一個結(jié)點都及深度為k的滿二叉樹中編 號為ln的結(jié)點一一對應(yīng)。為滿二叉樹和完全二叉樹的結(jié)構(gòu)比較。從完全二叉樹立義可知,結(jié)點的排列順序遵循從上到下、從左到右的規(guī)律。所謂從上到 下,表示本層結(jié)點數(shù)達到最大后,才能放入下一層。從左到右,表示同一層結(jié)點必須按從左 到右排列,若左邊空一個位巻時不能將結(jié)點放入右邊。完全二叉樹除最后一層外每一層的結(jié) 點數(shù)都達到最大值,最后一層只缺少右邊的若干結(jié)點。滿二叉樹也是完全二叉樹,反之完全二叉樹不一泄是滿二叉樹。性質(zhì)5:具
48、有n個結(jié)點的完全二叉樹深度為log2n+ 1或log2(n+l)o性質(zhì)6:如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號(從第1層到第log2n+l 層,每層從左到右),則對任一結(jié)點i(lWiWn),有:(1) 如果i=l,則結(jié)點i無雙親,是二叉樹的根:如果il,則苴雙親是結(jié)點i/2;(2) 如果2iWn,則結(jié)點i為葉子結(jié)點,無左孩子:否則,英左孩子是結(jié)點2i;(3) 如果2i+lWn,則結(jié)點i無右孩子:否則,其右孩子是結(jié)點2i+lo4二叉樹的存儲結(jié)構(gòu)在計算機中,二叉樹通常采用鏈式存儲結(jié)構(gòu)。用于存儲二叉樹中各元素的存儲結(jié)點由兩 部分組成:數(shù)據(jù)域及指針域。但在二叉樹中,由于每一個元素可以有兩個
49、后件(兩個子結(jié)點), 因此,用于存儲二叉樹的存儲結(jié)點的指針域有兩個:一個用于指向該結(jié)點的左子結(jié)點的存儲 地址,稱為左指針域:另一個用于指向該結(jié)點的右子結(jié)點的存儲地址,稱為右指針域。 考點18二叉樹的遍歷所謂遍歷二叉樹,就是遵從某種次序,訪問二叉樹中的所有結(jié)點,使得每個結(jié)點僅被訪 問一次。1前序遍歷前序遍歷是指在訪問根結(jié)點、遍歷左子樹及遍歷右子樹這三者中,首先訪問根結(jié)點,然 后遍歷左子樹,最后遍歷右子樹;并且,在遍歷左右子樹時,仍然先訪問根結(jié)點,然后遍歷 左子樹,最后遍歷右子樹。前序遍歷描述為:若二叉樹為空,則執(zhí)行空操作。否則:訪問根結(jié)點:前序遍歷左子樹:前序遍歷 右子樹。2中序遍歷中序遍歷是指
50、在訪問根結(jié)點、遍歷左子樹及適歷右子樹這三者中,首先遍歷左子樹,然 后訪間根結(jié)點,最后迪歷右子樹;并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后訪 問根結(jié)點,最后遍歷右子樹。中序遍歷描述為:若二叉樹為空,則執(zhí)行空操作。否則:中序遍歷左子樹;訪問根結(jié)點;中序遍歷 右子樹。3后序遍歷15 / 35計算機二級公共基礎(chǔ)知識(全)后序遍歷是指在訪問根結(jié)點、遍歷左子樹及遍歷右子樹這三者中,首先遍歷左子樹,然 后遍歷右子樹,最后訪問根結(jié)點,并且,在遍歷左、右子樹時,仍然先遍歷左子樹,然后遍 歷右子樹,最后訪問根結(jié)點。后序遍歷描述為:若二叉樹為空,則執(zhí)行空操作。否則:后序遍歷左子樹;后序遍歷右子樹:訪問 根結(jié)
51、點第2章程序設(shè)計基礎(chǔ)2. 1程序設(shè)計方法及風格就程序設(shè)訃方法和技術(shù)的發(fā)展而言,主要經(jīng)過了結(jié)構(gòu)化程序設(shè)計和而向?qū)ο蟮某绦蛟O(shè)計 階段。一般來講。程序設(shè)計風格是指編寫程序時所表現(xiàn)出的特點、習慣和邏輯思路。程序是由 人來編寫的,為了測試和維護程序,往往還要新聞記者和跟蹤程序,因此程序設(shè)計的風格總 體而言應(yīng)該強調(diào)得意和淸晰,程序必須是可以理解的。要形成良好的程序設(shè)計風格,主要應(yīng)注重和考慮下述一些因素。1、源程序文檔化2、源程序文檔化應(yīng)考慮如下幾點:(1)符號劃的命需:符號劣的命飲應(yīng)具有一上的實際含義,以便于對程序功能的理解。(2)程序注釋:下克的注釋能夠幫助讀者理解程序。(3)禮堂組織:為使程序的結(jié)構(gòu)一
52、目了然,可以在程序中利用空格、空行、縮進待技 巧使程序?qū)哟螠[晰。2、數(shù)據(jù)說明的方法在編寫程序時,需要注意數(shù)據(jù)說明的風格,以便使程序中的數(shù)據(jù)說明更易于理解和維護。 一般應(yīng)注意如下幾點:(1)數(shù)據(jù)說明的次序規(guī)范化鑒于程序理解、新聞記者和維護的需要,使數(shù)據(jù)說明次序固左,可以使數(shù)拯的發(fā)生容易查找,也有利于測試、排錯和維護。(2)說明語句中變量安排有序化。當一個說明語句說明多個變量時,變量按照字母順序為好。(3)使用注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)。3、語句的結(jié)構(gòu)程序應(yīng)該簡單易懂,語句構(gòu)造應(yīng)該簡單直接,不應(yīng)該為提高效率而把語句復(fù)雜化。一般應(yīng)注意如下:(1)在一行內(nèi)只寫一條語句:(2)程序編寫應(yīng)優(yōu)先考慮淸晰性;(
53、3)除非對效率有特殊要求,程序編寫要做淸晰第一,效率第二:(4)首先要保證程序正確,然后才要求提髙速度:(5)避免使用臨時變量而使程序的可讀性下降;(6)避免不必要的轉(zhuǎn)移;(7)盡可能使用庫函數(shù);(8)避免采用復(fù)雜的條件語句:(9)盡量減少使用“否左”條件的條件語句:(10)數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化:(11)要模塊化,使模塊功能盡可能單一化:(12)利用住處隱蔽,確保每一個模塊的獨立性;(13)從數(shù)據(jù)出發(fā)去構(gòu)造程序:(14)不要修補不好的程序,要重新編寫;4、輸入和輸岀無論是批處理的輸入和輸出方式,還是交互式的輸入和輸岀方式,在設(shè)訃和編程時都應(yīng) 該考慮如下原則:(1)對所有的輸入數(shù)據(jù)都要檢驗
54、數(shù)據(jù)的合法性;(2)檢查輸入項的各種重要組合的合理性;(3)輸入格式要簡單,以使得輸入的步驟和操作盡可能簡單:(4)輸入數(shù)據(jù)時,應(yīng)允許使用自由格式:(5)應(yīng)允許缺省值;(6)輸入一批數(shù)據(jù)時,最好使用輸入結(jié)束標志:(7)在以交互式輸入/輸出方式進行輸入時,要在屏幕上使用提示符明確提示輸入 的請求,同時在數(shù)據(jù)輸入過程中的輸入結(jié)束時,應(yīng)在屏幕上給岀狀態(tài)信息。(8)當程序設(shè)計語言對輸入格式有嚴格要求時,應(yīng)保持輸入格式及輸入語句的一 致性:給所有的輸入出加注釋,并設(shè)計輸出報表格式。2. 2結(jié)構(gòu)化程序設(shè)計一、結(jié)構(gòu)化程序設(shè)計的原則結(jié)構(gòu)化程序設(shè)計方法的主要原則可以槪括為自頂向下,逐步求精,模塊化,限制使用 g
55、oto語句。1、自頂向下:程序設(shè)計時,應(yīng)先考慮總體,后考慮細節(jié):先考慮全局目標,后考慮 局部目標。不要一開始就過多追求眾多的細盯,先從最上層總目標開始設(shè)計,逐步使問題具 體化。2、逐步求精:對復(fù)雜問題,應(yīng)設(shè)計一些子目標作過渡,逐步細化。3、模塊化:一個復(fù)雜問題,肯泄是由若干稍簡單的問題構(gòu)成。模塊化是把程序要解 決的總目標分解為分目標,再進一步分解為具體的小目標,把每個小目標稱為一個模塊。4、限制使用goto語句使用goto語句經(jīng)實驗證實:(1)濫用GOTO語句確實有害,應(yīng)晝避免:(2)完全避免使用GOTO語句也并非是個明智的方法,有些地方使用GOTO語句,會 使程序流程更淸楚、效率更高:(3)
56、爭論的焦點不應(yīng)該放在是否取消GOTO語句,而應(yīng)該放在用什么樣的程序結(jié)構(gòu)上。 英中最關(guān)鍵的是,肯泄以提髙程序淸晰性為目標的結(jié)構(gòu)化方法。二、結(jié)構(gòu)化程序的基本結(jié)構(gòu)及特點1、順序結(jié)構(gòu):順序結(jié)構(gòu)是簡單的程序設(shè)計,它是最基本、最常用的結(jié)構(gòu),所謂順序執(zhí) 行,就是按照程序語句行的自然順序,一條語句一條語句地執(zhí)行程序程序。2、選擇結(jié)構(gòu):選擇結(jié)構(gòu)又稱為分支結(jié)構(gòu),它包括簡單選擇和多分支選擇結(jié)構(gòu),這種結(jié) 構(gòu)可以根據(jù)設(shè)立的條件,判斷應(yīng)該選擇哪一條分支來執(zhí)行相應(yīng)的語句序列。3、重復(fù)結(jié)構(gòu):重復(fù)結(jié)構(gòu)又稱為循環(huán)結(jié)構(gòu),它根據(jù)給左的條件,判斷是否需要重復(fù)執(zhí)行 某一相同的或類似的程序段,利用重復(fù)結(jié)構(gòu)可簡化大雖的程序行。分為兩類:一是先判斷后 執(zhí)行,一是先執(zhí)行后判斷。優(yōu)點:一是程序易于理解、使用和維護。二是編程工作的效率,降低軟件開發(fā)成本。三、結(jié)構(gòu)化程序設(shè)計原則和方法的應(yīng)用要注意把握如下要素:1、使用程序設(shè)計語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯。2、選用的控制結(jié)構(gòu)只準許有一個入口和一個出口:3、程序語句組成容易識別的塊,每塊只有一個入口和一個出口:4、復(fù)雜結(jié)構(gòu)應(yīng)該嵌套的基本控制結(jié)構(gòu)進行組合嵌套來實現(xiàn);5、語言中所沒有的控制結(jié)構(gòu),應(yīng)該采用前后一致的方法來模擬:6、嚴格控制GOTO語句的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 橄欖石項目評價分析報告
- 散列表課程設(shè)計
- 指甲刷市場環(huán)境與對策分析
- 旋轉(zhuǎn)式脫水機非加熱項目可行性實施報告
- 平臺開發(fā) 培訓課程設(shè)計
- Glycerol-3-phosphate-Oxidase-Aerococcus-viridans-GPO-Aerococcus-viridans-生命科學試劑-MCE
- 嬰兒搖鈴項目評價分析報告
- 期貨投資學課程設(shè)計
- 民用無人機相關(guān)項目建議書
- 北京聯(lián)合大學《地域文化品牌形象設(shè)計》2022-2023學年第一學期期末試卷
- 《建筑施工安全檢查標準》JGJ59-20248
- 宣講《鑄牢中華民族共同體意識》全文課件
- MOOC 跨文化交際通識通論-揚州大學 中國大學慕課答案
- 國開2024年《鋼結(jié)構(gòu)(本)》階段性學習測驗1-4答案
- 小學三年級數(shù)獨比賽“六宮”練習題(88道)
- EDA實驗報告1組合邏輯電路的設(shè)計
- 健美操大單元計劃、教學計劃2
- 2023年全國電力生產(chǎn)人身傷亡事故統(tǒng)計
- 10000中國普通人名大全
- 肺部體格檢查ppt課件.ppt
- 《環(huán)境保護稅政策及申報表》講解
評論
0/150
提交評論