当前位置：文档之家 › 串的抽象数据类型的定义.

串的抽象数据类型的定义.

  • 格式：ppt
  • 大小：230.50 KB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

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

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

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的子串
《数据结构与算法(C++语言版)》第4章_串

《数据结构与算法(C++语言版)》第4章_串


串函数与串的类定义
• 常用的 常用的C++串函数 串函数 • C++的串库（string.h）中提供了许多字符串的操作函数，几 个常用的C++字符串函数及其使用方法如下。 •假设已有以下定义语句：
串函数与串的类定义
• （1）串拷贝函数 • char *strcpy(char *s1, const char *s2)，将字符串s2复制到字 符串数组s1中，返回s1的值。 • char *strncpy(char *s1, const char *s2, size_tn)将字符串s2中最 多n个字符复制到字符串数组s1中，返回s1的值。 • 例如：
串函数与串的类定义
• （3）串比较函数 • int strcmp(const char *s1, const char *s2)，比较字符串s1和字 符串s2。函数在s1等于、小于或大于s2时，分别返回0、小 于0或者大于0的值。 • int strncmp(const char *s1, const char *s2, size_tn)比较字符串 s1中的n个字符和字符串s2。函数在s1等于、小于或大于s2 时，分别返回0、小于0或者大于0的值。 • 例如：
串模式匹配
• 无回溯的匹配算法 • 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹 配相当于将子串P后移1位再从头与主串中对应字符进行比 较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配 的起点的下一个位置，这样，主串中每个字符都要与子串 中的第1个字符对应一次，再向后比较。因此，主串中每个 字符参加比较的次数最多可达n次（n为子串长度），因此 时间复杂度为O(nm)。那么，能否使目标串中每个字符只参 加一次比较呢？也就是说，能否不回溯i指示器？回答是肯 定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时 解决的，所以有的文献也称这种思想的串匹配算法为KMP 算法。
数据结构简答题和论述题

数据结构简答题和论述题

数据结构简答题和论述题1、试描述数据结构和抽象数据类型的概念与程序设计语⾔中数据类型概念的区别。

【解答】数据结构是指相互之间存在⼀定关系的数据元素的集合。

⽽抽象数据类型是指⼀个数据结构以及定义在该结构上的⼀组操作。

程序设计语⾔中的数据类型是⼀个值的集合和定义在这个值集上⼀组操作的总称。

抽象数据类型可以看成是对数据类型的⼀种抽象。

串:是零个或多个字符组成的有限序列。

串是⼀种特殊的线性表，它的每个结点仅由⼀个字符组成。

空串 :长度为零的串，它不包含任何字符。

空⽩串 :仅由⼀个或多个空格组成的串⼦串 :串中任意个连续字符组成的⼦序列称为该串的⼦串。

串变量和串常量通常在程序中使⽤的串可分为：串变量和串常量。

（1）串变量 ：串变量和其它类型的变量⼀样，其取值是可以改变的。

（2）串常量 ：串常量和整常数、实常数⼀样，在程序中只能被引⽤但不能改变其值。

即只能读不能写。

（1）树形图表⽰： 树形图表⽰是树结构的主要表⽰⽅法。

（2）树的其他表⽰法① 嵌套集合表⽰法：是⽤集合的包含关系来描述树结构。

② 凹⼊表表⽰法：类似于书的⽬录③ ⼴义表表⽰法：⽤⼴义表的形式表⽰的。

上图 (a)树的⼴义表表⽰法如下：（A（B（E，F（I，J））， C，D（G，H）））1．中序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)访问根结点； (3)遍历右⼦树。

2．先序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1) 访问根结点； (2) 遍历左⼦树； (3) 遍历右⼦树。

3．后序遍历得递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)遍历右⼦树； (3)访问根结点。

2、链表具有的特点是B 插⼊、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正⽐顺序队列（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2） 顺序队列的表⽰①和顺序表⼀样顺序队列⽤⼀个向量空间存放当前队列中的元素。

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

【二】、什么是抽象数据类型

【⼆】、什么是抽象数据类型【⼆】、什么是抽象数据类型在上⼀篇【】中我详细介绍了我对数据结构的理解，其实描述数据结构，有⼀个很好的⽅法叫抽象数据类型。

下⾯我会详细介绍抽象数据类型。

抽象数据类型英⽂名叫(Abstract Data Type)，这⾥有两个关键词，⼀个叫“数据类型”，⼀个叫“抽象”，它们分别是什么意思呢？⾸先说什么是数据类型呢？数据类型，它包含了两个东西，⼀个是“数据对象集”，就是我们说的“是什么东西”，第⼆个是“数据集合相关联的操作集”，就上我在上⼀篇中说的，我们不能单纯讲怎么去处理图书，我们是要对这些图书进⾏操作的，这两件事情：图书的摆放，对图书的操作，是紧密结合在⼀起的。

这两个东西在C语⾔⾥是独⽴处理的，但是在⼀些⾯向对象的语⾔⾥边，⽐如C++、Java，你就会发现，它们很好的为数据类型专门设计了⼀种机制，就是⼀个“类”，把这个数据集跟它相关的操作集封装在⼀个类⾥⾯。

那再说什么是抽象呢？总体来说，我们只描述数据对象集和相关的操作集"是什么"，我们不关⼼“它是怎么做到的”这个问题。

可能到现在⼀些没有基础的朋友看起来还是很抽象，没关系，我再举个例⼦，可能帮助你更好的理解抽象数据类型到底是个什么东西，这个例⼦是关于“矩阵”的抽象数据类型的定义。

⾸先我们要给这个抽象数据类型⼀个名称叫“矩阵”，然后我们要描述⼀下它的数据对象集，⼀个N M的矩阵，是由N M个矩阵的元素构成的，我们把这个元素描述成⼀个三元组a,i,j，其中a是这个矩阵元素的值，同时我们还需要知道这个矩阵元素在矩阵⾥⾯所处的位置，就是它的⾏号i和列号j，就这样描述了⼀个数据的对象集，相关联的操作集有很多很多(如下图)我们来看⼀下，为什么这个就叫做“抽象”的表⽰呢？⾸先我们来看，在描述数据对象集的时候，说a是矩阵元素的值，那这个值是float？还是double？还是int？我们在这个抽象数据类型中描述是不关⼼的，相应地，当需要对它的元素值进⾏操作的时候，我们返回的也是ElementType,是⼀个通⽤的元素类型，我在实现这个矩阵相关的所有函数的时候，我在头上写⼀个define,你需要什么，我就把它define(定义)成什么样⼦，这样的话，你实现的这些函数是跟“你那个矩阵元素到底是哪种类型”是没有关系的，哪种类型都是可以运算的。

串PPT课件专题培训

串PPT课件专题培训


例：
1.空串和空格串有无区别？ 有区别。空串(Null String)是指长度为零旳串；而空 格串(Blank String)是指包括一种或多种空格旳字符串 .
2.既有下列4个字符串：
a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’
问：① 他们各自旳长度？ ② b是哪个串旳子串？它在主串中旳位置是多少？
T.length =i;
}
return OK;
}//StrAssign
三、链式存储：用链表存储串值，易插入和删除。
Typedef struct { char *ch; // 若非空串,按串长分配空间; 不然 ch = NULL int length; //串长度
}HString
例：用“堆”实现串插入操作(教材P75)
Status StrInsert ( HString &S, int pos, HString T ){
❖ 堆分配存储表达
——用一组地址连续旳存储单元存储串值旳字符 序列,但存储空间是在程序执行过程中动态分配 而得。
链式 存储
❖ 串旳块链存储表达
——链式方式存储
一、定长顺序存储
用一组连续旳存储单元来存储串，直接使用定长旳字符 数组来定义，数组旳上界预先给出，故称为静态存储分 配。
例如： #define MAXSTRLEN 255 //顾客可用旳最大串长 typedef unsigned char SString[MAXSTRLEN＋1 ]; SString S; //S是一种可容纳255个字符旳顺序串。
Status Concat(SString &T, SString S1, SString S2,) { // 用T返回由S1和S2联接而成旳新串。若未截断, 则返回TRUE，不然FALSE。
串

串

初始条件：串S和T存在。 操作结果:若S>T，则返回值>0；若S = T，则返回值=0；若S<T，则返回值<0.
ClearString (&S)
初始条件：串S存在。 操作结果：将S清为空串。
Concat (&T , S1, S2)
初始条件：串S1和S2存在。 操作结果：用T返回由S1和S2联接而成的新串。
Status ClearString(HString &S) { //将S清为空串. if(S.ch) { free(S.ch); S.ch=NULL;} S.length=0; return OK; }// ClearString
Status Concat(HString &T, HString S1, HString S2)
int Strlength(HString S) { return S.length; }
int StrCompare(HString S, HString T) { //若S>T，则返回值>0；若S = T，则返回值=0；若S<T，则返回值<0 for( i=0; i< S.length && i< T.length; ++i ) if(S.ch[i]!= T.ch[i]) return S.ch[i]-T.ch[i]; return S.length- T.length; }
• 二、串的抽象数据类型的定义
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)
抽象数据类型

抽象数据类型

抽象数据类型1.数据类型数据类型（data type）是⼀个值的集合和定义在这个值集上的⼀组操作的总称。

原⼦类型:如语⾔的整形、字符型等标准类型及指针等简单的导出类型和空类型。

结构类型：其值是由若⼲成分按某种结构组成的，因此是可以分解的，并且它的成分可以是⾮结构的，也可以是结构的，通常是由标准类型派⽣的。

例如，C/C++中的数组、结构等类型。

2.抽象数据类型（abstract data type, ADT）抽象数据类型是指⼀个数学模型以及定义在该模型上的⼀组操作。

它通常是指对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据的操作的集合。

“抽象”的意义在于数据类型的数学抽象特性。

3.抽象数据类型的描述⽅法（D，S，P）D是数据对象，S是D上的关系集，P是对D的基本操作集。

4.抽象数据类型⼀般可以由数据对象、数据关系及基本操作来定义。

ADT 抽象数据类型{数据对象（数据对象的定义）数据关系（数据关系的定义）基本操作（基本操作的定义）}ADT 抽象数据类型名其中，数据对象和数据关系的定义⽤集合描述，基本操作的定义格式为返回类型基本操作名（参数表）5.对于每个操作，包含下列5个基本要素：输⼊前置条件过程输出后置条件6.基本操作有两种参数：赋值参数只为操作提供输出值；引⽤参数以&开头，除可提供输出值外，还将返回操作结果。

7.⾯向对象的程序设计（OPP）⽅法。

在⾯向对象程序设计语⾔中，借助对象描述抽象数据类型，存储结构的说明和操作函数的说明被封装在⼀个整体结构中，这个整体结构称为类（class），属于某个类的具体变量称为对象（object）。

8.ADT和类的概念实际上反映了程序或软件设计的两层抽象：ADT相当于是在概念层（抽象层）上描述问题，⽽类相当于是在实现层上描述问题。

抽象数据类型与C++中类的对应关系如下：抽象数据类型——类数据对象——数据成员（属性）基本操作——成员函数（⽅法）。

数据结构知识点总结归纳整理

数据结构知识点总结归纳整理

第1章绪论1.1 数据结构的基本概念数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。

例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型是一个值的集合和定义在此集合上一组操作的总称。

•原子类型：其值不可再分的数据类型•结构类型：其值可以再分解为若干成分（分量）的数据类型•抽象数据类型：抽象数据组织和与之相关的操作抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。

抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。

#关键词：数据，数据元素，数据对象，数据类型，数据结构数据结构的三要素：1.逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。

分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。

2.存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。

3.数据的运算：包括运算的定义和实现。

运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

1.2 算法和算法评价算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。

一个算法有零个或多个的输入，有一个或多个的输出。

时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。

一般指最坏情况下的时间复杂度。

空间复杂度定义为该算法所耗费的存储空间。

算法原地工作是指算法所需辅助空间是常量，即O(1)。

第2章线性表2.1 线性表的定义和基本操作线性表是具有相同数据类型的n个数据元素的有限序列。

第4章 串

第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。 特别地，空串是任意串的子串，任意串是其自身的 子串。 通常在程序中使用的串可分为两种：串变量和串常 量。
04 串d

04 串d


子串： 子串：串中任意个连续的字符组成的子序列称 为该串的子串。 为该串的子串。 主串：包含子串的串相应地称为主串。 主串：包含子串的串相应地称为主串。 空串： 时的串为空串。 空串： n=0时的串为空串。 时的串为空串 空格串： 空格串：由一个或多个称为空格的特殊字符组 成的串。 成的串。 通常将字符在串中的序号称为该字符在串中的 通常将字符在串中的序号称为该字符在串中的 位置。 位置。
ADT LinearList{ 数据元素: 为某一数据对象} 数据元素 D={ai| ai∈D0, i=1, 2, …,n,n≥0,D0为某一数据对象 关系: S={<ai, ai+1> | ai, ai+1∈D0，i=1, 2, …, n-1} 关系 基本操作: 基本操作 InitList(L): 初始化 DestroyList(L): 销毁 ClearList(L): 置空表 EmptyList(L): 判断表是否为空 ListLength(L): 求表长 Locate(L, e): 查找 GetData(L, i): 求第 个结点 求第i个结点 InsList(L, i, e): 插入 DelList(L, i, &e): 删除 } ADT LinearList
9
第四章 串
串的定义 抽象数据类型串的实现
定长顺序串 堆串 块链串
模式匹配 串的应用举例： 串的应用举例：文本编辑 要点小结 参考书目及网络资源 讨论时间
School of Computer Sci. & Eng.,Wenzhou University
10
定长顺序串
定长顺序串是将串设计成一种结构类型 串的 定长顺序串是将串设计成一种结构类型,串的 是将串设计成一种结构类型 存储分配是在编译时完成的。 存储分配是在编译时完成的。 定长顺序串类型定义 #define MAXLEN 40 typedef struct {//串结构定义 串结构定义 char ch[MAXLEN]; int len; } SString;

数据结构_字符串操作原理


4.1 串类型的定义

一、串的基本概念

串(String)的定义
s＝“a1a2…an”

其中：
s为串的名字， 串的值
ai(1≤i≤n)一般是字母、数学、标点符号等可屏幕显
示的字符。
串的长度n。
4.1 串类型的定义

字符串与一般的线性表的区别：


串的数据元素约束为字符集；
串的基本操作通常针对串的整体或串的一个部分进行。


3.串的某些操作（如：串的连接、串的替换等）受到限制。
4.2.2 堆分配存储表示

特点：

仍用一组连续的存储单元来存放串，但存储空间是在程序 执行过程中动态分配而得。 利用malloc函数合理预设串长空间。
typedef struct{ char *ch; int length; }HString;

子串和主串

eg:
A＝“This is a string” B＝“is”

特别地：

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

串的相等
二、串的抽象数据类型定义
ADT String{
数据对象：D＝{ai|ai∈CharacterSet,i＝1,2,…,n;n≥0}
数据关系：S＝{< ai-1 , ai >| ai-1， ai ∈D, i ＝ 2,…,n} 基本操作： StrAssign(&T,chars) StrLength(S) SubString(&Sub,S,pos,len) StrCopy(&T,S) Index(S,T,pos)

串的结束标志的设置

抽象数据类型名词解释

抽象数据类型名词解释抽象数据类型抽象数据类型(abstract data type)抽象数据类型是对具体数据类型的扩充，它提供了多种方式来组织数据，如二进制、结构化文本等。

在许多情况下，数据类型并不能全面反映系统的需求，于是出现了抽象数据类型。

抽象数据类型描述一个计算机系统可以使用哪些数据类型，其中每种数据类型定义了一组操作。

从设计角度看，一个抽象数据类型是特定于某个具体硬件和软件平台的，但是这个类型被应用到任何一个硬件和软件平台上都将具有相同的含义。

抽象数据类型分类根据实现该抽象数据类型所用数据元素的类型，可以将抽象数据类型分为：基本数据类型：具有通用性的数据类型，其定义简单。

抽象数据类型中的所有操作，都可以使用基本数据类型中的成员来实现。

具体数据类型：不具有通用性，其定义较复杂。

从设计角度看，由于具体数据类型中的成员可能要受到硬件的制约，使得设计人员不得不考虑到硬件的具体类型。

抽象数据类型的主要特点： 1、在抽象数据类型定义中，不仅包括对象的引用和数据元素的数据值，还定义了操作和函数调用关系。

2、抽象数据类型中，常量成员只能按照预先确定的格式传送，字符串长度必须遵循预先确定的长度。

3、抽象数据类型的数据元素是按照不同规则组合在一起的。

4、抽象数据类型允许用户建立新的数据类型。

2、抽象数据类型的内部表示法：用对象的名称作为指针，与数据元素的数据类型相联系的一种表示方法。

有两种形式，一种是与其它数据类型相联系的形式；另一种是与标识符相联系的形式。

3、接口方法：指用来说明一个类能够用于实现另一个类的功能的类型信息。

接口方法的定义很简单，它总是指向对象的内部或者是指向一个成员函数。

4、基类：也叫做父类或者是上级类。

基类实现的是一个类的数据操作。

基类中定义的每个数据操作都要有目的地实现。

5、派生类：也叫子类或者是下级类。

派生类实现的是一个类的功能。

6、虚基类：也叫做基类或者是自身。

虚基类就是一个类，其中定义的每个数据操作都无需实现。

数据结构之串类型

数据结构之串类型 串的基本概念： 串(字符串)：是零个或多个字符组成的有限序列。

记作： S=“a1a2a3…”，其中S是串名，ai(1≦i≦n)是单个，可以是字母、数字或其它字符。

串值：双引号括起来的字符序列是串值。

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

空串(空的字符串)：长度为零的串称为空串，它不包含任何字符。

空格串(空⽩串)：构成串的所有字符都是空格的串称为空⽩串。

注意：空串和空⽩串的不同，例如“ ”和“”分别表⽰长度为1的空⽩串和长度为0的空串。

⼦串(substring)：串中任意个连续字符组成的⼦序列称为该串的⼦串，包含⼦串的串相应地称为主串。

⼦串的序号：将⼦串在主串中⾸次出现时的该⼦串的⾸字符对应在主串中的序号，称为⼦串在主串中的序号（或位置）。

特别地，空串是任意串的⼦串，任意串是其⾃⾝的⼦串。

串相等：如果两个串的串值相等(相同)，称这两个串相等。

换⾔之，只有当两个串的长度相等，且各个对应位置的字符都相同时才相等。

通常在程序中使⽤的串可分为两种：串变量和串常量。

串的抽象数据类型定义： ADT String{ 数据对象：D = { ai|ai∈CharacterSet, i=1,2,…,n, n ≥0 } 数据关系：R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n } 基本操作： StrAssign(t , chars) 初始条件： chars是⼀个字符串常量。

操作结果：⽣成⼀个值为chars的串t 。

StrConcat(s, t) 初始条件：串s, t 已存在。

操作结果：将串t联结到串s后形成新串存放到s中。

StrLength(t) 初始条件：字符串t已存在。

操作结果：返回串t中的元素个数，称为串长。

SubString (s, pos, len, sub) 初始条件：串s, 已存在, 1≦pos≦StrLength(s)且 0≦len≦StrLength(s) –pos+1。

数据结构 串基本操作代码

数据结构串基本操作代码简介本文档介绍了数据结构中串的基本操作代码,包括串的定义、串的赋值、串的比较、串的连接、串的替换等。

1.串的定义串是由零个或多个字符组成的有限序列,是字符串的抽象数据类型。

常用的串类型包括顺序串和链式串。

1.1 顺序串顺序串是使用数组来存储字符序列的数据结构。

其定义如下：```cdefine MaXSiZe 100 // 串的最大长度typedef struct {char data[MaXSiZe]； // 存储串的字符数组int length； // 串的长度} SqString；```1.2 链式串链式串是使用链表来存储字符序列的数据结构。

其定义如下：```ctypedef struct LNode {char data； // 存储串的字符struct LNode next； // 指向下一个节点的指针} LNode, LinkString；```2.串的基本操作2.1 串的赋值将一个字符串赋值给一个串,可以使用字符串赋值函数`strcpy`或者循环遍历字符串赋值。

2.1.1 使用strcpy函数赋值```cinclude <string.h>void Strassign(SqString s, char str) {strcpy(s->data, str)；s->length = strlen(str)；}```2.1.2 使用循环遍历赋值```cvoid Strassign(SqString s, char str) {int i；for (i = 0； str[i] ！= '\\0'； i++) {s->data[i] = str[i]；}s->length = i；s->data[i] = '\\0'；}```2.2 串的比较比较两个串是否相等,可以使用字符串比较函数`strcmp`或者循环遍历比较。

4-2-数据结构——从概念到C++实现(第3版)-王红梅-清华大学出版社

第四章 字符v 串和多维数组
4-2-1 字符串的逻辑结构
讲什么？
字符串的定义
数
据
结
字符串的基本概念
构 （
从
概
念
到
实
字符串的抽象数据类型定义
现 ）
清 华 大 学 出 版 社
串的定义
线性表（表）：具有相同类型的数据元素的有限序列
将元素类型限制为字符
数 据
结
构
（ห้องสมุดไป่ตู้
字符串（串）：零个或多个字符组成的有限序列
2.1 如果S[i] 等于T[j]，继续比较 S 和 T 的下一个字符；
2.2 否则，将 i 和 j 回溯，准备下一趟比较；
3. 如果T中所有字符均比较完，则返回匹配的起始比较下标；否则返回 0；
BF算法——运行实例
例：主串 S = "ababcabcacbab"，模式 T ="abcac"
i ii
S5 = " "
S3 = "ab12 "
S6 = " "
抽象数据类型定义
ADT String
DataModel
串中的数据元素仅由一个字符组成，相邻元素具有前驱和后继关系
Operation StrAssign ：串赋值 StrLength ：求串S的长度 Strcat ：串连接
数
据
结
构
（
从
概
念
到
字符串的基本操作有什么特点？
从 概 念 到
实
2
现 ）
趟 abcac
i=2，j=2失败；
清 华 大
学
i 回溯到 1，j 回溯到 0

特殊线性表——栈队列和串

第 3 章特殊线性表——栈、队列和串3.1 栈3.1.1 栈的逻辑结构1. 栈的定义栈是限定仅在表尾进行插入和删除操作的线性表。

允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。

2. 栈的抽象数据类型定义ADT StackData栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系OperationInitStack输入：无功能：栈的初始化输出：无后置条件：构造一个空栈DestroyStack前置条件：栈已存在输入：无功能：销毁栈输出：无后置条件：释放栈所占用的存储空间Push前置条件：栈已存在输入：元素值x功能：在栈顶插入一个元素x输出：如果插入不成功，抛出异常后置条件：如果插入成功，栈顶增加了一个元素Pop前置条件：栈已存在输入：无功能：删除栈顶元素输出：如果删除成功，返回被删元素值，否则，抛出异常后置条件：如果删除成功，栈顶减少了一个元素GetTop前置条件：栈已存在输入：无功能：读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变 Empty前置条件：栈已存在 输入：无功能：判断栈是否为空输出：如果栈为空，返回1，否则，返回0 后置条件：栈不变 endADT3.1.2 栈的顺序存储结构及实现1. 栈的顺序存储结构——顺序栈栈的顺序存储结构称为顺序栈。

1. 顺序栈的实现const int StackSize=10; //10只是示例性的数据，可以根据实际问题具体定义 template <class T> //定义模板类SeqStack class SeqStack {public:private: };3. 两栈共享空间提出问题：在一个程序中如果需要同时使用具有相同数据类型的两个栈时，如何处理呢？ 解决方案一：为每个栈开辟一个数组空间；解决方案二：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，每个栈从各自的端点向中间延伸，如图3-3所示。

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

StrCopy (&T, S)
(串复制)
初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。
StrEmpty (S)
(判空)
初始条件：串 S 存在。
操作结果：若 S 为空串，则返回 TRUE, 否则返回 FALSE。(为空串)
StrLength (S)
(求长度)
初始条件：串 S 存在。
求得 sub = man SubString( sub, commander , 1, 9) 求得 sub = commander SubString( sub, commander , 9, 1)
求得 sub = r
SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ? 起始位置和子串长度之间存在约束关系 SubString(student, 5, 0) = 长度为 0 的子串为“合法”串
StrInsert (&S, pos, T)
(插入)
初始条件：串 S 和 T 均存在， 1≤pos≤StrLength(S)＋1。 操作结果：在串 S 的第 pos 个字符之前 插入串T。 例如：S = chater ，T = rac ， 则执行 StrInsert(S, 4, T) 之后得到 S = character
操作结果： 用 V 替换主串 S 中出现的所有与 （模式串）T 相等的不重叠的子串。
例如：
假设 S = abcaabcaaabca bca bca bca, T = bca 若 V = x , 则经置换后得到 S = axaxaax
若 V = bc , 则经置换后得到 S = abcabcaabc
StrDelete (&S, pos, len) (删除)
初始条件： 串 S 存在，且 1≤pos≤StrLength(S)-len+1。 操作结果：
从串 S 中删除第 pos 个字符起 长度为len的子串。
对于串的基本操作集可以有不同的定义 方法，在使用高级程序设计语言中的串类 型时，应以该语言的参考手册为准。 在上述抽象数据类型定义的13种操作中， 串赋值 StrAssign、串复制 Strcopy、 串比较 StrCompare、求串长 StrLength、
ClearString (&S)
Index (S, T, pos)
Replace (&S, T, V) StrInsert (&S, pos, T)
StrDelete (&S, pos, len)
} ADT String
StrAssign (&T, chars)
(串赋值)
初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。
Concat (&T, S1, S2) (串联接)
初始条件：串 S1 和 S2 存在。
操作结果： T 为由串 S1 和串 S2 联接 所得的Байду номын сангаас。
例如： Concat( T, man, kind)
求得 T = mankind Concat( T, kind, man) 求得 T = kindman
4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 文本编辑 —串的应用举例
ADT String {
数据对象：
串是有限长的字符序 列，由一对双引号相 括，如: a string
D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 }
数据关系：
R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n }
中的第一个字符在主串中的“位序” 。 假设 S = abcaabcaaabc , T = bca Index(S, T, 1) = 2;
Index(S, T, 3) = 6;
Index(S, T, 8) = 0;
Replace ( S, T, V)
(串置换)
初始条件： 串 S, T 和 V 均已存在， 且 T 是非空串。
基本操作：
StrAssign (&T, chars)
DestroyString(&S)
StrCopy (&T, S)
StrLength(S)
StrEmpty (S) Concat (&T, S1, S2) StrCompare (S, T)
SubString (&Sub, S, pos, len)
操作结果：返回串 S 中字符的个数。
StrCompare (S, T) (串比较)
初始条件：串 S 和 T 都存在。 操作结果：由串 S 小于或等于或大于串 T 分别返回小于或等于或大于 0 的值 。 例如：StrCompare( data , state ) < 0
StrCompare( cat , case ) > 0
Index ( S, T, pos)
(定位函数)
初始条件： 串 S 和 T 存在，且 T 是非空串， 1≤pos≤StrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同的 子串，则返回它在主串 S 中第 pos 个字符之后第一次出现的位置; 否则函数值为0。
“子串在主串中的位置”意指子串
串联接 Concat 以及求子串 SubString 等六种操作构成串类型的最小操作子集。
利用串比较、求串长和求子串等操 作实现定位函数 Index( S, T, pos ) 算法的基本思想为：
StrCompare(SubString(S, i, StrLength(T)), T )
SubString (&Sub, S, pos, len) (求子串)
初始条件：
串 S 存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。 操作结果： 以 Sub 返回串 S 中第 pos 个字符起 长度为 len 的子串。
子串为“串”中的一个字符子序列 例如： SubString( sub, commander , 4, 3)