链式存储结构ppt课件.ppt

《链式存储结构ppt课件.ppt》由会员分享，可在线阅读，更多相关《链式存储结构ppt课件.ppt（70页珍藏版）》请在三一办公上搜索。

1、数据结构讲义,第四章 串,2,4.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例,第四章 串,3,1、串类型的定义,串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作s=c0c1c2cn-1 (n0)其中： s为串名，用双引号括起来的字符序列是串的值； ci(0in-1)可以是字母、数字或其它字符； 双引号为串值的定界符，不是串的一部分； 字符串字符的数目n称为串的长度； 零个字符的串称为空串； 仅由空格组成的的串称为空格串。,4,零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Null string），如：s=，它的长度为零；仅由空

2、格组成的的串称为空格串，如：s=；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=Im a student的长度为13。在C语言中，用单引号引起来的单个字符与单个字符的串是不同的， 如s1=a与s2=a两者是不同的，s1表示字符，而s2表示字符串。,空串与空格字符串,5,字符与字符串：称一个字符在串序列中的序号为该字符在串中的位置；当一个字符在串中多次出现时，以该字符第一次在字符串中出现的位置为该字符在串中的位置。子串与主串：子串：一个串的任意个连续的字符组成的子序列称为该串的子串；主串：包含子串的串称为主串。子串在主串中的位置是以子串的第一个字符在主串中的位置来表示的。两串串相等

3、：称两个串是相等的，当且仅当这两个串的值相等。也即：两个串的长度相等，并且各个对应位置的字符都相等时才相等。字符相等意味着字符所对应的ascii值相等。,主串和子串,6,串的基本操作定长顺序存储表示堆分配存储表示串的块链存储表示,2、串的表示和实现,7,串基本操作C语言函数库串处理函数串的基本操作描述串与线性表的比较串的存储结构,串的基本操作,8,串的基本操作分析：常规操作单串操作双串操作子串编辑操作索引操作,串的基本操作,9,常规操作： 字符串初始化： InitString 字符串销毁： DestoryString单串操作： 求字符串长度：StrLength : 判断是否为空串： 将给定字符

4、串清空：双串操作： 两个字符串是否相等； 两个字符串复制； 两个字符串连接；,串的基本操作分析,10,子串编辑操作： 查找给定的子串是否存在： 查找给定的子串存在数量：索引操作： 在某个位置开始插入某个字符串：StrInsert; 在某个位置替换给定长度的子串：StrReplaceIndex； 在某个位置删除给定长度的子串：StrDeleteIndex； 自某位置开始取给定长度的子串：StrSubString,串的基本操作分析,11,C语言函数库串处理函数,对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。例如：C语言函数库中提供下列串处理函

5、数：gets(str) 输入一个串；puts(str) 输出一个串；strcat(str1, str2) 串联接函数；strcpy(str1, str2, k) 串复制函数；strcmp(str1, str2) 串比较函数；strlen(str) 求串长函数；c语言提供的关于字符串处理函数，其说明主要在“string.h”中。,12,C语言函数库串处理函数,strcpy： 将字符串src复制到destStrcat：将字符串src添加到dest末尾Strchr：检索并返回字符c在字符串s中第一次出现的位置Strcmp：字符串s1与s2的大小,并返回s1-s2strcpy ：将字符串src复制到d

6、estStrcspn：扫描s1,返回在s1中有,在s2中也有的字符个数Strdup：将字符串s复制到最近建立的单元Strerror: 本函数返回最近一次的错误信息, Stricmp:比较字符串s1和s2,并返回s1-s2strlen: 返回字符串s的长度,13,C语言函数库串处理函数,strlwr ：字符串s中的大写字母全部转换成小写字母,并返回转换后的字符串strncat：将字符串src中最多maxlen个字符复制到字符串dest中strncmp：比较字符串s1与s2中的前maxlen个字符strncpy：复制src中的前maxlen个字符到dest中strnicmp：比较字符串s1与s2中

7、的前maxlen个字符Strnset： 将字符串s的前n个字符置于ch中strpbrk :扫描字符串s1,并返回在s1和s2中均有的字符个数Strrchr: 扫描最后出现一个给定字符c的一个字符串sStrrev: 将字符串s中的字符全部颠倒顺序重新排列,并返回排列后的字符串Strset: 将一个字符串s中的所有字符置于一个给定的字符ch,14,C语言函数库串处理函数,strspn: 扫描字符串s1,并返回在s1和s2中均有的字符个数 strstr: 扫描字符串s2,并返回第一次出现s1的位置 strtod: 将字符串str转换成双精度数,并返回这个数, strtok: 检索字符串s1,该字符串

8、s1是由字符串s2中定义的定界符所分隔 strtol:将字符串str转换成长整型数,并返回这个数,strupr: 将字符串s中的小写字母全部转换成大写字母,并返回转换后的字符串,串的基本操作,StrAssignStrCopyStrDestroyStrEmptyStrCompareStrLengthStrConcat,StrSubStringStrIndexStrReplaceStrInsertStrDeleteStrClear,16,StrAssign,StrAssign (&T, chars)初始条件：chars 是字符串常量。操作结果：把 chars 赋为 T 的值。,17,StrCopy

9、,StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。,18,StrDestroy,StrDestroy (&S)初始条件：串 S 存在。操作结果：串 S 被销毁。,19,StrEmpty,StrEmpty (S)初始条件：串S存在。操作结果：若 S 为空串，则返回TRUE，否则返回 FALSE。“”表示空串，空串的长度为零。,20,StrEmpty,StrEmpty (S)初始条件：串S存在。操作结果：若 S 为空串，则返回TRUE，否则返回 FALSE。“”表示空串，空串的长度为零。,21,StrCompare,StrCompare (S, T)初始

10、条件：串 S 和 T 存在。操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。例如：StrCompare(data, state) 0,22,StrLength,StrLength (S)初始条件：串 S 存在。操作结果：返回 S 的元素个数,称为串的长度。,23,StrConcat,StrConcat (&T, S1, S2)初始条件：串 S1 和 S2 存在。操作结果：用 T 返回由 S1 和 S2联接而成的新串。 例如： StrConcate( T, man, kind)求得 T = mankind,24,StrSubString,StrSubStri

11、ng (&Sub, S, pos, len)初始条件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。操作结果： 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。子串为“串” 中的一个字符子序列,25,StrSubString示例,例如： StrSubString( sub, commander, 4, 3)求得 sub = man ； StrSubString( sub, commander, 1, 9)求得 sub = commander； StrSubString( sub, commander, 9, 1)求得 s

12、ub = r； StrSubString(sub, commander, 4, 7) sub = ? StrSubString(sub, beijing, 7, 2) sub = ? StrSubString(sub,student, 5, 0) sub= 长度为 0 的子串为“合法”串,26,StrIndex,StrIndex (S, T, pos)初始条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果： 若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。子串在主串中的位置“子串在主串中的位置”意指

13、子串中的第一个字符在主串中的位序。假设 S = abcaabcaaabc, T = bcaStrIndex(S, T, 1) = 2；StrIndex(S, T, 3) = 6；StrIndex(S, T, 8) = 0；,27,StrReplace,StrReplace (&S, T, V)初始条件：串S, T和 V 均已存在，且 T 是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。StrReplace例:假设 S = abcaabcaaabca，T = bca若 V = x， 则经置换后得到 S = axaxaax,28,StrInsert,StrInser

14、t (&S, pos, T)初始条件：串S和T存在， 1posStrLength(S)1。操作结果：在串S的第pos个字符之前插入串T。例如：S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = character,29,StrDelete,StrDelete (&S, pos, len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。,30,StrClear,StrClear (&S)初始条件：串S存在。操作结果：将S清为空串。,31,串类型,在上述抽象数据类型定义的1

15、3种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。,32,串类型,定位函数Index(S,T,pos)例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。算法的基本思想为：StrCompare(SubString(S, i, StrLength(T),T ) ? 0

16、,33,StrIndex,/* T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0 */int StrIndex (String S, String T, int pos) if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) StrSubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; return 0; /* S中不存在与T相等的子串 */ ,3

17、4,串与线性表的比较,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。,35,串的存储结构,对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。,36,串的存储结构,实现串名到串值的访问，在C语言中可以有两种方式：串的静态存储结构：将串定义为字符型数组，数组名就是串名，串的存储空

18、间分配在编译时完成，程序运行时不能更改。串的动态存储结构：定义字符指针变量，存储串值的首地址，通过字符指针变量名访问串值，串的存储空间分配是在程序运行时动态分配的。,37,串存储结构区别,静态存储采用顺序存储结构；动态存储采用的是链式存储和堆存储结构串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。,38,定长顺序存储表示,1.串的静态存储结构2.串的紧缩式存储3.串的顺序存储结构4.在静态存储方式中求子串,39,类似于线性表的顺序存储结构，用一

19、组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计算机的存储器地址是采用的字编址，一个字（即一个存储单元）占多个字节，因此顺序存储结构方式有两种：,串的静态存储结构,40,（1）紧缩格式：即一个字节存储一个字符。这种存储方式可以在一个存储单元中存放多个字符，充分地利用了存储空间。但在串的操作运算时，若要分离某一部分字符时，则变得非常麻烦。（2）非紧缩格式：这种方式是以一个存储单元为单位，每个存储单元仅存放一个字符。这种存储方式的空间利用率较低，如一个存储单元有4个字节，则空间利用率仅为25%。但这种存储方式中不需要分离字符，因而程序处理字符的速度高。,串的静态存储

20、结构,41,如图所示是以4个字节为一个存储单元的存储结构，每个存储单元可以存放4个字符。对于给定的串s=datastructure，在C语言中采用字符0作串值的结束符。串s的串值连同结束符的长度共15，只需4个存储单元。,串的紧缩式存储,42,串的定长顺序存储结构,类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256 char sMAXSIZE; 则串的最大长度不能超过256。 如何标识实际长度？,特殊字符作为串结束符,首字符存放串长度,指针标识,通常情况下有三种基本方法,43

21、,特殊字符作为串的终结符在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用0来表示串的结束。这种存储方法不能直接得到串长度，是用判断当前字符是否是0来确定串是否结束，的从而求得串的长度。char sMaxSize;,定长顺序存储终结符,图4.1 串的顺序存储方式1,44,类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：#define MaxSize typedef struct char strMaxSize ; int curlen; /*串长度*/ String; /* 串类型定义*/,定长顺序存储指针标识

22、,45,定义一个串变量：String s; s.data,定长顺序存储指针标识图示,图4.1 串的顺序存储方式2,这种存储方式可以直接得到串的长度：s.curlen+1。,46,设定长串存储空间：char sMAXSIZE+1; 用s0存放串的实际长度，串值存放在s1sMaxSize，字符的序号和存储位置一致，应用更为方便。,首字符存放串长度,在静态存储方式中求子串int SubStr(String s1, String *s2 , int start, int len) int j,k; j=s1.length; if(start j|len0) /*参数错误*/ (*s2).str0=0;

23、 (*s2).length=0; return FALSE; ,静态存储示例,k=strlen(s1.strstart -1) ;/*求子串的长度*/ if (lenk) (*s2).length=k; else (*s2).length=len; /*置子串的串长*/ for(j=0;j=(*s2).length;j+,m+) (*s2).strj=s1.strm-1; (*s2).strj=0;/*置结束标记*/ return TRUE; ,静态存储示例,49,堆分配存储表示,串的动态存储结构堆存储结构链式存储结构在链式存储方式中求子串串名的存储映象,50,串的动态存储结构,我们知道，串的

24、各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。串的动态存储方式采用两种形式: 链式存储结构 堆存储结构,51,堆存储结构特点,堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值长度相等的存储空间。,52,堆存储结构操作,在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如果分配成功，则

25、返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。用堆存放字符串时，其结构用C语言定义如下：typedef struct char *str; int length; HeapString;,53,链式存储结构,串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。用链表存放字符串时，其结构用C语言定义如下：typedef struct node char str; struct node *next; LinkStringType;,54,int substr(HeapString s1,

26、 HeapString *s2,int m,int n) HeapString *p,*q,*v; int length1,j; p= ,在链式存储方式中求子串,55,=s1.next ; for(j=0;jnext;/*找到子串和起始位置*/ s2=(slstrtype *)malloc(sizeof(slstrtype);/*分配子串和第一个结点*/ v=s2; q=v; for(j=0;jnext!=NULL;j+) /*建立子串*/ q-str=p-str; p=p-next; q=(slstrtype *)malloc(sizeof(slstrtype); v-next=q; v=q

27、; q-str=0; q-next=NULL; /*置子串和尾结点*/ return TRUE;,在链式存储方式中求子串,56,串名的存储映象,串名的存储映象就是建立了串名和串值之间的对应关系的一个符号表。在这个表中的项目可以依据实际需要来设置，以能方便地存取串值为原则。如：s1=data ；s2=structure假若一个单元仅存放1个字符，则上面两个串的串值顺序存储如图4-5所示。若符号表中每行包含有串名、串值的始地址、尾地址，则如图4-6（a）所示，也可以不设尾地址，而设置串和长度值。则如图4-6（b）所示。对于链式存储串值的方式，如果要建立串变量的符号表，则只需要存入一个链表的表头指针

28、即可。,57,块链存储结构,用单链表存放串，每个结点仅存储一个字符，如图4-3所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构。用块链存放字符串时，其结构用C语言定义如下：typedef struct nodechar str4;struct node *next; LinkStringType;,58,单字符链式存储结构,串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。用链表存放字符串时，其结构用C语言定义如下：typedef

29、struct node char str; struct node *next; LinkStringType;,59,3、串的模式匹配算法,串的模式匹配算法朴素的模式匹配无回溯匹配问题,60,串的模式匹配算法,模式匹配定义:子串的定位操作通常称做串的模式匹配。设有两个串s和t：s = s0s1sn-1；t = t0t1tm-1 ，其中1mn（通常有m n）。我们的任务是要在s中找出一个与t相同的子串。通常把s称为目标，把t称为模式。从目标s中查找与模式t完全相同的子串的过程叫作模式匹配。匹配结果有两种：如果s中存在等于t的子串，就指出该子串在s中的位置，称为匹配成功；否则称为匹配失败,函数值

30、为零。模式匹配通常有：朴素的模式匹配、无回溯匹配。,朴素的模式匹配思想,有两个串s和t：基本思想：先从主串s中的第一个字符起，截取模式串T的长度的子串，然后与模式串T中的字符逐个比较，其子串与模式串相同，即返回所截取子串的头一个字符位置作为查找的位置；否则，取S中的第二个字符为子串头，将其后的字符再依次与模式串T比较，判断是否相等，依次类推，直到找到位置或没有与模式串相同的子串为止，匹配成功，返回位置，否则，匹配失败，返回0。,62,朴素的模式匹配图示,设目标串以t“abbaba”和p“aba”为例，t的长度为n（n=6），p的长度为m（m=3）,63,朴素的模式匹配代码,int index(

31、String s,String t,int Start) int i=Start,j=0; /*初始化*/ while (istri=t-strj) i+; j+; /* 继续匹配下一个字符 */ else j = j - i + 1;i = 0; /* 主串、子串的i、j值回溯，重新开始下一次匹配 */ if (i=p-length) return( j - p-length + 1); /* 匹配成功，返回第一个字符序号 */ else return 0; /* 匹配失败 */ ,64,无回溯匹配问题,无回溯匹配问题的提出朴素的模式匹配有回溯，效率不高，因此我们希望找到无回溯的算法。为要找

32、到一个无回溯的匹配算法，关键在于一旦pi和tj比较不等，即：要能立即确定右移的位数和继续（无回溯的）比较的字符，也就是说应该用p中哪个字符和tj进行比较。,65,无回溯匹配算法的核心问题,一旦pi和tj比较不等,若p中字符pk应该和tj继续比较，显然ki，并且对不同的i，k值也不相同。Knuth等人发现这个k值仅依赖于模式p本身（前i个字符）的组成，而与目标t无关。用nexti表示与i对应的k值，其意义在于：若nexti，表示一旦匹配过程中pi与tj比较不等，可用p中以nexti为下标的字符与tj进行比较；若nexti-1，则表示p中任何字符都不必再与tj进行比较，下次比较从tj+1和p0开始

33、。无回溯算法的核心问题就是怎样计算next数组。,66,串操作应用举例,文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一般包括串的输入、查找、修改、删除、输出等。,67,文本编辑,例如有下列一段源程序：main() int a,b,c; gggggggscanf(%d,%d, 我们把这个源程序看成是一个文本，为了编辑的方便，总是利用换行符把文本

34、划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中，如表4-2所示（图中n表回车符）。,68,文本在内存中表示,表4-2,表4-3 行表及其信息排列,文本存储映象,在输入程序的同时，文本编辑程序先为文本串建立相应的页表和行表，即建立各子串的存储映象。串值存放在文本工作区，而将页号和该页中的起始行号存放在页表中，行号、串值的存储起始地址和串的长度记录在行表，由于使用了行表和页表，因此新的一页或一行可存放在文本工作区的任何一个自由区中，页表中的页号和行表中的行号是按递增的顺序排列的，如表

35、4-3所示。设程序的行号从110开始。,70,下面我们就来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。若插入行145，则行表中从150开始的各行信息必须向下平移一行。（2）删除一行时，则只要在行表中删除该行的行号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针和字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述，有兴趣的同学可设计其中的算法。,文本的编辑,