数据结构(第二版) 郑泳 方风波 第四章 串新.pptVIP

第四章 串 知识教学目标 串的基本概念及串运算函数 串的顺序存储和链式存储 字串定位运算的实现 能力培养目标 串的有关概念和操作 常见C语言串的运算函数 串的存储结构 子串定位运算 4.1 串及其运算 字符串（string）简称串，是一种特殊的线性表，其特殊性主要在于该线性表中的每个结点都是一个字符，故可将字符串定义为由零个或多个字符组成的一个有限序列，一般记为： s =“a1a2a3…an” （n≥0） 其中，s为串的名称；用双引号扩起来的字符序列a1a2a3…an是串的值，但引号本身不属于串的内容，它的作用是避免串与常数或标识符相混淆；ai（1 ≤ i ≤ n）是任意一个字符，称为串的元素，是构成串的基本单位，i为它在整个串中的序号。 4.1.2 串的基本运算 有关串的基本运算主要有： 1) 求串的长度len（s）：返回串s的长度，即串s中所包含的字符个数。 2) 串赋值assign(s,t)：将串t的值赋给串s。 3) 串相等判断equal(s,t)：若串s和串t相等，则函数返回true，否则返回false。 4) 串连接concat(s,t)：串s和串t连接成一个新串，并赋值给串s。 5) 求子串sub(s,start,len,t):当s存在，0≤start≤len(s)，0≤len≤len(s)－start，子串t的值为从串s中第start个字符起，长度为len的字符序列。 6) 子串定位index(s,t)：若主串s中存在和t相等的子串，则返回它在主串s中第一次出现的位置，否则返回0。 7) 置换replace(s,t,v)：用串v置换串s中出现的所有与串t相同的不重叠子串。 8) 子串的插入insert(s,i,t)：当串s和t存在，1≤i≤len(s)+1时，在串s中第i个字符前插入串t。 9) 子串的删除delete(s,i,j)：当串s存在，1≤i≤len(s)－j+1时，从串s中删除第i个字符起长度为j的子串。 4.2 串的存储结构 由于串是元素为字符的特殊线性表，因此，其存储结构与线性表的存储结构类似，也可以分别采用顺序存储结构和链式存储结构。但因为字符的特殊性和串经常被作为一个整体来处理的特点，所以串在存储时还有一些特殊技巧。 4.2.1 串的顺序存储 1. 非紧缩格式 在这种格式下，由于一个存储单元仅仅存放一个字符，因而比较浪费存储空间，但它简化了对串的运算。 2. 紧缩格式 为了节省存储空间，也可以用紧缩格式来存储串，即在一个存储单元中存放多个字符，如图4.2所示，在一个存储单元中存放4个字符。 3. 单字节存储方式 有的计算机是以字节进行编址的，其存取的单位是字节。而一个字符正好占一个字节，这就自然形成了每个存储单元存放一个字符的分配方式。 4.2.2 串的链式存储 1．数据域为单个字符 2．结点的大小为K(K1) 其类型定义如下： #define NodeSize 4 //结点大小，由用户指定，这里为4 typedef struct node { char data[NodeSize]; //结点数据域为数组，存放NodeSize个字符 struct node * next; } LinkStrNode; 4.3 串运算的实现 顺序存储结构的串的数据类型可定义为： ＃define MaxSize 100 //假定串的最大容量为100 struct string { char ch[MaxSize]; //存放串值的一维数组 int curlen; //当前串的长度 }SeqString; 串的基本运算的算法如下： 【算法4.1】 串的赋值。 void assign(SeqString *s,SeqString *t) { //将串t的字符逐个赋给串s。 for (int j=0;jt-curlen;j++) { s-ch[j]=t-ch[j]; } s-curlen=t-curlen; } 【算法4.2】 求串的长度。 所谓求串的长度，就是求出串中包括字符的个数。 int len（SeqString *s） { return s-curlen; } 【算法4.3】 串相等判断。 要判断两个串是否相等，首先要看两个串的长度是否相等，若长度相等，再看对应位置上的字符是否相等。 int equal(SeqString *s,SeqString *t) { int i; if ( s-curlen != t-curlrn ) return (0); for (i=0;is-curlen;i++) if ( s-ch[i] != t-ch[i] ) retur