安徽農(nóng)業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專升本串、數(shù)組和廣義表市公開課特等獎(jiǎng)市賽課微課一等獎(jiǎng)?wù)n件

可表示為：（a1,a2,……,an）線性結(jié)構(gòu)第2章線性表第3章棧和隊(duì)列第4章串、數(shù)組和廣義表

第1頁(yè)串比較，strcmp(chars1,chars2)串復(fù)制，strcpy(charto,charfrom)串連接，strcat(charto,charfrom)求串長(zhǎng)，strlen(chars)

……調(diào)用標(biāo)準(zhǔn)庫(kù)函數(shù)#include<string.h>補(bǔ)充：C語(yǔ)言中慣用串運(yùn)算第2頁(yè)第4章串、數(shù)組和廣義表4.1串4.2數(shù)組4.3廣義表

教學(xué)內(nèi)容第3頁(yè)1.掌握串存放方法，了解串兩種模式匹配算法；2.明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，掌握數(shù)組存放時(shí)地址計(jì)算方法，了解幾個(gè)特殊矩陣壓縮存放方法。

教學(xué)目標(biāo)1.了解串存放方法，了解串兩種模式匹配算法，重點(diǎn)掌握BF算法。2.明確數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)特點(diǎn)，掌握數(shù)組地址計(jì)算方法，了解幾個(gè)特殊矩陣壓縮存放方法。3.掌握廣義表定義、性質(zhì)及其GetHead和GetTail操作。第4頁(yè)4.1串串(String)----零個(gè)或多個(gè)字符組成有限序列串名串值串長(zhǎng)n空串n=0第5頁(yè)a=‘BEI’,b=‘JING’

c=‘BEIJING’

d=‘BEIJING’子串字符位置主串子串位置串相等空格串第6頁(yè)數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:基本操作:(1)

StrAssign(&T,chars)//串賦值(2)StrCompare(S,T)//串比較(3)StrLength(S)//求串長(zhǎng)(4)Concat(&T,S1,S2)//串聯(lián)ADTString{串抽象數(shù)據(jù)類型第7頁(yè)(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)//串銷毀}ADTString(8)第8頁(yè)次序存放鏈?zhǔn)酱娣糯娣沤Y(jié)構(gòu)第9頁(yè)typedefstruct{char*ch;//若串非空,則按串長(zhǎng)分配存放區(qū),//不然ch為NULLintlength;//串長(zhǎng)度}HString;

次序存放表示第10頁(yè)鏈?zhǔn)酱娣疟硎镜?1頁(yè)#defineCHUNKSIZE80//可由用戶定義塊大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串頭指針和尾指針

intcurlen;//串當(dāng)前長(zhǎng)度}LString;

鏈?zhǔn)酱娣疟硎镜?2頁(yè)可將多個(gè)字符存放在一個(gè)結(jié)點(diǎn)中，以克服其缺點(diǎn)優(yōu)點(diǎn)：操作方便缺點(diǎn)：存放密度較低實(shí)際分配存放位串值所占存放位存放密度=鏈?zhǔn)酱娣疟硎镜?3頁(yè)算法目標(biāo)：BF算法（又稱古典、經(jīng)典、樸素、窮舉）KMP算法（特點(diǎn)：速度快）算法種類：確定主串中所含子串第一次出現(xiàn)位置（定位）即怎樣實(shí)現(xiàn)教材P72Index(S,T,pos)函數(shù)串模式匹配算法第14頁(yè)

S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指針回溯BF算法設(shè)計(jì)思想第15頁(yè)將主串第pos個(gè)字符和模式第一個(gè)字符比較，若相等，繼續(xù)逐一比較后續(xù)字符；若不等，從主串下一字符起，重新與模式第一個(gè)字符比較。直到主串一個(gè)連續(xù)子串字符序列與模式相等。返回值為S中與T匹配子序列第一個(gè)字符序號(hào)，即匹配成功。不然，匹配失敗，返回值0BF算法設(shè)計(jì)思想Index(S,T,pos)第16頁(yè)intIndex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]=T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}BF算法描述（算法4.1）第17頁(yè)若n為主串長(zhǎng)度，m為子串長(zhǎng)度，最壞情況是BF算法時(shí)間復(fù)雜度主串前面n-m個(gè)位置都部分匹配到子串最終一位，即這n-m位各比較了m次最終m位也各比較了1次總次數(shù)為：(n-m)*m+m＝(n-m+1)*m若m<<n，則算法復(fù)雜度O(n*m)例：S=‘0000000001’，T=‘0001’，pos=1第18頁(yè)KMP（KnuthMorrisPratt）算法/~knuth/《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第1卷基本算法》

98元《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第2卷半數(shù)值算法》98元《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第3卷排序與查找》98元第19頁(yè)利用已經(jīng)部分匹配結(jié)果而加緊模式串滑動(dòng)速度？且主串S指針i無(wú)須回溯！可提速到O(n+m)！S=‘a(chǎn)babcabcacbab’T=‘a(chǎn)bcac’S=‘a(chǎn)b

abca

bcacbab’T=‘a(chǎn)bca

c’S=‘a(chǎn)b

abcabcacbab’T=‘a(chǎn)bcac’iiikk

a

b

aa

b

ckiiKMP算法設(shè)計(jì)思想（了解）第20頁(yè)串操作應(yīng)用舉例－－文本編輯文本可被看作一個(gè)字符串，稱為文本串頁(yè)則是文本串子串行又是頁(yè)子串。頁(yè)號(hào)起始行號(hào)頁(yè)表…………行號(hào)起始地址長(zhǎng)度行表…………第21頁(yè)本節(jié)所討論數(shù)組與高級(jí)語(yǔ)言中數(shù)組區(qū)分：高級(jí)語(yǔ)言中數(shù)組是次序結(jié)構(gòu)；而本章數(shù)組既能夠是次序，也能夠是鏈?zhǔn)浇Y(jié)構(gòu)，用戶可依據(jù)需要選擇。4.2數(shù)組第22頁(yè)數(shù)組抽象數(shù)據(jù)類型數(shù)據(jù)對(duì)象:數(shù)據(jù)關(guān)系:ADTArray{第23頁(yè)基本操作:

(1)InitArray(&A,n,bound1,boundn)//結(jié)構(gòu)數(shù)組A(2)DestroyArray(&A)//銷毀數(shù)組A(3)Value(A,&e,index1,…,indexn)//取數(shù)組元素值

(4)Assign(A,&e,index1,…,indexn)//給數(shù)組元素賦值}ADTArray第24頁(yè)一維數(shù)組352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la第25頁(yè)二維數(shù)組第26頁(yè)以行序?yàn)橹餍駽,PASCAL數(shù)組次序存放第27頁(yè)以列序?yàn)橹餍騀ORTRAN第28頁(yè)

a[n][m]設(shè)數(shù)組開始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二維數(shù)組行序優(yōu)先表示第29頁(yè)①②③三維數(shù)組按頁(yè)/行/列存放，頁(yè)優(yōu)先次序存放

第30頁(yè)a[m1][m2][m3]

各維元素個(gè)數(shù)為

m1,m2,m3

下標(biāo)為i1,i2,i3數(shù)組元素存放位置：

LOC(i1,i2,i3)=a+

i1*m2*m3+i2*m3+i3前i1頁(yè)總元素個(gè)數(shù)第i1頁(yè)前i2行總元素個(gè)數(shù)第i2行前i3列元素個(gè)數(shù)三維數(shù)組第31頁(yè)

各維元素個(gè)數(shù)為

m1,m2,m3,…,mn

下標(biāo)為i1,i2,i3,…,in

數(shù)組元素存放位置：

n維數(shù)組第32頁(yè)n維數(shù)組第33頁(yè)設(shè)有一個(gè)二維數(shù)組A[m][n]按行優(yōu)先次序存放，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。設(shè)數(shù)組元素A[i][j]存放在起始地址為L(zhǎng)oc(i,j)存放單元中∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.練習(xí)第34頁(yè)設(shè)有二維數(shù)組A[10,20]，其每個(gè)元素占兩個(gè)字節(jié)，A[0][0]存放地址為100，若按行優(yōu)先次序存放，則元素A[6,6]存放地址為

，按列優(yōu)先次序存放，元素A[6,6]存放地址為

。練習(xí)352232(6*20+6)*2+100=352(6*10+6)*2+100=232第35頁(yè)1.什么是壓縮存放？若多個(gè)數(shù)據(jù)元素值都相同，則只分配一個(gè)元素值存放空間，且零元素不占存放空間。2.什么樣矩陣能夠壓縮？

一些特殊矩陣，如：對(duì)稱矩陣，對(duì)角矩陣，三角矩陣，稀疏矩陣等。3.什么叫稀疏矩陣？矩陣中非零元素個(gè)數(shù)較少（普通小于5%）特殊矩陣壓縮存放第36頁(yè)4.3廣義表

廣義表（列表）：n(0)個(gè)表元素組成有限序列，記作LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它能夠是表(稱為子表)，能夠是數(shù)據(jù)元素(稱為原子)。

n為表長(zhǎng)度。n=0廣義表為空表。第37頁(yè)線性表成份都是結(jié)構(gòu)上不可分單元素廣義表成份能夠是單元素，也能夠是有結(jié)構(gòu)表線性表是一個(gè)特殊廣義表廣義表不一定是線性表，也不一定是線性結(jié)構(gòu)廣義表與線性表區(qū)分？第38頁(yè)廣義表基本運(yùn)算（1）求表頭GetHead(L)：非空廣義表第一個(gè)元素，能夠是一個(gè)單元素，也能夠是一個(gè)子表（2）求表尾GetTail(L)：非空廣義表除去表頭元素以外其它元素所組成表。表尾一定是一個(gè)表第39頁(yè)練習(xí)A=()

GetHead和GetTail均無(wú)定義A=(a,b)

GetHead(A)=aGetTail(A)=(b)

A=(a)

GetHead(A)=aGetTai