串的基础知识

迈不过友情╰ 2022-07-24 11:04 271阅读 0赞

从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。

串是重要的非数值处理对象，它是以字符作为数据元素的线性表。

串：即字符串，是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。

若干术语：

串长:串中字符个数（n≥0）， n=0 时称为空串 。

空白串:由一个或多个空格符组成的串。

字符位置:字符在串中的序号。

串相等:串长度相等，且对应位置上字符相等。

子串：串中任意个连续的字符组成的子序列。

主串：包含子串的串。

子串的位置：子串的第一个字符在主串中的序号。

串的数据对象约束为某个字符集。

微机上常用的字符集是标准ASCII码，由 7 位二进制数 表示一个字符，总共可以表示 128 个字符。扩展ASCII 码由 8 位二进制数表示一个字符，总共可以表示 256 个 字符，足够表示英语和一些特殊符号，但无法满足国际需要。 Unicode码由 16 位二进制数表示一个字符，总共可以表示2的16次方个字符，即6万5千多个字符，能够表示世界上所有语言的所有字符，包括亚洲国家的表意字符。为了保持兼容性，Unicode字符集中的前256个字符与扩展ASCII码完全相同。

ADT String {
            数据对象：
            D＝{ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 
            数据关系：
            R1＝{ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n }
            基本操作：
            
    } ADT String

![Center][]

StrInsert (&S, pos, T) (插入)

初始条件：串 S 和 T 均存在，1≤pos≤StrLength(S)＋1。

操作结果：在串 S 的第 pos 个字符之前插入串T。

例如：S = "chater"，T = "rac", 则执行 StrInsert (S, 4, T) 得到 S = "character"

StrDelete (&S, pos, len) (删除)

初始条件：串 S 存在，且1≤pos≤StrLength(S)-len+1。

操作结果：从串 S 中删除第 pos 个字符起长度为len的子串。

StrAssign (&T, chars) (串赋值)

初始条件：chars 是字符串常量。

操作结果：把 chars 赋为 T 的值。

StrCopy (&T, S) (串复制)

初始条件：串 S 存在。

操作结果：由串 S 复制得串 T。

Concat (&T, S1, S2) (串联接)

初始条件：串 S1 和 S2 存在。

操作结果：T 为由串 S1 和串 S2 联接所得的串。

例如： Concat( T, "man", "kind") 求得 T = "mankind" Concat( T, "kind", "man") 求得 T = "kindman"

StrCompare (S, T) (串比较)

初始条件：串 S 和 T 都存在。

操作结果：若串 S > T, 则返回值>0；若S=T, 则返回值=0；若串 S < T, 则返回值<0.

例如：StrCompare("data", "state") < 0 StrCompare("compute", "case") > 0

Replace ( S, T, V) (串置换)

初始条件：串 S, T 和 V 均已存在，且 T 是非空串。

操作结果：用 V 替换主串 S 中出现的所有与（模式串）T 相等的不重叠的子串。

例如： 假设 S = "abcaabcaaabca", T = "bca" 若 V = "x", 则经置换后得到 S = "axaxaax" 若 V = "bc", 则经置换后得到 S = "abcabcaabc"

SubString (&Sub, S, pos, len) (求子串)

初始条件： 串 S 存在，1≤pos≤StrLength(S) 且 0≤len≤StrLength(S)-pos+1。

操作结果: 以 Sub 返回串 S 中第 pos 个字符起长度为 len 的子串。

例如： SubString ( sub, "commander", 4, 3)  求得 sub = "man"

SubString( sub, "commander", 1, 9) 求得 sub = "commander"

SubString( sub, "commander", 9, 1) 求得 sub = "r"

Index ( S, T, pos) (定位函数)

初始条件：串 S 和 T 存在，且 T 是非空串， 1≤pos≤StrLength(S)。

操作结果：若主串 S 中存在和串 T 值相同的子串，则返回它在主串 S 中第 pos个字符起第一次出现的位置; 否则函数值为0。

假设 S = "abcaabcaaebc", T = "abc" Index(S, T, 1) = 1;  Index(S, T, 3) = 5;  Index(S, T, 8) = 0;

**串和线性表的区别**

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别。

在线性表的基本操作中，大多以“单个元素”作为操作对象；

而在串的基本操作中，通常以“串的整体”作为操作对象。

**串的表示和实现  
![20160520200418065][]**

定长顺序存储特点：

用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。

例如：

\#define Maxstrlen 255 //用户可用的最大串长

typedef unsigned char SString\[ Maxstrlen＋1 \] ;

SString s; //s是一个可容纳255个字符的顺序串。

注： 一般用SString\[0\]来存放串长信息；

C语言约定在串尾加结束符 ‘ \\0’，以利操作加速，但不计入串长；

若字符串超过Maxstrlen 则自动截断（因为静态数组存不 进去）。

如果想要存放超长的字符串，静态数组有缺陷，改用动态分配的一维数组----------堆

堆分配存储特点：

仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。

思路：利用malloc函数合理预设串长空间。

特点： 若在操作中串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。

约定：所有按堆存储的串，其关键信息放置在：

Typedef struct \{

char \*ch; // 若非空串,按串长分配空间; 否则 ch = NULL

int length; //串长度

\}HString

用“堆”实现串插入操作

Status StrInsert ( HString &S,  int pos,  HString T ) {                    
            //在串S的第pos个字符之前（包括尾部）插入串T 
            if (pos<1||pos>S.length+1) return ERROR;    //pos不合法则告警    
            if(T.length){          //只要串T不空，就需要重新分配S空间，以便插入T     
            if (!（S.ch=(char*)realloc (S.ch, (S.length+T.length)* sizeof(char))  ))  exit(OVERFLOW);           
                for ( i=S.length-1; i>=pos-1; --i )   //为插入T而腾出pos之后的位置             
                S.ch [i+T.length] = S.ch [i];       //从S的pos位置起全部字符均后移           
                S.ch[pos-1…pos+T.length-2] = T.ch[0…T.length-1];   //插入T，略/0                         
                S.length + = T.length;  //刷新S串长度    
            } 
            return OK; 
    }//StrInsert

堆分配存储表示  
![20160520200538862][]  
比较字符串是否相同

Int  Strcompare ( Hstring S, Hstring T )  {         
            for ( i = 0; i < S.length && i <T.length; ++i )           
            if ( S.ch[i] != T.ch[i] )  
                return  S.ch [i] – T.ch[i];      
            return  S.length- T.length;   
    }  // StrCompare

清空字符串

Status ClearString ( Hstring  &S) {         
            if ( S.ch )  { free(S.ch);  S.ch = NULL; }       
            S.length = 0;       
            return  OK;  
    } // ClearString

联接两个串成新串

Status Concat ( HString  &T, Hstring  S1,  Hstring  S2 ) {  
            //用T返回由S1和S2联接而成的新串。      
            if (T.ch)   free(T.ch);            // 释放旧空间     
            if ( !(T.ch = (char *) malloc ((S1.length+S2.length) *sizeof (char) ) ) )       exit ( OVERFLOW);      
            T.ch[0 .. S1.length-1] = S1.ch[0 .. S1.length-1];      
            T.length = S1.length + S2.length ;      
            T.ch [S1.length .. T.length-1] = S2.ch [0 .. S2.length-1];       
            return  OK;   
    } // Concat

求子串

Status SubString ( Hstring &Sub, Hstring S, int pos, int len ) { 
             //用Sub返回串S的第pos个字符起长度为len的子串。 
            // 其中,1<=pos<= StrLength (S) 且 0<=len<=StrLength(S)-pos+1。      
            if ( pos < 1 || pos>S.length || len<0 ||  len>S.length-pos+1)           
            return  ERROR;        // 参数不合法      
            if ( Sub.ch)   free ( Sub.ch);    // 释放旧空间      
            if (!len)  { Sub.ch = NULL; Sub.length = 0; }   // 空子串         
            else {// 完整子串                  
                Sub.ch = ( char *) malloc ( len *sizeof ( char ));                  
                Sub.ch[0..len-1] = S.ch [ pos-1.. Pos+len-2] ;                  
                Sub.length = len;                  
            }                 
            return  OK;
     }

![20160520200701456][]  
块链类型定义：

#define  CHUNKSIZE  80     //可由用户定义的块大小 
            typedef  struct  Chunk {           //首先定义结点类型            
                char    ch [ CHUNKSIZE ];  //结点中的数据域            
                struct  Chunk * next ;          //结点中的指针域 
            }Chunk;
            typedef  struct {                 //其次定义用链式存储的串类型             
                Chunk  *head;           //头指针             
                Chunk  *tail;             //尾指针             
                int  curLen;               //结点个数    
            } LString;        //串类型只用一次，前面可以不加Lstring

注：

串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。

这类操作中均涉及到定位问题，称为串的模式匹配。它是串处理系统中最重要的操作之一。

关于串的模式匹配敬请期待。  
申明：备考期末，如果不到之处，敬请指出，感激不尽。

[Center]: /images/20220722/566911786ae8453d951a6a087fba4b4b.png
[20160520200418065]: /images/20220722/b4fa4383c4cc4d2d9fd8265b4f2773b0.png
[20160520200538862]: /images/20220722/f2aacd79d7d24b6a853df0e148ad3bc1.png
[20160520200701456]: /images/20220722/351cc89d54cb49aeab7137ab9cb4fcc9.png