第4章串文件.ppt

数据结构;内容提要;基本 要求;记为： s =‘ a1 a2 …….. an’ (n≥0 );术语：; 子串： 子串位置： 字符位置： 串相等：;ADT String{ Objects: D={ai | ai∈CharacterSet, i=1, 2,…，n, n≥0} Relations: R1={ai-1,ai | ai-1,ai ∈D, i=2, …，n} functions: StrAssign(T, chars) // 串赋值，生成值为chars的串T StrCompare(S,T) // 串比较，若ST，返回值大于0… StrLength(S) // 求串长，即返回串S中的元素个数 Concat(T, S1, S2) // 串连接，用T返回S1＋S2的新串 SubString(Sub, S, pos, len) // 求S中pos起长度为len的子串 …… Index(S, T, pos) //子串定位函数（模式匹配），返回位置 Replace(S, T,V) // 用子串V替换子串T }ADT String;Replace(S, T,V) // 用子串V换子串T;解答: INDEX（s,’A’）返回的只是“第一次”出现的位置。 如果还要有哪些信誉好的足球投注网站后面的A，则pos变量要跟着变才行。 也就是说，要把得到的“第一次”位置再代入INDEX（ s,’A’，pos）函数中循环操作才行。 ;4.2 串的表示和实现;定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。;例1：用顺序存储方式编写求子串函数SubString(Sub,S,pos,len) ; 0 1 ;s1.ch;大家来思考;思路：利用malloc函数合理预设串长空间。 特点： 若在操作中串值改变，还可以利用realloc函数按新串长度增加空间（即动态数组概念） 。;C是指针变量，可以自增！意即每次后移一个数据单元。;Status StrInsert ( HString S, int pos, HString T ) { //在串S的第pos个字符之前（包括尾部）插入串T if (pos1||posS.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 ) S.ch[i+T.length] = S.ch[i]; // 为插入T而腾出pos之后的位置，即从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;S.length;讨论：法1存储密度为 ；法2存储密度为 ；;#define CHUNKSIZE 80 //每块大小，可由用户定义 typedef struct Chunk { //首先定义结点类型 char ch [ CHUNKSIZE ]; //每个结点中的数据域 struct Chunk * next ; //每个结点中的指针域 }Chunk; ;算法目的：确定主串中所含子串第一次出现的位置（定位） ;BF算法的实现—即编写Index(S,T,pos)函数;Int Index(SString S, SString T, int pos) { i=pos; j=1; while ( i=S[0] j=T[0] ) { if (S[i] = = T