1.1數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容:
? ? 計(jì)算機(jī)數(shù)值計(jì)算一般步驟:首先從具體問(wèn)題抽象出數(shù)學(xué)模型——》然后設(shè)計(jì)一個(gè)解釋此數(shù)學(xué)模型的算法——》最后編寫程序胞四。
? ? 上述過(guò)程中屁使,尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問(wèn)題;從中提取操作對(duì)象,并找出這些對(duì)象之間的關(guān)系,然后用數(shù)學(xué)語(yǔ)言加以描述,即建立相應(yīng)的數(shù)學(xué)方程敬鬓。
? ? 數(shù)據(jù)結(jié)構(gòu)主要研究非數(shù)值計(jì)算問(wèn)題,非數(shù)值計(jì)算問(wèn)題無(wú)法用數(shù)學(xué)方程建立數(shù)學(xué)模型笙各;
? ? 數(shù)據(jù)結(jié)構(gòu):(簡(jiǎn)化定義)是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)中的操作對(duì)象钉答,以及這些對(duì)象之間的關(guān)系和操作
? ??的學(xué)科,數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)酪惭、計(jì)算機(jī)硬件和軟件三者之間的一門核心課程希痴。
非數(shù)值計(jì)算數(shù)據(jù)結(jié)構(gòu)模型實(shí)例:
? ???????????線性表結(jié)構(gòu)(元素之間一一對(duì)應(yīng)):學(xué)生學(xué)籍管理模型,圖書(shū)館的書(shū)目管理系統(tǒng)春感,庫(kù)存管理系統(tǒng)
? ? ? ? ? ? 樹(shù)數(shù)據(jù)結(jié)構(gòu)(元素之間一對(duì)多):人機(jī)對(duì)弈問(wèn)題砌创,計(jì)算機(jī)文件系統(tǒng),單位組織機(jī)構(gòu)
? ? ? ? ? ? 圖結(jié)構(gòu)(元素之間多對(duì)多):最短路徑問(wèn)題鲫懒,網(wǎng)絡(luò)工程圖嫩实,網(wǎng)絡(luò)通信
數(shù)據(jù)結(jié)構(gòu)發(fā)展簡(jiǎn)述:
? ? 20實(shí)際60年代初期,“數(shù)據(jù)結(jié)構(gòu)”散見(jiàn)于操作系統(tǒng)窥岩、編譯原理甲献;
? ? 1968年,作為獨(dú)立課程列入美國(guó)一些大學(xué)的計(jì)算機(jī)科學(xué)教學(xué)計(jì)劃颂翼;同年計(jì)算機(jī)科學(xué)家D.E.Knuth教授發(fā)表《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第一卷《基本算法》晃洒。這是第一本教系統(tǒng)的闡述數(shù)據(jù)機(jī)構(gòu)基本內(nèi)容的著作。
? ? 之后朦乏,結(jié)構(gòu)化程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要研究方向球及,人們普遍認(rèn)為,程序設(shè)計(jì)的實(shí)質(zhì)呻疹,就是對(duì)所處理的問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)吃引,并在此結(jié)構(gòu)的基礎(chǔ)上施加一種好的算法。著名科學(xué)及Wirth教授的《算法+數(shù)據(jù)結(jié)構(gòu)=程序》正是這種觀點(diǎn)的集中體現(xiàn)刽锤。
數(shù)據(jù)結(jié)構(gòu)發(fā)展方向:
? ? 一方面镊尺,面向個(gè)專門領(lǐng)域中特殊問(wèn)題的數(shù)據(jù)結(jié)構(gòu)正在研究和發(fā)展;
? ? 一方面并思,從抽象數(shù)據(jù)類型的觀點(diǎn)來(lái)討論數(shù)據(jù)結(jié)構(gòu)庐氮,已成為一種新趨勢(shì)。
1.2.1基本概念和術(shù)語(yǔ):
數(shù)據(jù)(data):客觀事物的表示符號(hào)宋彼,是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱弄砍。
數(shù)據(jù)元素(data-element):數(shù)據(jù)的基本單位颅筋,一般也被稱為元素;用于完成的描述一個(gè)對(duì)象输枯,例如學(xué)生學(xué)籍管理模型中一名學(xué)生的記錄,可被稱為一個(gè)數(shù)據(jù)元素占贫。
數(shù)據(jù)項(xiàng)(data item):是組成數(shù)據(jù)元素的桃熄、有獨(dú)立含義的、不可分割的最小單位型奥。例如一名學(xué)生記錄表中的學(xué)號(hào)瞳收、姓名、性別等厢汹。
數(shù)據(jù)對(duì)象(data object):是性質(zhì)相同的數(shù)據(jù)元素的集合螟深,是數(shù)據(jù)的一個(gè)子集。學(xué)生基本信息表也可被看作一個(gè)數(shù)據(jù)對(duì)象烫葬,他是學(xué)生信息的集合界弧。一個(gè)集合內(nèi),元素的性值均相同搭综,都可稱之為一個(gè)數(shù)據(jù)對(duì)象垢箕。
數(shù)據(jù)結(jié)構(gòu)(data structure):是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,換句話說(shuō)兑巾,數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合条获,“結(jié)構(gòu)”就是數(shù)據(jù)元素之間存在的關(guān)系,比如線性結(jié)構(gòu)蒋歌,樹(shù)結(jié)構(gòu)等帅掘。
數(shù)據(jù)結(jié)構(gòu)的形式定義:
? ? 是一個(gè)二元組:
? ? ? ? Data-Structure(D,S)堂油;其中D是數(shù)據(jù)元素的有限集合修档,S是D上關(guān)系的有限集合;
數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)層次:
????1)邏輯結(jié)構(gòu):數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)称诗,他與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)萍悴,是獨(dú)立于計(jì)算機(jī)的。因此寓免,數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型癣诱。數(shù)據(jù)元素之間的關(guān)系,可以是數(shù)據(jù)之間代表某種元素的自然關(guān)系袜香,也可以是為處理問(wèn)題方便人為定義的關(guān)系撕予,這種自然或人為定義的關(guān)系,稱為數(shù)據(jù)元素之間的邏輯關(guān)系蜈首,相應(yīng)的結(jié)構(gòu)稱為邏輯結(jié)構(gòu)实抡。
? ? ? ? ?邏輯結(jié)構(gòu)兩要素:數(shù)據(jù)元素欠母,關(guān)系。關(guān)系是指數(shù)據(jù)元素之間的邏輯關(guān)系吆寨;根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性赏淌,通常有四類結(jié)構(gòu),如下所示啄清,他們的復(fù)雜程度一次遞進(jìn):
? ? ? ? a.集合結(jié)構(gòu):數(shù)據(jù)元素屬于同一集合六水,別無(wú)其他關(guān)系
? ? ? ? b.線性結(jié)構(gòu):數(shù)據(jù)元素之間一一對(duì)應(yīng)的關(guān)系結(jié)構(gòu);例如將學(xué)生信息按學(xué)號(hào)一一排列
? ? ? ? c.樹(shù)結(jié)構(gòu):數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系辣卒;例如掷贾,在公司管理中,老板管理多個(gè)項(xiàng)目組荣茫,項(xiàng)目組管理多個(gè)員工
? ? ? ? d.圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu):數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系想帅;例如多位同學(xué)之間的朋友關(guān)系
? ??????其中集合結(jié)構(gòu),樹(shù)結(jié)構(gòu)啡莉,網(wǎng)狀結(jié)構(gòu)港准,都是非線性結(jié)構(gòu)
? ??????線性結(jié)構(gòu)包括線性表、棧咧欣、隊(duì)列(具有特殊限制的線性表叉趣,數(shù)據(jù)操作只能在表的一端多兩端進(jìn)行)、字符该押、數(shù)組疗杉、廣義表。
? ? ? ? 非線性結(jié)構(gòu)包括樹(shù)蚕礼、二叉樹(shù)烟具、有向圖、無(wú)向圖
????2)存儲(chǔ)結(jié)構(gòu):數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)奠蹬,也稱物理結(jié)構(gòu)朝聋,把數(shù)據(jù)對(duì)象存儲(chǔ)在計(jì)算機(jī)時(shí),既要存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)囤躁,又要存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系冀痕,數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)用一個(gè)結(jié)點(diǎn)表示。
? ? ? ? 數(shù)據(jù)元素在計(jì)算機(jī)中的兩種基本存儲(chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)狸演、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)言蛇。
? ? ? ? ? ? 順序存儲(chǔ)結(jié)構(gòu):用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu),順序存儲(chǔ)結(jié)構(gòu)要求元素依次存放在一片連續(xù)的存儲(chǔ)空間中宵距;如下圖所示:
? ? ? ? ? ? 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):順序存儲(chǔ)結(jié)構(gòu)要求元素依次存放在一片連續(xù)的存儲(chǔ)空間中腊尚,而鏈?zhǔn)浇Y(jié)構(gòu)無(wú)需占用一整塊存儲(chǔ)空間,但為了表示節(jié)點(diǎn)之間的關(guān)系满哪,需要給每個(gè)結(jié)點(diǎn)附加一個(gè)指針字段婿斥,用于存放后繼元素的存儲(chǔ)地址劝篷,所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言的指針類型來(lái)描述,如下圖所示:
順序存儲(chǔ)結(jié)構(gòu)民宿、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的區(qū)別和聯(lián)系:
????區(qū)別:
順序結(jié)構(gòu):數(shù)據(jù)元素存放的地址是連續(xù)的娇妓;
鏈?zhǔn)浇Y(jié)構(gòu):數(shù)據(jù)元素之間存放的地址是否連續(xù)沒(méi)有要求
????聯(lián)系:
數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的兩個(gè)方面,一個(gè)算法的設(shè)計(jì)取決于所選的邏輯結(jié)構(gòu)活鹰,而算法的實(shí)現(xiàn)依賴于所采用的邏輯結(jié)構(gòu)峡蟋。
邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu):
1.2.2數(shù)據(jù)類型和抽象數(shù)據(jù)類型
數(shù)據(jù)類型(data type):指的是一個(gè)值的集合和定義在該值集上的一組操作的總稱。
數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)密不可分华望,js中有引用數(shù)據(jù)類型和基本數(shù)據(jù)類型
數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型,也不同于數(shù)據(jù)對(duì)象仅乓,它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對(duì)象赖舟,而且要描寫數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。
數(shù)據(jù)結(jié)構(gòu)的運(yùn)算:
1)建立(create)一個(gè)數(shù)據(jù)結(jié)構(gòu)
2)消除(Destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu)
3) 從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個(gè)數(shù)據(jù)元素
4) 把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中
5) 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)(Access)
6) 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素進(jìn)行修改(Modify)
7) 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(Sort)
8) 對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(Search)
抽象數(shù)據(jù)類型(Abstract Data Type夸楣,ADT):是指一個(gè)數(shù)學(xué)模型宾抓,以及定義在該模型上的一組操作。
ADT定義僅是一組邏輯特性描述豫喧,與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無(wú)關(guān)石洗,因此,不論ADT內(nèi)部結(jié)構(gòu)如何讓變化紧显,只要其數(shù)學(xué)特性不變讲衫,都不影響其外部使用
ADT的形式化定義是三元組:ADT = (D,S孵班,P)
? ? ????其中D是數(shù)據(jù)對(duì)象涉兽,S(數(shù)據(jù)關(guān)系)是D上的關(guān)系集,P(基本操作)是對(duì)D的基本操作篙程。
ADT的一般定義形式:
ADT<抽象數(shù)據(jù)類型名>{
? ? ? ? 數(shù)據(jù)對(duì)象:<數(shù)據(jù)對(duì)象的定義>
? ? ? ? 數(shù)據(jù)關(guān)系:<數(shù)據(jù)關(guān)系的定義>
????????基本操作:<基本操作的定義>
} ADT<抽象數(shù)據(jù)類型名>
? ? ? ??——其中枷畏,數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述;
? ???????——<基本操作的定義>? :
? ? ? ? ? ? ? ? ? ? <基本操作名>(<參數(shù)名>)
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 初始條件:<初始條件描述>
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 操作結(jié)果:<操作結(jié)果描述>
初始條件:描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件,若不滿足虱饿,則操作失敗拥诡。返回響應(yīng)的出錯(cuò)信息。
操作結(jié)果:描述操作正常完成之后氮发,數(shù)據(jù)結(jié)構(gòu)的變化狀況應(yīng)返回結(jié)果渴肉。
抽象數(shù)據(jù)類型使用的意義:
????????運(yùn)用抽象數(shù)據(jù)類型描述數(shù)據(jù)結(jié)構(gòu),有助于在設(shè)計(jì)一個(gè)軟件系統(tǒng)時(shí)爽冕,不必首先考慮其中包含的數(shù)據(jù)對(duì)象宾娜,以及操作在不同處理器中的表現(xiàn)和實(shí)現(xiàn)細(xì)節(jié),而是在構(gòu)成軟件系統(tǒng)的每個(gè)相對(duì)獨(dú)立的模塊上定義一個(gè)數(shù)據(jù)和相應(yīng)的操作扇售,把這些數(shù)據(jù)的表示和操作細(xì)節(jié)留在模塊內(nèi)部解決前塔,在更高層次上進(jìn)行軟件的分析和設(shè)計(jì)嚣艇,從而提高軟件的整體性能和利用率。
? ? ? ? ADT概念與賣你想對(duì)象思想一致华弓,ADT獨(dú)立于具體實(shí)現(xiàn)食零,將數(shù)據(jù)和操作封裝在一起,使得用戶程序只能通過(guò)ADT定義的某些操作來(lái)訪問(wèn)其中的數(shù)據(jù)寂屏,從而實(shí)現(xiàn)了信息隱藏贰谣。在C++中,類的聲明表示ADT迁霎,類的實(shí)現(xiàn)表示ADT的實(shí)現(xiàn)吱抚。
1.3算法
算法(Algorithm):是對(duì)特定問(wèn)題求解方法(步驟)的一種描述,時(shí)指令的有限序列考廉,其中每一條指令表示一個(gè)或多個(gè)操作秘豹。
算法滿足以下五個(gè)特性:
? ? ? ? 1)有窮性:算法執(zhí)行有窮的步驟,并在有窮時(shí)間內(nèi)結(jié)束
? ? ? ? 2)確定性:算法中每一條指令必須具有確切的含義昌粤,不存在二義性既绕,且算法只有一個(gè)入口和出口
? ? ? ? 3)可行性:算法中的左右操作可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)
? ? ? ? 4)輸入:一個(gè)算法有零個(gè)或多個(gè)輸入,這些輸入取自于某個(gè)特定的對(duì)象集合
? ? ? ? 5)輸出:一個(gè)算法有一個(gè)或多個(gè)輸出涮坐,這些輸出是同輸入有著特定關(guān)系的量
算法和程序是兩種不同的概念凄贩,一個(gè)計(jì)算機(jī)程序?qū)σ粋€(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言具體實(shí)現(xiàn),算法必須可終止袱讹,意味著并不是所有計(jì)算機(jī)程序都是算法疲扎。
評(píng)價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn):
? ? ? ? 1)正確性:滿足具體問(wèn)題的需求;
? ? ? ? 2)可讀性:供人閱讀和交流捷雕;
? ? ? ? 3)健壯性:有容錯(cuò)處理评肆,當(dāng)輸入有誤時(shí),算法應(yīng)能進(jìn)行處理非区。不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果瓜挽。
? ? ? ? 4)通用性:算法應(yīng)具有一般性,即算法的處理結(jié)果對(duì)于一般的數(shù)據(jù)集合都成立征绸。
? ? ? ? 5)效率與存儲(chǔ)量需求:效率指算法執(zhí)行時(shí)間久橙,存儲(chǔ)量指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般這兩者與問(wèn)題的規(guī)模有關(guān)管怠。
算法效率的度量:
算法執(zhí)行時(shí)間需通過(guò)一句該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來(lái)度量淆衷,其方法通常有兩種:
事后統(tǒng)計(jì):計(jì)算機(jī)內(nèi)部執(zhí)行時(shí)間和占用空間的統(tǒng)計(jì);
事前分析:求出該算法的時(shí)間界限函數(shù)渤弛;????
? ? ? ? 于此相關(guān)的因素有:
? ? ? ? ?——一句算法選用何種策略
? ? ? ? ?——問(wèn)題的規(guī)模
? ? ? ? ——程序設(shè)計(jì)的語(yǔ)言
? ? ? ? ——編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量
? ? ? ? ——機(jī)器執(zhí)行指令的速度????
? ? ? ? 撇開(kāi)軟硬件等有關(guān)部門因素祝拯,可以認(rèn)定一個(gè)特定算法運(yùn)行工作量的大小,只依賴于問(wèn)題的規(guī)模(通常用n表示),或者說(shuō)他是問(wèn)題規(guī)模的函數(shù)佳头。
算法的時(shí)間復(fù)雜度定義:算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的函數(shù)鹰贵,其時(shí)間度量記作,稱作算法的漸近時(shí)間復(fù)雜度(Asymptotic? Time Complexity);一般的康嘉,常用最深層循環(huán)內(nèi)的語(yǔ)句中的原操作的執(zhí)行頻度來(lái)表示碉输。
? ? ? ? 的定義:表示的數(shù)量級(jí);
? ? ? ??的嚴(yán)格定義:若和是定義在正整數(shù)集合上的兩個(gè)函數(shù)亭珍,則表示存在常數(shù)和敷钾,使得時(shí),都滿足肄梨。
? ? ? ? 該定義說(shuō)明函數(shù)和具有相同的增長(zhǎng)趨勢(shì)阻荒。符號(hào)用來(lái)描述速率的增長(zhǎng)上限。
問(wèn)題規(guī)模:是算法求解問(wèn)題輸入量的多少众羡,是問(wèn)題大小的本質(zhì)表示侨赡,一般用整數(shù)n表示。
語(yǔ)句頻度:一條語(yǔ)句的重復(fù)執(zhí)行次數(shù)纱控。
分析算法時(shí)間復(fù)雜度的基本方法:找出所有語(yǔ)句中語(yǔ)句頻度最大的那條語(yǔ)句作為基本語(yǔ)句,計(jì)算基本語(yǔ)句的頻度得到問(wèn)題規(guī)模n的某個(gè)函數(shù),取其數(shù)量級(jí)用符號(hào)表示菜秦,具體計(jì)算數(shù)量級(jí)時(shí)可用以下定理:
定理1.1:若是一個(gè)m次多項(xiàng)式甜害,則;
表示時(shí)間復(fù)雜度的階:
實(shí)例:
算法的空間復(fù)雜度(space complexity):是指算法編寫成程序后在計(jì)算機(jī)中運(yùn)行時(shí)球昨,所需存儲(chǔ)空間大小的度量尔店,記作;
該存儲(chǔ)空間一般包括三個(gè)方面:
? ? ? ? -指令常數(shù)變量所占據(jù)的存儲(chǔ)空間
? ? ? ? -輸入數(shù)據(jù)所占用的存儲(chǔ)空間
? ? ? ? -輔助(存儲(chǔ))空間
? ? ? ? ——一般的,算法的空間復(fù)雜度值得是輔助空間
? ? ? ? 一維數(shù)組a[n]:空間復(fù)雜度為O(n);
? ? ? ? 二位數(shù)組a[n][m]:空間復(fù)雜度為O(m*n);