數(shù)據(jù)結(jié)構(gòu)——C語言描述第1章-緒論

1、數(shù)據(jù)結(jié)構(gòu)C語言描述（慕課版）第1章 緒論編著：張同珍 & 學(xué)校： 上海交通大學(xué)緒論數(shù)據(jù)結(jié)構(gòu)定義基本操作存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)算法算法的時(shí)空復(fù)雜度數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)是外界信息進(jìn)入計(jì)算機(jī)，并被計(jì)算機(jī)處理的符號(hào)，數(shù)據(jù)元素是數(shù)據(jù)的基本單位。如有一組學(xué)生信息，每個(gè)學(xué)生信息是一個(gè)結(jié)構(gòu)類型數(shù)據(jù)，包含了學(xué)號(hào)、姓名、年齡等字段，那么這組學(xué)生信息是數(shù)據(jù)，每一個(gè)學(xué)生信息是數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)：是指相互之間具有一定關(guān)系的相同類型的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象：1. 元素之間的關(guān)系（邏輯結(jié)構(gòu)）2. 元素關(guān)系操作3. 元素和關(guān)系在內(nèi)存中的存儲(chǔ)（物理結(jié)構(gòu)）4. 在各種存儲(chǔ)方式下關(guān)系操作的實(shí)現(xiàn)5. 每種數(shù)據(jù)結(jié)構(gòu)的典型應(yīng)用研究數(shù)據(jù)的

2、邏輯結(jié)構(gòu)就是研究類型相同的一組元素和元素間的關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)集合關(guān)系：元素間呈松散關(guān)系，結(jié)構(gòu)中不同元素除了同屬于一個(gè)集合，相互間并無其他制約關(guān)系。如同班級(jí)里同學(xué)間的關(guān)系。線性關(guān)系：元素間呈現(xiàn)出你先我后的順序，是一種一對(duì)一的關(guān)系。如隊(duì)列中元素間的關(guān)系。除了隊(duì)首，每個(gè)元素有且只有一個(gè)唯一的直接前驅(qū)元素；除了隊(duì)尾，每個(gè)元素有且只有一個(gè)唯一的直接后繼元素。樹形關(guān)系：元素間呈現(xiàn)出一對(duì)多的關(guān)系。如家譜中人物間關(guān)系，一個(gè)人可以有多個(gè)兒子，卻只能有一個(gè)父親。即每個(gè)元素可以有多個(gè)后繼，卻只能有一個(gè)前驅(qū)。圖關(guān)系：元素間呈現(xiàn)多對(duì)多的關(guān)系。如城市間通過飛機(jī)航線形成的關(guān)系，例如上海、北京、西安3個(gè)城市中，任何兩個(gè)城

3、市間都可以有直飛航線。分以下幾種：數(shù)據(jù)的邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)通?？梢杂枚M描述: Data_Struct=(D,R)，其中D是元素的集合，R是關(guān)系的集合。例如整數(shù)110組成的有序集就是一個(gè)線性結(jié)構(gòu)。D= |110，R=1,21,2。其中1,2表示一個(gè)有序偶，即x1和x2有順序關(guān)系，x1是直接前驅(qū)，x2是直接后繼。關(guān)系操作（或稱基本操作）是和數(shù)據(jù)的邏輯結(jié)構(gòu)緊密相關(guān)的，它來源于關(guān)系自身的特點(diǎn)。構(gòu)造類：在內(nèi)存中建立這種數(shù)據(jù)結(jié)構(gòu)。如一個(gè)空的隊(duì)列。基本操作都可以分為五大類：構(gòu)造類、屬性類、數(shù)據(jù)操縱類、遍歷類、典型應(yīng)用類。屬性類：對(duì)元素及元素之間的關(guān)系的各類查詢。 屬于東瞧瞧、西看看，不影響元素及元素關(guān)系

4、本身。數(shù)據(jù)操縱類：對(duì)元素或元素關(guān)系有改變的操作，如插入或刪除某個(gè)元素。修改可視作刪除后插入。遍歷類：對(duì)結(jié)構(gòu)中的每個(gè)元素訪問且只訪問一遍。典型應(yīng)用類：所屬結(jié)構(gòu)獨(dú)特的應(yīng)用，不同結(jié)構(gòu)其典型應(yīng)用各不相同。數(shù)據(jù)的邏輯結(jié)構(gòu)+基本操作=抽象數(shù)據(jù)類型ADT（Abstract Data Type）。ADT和在計(jì)算機(jī)內(nèi)的表示、實(shí)現(xiàn)無關(guān)，只和數(shù)據(jù)自身的邏輯特征相關(guān)。ADT類似高級(jí)語言中的數(shù)據(jù)類型，如整型: 一個(gè)整數(shù)集合以及在這個(gè)集合中系統(tǒng)支持的基本操作（四則運(yùn)算、比較運(yùn)算等）。ADT區(qū)別于具體某種類型，只關(guān)心元素關(guān)系和關(guān)系操作，不實(shí)際要求數(shù)據(jù)的具體類型，只要元素類型一致。ADT的描述可以用自然語言也可以用偽代碼，其

5、內(nèi)容包含元素集合、元素關(guān)系集合、基本操作?；静僮鞅砻魃钪械囊粋€(gè)個(gè)基本的問題，有明確的已知條件和結(jié)果要求?；静僮鞯木唧w實(shí)現(xiàn)依賴于數(shù)據(jù)和數(shù)據(jù)關(guān)系在內(nèi)存中如何存儲(chǔ)，在邏輯結(jié)構(gòu)分析階段并不知道存儲(chǔ)方式，因此無法給出，也不需要考慮。順序存儲(chǔ)是用一塊連續(xù)的空間來存儲(chǔ)數(shù)據(jù)，同時(shí)借助這組空間在地址上的鄰接及有序性來存儲(chǔ)元素之間的關(guān)系，順序存儲(chǔ)的結(jié)構(gòu)稱順序結(jié)構(gòu)。高級(jí)語言中的數(shù)組可以實(shí)現(xiàn)連續(xù)空間的獲取，幫助實(shí)現(xiàn)順序結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)是在內(nèi)存中使用多個(gè)獨(dú)立的內(nèi)存空間，每個(gè)獨(dú)立的空間除了包括存儲(chǔ)元素的空間，還包括附加的空間來存儲(chǔ)元素之間的關(guān)系。鏈?zhǔn)酱鎯?chǔ)的數(shù)據(jù)結(jié)構(gòu)稱鏈?zhǔn)浇Y(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：也稱物理結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)在內(nèi)存

6、中的表示。常見的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種。算法及其要求這里算法是指用計(jì)算機(jī)解決一個(gè)具體問題的方法和步驟。算法必須滿足五個(gè)特性：一個(gè)算法中的每一步要在有限的時(shí)間內(nèi)完成，而整個(gè)算法必須在有限步之后完成。有窮性：算法中的每一步都有確定的含義，沒有二義性。確定性：算法中的每一步都是經(jīng)過有限次基本操作就可以完成的，每一步自身沒有復(fù)雜的算法問題?？尚行裕焊鶕?jù)問題需要，一個(gè)算法可以有零個(gè)或者若干個(gè)輸入作為解決問題的已知條件。有輸入：算法執(zhí)行結(jié)束后，有零個(gè)或者若干個(gè)輸出作為算法運(yùn)行結(jié)果。有輸出：算法及其要求度量算法優(yōu)劣的幾個(gè)要素：準(zhǔn)確反映并能滿足具體問題的要求，即對(duì)于任意一個(gè)合法的輸入， 都能給出正確

7、的結(jié)果。正確性：可供人們閱讀的容易程度，可讀性好的算法便于閱讀、理解、交 流、調(diào)試和糾錯(cuò)。可讀性：對(duì)各種不同的輸入都要有相應(yīng)的反應(yīng)。輸入數(shù)據(jù)合法，要有相應(yīng)的輸出；輸入數(shù)據(jù)不合法，要有相應(yīng)的響應(yīng)處理。健壯性：算法的執(zhí)行時(shí)間，應(yīng)能滿足問題解決的時(shí)間容忍要求。 如實(shí)時(shí)系統(tǒng)對(duì)處理時(shí)間有一個(gè)及時(shí)性反應(yīng)的要求。執(zhí)行時(shí)間越短，算法的時(shí)間效率越高。時(shí)間效率：算法執(zhí)行期間所需要的最大內(nèi)存空間。所需要的內(nèi)存空間越少，空間效率越高?？臻g效率：算法的時(shí)間復(fù)雜度算法的執(zhí)行時(shí)間是指依據(jù)算法編制的程序運(yùn)行時(shí)所消耗的時(shí)間。度量方法有運(yùn)行后度量和運(yùn)行前分析。運(yùn)行后度量：指根據(jù)不同算法事先編制好的程序和同樣的測(cè)試數(shù)據(jù)，在程序運(yùn)行

8、時(shí)借助機(jī)器的計(jì)時(shí)功能進(jìn)行計(jì)時(shí)，當(dāng)不同程序運(yùn)行結(jié)束時(shí)，分別記錄實(shí)際的運(yùn)行時(shí)間并進(jìn)行比較。運(yùn)行前分析：指在算法設(shè)計(jì)好但還沒有編程實(shí)現(xiàn)時(shí)，根據(jù)幾個(gè)方面的影響因素對(duì)算法的執(zhí)行時(shí)間進(jìn)行分析。算法時(shí)間復(fù)雜度的影響因素：02OPTION編譯后代碼的質(zhì)量：高級(jí)語言編制的程序通常要進(jìn)行編譯，不同編譯器往往采用不同的優(yōu)化策略，這樣便造成代碼運(yùn)行效率不同，也稱代碼質(zhì)量不同。03OPTION書寫程序所用的語言：同樣的算法，使用的編程語言越高級(jí)，實(shí)現(xiàn)的效率就越高，但執(zhí)行的效率就越低。04OPTION問題的規(guī)模：規(guī)模即指問題涉及的數(shù)據(jù)量的大小，通常數(shù)據(jù)量越大效率越低，一旦數(shù)據(jù)量大到一定級(jí)別，可能就要用到大數(shù)據(jù)處理方法，如

9、用分布式。05OPTION算法采用的策略和方法：同一問題可以有不同的方法和策略進(jìn)行解決，同一算法采用不同的方法策略消耗的時(shí)間可能就不同。機(jī)器的運(yùn)算速度：這里主要考慮計(jì)算機(jī)的主頻和字長。01OPTION設(shè)計(jì)算法時(shí)，考慮到時(shí)間消耗，主要是從算法的設(shè)計(jì)方案入手。算法時(shí)間復(fù)雜度計(jì)算運(yùn)行時(shí)間是算法實(shí)現(xiàn)中所有語句執(zhí)行的時(shí)間總和，由于不同機(jī)型指令集不同，且不同指令執(zhí)行時(shí)間也不同，所以使用算法中語句執(zhí)行的次數(shù)來度量更合理。語句執(zhí)行次數(shù)稱時(shí)間頻度，語句執(zhí)行的次數(shù)越多，時(shí)間花費(fèi)越多。一組相同數(shù)據(jù)可能引起一些語句反復(fù)執(zhí)行，因此一般算法的時(shí)間頻度和要處理的數(shù)據(jù)規(guī)模有關(guān)，故可以表示為數(shù)據(jù)規(guī)模n的函數(shù)T(n)。s = 0

10、;for (i=0; in; i+)s = s+ i;語句s = 0執(zhí)行1次， i=0執(zhí)行1次，i0) for (i=0; in; i+) printf(“%d “, i”);elseprintf(“n0的情況，為n次，而非n0，有T(n)Cf(n)。算法時(shí)間復(fù)雜度計(jì)算T(n)=32+2+10T(n)32+22+102152顯然存在0=1, =15，當(dāng)n0時(shí)，有T(n)152， 即f(n)=2，算法的復(fù)雜度為O（2)。又T(n)=3n+3的時(shí)間復(fù)雜度和T(n)=n的時(shí)間復(fù)雜度一樣都是O(n)?？梢钥闯?，時(shí)間復(fù)雜度是一個(gè)時(shí)間頻度表達(dá)式中的最高次項(xiàng)，且不帶系數(shù)。算法時(shí)間復(fù)雜度計(jì)算如果有內(nèi)外兩重循環(huán)

11、，相互不獨(dú)立：s=0;for (i=0; in; i+)for (j=0; ji; j+) s=s+i+j; printf(“s=%d”, s);可以將外循環(huán)打開來算：當(dāng)i=0時(shí)，內(nèi)循環(huán)體執(zhí)行0次；當(dāng)i=1時(shí)，內(nèi)循環(huán)體執(zhí)行1次；當(dāng)i=n-1時(shí)，內(nèi)循環(huán)體執(zhí)行n-1次；所以內(nèi)循環(huán)體一共執(zhí)行0+1+2+n-1=n(n-1)/2次，時(shí)間復(fù)雜度為O(2)。時(shí)間復(fù)雜度的計(jì)算方法總結(jié)：找到算法中和數(shù)據(jù)規(guī)模n有關(guān)的循環(huán)語句，計(jì)算循環(huán)體的執(zhí)行次數(shù)獲得時(shí)間頻度函數(shù)，取n的最高次項(xiàng)，去掉其系數(shù)，即是時(shí)間復(fù)雜度。按照這個(gè)順序排列，時(shí)間效率由高到低。當(dāng)?shù)竭_(dá)立方階之后，一旦數(shù)據(jù)規(guī)模大些，時(shí)間就不能忍受了，就是一個(gè)頑性算法

12、了?？臻g復(fù)雜度的度量實(shí)現(xiàn)算法的程序本身需要占據(jù)存儲(chǔ)空間；01OPTION通常1和2是不可避免的，在設(shè)計(jì)算法時(shí)主要關(guān)注額外的輔助空間。漸進(jìn)空間復(fù)雜度稱空間復(fù)雜度，是當(dāng)數(shù)據(jù)規(guī)模n趨于無窮時(shí)的輔助空間量階。待處理的數(shù)據(jù)需要在內(nèi)存中存儲(chǔ)，占據(jù)一定的空間；02OPTION在處理數(shù)據(jù)的過程中需要一些額外的輔助空間。03OPTION算法的空間消耗包括3個(gè)方面：空間復(fù)雜度的度量實(shí)現(xiàn)數(shù)據(jù)序列逆置的算法程序示例一：int a10=1,6,2,5,8,9,5,4,3,12;int t, i;for (i=0; i5; i+) t=ai;ai=a10-i-1;a10-i-1=t;為了完成n=10個(gè)元素的逆置，將a0和a9交換，將a1和a8交換，最后直到a4和a5交換，期間使用的輔助空間為一個(gè)變量t。故其空間復(fù)雜度和元素個(gè)數(shù)沒有關(guān)系，為O(1)。空間復(fù)雜度的度量實(shí)現(xiàn)數(shù)據(jù)序列逆置的算法程序示例二：int a10=1,6,2,5,8,9,5,4,3,12,b10;i