数据结构-线性表.ppt

《数据结构-线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构-线性表.ppt（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1/15,数据结构串,2/15,知识点：串的定义、表示与实现，定位函数,第四章 串,3/15,第四章 串,4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法4.4 串操作应用举例,4/15,4.1 串类型的定义,串一对单引号括起的字符序列，如“abcd ef”一般地，串是由零个或多个字符组成的有限序列一些概念：串的长度、空串、子串、主串、 字符/子串在串/主串中的位置如：S=“Data Structure”，S为串名，“Data Structure”为串值，长度为14；“ata Str”为主串S的子串，它在S中的位置为2称两个串是相等的，当且仅当这两个串的值相等。空格串 vs.

2、 空串是特殊的线性表 1)元素类型为字符； 2)操作对象：个体(字符)与整体(子串),5/15,4.1 串类型的定义-ADT String,ADT String 串的整体操作赋值 StrAssign(S, “Data Structure”)复制 StrCopy(T, S) / T0) / pos的合法性n = StrLength(S); m = StrLength(T); i = pos;while( i=n-m+1) SubString(sub, S, i, m); if (StrCompare(sub, T) != 0) +i; else return i; / 返回子串在主串中的位置 /

3、 while / if return 0; / S中不存在与T相等的子串 / Index,7/15,4.2 串的表示和实现-定长顺序存储,定长顺序存储表示-顺序映像类型定义typedef unsigned char SStringMAXSTRLEN+1; 约定：1) 下标为0的分量存放串的长度 或 2)串值后加入一个不计入串长的结束标记字 符，如C语言中的0 串联接Concat(&T, S1, S2) 是定长存储，联接后T的串长为S1和S2串长之和，该长度可能会超出MAXSTRLEN分情况处理，超出部分要“截断”,8/15,4.2 串的表示和实现-定长顺序存储,串联接Concat(,9/15,

4、4.2 串的表示和实现-定长顺序存储,求子串SubString( 评价串长超出最大长度，约定采用截尾法串长过小，则串空间浪费较大,10/15,4.2 串的表示和实现-堆分配存储,堆分配存储表示-顺序映像类型定义typedef struct char *ch;/ 串值所在的存储区的起始地址 int length;/ 串长度 HString; 一些操作的实现基于复制 利用malloc()分配一块足够的空间，再按要求完成复制；如StrAssign(&T,chars), Concat(&T, S1, S2), SubString(&Sub, S, pos, len),11/15,4.2 串的表示和实现

5、-堆分配存储,堆分配存储表示-顺序映像一些操作的实现基于链接建立串名和串值的映射关系，如: StrAssign(&T, chars) 评价基于动态存储管理建立串名和串值的映射关系处理方便、串值共享,12/15,4.2 串的表示和实现-块链存储,块链存储表示-链式映像sizeof(char) sizeof(链域) 存储密度不高存储密度 = 串值所占的存储位/实际分配的存储位类型定义typedef struct Chunk char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct Chunk *head, *tail;/ 串的头和尾指针

6、 int curlen;/ 串的当前长度 LString;,13/15,4.2 串的表示和实现-块链存储(续),存储密度的影响存储密度小，运算处理方便，但存储占用量大评价存储密度较低块链使串的操作复杂化顺序映像的缺点空间利用率低空间不可扩充，使串的某些操作（联接、置换）受到限制插入、删除、置换操作带来的移动,14/15,4.3 串的模式匹配算法,求子串位置的定位函数 Index(S, T, pos)模式匹配(T:模式串)基于堆分配存储的算法int Index( HString S, HString T, int pos ) i = pos; j = 1; while ( iT.length) return (i T.length); else return 0;,15/15,4.4 串操作应用举例,文本编辑处理规则：行插入/删除，页插入/删除，数据结构：页表、行表(行号，起始地址，长度)建立词索引表数据结构词表书名中的关键词集合关键词索引表,