当前位置：文档之家 › 串的定义及其基本运算

串的定义及其基本运算

  • 格式：ppt
  • 大小：333.50 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

串的基本概念

串的基本概念

串的基本概念
串（string）是由0个或多个字符组成的有序序列，称为字符串。

它通常被表示为一个记号，例如s='abcdefg'，其中s是字符串的名字，a、b、c等
是串的值，可以是字母、数字或者字符。

串的长度是指串中元素的个数。

例如，在字符串s='abcdefg'中，长度为7。

空串是不含任何字符的串，其长度为0。

子串是指一个主串中任意连续字符组成的字符串。

例如，在字符串
s='abcdefg'中，'a'、'bc'、'defg'等都是子串。

此外，当两个串的长度相等，并且对应位置的元素也相等时，这两个串被认为是相等的。

请注意，以上解释是基于计算机科学中关于串的基本概念。

在其他领域，如数学、物理或哲学中，串的概念可能会有所不同。

数据结构(C语言版)_第3章 串与数组

数据结构(C语言版)_第3章 串与数组
typedef struct lnode {
char data; struct lnode *next;
}lstring;
3.3.3 串的存储结构——链式存储结构
当结点大小>1时，可以采用块链结构。
#define CHUNKSIZE 100
/*可由用户定义块的大小*/
typedef struct Chunk
第三章 串与数组
本章要点
➢字符串的基本概念与基本运算 ➢字符串的存储和基本运算的实现 ➢数组的概念和基本运算 ➢数组的存储结构 ➢特殊矩阵的压缩存储及运算 ➢广义表的概念及相关术语 ➢广义表的存储形式
3.1 “文学研究助手”案例导入
“文学研究助手”引例：请从下面的英文文章里，统计其中 good出现的次数和位置，并查找单词the所在的行号，该行中出 现的次数以及在该行中的相应位置。
3.4.1 数组的定义
数组是n个具有相同类型的数据元素构成的有限序列，数组 中的数据是按顺序存储在一块地址连续的存储单元中。
数组中的每一个数据通常称为数组元素，数组元素用下标 区分，其中下标的个数由数组的维数决定。
若线性表中的数据元素为非结构的简单元素，则称为一维 数组，又称为向量；若一维数组中的数据元素又是一维数组结 构，则称为二维数组；依次类推，若二维数组中的元素又是一 个一维数组结构，则称作三维数组。
3.3.4 串的基本操作的实现算法
第二种顺序存储方式下几种基本操作的算法
算法1：串连接操作 算法2：串比较操作 算法3：取子串操作 算法4：串插入操作 算法5：串删除操作 算法6：串置换函数 算法7：子串定位操作
3.3.5 串的应用
【例3-1】设计一个算法求串s中出现的第1个最长重复子串 及其位置。

ch4

ch4

第四章串本章介绍了串的逻辑结构，存储结构及串上的基本运算，由于在高级语言中已经提供了较全善的串处理功能，因此本章的重点是掌握在串上实现的模式匹配算法。

同时这也是本章的难点。

但是从全书来讲，这属于较简单的一章内容。

1.串及其运算(领会)(这些内容比较容易理解，不用死记)串就是字符串，是一种特殊的线性表，它的每个结点仅由一个字符组成。

空串：是指长度为零的串，也就是串中不包含任何字符(结点)。

空白串：指串中包含一个或多个空格字符的串。

不同与空串，它的结点就是一个空格字符。

在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。

子串在主串中的序号就是指子串在主串中首次出现的位置。

如A="I love you"B="love",则B在A中的序号为3，注意空格也是字符。

空串是任意串的子串，任意串是他自身的子串。

串分为两种：串常量和串变量。

串常量在程序中不能改变，串变量则可以。

关于串的基本运算，基本上在C语言中已经学过，主要有求串长strlen(char *s)、串复制strcpy(char *to,char *from)、串联接strcat(char *to,char *from)、串比较charcmp(char *s1,char *s2)和字符定位strchr(char *s, char c)等这些基本运算通过练习来掌握。

2.串的存储结构(简单应用)串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。

串的顺序存储结构简称为顺序串，顺序串又可按存储分配的不同分为静态存储分配的顺序串和动态存储分配的顺序串。

静态的意思可简单地理解为一个确定的存储空间，它的长度是不可变的。

如直接使用定长的字符数组来定义一个串。

它的优点是涉及串长的操作速度快，因为它的最大长度是不变的。

动态存储分配就是在定义串时不分配存储空间，直到需要使用时按所需串的长度分配存储单元给它，并且在运行中还可以根据需要变化串的长度，这就是动态分配。

数据结构第4章数组和串

数据结构第4章数组和串
1
● 教学目的：理解抽象数据类型数组的概念， 掌握数组的不同存储结构的实现及应用，了 解广义表的相关概念，掌握串的逻辑结构、 存储结构及其基本运算。
● 教学重点：数作在不同 存储结构上的实现。 ● 教学难点：带状矩阵的压缩存储；稀疏矩 阵的三元组表实现及其转置算法，堆结构的 串操作实现；串的模式匹配算法。
矩阵的压缩存储
printf("Array a:\n"); k=0; for(i=0;i<N;i++)//输出矩阵A { for(j=0;j<N;j++) if(i<j)printf("%5d",sa[M-1]); else printf("%5d",sa[i*(i+1)/2+j]); printf("\n"); } printf("Array b:\n"); k=0; for(i=0;i<N;i++)//输出矩阵B { for(j=0;j<N;j++) if(i>j)printf("%5d",sb[M-1]); else printf("%5d",sb[j*(j+1)/2+i]); printf("\n"); }}
矩阵的压缩存储
由此可见，要唯一表示一个稀疏矩阵，在存储三 元组表的同时还需存储该矩阵总的行数、列数及非 零元个数。 练习：写出图4-9(a)所示稀疏矩阵的三元组表。
三元组表（也是线性表）的存储方式主要有两种： 顺序存储和链式存储，从而可引出稀疏矩阵的两种 压缩存储方法：三元组顺序表和十字链表。 3、三元组顺序表
矩阵的压缩存储

C语言-串

C语言-串

4.2 串的顺序表示与实现
4.2.2 顺序串的基本运算
（1）串的赋值。串的赋值即把字符串常量cstr中的每一个字符赋值给串S。串的 赋值算法实现如下。 void StrAssign(SeqString *S,char cstr[]) /*串的赋值操作*/
{ int i=0; for(i=0;cstr[i]!=’\0’;i++) /*将常量cstr中的字符赋值给串S*/ S->str[i]=cstr[i]; S->length=i;
T->length=S.length;
/*将串S的长度赋值给串T*/
}
4.2 串的顺序表示与实现
（5）比较两个串的大小。
int StrCompare(SeqString S,SeqString T)
/*串的比较操作*/
{
int i;
for(i=0;i<S.length&&i<T.length;i++) 两个串中的字符*/
4.1 串
4.1.2 串的抽象数据类型
1．数据对象集合 串的数据对象集合为{a1，a2，…，an}，每个元素的类型均为字 符。 串是一种特殊的线性表，区别仅仅在于串的数据对象为字符集合。 串具有线性表的特征：除了第一个元素a1外，每一个元素有且只有 一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有 一个直接后继元素。数据元素之间的关系是一对一的关系。
4.1 串
2．基本操作集合
串的操作通常不是以单个元素作为操作对象，往往是一连串的字 符作为操作对象。例如，在串中查找某个子串，将一个串连接在另一 个串的末尾等。
为了说明的方便，定义以下几个串： S=”I come from Beijing”， T=”I come from Shanghai”， R=”Beijing”， V=”Chongqing”， 则StrLength(S)=19，StrLength(T)=20，StrLength(R)=7， StrLength(V)=9。

ADT字符串

ADT字符串

字符串与字符数组的关系

字符数组：字符数组是C语言中最常见的数组 类型

Char S[]；定义一个字符数组变量 字符串常量，以字符数组的形式存储，数组的元素 分别存储字符串的各个字符，并以’\0’标志字符的 结束

字符串：


字符串的用法：与字符数组的使用基本 相同
串的基本运算
为叙述方便起见，先定义几个相关的变量： char str1[20]="dir/bin/appl“ char str2[20]="file.asm"，str3[30],*p；
用T[i‥j]表示T的子串“titi+1…tj”(0≦i≦j≦n-1)； P[i‥j]表示P的子串"pipi+1…pj"(0≦i≦j≦m-1)。
依 次 将 目 标 串 中 的 子 串 T[i‥i+m-1] 和 模 式 串 P[0..m-1] 进 行 比 较 ， 若 T[i..i+m-1]=P[0..m-1]( 即 titi+1‥ti+m-1"="p0p1…pm-1") ，则称从位置 i 开始的匹 配成功；若 T[i..i+m-1]≠P[0..m-1] ，则称从位置 i 开始 的匹配失败。上述的位置 i 又称为位移，当 T[i..i+m1]=P[0..m-1] 时 ， i 称 为 有 效 位 移 ； 当 T[i..i+m1]≠P[0..m-1]时，i称为无效位移。 例如， T=“acaabc” ， P=“aab” ，当 i 为 0 、 1 时为 无效位移，当i为2时为有效位移。这样，串匹配问题 可简化为找出某给定模式串 P在给定目标串 T中首次 出现的有效位移。

05第五章串


5.3 串的存储结构
串作为线性表的一个特例，用于线性表的存储结构也适用于串。但是， 由于串中数据元素全部为字符，故存储表示有其特殊之处。
对串的存储可以有两种处理方式：一种是将串定义成字符型数组，串的
存储空间分配在编译时完成，不能更改，这种方式称为串的静态存储结
构；另一种是串的存储空间在程序运行时动态分配，这种方式称为串的
/*串的顺序存储结构表示*/
const int maxsize=maxlen； //maxlen表示串的最大容量
struct segstring
{

char ch[maxsize]； //存放串的值的一维数组
int len；
//当前串的实际长度
}；
5.3.1 串的顺序存储结构
串的实际长度可在定义的最大长度范围内随意，超过最大长度的串值则 被舍去，称之为截断。当计算机按字节（byte）为单位编址时，一个机 器字（存储单元）刚好存放一个字符，串中相邻的字符顺序的存储在地 址相邻的字节中；当计算机按字（word）为单位编址时，一个存储单元 由若干字节组成。这时，顺序存储结构有紧凑格式和非紧凑格式两种存 储方式。 1. 紧凑格式 所谓紧凑格式就是在存储单元中尽量的多存储字符。例如，S=“Love China”，按紧凑格式可以存放在三个存储单元中（假设计算机的字长为 32位，即4bytes），如图5-1所示。
在早期的程序设计语言中，就引入了串的概念。随着计算机技术的发 展，计算机越来越多地用于解决非数值处理问题，这些问题所涉及的 主要操作对象是字符串（简称串）。例如在管理信息系统中，用户的 姓名、地址、商品的名称、规格等都是字符串，字符串已成为数据处 理中不可缺少的数据对象。目前，大多数程序设计语言都支持串操作， 可以执行各种运算，并提供相应的串函数。然而，在不同的应用中， 处理的字符串有不同的特点，为了有效的对字符串进行处理，就要了 解串的内部表示和处理过程，从而根据具体情况使用合适的存储结构。 信息检索系统、中文信息处理系统、学习系统、自然语言翻译系统以 及音乐分析处理系统等等都是基于串的基本运算来设计和开发的软件 系统。

第4章 串

沈阳工业大学
数
据
结
构
与
算
法
(4)串比较（compare) int strcmp(char *s1,char *s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0 或大于0时分别表示s1<s2、s1=s2或s1>s2 例如：result=strcmp(“baker”,”Baker”) result>0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result<0 （5）字符定位(index) char strchr(char *s,char c); 该函数是找字符c在字符串中第一次出现的位置，若找到 则返回该位置，否则返回NULL。 例如：p=strchr(s2,’.’); p 指向“file”之后的位置 s2=“file.cpp”
}
沈阳工业大学
数
据
结
构
与
算
法
2堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元 存放串值字符序列，但它们的存储空间是在程序执行过程中 动态分配而得。所以也称为动态存储分配的顺序表。在C语 言中，利用动态存储管理函数，来根据实际需要动态分配和 释放字符数组空间。 typedef char *string; //c中的串库相当于此类型定义
沈阳工业大学
数
据
结
构
与
算
法
串中任意个连续字符组成的子序列称为该串的子串 ，包含子串的串相应地称为主串。通常将子串在主串中 首次出现时的该子串的首字符对应的主串中的序号，定 义为子串在主串中的序号（或位置）。例如，设A和B分 别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其中首 次出现所对应的主串位置是3。因此，称B在A中的序号 （或位置）为3。 特别地，空串是任意串的子串，任意串是其自身的 子串。 通常在程序中使用的串可分为两种：串变量和串常 量。

串


静态存储分配的顺序串
#define MaxStrSize 256 typedef struct { char ch[MaxStrSize]; int length; }SeqString;
// 设串最长为256 设串最长为
动态存分配的顺序串
char *string; typedef struct { char *ch int length; }HString;
head
head D T R A R E
(A)结点大小为 (A)结点大小为4 结点大小为4
T U S ^ A C T S U
(B)结点大小为 (B)结点大小为1 结点大小为1
#define NodeSize 80 typedef struct node { char data[NodeSize]; struct node *next; }LinkStrNode, *LinkString;
// 结点类型
用顺序方式存储串值时， 用顺序方式存储串值时，由于在串类型的定义中预先规定 一个串允许的最大长度，则当多数串长较小时， 一个串允许的最大长度，则当多数串长较小时，空间的利 用率很低。另一方面，由于限定了串的最大长度， 用率很低。另一方面，由于限定了串的最大长度，使串的 某些操作如联接、 某些操作如联接、置换等受到很大限制或者产生错误的结 果。 用链表存储串值时，虽然由于链表结构比较灵活， 用链表存储串值时，虽然由于链表结构比较灵活，使串长 不受限制，但同样受到存储密度的制约， 不受限制，但同样受到存储密度的制约，因此存储串的链 表通常是“块的链表” 但由此使串的操作复杂化， 表通常是“块的链表”，但由此使串的操作复杂化，且存 在着结点大小取多大较合适的问题。 在着结点大小取多大较合适的问题。 在很多实际应用的串处理系统中，采用的是另一种动态存 在很多实际应用的串处理系统中， 储结构，它的特点是： 储结构，它的特点是：每个串的串值各自存储在一组地址 连续的存储单元中， 连续的存储单元中，但它们的存储地址是在程序执行过程 中动态分配得到的。这种存储结构称为堆分配存储结构 堆分配存储结构。 中动态分配得到的。这种存储结构称为堆分配存储结构。

串 串

对于插入操作，如果串中最后一个字符的存储位置后面没有剩余空间或 剩余空间的长度小于将要插子串的长度，那么要完成这个子串的插入操 作，必须先申请一块新的、长度合适的存储块。然后，先复制插入点前 的子串，再接上插入的子串，最后在复制插入点后的子串。这样的操作 较麻烦。当删除一个子串时，或者用“F”符代替被删除的字串字符（ 这时的“F”个数应等于被删除子串的长度）；或者移动原串中的字符 将存储的空间压缩以实现删除。
上一页
返回
5.2 串的存储结构
如同线性表一样，串也有顺序存储结构和链式存储结构。 任何一种存储结构对于不同串的运算并非都是十分有效的。对于串的插
入和删除操作，顺序存储结构是不方便的，而链式存储结构则显得方便 些。对于访问串的字符操作，如访问单个字符，对链式存储结构是不困 难的；当要访问一组连续的字符时，则用链式存储结构要比顺序存储结 构麻烦。所以应针对不同的应用来选择串的存储结构。 5.2.1 串的顺序存储结构 串的顺序存储结构称为顺序串。顺序串就是把串中的字符依次存放在一 组连续的存储空间中。也就是用向量存储串。例如，对于串 =“PROGRAM”，当用向量来存储时，其存储状态如图5-1所示。
上一页 下一页Leabharlann 返回5.2 串的存储结构结点大小大于1的结点结构类型如下： struct linkstringnode {char data[chunksize];/* chunksize 为结点大小*/ struct linkstringnode *next; } 串链式存储时，链串通常是由头指针唯一确定的，其操作与线性表类似
该软件采用Client/Server （客户/服务器）体 系结构，包含了电子电路原理图设计、多层印制 电路板设计（包含印制电路板自动布线）、通用 可编程逻辑器件设计、模拟电路与数字电路混合 信号仿真及分析、图表生成、电子表格生成、同 步设计、联网设计、3D模拟等功能。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
例如操作前：s1=＂he＂，s2=＂ bei＂，
则操作结果是s1=＂he bei＂
（4）串比较 strcmp(s1,s2); 操作结果：若s1==s2，返回值为0；若s1<s2, 返回值<0；若 s1>s2, 返回值>0。
result= strcmp("abc","Abc");/* result>O */
5页
2020/9/19
数据结构(C语言版)
第5章 串
（2）串拷贝strcpy (s1,s2) ; 执行操作：将s2的串值赋值给s1。 操作结果：串s1的值与串s2的值相等，s1原来的值被覆盖掉。 例如 strcpy (str3,str1)
（3）连接操作 ：strcat (s1,s2) ; 操作结果：将字符串s2连接 在s1的后面，s2不改变。
例如：substr(str1, str3,5,3)，则str3="bin"
再例如：substr(str1, str3,14,3)，则str3=NULL
（6）子串定位 strindex(s,t)；找子串t在主串s中首次出 现的位置
操作结果：若t∈s，则操作返回t在s中首次出现的位置， 否则返回值为-1。
串的链式存储结构简称为链串。其结点数据域为单个
子串的位置：子串在主串中首次出现时，该子串的 首字符对应主串的序号称为子串在主串中的位置。
例如，设A和B分别为
A="This is a string”，B ="is“
则B是A的子串,A为主串。且位置是3。
4页
2020/9/19
数据结构(C语言版)
第5章 串
特别规定，空串是任意串的子串，任意串是其自身 的子串。 串相等：两个串相等，是指两个串的长度相等且对 应字符都相同。
数据结构(C语言版)
第5章 串
5.1 串的定义及其基本运算 5.2 串的存储结构 5.3 串运算的应用
小结
1页
2020/9/19
数据结构(C语言版)
第5章 串
本章学习目标
串（即字符串）是一种特殊的线性表，它的数据 元素仅由一个字符组成。如在学生信息管理系统 中，学生姓名、籍贯等信息是作为字符串处理的。 通过本章学习，应掌握如下内容：
3页
2020/9/19
数据结构(C语言版)
第5章 串
２．几个术语
空白串：仅由一个或多个空格组成的串称为空白串 (Blank String)。
应注意空串和空白串的不同，如" "和""分别表示长 度为1的空白串和空串。
子串与主串：串中任意连续的字符组成的子序列称
为该串的子串。包含子串的串相应地称为主串。
（8）删除 StrDelete(s,i,len) ; 操作条件：串s存在，1≤i≤strlen (s)， 0≤len≤strlen (s)-i+1。 操作结果：删除串s 中从第i个字符开始的长度为len
的子串，s的串值改变。 （9）串替换 strrep(s,t,r) ; 操作条件：串s，t，r存在，t不为空。 操作结果：用串r 替换串s中出现的所有与串t相等的子
如：strindex(＂abcdebda＂,＂bc＂)=2
strindex(＂abcdebda＂,＂ba＂)=-1
7页
2020/9/19
数据结构(C语言版)
第5章 串
4 （7）串插入 StrInsert(s,i,t) ; 操作条件：串s,t存在，1≤i≤strlen(s)+1。 操作结果：将串t插入到串s 的第i个字符位置上。
因为必须留一字节来存放串 终结符’\0’。
若不设置终结符，可用一个整数length来表示串的长度，此时 顺序串的类型定义完全和顺序表类似：
typedef struct
{ char elem[MAXSIZE] ;
int lenபைடு நூலகம்th ;
s.curlen
} SeqString ;
0 1 2 3 4 5 … MAXSIZE-1
串，s的串值改变。
8页
2020/9/19
数据结构(C语言版)
第5章 串
5.2 串的存储结构 ——顺序存储和链式存储结构
5.2.1 串的顺序存储
1．静态存储的顺序串：是指按预定义的大小，为每一个串变
量分配一个固定长度的存储区。
如：#define MAXSIZE 256
但最多只能存放255个字符，
char s[MAXSIZE];
result= strcmp ("exam1.c","exam1.c");/* result=O */
result= strcmp ("Joe',"Joseph");/* result<O */
6页
2020/9/19
数据结构(C语言版)
第5章 串
（5）求子串substr (s1,s2,m,n) ；操作结果：返回从串s1 的第m个字符开始的长度为n的子串，并赋值给s2。当 n=0时得到的是空串。
5.1.2 串的基本运算
为叙述方便起见，先定义几个相关的变量：
char str1[20]="dir/bin/appl“ char str2[20]="file.asm"，str3[30],*p； int result； （1）求串长strlen(str); 操作结果：返回串str的字符个数。若 str为空串，则返回值为0。 例如 strlen(str1) /* 值为12 */
串的基本概念；
串的存储结构；
串的基本操作。
2页
2020/9/19
数据结构(C语言版)
第5章 串
5.1 串的定义及其基本运算 5.1.1 串的基本概念
１．串的定义
串（又称字符串）（String）是由零个或多个任意字符 组成的序列。一般记作：
s=＂c1 c2 … cn＂ (n≥0) 其中s 是串名，双引号括起来的字符序列是串值，引号 本身不属于串的内容；c i(1≤I≤n)可以是字母、数字或其 它字符，称为串的元素，是构成串的基本单位，i是它 在整个串中的序号；n为串的长度，表示串中所包含的 字符个数，当n=0时，称为空串(Empty String)，通常 记为Ф，它不包含任何字符。
s.data S t u d e n
9页
2020/9/19
数据结构(C语言版)
第5章 串
2．动态存储分配的顺序串 稍复杂的定义
较简单的定义
typedef struct{
typedef char *string;
5.2.2 串的链式存储
char *ch; int length; }Hstring ;