[初三政史地]04串.pptVIP

第4章 串 * * 4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例 4.1 串的类型定义 串(String)：零个或多个字符组成的有限序列，元素类型受限的线性表。 一般记作S=“a1a2a3…an”。 一、定义 串长：串中所包含的字符个数。 空串(Empty String)：长度为零，不含任何字符。 空白串(Blank String)：由一个或多个空格组成的串。 子串：串中任意个连续字符组成的子序列。 主串：包含子串的串。 　空串是任何串的子串，任何串是其自身的子串 　串中某字符在串中出现时的序号（从1开始）称为该字符在串中的位置；子串在主串中第一次出现时，子串的第一个字符在主串中的序号，称为该子串在主串中的位置。 例：A=“This is a string” B=“is” 如果两个串的长度相同，并且各个对应位置上的字符也相同，则称这两个串相等。 串常量：只能引用不能改值，一般用直接量来表示。 串变量：值可以改变，必须用名字来识别。 注：C/C++并没有串变量类型，用字符数组或字符指针表示： char name[]=”John”,*p=”Tom”; 数组名是常指针，初始化后不能赋值，name=“Smith”;错。 1）赋值 StrAssign(T, chars)：将串chars的值传给串T。 StrCopy(T, S) // strcpy( T, S ) 2）联接 ConCat( T, S1, S2 ) // strcat(T, S) 3）求串长 StrLength( S ) // strlen(S) 4）求子串 SubString(Sub, S, pos, len) 5）串比较 StrCompare(S,T) // strcmp(S,T)。 6）插入 StrInsert(S, pos, T) 7）删除 StrDelete(S, pos, len) 8）子串定位 Index( S, T, pos ) // strstr(S,T)。 9）置换 Replace(S, T, V) 二、基本运算 严格说来，只有前5个是基本运算，后面4个不是。 例如利用置换运算 Replace(S, T, V)可完成插入和删除功能 4.2 串的表示和实现 1 ．顺序存储 2 ．索引存储 3 ．链式存储 串是特殊的线性表，存储结构与线性表的存储结构类似 4.2.1 顺序存储表示 非紧缩格式 紧缩格式 带终结符 const int maxsize = 100 ; char ch[maxsize+1] ; //存放终结符 const int maxsize=100 ; typedef struct { char ch[maxsize] ; //不存终结符 int n ; 　　　 //当前串长 } sqstring ; 无终结符 4.2.1 顺序存储表示 复制 StrCopy( S, T) 插入 StrInsert(S, pos, T) 置换 Replace(S, T, V) 截断方式 重定义S串 判断 pos, len 的有效性 求子串 SubString(Sub, S, pos, len) 为解决截断问题，使用new申请动态堆存储串 const int nodesize=4; //结点大小，假设为4 typedef struct node * pointer; //结点指针类型 struct node { char S[nodesize]; pointer next; }; typedef pointer lkstring; //链串类型 填充特殊字符 字符移动 4.2.2 链式存储 用串名作关键字组织索引表，其中地址部分指出串起始地址、末地址。末地址的表示：串长、尾指针、串尾结束符等。 4.2.3 索引存储 堆结构：在系统中开辟一个容量很大、地址连续的空间作可用空间，建新串时从中分配存储空间。每个串建立一个索引，指出该串的长度、及在可用空间中的起始位置。 实现多个串值空间的共享和动态分配。 例如，文本编辑，整个文本建堆，每行建索引，名字域就是行号，称为行表；每页建索引，得到页表。 例 比较两个串的大小 int comp(char s1[],char s2[]) { int i; i=0; while(s1[i]!=’\0’ s1[i]==s2[i]) i++; return s1[i]?s2[i]; } 4.3 串的模式匹配算