零基礎(chǔ)學(xué)數(shù)據(jù)結(jié)構(gòu)-第1章-概述復(fù)習(xí)進程

零基礎(chǔ)學(xué)數(shù)據(jù)結(jié)構(gòu)-第1章-概述1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)2．數(shù)據(jù)結(jié)構(gòu)的地位在我國，數(shù)據(jù)結(jié)構(gòu)已經(jīng)不僅僅是計算機專業(yè)的核心課程，還是其他非計算機專業(yè)的主要選修課程之一。數(shù)據(jù)結(jié)構(gòu)的研究不僅涉及到計算機硬件的研究范圍，而且與計算機軟件的研究有著更密切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。因此，可以認為數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程。1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)開發(fā)所有的計算機系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，要想更好地運用計算機來解決實際問題，僅掌握幾種計算機程序設(shè)計語言是難以應(yīng)付眾多復(fù)雜問題的。要想有效地使用計算機、充分發(fā)揮計算機的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)方面的有關(guān)知識。打好“數(shù)據(jù)結(jié)構(gòu)”這門課程的扎實基礎(chǔ)，對于學(xué)習(xí)計算機專業(yè)的其他課程，如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫管理系統(tǒng)、軟件工程、人工智能等都是十分有益的。1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)在計算機發(fā)展的初期，人們使用計算機的目的主要是處理數(shù)值計算問題。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是為了了解計算機處理對象的特性，將實際問題中所涉及的處理對象在計算機中表示出來并對它們進行處理。與此同時，通過算法訓(xùn)練來提高學(xué)生的思維能力，通過程序設(shè)計的技能訓(xùn)練來促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。

1.2基本概念和術(shù)語1．數(shù)據(jù)（data）

數(shù)據(jù)是描述客觀事物的符號，能輸入到計算機中并能被計算機程序處理的符號集合。它是計算機程序加工的“原料”。例如，一個文字處理程序（如Microsoftword）的處理對象就是字符串，一個數(shù)值計算程序的處理對象就是整型和浮點型數(shù)據(jù)。因此，數(shù)據(jù)的含義非常廣泛，如整型、浮點型等數(shù)值類型及字符、聲音、圖像、視頻等非數(shù)值數(shù)據(jù)都屬于數(shù)據(jù)范疇。1.2基本概念和術(shù)語2．數(shù)據(jù)元素（dataelement）數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項（dataitem）組成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。例如，一個學(xué)校的教職工基本情況表包括編號、姓名、性別、籍貫、所在院系、出生年月、職稱等數(shù)據(jù)項。這里的數(shù)據(jù)元素也稱為記錄。教職工基本情況如表1.1所示。1.2基本概念和術(shù)語表1.1教職工基本情況表編號姓名性別籍貫所在院系出生年月職稱05002胡志剛男河南化工學(xué)院1970.10教授01156張琳女北京文學(xué)院1978.08副教授03527李燕女陜西信息學(xué)院1981.11講師1.2基本概念和術(shù)語3．數(shù)據(jù)對象（dataobject）數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，正整數(shù)數(shù)據(jù)對象是集合N={1，2，3，…}，字母字符數(shù)據(jù)對象是集合C={‘A’，’B’，’C’，…}。1.2基本概念和術(shù)語4．數(shù)據(jù)結(jié)構(gòu)（datastructure）

數(shù)據(jù)結(jié)構(gòu)即數(shù)據(jù)的組織形式，它是數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素集合。在現(xiàn)實世界中，任何事物都是有內(nèi)在聯(lián)系的，而不是孤立存在的，同樣在計算機中，數(shù)據(jù)元素不是孤立的、雜亂無序的，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合。例如，表1.1的教職工基本情況表是一種表結(jié)構(gòu)，學(xué)校的組織機構(gòu)是一種層次結(jié)構(gòu)，城市之間的交通路線屬于圖結(jié)構(gòu)，如圖1.1、圖1.2所示。1.2基本概念和術(shù)語1.2基本概念和術(shù)語5．數(shù)據(jù)類型（datatype）數(shù)據(jù)類型是用來刻畫一組性質(zhì)相同的數(shù)據(jù)及其上的操作。數(shù)據(jù)類型是按照值的不同進行劃分的。在C語言中，按照取值的不同，數(shù)據(jù)類型還可以分為兩類：原子類型和結(jié)構(gòu)類型。原子類型是不可以再分解的基本類型，包括整型、實型、字符型等。結(jié)構(gòu)類型是由若干個類型組合而成，是可以再分解的。例如，整型數(shù)組是由若干整型數(shù)據(jù)組成的，結(jié)構(gòu)體類型的值也是由若干個類型范圍的數(shù)據(jù)構(gòu)成，它們的類型都是相同的。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)1.3.1邏輯結(jié)構(gòu)數(shù)據(jù)元素之間存在4種結(jié)構(gòu)類型：（1）集合。結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合外，數(shù)據(jù)元素之間沒有其它關(guān)系。這就像我們數(shù)學(xué)中的自然數(shù)集合，集合中的所有元素都屬于該集合，除此之外，沒有其它特性。例如，數(shù)學(xué)中的正整數(shù)集合{5，67，978，20，123，18}，集合中數(shù)除了屬于正整數(shù)外，元素之間沒有其它關(guān)系，數(shù)據(jù)結(jié)構(gòu)中的集合關(guān)系就類似于數(shù)學(xué)中的集合。集合表示如圖1.3所示。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)（2）線性結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系。線性結(jié)構(gòu)如圖1.4所示。數(shù)據(jù)元素之間有一種先后的次序關(guān)系，a,b,c是一個線性表，其中，a是b的前驅(qū)，b是a的后繼。（3）樹形結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系，樹形結(jié)構(gòu)如圖1.5所示。這就像學(xué)校的組織結(jié)構(gòu)圖，學(xué)校下面是教學(xué)的院系、行政機構(gòu)的部和處及一些研究所。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)（4）圖結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素是多對多的關(guān)系。圖1.6就是一個圖結(jié)構(gòu)。城市之間的交通路線圖就是多對多的關(guān)系，a，b，c，d，e，f，g是7個城市，城市a和城市b、e、f都存在一條直達路線，而城市b也和a、c、f存在一條直達路線。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)1.3.2存儲結(jié)構(gòu)存儲結(jié)構(gòu)也稱為物理結(jié)構(gòu)，指的是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中存儲形式。數(shù)據(jù)元素的存儲結(jié)構(gòu)形式通常有兩種：順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。采用順序存儲的字符串”abcdef”的存儲結(jié)構(gòu)如圖1.7所示。鏈式存儲是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的，數(shù)據(jù)元素的存儲關(guān)系并不能反映其邏輯關(guān)系，因此需要借助指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。字符串”abcdef”的鏈式存儲結(jié)構(gòu)如圖1.8所示。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的，今后在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的過程中，讀者將會發(fā)現(xiàn)，任何一個算法的設(shè)計取決于選定的數(shù)據(jù)邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)。1.4抽象數(shù)據(jù)類型及其描述1.4.1什么是抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型（abstractdatatype，簡稱ADT）是描述具有某種邏輯關(guān)系的數(shù)學(xué)模型，并對在該數(shù)學(xué)模型上進行的一組操作。抽象數(shù)據(jù)類型描述的是一組邏輯上的特性，與在計算機內(nèi)部表示無關(guān)。計算機中的整數(shù)數(shù)據(jù)類型是一個抽象數(shù)據(jù)類型，不同的處理器可能實現(xiàn)方法不同，但其邏輯特性相同，即加、減、乘、除等運算是一致的。1.4抽象數(shù)據(jù)類型及其描述抽象數(shù)據(jù)類型不僅包括在計算機中已經(jīng)定義了的數(shù)據(jù)類型，例如整型、浮點型等，還包括用戶自己定義的數(shù)據(jù)類型，例如結(jié)構(gòu)體類型、類等。一個抽象數(shù)據(jù)類型定義了一個數(shù)據(jù)對象、數(shù)據(jù)對象個數(shù)據(jù)元素之間的關(guān)系及對數(shù)據(jù)元素的操作。抽象數(shù)據(jù)類型通常是指用戶定義，用來解決應(yīng)用問題的數(shù)據(jù)模型，包括數(shù)據(jù)的定義和操作。例如，C++的類就是一個抽象數(shù)據(jù)類型，它包括用戶類型的定義和在用戶類型上的一組操作。1.4抽象數(shù)據(jù)類型及其描述抽象數(shù)據(jù)類型體現(xiàn)了程序設(shè)計中的問題分解、抽象和信息隱藏特性。抽象數(shù)據(jù)類型把實際生活中的問題分解為多個規(guī)模小且容易處理的問題，然后進行建立起一個計算機能處理的數(shù)據(jù)模型，并把每個功能模塊的實現(xiàn)細節(jié)作為一個獨立的單元，從而使具體實現(xiàn)過程隱藏起來。1.4抽象數(shù)據(jù)類型及其描述1.4.2抽象數(shù)據(jù)類型的描述本書把抽象數(shù)據(jù)類型分為兩個部分來描述：數(shù)據(jù)對象集合和基本操作集合。其中，數(shù)據(jù)對象集合包括數(shù)據(jù)對象的定義及數(shù)據(jù)對象中元素之間關(guān)系的描述，基本操作集合是對數(shù)據(jù)對象的運算的描述。數(shù)據(jù)對象和數(shù)據(jù)關(guān)系的定義可采用數(shù)學(xué)符號和自然語言描述，基本操作的定義格式為：基本操作名（參數(shù)表）：初始條件和操作結(jié)果描述。

1.4抽象數(shù)據(jù)類型及其描述例如，線性表的抽象數(shù)據(jù)類型描述如下：1．數(shù)據(jù)集合線性表的數(shù)據(jù)對象集合為{a1，a2，…，an}，每個元素的類型均為DataType。其中，除了第一個元素a1外，每一個元素有且只有一個直接前驅(qū)元素，除了最后一個元素an外，每一個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系。1.4抽象數(shù)據(jù)類型及其描述2．基本操作集合線性表的基本操作主要有：（1）InitList(&L)：初始化操作，建立一個空的線性表L。這就像是在日常生活中，一所院校為了方便管理，建立一個教職工基本情況表，準備登記教職工信息。（2）ListEmpty(L)：若線性表L為空，返回1，否則返回0。這就像是剛剛建立了教職工基本情況表，還沒有登記教職工信息。（3）GetElem(L,i,&e)：返回線性表L的第i個位置元素值給e。這就像在教職工基本情況表中，根據(jù)給定序號查找某個教師信息。（4）LocateElem(L,e)：在線性表L中查找與給定值e相等的元素，如果查找成功返回該元素在表中的序號表示成功，否則，返回0表示失敗。這就像在教職工基本情況表中，根據(jù)給定的姓名查找教師信息。（5）InsertList(&L,i,e)：在線性表L中的第i個位置插入新元素e。這就類似于經(jīng)過招聘考試，引進了一名教師，這個教師信息被登記到教職工基本情況表中。1.4抽象數(shù)據(jù)類型及其描述可能你會在大多數(shù)教材上看到線性表的抽象數(shù)據(jù)類型用以下方式描述：ADTList{數(shù)據(jù)對象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}1.4抽象數(shù)據(jù)類型及其描述需要注意的是，在基本操作的描述過程中，參數(shù)傳遞有兩種方式：一種是數(shù)值傳遞，另一種是引用傳遞。前者僅僅是將數(shù)值傳遞給形參，并不返回結(jié)果；后者其實是把實參的地址傳遞給形參，實參和形參其實是同一個變量，被調(diào)用函數(shù)通過修改該變量的值返回給調(diào)用函數(shù)，從而把結(jié)果帶回。在描述算法時，通過在參數(shù)前加上&，表示引用傳遞，如果參數(shù)前沒有&，表示是數(shù)值傳遞。1.5算法1.5.1數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切。兩者既有聯(lián)系又有區(qū)別。數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系可用一個公式描述：程序=算法+數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是算法實現(xiàn)的基礎(chǔ)，算法總是要依賴于某種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的。算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。1.5算法

數(shù)據(jù)結(jié)構(gòu)與算法的區(qū)別在于：數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上解決實際問題。算法是編程思想，數(shù)據(jù)結(jié)構(gòu)則是這些思想的邏輯基礎(chǔ)。1.5算法1.5.1什么是算法

算法(algorithm)是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為有限的操作序列。操作序列包括了一組操作，每一個操作都完成特定的功能。例如，求n個數(shù)中最大者的問題，其算法描述如下：1．定義一個變量max和一個數(shù)組a[]，分別用來存放最大數(shù)和數(shù)組的元素，并假定第一個數(shù)最大，賦給max，即：max=a[0];1.5算法2．依次把數(shù)組a中其余的n-1個數(shù)與max進行比較，遇到較大的數(shù)時，將其賦給max。for(i=1;i<n;i++)if(max<a[i])max=a[i];最后，max中的數(shù)就是n個數(shù)中的最大者。1.5算法1.5.2算法的五大特性算法具有以下5個特性。（1）有窮性。有窮性指的是算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。（2）確定性。算法的每一步驟都具有確定的含義，不會出現(xiàn)二義性。算法在一定條件下，只有一條執(zhí)行路徑，也就是相同的輸入只能有一個唯一的輸出結(jié)果。（3）可行性。算法的每一步都必須是可行的，也就是說，每一步都能夠通過執(zhí)行有限次數(shù)完成。（4）輸入。算法具有零個或多個輸入。（5）輸出。算法至少有一個或多個輸出。輸出的形式可以是打印輸出也可以是返回一個或多個值。1.5.3算法的描述算法的描述方式有多種：自然語言、偽代碼（或稱為類語言）、程序流程圖及程序設(shè)計語言（如C語言）。例如，判斷正整數(shù)m是否為質(zhì)數(shù)的算法可用以下幾種方式描述。1.5算法1.5算法1．自然語言描述法我們利用自然語言描述m是否為質(zhì)數(shù)的算法如下：（1）輸入正整數(shù)m，令i=2；（2）如果i<=，則令m對i求余，將余數(shù)送入中間變量r；否則，輸出“m是質(zhì)數(shù)”，算法結(jié)束；（3）判斷r是否為零。如果為零，輸出“m不是質(zhì)數(shù)”，算法結(jié)束。如果r不為零，則令i增加1，轉(zhuǎn)到步驟（2）執(zhí)行。1.5算法2．程序流程圖法判斷m是否為質(zhì)數(shù)的程序流程圖如圖1.9所示。我們采用類C語言描述和C語言描述如下：1.5算法

3．類語言法voidIsPrime()/*判斷m是否為質(zhì)數(shù)*/{ scanf(m); /*輸入正整數(shù)m*/ for(i=2;i<=sqrt(m);i++){r=m%i;/*求余數(shù)*/if(r==0)/*如果m能被整除*/{printf(“m不是質(zhì)數(shù)！”);break;}}printf(“m是質(zhì)數(shù)！”);}1.5算法

4．程序設(shè)計語言法voidIsPrime()/*判斷m是否為質(zhì)數(shù)*/{printf(“請輸入一個正整數(shù)：”); scanf(“%d”,&m);/*輸入正整數(shù)m*/ for(i=2;i<=sqrt(m);i++){r=m%i; /*求余數(shù)*/if(r==0) /*如果m能被整除*/{printf(“m不是質(zhì)數(shù)！\n”);break;}}printf(“m是質(zhì)數(shù)！\n”);}1.6.1算法設(shè)計的四個目標一個好的算法應(yīng)該具備以下目標：1．算法的正確性算法的正確性（correctness）是指算法至少應(yīng)該包括對于輸入、輸出和加工處理無歧義性的描述，能正確反映問題的需求，且能夠得到問題的正確答案。1.6算法分析通常算法的正確性應(yīng)包括以下4個層次：a.算法對應(yīng)的程序沒有語法錯誤；b.對于幾組輸入數(shù)據(jù)能得到滿足規(guī)格要求的結(jié)果；c.對于精心選擇的典型的、苛刻的帶有刁難性的幾組輸入數(shù)據(jù)能得到滿足規(guī)格要求的結(jié)果；d.對于一切合法的輸入都能得產(chǎn)生滿足要求的結(jié)果。1.6算法分析2．可讀性算法主要是為了人們方便閱讀和交流，其次才是計算機執(zhí)行?？勺x性（readability）好有助于人們對算法的理解，晦澀難懂的程序往往隱含錯誤不易被發(fā)現(xiàn)，難以調(diào)試和修改。1.6算法分析3．健壯性（robustness）當輸入數(shù)據(jù)不合法時，算法也能做出反應(yīng)或進行處理，而不會產(chǎn)生異常或莫名其妙的輸出結(jié)果。例如，求一元二次方程根ax2+bx+c=0的算法，需要考慮多種情況，先判斷b2-4ac的正負，如果為正數(shù)，則該方程有兩個不同的實根；如果為負，表明該方程無實根；如果為零，表明該方程只有一個實根；如果a=0，則該方程又變成了一元一次方程，此時若b=0，還要處理除數(shù)為零的情況。如果輸入的a、b、c不是數(shù)值型，還要提示用戶輸入錯誤。1.6算法分析4．高效率和低存儲量效率指的是算法的執(zhí)行時間。對于同一個問題如果有多個算法能夠解決，執(zhí)行時間短的算法效率高，執(zhí)行時間長的效率低。存儲量需求指算法在執(zhí)行過程中需要的最大存儲空間。效率與低存儲量需求都與問題的規(guī)模有關(guān)，求100個人的平均分與求1000個人的平均分所花的執(zhí)行時間和運行空間顯然有一定差別。設(shè)計算法時應(yīng)盡量選擇高效率和低存儲量需求的算法。1.6算法分析1.6.2算法效率評價算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上的運行時所耗費的時間來度量，而度量一個算法在計算機上的執(zhí)行時間通常有兩種方法：1．事后統(tǒng)計方法這種方法有兩個缺陷：一是必須依據(jù)算法事先編制好程序，這通常需要花費大量的時間與精力；二是時間的長短依賴計算機硬件和軟件等環(huán)境因素，有時會掩蓋算法本身的優(yōu)劣。因此，人們常常采用事前分析估算的方法評價算法的好壞。1.6算法分析2．事前分析估算方法這主要在計算機程序編制前，對算法依據(jù)數(shù)學(xué)中的統(tǒng)計方法進行估算。這主要是因為算法的程序在計算機上的運行時間取決于以下因素：a．算法采用的策略、方法；b．編譯產(chǎn)生的代碼質(zhì)量；c．問題的規(guī)模；d．書寫的程序語言，對于同一個算法，語言級別越高，執(zhí)行效率越低；e．機器執(zhí)行指令的速度。1.6算法分析例如，斐波那契數(shù)列的算法和語句的的頻度如下。每一條語句的頻度f0=0;1f1=1;1printf(“%d,%d”,f0,f1);1for(i=2;i<=n;i++)n{ fn=f0+f1;n-1 printf(“,%d”,fn);n-1 f0=f1;n-1 f1=fn;n-1}每一條語句的右端是對應(yīng)語句的頻度（frequencycount），即語句的執(zhí)行次數(shù)。上面算法總的執(zhí)行次數(shù)為T(n)=1+1+1+n+4(n-1)=5n-1。1.6算法分析1.6.3算法的時間復(fù)雜度在進行算法分析時，語句總的執(zhí)行次數(shù)T（n）是關(guān)于問題