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

数据结构串

  • 格式：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章串


设主串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. 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的子串。
❖ 特别地，空串是任意串的子串，任意串是其自 身的子串。
❖ 称两个串是相等的，当且仅当这两个串的值相 等。即两个串的长度相等，并且各个对应位置 的字符也都相等时才相等。