链式存储结构

数据结构讲义第四章串24.1串类型的定义4.2串的表示和实现4.3串的模式匹配算法4.4串操作应用举例第四章串31、串类型的定义串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作s=〃c0c1c2…cn-1〃(n≥0)其中：s为串名，用双引号括起来的字符序列是串的值；ci(0≤i≤n-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度；零个字符的串称为空串；仅由空格组成的的串称为空格串。4零个字符的串称为空串，通常以两个相邻的双引号来表示空串（Nullstring），如：s=〃〃，它的长度为零；仅由空格组成的的串称为空格串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=〃I’mastudent〃的长度为13。在C语言中，用单引号引起来的单个字符与单个字符的串是不同的，如s1=＇a＇与s2=〃a〃两者是不同的，s1表示字符，而s2表示字符串。空串与空格字符串5字符与字符串：称一个字符在串序列中的序号为该字符在串中的位置；当一个字符在串中多次出现时，以该字符第一次在字符串中出现的位置为该字符在串中的位置。子串与主串：子串：一个串的任意个连续的字符组成的子序列称为该串的子串；主串：包含子串的串称为主串。子串在主串中的位置是以子串的第一个字符在主串中的位置来表示的。两串串相等：称两个串是相等的，当且仅当这两个串的值相等。也即：两个串的长度相等，并且各个对应位置的字符都相等时才相等。字符相等意味着字符所对应的ascii值相等。主串和子串6串的基本操作定长顺序存储表示堆分配存储表示串的块链存储表示2、串的表示和实现7串基本操作C语言函数库串处理函数串的基本操作描述串与线性表的比较串的存储结构串的基本操作8串的基本操作分析：常规操作单串操作双串操作子串编辑操作索引操作串的基本操作9常规操作：字符串初始化：InitString字符串销毁：DestoryString单串操作：求字符串长度：StrLength:判断是否为空串：将给定字符串清空：双串操作：两个字符串是否相等；两个字符串复制；两个字符串连接；串的基本操作分析10子串编辑操作：查找给定的子串是否存在：查找给定的子串存在数量：索引操作：在某个位置开始插入某个字符串：StrInsert;在某个位置替换给定长度的子串：StrReplaceIndex；在某个位置删除给定长度的子串：StrDeleteIndex；自某位置开始取给定长度的子串：StrSubString串的基本操作分析11C语言函数库串处理函数对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。例如：C语言函数库中提供下列串处理函数：gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；c语言提供的关于字符串处理函数，其说明主要在“string.h”中。12C语言函数库串处理函数strcpy：将字符串src复制到destStrcat：将字符串src添加到dest末尾Strchr：检索并返回字符c在字符串s中第一次出现的位置Strcmp：字符串s1与s2的大小,并返回s1-s2strcpy：将字符串src复制到destStrcspn：扫描s1,返回在s1中有,在s2中也有的字符个数Strdup：将字符串s复制到最近建立的单元Strerror:本函数返回最近一次的错误信息,Stricmp:比较字符串s1和s2,并返回s1-s2strlen:返回字符串s的长度13C语言函数库串处理函数strlwr：字符串s中的大写字母全部转换成小写字母,并返回转换后的字符串strncat：将字符串src中最多maxlen个字符复制到字符串dest中strncmp：比较字符串s1与s2中的前maxlen个字符strncpy：复制src中的前maxlen个字符到dest中strnicmp：比较字符串s1与s2中的前maxlen个字符Strnset：将字符串s的前n个字符置于ch中strpbrk:扫描字符串s1,并返回在s1和s2中均有的字符个数Strrchr:扫描最后出现一个给定字符c的一个字符串sStrrev:将字符串s中的字符全部颠倒顺序重新排列,并返回排列后的字符串Strset:将一个字符串s中的所有字符置于一个给定的字符ch14C语言函数库串处理函数strspn:扫描字符串s1,并返回在s1和s2中均有的字符个数strstr:扫描字符串s2,并返回第一次出现s1的位置strtod:将字符串str转换成双精度数,并返回这个数,strtok:检索字符串s1,该字符串s1是由字符串s2中定义的定界符所分隔strtol:将字符串str转换成长整型数,并返回这个数,strupr:将字符串s中的小写字母全部转换成大写字母,并返回转换后的字符串串的基本操作StrAssignStrCopyStrDestroyStrEmptyStrCompareStrLengthStrConcatStrSubStringStrIndexStrReplaceStrInsertStrDeleteStrClear16StrAssignStrAssign(&T,chars)初始条件：chars是字符串常量。操作结果：把chars赋为T的值。17StrCopyStrCopy(&T,S)初始条件：串S存在。操作结果：由串S复制得串T。18StrDestroyStrDestroy(&S)初始条件：串S存在。操作结果：串S被销毁。19StrEmptyStrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。“”表示空串，空串的长度为零。20StrEmptyStrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE。“”表示空串，空串的长度为零。21StrCompareStrCompare(S,T)初始条件：串S和T存在。操作结果：若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCompare(data,state)0StrCompare(cat,case)022StrLengthStrLength(S)初始条件：串S存在。操作结果：返回S的元素个数,称为串的长度。23StrConcatStrConcat(&T,S1,S2)初始条件：串S1和S2存在。操作结果：用T返回由S1和S2联接而成的新串。例如：StrConcate(T,man,kind)求得T=mankind24StrSubStringStrSubString(&Sub,S,pos,len)初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。子串为“串”中的一个字符子序列25StrSubString示例例如：StrSubString(sub,commander,4,3)求得sub=man；StrSubString(sub,commander,1,9)求得sub=commander；StrSubString(sub,commander,9,1)求得sub=r；StrSubString(sub,commander,4,7)sub=?StrSubString(sub,beijing,7,2)sub=?StrSubString(sub,student,5,0)sub=长度为0的子串为“合法”串26StrIndexStrIndex(S,T,pos)初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。子串在主串中的位置“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。假设S=abcaabcaaabc,T=bcaStrIndex(S,T,1)=2；StrIndex(S,T,3)=6；StrIndex(S,T,8)=0；27StrReplaceStrReplace(&S,T,V)初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。StrReplace例:假设S=abcaabcaaabca，T=bca若V=x，则经置换后得到S=axaxaax28StrInsertStrInsert(&S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。操作结果：在串S的第pos个字符之前插入串T。例如：S=chater，T=rac，则执行StrInsert(S,4,T)之后得到S=character29StrDeleteStrDelete(&S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)-len+1。操作结果：从串S中删除第pos个字符起长度为len的子串。30StrClearStrClear(&S)初始条件：串S存在。操作结果：将S清为空串。31串类型在上述抽象数据类型定义的13种操作中，串赋值StrAssign、串复制Strcopy、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。32串类型定位函数Index(S,T,pos)例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。算法的基本思想为：StrCompare(SubString(S,i,StrLength(T)),T)?033StrIndex/*T为非空串。若主串S中第pos个字符之后存在与T相等的子串，则返回第一个这样的子串在S中的位置，否则返回0*/intStrIndex(StringS,StringT,intpos){if(pos0){n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1){StrSubString(sub,S,i,m);if(StrCompare(sub,T)!=0)++i;elsereturni;}}return0;/*S中不存在与T相等的子串*/}34串与线性表的比较串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。35串的存储结构对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。36串的存储结构实现串名到串值的访问，在C语言中可以有两种方式：串的静态存储结构：将串定义为字符型数组，数组名就是串名，串的存储空间分配在编译时完成，程序运行时不能更改。串的动态存储结构：定义字符指针变量，存储串值的首地址，通过字符指针变量名访问串值，串的存储空间分配是在程序运行时动态分配的。37串存储结构区别静态存储采用顺序存储结构；动态存储采用的是链式存储和堆存储结构串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大差别。在线性表的基本操作中，