武汉理工大学-信息工程学院-数据结构-ppt-课件ch04-1-串1

第4章串数据结构讲义信息工程学院魏洪涛Email:[e-mail]4.1串的类型定义串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3…an”其中S是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串，它不包含任何字符，注意与空格串不同。串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为A=“Thisisastring”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。串的基本操作1.串复制StrCpy(&S,T)2.联接Concat(&S,T1,T2)3.求串长度StrLen(T)4.子串SubString(&S,T,i,len)5.串比较大小StrCmp(S,T)6.串插入SInsert(&S,i,T)7.串删除SDelete(&S,i,len)8.求子串位置Index(S,T)9.串替换Replace(&S,T,V)C语言中串操作的实现定义下列几个变量：chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;(1)求串长(length)intstrlen(char*s);//求串的长度例如：printf(“%d”,strlen(s1));输出13(2)串复制(copy)char*strcpy(char*to,char*from);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcpy(s3,s1);//s3=“dirtreeformat”(3)联接(concatenation)charstrcat(char*to,char*from)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。例如：strcat(s3,”/”)strcat(s3,s2);//s3=“dirtreeformat/file.mem”(4)串比较（compare)intstrcmp(char*s1,char*s2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2、s1=s2或s1s2例如：result=strcmp(“baker”,”Baker”)result0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result0(5)字符定位(index)charstrchr(char*s,charc);该函数是找字符c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,’.’);p指向“file”之后的位置s2=“file.cpp”4.2串的表示与实现C语言中定长顺序存储的实现串的顺序存储演示ch4_sstring.c堆分配存储表示仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。typedefstruct{char*ch;intlength;}HSring;串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedefstructnode{chardata;structnode*next;}lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小．要用特殊字符来填充最后一个结点，以表示串的终结。#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}lstring;作业实现intStrLength(char*s1)–返回串s的长度。实现StrCompare(char*s1,char*s2)。–比较两个串的第一个字符的ASCII码，如果第1个串的字符大于第2个串的字符，则返回1，反之则返回-1。如果相等，则继续比较下一个字符。可参考P77。实现StrInsert(char*s,intpos,char*t)–在串s的第pos个字符之前插入串t。直接实现或者利用StrLength(),SubString()和Concat()。