《數(shù)據(jù)結(jié)構(gòu)》基本概念

1、1基本概念?數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)是信息的載體，在計(jì)算機(jī)科學(xué)中是指所有能輸入輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和處理處理的符號(hào)集合。?數(shù)據(jù)元素?cái)?shù)據(jù)元素?cái)?shù)據(jù)元素也稱為結(jié)點(diǎn)，是表示數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。?數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。?數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。注意：在不產(chǎn)生混淆的情況下，將數(shù)據(jù)對(duì)象簡(jiǎn)稱為數(shù)據(jù)。?數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互

2、之間存在一定關(guān)系的數(shù)據(jù)元素的集合，即數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組DataStructure=(DR)，其中D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。?數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間邏輯關(guān)系的整體。根據(jù)數(shù)據(jù)元素之間邏輯關(guān)系的不同，數(shù)據(jù)結(jié)構(gòu)分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個(gè)集合”，除此之外，沒有任何關(guān)系；⑵線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系；⑶樹結(jié)構(gòu)：數(shù)

3、據(jù)元素之間存在著一對(duì)多的層次關(guān)系；⑷圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系。注意：數(shù)據(jù)結(jié)構(gòu)分為兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。?數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示。通常有兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組連續(xù)連續(xù)的存儲(chǔ)單元依次依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是由元素的存儲(chǔ)位置來表示的。鏈接存儲(chǔ)結(jié)構(gòu)的基本思想是：用一組任意任意的存儲(chǔ)單

4、元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系是用指針來表示的。注意：存儲(chǔ)結(jié)構(gòu)除了存儲(chǔ)數(shù)據(jù)元素之外，必須存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系。?抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱。抽象數(shù)據(jù)類型提供了使用和實(shí)現(xiàn)兩個(gè)不同的視圖，實(shí)現(xiàn)了封裝和信息隱藏。?算法的定義算法的定義通俗地講，算法是解決問題的方法，嚴(yán)格地說，算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。?算法的特性算法的特性⑴輸入：一個(gè)算法有零個(gè)

5、或多個(gè)輸入（即算法可以沒有輸入），這些輸入通常取自于某個(gè)特定的對(duì)象集合。⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出（即算法必須要有輸出），通常輸出與輸入之間有著某種特定的關(guān)系。3structDulNodeElemTypedataElemType表示不確定的數(shù)據(jù)類型structDulNodeprinextpri為前驅(qū)指針域，next為后繼指針域firstfirst表示雙鏈表的頭指針?棧的定義棧的定義棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。允許插

6、入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。?棧的操作特性棧的操作特性棧的操作具有后進(jìn)先出后進(jìn)先出的特性。?隊(duì)列的定義隊(duì)列的定義隊(duì)列隊(duì)列是只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。?隊(duì)列的操作特性隊(duì)列的操作特性隊(duì)列的操作具有先進(jìn)先出先進(jìn)先出的特性。?循環(huán)隊(duì)列中解決隊(duì)空隊(duì)滿的判斷條件循環(huán)隊(duì)列中解決隊(duì)空隊(duì)滿的判斷條件方法一：附設(shè)一個(gè)存儲(chǔ)隊(duì)列中元素個(gè)數(shù)的變

7、量num，當(dāng)num=0時(shí)隊(duì)空，當(dāng)num=QueueSize時(shí)為隊(duì)滿；方法二：修改隊(duì)滿條件，浪費(fèi)一個(gè)元素空間，隊(duì)滿時(shí)數(shù)組中只有一個(gè)空閑單元；即隊(duì)空的條件是front=rear，隊(duì)滿的條件是(rear1)%QueueSize=front，隊(duì)列長(zhǎng)度為(rearfrontQueueSize)%QueueSize。方法三：設(shè)置標(biāo)志flag，當(dāng)front=rear且flag=0時(shí)為隊(duì)空，當(dāng)front=rear且flag=1時(shí)為隊(duì)滿。?串的定義串的定

8、義串是零個(gè)或多個(gè)字符組成的有限序列。?空格串和空串的定義空格串和空串的定義只包含空格的串稱為空格串空格串。串中所包含的字符個(gè)數(shù)稱為串的長(zhǎng)度，長(zhǎng)度為0的串稱空串空串，記作““。?串的比較串的比較串的比較是通過組成串的字符之間的比較來進(jìn)行的。給定兩個(gè)串：X=“x1x2…xn“Y=“y1y2…ym“則當(dāng)n=m且x1=y1，…，xn=ym時(shí)，稱X=Y；當(dāng)下列條件之一成立時(shí)，稱X＜Y：⑴n＜m，且xi=yi（i=1，2，…，n）；⑵存在某個(gè)k≤m

9、in(m，n)，使得xi=yi（i=1，2，…，k1），xk＜yk。?改進(jìn)的模式匹配算法中改進(jìn)的模式匹配算法中next[j]的求法的求法用next[j]表示tj對(duì)應(yīng)的k值（1≤j≤m），其定義如下：?數(shù)組的基本操作數(shù)組的基本操作數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。因此，在數(shù)組中通常只有兩種操作：⑴讀?。航o定一組下標(biāo)，讀取相應(yīng)的數(shù)組元素；0j=1maxk|1≤k＜j且＂t1t2…tk1＂=＂tj