串和数组.

Presentation on theme: "串和数组."— Presentation transcript:

1 串和数组

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

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

4 串的抽象数据类型定义 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

5 串的最小操作子集 串的最小子集操作 举例说明 串赋值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

6 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

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

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

9 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

10 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

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

12 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

13 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

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

15 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

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

17 数组的顺序存储结构 次序约定 a11 a12 …….. a1n a11 a12 …….. a1n a21 a22 …….. a2n
以行序为主序 以列序为主序 a a12 …….. a1n a 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 a a12 …….. a1n a a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

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

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

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

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

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

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

24 作业与实验 设有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]的地址是多少？