串和数组

教学目标 了解字符串的基本概念和基本操作； 掌握字符串的基本操作在顺序存储结构上的实现； 了解字符串的基本操作在链式存储结构上的实现; 了解数组的基本概念和基本操作； 掌握二维数组的映像函数； 特殊矩阵的压缩存储

1 串类型的定义 串的定义 串由零个或多个任意字符组成的字符序列。 s=“c1 c2 … cn” 串的长度 空串、空格串 串相等 子串、主串 3/18

串的抽象数据类型定义 ADT String { 数据对象：D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n } 基本操作： SubString (&Sub, S, pos, len) 初始条件：串S存在，1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果：用Sub返回串S的第pos个字符起长度为len的子串。 StrInsert (&S, pos, T) 初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。 操作结果：在串S的第pos个字符之前插入串T。 StrDelete (&S, pos, len) 初始条件：串S存在，1≤pos≤StrLength(S)-len+1。 操作结果：从串S中删除第pos个字符起长度为len的子串。 … } ADT String 4/18

串的最小操作子集 串的最小子集操作 举例说明 串赋值StrAssign 串比较StrCompare 求串长StrLength 求子串SubString 串联接Concat 举例说明 定位函数Index(S,T,pos) 3 = Index(“abbcd”, “bc”,2) 基本思想：在主串S中取从第i(i的初值为pos)个字符起、长度和串T相等的子串。和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止。 5/18

Index (String S, String T, int pos) int Index (String S, String T, int pos) { if (pos > 0) { n = StrLength(S); m = StrLength(T); for (i = pos; i <= n-m+1; i++) { SubString (sub, S, i, m); if (StrCompare(sub,T) == 0) return i; } // for } // if return 0; // S中不存在与T相等的子串 } // Index 6/18

2 串的表示和实现 定长顺序存储表示 堆分配存储表示 串的块链存储表示 7/18

2.1 定长顺序存储表示 char data[MAXSTRLEN+1] 采用带长度域的结构 typedef struct { int length; } SeqString; 3 a b c a b c d Length=4 8/18

Concat(SString &T,SString S1,SString S2) 基本操作-串的联接算法 Concat(SString &T,SString S1,SString S2) 基本思想 1）两串相连后长度不超过MAXSTRLEN T = S1+S2 2）两串相连后长度超过MAXSTRLEN S1长度 < 最大长度: T = S1+S2.part S1长度 = 最大长度: T= S1 9/18

Concat(SString &T, SString S1, SString S2) Status Concat(SString &T, SString S1, SString S2) { if (S1[0]+S2[0] <= MAXSTRLEN) { // 未截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; } else if (S1[0] < MAXSTRSIZE) { // 截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN-S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } else { // 截断(仅取S1) T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; uncut = FALSE; } return uncut; } // Concat 10/18

2.2 堆分配存储表示 typedef struct { char *ch; int length; } HString; 11/18

Concat(HString &T, HString S1, HString S2) Status Concat(HString &T, HString S1, HString S2) { if (T.ch) free(T.ch); T.length=S1. length+S2. length; if (!(T.ch = (char *)malloc(T.length*sizeof(char))) exit(OVERFLOW); T.ch[0..S1.length-1]=S1.ch[0 ..S1.length-1]; T.ch[S1.length..T.length-1]=S2.ch[0 ..S2.length-1]; return OK; }//Concat 12/18

2.3 串的块链存储表示 当结点大小大于１时，串尾会出现无效字符。 串值所占的存储位/实际分配的存储位。 结点大小 存储密度 类型定义 2.3 串的块链存储表示 结点大小 当结点大小大于１时，串尾会出现无效字符。 存储密度 串值所占的存储位/实际分配的存储位。 类型定义 #define CHUNKSIZE 3 typedef struct Chunk { // 结点结构 char ch[CHUNKSIZE]; struct Chunk *next; } Chunk; //块定义 typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString; //块链串 13/18

3 串的模式匹配算法 3 = Index(“abbcd”, “bc”,2) 基本概念 3 串的模式匹配算法 3 = Index(“abbcd”, “bc”,2) 基本概念 串的定位操作Index(S,T,pos)称为串的模式匹配。 串Ｓ称主串，串Ｔ称模式串。 基本思路 从主串的第pos个字符起每次取出长度和模式串相等的子串，将该子串与模式串的字符一一比较。如果成功比较结束，则该子串就是要求的子串，否则从主串的下一个子串重新比较。 14/18

Index(SString S,SString T,int pos) int Index(SString S,SString T,int pos){ 　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;}　//指针回溯到第i-j+2个字符 　}//while 　if (j>T[0]) return i-T[0]; //找到匹配的子串 　else return 0;　//未找到 } //Index 15/18

4 数组 数组的定义和特点 定义 数组特点 数组运算 数组结构固定 数据元素同构 给定一组下标，存取相应的数据元素 4 数组 数组的定义和特点 定义 ( ) ( ) 数组特点 数组结构固定 数据元素同构 数组运算 给定一组下标，存取相应的数据元素 给定一组下标，修改数据元素的值

数组的顺序存储结构 次序约定 a11 a12 …….. a1n a11 a12 …….. a1n a21 a22 …….. a2n 以行序为主序 以列序为主序 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l   按行序为主序存放 amn …….. am2 am1 ………. a2n a22 a21 a1n ……. a12 a11 1 n-1 m*n-1 n   按列序为主序存放 1 m-1 m*n-1 m amn …….. a2n a1n ………. am2 a22 a12 am1 ……. a21 a11 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

4.1 矩阵的压缩存储 特殊矩阵 对称矩阵 三角矩阵 对角矩阵 稀疏矩阵 18/16

对称矩阵 按行序为主序： 1 2 9 7 4 6 … 5 a11 a21 a22 a31 a32 an1 ann …... k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：

三角矩阵 ann c … an2 an1 a33 a32 a31 a22 a21 a11 按行序为主序： 上三角阵　　 　　　　　　　 下三角阵　　 　　　　　　　 ann c … an2 an1 a33 a32 a31 a22 a21 a11 a11 a21 a22 a31 a32 an1 ann …... k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：

带状矩阵 带状矩阵压缩存储作为课后作业。

稀疏矩阵 设在m×n矩阵中，有 t 个数据元素不为零，则通常认为当 时，称该矩阵为稀疏矩阵，其中δ称稀疏因子。 数据类型 i j v 1 1 1 15 2 1 4 22 3 1 6 -15 4 2 2 11 5 2 3 3 6 3 4 6 7 5 1 91 数据类型 typedef struct { int i,j; //非零元素的行、列 ElemType e; //非零元素值 }SPNode; //三元组类型 typedef struct { int mu,nu,tu; SPNode data[SMAX+1]; //data[0]未用 } SPMatrix; //三元组表的存储类型 //矩阵的行、列和非零元素的个数

作业与实验 作业 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1<S2时则返回负数。 用顺序存储结构实现在字符串S中删除所有其值等于ch的字符的算法。 设单链表中存放n个字符，试设计算法判断字符串是否关于中心对称。

作业与实验 设有n行n列的对称矩阵A，每个数组元素占L个字节的存储单元，按行的顺序将下三角矩阵中的元素(包括对角线上的元素)存放在n*(n+1)/2个存储单元中，已知A[0][0]的地址为1000，则A[i][j](i>=j)的地址是多少？ 设有n行n列的三对角矩阵A，每个数组元素占L个字节的存储单元，按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知A[0][0]的地址为1000，则三对角线上元素A[i][j]的地址是多少？