第4章 串、数组和广义表
时间:2025-07-10
时间:2025-07-10
数据结构
数据结构陈文森
2013年7月12日
数据结构
第4章
串、数组和广义表
教学内容4.1 4.2 4.3 串 数组 广义表
2013年7月12日
数据结构
教学目标1. 了解串的存储方法,理解串的两种模式匹配 1. 掌握串的存储方法,理解串的两种模式匹 算法,重点掌握BF算法。 配算法; 2. 明确数组和广义表这两种数据结构的特点, 2. 明确数组和广义表这两种数据结构的特点 掌握数组地址计算方法,了解几种特殊矩阵 ,掌握数组存储时地址计算方法,了解几种 的压缩存储方法。 特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和 GetTail的操作。2013年7月12日
数据结构
4.1 串串(String)----零个或多个字符组成的有限序列
s ' a1a2 an '串名 串值 串长
n
空串2013年7月12日
n=0
数据结构
串的存储结构顺序存储 链式存储
2013年7月12日
数据结构
顺序存储表示typedef struct{
char *ch; int length;
//若串非空,则按串长分配存储区,//否则ch为NULL
//串长度
}HString;
2013年7月12日
数据结构
链式存储表示head
A B C Dhead
E F G H
I # # #
A
B
C
...
I
2013年7月12日
数据结构
链式存储表示#define CHUNKSIZE 80 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; //可由用户定义的块大小
typedef struct{ Chunk *head,*tail; //串的头指针和尾指针 int curlen; //串的当前长度 }LString;2013年7月12日
数据结构
串的模式匹配算法 算法目的:确定主串中所含子串第一次出现的位置(定位) 即如何实现教材P72 Index(S,T,pos)函数
算法种类: BF算法(又称古典的、经典的、朴素的、穷举的)
KMP算法(特点:速度快)
2013年7月12日
数据结构
BF算法设计思想 i S :ababcabcacbabT :abc j
i指针回溯
S :ababcabcacbab
T : abcS :ababcabcacbab T : abc2013年7月12日
数据结构
BF算法设计思想Index(S,T,pos) 将主串的第pos个字符和模式的第一个字符比较, 若相等,继续逐个比较后续字符; 若不等,从主串的下一字符起,重新与模式的 第一个字符比较。 直到主串的一个连续子串字符序列与模式相等 。 返回值为S中与T匹配的子序列第一个字符的序号, 即匹配成功。
否则,匹配失败,返回值 02013年7月12日
数据结构
BF算法描述(算法4.1)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; } if ( j>T[ 0 ]) return i-T[0]; else return 0; }
2013年7月12日
数据结构
BF算法时间复杂度例: S=‘0000000001’,T=‘0001’,pos=1 若n为主串长度,m为子串长度,最坏情况是 主串前面n-m个位置都部分匹配到子串的最后一 位,即这n-m位各比较了m次 最后m位也各比较了1次
总次数为:(n-m)*m+m=(n-m+1)*m 若m<<n,则算法复杂度O(n*m)2013年7月12日
数据结构
4.2 数组本节所讨论的数组与高级语言中的数组区别:
高级语言中的数组是顺序结构; 而本章的数组既可以是顺序的,也可以是链式结构, 用户可根据需要选择。
2013年7月12日
数据结构
一维数组
LOC(i) =0 1 2
a,3 4
i=05 6 7 8 9
LOC(i-1)+l = a+i*l, i > 0
a 35 27 49 18 60 54 77 83 41 02l l l l l l l a+i*l l l l
LOC(i) = LOC(i-1)+l = a+i*l
2013年7月12日
数据结构
二维数组A ( 1, 2 , , p ) (p m或n)
Am n i (ai1, ai 2 , , ain ) 1 i m
a11 a12 a1n a a22 a2 n 21 am1 am 2 amn a11 a12 a1n a a22 a2 n 21 am1 am 2 amn 2013年7月12日
j (a1 j , a2 j , , amj ) 1 j n
Am n
…… 此处隐藏:25字,全部文档内容请下载后查看。喜欢就下载吧 ……