線性表與字符串-2

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

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

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

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

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

6、放的位置為：頁優(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ù)組線性表線性聚集，一個存儲n(n0)個表項的序列。n是表的長度，可以是任意整數(shù)。n=0為空表。表的長度隨增加或刪除某些表項而發(fā)生改變。每個表項都是單個對象，其數(shù)據(jù)類型相同。各個表項通過其位置來訪問；

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

8、eleteList(L, i) 刪除L的第i個表元。線性表 的存儲結(jié)構(gòu)常用的存儲結(jié)構(gòu)：順序存儲鏈接存儲順序存儲（順序表）設(shè)順序表的每個表元的結(jié)構(gòu)都相同，記LOC（ ai）為存儲ai的開始地址，則 LOC（ ai）=LOC(a0) + i*sizeof(a0)順序存儲線性表的數(shù)據(jù)類型#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 次表項的插入int InsertList (SeqList *l, , DataType x, int i ) int j;/在表中第 i 個位置插入新元素 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; /插入成功 表項的刪除 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; /表中沒有 x 線性表的應(yīng)用：集合的“并”運算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); 有一個指針指向鏈表的第一個表元，習(xí)慣稱該指針為“頭指針”或“鏈表頭”。頭指針head指向第一個表元，第一個表元又指向第二個表元，直到最后一個表元，該表元不再指向其他表元，習(xí)慣稱鏈表的最后一個表元為“表尾”。 一個非空鏈表一個空鏈表first = NULL鏈接存儲線性表-單鏈表結(jié)構(gòu)單鏈表的存儲映像單鏈表的數(shù)據(jù)類型typedef char DataType;typedef struct

12、 node DataType data; struct node *next; ListNode;typedef struct ListNode *head; LinkList;1.遍歷鏈表從鏈表的首表元開始，沿著鏈表表元的鏈接順序逐一考察各表元，直至鏈表結(jié)束。用指針p遍歷整個鏈表，訪問表元只做輸出表元值的工作。p的初值為鏈表頭指針，在p不等于NULL值時循環(huán)，輸出p所指表元的值，并準(zhǔn)備考察下一個表元(即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)備訪問下一個表元 */ printf(”n”); 2.在鏈表中查找指定值的表元在鏈表中查找指定值表元有不同目的獲取該表元的詳細(xì)信息，稱為簡單查找。對鏈表的修改，或?qū)⒉榈降谋碓獎h除，或在查到的表元之前插入一個新表元等，稱為動態(tài)查找。另外，查找過程的實現(xiàn)又可分兩種情況，一是無序鏈表上的查找，二是有序鏈表上的查找。（1）無序鏈表上的簡單查找簡單查找過程:從鏈表頭指針?biāo)傅牡谝粋€表元出發(fā)，順序查找。或發(fā)現(xiàn)有指定值的表元，以指向該表元的指針值為查找結(jié)果；或查找至鏈表末尾，未發(fā)現(xiàn)有指定值的表元，查找結(jié)果為NUL

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

15、。否則，鏈表中沒有值為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）無序鏈表上的動態(tài)查找動態(tài)查找應(yīng)為插入或刪除做好必要的準(zhǔn)備工作。由于是單向鏈表，函數(shù)除要回答查找結(jié)束時的當(dāng)前表元的指針外，還應(yīng)回答該表元的前驅(qū)表元指針。令函數(shù)返回值是查找結(jié)束時當(dāng)前表元的指針，函數(shù)另設(shè)一個指針形參，將找到的前驅(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)有序鏈表上的動態(tài)查找表元按值從小到大順序鏈接，與無序鏈表上的動態(tài)查找類似，但查找循環(huán)當(dāng)發(fā)現(xiàn)查找值不比鏈表當(dāng)前表元的值小時，就應(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.從鏈表刪除指定值的表元為刪除首先要查找指定值的表元。若未找到，則不做刪除工作；若找到，則將它從鏈表中刪除。刪除時要考慮兩種不同情況，如刪的是首表元，要更改鏈表頭指針；否則更改前驅(qū)表元的后繼指針。在無序整數(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é)點的單鏈表表頭結(jié)點位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。設(shè)置表頭結(jié)點的目的是統(tǒng)一空表與非空表的操作，簡化鏈表操作的實現(xiàn)。非空表 空表循環(huán)鏈表 (Circular List)循環(huán)鏈表是單鏈表的變形。相同點：兩者結(jié)點結(jié)構(gòu)相同。不同點：循環(huán)鏈表最后一個結(jié)點的link指針不為 0 (NULL)，而是指向了表的前端。為簡化操作，在循環(huán)鏈表中往往加入表頭結(jié)點。特點：只要知道表中某一結(jié)點的地址，就可搜尋到所有其他結(jié)點。循環(huán)鏈表的示例帶表頭結(jié)點的循環(huán)鏈表 字符串

22、 (String)字符串是n ( 0 ) 個字符的有限序列，記作 S : “c0c1c2cn-1” 其中，S是串名字 “c0c1c2cn-1”是串值 ci是串中字符 n是串的長度。 如：“Welcome to Shanghai !”41char *subStr (char*s, int pos, int len , char *ss) /從串中第pos個位置起連續(xù)提取len個字符 /形成子串返回 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。 運用KMP算法的匹配過程第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