下载文档原格式
第4章串串：限定数据元素类型的线性表。
1 逻辑结构1.1 定义位串：数据元素属于{0,1}ASCII码串: 数据元素属于ASCII码字符集。
数字串：数据元素属于整数集合2 顺序串///////////////////////////////// // 项目路径：7动态顺序串/////////////////////////////////2.2 构造/析构（测试函数Test1）template <class T>String<T>:: String( ){ m_Data=NULL; m_Size=m_Length=0; }template <class T>String<T>::String(T a[], int n){ m_Size = m_Length = n;m_Data = new T[m_Size];if(!m_Data) throw "内存不够，上溢";for(int i=0; i<m_Length; i++)m_Data[i]=a[i];}template <class T>String<T>::String(String &s) // 拷贝构造函数{ m_Size = m_Length = s.m_Length;m_Data = new T[m_Size];if(!m_Data) throw "内存不够，上溢";for(int i=0; i<m_Length; i++)m_Data[i]=s.m_Data[i];}template <class T>String<T>:: ~String( ){ delete []m_Data; }2.3 比较（测试函数Test2）// 重载<template <class T>bool String<T>::operator<(String &s){ for(int i=0; i<m_Length && i<s.m_Length; i++) { if(m_Data[i]<s.m_Data[i]) return true;if(m_Data[i]>s.m_Data[i]) return false;}if(m_Length<s.m_Length) return true;return false;}// 重载==template <class T>bool String<T>::operator==(String &s){ for(int i=0; i<m_Length && i<s.m_Length; i++) if(m_Data[i]!=s.m_Data[i]) return false; if(m_Length==s.m_Length) return true;return false;}2.4 取子串、连接（测试函数Test3）// 取子串template <class T>String<T> String<T>::Substr(int pos,int len) { if(pos+len>m_Length) // 预防子串长度越界len=m_Length-pos;String<T> s;s.m_Length=s.m_Size=len;s.m_Data = new T[s.m_Size];if(!s.m_Data) throw "内存不够，上溢";for(int i=0; i<len; i++)s.m_Data[i]=m_Data[pos+i];return s;}// 连接stemplate <class T>void String<T>::Concat(String s){ if(m_Length+s.m_Length > m_Size) // 空间不够ReNew(m_Length+s.m_Length);for(int i=0; i<s.m_Length; i++)m_Data[m_Length+i] = s.m_Data[i];m_Length += s.m_Length;}// 重新分配串的存储空间template <class T>void String<T>::ReNew(int size){ T *p=new T[size]; // 重新申请空间 m_Size=size;for(int i=0; i<m_Length; i++) // 数据迁移p[i]=m_Data[i];delete []m_Data; // 释放原串空间 m_Data = p;}2.5 插入、删除（测试函数Test4）// 第i个位置上插入stemplate <class T>void String<T>::Insert(int pos, String s){ if(m_Length+s.m_Length > m_Size) // 空间不够 ReNew(m_Length+s.m_Length);for(int i=m_Length-1; i>=pos; i--) // 向后移位 m_Data[i+s.m_Length] = m_Data[i];for(i=0; i<s.m_Length; i++)m_Data[pos+i] = s.m_Data[i];m_Length += s.m_Length;}// 删除子串template <class T>void String<T>::Delete(int pos,int len){ for(int i=pos+len; i<m_Length; i++) // 向前移位 m_Data[i-len] = m_Data[i];m_Length -= len;}2.6 顺序串的评价优点：访问子串方便，缺点：空间大小不灵活，插入、删除费时。
第四章串本章介绍了串的逻辑结构，存储结构及串上的基本运算，由于在高级语言中已经提供了较全面的串处理功能，因此本章的重点是掌握在串上实现的模式匹配算法，同时这也是本章的难点。
但是从全书来讲，这属于较简单的一章内容。
4.1 串类型的定义一、串定义：串（String）（或字符串）：由零个或多个字符组成的有限序列。
一般记为： s='a1a2...an'(n>=0)其中：s是串的名，用单引号括起来的字符序列是串的值。
串的长度：串中字符的数目n。
空串：零个字符的串，它的长度为零。
子串：串中任意个连续的字符组成的子序列称为该串的子串。
主串：包含子串的串相应地称为主串。
位置：字符在序列中的序号称为该字符在串中的位置。
子串在主串中的位置：以子串的第一个字符在主串中的位置来表示。
例：a='BEI',b='JING',c='BEIJING',d='BEI JING'串长分别为3,4,7,8,且a,b都是c,d的子串。
称两个串是相等的，当且仅当这两个串的值相等。
特别地，空串是任意串的子串，任意串是其自身的子串。
二、串的抽象数据类型的定义：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)：chars是字符常量。
生成一个其值等于chars的串T。
StrCopy(&T,S)：串S存在则由串S复制得串TStrEmpty(S)：串S存在则若S为空串,返回真，否则返回假StrCompare(S,T)：串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T,则返回值<0StrLength(S)：串S存在返回S的元素个数称为串的长度.ClearString(&S)：串S存在将S清为空串Concat(&T,S1,S2)：串S1和S2存在用T返回由S1和S2联接而成的新串SubString(&Sub,S,pos,len)：串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1Index(S,T,pos)：串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0Replace(&S,T,V)：串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串StrInsert(&S,pos,T)：串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串TStrDelete(&S,pos,len)：串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串DestroyString(&S)：串S存在,则串S被销毁}ADT String三、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。
