線(xiàn)性表與字符串-2

1、數(shù)組線(xiàn)性表字符串第二章 線(xiàn)性表和字符串1數(shù)組二元組的一個(gè)集合。存儲(chǔ)于一個(gè)連續(xù)存儲(chǔ)空間中的相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素的集合；通過(guò)數(shù)組元素的下標(biāo)，可以得到存放該數(shù)組元素的存儲(chǔ)地址，從而可以訪(fǎng)問(wèn)該數(shù)組元素的值。一維數(shù)組向量具有相同類(lèi)型的n(n0)個(gè)元素的有限序列。n為數(shù)組長(zhǎng)度或數(shù)組大??；n=0為空數(shù)組。各數(shù)組元素處于一個(gè)線(xiàn)性聚集或線(xiàn)性表中。每個(gè)元素的數(shù)據(jù)類(lèi)型相同；占有相同的存儲(chǔ)空間；每個(gè)元素的開(kāi)始位置到相鄰元素的開(kāi)始位置的距離相等。2一維數(shù)組的特點(diǎn)數(shù)組中的每一個(gè)元素在數(shù)組中的位置由下標(biāo)唯一確定；除第一個(gè)元素外，其它元素有且僅有一個(gè)直接前驅(qū)，第一個(gè)元素沒(méi)有前驅(qū)。除最后一個(gè)元素外，其它元素有且僅有一個(gè)直接后

2、繼，最后一個(gè)元素沒(méi)有后繼。 示例長(zhǎng)度為10，每個(gè)元素占l個(gè)存儲(chǔ)字，起始地址為a。3數(shù)組的定義和初始化創(chuàng)建數(shù)組靜態(tài)數(shù)組在聲明數(shù)組對(duì)象時(shí)顯式地定義了數(shù)組長(zhǎng)度；定義了數(shù)組的下標(biāo)范圍；對(duì)數(shù)組各元素賦值；存儲(chǔ)空間不隨程序的執(zhí)行而改變。動(dòng)態(tài)數(shù)組用指針聲明數(shù)組；在指針中只存放數(shù)組第一個(gè)元素的地址，所以?xún)H占用一個(gè)存儲(chǔ)空間；用+和- -可訪(fǎng)問(wèn)數(shù)組下一個(gè)元素或前一個(gè)元素。數(shù)組的標(biāo)準(zhǔn)操作存儲(chǔ)抽取示例Positioni=Positioni-1+Numberi-1賦值符號(hào)右邊表示按下標(biāo)i-1直接提取相應(yīng)數(shù)組元素的值；賦值符號(hào)左邊表示按下標(biāo)i把右邊的計(jì)算結(jié)果直接存儲(chǔ)到相應(yīng)數(shù)組元素中。二維數(shù)組矩陣由n個(gè)行向量m個(gè)列向量所組

3、成的向量。共有n*m個(gè)數(shù)組元素；元素 jk處于第j個(gè)行向量的第k個(gè)列向量；在行和列方向上各有一個(gè)直接前驅(qū)和直接后繼。某一個(gè)數(shù)組元素在數(shù)組中的位置需由下標(biāo)的二元組jk唯一確定。三維數(shù)組共有m1*m2*m3個(gè)數(shù)組元素；每個(gè)數(shù)組元素同時(shí)處于三個(gè)向量之中；最多有三個(gè)直接前驅(qū)和直接后繼。某一個(gè)數(shù)組元素在數(shù)組中的位置需由下標(biāo)的三元組ijk唯一確定。 二維數(shù)組 三維數(shù)組行向量 下標(biāo) i 頁(yè)向量 下標(biāo) i列向量 下標(biāo) j 行向量 下標(biāo) j 列向量 下標(biāo) k7n維數(shù)組am1m2.mn 總共有m1*m2*mn個(gè)數(shù)組元素；每一個(gè)數(shù)組元素ai1i2.in處于n個(gè)向量之中；每一個(gè)數(shù)組元素的位置由下標(biāo)的n元組i1i2.i

4、n 唯一確定。數(shù)組連續(xù)存儲(chǔ)方式在實(shí)現(xiàn)數(shù)組存儲(chǔ)時(shí)，通常是按各個(gè)數(shù)組元素的排列順序，順次存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)域內(nèi)，得到一個(gè)所有數(shù)組元素的線(xiàn)性序列。一維數(shù)組第一個(gè)元素的起始位置為，每一個(gè)數(shù)組元素的存儲(chǔ)大小為l。任一數(shù)組元素的存儲(chǔ)地址LOC(i)：LOC(1) = LOC(0) + l =+ lLOC(2) = LOC(1) + l =+ 2*l，LOC(i) = LOC ( i -1 ) + l =+ i*l9行優(yōu)先順序所有數(shù)組元素按行向量依次排列，第i+1個(gè)行向量緊跟在第i個(gè)行向量后面。列優(yōu)先順序所有數(shù)組元素按列向量依次排列，第j+1個(gè)列向量緊跟在第j個(gè)列向量后面。二維數(shù)組10行優(yōu)先 LOC (

5、 j, k ) = LOC ( j, 0 )+k*l/第j行開(kāi)始位置加k*l = LOC ( j-1, 0 )+m*l+k *l /第j-1行開(kāi)始位置加該行元素個(gè)數(shù)m*l加k *l = LOC ( j-2, 0 )+2*m*l +k*l /前推到第j-2行 = = LOC (0, 0 )+j*m*l +k*l /前推到第0行 = +( j * m + k )*l設(shè)二維數(shù)組anm第一個(gè)元素a00在相應(yīng)的一維數(shù)組中存放于第一個(gè)位置，其地址為，每個(gè)元素占l個(gè)元素的空間。則任一數(shù)組元素ajk在相應(yīng)一維數(shù)組中的存放地址利用遞推公式計(jì)算：設(shè)三維數(shù)組am1m2m3中，對(duì)于任一數(shù)組元素a ijk在一維數(shù)組中存

6、放的位置為：頁(yè)優(yōu)先 LOC ( i, j, k ) = LOC ( i, 0 , 0 )+j*m3*l+k*l = LOC ( i-1, 0, 0 )+m2*m3*l+j*m3*l+k*l = LOC ( i-2, 0, 0 )+2*m2*m3*l+j*m3*l+k*l = = LOC (0, 0 , 0 )+i*m2*m3*l+j*m3*l+k*l = +(i*m2*m3+j*m3+k)*l三維數(shù)組線(xiàn)性表線(xiàn)性聚集，一個(gè)存儲(chǔ)n(n0)個(gè)表項(xiàng)的序列。n是表的長(zhǎng)度，可以是任意整數(shù)。n=0為空表。表的長(zhǎng)度隨增加或刪除某些表項(xiàng)而發(fā)生改變。每個(gè)表項(xiàng)都是單個(gè)對(duì)象，其數(shù)據(jù)類(lèi)型相同。各個(gè)表項(xiàng)通過(guò)其位置來(lái)訪(fǎng)問(wèn)；

7、第一個(gè)表項(xiàng)位于表的頭部，最后一個(gè)表項(xiàng)位于表的尾部。除最后一個(gè)表項(xiàng)之外，其它每個(gè)表項(xiàng)有且僅有一個(gè)直接后繼。13線(xiàn)性表的特點(diǎn)特點(diǎn) 順序存取為了得到順序表中所要求的項(xiàng)，必須從表的第一個(gè)表項(xiàng)開(kāi)始，逐個(gè)訪(fǎng)問(wèn)表項(xiàng)，直到找到滿(mǎn)足要求的表項(xiàng)為止。 遍歷 逐項(xiàng)訪(fǎng)問(wèn) 從前向后 從后向前 從兩端向中間14線(xiàn)性表上的基本運(yùn)算InitList(L) 構(gòu)造一個(gè)空的順序表Length(L) 求順序表L中的表元個(gè)數(shù)GetNode(L, i) 取順序表L中的第i個(gè)表元LocateNode(L, x)在順序表中找值為x的結(jié)點(diǎn)，返回該結(jié)點(diǎn)在L中的位置。InsertList(L, x, i)在L的第i個(gè)位置插入一個(gè)值為x的新表元。D

8、eleteList(L, i) 刪除L的第i個(gè)表元。線(xiàn)性表 的存儲(chǔ)結(jié)構(gòu)常用的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)鏈接存儲(chǔ)順序存儲(chǔ)（順序表）設(shè)順序表的每個(gè)表元的結(jié)構(gòu)都相同，記LOC（ ai）為存儲(chǔ)ai的開(kāi)始地址，則 LOC（ ai）=LOC(a0) + i*sizeof(a0)順序存儲(chǔ)線(xiàn)性表的數(shù)據(jù)類(lèi)型#define MaxSize 100typedef int DataTypetypedef struct DataType dataMaxSize; int len;SeqList;16順序搜索圖示 x = 48 x = 5017int LocateNode(SeqList *l, DataType key ) i

9、nt i; for(i = 0; i len; i+) if(l-datai = key) return i; return -1;搜索成功 若搜索概率相等，則搜索不成功 數(shù)據(jù)比較 n 次表項(xiàng)的插入int InsertList (SeqList *l, , DataType x, int i ) int j;/在表中第 i 個(gè)位置插入新元素 x if ( i l-len | l-len = MaxSize ) return 0; /插入不成功 else for ( j=l-len; ji; j- ) l-dataj = l-dataj -1; l-datai = x; l-len+; retu

10、rn 1; /插入成功 表項(xiàng)的刪除 int DeleteList( SeqList *l, int x ) int i, j; /在表中刪除已有元素 x i = LocateNode (l, x); /在表中搜索 x if ( i = 0 ) for ( j=i; jlen-1; j+ ) l-dataj = l-dataj+1; l-len-; return 1; /成功刪除 return 0; /表中沒(méi)有 x 線(xiàn)性表的應(yīng)用：集合的“并”運(yùn)算void Union ( SeqList *LA, SeqList *LB) int i, k; DAtaType x; for (i=0; ilen;

11、 i+ ) x = LBi; /在LB中取一元素 k =LocateNode(LA, x); /在LA中搜索它 if ( k = -1 ) /若未找到插入它 InsertList (LA , x, LA-len); 有一個(gè)指針指向鏈表的第一個(gè)表元，習(xí)慣稱(chēng)該指針為“頭指針”或“鏈表頭”。頭指針head指向第一個(gè)表元，第一個(gè)表元又指向第二個(gè)表元，直到最后一個(gè)表元，該表元不再指向其他表元，習(xí)慣稱(chēng)鏈表的最后一個(gè)表元為“表尾”。 一個(gè)非空鏈表一個(gè)空鏈表first = NULL鏈接存儲(chǔ)線(xiàn)性表-單鏈表結(jié)構(gòu)單鏈表的存儲(chǔ)映像單鏈表的數(shù)據(jù)類(lèi)型typedef char DataType;typedef struct

12、 node DataType data; struct node *next; ListNode;typedef struct ListNode *head; LinkList;1.遍歷鏈表從鏈表的首表元開(kāi)始，沿著鏈表表元的鏈接順序逐一考察各表元，直至鏈表結(jié)束。用指針p遍歷整個(gè)鏈表，訪(fǎng)問(wèn)表元只做輸出表元值的工作。p的初值為鏈表頭指針，在p不等于NULL值時(shí)循環(huán)，輸出p所指表元的值，并準(zhǔn)備考察下一個(gè)表元(即p = p-next)。遍歷鏈表的函數(shù)： void travelLink(LinkList *L) ListNode *p = L-head; while ( p != NULL ) prin

13、tf(”%4c”, p-data); /* 輸出表元的值 */ p = p-next; /* 準(zhǔn)備訪(fǎng)問(wèn)下一個(gè)表元 */ printf(”n”); 2.在鏈表中查找指定值的表元在鏈表中查找指定值表元有不同目的獲取該表元的詳細(xì)信息，稱(chēng)為簡(jiǎn)單查找。對(duì)鏈表的修改，或?qū)⒉榈降谋碓獎(jiǎng)h除，或在查到的表元之前插入一個(gè)新表元等，稱(chēng)為動(dòng)態(tài)查找。另外，查找過(guò)程的實(shí)現(xiàn)又可分兩種情況，一是無(wú)序鏈表上的查找，二是有序鏈表上的查找。（1）無(wú)序鏈表上的簡(jiǎn)單查找簡(jiǎn)單查找過(guò)程:從鏈表頭指針?biāo)傅牡谝粋€(gè)表元出發(fā)，順序查找?；虬l(fā)現(xiàn)有指定值的表元，以指向該表元的指針值為查找結(jié)果；或查找至鏈表末尾，未發(fā)現(xiàn)有指定值的表元，查找結(jié)果為NUL

14、L，表示鏈表中沒(méi)有指定值的表元。ListNode * searchSLink(LinkList *L, DataType key) ListNode *v = L-head; while ( v != NULL ) & ( v-data != key) v = v-next; return v; （2）有序鏈表上的簡(jiǎn)單查找如鏈表的表元是按值從小到大有序的，在順序考察鏈表表元的查找循環(huán)中，當(dāng)發(fā)現(xiàn)還有表元，并且該表元的值比key小時(shí)，應(yīng)繼續(xù)查找。反之，若不再有表元，或當(dāng)前表元值不比key值小，則應(yīng)結(jié)束查找。查找循環(huán)結(jié)束后，僅當(dāng)還有表元，且表元的值與key值相同情況下，才找到，函數(shù)返回當(dāng)前表元的指針

15、。否則，鏈表中沒(méi)有值為key的表元，函數(shù)返回NULL值。ListNode *searchSOLink(LinkList *L, DataType key) ListNode *v = L-head; while(v!= NULL)&(v-datanext; return v != NULL & v-data = key ? v : NULL; （3）無(wú)序鏈表上的動(dòng)態(tài)查找動(dòng)態(tài)查找應(yīng)為插入或刪除做好必要的準(zhǔn)備工作。由于是單向鏈表，函數(shù)除要回答查找結(jié)束時(shí)的當(dāng)前表元的指針外，還應(yīng)回答該表元的前驅(qū)表元指針。令函數(shù)返回值是查找結(jié)束時(shí)當(dāng)前表元的指針，函數(shù)另設(shè)一個(gè)指針形參，將找到的前驅(qū)表元的指針存于環(huán)境中的某

16、指針變量中。ListNode *searchDSLink(LinkList *L, DataType key，ListNode * pp) ListNode *v = L-head, *u = NULL; while ( v != NULL ) & ( v-data != key) u = v ; v = v-next; /* 后繼表元成為當(dāng)前表元 */ *pp = u; return v; (4)有序鏈表上的動(dòng)態(tài)查找表元按值從小到大順序鏈接，與無(wú)序鏈表上的動(dòng)態(tài)查找類(lèi)似，但查找循環(huán)當(dāng)發(fā)現(xiàn)查找值不比鏈表當(dāng)前表元的值小時(shí)，就應(yīng)提早結(jié)束查找循環(huán)。 ListNode * searchDOLink(Li

17、nkList *L, DataType key， ListNode * pp) ListNode *v = L-head, *u = NULL; while ( v != NULL ) & ( v-data next; *pp = u; return v; 3.從鏈表刪除指定值的表元為刪除首先要查找指定值的表元。若未找到，則不做刪除工作；若找到，則將它從鏈表中刪除。刪除時(shí)要考慮兩種不同情況，如刪的是首表元，要更改鏈表頭指針；否則更改前驅(qū)表元的后繼指針。在無(wú)序整數(shù)鏈表上刪除指定值表元的函數(shù)中。因函數(shù)在刪除鏈表首表元時(shí)，要修改鏈表頭指針。函數(shù)返回刪除表元的指針。ListNode *sDelete(

18、LinkList *L,DataType key) ListNode *u, *w; u = L-head; /* 讓 u 指向鏈表的首表元 */ while (u != NULL) & (u-data != key) w = u; u = u - next; if (u != NULL)/* 鏈表中有值為key的表元 */ if (u = L-head) L-head = u-next;/* 修改鏈表頭指針 */ else w-next = u-next; u-next = NULL ; return u;4.在有序鏈表中插入指定值的表元尋找插入位置，生成新表元并插入之。void rInse

19、rte(LinkList *L, DataType key) ListNode *u, *w, *p; u = searchDOLink(L, key, &w); p=(ListNode*)malloc(sizeof(ListNode); p-data = key; p-next = u; if (w=NULL) L-head = p; /* 修改鏈表頭指針 */ else w-next = p;5.建立單鏈表(1)頭插法建表LinkList CreatListF(void) char ch; LinkList L; ListNode *p; L.head = NULL; while(ch =

20、 getchar() != n) p = (ListNode *)malloc(sizeof(ListNode); p-data = ch; p-next = L.head; L.head = p; return L; (2)尾插法建表LinkList CreatListR(void) char ch; LinkList L; ListNode *p, *r; L.head = r = NULL; while(ch = getchar() != n) p = (ListNode *)malloc(sizeof(ListNode); p-data = ch; if(r = NULL) L.hea

21、d = p; else r-next = p r = p; if(r != NULL) r-next = NULL; return L; 帶表頭結(jié)點(diǎn)的單鏈表表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。非空表 空表循環(huán)鏈表 (Circular List)循環(huán)鏈表是單鏈表的變形。相同點(diǎn)：兩者結(jié)點(diǎn)結(jié)構(gòu)相同。不同點(diǎn)：循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的link指針不為 0 (NULL)，而是指向了表的前端。為簡(jiǎn)化操作，在循環(huán)鏈表中往往加入表頭結(jié)點(diǎn)。特點(diǎn)：只要知道表中某一結(jié)點(diǎn)的地址，就可搜尋到所有其他結(jié)點(diǎn)。循環(huán)鏈表的示例帶表頭結(jié)點(diǎn)的循環(huán)鏈表 字符串

22、 (String)字符串是n ( 0 ) 個(gè)字符的有限序列，記作 S : “c0c1c2cn-1” 其中，S是串名字 “c0c1c2cn-1”是串值 ci是串中字符 n是串的長(zhǎng)度。 如：“Welcome to Shanghai !”41char *subStr (char*s, int pos, int len , char *ss) /從串中第pos個(gè)位置起連續(xù)提取len個(gè)字符 /形成子串返回 int i, j; if ( pos 0 | len 0 ) *ss = 0; /返回空串 else /提取子串 for(i=0, j=pos; sj!=0 & i 0，則目標(biāo)指針不變， 模式指針回到

23、 p f ( j-1)+1。 運(yùn)用KMP算法的匹配過(guò)程第1趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 1 j = f (j-1)+1 = 0第2趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 0 目標(biāo)指針加 1 第3趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c j = 5 j = f (j-1)+1 = 2 第4趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 (a b) a a b c a c int