第4章 串、数组和广义表 4．1 串 4．2 数组 4．3 广义表.

Presentation on theme: "第4章 串、数组和广义表 4．1 串 4．2 数组 4．3 广义表."— Presentation transcript:

1 第4章 串、数组和广义表 4．1 串 4．2 数组 4．3 广义表

2 4．1 串 4．1．1串的基本概念 串: 由零个或多个字符组成的有限序列。 s = “s1s2 … sn” ( n≥0) 串值 串名

3 串中任意个连续的字符组成的子序列称为该串的子串。
包含子串的串称为主串。 例:“eij” 是 “beijing” 的子串，“beijing” 为主串。

4 4．1．2串的运算及存储 1、串的运算 (1)求串长：StrLen(S) 操作条件 S存在。 操作结果 求S的长度。
(2)串赋值StrAssign(S1，S2) 操作条件 S1是一个串变量，S2是串常量或串变量。 操作结果 将S2赋值给S1,S1原来值被覆盖。 (3)连接操作StrCat(S1，S2) 操作条件 串S1,S2存在。 操作结果 将S2放在S1的末尾，与S1连接一个新串。

5 (4)求子串StrSub(S，i，piecelen)
(5)串比较StrCmp(S1，S2) 操作条件 串S1,S2存在。 操作结果 比较串的大小。

6 (6)子串定位StrIndex(S，T) 操作条件 串S，T存在。 操作结果 查找子串T在主串S中首次出现的位置。如果S中不包含T，则返回值为-1。 (7)串插入StrInsert(S，i，T) 操作条件 串S,T存在 操作结果 将T插入S的第i个位置,S中第i个位置及以后字符后移。

7 (8)子串删除StrDelete(S，i，piecelen)
(9)串替换StrReplace(S，i，T) 操作条件 串S，T存在。 操作结果 用T替换S中自第i个字符开始，长度与T相等的子串。

8 2、串的存储 串的顺序存储结构简称为顺序串。 字符数组描述: #define MAXSIZE 255
/*假设要处理的串的长度不会超过255*/ char S[MAXSIZE]；

9 typedef struct { char s[MAXSIZE]; int len; /* 用整数来存储串的实际长度*/ }SeqString;

10 （1）串连接 int StrCat(SeqString *S1,SeqString *S2) { int i;
if(S1->len+S2->len<MAXSIZE) { for(i=0;i<S2->len;i++) S1->s[S1->len+i]=S2->s[i]; /*把S2连接S1之后*/ S1->len=S1->len+S2->len; return 1; } else { for(i=0;i<MAXSIZE-S1->len;i++) S1->s[S1->len+i]=S2->s[i]; S1->len=MAXSIZE ; return 0; }}

11 （2） 求子串 Status StrSub(SeqString *S,SeqString *S1,int i,int piecelen)
/*S为主串，S1为子串，i为起始位置，piecelen为长度*/ {if(i+piecelen>S->len) { printf(“子串超界”) exit(-1);} else { for(k=0; k< piecelen; k++) S1->s[k]=S->s[i+k]; /*把子串赋给S1*/} S1->len=piecelen ; return OK;}

12 （3）串插入 else if(i==S->len) StrInsert(Seqstring *S,
Seqstring *T) {if(i>=S->len|| S->len+T->Ien>MAXSIZE) printf(“不能插入”); else if(i==0) {for(k=S->len+T->len-1;k>=T->len ;k--) S->s[k]=S->s[k-T->len]; for(k=0; k< T->len;k++) S->s[k]=T->s[k];} else if(i==S->len) for(k=0;k<T->len; k++) S->s[S->1en+k]=T->s[k]; else {for(k=S->len-1;k>=i;k--) S->s[T->len+k]=S->s[k]; /*将S后移*/ S->s[i+k]=T->s[k]; /*将T插入S中*/} }

13 （4）删除子串 Status StrDelete(SeqString *S，int i，int piecelen)
{ if(i+piecelen>S->len) /*所要删除的子串超界*/ printf(“子串超界”); else {for(k=i+piecelen; k<S->len; k++, i++) S->s[i]=S->s[k]; ／*将r后面的部分覆盖到前面*／} }

14 3、串的模式匹配 设S和T为两个串，在主串S中找到等于子串T的位置的过程称为模式匹配，如果找到，则称匹配成功，返回T在S中首次出现的存储位置，否则匹配失败，返回-1。T也称为模式串。 模式匹配可用回溯匹配法。

15 第一次匹配 s= ababcabcdeabc i=2 失败
t=abcde j=2 第二次匹配 s= ababcabcdeabc i=1 失败 t=abcde j=0 第三次匹配 s= ababcabcdeabc i=5 失败 t=abcde j=3 第四次匹配 s= ababcabcdeabc i=3 失败 t=abcde j=0 第五次匹配 s= ababcabcdeabc i=4 失败 第六次匹配 s= ababcabcdeabc i=9 成功 t=abcde j=4

16 int StrIndex(SeqString *S，SeqString *T)
{int i=0,j=0; while(i<S->len&&j<T->len) if(S->s[i]==T->s[j]) {i++;j++;} /*继续比较后续字符*／ else {i=i-j+1;j=0;} if(j>=T->len) return i-T->len; return 0;}

17 4．2 数组 4．2．1数组的基本概念 一维数组

18 二维数组 三维数组 行向量 下标 i 页向量 下标 i 列向量 下标 j 行向量 下标 j 列向量 下标 k

19 4.2.2 数组的顺序表示和实现 （1）一块足够大的连续内存空间。 （2）一个寻址函数Loc。

20 1、一维数组的寻址函数 一维数组A[b..b+n-1] 寻址函数： Loc(i)=Loc(b)+(i-b) ×s b≤i≤b+n-1
Loc(i)=Loc(0)+i×s 0≤i≤n-1

21 2、二维数组的寻址函数 ⑴行优先顺序a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn
⑵列优先顺序 a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anm

22 行优先存储 αr … . . . ar+1 αr+m-1 ar,c ar,c+1 Am×n ar,c+n-1 ar+1,c
ar+m-1,c ar+m-1,c+n-1 ar+m-1,c+1 αr ar+1 ar,c ar,c ar,c ar,c+n-1 ar+1,c ar+1,c ar+1,c ar+1,c+n-1 ar+m-1,c ar+m-1,c ar+m-1,c ar+m-1,c+n-1 . . . Am×n αr+m-1

23 列优先存储 αc … . . . ac+1 αc+n-1 ar,c ar+1,c Am×n ar+m-1,c ar,c+1
ar,c+n-1 ar+m-1,c+n-1 ar+1,c+n-1 αc ac+1 αc+n-1 ar,c ar,c ar,c ar,c+n-1 ar+1,c ar+1,c ar+1,c ar+1,c+n-1 ar+m-1,c ar+m-1,c ar+m-1,c ar+m-1,c+n-1 . . . Am×n

24 列优先，寻址函数： Loc(i,j) = Loc(r,c) + ((j-c) ×m + (i-r)) ×s r≤i≤r+m-1，c≤j≤c+n-1 行优先，寻址函数： Loc(i,j) = Loc(r,c) + ((i-r) ×n + (j-c)) ×s 当r、c为0，寻址函数： Loc(i,j) = Loc(0,0) + (i×n + j) ×s 0≤i≤m-1，0≤j≤n-1

25 【例4.1】a[1..10][2..8]基地址为1024，每个元素占2个存储单元，若行优先存储，a[5,3]的地址是多少？若以列优先呢？
当行优先时， Loc(i,j)=Loc(r,c)+((i-r)×n+(j-c))×s Loc(5,3)=1024+((5-1)×(8-2+1)+(3-2))×2=1082 当列优先时， Loc(i,j) = Loc(r,c)+((j-c)×m+(i-r))×s Loc(5,3)=1024+((3-2)×(10-1+1)+(5-1))×2=1052

26 【例4.2】a[0..10][2..10]按行优先存储a[7][4]与按列优先存储a[i][j]相对基地址的偏移量相等，则i、j等于多少？
行优先时， Loc(7,4)=Loc(0,2)+(7×(10-2+1)+(4-2))×s=Loc(0,2) +65×s 列优先时， Loc(i,j)=Loc(0,2)+((j-2)× 11 + i) × s (j-2) × 11 + i = 65, 故j = 7,i = 10。

27 4．2．3矩阵的压缩存储 1、特殊矩阵的压缩存储 特殊矩阵指元素之间具有特定规律的矩阵。 对称矩阵 三角矩阵 对角矩阵

28 1）对称矩阵 o 满足: ai j = aj i n2 个矩阵需占用 n(n+1)/2 存储空间 a11 a21 a22 或 . . .
an an ann . . . 或 n2 个矩阵需占用 n(n+1)/2 存储空间

29 关键问题: 建立 SA[k] 和aij 的一一对应关系。
i (i – 1) 2 + j - 1 j (j – 1) + i - 1 当 i ≥ j 当 i ＜ j a12 = a13 = a11 a21 a22 a31 ann k = 1 2 3 n(n+1) 2 - 1

30 2) 三角矩阵 C 矩阵的上(下)三角(不包括对角线)中的元素均为常数 c 的 n 阶矩阵。 a11 a21 a22 . . .
an an ann . . . C

31 关键问题: 建立 SA[k] 和aij 的一一对应关系。
i (i – 1) 2 + j - 1 当 i ≥ j k = 当 i ＜ j n(n+1) 2 a11 a21 a22 a31 ann c a12 ,a13 … n(n+1) 2 k = 1 2 3 n(n+1) 2 - 1

32 3) 对角矩阵 n阶方阵满足所有非零元素集中在以主对角线为中心的带状区域中，称为n阶对角矩阵。主对角线上下方各有b条次对角线，称b为矩阵半带宽，(2b+1)为矩阵的带宽。 o a11 a12 a21 a22 a23 a32 a a34 an,n-1 ann an-1,n 三对角矩阵 o 一般情况

33 关键问题: 建立SA[k] 和aij 的一一对应关系。
三对角矩阵: k = 2 ( i - 1 ) + j - 1 (| i - j | ≤ 1) a11 a12 a21 a22 a23 a32 k = 1 2 3 4 5

34 2、稀疏矩阵的压缩存储 稀疏矩阵的压缩存储方法很多，诸如三元组顺序表、二元组顺序表、带辅助向量的二元组顺序表和十字链表等。

35 1）稀疏矩阵的三元组表示 #define MAXSIZE 100 /*非零元素最多个数*/ typedef struct
{ int row; /*行号*/ int col; /*列号*/ DataType value; /*元素值*/ }TupNode; /*三元组定义*/ { int m ; /*行数值*/ int n; /*列数值*/ int len; /*非零元素个数*/ TupNode data[MAXSIZE]; } TSMatrix; /*三元组顺序表定义*/

36 稀疏矩阵 三元组表示

37 MatrixTran (DataType source[n][m]，DataType dest[m][n])
矩阵转置的经典算法： MatrixTran (DataType source[n][m]，DataType dest[m][n]) { int i,j; for(i=0;i<m;i++) for(j=0;j<n;j++) dest[i][j]=source[j][i];}

38 稀疏矩阵转置：

39 方法一：按三元组表A的列序(即转置后B的行序)进行转置，并依次送入B中。

40 基于稀疏矩阵的三元组表示矩阵的转置算法 MatrixTranspose (TSMatrix A，TSMatrix *B) { int i，j，k; B->m=A.n;B->n=A.m;B->len=A.len; if(B->len>0) { j=0; for(k=0;k<A.n;k++) for(i=0;i<A.len;i++) if(A.data[i].col==k) {B->data[j].row= A.data[i].col; B->data[j].col=A.data[i].row; B->data[j].e=A.data[i].e; j++;} }}

41 方法二：快速转置算法 (1)待转置矩阵source每一列中非零元素的个数。
(2)待转置矩阵source每一列第一个非零元素在三元组表B中的正确位置。

42 position[0]=0 position[col]=position[col-1]+num[col-1]

43 MatrixFastTranspose(TSMatrix A,TSMatrix * B)
{ int col,t,p,q; B->len=A.len;B->n=A.m;B->m=A.n; if(B->len) { for(col=0;col<A.n;col++) num[col]=0； for(t=0;t<A.len;t++) num[A.data[t].col]++; /*计算每一列的非零元素的个数*/ position[0]=0; for(col=1;col<A.n;col++) /*求col列中第一个非零元素在B.data[]中的正确位置*/ position[col]=position[col-1]+num[col-1]; for(p=0;p<A.len;p++) {col=A.data[p].col;q=position[col]; B->data[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].value=A.data[p].value; position[col]++;} }}

44 算法分析： 快速转置算法的时间主要耗费在四个并列的单循环上，时间复杂度为O(A.n+A.len)。
当待转置矩阵M中非零元素个数接近于A.m×A.n时，算法的时间复杂度O(A.m×A.n)。

45 矩阵的每一个非零元素用一个结点表示，除了(row，col，value)以外，还有两个链域：
2) 稀疏矩阵的链式存储结构：十字链表 矩阵的每一个非零元素用一个结点表示，除了(row，col，value)以外，还有两个链域： right：同一行的下一个非零元素； down：同一列中的下一个非零元素。

46

47 4．3 广义表 4.3.1 广义表的定义 n（n≥0）个相互具有线性关系的数据元素组成的有限序列，n称为广义表长度，表中的每个数据元素可以是原子，也可以是一个子表。当广义表不空时，称第一个数据元素为该广义表的表头（head），称其余数据元素组成的表为该广义表的表尾（tail）。

48 (1)A=（）A是空广义表，表长为零。 (2)B =（a）B含有一个原子，表长为1 (3)C =（b，（c，d，e））C含有一个原子和一个子表，表长为2。 (4)D =（B，C，e）D含有两个子表和一个原子，表长为3。 (5)E =（（））E含有一个空子表，表长为1。

49 广义表的基本操作：取表头操作（GetHead）和取表尾操作（GetTail）。
例如： GetHead（B）=a GetTail（B）=（） GetHead（C）=b GetTail（C）=（（c，d，e）） GetHead（E）=（） GetTail（E）=（）

50 4.3.2 广义表的存储结构 typedef struct glnode {Tag tag; union { GListDT atom;
struct glnode *list; }elem; struct glnode *next; }GNode, *GList;

51 广义表PL=（a，（b，（c，d）），（））

52 结 束！