三种特殊的线性表——栈、队列、串

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

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

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

串长:串中字符个数&＃xff08;n≥0&＃xff09;. n&＃61;0 时称为空串 。

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

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

串相等:串长度相等&＃xff0c;且对应位置上字符相等。

子串&＃xff1a;串中任意个连续的字符组成的子序列。

主串&＃xff1a;包含子串的串。

子串的位置&＃xff1a;子串的第一个字符在主串中的序号。

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

串是有限长的字符序列&＃xff0c;由一对双引号相括&＃xff0c;如: “a string”

StrInsert (&S, pos, T)    (插入) 初始条件&＃xff1a;串 S 和 T 均存在&＃xff0c;1≤pos≤StrLength(S)&＃xff0b;1。 操作结果&＃xff1a;在串 S 的第 pos 个字符之前插入串T。例如&＃xff1a;S &＃61; "chater"&＃xff0c;T &＃61; "rac ", 则执行 StrInsert (S, 4, T) ,得到 S &＃61; "character"

StrDelete (&S, pos, len)    (删除) 初始条件&＃xff1a;串 S 存在&＃xff0c;且1≤pos≤StrLength(S)-len&＃43;1。 操作结果&＃xff1a;从串 S 中删除第 pos 个字符起长度为len的子串。

StrAssign (&T, chars)    (串赋值) 初始条件&＃xff1a;chars 是字符串常量。 操作结果&＃xff1a;把 chars 赋为 T 的值。

StrCopy (&T, S)    (串复制) 初始条件&＃xff1a;串 S 存在。 操作结果&＃xff1a;由串 S 复制得串 T。

Concat (&T, S1, S2)    (串联接) 初始条件&＃xff1a;串 S1 和 S2 存在。 操作结果&＃xff1a; T 为由串 S1 和串 S2 联接所得的串。例如&＃xff1a; Concat( T, "man", "kind")           求得  T &＃61; "mankind"         Concat( T, "kind", "man")           求得  T &＃61; "kindman"

StrCompare (S, T)    (串比较) 初始条件&＃xff1a;串 S 和 T 都存在。 操作结果&＃xff1a;由串 S > T, 则返回值>0&＃xff1b;若S&＃61;T,则返回值&＃61;0&＃xff1b;由串 S 例如&＃xff1a;StrCompare(" data ", " state ") 0

Replace ( S, T, V)    (串置换) 初始条件&＃xff1a;串 S, T 和 V 均已存在&＃xff0c;且 T 是非空串。 操作结果&＃xff1a;用 V 替换主串 S 中出现的所有与&＃xff08;模式串&＃xff09;T 相等的不重叠的子串。例如&＃xff1a;假设 S &＃61; "abcaabcaaabca",  T &＃61; "bca ",若 V &＃61; "x ", 则经置换后得到     S &＃61; "axaxaax "

SubString (&Sub, S, pos, len)    (求子串) 初始条件&＃xff1a;串 S 存在&＃xff0c;1≤pos≤StrLength(S)   且  0≤len≤StrLength(S)-pos&＃43;1。      操作结果: 以 Sub 返回串 S 中第 pos 个字符起长度为 len 的子串。例如&＃xff1a;子串为“串”中的一个字符子序列.SubString ( sub, "commander ", 4, 3)求得  sub &＃61; "man ";SubString( sub, "commander ", 1, 9)求得  sub &＃61; "commander ";SubString( sub, "commander ", 9, 1)求得  sub &＃61; "r ".

 Index ( S, T, pos)    (定位函数) 初始条件&＃xff1a;串 S 和 T 存在&＃xff0c;且 T 是非空串&＃xff0c;1≤pos≤StrLength(S)。 操作结果&＃xff1a;若主串 S 中存在和串 T 值相同的子串&＃xff0c;则返回它在主串 S 中第 pos个字符之后第一次出现的位置; 否则函数值为0。

 “子串在主串中的位置”意指子串中的第一个字符在主串中的“位序” 。假设 S &＃61; "abcaabcaaabc ",  T &＃61; &＃39;bca “,Index(S, T, 1) &＃61; 2;Index(S, T, 3) &＃61; 6;Index(S, T, 8) &＃61; 0;

串赋值 StrAssign   串比较 StrCompare、求串长 StrLength、   串联接 Concat 以及求子串 SubString 等5种操作构成串类型的最小操作子集。

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

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

在线性表的基本操作中&＃xff0c;大多以“单个元素”作为操作对象&＃xff1b;     而在串的基本操作中&＃xff0c;通常以“串的整体”作为操作对象。

串有三种机内表示方法&＃xff1a;

顺序存储

定长顺序存储表示 ——用一组地址连续的存储单元存储串值的字符序列。

堆分配存储表示 ——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。

链式存储

串的块链存储表示 ——链式方式存储

定长顺序存储特点&＃xff1a;    用一组连续的存储单元来存放串&＃xff0c;直接使用定长的字符数组来定义&＃xff0c;数组的上界预先给出&＃xff0c;故称为静态存储分配。

例如&＃xff1a;

#define Maxstrlen 255    //用户可用的最大串长    typedef unsigned char SString[ Maxstrlen&＃xff0b;1 ] ;       SString s;   //s是一个可容纳255个字符的顺序串。

注&＃xff1a;  一般用SString[0]来存放串长信息&＃xff1b;

C语言约定用字符数组存储字符串常量时&＃xff0c;自动在串尾加结束符 ‘ \0’&＃xff0c;以利操作加速&＃xff0c;但不计入串长&＃xff1b;

char c[10]&＃61;“abcde” 若字符串超过Maxstrlen 则自动截断&＃xff08;因为静态数组存不 进去&＃xff09;。  

1) 串连接 Concat(&T, S1,S2)

Status Concat ( Sstring &T, Sstring S2){if ( S1[0] &＃43;S2[0] } // Concat

2) 求子串函数SubString (&Sub, S, pos, len)----将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中&＃xff08;注&＃xff1a;串Sub的预留长度与S一样&＃xff09;

Status SubString (SString &sub, SString S, int pos, int len ){if (posS[0] || lenS[0]-pos&＃43;1)return ERROR; //pos不合法则警告Sub[1……len] &＃61; S [pos……pos&＃43;len-1];Sub[0]&＃61;len;return OK;}

想存放超长字符串怎么办&＃xff1f;——静态数组有缺陷&＃xff01;改用动态分配的一维数组——“堆”&＃xff01;

堆分配存储特点&＃xff1a;仍用一组连续的存储单元来存放串&＃xff0c;但存储空间是在程序执行过程中动态分配而得。

思路&＃xff1a;利用malloc函数合理预设串长空间。

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

约定&＃xff1a;所有按堆存储的串&＃xff0c;其关键信息放置在&＃xff1a;

Typedef struct {char *ch; // 若非空串,按串长分配空间; 否则 ch &＃61; NULLint length; //串长度}HString

1&＃xff09;用“堆”实现串插入操作

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

2)  堆分配存储表示

Status StrAssign( HString &T, char *chars ) {if (T.ch) free(T.ch);for (i&＃61;0, c&＃61;chars;* c; &＃43;&＃43;i, &＃43;&＃43;c); //求串长度//直到终值为“假”停止&＃xff0c;串尾特征是‘/0’&＃xff1d;NULL&＃61;0//指针变量C也可以自增&＃xff01;意即每次后移一个数据单元。if (!i) {T.ch &＃61; NULL; T.length &＃61; 0;}else{if (!(T.ch &＃61; (char*)malloc (i*sizeof(char))))exit(OVERFLOW);T.ch[0..i-1] &＃61; chars[0..i-1];T.length &＃61;i;}Return OK;}//StrAssign

3) 比较字符串是否相同

Int Strcompare ( Hstring S, Hstring T ){ for ( i &＃61; 0; i

  4) 清空字符串

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

5) 联接两个串成新串

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

6&＃xff09;求子串

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

链式存储特点 &＃xff1a;用链表存储串值&＃xff0c;易插入和删除。

链表结点&＃xff08;数据域&＃xff09;大小取1

链表结点&＃xff08;数据域&＃xff09;大小取n(例如n&＃61;4)

法1存储密度为     1/2  &＃xff1b;法2存储密度为      9/15&＃61;3/5     &＃xff1b;

显然&＃xff0c;若数据元素很多&＃xff0c;用法2存储更优—称为块链结构

块链类型定义&＃xff1a;

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

串的链式存储结构对某些操作比较方便&＃xff0c;但是总体来说没有前面的两种存储结构灵活。

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

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

空串和空白串的区别&＃xff1a;空串(Null String)是指长度为零的串&＃xff1b;而空白串(Blank  String),是指包含一个或多个空白字符‘  ’(空格键)的字符串.

模式匹配(Pattern Matching) 即子串定位运算&＃xff08;Index函数&＃xff09;。

算法目的&＃xff1a;确定主串中所含子串第一次出现的位置&＃xff08;定位&＃xff09;       ——即如何实现 Index(S,T,pos)函数

初始条件&＃xff1a;串S和T存在&＃xff0c;T是非空串&＃xff0c;1≤pos≤StrLength(s)

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

注&＃xff1a;S称为被匹配的串&＃xff0c;T称为模式串。若S包含串T&＃xff0c;则称“匹配成功”&＃xff0c;否则称 “匹配不成功” 。

 BF算法  &＃xff08;又称古典或经典的、朴素的、穷举的&＃xff09;  KMP算法&＃xff08;特点&＃xff1a;速度快&＃xff09;

① BF算法设计思想&＃xff1a; 将主串的第pos个字符和模式的第1个字符比较&＃xff0c;若相等&＃xff0c;继续逐个比较后续字符&＃xff1b;若不等&＃xff0c;从主串的下一字符&＃xff08;pos&＃43;1&＃xff09;起&＃xff0c;重新与第一个字符比较。  直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号&＃xff0c;即匹配成功。   否则&＃xff0c;匹配失败&＃xff0c;返回值 0 .

模式匹配——BF算法

例&＃xff1a;主串S&＃61;"ababcabcacbab"&＃xff0c;模式T&＃61;"abcac"

② BF算法的实现—即Index&＃xff08;&＃xff09;操作的实现 

Int Index (SString S, SString T, int pos) {i&＃61;pos; j&＃61;1;while ( iT[0]) return i-T[0]; //子串结束&＃xff0c;说明匹配成功else return 0;}//Index

若n为主串长度&＃xff0c;m为子串长度&＃xff0c;则串的BF匹配算法最坏的情况下需要比较字符的总次数为O(n*m)----BF匹配算法的最坏时间复杂度

最恶劣情况是&＃xff1a;主串中前面n-m个位置都部分匹配到子串的最后一位时出现不等&＃xff0c;此时需要将指针i回溯&＃xff0c;并从模式的第一个字符开始重新比较&＃xff0c;整个匹配过程中&＃xff0c;指针i需回溯&＃xff08;n-m)次&＃xff0c;则while循环次数为(n-m&＃43;1)*m。例如&＃xff1a;S&＃61;"aaaaaaaaaaab" &＃xff0c;T&＃61;"aaab"&＃xff0c;但一般情况下BF算法的时间复杂度为近似于O(n&＃43;m)

KMP算法&＃xff08;特点&＃xff1a;速度快&＃xff09;

① KMP算法设计思想

利用已经部分匹配的结果而加快模式串的滑动速度&＃xff0c;而且主串S的指针i不必回溯&＃xff01;可提速到O(n&＃43;m)&＃xff01;

② KMP算法的推导过程

抓住部分匹配结果的两个特征&＃xff1a;

设目前应与T的第k字符开始比较&＃xff0c;则T的k-1&＃xff5e;1位&＃xff1d;S前i-1&＃xff5e;i-(k-1)位&＃xff0c;即&＃xff1a;S中位置i前面的k-1位字符串&＃61;T中的前k-1位

刚才肯定是在S的i处和T的第j字符 处失配&＃xff0c;则S前i-1&＃xff5e;i-(k-1)位&＃xff1d;T的j-1&＃xff5e;j-(k-1)位&＃xff0c;即&＃xff1a;S中位置i前面的k-1位字符串&＃61;T中j前面的k-1位

两式联立可得&＃xff1a;‘T1…Tk-1’&＃61;‘Tj-(k-1) …Tj-1’

注意&＃xff1a;j 为当前已知的失配位置&＃xff0c;我们的目标是计算新起点 k&＃xff0c; 仅剩一个未知数k&＃xff0c;理论上已可解&＃xff0c;且k仅与模式串T有关&＃xff01;

根据模式串T的规律&＃xff1a;   ‘T1…Tk-1’&＃61;‘Tj-(k-1) …Tj-1’ 和已知的当前失配位置j &＃xff0c;可以归纳出计算新起点 k的表达式。 令k &＃61; next[ j ]&＃xff0c;则

③ KMP算法的实现 &＃xff08;关键技术:计算next[j]&＃xff09;

第一步:先把模式T所有可能的失配点j所对应的next[j]计算出来&＃xff1b;

第二步: 执行定位函数index_kmp &＃xff08;与BF算法模块非常相似&＃xff09;

Int Index_KMP (SString S, SString T, int pos) {i&＃61;pos; j&＃61;1;while ( iT[0]) return i-T[0]; //子串结束&＃xff0c;说明匹配成功else return0;}//Index_KMP

求解next[j] 算法的流程图:

void get_next (SString T, int &next[ ] ){ //next函数值存入数组nexti&＃61;1; next[1]&＃61;0; j&＃61;0;while(i}// get_next

改进算法nextval [ j ]

void get_nextval (SString T, int &nextval[ ] ){ //next函数修正值存入数组nextvali&＃61;1; nextval[1]&＃61;0; j&＃61;0;while ( i}// get_nextval

④ KMP算法的时间复杂度

回顾BF的最恶劣情况&＃xff1a;S与T之间存在大量的部分匹配&＃xff0c;比较总次数为&＃xff1a; (n-m&＃43;1)*m&＃xff1d;O(n*m)

而此时KMP的情况是&＃xff1a;由于指针i无须回溯&＃xff0c;比较次数仅为n,即使加上计算next[j]时所用的比较次数m&＃xff0c;比较总次数也仅为n&＃43;m&＃61;O(n&＃xff0b;m)&＃xff0c;大大快于BF算法。

注意&＃xff1a;由于BF算法在一般情况下的时间复杂度也近似于O(n&＃43;m), 所以至今仍被采用。

KMP算法的用途&＃xff1a;因为主串指针i不必回溯&＃xff0c;所以从外存输入文件时可以做到边读入边查找&＃xff0c;“流式”作业&＃xff01;