当前位置：文档之家 › 数据结构串

数据结构串

  • 格式：ppt
  • 大小：278.50 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

数据结构——第4章 串(C#)

数据结构——第4章 串(C#)

将当前链串的所有结点?nstr将q结点插入到尾部将q结点插入到尾部将链串t的所有结点?nstr将q结点插入到尾部尾结点的next置为null返回新建的链串5求子串substrij返回当前串中从第i个字符开始的连续j个字符组成的子串ຫໍສະໝຸດ 第4章 串4.1 串的基本概念
4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an"（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的 长度，当n=0时，称为空串。
4.2 串的存储结构
4.2.1 串的顺序存储结构－顺序串
和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下：
class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算 法如下：
public string DispStr() { int i; string mystr=""; if (length==0) mystr = "空串"; else { for (i=0;i<length;i++) mystr+=data[i].ToString(); } return mystr; }
数据结构-第4章串(C#)

数据结构-第4章串(C#)

时间复杂度
最坏情况下，需要进行n*(m+1)次比较，其中n为主串长度，m为模式串长度。 因此，时间复杂度为O(n*m)。
KMP模式匹配算法
算法思想
当模式串与主串的子串不匹配时，KMP 算法能够利用已经匹配的部分信息，将 模式串向右滑动一定的距离，继续进行 比较。这个滑动的距离是通过预处理模 式串得到的“部分匹配表”来确定的。
字符串操作示例
01 02 03
``` 替换示例 ```csharp
字符串操作示例
01
string str = "Hello, World!";
02
string newStr = str.Replace("World", "C#"); // 将子字符 串"World"替换为"C#"
03
Console.WriteLine(newStr); // 输出: Hello, C#!
字符串操作示例
• foreach (var fruit in fruits)
字符串操作示例
{
Console.WriteLine(fruit); // 依次输出: apple banana orange
字符串操作示例
}
```
03 串的模式匹配算法
朴素模式匹配算法
算法思想
从主串的第一个字符开始，将模式串与主串的相应子串进行逐个字符的比较，若 相等，则继续比较后续字符，否则从主串的下一个字符开始重新比较。
自定义串类应用举例：文本编辑器功能实现
{
private MyString currentText;
自定义串类应用举例：文本编辑器功能实现
数据结构 第四章 串

数据结构 第四章 串

第四章 串
4.1 4.2
串类型的定义 串的表示和实现
4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示
第四章 串
4.1 串类型的定义
一、串的基本概念 定义：字符串是 n ( 0 ) 个字符的有限序列
记作 S = “c1c2c3…cn”
其中:
S 是串名字 “c1c2c3…cn”是串值 ci 是串中字符 n 是串的长度
4.1 串类型的定义
一、串的基本概念
串中任意个连续字符组成的子序列称为该串的
子串，包含子串的串相应地称为主串。
子串在主串中首次出现时的该子串的首字符 对应的主串中的序号，定义为子串在主串中的
序号（或位置）
例如，设A和B分别为 A=“This is a string” B=“is”
4.1 串类型的定义
提取子串的算法示例
pos = 3, len = 3 infini ty
pos = 6, len = 4 infini ty
fin
len S[0]-pos+1
超出 len > S[0]-pos+1
合法参数条件: Pos>=0, Pos<=S[0], Len>=0
len <=S[0]-pos+1
求子串的过程即为复制字符序列的过程，将串S中的 第pos个字符开始长度为len的字符复制到串T中。
1、串的插入的动态实现过程 s.length+ t.length
SA
l o v el y
pos Tl o
t.length
vely
g irl!
t.length
1、串的插入的动态实现过程 s.length+ t.length
数据结构第4章 串

数据结构第4章 串

ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;
数据结构-第4章 串

数据结构-第4章 串

真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。
数据结构 第四章 串

数据结构 第四章 串


13 14
15
16 17
maxsize
…
t
h
i
s
i
s
a
s
t
r
i
n
g
\0
顺序串示意图
联接算法 SeqString *stract(SeqString *s1,SegString *s2) { for(int i=0; i<=s2curlen; i++) s1str[s1curlen++]=s2str[i]; return s1; }
求子串算法 SeqString *substr(SeqString *s, int i, int j) { SegString *ss=new SegString[1]; for(int k=0, sscurlen=0; k<j&&i+k< scurlen; k++) ssstr[sscurlen++]=sstr[i+k]; ssstr[sscurlen]=’\0’; return ss; }
第四章 串
内容 串及其运算 串的 存储结构 串运算的实现
4.1 串及其运算
4.1.1 串的基本概念
串(String)是由零个或多个字符组成的有限序列。 一般记为 S= ˝a1a2a3……an˝ n≥0 其中S为串名, 双引号括住的字符序列是串值; ai 的可以字母、数字或其它字符。字符个数n为串 的长度。 当n=0时为空串（S=˝˝）。串中任意个 连续字符组成的有限子序列称为该串的子串。
（3）求串长（strlen） strlen(s)是获得字符串S长度的函数。例如： s= ˝string ˝; 则strlen(s)的值为6。 strlen(˝Get length of the string˝ )的值为24。 （4）求子串（substr） strlen(s, i, j)表示从字串S的第i个字符开始抽出j个字符构成 新的字串的函数。其中1≤i≤strlen(s), 1≤i≤strlen(s)-i+1。 例如：s= ˝Get a substring from the string˝ 则substr(s,7,9)的值为˝substring˝ 。 （5）串比较（strcmp） strcmp(s1,s2)为获得字串s1和s2比较结果的函数。当s1<s2 时，函数值小于0，当s1=s2时，函数值等于0。 当s1=s2 时，函数值大于0。
数据结构(串)

数据结构(串)

数据结构(串)数据结构(串)1.介绍1.1 定义数据结构(串)是计算机科学中的一种基础数据结构，用于存储和操作一系列具有相同数据类型的元素的集合。

1.2 特性- 顺序存储：串中的元素按照在字符串中的顺序存储。

- 长度可变：可以动态改变串的长度。

- 计数方式：通常使用0开始计数。

1.3 应用字符串的数据结构广泛应用于文本处理、模式匹配、编译器设计等领域。

2.串的基本操作2.1 创建串：定义一个字符串变量并为其分配内存空间。

2.2 销毁串：释放字符串变量占用的内存空间。

2.3 清空串：将字符串中的元素清空，使字符串变为空串。

2.4 判断串是否为空：判断字符串是否为空串。

2.5 获取串的长度：获取字符串中元素的个数。

2.6 拷贝串：将一个串拷贝到另一个串中。

2.7 两个串：将两个串连接成一个新的串。

2.8 截取子串：从原串中截取一段子串。

2.9 查找子串：在串中查找指定子串的位置。

2.10 替换子串：在串中将指定子串替换成新的子串。

2.11 插入子串：在串中指定位置插入一个子串。

2.12 删除子串：从串中删除指定的子串。

3.串的存储结构3.1 顺序存储结构：使用一维数组存储字符串的字符元素。

3.2 链式存储结构：使用链表存储字符串的字符元素，每个节点存储一个字符。

4.串匹配算法4.1 暴力匹配算法：逐个比较字符串中的字符，若匹配失败则向后移动。

4.2 KMP算法：利用前缀函数预处理，避免重复比较已经匹配的字符。

4.3 Boyer-Moore算法：从匹配串的末尾开始比较，利用坏字符规则和好后缀规则跳过不必要的比较。

5.附件本文档不涉及附件。

6.法律名词及注释- 数据结构：指计算机科学中研究数据存储方式及其相关操作的学科。

- 串：也称为字符串，是由零个或多个字符组成的有序序列。

第四章 串

第四章 串

主串S首次出现的位置；否则返回0
– 例如
• 主串S = • 子串T = CD • 则index(S,T)，返回子串T在S中，第一次出现的位置3
19
串的模式匹配
Brute-Force算法基本思想： • 从目标串s 的第一个字符起和模式串t的第一个字符进行比较 • 若相等，则继续逐个比较后续字符，否则从串s 的第二个字 符起再重新和串t进行比较。 • 依此类推，直至串t 中的每个字符依次和串s的一个连续的字 符序列相等，则称模式匹配成功，此时串t的第一个字符在串s 中的位置就是t 在s中的位置，否则模式匹配不成功。
两式联立可得：“T0…Tk-1”= “Tj-k…Tj-1”
注意：j为当前已知的失配位置，我们的目标是计算新起点k。式中仅剩 一个未知数k，理论上已可解！
奇妙的结果：k仅与模式串T有关！
27
新起点k怎么求？
根据模式串T的规律：“T0…Tk-1”=“Tj-k …Tj-1” 由当前失配位置j(已知)，归纳计算新起点k的表达式。
j=next[j]的位置(即模式串继续向右移动)，再比较 si 和 tj 。
依次类推，直到下列两种情况之一： 1)j退回到某个j=next[j]时有 si = tj，则指针各增1，继续匹配； 2)j退回至j=0，此时令指针各增1，即下一次比较 si+1和 t0 。
30
串的模式匹配：KMP算法
• 模式串的next函数
6
串的基本概念
4.两个字符串相等的充分必要条件为两个字符串的长度相等，并 且对应位置上的字符相等。
例如：‘abcd’ ≠ ‘bacd’ ‘abcd’ = ‘abcd’
7
串的基本操作
1.给串变量赋值 ASSIGN(S1,S2)
数据结构中的串

数据结构中的串

if(pos>=0) { n=StrLength(S); m=StrLength(T); i=pos; while ( i<=n-m ) { SubString( sub,S,i,m );//返回S中从i起长度为m的子串 if( SubCompare (sub,T)!= 0 ) i++; else return i; } // while
StrCompare(S, T) : 若S>T 返回>0;若S=T 返回=0;若
S<T 返回<0;
StrLength( S ) :串S存在，返回S中元素的个数，称为串
的长度
more
串的基本操作
Concat( &T, S1,S2 ) : 用T返回S1和S2联接而成的新串 SubString( &Sub,S,pos,len ) : 用Sub返回串S的第pos个
▪ 两个串之间可以进行比较。 ▪ 称两个串相等，当且仅当这两个串的值相等，包括
两个串的长度相等，并且各个对应位置的字符都相 等。
▪ 当两个串不相等时，可按“字典顺序”分大小。令
s= “s0s1…sm-1” (m>0) t= “t0t1…tn-1” (n>0) ▪ 假设，两者最大有前k个子序列相等（最大相等前缀子
▪ 串中任意个连续的字符组成的子序列称为该串的子串。包含 子串的的串相应地称为主串。通常称字符在序列中的序列号 为该字符在串中的位置。子串在主串中的位置则以子串第0 个字符在主串的位置来表示。
4.1 串的定义和操作
▪ 例如：下面a，b，c，d都是串
▪ a=“BEI”
长度为3
▪ b=“JING”
长度为4
44
第4章 串
数据结构第4章串

数据结构第4章串


设主串s=“ababbabbcda”，模式t=“abbcd”：
↓i=3
第1趟： a b a b b a b b c d a a b b
↑j=3 ↓i=2
第2趟： a b a b b a b b c d a a
↑j=1 ↓i=6
第3趟： a b a b b a b b c d a a b b c
↑j=4
设主串s=＂ababbaabbabbcde＂，子串t=＂ abbabb ＂ 第1 趟 a b a b b a a b b a b b c d e a b b a b b
↑j=3 next[3]=1 ↓i=3
第2 趟 a b a b b a a b b a b b c d e a b b a b b
串的堆存储结构
在C语言中 ，提供了一个称之为“堆” 的共享空间，可以在程序运行过程中， 由系统利用函数malloc( )和free( )来动 态地申请或释放一块连续空间。 串的堆式存储结构仍属于串的顺序存储 结构范畴，但与前面的定长顺序存储方 式存在的区别在于其存储空间是在程序 执行过程中动态分配的，而不是静态分 配的。
• KMP算法：
int KMP _ StrIndex (char *s,char *t,int pos)
/*从主串s的第pos个字符开始找首次与模式串t相等的子串*/
{ int i=pos,j=1,slen,tlen; while (i<=s[0] && j<=t[0] ) if (j==0||s[i]==t[j]) { i++; j++; } else j=next[j]; /*j指针回溯*/ if (j>t[0]) return i-t[0]; else return 0; }
数据结构 串

数据结构 串

1第4章串主要内容： 串的基本概念 串的定长顺序表示 串的堆分配存储表示 串的块链存储表示2串的概述串是一种常用于非数值处理的线性结构从数据结构角度看，串是一种线性表，其特殊之处在于其数据元素类型被限定为字符。

因此也可以称串是一种特殊的线性表。

从数据类型来看，串由字符构成，其操作特点和线性表大不相同，是完全不同的数据类型。

串通常以串的整体作为操作对象，因为串中的单个元素常常是无意义的。

而线性表的操作对象多以单个元素为操作对象串是元素类型被限制为字符的特殊线性表3§ 4.1 串的类型定义1. 串的基本概念串(String)：是零个或多个字符组成的有限序列。

一般记作S= ‘a 1a 2a 3…a n ’，S 是串名，单引号括起来的字符序列是串值； a i (1≤i ≤n )可以是字母、数字或其它字符；i 是字符在序列中的序号，也称为该字符在串中的位置。

n 是串中所包含的字符个数，称为该串的长度。

引号不属于串。

两个串相等，当且仅当两个串值相等，即长度、位置相等。

4空串和空白串空串(Empty String)：长度为零的串，不包含任何字符。

空白串(Blank String)：空格也是串集合中的一个元素，通常将仅由一个或多个空格组成的串称为空白串。

注意：空串和空白串不同。

例如“”和“”分别表示长度为1的空白串和长度为0的空串。

为了清楚起见，用“φ”来表示空串5子串和主串子串：串中任意个连续字符组成的子序列称为该串的子串。

主串：包含子串的串相应地称为主串。

B 是A 的子串。

B 在A 中出现了两次，B 在A 中的序号(或位置)为3。

注意：空串是任意串的子串，任意串是其自身的子串子串的位置：通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号，定义为子串在主串中的序号(或位置)。

例如：设A=“This is a string”，B=“is”。

问B 是A 的子串吗？如果是，B 在A 中出现了几次？其位置是几？62. 串的抽象数据定义ADT string {数据对象: D 数据关系: R 基本操作：StrAssign(&S,chars);StrCopy(&S,S1); StrEmpty(&S);StrCompare(S1,S2);StrLength(S); ClearString(&S);Concat(&S,S1,S2); SubString(&Sub,S,pos,len);Index(S,Sub,pos); Replace(&S,Sub,T); StrInsert(&S,pos,Sub); StrDelete(&S,pos,len);DestroyString(&S);}ADT String7§4.2 串的顺序表示和实现串的顺序存储：即用一组地址连续的存储单元存储串值中的字符序列非紧缩格式：一个存储单元中只存放一个字符，所需存储单元个数即是串的长度。

数据结构 第2章 串


if(j==m) return(i);
} return(-1);
算法评价： 比较总次数：m*(n-m+1) 时间复杂度：O(m*(n-m))
}
若n>>m：O(m*n)
2)匹配算法——KMP算法
t= aaabcaaadcaaadaaaabc p= aaada
算法：如果存在一个整数k(k<j)，使得模式P中 开头k个字符与前面k个字符相同，则只要从 模式P中的p[k]开始与正文Ｔ中的t[i]开始比较， 就可以省去前面的k次比较。
01 2 3 4 5
m x不在p中，或只在末尾 1）求d(x)
m-i-1 否则
2）不匹配,向右移d(x)(对应后,从最后一个字符比较) 匹配，取i-m+1
0 1 2 3 4 5 6 7 8 9 10 12 14 16 18 20 22
2) 非紧缩格式是以一个存储单元为单位, 也就是一个存储单元
中仅放一个字符。 在一个程序中使用的串变量较少, 且各串变 量的长度又都较短时，如果希望该程序处理字符的速度尽可能 快, 那么选择非紧缩格式比较合适。 在这种存储格式中, 串的长 度是隐式的, 串所占用存储单元的个数即为串长。
例: 假设一存储单元可以存放4个字符, 同样 对于字串(This is a flag), 共需14个存储单元, 其存放的直观表示如表 4.2。 这种存储格式 对存储空间的利用率仅为25%, 但如上所述, 该方法在字符加工处理方面会节省时间。
2、算法： 回溯法（朴素的模式匹配法） KMP算法 BM算法
1) 回溯法 成功匹配:返回首次出现的起始位置
失败匹配:返回-1
匹配算法——简单算法
t=“abcdabcdabccdacd”

[数据结构]-串

[数据结构]-串简介字符串（String）是由字符组成有限序列，是常⽤的⼀种⾮数值数据，串的逻辑结构是线性表，串是⼀种特殊的线性表，限制其元素类型是字符，串的操作特点与线性表不同，主要对⼦串进⾏操作，通常采⽤顺序存储结构存储。

串的基本概念串定义：⼀个串是由n(n>=0) 个字符组成的有限序列记做s="s0 s1 s2" ，其中s是串名，⼀对双引号括起来的字符序列 s0 s1 s2 是串值，s1（i=0,1,n-1）为特定字符集中的⼀个字符，⼀个串中包含的字符数称为串的长度，例如，字符串 “data” 长度是4，双引号不计⼊长度，长度为0的串称为空串，记做“”，由多个空格字符构成的字符串 “” 称为空格串。

⼀个字符在串中的位置称为该字符在串中的序号（Index）,⽤⼀个整数表⽰，约定串中的第⼀个字符的序号为0，-1表⽰该字符不在指定串中。

⼦串：由串s中任意连续字符组成的⼀个⼦序列 sub称为s的⼦串（Substring）,s称为sub的主串。

例如 “at” 是“data” 的⼦串，特别的，空串是任意串的⼦串，任意串s都是他⾃⾝的⼦串，除了⾃⾝之外，s的其他⼦串称为s的真⼦串。

⼦串序号是指该⼦串⾸字符在主串中的序号。

例如 “dat” 在 “data” 中序号是0串⽐较规则与字符⽐较规则有关，字符⽐较规则犹豫所属字符集的编码决定，通常在字符集中同意字母的⼤⼩写形式有不同的编码。

两个串相等是指，串长度相等且哥哥对应位置是上的字符也相等。

两个串的⼤⼩由对应位置的收个不同字符的⼤⼩决定，字符⽐较次序是从头开始依次向后。

当两个串长度不等⽽对应位置的字符都相同时候，较长的串定义为较⼤。

串的抽象数据类型串与线性表是不同的抽象数据类型，两者操作不同，串的基本操作有：创建求长度读取设置字符，求⼦串，插⼊，删除，连接，判断等，查找，替换，其中求⼦串，插⼊，查找等操作1以⼦串为单位，⼀次操作处理多个字符。

数据结构——串


7
三、串的基本操作 C语言中常用的串运算 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result;
(1) 求串长(length) int strlen(char s); //求串的长度
例如：printf(“%d”,strlen(s1)); 输出13
char strcat(char s1 , char s2)
该函数将串s2复制到串s1的末尾，并且返回一 个指向串s1的开始处的指针。
例如：strcat(a3,”/”)
strcat(a3,a2);
2020//4//a143=“dirtreeformat/file.mem”
9
(4)串比较（compare)
A=“This is a string” B=“is” B在A中出现了两次，其中首次出现所对应的主串
位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子
串。
2020/4/14
5
二、串的抽象数据定义
• ADT String { • 数据对象:D={ai| ai
16
顺序串的类型定义和顺序表类似： typedef char ElemType;
typedef struct { ElemType ch[maxstrlen]; int length;
}sstring; //其优点是涉及到串长操作时速度快。
2020/4/14
17
4.2.2 堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存 放字符串序列，但它们的存储空间是在程序执行过程中动态 分配而得。所以也称为动态存储分配的顺序表。在C语言中， 利用malloc和realloc,free等动态存储管理函数，来根据实 际需要动态分配和释放字符数组空间。这样定义的顺序串类

数据结构(串)

数据结构(串)数据结构(串)数据结构中的串（String）是由字符构成的有限序列。

在计算机科学中，串是一种基本的数据结构，被广泛应用于字符串处理、文本搜索、模式匹配等领域。

1. 串的定义和基本操作串可以使用多种方式来定义和表示，常见的方式有：- 定长顺序存储表示：使用数组来存储串，数组的长度和最大串长相等，不足的部分用特定字符填充（通常用空格）。

- 堆分配存储表示：使用堆（动态内存分配区）来存储串，可以根据实际需要动态分配和释放串的存储空间。

- 串的块链存储表示：将串分成多个块，将每个块使用链表进行表示，将各块在一起组成完整的串。

串的基本操作包括：- 串的赋值：将一个串赋值给另一个串。

- 串的连接：将两个串按顺序连接成一个新的串。

- 串的比较：比较两个串的大小关系。

- 串的截取：从一个串中截取出一段子串。

- 串的插入：将一个串插入到另一个串的指定位置。

- 串的删除：删除一个串中指定位置的字符或一段子串。

- 串的替换：将一个串中指定位置的字符或一段子串替换成另一个串。

2. 串的匹配算法串的匹配是指在一个主串中查找一个模式串的过程。

常见的串匹配算法包括：- 朴素匹配算法：也称为暴力匹配算法，是最简单的匹配算法。

它从主串的第一个字符开始，与模式串逐个字符进行比较，若不匹配，则主串向后移动一位，直到找到匹配的子串或主串遍历完。

- KMP算法：即Knuth-Morris-Pratt算法，通过利用模式串自身的信息，减少字符的比较次数。

该算法具有线性时间复杂度，是一种高效的匹配算法。

- Boyer-Moore算法：基于模式串中的字符发生不匹配时的启发式策略，通过跳跃式地移动模式串，减少字符的比较次数，从而提高匹配效率。

3. 串的应用串作为一种基本的数据结构，在实际应用中具有广泛的用途，主要包括以下几个方面：- 字符串处理：串在文本编辑、编译器设计、语法分析、文件操作等方面都有广泛应用。

- 模式匹配：串的匹配算法常被用于字符串搜索、DNA序列分析、信息检索等领域。

数据结构课件——串


(2)串复制 strcpy(&T,S); 将串 S 复制到串 T 中 例如: 例如:strcpy(s3,s1); //s3='dirtreeformat dirtreeformat' //s3= dirtreeformat (3)联接 (3)联接 concat(&T,S1,S2) 返回由S1 S2连接而成的新串 S1和 连接而成的新串. 用T返回由S1和S2连接而成的新串. 例如: 例如:strcat(&T,s3,S2) //s3="dirtreeformatfile.mem dirtreeformatfile.mem" //s3= dirtreeformatfile.mem
2.求子串算法 2.求子串算法 substr(st &sub,st s,int pos,int len) {if(pos<1||pos>s[0]||len<0||len>s[0]{if(pos<1||pos>s[0]||len<0||len>s[0]pos+1) return error; Sub[1….len]=s[pos pos+len.len]=s[pos…pos+len Sub[1 .len]=s[pos pos+len-1]; Sub[0]=len; Return ok;}
注意:空串和空格串的不同,例如' 注意:空串和空格串的不同,例如' ' ''分别表示长度为 分别表示长度为1 和''分别表示长度为1的空格串和长度 的空串. 为0的空串. 子串: 子串:串中任意个连续字符组成的子序列 称为该串的子串, 称为该串的子串,包含子串的串相 应地称为主串. 应地称为主串. 串中位置: 串中位置:通常将字符在序列中的序列号 称位串中位置. 称位串中位置.子串在主串中 首次出现时的该子串的首字符 对应的序号. 对应的序号.

数据结构-串

数据结构-串数据结构-串概述：串是由零个或多个字符组成的有限序列，是一种常见的数据类型。

在计算机科学中，串经常被用来表示文本字符串。

本文将介绍串的基本定义、操作以及相关的应用。

1.串的定义1.1 字符集字符集是构成串的基本元素，它包含了一个或多个字符。

1.2 串的长度串的长度是指串中字符的个数，通常用n表示。

1.3 串的表示串的表示可以使用字符数组、指针、链表等方法，具体的表示方法根据实际情况选择。

2.串的基本操作2.1 串的初始化初始化一个空串或者将一个已有的串赋值给另一个串变量。

2.2 串的连接将两个串连接起来形成一个新串。

2.3 串的截取对一个串进行截取，截取出一个子串。

2.4 串的比较比较两个串是否相等或者大小关系。

2.5 串的插入在一个串的指定位置插入一个子串。

2.6 串的删除从一个串中删除指定位置的子串。

2.7 串的替换在一个串中将指定位置的子串替换为另一个子串。

3.串的应用3.1 字符串匹配判断一个串是否包含另一个串，可以使用字符串匹配算法，如朴素模式匹配算法、KMP算法等。

3.2 文本编辑在文本编辑器中对文本进行插入、删除、替换等操作，就是基于串的操作。

3.3 编码解码在计算机通信中，对数据进行编码和解码时，也会使用到串的操作。

3.4 数据压缩在数据压缩算法中，也会使用到串的操作。

本文档涉及附件：无法律名词及注释：1.串：在计算机科学中，串指由零个或多个字符组成的有限序列。

2.字符集：字符集是指包含了一个或多个字符的集合，比如ASCII、Unicode等。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构
5
定长顺序存储表示的典型操作实现
❖ 串联接
Status Concat(SString &T, SString S1, SString S2) {
// 用T返回由S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE。
if(S1[0]+S2[0] <= MAXSTRLEN) { // 未截断
数据结构
2
串的抽象数据类型定义
ADT Stack{
数据对象: D={ai| ai(- CharacterSet,i=1,2,...,n,n>=0} 数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n} 基本操作：
StrAssign(&T,chars) chars是字符常量。生成一个其值等于chars的串T。
StrCopy(&T,S)
串S存在则由串S复制得串T
StrEmpty(S) 串S存在则若S为空串,返回真否则返回假
StrCompare(S,T)串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T, 则返回值<0
StrLength(S) 串S存在返回S的元素个数称为串的长度.
ClearString(&S)
if (pos > 0) {
n = StrLength(S); m = StrLength(T); // 求得串长
-m+1) {
SubString(sub, S, i, m); // 取得从第 i 个字符起长度为 m 的子串
if(StrCompare(sub,T) != 0) ++i ;
for (i=1; i<=S1[0]; i++) T[i] = S1[i];
for (i=1; i<=S2[0]; i++) T[S1[0] + i] = S2[i];
T[0] = S1[0]+S2[0];
else return i ;
// 找到和 T 相等的子串
} // while
} // if
return 0;
// S 中不存在满足条件的子串
} // Index
数据结构
4
串的顺序表示和实现
❖ 串的顺序存储结构是用一组连续的存储单元依次存放串中的每个数据 元素。有两种实现方式：第一种是事先定义字符串的最大长度，字符 串存储在一个定长的存储区中，即静态数组表示法。第二种是在程序 执行过程中，利用标准函数malloc和free动态地分配或释放存储字符 串的存储单元它的好处在于：可以根据具体情况，灵活地申请适当数 目的存储空间，从而提高存储资源的利用率，即动态数组表示法(字符 指针)。
串S存在将S清为空串
Concat(&T,S1,S2) 串S1和S2存在用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len) 用Sub返回串S的第pos个字符起长度为len的子 串
Index(S,T,pos)
若主串S中存在和串T值相同的子串,则返回它在主串S中第
pos个字符之后第一次出现的位置,否则函数值为0
❖ 例如，可利用判等、求串长和求子串等操作实现串的定位函数 Index(S,T,pos) 和串的置换操作 Replace(S,T,V)。
❖ int Index(String S, String T, int pos) {
// 若主串S中第 pos 个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0。
3
❖ 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数 来实现。在使用时，应以该语言的参考手册为准。但在上述抽象数据 类型定义的13种操作中，串赋值StrAssign、串复制StrCopy、串比 较StrCompare、求串长StrLength、串联接Concat以及求子串 SubString等6种操作构成串类型的最小操作子集。即这些操作不可 能利用其他串操作来实现，反之，其他串操作可在这个最小操作集上 实现。
❖ 静态数组表示(定长顺序存储表示) #define MAXSTRLEN 255 //用户可在255以内定义最大串长 typedef char SStrint[MAXSTRLEN + 1]; //0号单元存放串的长度
❖ 动态数组表示（堆分配存储表示） typedef struct{ char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL int length; //串长度 }HString;
可以出现在其他字符之间。由一个或多个空格组成的串
称为空格串(blank string)，例如“ ”，“ ”和
“ ”是三个空格串，它们的长度为串中空格字符的个
数，分别为1，3和5。为了清楚起见，我们将用符号
“Φ”表示“空串”。
数据结构
1
❖ 串中任意个连续的字符组成的子序列称为该串 的子串。包含子串的串相应地称为主串。通常 称字符在序列中的序号为该字符在串中的位置。 子串在主串中的位置则以子串的第一个字符在 主串中的位置来表示。
Replace(&S,T,V) 用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(&S,pos,T) 在串S的第pos个字符之前插入串T
StrDelete(&S,pos,len)
从串中删除第pos个字符起长度为len的子串
DestroyString(&S) }ADT String
串S存在数,则据串结S被构销毁
串
❖ 串(String) ：是一种特殊的线性表。其特殊性在于限 定了所有的数据元素必须都是字符。
❖ 假设串s=“a1a2a3…an”（n>=0），那么s是串的 名，用双引号括起来的字符序列是串的值；串中字符的 数目n称为串的长度。零个字符的串称为空串（null string），它的长度为零。
❖ 在各种应用中，空格通常是串的字符集合中的一个元素，
❖ 例：a='BEI',b='JING',c='BEIJING',d='BEI JING‘ 则串长分别为3,4,7,8,且a,b都是c,d的子串。
❖ 特别地，空串是任意串的子串，任意串是其自 身的子串。
❖ 称两个串是相等的，当且仅当这两个串的值相 等。即两个串的长度相等，并且各个对应位置 的字符也都相等时才相等。