07.第07节课第4章串

罗泽兵 · 发表于 2024-4-15 09:16:27

好同学们，大家好，今天呢，我们来为大家讲解一下数据结构当中有关串的这样一个知识。在计算机上呢，非数值处理的对象呢，大部分是字符串数据。字符串呢，一般简称为串。串是一种特殊的线性表，其特殊性呢，体现在数据元素是一个字符，也就是说。串是一种内容受限的线性表。由于现在呢？

使用的计算机呢？硬件结构是面向数值计算和需要而设计的。在处理字符串数据的时候呢，比处理整数和浮点数呢要复杂的多，而且在不同类型的应用中呢，所处理的字符串呢？具有不同的特点，要实现字符串的有效处理就必须呢，根据具体情况采用合适的存储结构。那么，我们呢？首先来给大家看一下串的定义，存储结构和基本操作。我们重点呢，来讲一下串的模式，

匹配算法。串可以看作是一种线性表。它的这样一个去操作呢，通常是按成组的元素来进行的。数组可以认为是线性表了，在维数上的一种扩展。我们的串呢，它和数组呢，依然属于线性结构，但是存储结构方面呢，线比较线性表呢，比较复杂。我们首先来看一下串的定义。串或者简称字符串是由零个或多个字符组成的有限序列，那么我们记住了s等于。

双引号a0a1一直到AI一直到ai- 1。双引号n呢大于等于零。其中呢？我们的串s呢，是串的名称，用双引号括起来的呢，它是串的值。AI可以是字母，数字或其他字符串中的字符的数目n呢？称为串的长度。零个字符的这样一个串呢，称为空串，其长度为零。串中任意连续的字符呢？组成的子序列称为该串的子串。

包含子串的串呢，相应的称为主串。通常称字符呢，在序列中的序号为该字符，在串中的位置。子串在主串中的位置呢，则以子串的第一个字符呢，在主串中的位置来表示。那么，我们来看一下。我们的串呢有，比如说a stream。a+b。还有我们的空串。那么这些呢，

都是我们的串。那么，这是我们串的这样一个部分，那么我们的串呢？称如怎么样？两个串是相等的呢，当且仅当。这两个串它的值相等，也就是说。只有当两个串的长度相等，并且各个对应位置的字符了都相等时了，这两个串才相等。刚才我们看的这些几个几个串，比如说a stream a+b空串。这些呢，

彼此呢，都不相等，我们说两个串相等呢，只有当它们的长度相等。并且在各个对应位置的字符相等呢，才说这两个串是相等的，那么我们这些串呢，它是不相等的。我们来看一下。在各种应用中呢，空格常常是串的字符集中的一个元素，因而呢，可以出现在其他字符中间。那么，这是我们空格的这样一个部分，

一个或多个空格组成的串呢？称为空格串。那么，大家要注意了，我们的空格串，比如说。我们这样一个空格串，与我们的空这样的一个空格串，就是一个或多个空格组成的空格串呢，称为空空。这个组成的串呢，称为空格串，但是大家要注意这个时候呢，它不是空转它的长度呢是。串中空格字符的个数。

那么大家注意，我们的空格串呢？那么它不是它不是它不是空串空格串呢？不是空串。那么，接下来我们看一下。串着。基本操作。串的逻辑结构和线性表呢，比较相似，区别仅在于串的数据对象呢，约束为字符集。然而呢，串的基本操作和线性表呢，有比较大的区别，

在线性表的基本操作呢？大多以单个元素为操作对象，比如说在线性表中查找某个元素，取求某个元素。在某个位置呢，插入一个元素或删除一个元素，而在串的基本操作中。通常以串的整体作为操作对象，比如说在串中查找某个子串，求取一个子串，在串中的某个位置插入一个子串，以及呢，删除一个子串的。我们串了它有一些基本操作，比如说。

string assign destroyed string string copy dream lenses to compare.contact cut cut string empty.以及呢，substring clear stream index replace string insert string delete，那么我们来看一下这些部分。string assign.这样一个操作呢，它的初始条件呢，是我们的恰似它的参数，恰似。是字符串常量。它的结果呢，是把恰似赋值为t的值。比如说。生成一个期值呢等于。

恰似的串。t那么就是说这里呢，就是生成一个期值呢，等于char值的串t。还有struc copy，struc copy呢？它的这样一个操作条件呢？是串s存在。它的操作条件呢？它的操作结果呢？是由创s复制的。串t。还有我们的destroy。所以这个呢，它的初始条件呢，

是我们的串s存在操作结果呢。是创s被销毁。还有smt。它的初始条件是串s存在操作，结果呢，是串s为空，串则返回true。否则呢，返回。我们的这样一个两个双引号呢，直接两个连起来的双引号呢，表示空串空串的长度呢为零。我们双引号中呢，有这样一个空的地方呢，表示空格它是有长度的，

这样一个部分。还有spring comp are ST初始条件呢，是串s和t存在它的，其它的结果呢？是进行比较，如果s大于t则返回。值大于零，如果s=t，则返回值呢？等于零，如果s小于t，那么则返回值呢？小于零。比如说我们来看一下这样一个例子。string compare data state。

比较state和state这两个字符串，那么比如说前一个字符串呢？那么小于后面一个字符串？那么这样呢就？s小于t，那么返回值零。还有我们的后面一个比较的这样一个部分，那么比较的这样一个运用的。实训的这样一个内容。那么我们还有呢？string lengths它的初始条件呢，是创s存在操作结果呢。是返回s的元素个数称为串的长度。初始条件还有我们的contact contact。它的初始条件呢，

是串s和一和s2存在。它的操作结果呢，是用t返回由s1和s2连接形成的新串。比如说。time cut.t mankind那么得到的这样一个结果呢？是t=mankind。还有substrate。它这样的结果，初始条件呢，是串s存在，且零小于pose，小于ss，小于s的长度。且零小于任。

小于strengthen CS点，pose它的操作结果呢是？用sub返回s的d或是个字符。起长度为嫩的子串。那么我们看一下子串中为串的第一个字符的子序列。比如说substrate，sub commander四三，那就是呢。返回串SD post的第四个字符起长度为三的，这样一个字符串那么就是我们的慢这样一个部分。还有string sub commander一九那么得到的这样一个结果呢？sub=commander还有substring=sub commander九一那么得到的结果呢？是r。那么我们看一下。起始位置呢？

和字串长度之间存在的约束关系。比如说。长度为零的子串呢？我们是合法串。还没有我们的index ST pose。初始条件呢，是s和t存在。选t呢是非空串零小于pose小于stream lengths- 1操作，结果呢是若主串s中。存在和串t值相同的子串则返回它。在主串中，第post字符后第一次出现的位置，否则函数值为零。子串在主串中的位置呢？指子串中的第一个字符呢？

在主串中的位序，比如说s等于这样一个字符，串t=bac。那么，index SP 1那么就等于2 index SP 3那么就等于六那么这样一个？畏惧的这样一个部分。还有我们的index s七八，那么等于零。以及我们的replace，那么这个操作初始条件呢？是串ST和微居里存在。且t呢，是非空串操作结果呢，是用v替换主串s中出现的所有语。其相等的不重叠的子串，

那么它的这样一个操作方，它它的这样一个。它的这样一个。功功能呢，就是用v替换主串s中出现的，与所有t相等的不重叠的子串。比如说。设s。等于后面的这样一个字，符串t=BC a，如果我们的v=x，那么经过置换后呢？那s等于后面的这样一个字，符串。那么，

如v=BC，那么得到经置换后呢？等到s呢？等于这样一个字，符串。好，我们的string string sert，它的初始条件呢？是串s和t存在，且一小于pose。小于stringless操作结果呢，是在串s的t post字符之前插入串。串t。比如说s等于后面的这样一个部分t=rac，那么执行string set之后呢？

得到了s等于这样一个character，那么这样一个部分。还有我们的string delete。它的初始条件呢，是创s存在且一小于pose，小于strengthens s-lens。操作结果呢，是从串s中删除depos的字符起，长度为嫩的字符。子串string clear stream，它的初始条件呢，是串s存在操作结果呢，是将s记为空串。那么，对于串的基本操作集呢？

可以有不同的定义方法在使用高级程序设计语言中的串类型时呢？应以该语言的参考手册为准，比如说C语言库案中呢？启动下列的处理。串处理函数，比如说gets RAY puts struct three copy。three compare three length就是我们输入串输出串串连接函数串复制函数串比较函数呢，也求串乘函数，那么在上述类型呢？定义的13种串抄中，中串赋值串复制串比较求串长。串连接以及求子串等六种操作呢，构成串类型的最小操作子集，比如说这些操作呢，不可能利用其他串操作来实现。

那么，其他串操作呢？可以在这个最小串操作子集上存在进行实现。串的逻辑结构和线性表呢，比较相似，区别仅在于串的数据对象约束为字符集串的基本操作和线性表呢，有很大差别。在线性表的基本操作中，大多以单个元素作为操作对象，在串的基本操作中呢，通常以串的整体作为操作对象。接下来我们看一下串的表示和实现。在程序设计语言中，串只是作为输入或输出的常量存在，只需比存储尺寸的。

只需存储尺寸的串值，那么比如说我们的字符序列，但在多数非数字处理的程序中呢，串也以变量的形式出现。那么，接下来我们看一下串的定场存储表示以及串的堆分配存储表示和串的块列存储表示。那么首先呢，我们来看一下串的定长存储存顺序，存储表示，那么我们用这样一个描述呢，就是井号define max。s string string lens二五五hyper defy on signed char string max。认识。max string length+1，那么用我们的这样一个存放呢？

串的这样一个长度。那么，如果用C语言的串类型描述算法呢？可以用一组连续的存储单元存放串的字符序列。并以零反斜杠零作为结束标志。比如说串的说明是。character street 10那么字符串呢？最大串长为九。串的定长存储操作的特点呢？串的实际长度呢？可以在这个。与这个定义长度的范围的随意设定。超过定义长度的串呢，则被舍去称之为截断。按这种串表示方法实现的串的运算式呢，

其基本操作呢，为字符串的这样一个复制。接下来我们看一下串的连接操作。contact.void CON cut那么chars 1数组，chars 2数组，chart数组in tig in的kg k=0。while seg不等于反斜杠零。TK加加等于s1g加加复制s1。g=0。while.s2g不等于零。TK加加等于s2g加加，那么接着呢？复制我们的as 2。

那么最后呢，在我们的数组七的最后面呢，加上一个反斜杠零那么去作为结作为进行。表示结束的这样一个部分，那么我们来看一下它的这样一个连接操作，那么这个连接操作呢？那么CON cult这样一个连接操作呢，是由我们的。后最后一个数组七这样一个数组呢，返回由我们前面。串1s一和串s2。连接而行的这样一个星串，那么我们首先呢，是j=0 k=0，然后呢，

当s1它的这样一个数组数据元素呢？数组元素呢，不为这样一个反斜杠零的时候呢，那么我们的s。1g加加。那么就赋给我们的TK加加，那么赋值s1，那么再让j=0当s2j，不不不，是我们这样一个反斜杠零的，这样一个字符的时候呢？那么，让s2g加加赋给我们的TK加加，那么接着呢？复制我们的s2，

最后呢？写上一个。返七二零这样一个字符，那么这表示结束，那么这样一个部分。那么，这是我们的串的连接操作，它的这样一个方式，那么接下来我们看一下定场分配，那么在调用程序。what is the name?chars 1。数组等于China恰s2，数组等于北京。看s1s2t1，

那么就是用t1呢？返回由s1和s2。连接而行的这样一个星串，那么最后呢？输出我们的t1，然后呢？输出一个换行符，那么程序结束。呃，接下来我们再看一下串的堆分配存储表示。如果完全用伪代码了，伪代码我我如我们看一下这个串的定义，看一下这个定义type defined struct恰新ch。intern ceh street，那么这是我们定义的这样一个结构体，

如果直接用C语言来描述算法，可以通过函数new和delete为用户进行串值空间的动态管理。每一个新产生的串呢，分配一个存储区。称串值共享的存储区为堆。这里串操作实现的常用思路呢，是先为新生成的串分配一个存储空间，然后进行串词的复制。那么，我们来看一下串的堆分配存储表是实现由我们的CON cut操作和我们的substring操作。那么，我们来看一下。we的can cut下新s一下，新s二下，新加一个符号tint I=0 j=0。

七等于零七二。strings s1，加strings s2，加一，那么就是为c呢分配存储空间，那么它的长度呢是s1的长度和s2的长度呢，那么再加上一。while.ti=SEI，不等于。反斜杠零那么a加加。while.ci.等于。s2g不等于反信号零。

那么，加加I，加加d，加加。嗯。那么，这是我们的。连接的这样一个操作，那么这里呢？while.ti=s 1I，那么就是将s1I的这样一个值呢？赋给ti，如果它不等于零的话，那么接下来I加加进行下一个。

数据元素的这样一个复制。复值元素的这样一个赋值，那么接下来呢？是我们的y ti=s 2g不等于零，那么接下来呢？如果。s2g呢，赋给我们的it I那么它不等于我们的反七杠零的话，那么接下来呢，再进行I加加和g加加进行我们下一个元素的赋值，那么这是我们那么这样一个操作的部分。第二种程序呢，无需先无需预先申请空间。what May.下星s 1=China下星s2等于北京下星期一。

comcast.s1，s2，p1。最后呢，进行输出，看这样一个输出的部分，然后呢，再进行换行。那么，这里呢，就是将我们的。用t1呢返回。s1和s2呢连接形成了这样一个新串。

		自动登录	找回密码
密码			立即注册