当前位置：文档之家 › 数据结构第四章串ppt

数据结构第四章串ppt

  • 格式：ppt
  • 大小：1.16 MB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

数据结构四PPT课件

数据结构四PPT课件

pos len
堆分配存储特点：仍用一组连续的存储单元来存放串，
但存储空间是在程序执行过程中动态分配而得。
思路：利用malloc函数合理预设串长空间。
有的语言允许对串常量命名，以使程序易读、易写。 【例】C++中，可定义串常量path
const char path[]="dir/bin/appl";
5
练1：串是由
字符组成的序
列，一般0记个或多个
为 S=’a1a2……an’
练2：现。有以下4个字符串：
a =‘BEI’
b =‘JING’ c = ‘BEIJING’
数据结构课程的内容
第4章 串 （String）
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
4.1 串类型的定义
4.2 串的表示和实现 4.3 串的模式匹配算法
4.1 串类型的定义
串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。
记为： s =‘ a1 , a2 , …….. , an’ (n≥0 )
讨论：想存放超长字符串怎么办？——静态数组有缺陷！
改用动态分配的一维数组—— “堆”！
例：用顺序存储方式实现求子串函数SubString(&Sub, S, pos,
len)
将串S中从第pos个字符开始长度为len的字符序列复 制到串Sub中（注：串Sub的预留长度与Ssub, SString S, int pos, int len )
d
= ‘问B：EI①JI他NG们’各自的长度？ a =3，b =4，c = 7，d=8
② a是哪个串的子串？在主串中的位置是多少？

数据结构第4章串B教学ppt

数据结构第4章串B教学ppt
严蔚敏、吴伟民编著的经典教材，详细介绍了各 种数据结构及其基本操作，包括串的实现和应用。
《算法导论》
Thomas H. Cormen等编著的经典算法教材，深 入讲解了算法设计和分析的方法，包括串的模式 匹配等算法。
MOOC课程
中国大学MOOC、Coursera等在线教育平台上 提供了大量与数据结构和算法相关的课程，可以 系统地学习相关知识和技能。
压缩串处理技术
针对大规模文本数据，研究压缩串处理技术可以减少存储 空间占用，提高处理效率，是未来发展的重要方向之一。
串的并行处理技术
利用并行计算技术加速串的处理过程，提高处理效率，是 未来研究的热点之一。需要解决并行化算法设计、并行计 算框架选择等问题。
拓展学习资源推荐
1 2 3
《数据结构（C语言版）》
Sunday算法
Sunday算法是一种简单且高效的字符串匹配算法，其核心思 想是当发现不匹配的字符时，直接跳过主串中当前字符之前 的所有字符，将模式串与主串的下一个字符进行比较。
03
串的应用举例
文本编辑中的串操作
01
02
03
字符串匹配
在文本编辑中，经常需要 查找或替换特定的字符串， 这可以通过串的匹配操作 实现。
可以使用数组下标和字 符串截取函数`substr()` 实现串的截取，如`char ch = str[2];`或 `std:string sub = str.substr(2, 4);`。
Python语言实现串的基本操作
串的定义与初始化
在Python中，串使用引号（单引号、双 引号或三引号）进行定义和初始化，如`s = 'hello'`或`s = "hello"`。的比较

最新课件-数据结构教学第4章串 精品

最新课件-数据结构教学第4章串 精品
例如, 设链表中每个结点只存放一个字符, 则在C语言中可 使用如下说明:
struct list struct list * next; /* 指向下一个结点的指针 */ char data; /* 字符 */
} * point; /* point为结构类型的指针, 指向第一结点 */ 根据上述说明, 字符串′string′的链表存储可用图4.1表示。 如果链表中每个结点可存放4个字符, 则结点结构为: struct list struct list * next;
4.2.2 串的链表存储
由于各种串运算与串的存储方式有密切关系 , 若要随机存 取串中第K个字符, 顺序存储显得比较方便; 若要对串进行插入、 删除等操作, 顺序存储就显得比较繁琐, 而链表存储则显示出 明显的优越性。
链表存储是把可利用的存储空间分成一系列大小相同的 结点 ( 若干连续的存储单元 ), 每个结点含有两个域 : data 域和 next域。 data域用来存放字符; next域用来存放指向下一个结点 (首地址)的指针。 结点的大小是指data域中可以存放字符的个 数, next域的大小则取决于寻址的范围。
元中仅放一个字符。 在一个程序中使用的串变量较少, 且各串 变量的长度又都较短时，如果希望该程序处理字符的速度尽 可能快, 那么选择非紧缩格式比较合适。 在这种存储格式中, 串的长度是隐式的, 串所占用存储单元的个数即为串长。
例: 假设一存储单元可以存放4个字符, 同样对于字串(This is a flag), 共需14个存储单元, 其存放的直观表示如表 4.2。 这 种存储格式对存储空间的利用率仅为25%, 但如上所述, 该方法 在字符加工处理方面会节省时间。 3) 某些计算机( 如一般的微型计算机 ), 是以字节为存取单位 的, 一个字符通常又占用一个字节, 这就自然形成了每个存储 单位存放一个字符的分配方式。这种方式一般不需要存放串 长的存储单元, 而需要以程序中各变量值所不包含的字符作为 结束符。 例: 在C语言中, 字符串存放在一个连续的存储单元中, 一 个字符占一个字节。对于字符串′STRING′, 在微机中只需 7 个 存储单元。直观表示如下:

第4章 串 数据结构课件

第4章 串 数据结构课件
saaaaabaaabsaaaaab设匹配成功发生在设匹配成功发生在sisi处则在处则在ii11趟不成功的匹配中共趟不成功的匹配中共比较了比较了ii11mm次第次第ii趟成功的匹配共比较了趟成功的匹配共比较了mm次所以总共比较了所以总共比较了iimm次因此平均比较的次数是次因此平均比较的次数是一般情况下一般情况下mnmn因此最坏情况下的时间复杂度是因此最坏情况下的时间复杂度是onmonm
）：从主串 的第pos个字符起定 （10）子串定位 ）子串定位StrIndex（s，t，pos）：从主串 的第 个字符起定 （ ， ， ）：从主串s的第 位串s中是否存在和串 值相等的子串，若存在，则返回子串t在主串 中是否存在和串t值相等的子串 在主串s中 位串 中是否存在和串 值相等的子串，若存在，则返回子串 在主串 中 第一次出现的位置，否则，返回函数值0。 第一次出现的位置，否则，返回函数值 。 例如， 例如， StrIndex（“Beijing”，“jin”，1）=4； （ ， ， ） ； StrIndex（“Beijing”，“jng”，2）=0 （ ， ， ） ）：用 串置换s串中第 （11）置换运算 ）置换运算StrReplace（s，pos，len，t）：用t串置换 串中第 （ ， ， ， ）： 串置换 pos字符开始的连续的 个字符。 字符开始的连续的len个字符 字符开始的连续的 个字符。 例如，s=“Thatфisфaфbag！”，则 例如， ！ StrReplace（s，3，2，“is”）＝“Thisфisфaфbag！” （， ， ， ）＝“ ）＝ ！ 有时用另一种置换运算StrReplace（s，t，v）表示用 串置换所有在 （ ， ， ）表示用v串置换所有在 有时用另一种置换运算 s串中出现的与 串相等的子串。 串中出现的与t串相等的子串 串中出现的与 串相等的子串。 例如， ＋＋；” 例如，s=“if（j<n）ф j＋＋；”，t=“j”，v=“i”，则 （ ） ＋＋； ， ， StrReplace（s，t，v）=“if（i<n）ф i＋＋；” （，， ） ＋＋；” （ ） ＋＋； 以上介绍的是有关串的一些基本运算， 以上介绍的是有关串的一些基本运算，利用它们可以处理关于串的 各种操作，在使用高级程序设计语言中的串类型时， 各种操作，在使用高级程序设计语言中的串类型时，对于串的基本运算 可以有不同的定义方法。 可以有不同的定义方法。

数据结构第4章PPT课件

数据结构第4章PPT课件
• (12)StrReplace(S,T,pos,len)：串替换操作。当1≤pos≤StrLength(S)且0≤len≤StrLength(S)pos+1时，用串T替换串S中从第pos个字符开始的len个字符。
• (13)StrDestroy(S)：串销毁操作。销毁串S。
10
第10页/共33页
4.2 串的存储结构
4.1 串的定义及基本操作
• 串即字符串，计算机处理的对象分为数值数据和非数值数据，字符串是最基本的非数值数据。 • 字符串的应用非常广泛，它是许多软件系统(如字符编辑、情报检索、词法分析、符号处理、自然语言翻译
等系统)的操作对象。 • 在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的。字符
• 线性表的顺序和链式存储结构对于串都是适用的。但任何一种存储结构对于串的不同运 算并非都是十分有效的。
• 对于串的插入和删除操作，顺序存储结构是不方便的，而链式存储结构则显得方便些。 如果访问串中单个字符，对链表来说是不困难的；当要访问一组连续的字符时，用链式 存储结构要比用顺序存储结构麻烦。
11
9
第9页/共33页
串的基本操作
• (10)SubString(Sub,S,pos,len)：求子串操作。若存在位置1≤pos≤StrLength(S)且 1≤len≤StrLength(S)-pos+1，则用Sub返回串S的第pos个字符起长度为len的子串。
• (11)StrIndex(S,T)：串定位操作。若串S中存在和串T相同的子串，则返回它在串S中第一次出现的位 置；否则返回0。
•
同样存储S=＂
String Structure＂，用
紧凑格式一个地址能存四

数据结构第4章串B教学ppt

数据结构第4章串B教学ppt
布置第4章作业：
1.令s=„aaab‟,t=„abcabaa‟,
u=„abcaabbabcabaacbacba‟
试分别求出它们的next函数值和nextval函数值 2.已知主串s=„ADBADABBAABADABBADADA‟, 模式串pat=„ADABBADADA‟, 写出模式串的nextval函数值，并由此画出KMP算法 匹配的全过程
利用演示系统看BF算法执行过程。
4
例2： S=„ababcabcacbab‟，T=„abcac‟，求Index(S,T,5) （参见教材P79）
Int Index(SString S, SString T, int pos) { i=pos; j=1;
i
pos=5
while ( i<=S[0] && j<=T[0] ) {
第一步，先把模式T所有可能的失配点j 所对应的next[j]计算出来； 第二步：执行定位函数Index_kmp （与BF算法模块非常相似） Int Index_KMP(SString S, SString T, int pos) { //见教材P82 i=pos; j=1; while ( i<=S[0] && j<=T[0] ) { if (j==0|| S[i] = = T[j] ) {++i, ++j} //不失配则继续比较后续字符 else {j=next[j];} //特点：S的i指针不回溯，而且从T的k位置开始匹配 } if(j>T[0]) return i-T[0]; //子串结束，说明匹配成功 else return0; }//Index_KMP
17
讨论： next [ j ]是否完美无缺？ 前面定义的next函数在某些情况下还是有缺陷的， 例如模式aaaab与主串aaabaaaab匹配时的情况：

数据结构课件 第四章 串和数组

数据结构课件 第四章 串和数组

else {
s->str=(char*)malloc((len+1)*sizeof(char));
//分配空间
if (!s->str) return ERROR;
s->str[0..len]=string_constant[0..len];
//对应的字符赋值
s->length=len;
//赋予字符串长度
串的抽象数据类型定义
functions:
// 有13种之多
StrAssign(&T, chars) // 串赋值，生成值为chars的串T
StrCompare(S,T)
// 串比较，若S>T，返回值大于0…
StrLength(S)
// 求串长，即返回S的元素个数
Concat(&T, S1, S2) // 串连接，用T返回S1＋S2的新串
type unsigned char String[MAX_STRING];
第二种是在程序执行过程中，利用标准函数malloc和free动态
地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串
的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目
的存储空间，从而提高存储资源的利用率。类型定义如下所示：
（4）串连接 int Concat(STRING *s1,STRING s2) { STRING s; StringAssign(&s,s1->str); //将s1原来的内容保留在s中 len=Length(s1)+Length(s2); //计算s1和s2的长度之和 free(s1->str); //释放s1原来占据的空间 s1->str=(char*)malloc((len+1)*sizeof(char)); //重新为s1分配空间

精品课件-数据结构实用教程(C语言版)-第四章 串

精品课件-数据结构实用教程(C语言版)-第四章 串

； commander
, 4, 3) , 1, 9) , 9, 1)
r 长度为 0 的子串——空串，为“合法”串
Index (S, T, pos) （子串的定位函数） 初始条件：串S和T存在，T是非空串，
1≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同
的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。
char s[MAXSIZE]; 0 1 2 3 4 5 6 7 8 9 10 …
a b c d e f g h i j k \0
MAXSIZE-1 …
3. 讨论顺序串中定长串连接的基本运算。
串连接：把两个串S1和S2首尾连接成一个新串S，即 S≤S1+S2。
实现串的运算时，其基本操作为“字符序列的复制”。 下面以串连接为例讨论之，串的连接算法中需分三种情况处理，
插入串T。
例如： S = chater ，T = rac ， 则执行 StrInsert(S, 4, T)之后得到 S = character
StrDelete (&S, pos, len)
初始条件：串S存在 1≤pos≤StrLength(S)-len+1。
操作结果：从串S中删除第pos个字符 起长度为len的子串。
int curlen; } SeqString; 定义一个串变量：SeqString s； 这种存储方式可以直接得到串的长度：s.curlen+1 如图
s.data 0 1 2 3 4 5 6 7 8 9 10 … abcdefgh i j k
s.curlen
MAXSIZE-1 …
(2) 在串尾存储一个不会在串中出现的特殊字符作为串的终结符 ，以此表示串的结尾。比如C语言中处理定长串的方法就是这样， 它是用‘\0’来表示串的结束，如图所示。 这种存储方法不能直接得到串的长度，而是用判断当前字符是否 是‘\0’来确定串是否结束，从而求得串的长度。此时的串长为 隐含值，有时不便于进行某些操作。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

昌
顺序存储结构
大
链接存储结构
学
索引存储结构
科
技 学
不讲
院
6
4.2.1 串的顺序存储结构
南• 1．顺序存储的类型定义
昌• 顺序串的类型定义与顺序表的定义相似，可以用一个字符
大 型数组和一个整型变量表示，其中字符数组存储串，整型
学 变量表示串的长度。
科 技•
如串S=“Beijing”，字符串从S.ch[0]单元开始存放，用‘\0’
{ p=(linkstring *)malloc(LEN); p->data=t[k++];
y->next=p; y=p;}
y->next=NULL; return(s);
}/* L_STRASSIGN */
26
（2）求链串长度函数L_strlen(head)：求带头结点 链串head的长度。
南 昌
图4-2
十分浪费。
8
4.2.1 串的顺序存储结构
• （2）紧凑存储。同样存
南 昌
储S="Hello boy"，用紧
大 凑格式一个地址能存四
学 个字符，如图5-3所示。 科 技 紧凑存储的优点是空间
学 利用率高，缺点是对串
院 中字符处理的效率低。
存储地址 1000 1001 1002 1003
字长为4
}/* S_STRLEN */
22
（3）顺序串的比较函数S_strcmp(s1, s2)：比较两个顺序串的 大小。若s1=s2，则函数返回0；若s1＞s2，则函数返回正数； 若s1＜s2，则函数返回负数。
/* 两个顺序串比较函数，函数返回值为0、正数或负数 */
南int S_strcmp(s1, s2)
学 linkstring *s; char t[ ];
char t[] =“rogram”
科
{ int k=0; linkstring *y, *p; s=(linkstring*)malloc(LEN);
技 学
s->data='#' ; s #
y=s;
/* r为指向队尾指针 */
院
while(t[k]!='\0') /* 将字符串常量t依次赋给链串s */
昌seqstring *s1, *s2; 大{ int i=0, flag=1, m=0, n1, n2; 学 n1=S_strlen(s1); n2=S_strlen(s2);
S1:abcde S2:abcde
科 while ((flag==1)&&(i<=n1)&&(i<=n2))
技 { i++;
/* 求带头结点链串head的长度函数 */ int L_strlen(head) linkstring *head;
大 { linkstring *p; int i;
学
p=head->next; /* 指向链串head的首结点 */
科
for(i=1;p!=NULL;i++) /* 统计链串中结点的个数 */
科 技 串名
学 院
串元素
串值
n为串长
不包含任何字符的串称为空串（Empty String），
空串的长度为零。
2
• 串相等:
• “BeiJing 2010” “BeiJing 2010”
南•
一个串中任意个连续的字符组成的子序列称为该串的子 串，包含子串的串相应地称为该子串的主串。
昌 •例如：“a”、“ab”、“abcd”都是主串“abcde”的子串。
科
技• 对于结点大小为1的链串，其类型定义如下：
学 院
/* 链串结点大小为1的结点类型 */
typedef struct strnode
{ char data;
/* data为结点的数据域 */
struct strnode *next; /* next为指针域 */
} linkstring;
/* linkstring为链串类型 */
图4-3 9
4．顺序串的类型定义
南
昌 顺序串的类型定义与顺序表类似，可定义为：
大
#define STRMAX 64
学
typedef struct node
科
{ char data[STRMAX];
技
int slen;
学 院
}seqstring;
/* seqstring为顺序串的类型 */
10
4.2.2 串的链接存储结构
学
在串s1第i个字符位置之后插入字符串s2，例如，执行
科
insert(s2, 3,“THIS”) 后，s2=“b1b2b3THISb4…bm”。
技 学
（6）串删除delete(s,
i,
j)：
院
从串s第i个字符开始，连续删除j个字符。若不足j个字
符，则删除到s的最后一个字符。
例如，s=“good lucky to you!”，执行delete(s, 6, 6)后，
}/* S_STRASSIGN */ 21
南（2）求顺序串的长度函数S_strlen(s)：求顺
昌 序串s的长度。
大
学 /* 求顺序串长度函数 */
科 int S_strlen(s)
技 seqstring *s;
学 院
{ printf("\n\t顺序串长度length=%d\n", s->slen); return (s->slen);/* 返回顺序串的长度 */
串常量与串变量 • 串常量:在程序执行过程中，其值不能改变的量
南昌大学•例串E：rr变or量(“o:在ver程flo序w执”)行中 过“程ov中erf，lo其w”值是是直可接以量。改变的量 科 技 注意 不能使用赋值语句对串变量进行赋值运算。 学 院
5
4.2 串的存储结构
南 • 常用的串的存储方式有：
技 学 院
{ char c; int j=1; printf("\n\n\t\t请输入一个字符串，以#作为结束: "); scanf("%c", &c); while(c!='#' &&j<MAX)
{ s->data[j]=c; j++; scanf("%c", &c); }
s->data[j]='\0'; s->slen=j-1; }
11
2．改进的链接存储方法
• 改进的链接存储方法是：让链表中每个结点存放多个字符。
• 通常，将链表中每个结点数据域存储的字符个数称为结点的
南 大小。 昌 大 学 科 技 学 院•当结点大小m＞1（例如m = 4）时，链串最后一个结点的各
个数据域不一定被m个字符占满。此时，应在每个串的末尾
还没有被占用的数据域里加上一个串的结束标志
学 来表示串的结束，则串S的存储示意图下图所示。
院
7
4.2.1 串的顺序存储结构
• 2．存储方式
南• 当计算机按字节（Byte）为单
存储地址
字长为4
昌
位编址时，一个存储单元刚好 存放一个字符，串中相邻的字
大 学•
符顺序地存储在地址相邻的存 储单元中。 当计算机按字（例如1个字为
1000 1001 1002 1003
linkstring *head ; /* head是链串的头指针 */15
• 对于结点大小不为1的链串，其类型定义为：
南
/* NODESIZE为链串结点的大小，由用户自定义 */ #define NODESIZE 4
昌 typedef struct strnodem
大 { char data[NODESIZE]; /* data为结点数据域 */
1．一般的链接存储方法
南 • 采用链接存储结构的串称为链串。
昌 • 链串与链表的差异:在于其结点的数据域为字符类型。
大 • 下图就是一个字符串链接存储结构的示意图。
学
科
技 学
•
串的链接存储结构的优点： 便于字符的插入和删除运算。
院 • 串的链接存储结构的缺点：
存储空间的利用率很低。
访问链串的子串比访问顺序串的子串效率要低，
科 技
32位）为单位编址时，一个存 储单元可以由4个字节组成。 此时顺序存储结构又有非紧凑
学 院•
格式和紧凑格式两种存储方式。 （1）非紧凑存储。设串 S="Hello boy"，计算机字长为
32位（4个Byte），用非紧凑
格式一个地址只能存一个字符，
如图4-2所示。其优点是运算 处理简单，但缺点是存储空间
（例如‘\0’或‘@’），以表示串的结束，
12
3．链串的类型定义
• 链串和单链表的差异仅在于其结点数据域为字符类型。
南 • 链串中每个结点有两个域：数据域data存放一个字符或
昌 一个字符串（对于结点大小不为1的链串），指针域
大 next存放指向下一个结点的指针。一个链串则由头指针
学 head惟一确定。
s=“good to you！”。
19
4.3.2 顺序串上基本运算的实现
南（1）顺序串的赋值函数S_strassign(s)：将从键盘
昌 输入的一串字符赋给串变量s。
大/* 顺序串建立函数，从键盘输入字符串赋给顺序串变量s */ 学 void S_strassign(s)
科 seqstring *s;
大
学