1、8/22/2020,1,第二章 常見數(shù)據(jù)結(jié)構(gòu),計算機與信息學(xué)院 林敏 Email:jsjxy_,8/22/2020,2,第二章 常見數(shù)據(jù)結(jié)構(gòu),2.1 數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu),2.2 數(shù)組,2.3 串,8/22/2020,3,2.1數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu),2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型 數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項 數(shù)據(jù)對象 數(shù)據(jù)類型,8/22/2020,4,2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型,1.數(shù)據(jù) 是對客觀事物的符號表示。 在計算機科學(xué)中是指所有輸入到計算機中并被計算機程序處理的符號的總稱 。 如：學(xué)生的數(shù)據(jù)；圖書館的數(shù)據(jù)；,8/22/2020,5,2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型,2.數(shù)據(jù)元素

2、是數(shù)據(jù)的基本單位，每一數(shù)據(jù)元素所攜信息對應(yīng)研究對象的一個實體。 有時，數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。,數(shù)據(jù),8/22/2020,6,2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型,3.數(shù)據(jù)項 構(gòu)成數(shù)據(jù)元素的最小單位。,數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項,8/22/2020,7,2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型,4.數(shù)據(jù)對象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是一個數(shù)據(jù)的子集。 如：整數(shù)集合：0，+1，-1，+2，-2， 又如： 字符數(shù)據(jù)集合： A，B，C，Z。,8/22/2020,8,2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型,5.數(shù)據(jù)類型 是一個值的集合以及定義在這個值集上的一組操作的總稱。 如：C/C+語言中的int、char

3、、double、bool等。,8/22/2020,9,2.1.1數(shù)據(jù)、數(shù)據(jù)元素與數(shù)據(jù)類型,數(shù)據(jù)類型的分類 高級語言中的數(shù)據(jù)類型分為兩大類： 1.原子類型，其值不可分解。如C語言中的標準類型（整型、實型、字符型、）。 2.結(jié)構(gòu)類型，其值是由若干成分按某種結(jié)構(gòu)組成的,如結(jié)構(gòu)體(struct)類型數(shù)據(jù)。,8/22/2020,10,2.1.2抽象數(shù)據(jù)類型,抽象數(shù)據(jù)類型（ADT)是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作，與數(shù)據(jù)類型本質(zhì)上是同一概念。 ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象； 數(shù)據(jù)關(guān)系； 基本操作; 例：定義三角形、復(fù)數(shù)的抽象數(shù)據(jù)類型。,8/22/2020,11,2.1.3數(shù)據(jù)結(jié)構(gòu),定義：

4、是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 通俗的說：既要表示數(shù)據(jù)元素的結(jié)構(gòu)，又要表示數(shù)據(jù)元素之間的關(guān)系,DS=(D,R),8/22/2020,12,2.1.3數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)涉及以下幾個方面內(nèi)容： 1.數(shù)據(jù)的邏輯結(jié)構(gòu) 2.數(shù)據(jù)的存儲結(jié)構(gòu) 3.數(shù)據(jù)的運算與實現(xiàn),8/22/2020,13,2.1.3數(shù)據(jù)結(jié)構(gòu),1.數(shù)據(jù)的邏輯結(jié)構(gòu) 表示數(shù)據(jù)元素間的邏輯關(guān)系,線性結(jié)構(gòu),集合,樹,圖,8/22/2020,14,2.1.3數(shù)據(jù)結(jié)構(gòu),1.數(shù)據(jù)的邏輯結(jié)構(gòu),線性結(jié)構(gòu):存在一對一的關(guān)系，如表，隊列，棧，數(shù)組，串,非線性結(jié)構(gòu)：不存在一對一的關(guān)系，如集合，圖，樹形結(jié)構(gòu),8/22/2020,15,2.1.3數(shù)據(jù)

5、結(jié)構(gòu),2.數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)元素以及數(shù)據(jù)元素之間的關(guān)系在內(nèi)存中 的表示，也稱為物理結(jié)構(gòu)或存儲映像。 主要有以下幾種： 順序存儲 鏈式存儲 索引存儲和散列存儲,8/22/2020,16,2.1.3數(shù)據(jù)結(jié)構(gòu),3.數(shù)據(jù)的運算及實現(xiàn) 常見的運算有檢索，插入，刪除，更新，排序等 運算的具體實現(xiàn)與所采用的存儲結(jié)構(gòu)有關(guān) 例：隊列可以用順序存儲也可以使用鏈式存儲，但采用順序存儲與采用鏈式存儲時算法的實現(xiàn)時不同的。,8/22/2020,17,2.2數(shù)組,2.2.1數(shù)組定義及運算 定義：由一組數(shù)據(jù)類型相同的數(shù)據(jù)元素組 成，并采用順序存儲的線性結(jié)構(gòu)。 特點： 元素個數(shù)固定，順序排列，根據(jù)下標隨機訪問，下標規(guī)定了數(shù)

6、組的上下界 數(shù)組的運算：讀取，寫入,8/22/2020,18,2.2.2數(shù)組的順序存儲結(jié)構(gòu),數(shù)組在內(nèi)存中采用順序存儲結(jié)構(gòu),8/22/2020,19,2.2.2數(shù)組的順序存儲結(jié)構(gòu),多維數(shù)組的順序存儲方式,行式主序優(yōu)先,列式優(yōu)先存儲,Loc(aij)=loc(a11)+(i-1)*n+j-1)* size,8/22/2020,20,2.2.2數(shù)組的順序存儲結(jié)構(gòu),計算數(shù)組元素aij的地址 例：數(shù)組B1.10,-2.6,2.8以行為主序順序存儲，設(shè)基地址為100，每個元素的存儲長度為3,試求元素B5,0,7的存儲地址?,B5,0,7 =100+(5-1)*9*7+(0-(-2)*7+(7-2)*3 =

7、913,8/22/2020,21,2.2.3特殊矩陣的壓縮存儲,(1)對角矩陣,對角矩陣,壓縮存儲,aii=aii,8/22/2020,22,2.2.3特殊矩陣的壓縮存儲,(2)三對角矩陣,k=(i-1)*3-1+j-i+2 =2*(i-1)+j,8/22/2020,23,2.2.3特殊矩陣的壓縮存儲,(3)上三角矩陣,A=,a11 a12 a13 a1n a22 a23 a2n a33 a3n ann,8/22/2020,24,2.2.3特殊矩陣的壓縮存儲,(4)下三角矩陣,8/22/2020,25,2.2.3特殊矩陣的壓縮存儲,(5)對稱矩陣 aij=aji 轉(zhuǎn)換成上三角矩陣或下三角矩陣來

8、實現(xiàn),8/22/2020,26,2.2.3特殊矩陣的壓縮存儲,(6)稀疏矩陣：指矩陣中大多數(shù)元素為零的矩陣。,8/22/2020,27,2.2.3特殊矩陣的壓縮存儲,(6)稀疏矩陣： #define MAXSIZE 1000 /*非零元素的個數(shù)最多為1000*/ typedef struct int row, col; /*該非零元素的行下標和列下標*/ ElementType e； /*該非零元素的值*/ Triple; typedef struct Triple dataMAXSIZE+1; /* 非零元素的三元組表 。int m, n, len; /*矩陣的行數(shù)、列數(shù)和非零元素的個數(shù)*/

9、 TSMatrix；,8/22/2020,28,2.3.1串的基本概念,串:由零個或多個字符組成的有限序列。 記為： S=“a1a2a3a4a5a6a7a8an”(n0),子串,子串的位置：子串a(chǎn)2a3的位置為2,字符的位置：字符a5的位置為5,主串,8/22/2020,29,2.3.1串的基本概念,空串： n=0時的串為空串 空格串：由一個或多個稱為空格的特殊字 符組成的串。例：S=“ ” 串相等：長度相等且對應(yīng)的字符也相等,8/22/2020,30,2.3.1串的基本概念,串的基本運算 (1) 串賦值 StrAssign(s,chars)：建立串s,其值等于字符 序列s (2) 復(fù)制串St

10、rCopy(s,t)：將串t復(fù)制到串s (3)串比較 StrCompare(s,t)：若st返回正數(shù)，s=t返回0，st返回負數(shù) (4) 求串長 StrLength(s)：返回串s長度 (5)串聯(lián)接 concat(s,t)：返回s與t聯(lián)接后，長度為length(s)+length(t)的新串 (6)求子串 substr(s,i,n)：返回主串s中，從第i個字符開始的連續(xù)n個字符序列的字串，1ilength(s),0nlength(s)-i+1,8/22/2020,31,2.3.1串的基本概念,串的基本運算 (7)子串插入 StrInsert(s,i,t)：在s串的第i個字符之前插入串t，其中1

11、ilength(s)+1 (8)刪除子串 StrDelete(s,i,n)：從串s中刪去從第i個字符開始長度為n的子串，其中1ilength(s)，0nlength(s)-i+1 (9) 子串定位 StrIndex(s,t)：若t是主串s的子串，則返回t在s中第一次出現(xiàn)的位置，否則返回0 (10) 串置換 StrReplace(s,t,v)：以子串v替換所有s中出現(xiàn)且不重疊的子串t (11)判空串 empty(s)：若串s為空串，返回true，否則返回false (12)串清空 clear(s)：將串s置為空串,8/22/2020,32,2.3.2串的定長順序存儲及運算實現(xiàn),用一組地址連續(xù)的存

12、儲單元存儲串的字符序列 ,與計算機編址有關(guān),緊縮方式：按字編址，每個字節(jié)存放一個字符,非緊縮方式：按字編址，每個字存放一個字符,8/22/2020,33,2.3.2串的定長順序存儲及運算實現(xiàn),單字節(jié)存儲方式：按字節(jié)編址,按字節(jié)編址,每個字節(jié)存放一個字符,8/22/2020,34,2.3.2串的定長順序存儲及運算實現(xiàn),C語言中定義字符串 例：char s18=“abc” char s28=a,b,c,0 char s38=a,b,c char *s4=“abc” char s58;s50=a;s51=b;s52=0,8/22/2020,35,2.3.2串的定長順序存儲及運算實現(xiàn),串數(shù)據(jù)類型定義：

13、 方法一： #define maxlen 100/ 串的最大長度 typedef char string100; 方法二: #define maxlen 100/ 串的最大長度 typedef struct char chmaxlen; int len; / 指示當前串長度 sqstring;,8/22/2020,36,2.3.2串的定長順序存儲及運算實現(xiàn),基本運算的實現(xiàn)： （1）求串的長度 int StrLength(sqstring ss) return(ss.len); 思考：如果使用的是第一種定義串類型， 那么求串長的代碼怎么寫？,8/22/2020,37,2.3.2串的定長順序存儲及

14、運算實現(xiàn),基本運算的實現(xiàn)： （2）串賦值strassign.c void StrAssign(sqstring *to,char *from) int i=0; while(*(from+i)!=0) to-chi=*(from+i) ; i+; to-chi=0 ; to-len=i; ,#define maxlen 100/ 串的最大長度 typedef struct char chmaxlen; int len; / 指示當前串長度 sqstring;,調(diào)用此函數(shù)：sqstring to; StrAssign( l-len=s.len; for (i=0;ichi=s.chi; / 先復(fù)

15、制串s if (s.len+t.lenmaxlen) / 串s與串t長度總和超過最大串長, 追加復(fù)制部分t for (i=0;ichs.len+i=t.chi; l-len=maxlen; if (s.len+t.lenchs.len+i=t.chi; l-len=s.len+t.len; ,8/22/2020,39,2.3.2串的定長順序存儲及運算實現(xiàn),基本運算的實現(xiàn)： （4）求子串substr.c void substr(sqstring *t,sqstring s,int i,int len) int j; / 子串開始位置無效 if (is.len-1)printf(“ninvalid

16、 place);return; / 子串長度無效 if (lens.len-i)printf(ninvalid len);return; for (j=0;jchj=s.chj+i; t-len=len; t-chlen=0; ,8/22/2020,40,2.3.3 模式匹配,子串定位操作通常稱為串的模式匹配，其中子串稱為模式 例：主串”ababcabcacbab”與模式”abcac”的一般匹配過程：,ababcabcacbab abcac,8/22/2020,41,2.3.3 模式匹配,（1）串的順序存儲結(jié)構(gòu)的模式匹配一般算法：strindex.c int strindex(sqstring

17、 s,sqstring t) int i=0,j=0; while (is.len) ,最壞的時候，時間復(fù)雜度為O(n*m),8/22/2020,42,2.3.3 模式匹配,(2)串的模式匹配的改進 例：主串”ababcabcacbab”與模式”abcac”的改進匹配過程：用三趟匹配即完成,i=2,j=2,i=6,j=4,abcac,abcac,abcac,成功,8/22/2020,43,2.3.3 模式匹配,(2)串的模式匹配的改進 分析：改進的思想主題轉(zhuǎn)化為，當匹配失敗時，到底模式的哪一位繼續(xù)移動上來匹配呢？ 即： 1.主串不回溯，只會向前 2.模式的某一位替上來，與主串匹配失敗位再比較,

18、8/22/2020,44,2.3.3 模式匹配,(3)KMP算法 我們來推理下：如果Si和tj匹配失敗，將tk位移上來 與sj比較,t0t1tk-1=si-ksi-k+1 si-1,tj-kti-k+1tj-1=si-ksi-k+1 si-1,t0t1tk-1=tj-kt1tj-1,(0kj),8/22/2020,45,(3)KMP算法,next(j)函數(shù) 模式t0t1tjtm在tj為匹配失敗時，假設(shè)下 一位應(yīng)該與next(j)位相比較,8/22/2020,46,(3)KMP算法,例：求模式abaabcac的next(前綴函數(shù))值,next(j)=,maxk|0kj且t0.tk-1=tj-k.

19、tj-1比較首尾字符串,-1 當j=0時,0 其它情況,8/22/2020,47,(3)KMP算法,求匹配過程 例 ： 主串：acabaabaabcacaabc 子串：abaabcac 匹配過程描述： 先求出模式的next函數(shù) i=0;j=0;初始化主串指示器i和模式指示器j if (j=-1 or si=tj )i+;j+ 比較下個字符 else j=nextj;模式nextj位與i比較； 判斷是否已經(jīng)匹配成功,否則轉(zhuǎn),8/22/2020,48,(3)KMP算法,模式匹配的KMP算法： int index_KMP(sqstring s,sqstring t,int next) int i=0

20、,j=0; while (is.len) ,算法的復(fù)雜度是O(n+m),8/22/2020,49,(3)KMP算法,next函數(shù)求法 已經(jīng)模式t0t1.tk.tJ-1tJtJ+1, tJ位的next(j)=k; 則可知： t0t1.tk-1=tJ-ktJ-k+1 . tJ-1; 于是將其與自身進行模式匹配,發(fā)現(xiàn)：當主串tJ與模式tk比較時，說明之前已成功匹配到了第k-1位 ，并且不可能存在比這更多的位數(shù)； 于是求出tj位的next(j)=k;,8/22/2020,50,(3)KMP算法,next函數(shù)求法,于是得出next函數(shù)的求法思想： 將模式與自身按照KMP算法進行匹配 第一位的next(0)=-1; 當主串第J位第一次比較時，假設(shè)此時與子串第K位比較，于是求得此時next(j)=k；繼續(xù)按照KMP算法比較,例：abaabcac,8/22/2020,51,(3)KMP算法,使用類似kmp的算法求nex