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

数据结构第四章串

  • 格式：pdf
  • 大小：584.69 KB
  • 文档页数：32

下载文档原格式

  / 32

合集下载

严蔚敏数据结构-第四章 串

严蔚敏数据结构-第四章 串
S1 4 a b c d S2 2 e f T 6 a b c d e f
15
(2)S1串长 最大串长 串长<最大串长 串长 最大串长; S1,S2串长和 最大串长 串长和>最大串长 串长和 最大串长;
S1 6 a b c d e f S2 6 g h i j k l T 8 a b c d e f g h
3
串的抽象数据类型的定义： 串的抽象数据类型的定义： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet, i=1,2,...,n, n>=0} 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=2,...,n} 基本操作： 基本操作： StrAssign(&T, chars)
11
作业： 作业： 1.用5种串的基本操作（StrAssign、StrCompare、StrLen Concat、SubString）来逻辑实现StrInsert(&S, pos, T)操作 、 操作. ）
Status StrInsert(String S, int pos , String T) { if ……….. return error; , , ); ); ); );
chars是字符串常量。生成一个其值等于chars的串 。 是字符串常量。生成一个其值等于 的串T。 是字符串常量 的串
StrCopy(&T, S)
存在则由串S复制得串 串S存在则由串 复制得串 存在则由串 复制得串T
StrEmpty(S)
存在则若S为空串 串S存在则若 为空串 返回真否则返回假 存在则若 为空串,返回真否则返回假
Sub返回串 的第pos个字符起长度为 返回串S的第 个字符起长度为len的子串 用Sub返回串S的第pos个字符起长度为len的子串

计算机数据结构第四章串

计算机数据结构第四章串
空串,用” ”表示.
2、串的抽象数据类型定义
ADT String{ 数据对象：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。
2.求子串SubString(&Sub,S,pos,len)
初始条件：串S存在， 1≤pos≤StrLength(S)
且 0≤len≤StrLength(S)-pos+1 。 操作结果：用Sub返回串S的第pos个字
符起长度为len的子串。 算法思想：求子串的过程即为复制字符
序列的过程，将串S中从第pos个字符 开始长度为len的字符序列复制到串 Sub中。
基本运算实现
1.串联接Concat（&T，S1，S2）
S1[0]
S2[0]
S1
S2
T
T[0]
MAXSTRLEN
( a ) S1[0]+S2[0]≤MAXSTRLEN
S1[0]
S1
S2[0]
S2

T
S2中被截去的部分
T[0]
MAXSTRLEN
( b ) S1[0]<MAXSTRLEN 而S1[0] +S2[0]>MAXSTRLEN
若S=T，则返回值=0；若S<T，则返回值<0
int comparestr(SString S,SString T) {
int i; for (i=1;i<=s[0]&&i<=t[0];i++)

数据结构——第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;

数据结构（C语言版）第4章串

数据结构（C语言版）第4章串

第4章串串：限定数据元素类型的线性表。

1 逻辑结构1.1 定义位串：数据元素属于{0,1}ASCII码串: 数据元素属于ASCII码字符集。

数字串：数据元素属于整数集合2 顺序串///////////////////////////////// // 项目路径：7动态顺序串/////////////////////////////////2.2 构造/析构（测试函数Test1）template <class T>String<T>:: String( ){ m_Data=NULL; m_Size=m_Length=0; }template <class T>String<T>::String(T a[], int n){ m_Size = m_Length = n;m_Data = new T[m_Size];if(!m_Data) throw "内存不够，上溢";for(int i=0; i<m_Length; i++)m_Data[i]=a[i];}template <class T>String<T>::String(String &s) // 拷贝构造函数{ m_Size = m_Length = s.m_Length;m_Data = new T[m_Size];if(!m_Data) throw "内存不够，上溢";for(int i=0; i<m_Length; i++)m_Data[i]=s.m_Data[i];}template <class T>String<T>:: ~String( ){ delete []m_Data; }2.3 比较（测试函数Test2）// 重载<template <class T>bool String<T>::operator<(String &s){ for(int i=0; i<m_Length && i<s.m_Length; i++) { if(m_Data[i]<s.m_Data[i]) return true;if(m_Data[i]>s.m_Data[i]) return false;}if(m_Length<s.m_Length) return true;return false;}// 重载==template <class T>bool String<T>::operator==(String &s){ for(int i=0; i<m_Length && i<s.m_Length; i++) if(m_Data[i]!=s.m_Data[i]) return false; if(m_Length==s.m_Length) return true;return false;}2.4 取子串、连接（测试函数Test3）// 取子串template <class T>String<T> String<T>::Substr(int pos,int len) { if(pos+len>m_Length) // 预防子串长度越界len=m_Length-pos;String<T> s;s.m_Length=s.m_Size=len;s.m_Data = new T[s.m_Size];if(!s.m_Data) throw "内存不够，上溢";for(int i=0; i<len; i++)s.m_Data[i]=m_Data[pos+i];return s;}// 连接stemplate <class T>void String<T>::Concat(String s){ if(m_Length+s.m_Length > m_Size) // 空间不够ReNew(m_Length+s.m_Length);for(int i=0; i<s.m_Length; i++)m_Data[m_Length+i] = s.m_Data[i];m_Length += s.m_Length;}// 重新分配串的存储空间template <class T>void String<T>::ReNew(int size){ T *p=new T[size]; // 重新申请空间 m_Size=size;for(int i=0; i<m_Length; i++) // 数据迁移p[i]=m_Data[i];delete []m_Data; // 释放原串空间 m_Data = p;}2.5 插入、删除（测试函数Test4）// 第i个位置上插入stemplate <class T>void String<T>::Insert(int pos, String s){ if(m_Length+s.m_Length > m_Size) // 空间不够 ReNew(m_Length+s.m_Length);for(int i=m_Length-1; i>=pos; i--) // 向后移位 m_Data[i+s.m_Length] = m_Data[i];for(i=0; i<s.m_Length; i++)m_Data[pos+i] = s.m_Data[i];m_Length += s.m_Length;}// 删除子串template <class T>void String<T>::Delete(int pos,int len){ for(int i=pos+len; i<m_Length; i++) // 向前移位 m_Data[i-len] = m_Data[i];m_Length -= len;}2.6 顺序串的评价优点：访问子串方便，缺点：空间大小不灵活，插入、删除费时。

数据结构第4章串.

数据结构第4章串.

4.1 串
4.1.1 串的基本概念
串: 由零个或多个字符组成的有限序列。 s = “ a 1a 2 … a n ” s—串名 a1a2… an —串值 ai为字符 ( n≥0)
|s|—串的长度，即串中字符的数目。 空串：零个字符的串，记作φ = “”。空格串 |φ|＝0
子串：串中任意个连续的字符组成的子序列 主串：包含子串的串。 例，串 “eij” 是串 “beijing” 的子串， “beijing” 称为主串。 字符在串中的位置：字符在序列中的序号 子串在主串中的位置：子串的第一个字符在主 串中的位置。
(9) 串替换StrReplace(S，i，T) 操作条件: 串S，T存在。 操作结果: 用串T替换串S中自第i个字符开始，长度与T相 等的子串，S的串值改变。
2. 串的存储 顺序串: 串的顺序存储结构。串中的字符被顺 序地存放在一组地址连续的存储单元中。 定长:按预定义的大小为串变量分配一个长度 固定的存储区。 定长顺序串用字符数组描述：
#define MAXSIZE 255 /*假设要处理的串的长度不 会超过255*/ char S[MAXSIZE]；
串的实际长度可在这个预定义长度的范围内 随意设定，超过予定义长度的串值则被舍去 (“截断”)
0 C
1 h
2 i
3 n
4 e5 sLeabharlann 6 e \0… …
MAXSIZE-1
串长有两种表示方法: • 用一个整数来存储串的长度。串可以结构描述:
} int StrCat(SeqString *S1, else SeqString *S2) { /* 将 S2 连接到 S1 的末尾构成新串， for(i=0;i<MAXSIZE-S1若S2完全连接到S1末尾则返回 >len;i++) 1，否则返回零*/ S1->s[S1->len+i]=S2->s[i]; { int i; S1->len=MAXSIZE ; if(S1->len+S2return 0; >len<=MAXSIZE) } { }

数据结构-第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)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。

数据结构讲义第4章-串

数据结构讲义第4章-串

串长的表示方法: 1,用一个不会出现在串中的特殊字符在串值的尾部 来表示串的结束.例如,C语言中以字符｀\0′表示 串值的终结. 2,用s[0]存放串的实际长度,串值存放在 s[1]~s[MAXSIZE]. 3,类似顺序表,另设一个整数表示串长: typedef struct{ char ch[maxstrlen]; int length; }sstring;
即最坏情况下的时间复杂度是O(n*m).
2.改进后的模式匹配算法
一种对BF算法做了很大改进的模式匹配算法是克努特(Knuth),莫里 斯(Morris)和普拉特(Pratt)同时设计的,简称KMP算法. (1)KMP算法的思想 (2)next函数
(3) KMP算法 int StrIndex_KMP(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]; /*回溯*/ if (j>t[0]) return i-t[0]; /*匹配成功,返回存储位置*/ else return –1; }
示例
第一趟
第二趟
第三趟
第四趟
4.4 串的应用举例
1,文本编辑 2,信息检索 在常用的高级语言及开发环境中,大多系统本身都提供了串的 类型及大量的库函数,用户可直接使用,这样会使算法的设计 和调试更方便容易,可靠性更高.
习题四
4.1 设s='I AM A STUDENT',t='GOOD',q='WORKER' 求: strlength(s),substring(s,8,7),index(s,'A'),Replace(s,' STUDENT',q),concat(substring(s,6,2),concat(t,subst ring(s,7,8))) 4.2 从顺序串r中删除其值等于ch的所有字符,要求以较高 效率实现. 4.3令 s='aaab',t='abcabaa',u='abcaabbabcabaacbacba'. 试分别求出它们的next值 .

数据结构 第四章 串

数据结构 第四章 串

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。

数据结构第四章串

数据结构第四章串

(2) 置换操作：用联接算法来实现。用在求子串序号（a,b，h）中得到的 ind 将a分成3部分：第一部分是b在a中的第一个位置前的子串substr （a,1,ind－1）;第二部分是b（以c来代替）；第三部分是b在a中的最后一个 位置后的子串substr（a,ind+m,n）。 即 a substr(a,I,ind-1)||c||substr(a,ind+m,n)
4. 2 串的基本运算
对于串的基本操作，许多高级语言均提供了相应的运算或标准 库函数来实现。下面仅介绍几种常用的串运算。 (1)联接(concatenation) 联接是串的最基本，最重要的运算。两个串的联接是将一个串 紧接着放在另一个串的末尾。联接用符号“||”表示。 例如：a＝”bei” b=“jing” a || b=“beijing” (2)求子串(substr) SUBSTR(a，m，n)功能: 从a 中截取子串，从第m个字符到第n个 字符的子串（m<n)。子串应是将串a中取出从标号m开始的连续n －m＋1个字符。 例：SUBSTR(“ABCDEFG”,2,3)＝”BC” 利用求子串及联接两种运算可以完成对串的插入、删除和修改。 例如： a＝“bejing” b=“iy” ，将b插入到a的第二个字符之后 得到新的串s，则 s=substr(a,1,2) || b || substr(a,3,6) =“beiyjing”
（5）置换(repleace) 置换运算repleace(a,b,c)表示在a中搜索b，若b是a的 子串，就以c代替b，若不是，则经置换后，a不变。 例如：a=“monday”, b=“mon”, c=“thurs” repleace(a,b,c)=“thursday” 置换运算是将串a中所有的子串b用c来代替。 在一部分程序设计语言中没有实现，仍可用前三种运 算来完成。 置换算法过程：实现置换运算repleace（a,b,c），同 样也是在a中搜索是否与b相同的子串，若有，以c来代 替，再继续向下搜，直到在a中找不到和b相同的子串 为止。

数据结构第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; }

数据结构-第04章-串

数据结构-第04章-串

❖串赋值 StrAssign ❖串比较 StrCompare ❖求串长 StrLength ❖串联接 Concat ❖求子串 SubString
最小操作子集
算法4.1
int Index(String s, String T, int Pos){ if(pos>0){ n=StrLength(s); m=StrLength(T); i=pos; while (i<=n-m+1) { SubString(sub,s,I,m); If ( StrCompare(sub,T) != 0 ) ++ i; else return i; //返回子串在主串中的位置 }//while
串是由零个或多个字符组成的有限序列。 s= ‘a1a2…an ‘ (n≥0)
其中：s为串名； a1a2…an是串的值； 可以是字母、数字或其他字符； 字符串字符的数目n称为串的长度。
❖零个字符的串称为空串（Null String） ，长 度为0；以两个相邻的单引号来表示：
❖ s= ’’；
❖由若干个空格字符组成的串称为空格串，如： s= ’ ’；空格应计入串的长度中，如： s= ’It’s cool!’的长度为10。
❖假设S1,S2和T都是SString型的串变量,且串 T是由串S1联结串S2得到的,即串T的值的前 一段和串S1的值相等,串T的值的后一段和 串S2的值相等,则只要进行相应的"串值复制 "操作即可,对超长部分实施"截断"操作.
❖以下是串联接可能出现的三种情况:
S1 S2 T
aea
bf b
c \0 c
第4章 串
第四章 串
❖
4.1 串及基本运算
❖

数据结构-第四章串

数据结构-第四章串

数据结构-第四章串串也叫字符串，它是由零个或多个字符组成的字符序列。

基本内容1 串的有关概念串的基本操作2 串的定长顺序存储结构，堆分配存储结构；3 串的基本操作算法；4 串的模式匹配算法;5 串操作的应⽤。

学习要点1 了解串的基本操作，了解利⽤这些基本操作实现串的其它操作的⽅法；2 掌握在串的堆分配存储结构下，串的基本操作算法；3 掌握串的模式匹配算法；第四章串 4.1 串的基本概念4.2 串存储和实现4.3 串的匹配算法4.4 串操作应⽤举例第四章串 4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 4.4 串操作应⽤举例第四章串4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 4.4 串操作应⽤举例4. 1 串类型的定义⼀、串的定义1 什么是串串是⼀种特殊的线性表，它是由零个或多个字符组成的有,a2, a3, ... a n’限序列，⼀般记作s = ‘a1其中 s----串名， a1,a2, a3, ... a n----串值串的应⽤⾮常⼴泛，许多⾼级语⾔中都把串作为基本数据类型。

在事务处理程序中，顾客的姓名、地址；货物的名称、产地。

可作为字符串处理，⽂本⽂件中的每⼀⾏字符等也可作为字符串处理。

下⾯是⼀些串的例⼦：（1）a = ‘ LIMING’（2）b = ‘NANJING UNIVERSITY OF SCIENCE &TECHNOLOGY’（3）c = ‘ DATA STRUCTURE’（4）d = ‘’说明：1) 串中包含的字符个数，称为串的长度。

长度为0的串称为空串，它不包括任何字符，上⾯（4）中的串d 是空串,(5)中的e 是包含⼀个空格符的空格串；2）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。

2 串的有关术语1）⼦串串中任意连续的字符组成的⼦序列称为该串的⼦串例：c = ‘ DATA STRUCTURE’，f=‘DATA’ f是c的⼦串2）⼦串的位置⼦串T 在主串S中的位置是指主串S中第⼀个与T相同的⼦串的⾸字母在主串中的位置。

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

1. 类似顺序表，用一个指针来指向最后一个字符。 描述如下：
#define MAXLEN 256 typedef struct { char ch[MAXLEN]; int len; 如图4.1所示。 ch a b c d e
} SeqString;
…
len
SeqString s; 串的长度：s.len+1
串名
起始地址
如图4.4所示
name length stradr s1 5
s2 …
3 …
…
… a
b
c
d
e
h
i
j
…
图 4.4 带长度的索引表
2. 末尾指针的索引表
索引项的结点类型为： typedef struct { char name[MAXNAME]; char *stradr; char *enadr; } ENode; 如图4.5所示：
•4.1.1 串的基本概念
定义： 是零个或多个字符组成的有限序列。 一般记为：s=“a1a2...an” (n≥0) 其中: s是串的名字; n是串中字符的个数, 称为串的长度 字符在串中的序号称为该字符在串中的位置
术语：
1. 子串 串中任意个连续的字符组成的子序列称为该串的子串。 2. 主串
包含子串的串相应地称为主串。
name enadr stradr
s1 s2 … … …
串名
起始地址
末尾地址
… a
b
c
d
e
h
i
j
…
图 4.5 带末尾指针的索引表
3. 带特征位的索引表
当一个串的存储空间不超过一个指针的存储空间，可以直接将该串存
在索引项的指针域，这样即节约了存储空间，又提高查找速度，但这
时要加一个特征位tag以指出指针域存放的是指针还是串。 索引项的结点类型为： typedef struct { char name[MAXNAME]; int tag; 特征位 union { char *stradr; name tag char value[4]; s1 0 }uval; s2 1 … … }TNode;
4 判断串相等算法 串相等是指两个串的长度及其对应位置的字符完全相同 两个串t和s相等时返回1 int strEqual(SeqString s,SeqString t) {int i=0; if(s.len!=t.len) return 0; else {for(i=0;i<s.len+1;i++) if(s.ch[i]!=t.ch[i]) return 0; return 1;} }
f
g
h
i
\0
…
图4.2 串 的 顺 序 存 储 方 式2
3. 设定长串存储空间 char s[MAXLEN+1] 用s[0]存放串的实际长度，串值存放在s[1]~s[MAXLEN]，字符的 序号和存储位置一致，应用更为方便。 如图所示：
0 1 2 3 4 5 6 7 8 … MAXLEN
5
a
b
c
d
5 串连接运算算法
SeqString strConcat(SeqString s,Seqstring t) {SeqString r; int i,j; for(i=0;i<=s.len;i++) r.ch[i]=s.ch[i]; for(j=0;j<=t.len;j++) r.ch[s.len+j+1]=t.ch[j]; r.len=i+j-1; return r; }
对串的存储方式取决于我们对串所进行的运算。
4.2.1 串的定长顺序存储
用一组地址连续的存储单元存储串值中的字符序列。 为每一个串变量预分配一个固定长度的存储区，如： #define MAXLEN 256 char s[MAXLEN]; 则串的最大长度不能超过256。 可用以下方法 如何标识实际长度 ？
(7) 删除子串操作：StrDelete(S, pos, len)
初始条件: 串S存在，1≤pos≤StrLength(S)且 0≤len≤StrLength(S)-pos+1。 操作结果: 从串S中删除第pos个字符起长度为len
(8) 串复制操作：StrCopy(S, T) 初始条件: 串S 操作结果: 由串T复制得串S。 (10) 串比较操作：StrCompare(S, T)
4.3 串的堆存储结构
特点：
每个串值各自存储在一组地址连续的存储单元中。 但存储地址在程序执行过程中 动态分配 而得。
4.3.1 串名的存储映象
串名的存储映像是串名----串值内存分配对照表，也称为索引表。
表示形式有多种 常见的串名－串值存储映象索引表有如下几种：

1. 带串长度的索引表 索引项的结点类型为： typedef struct { char name[MAXNAME]； int length; 串长 char *stradr; } LNode;
9 子串替换算法 将串s中所有出现的字串s1替换成s2 SeqString RepString(SeqString s,SeqString s1,SeqString s2) {int i; i=Index(s,s1); while(i>=0) {DelString(&s,i,s1.len); InserString(&s,i,s2); i=index(s,s1); } return s; }
e
…
图4.3 串 的 定 长 顺 序 存 储
4.2.2 定长顺序串的基本操作
(以第一种方式作为串的存储结构) 请学生试着完成基本操作算法。可参考书P91~P94 列举几个算法如下：可略讲 1 串赋值操作 将一个数组t赋给串s void assign(SeqString*s,char t[]) {int i=0; while(t[i]!=‘\0’) {s->ch[i]=t[i]; i++;} s->len=i; }
3. 子串在主串中的位置 通常以子串的第一个字符在主串中的位置来表示。
4. 串相等 当两个串的长度相等, 并且每个对应位置的字符都相等， 称两个串是相等的。
4.1.2 串的基本运算
(1) 赋值操作：StrAsign(S, chars) 初始条件: chars是字符串常量。 操作结果: 生成一个值等于chars的串S。 (2) 求串长度：StrLength(S) 初始条件: 串S存在。 操作结果: 返回串S的长度，即串S中的元素个数。 (3) 联接函数：StrCat(S, T) 初始条件: 串S和T存在。 操作结果: 将串T的值连接在串S的后面。
起始地址 或串值
stradr/value
hij\0 …
… a
b
c
d
e
\0
…
图 4.6 带 特 征 位 的 索 引 表
4.3.2 堆存储结构
堆存储结构的基本思想是：在内存中开辟足够多的地址连续的存 储空间作为应用程序中所有串的可利用存储空间，称为堆空间。
3．教学重点：
①熟悉串的七种基本运算的定义及实现方法。 ②熟练掌握基本串匹配算法。
4．教学难点：
模式匹配算法。
第四章 串
4.1 串的定长及基本操作 4.2 串的定长顺序存储及基本操 4.3 串的堆存储结构
4.4 块链存储结构
4.1 串的定义
串是一种特殊的线性表。数据元素仅由一个字符组成。 1 保持线性表前驱、后继的关系； 2 对串整体进行操作。
8 主要讲述定位函数 算法思想如下： 首先将s1与t1进行比较，若不同，就将s2与t1进行比较，...，直到s的某 一个字符si和t1相同，再将它们之后的字符进行比较，若也相同，则如 此继续往下比较，当s的某一个字符si与t的字符tj不同时，则s返回到本 趟开始字符的下一个字符，即si-j+1，t返回到t1，继续开始下一趟的比较， 重复上述过程。若t中的字符全部比完，则说明本趟匹配成功，本趟的 起始位置是i-j+1或i-t[0]，否则，匹配失败。
2串复制运算算法
(将一个串t赋给串s)
void strCopy(SeqString *s,SeqString t) {int i; for(i=0;i<=t.len;i++) s->ch[i]=t.ch[i]; s->len=t.len; } 3 求串长算法 int strLength(SeqString s) { return(s.len+1); }
2. 在串尾存储一个特殊字符作为串的终结符 比如C语言中用’\0’来表示串的结束。 char s[MAXLEN]; 这种存储方法不能直接得到串的长度，是用判断当前字符 是否是’\0’来确定串是否结束，从而求得串的长度。 如图所示：
0 1 2 3 4 5 6 7 8 … MAXLEN -1
a
b
c
d
e
算法实现如下： StrIndex(SeqString s, int pos, SeqString t) {int i, j; if (t.len==0) return(0); i=pos; j=0; while(i<s.len&&j<t.len) if(s.ch[i]==t.ch[j]) { i++; j++;} else { i=i-j+1; j=0;} if(j>=t.len) return(i-j); else return(0); } StrIndex(SeqString s, int pos, SeqString t) {int i, j,start; if (t.len==0) return(0); i=pos; j=0; start=pos; while(i<s.len&&j<t.len) if(s.ch[i]==t.ch[j]) { i++; j++;} else {start++; i=start; j=0;} if(j>=t.len) return(start); else return(0); }