(C语言详细版)第四章串要点.ppt

知识点：串的定义、表示与实现，定位函数 说明：KMP算法略去不讲 第四章 串 本章学习导读 在计算机的各方面应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。 字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作 第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 作业 4.1 串类型的定义 串 C中的字符串：一对双引号括起的字符序列，如“abcd ef” 一般地，串是由零个或多个字符组成的有限序列,一般记作S=a1a2a3…an 其中S 是串名，单引号括起来的字符序列是串值；ai(1≤i≤n)可以是字母、数字或其它字符； 一些概念：串的长度、空串、子串、主串、字符/子串在串/主串中的位置 串中所包含的字符个数称为该串的长度。 长度为零的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 空串(φ) vs 空白串 注意：空串和空白串的不同，例如 和分别表示长度为1的空白串和长度为0的空串。 称两个串是相等的，当且仅当这两个串的值相等。 4.1 串类型的定义 串中任意个连续字符组成的子序列称为该串的子串 包含子串的串相应地称为主串 通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。 例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子串。 通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。 4.1 串类型的定义 通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。 但有的语言允许对串常量命名，以使程序易读、易写。如C++中，可定义 const char path[]=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。 串是特殊的线性表 1)元素类型为字符； 2)操作对象：个体(字符)与整体(子串) 4.1 串类型的定义-ADT String ADT String 串的整体操作 赋值 StrAssign(S, “Data Structure”) 复制 StrCopy(T, S) // T=S, T为“Data Structure” 比较 StrCompare(S, T) 连接 Concat(T, “Data”, “Structure”) //T为“DataStructure” 取子串 SubString(sub, S, 2, 5) // sub为“ata S” 子串在主串中的定位 Index(S, “a”, 3) // 4 子串置换 Replace(S, “a”, “b”) // S为“Dbtb Structure” 子串插入 StrInsert(S, 3, “aha”) // “Daahata Structure” 子串删除 StrDelete(S, 3, 5) // “Daructure” 4.1 串类型的定义-操作间的关系 串的基本操作(串的最小操作子集) 赋值操作 StrAssign(T, chars) 比较函数 StrCompare(T, S) 求串长函数 StrLength(S) 联接函数 Concat(T, S1, S2) 求子串函数 SubString(Sub, S, pos, len) 其他操作(除串清除ClearString和串销毁DestroyString外)均可在此最小操作集上实现。 4.1 串类型的定义-操作间的关系 定位函数 Index(S, T, pos) 利用求串长函数、求子串函数和比较函数。 参数：S主串, T子串, pos查找的起始位置 返回值：T在S中第pos个字符后第一次出现的位置 步骤： 1) pos的合法性判断：if ( pos=0