数据结构严蔚敏c语言课件.ppt

进入编辑时，先为文本串建立相应的页表和行表，即建立各子串的存储映象。 页表给出页号和该页的起始行号. 行表则指示每一行的行号、起始地址和该行子串的长度。为查找方便，行表是按行号递增顺序存储的。如下表所示。 然后需在文本编辑程序中设立页指针、行指针和字符指针，分别指示当前操作的页、行和字符。从而实现基本操作。 行 号 起 始 地 址 长 度 100 101 102 103 104 105 201 209 226 250 267 282 8 17 24 17 15 2 本章小结 熟悉串的五种基本操作的定义、并能利用这些基本操作实现串的其它各种操作的方法； 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法； 理解串匹配的KMP算法，熟悉next函数的定义，掌握手工计算给定模式串的next函数值和改进的next函数值； 理解串操作的应用方法和特点。 用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 例如： #define MAXSTRLEN 255 //用户可用的最大串长 typedef unsigned char SString[MAXSTRLEN＋1 ]; SString S; //S是一个可容纳255个字符的顺序串。 一、定长顺序存储 一般用SString[0]来存放串长信息； C语言约定在串尾加结束符 ‘ \0’，但不计入串长； 若字符串超过MAXSTRLEN, 则自动截断 （因为静态数组存不进去）。 算法描述 两串连接Concat(T,S1,S2) (算法4.2) 用T返回S1和S2连接成的新串. Status Concat(SString T, SString S1, SString S2,) { // 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE，否则FALSE。 return uncut; } // Concat 串的联接算法中需分三种情况处理： T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; } if (S1[0]+S2[0] = MAXSTRLEN) {// 未截断 else if (S1[0] MAXSTRLEN { // 截断 else { // 截断(仅取S1) T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN－S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; uncut = FALSE; } 求子串 SubString(Sub,S,pos,len) 将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中（注：串Sub的预留长度与S一样） 求子串函数SubString(Sub, S, pos, len) Status SubString(SString sub, SString S, int pos, int len ) { if(pos1 || posS[0] || len0 || lenS[0]-pos+1) return ERROR; //pos和len不合法则告警 Sub[1……len]=S[pos…pos+len-1]; Sub[0]=len; return OK; } s =‘ a1 , a2 , …….. , an’ pos len 讨论：想存放超长字符串怎么办？——静态数组有缺陷！ 改用动态分配的一维数组—— “堆”！ 思路：利用malloc函数合理预设串长空间。 特点： 若在操作中串值改变，还可以利用realloc函数按新串长度增加(堆砌)空间。 Typedef struct { char *ch; // 若非空串,按串长分配空间; 否则 ch = NULL int length; //串长度 }HString 仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。 二、堆分配存储 Status StrInsert ( HString S, int pos, HString T