1、可表示為：（a1 , a2 , , an） 線性結構第2章 線性表第3章 棧和隊列第4章 串、數組和廣義表 串比較，strcmp(char s1,char s2) 串復制，strcpy(char to,char from)串連接，strcat(char to,char from) 求串長，strlen(char s) 調用標準庫函數 #include補充：C語言中常用的串運算第4章串、數組和廣義表 4.1 串4.2 數組4.3 廣義表 教學內容1. 掌握串的存儲方法，理解串的兩種模式匹配算法；2. 明確數組和廣義表這兩種數據結構的特點，掌握數組存儲時地址計算方法，了解幾種特殊矩陣的壓縮存儲方法

2、。 教學目標1. 了解串的存儲方法，理解串的兩種模式匹配算法，重點掌握BF算法。2. 明確數組和廣義表這兩種數據結構的特點，掌握數組地址計算方法，了解幾種特殊矩陣的壓縮存儲方法。 3.掌握廣義表的定義、性質及其GetHead和GetTail的操作。4.1 串串(String)-零個或多個字符組成的有限序列串名串值串長n空串n=0a=BEI, b=JING c=BEIJING d=BEI JING子串字符位置主串子串位置串相等空格串數據對象:數據關系:基本操作:(1) StrAssign (&T,chars) /串賦值(2) StrCompare (S,T) /串比較(3) StrLength

3、(S) /求串長(4) Concat(&T,S1,S2) /串聯(lián) ADT String 串的抽象數據類型(5) SubString(&Sub,S,pos,len) /求子串(6) StrCopy(&T,S) /串拷貝(7) StrEmpty(S) /串判空(8) ClearString (&S) /清空串(9) Index(S,T,pos) /子串的位置(10) Replace(&S,T,V) /串替換(11) StrInsert(&S,pos,T) /子串插入(12) StrDelete(&S,pos,len) /子串刪除(13) DestroyString(&S) /串銷毀ADT Stri

4、ng(8) 順序存儲 鏈式存儲串的存儲結構typedef struct char *ch; /若串非空,則按串長分配存儲區(qū), /否則ch為NULL int length; /串長度HString; 順序存儲表示鏈式存儲表示#define CHUNKSIZE 80 /可由用戶定義的塊大小typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head,*tail; /串的頭指針和尾指針 int curlen; /串的當前長度LString; 鏈式存儲表示可將多個字符存放在一個結點中

5、，以克服其缺點優(yōu)點：操作方便缺點：存儲密度較低實際分配的存儲位串值所占的存儲位存儲密度=鏈式存儲表示算法目的：BF算法（又稱古典的、經典的、樸素的、窮舉的）KMP算法（特點：速度快）算法種類：確定主串中所含子串第一次出現的位置（定位）即如何實現教材P72 Index(S,T,pos)函數串的模式匹配算法 S : a b a b c a b c a c b a bT : a b cijS : a b a b c a b c a c b a b T : a b cS : a b a b c a b c a c b a bT : a b ci指針回溯BF算法設計思想將主串的第pos個字符和模式的第一

6、個字符比較， 若相等，繼續(xù)逐個比較后續(xù)字符； 若不等，從主串的下一字符起，重新與模式的第一個字符比較。 直到主串的一個連續(xù)子串字符序列與模式相等 。返回值為S中與T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值 0BF算法設計思想Index(S,T,pos)int Index(Sstring S,Sstring T,int pos) i=pos; j=1; while (i=S 0 & j T 0 ) return iT0; else return 0;BF算法描述（算法4.1）若n為主串長度，m為子串長度，最壞情況是BF算法時間復雜度主串前面n-m個位置都部分匹配到子串的最

7、后一位，即這n-m位各比較了m次最后m位也各比較了1次總次數為：(n-m)*m+m(n-m+1)*m若m 0 a, i = 0 a+i*la二維數組以行序為主序C, PASCAL數組的順序存儲以列序為主序FORTRANanm設數組開始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k二維數組的行序優(yōu)先表示三維數組按頁/行/列存放，頁優(yōu)先的順序存儲 am1m2 m3 各維元素個數為 m1, m2, m3 下標為 i1, i2, i3的數組元素的存儲位置： LOC ( i1, i2, i3 ) = a + i1* m2 * m3 + i2* m3 +

8、 i3前i1頁總元素個數第i1頁的前i2行總元素個數第 i2 行前 i3 列元素個數三維數組 各維元素個數為 m1, m2, m3, , mn 下標為 i1, i2, i3, , in 的數組元素的存儲位置： n維數組n維數組設有一個二維數組Amn按行優(yōu)先順序存儲，假設A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注(10)表示用10進制表示。設數組元素Aij存放在起始地址為Loc ( i, j ) 的存儲單元中 Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 644 + 2 * n +

9、 2 = 676. n = ( 676 - 2 - 644 ) / 2 = 15 Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.練習設有二維數組A10,20，其每個元素占兩個字節(jié)， A00存儲地址為100，若按行優(yōu)先順序存儲，則元素A6,6的存儲地址為 ，按列優(yōu)先順序存儲，元素A6,6的存儲地址為 。 練習352232(6*20+6)*2+100=352(6*10+6)*2+100=2321. 什么是壓縮存儲？若多個數據元素的值都相同，則只分配一個元素值的存儲空間，且零元素不占存儲空間。2. 什么樣的矩陣能夠壓縮？

10、一些特殊矩陣，如：對稱矩陣，對角矩陣，三角矩陣，稀疏矩陣等。3. 什么叫稀疏矩陣？矩陣中非零元素的個數較少（一般小于5%）特殊矩陣的壓縮存儲4.3 廣義表 廣義表（列表）： n ( 0 )個表元素組成的有限序列， 記作LS = (a0, a1, a2, , an-1) LS是表名，ai是表元素，它可以是表 (稱為子表)，可以是數據元素(稱為原子)。 n為表的長度。n = 0 的廣義表為空表。線性表的成分都是結構上不可分的單元素廣義表的成分可以是單元素，也可以是有結構的表線性表是一種特殊的廣義表廣義表不一定是線性表，也不一定是線性結構廣義表與線性表的區(qū)別？廣義表的基本運算（1）求表頭GetHea

11、d(L)：非空廣義表的第一個元素，可以是一個單元素，也可以是一個子表（2）求表尾GetTail(L)：非空廣義表除去表頭元素以外其它元素所構成的表。表尾一定是一個表練習A=( ) GetHead和GetTail均無定義A=(a,b) GetHead(A)=a GetTail(A)=(b) A=(a) GetHead(A)=a GetTail(A)=( ) A=(a) GetHead(A)=(a) GetTail(A)=( ) GetHead(GetTail(GetHead(GetTail(GetTail(A) A=(a,b,(c,d),(e,(f,g) d有次序性有長度有深度可遞歸可共享一個直接前驅和一個直接后繼表中元素個數表中括號的重數自己可以作為自己的子表可以為其他廣義表所共享廣義表的特點E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E為遞歸表1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(a, E)n=0，因為A是空表n=1，表中元素e