《《数据结构——C语言描述（第二版）》-王路群-电子教案 第四章 串》由会员分享，可在线阅读，更多相关《《数据结构——C语言描述（第二版）》-王路群-电子教案 第四章 串（24页珍藏版）》请在金锄头文库上搜索。
1、第四章 串,教学要求 1掌握：串的定义及基本运算。 2掌握：串的静态存储结构和动态存储结构，以及它们的基本运算的算法实现。 3了解：串的基本运算完成简单的文本输入和输出。,主要内容,4.1 串的基本概念 4.2 串的存储结构 4.3 串的基本运算及其实现 4.4 文本编辑 4.5 实训,4.1 串的基本概念,串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=c0c1c2cn-1 (n0) 其中：s为串名，用双引号括起来的字符序列是串的值；ci(0in-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。零个字符的串称
2、为空串，通常以两个相邻的双引号来表示空串（Null string），如：s=，它的长度为零；仅由空格组成的的串称为空格串，如：s=；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=Im a student的长度为13。 请读者注意，在C语言中，用单引号引起来的单个字符与单个字符的串是不同的， 如s1=a与s2=a两者是不同的，s1表示字符，而s2表示字符串。,4.1.1 串的定义,4.1.2 主串和子串 一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。称一个字符在串序列中的序号为该字符在串中的位置，子串在主串中的位置是以子串的第一个字符在主串中的位置来表
3、示的。当一个字符在串中多次出现时，以该字符第一次在主串中出现的位置为该字符在串中的位置。 例如：s1、s2、s3为如下的三个串：s1=Im a student;s2=student;s3=teacher。 则它们的长度分别为13、7、7；串s3是s1的子串，子串s3在s1中的位置为7，也可以说s1是s3的主串；串s2不是s1的子串，串s2和s3不相等。,4.2 串的存储结构 对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。实
4、现串名到串值的访问，在C语言中可以有两种方式：一是可以将串定义为字符型数组，数组名就是串名，串的存储空间分配在编译时完成，程序运行时不能更改。这种方式为串的静态存储结构。另一种是定义字符指针变量，存储串值的首地址，通过字符指针变量名访问串值，串的存储空间分配是在程序运行时动态分配的，这种方式称为串的动态存储结构。,4.2.1 串值的存储 我们称串是一种特殊的线性表，因此串的存储结构表示也有两种方法：静态存储采用顺序存储结构，动态存储采用的是链式存储和堆存储结构。,1串的静态存储结构 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。由于一个字符只占1个字节，而现在大多数计
5、算机的存储器地址是采用的字编址，一个字（即一个存储单元）占多个字节，因此顺序存储结构方式有两种： （1）紧缩格式：即一个字节存储一个字符。这种存储方式可以在一个存储单元中存放多个字符，充分地利用了存储空间。但在串的操作运算时，若要分离某一部分字符时，则变得非常麻烦。,图4-1 串值的紧缩格式存储,图4-1所示是以4个字节为一个存储单元的存储结构，每个存储单元可以存放4个字符。对于给定的串s=datastructure，在C语言中采用字符0作串值的结束符。串s的串值连同结束符的长度共15，只需4个存储单元。,图4-1 串值的紧缩格式存储,用字符数组存放字符串时，其结构用C语言定义如下： #def
6、ine MAXNUM typedef struct char strMAXNUM; int length; /*串长度*/ stringtype; /* 串类型定义*/ 由上述讨论可知，串的顺序存储结构有两大不足之处：一是需事先预定义串的最大长度，这在程序运行前是很难估计的。二是由于定义了串的最大长度，使得串的某些操作受限，如串的联接运算等。,图4-2 串值的非紧缩格式存储,（2）非紧缩格式：这种方式是以一个存储单元为单位，每个存储单元仅存放一个字符。这种存储方式的空间利用率较低，如一个存储单元有4个字节，则空间利用率仅为25%。但这种存储方式中不需要分离字符，因而程序处理字符的速度高。图4-
7、2即为这种结构的示意图。,2串的动态存储结构 我们知道，串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。 串的动态存储方式采用链式存储结构和堆存储结构两种形式： （1）链式存储结构 串的链式存储结构中每个结点包含字符域和结点链接指针域，字符域用于存放字符，指针域用于存放指向下一个结点的指针，因此，串可用单链表表示。 用链表存放字符串时，其结构用C语言定义如下： typedef struct node char str; struct node *next; slstrtype
8、; 用单链表存放串，每个结点仅存储一个字符，如图4-3所示，因此，每个结点的指针域所占空间比字符域所占空间要大得多。为了提高空间的利用率，我们可以使每个结点存放多个字符，称为块链结构，如图4-4所示每个结点存放4个字符。,用块链存放字符串时，其结构用C语言定义如下： typedef struct node char str4; struct node *next; slstrtype; （2）堆存储结构 堆存储结构的特点是，仍以一组空间足够大的、地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。每当产生一个新串时，系统就从剩余空间的起始处为串值分配一个长度和串值
9、长度相等的存储空间。 在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc()分配一块实际串长所需的存储空间，如果分配成功，则返回这段空间的起始地址，作为串的基址。由free()释放串不再需要的空间。 用堆存放字符串时，其结构用C语言定义如下： typedef struct char *str; int length; HSstrtype;,4.2.2 串名的存储映象 串名的存储映象就是建立了串名和串值之间的对应关系的一个符号表。在这个表中的项目可以依据实际需要来设置，以能方便地存取串值为原则。 如： s1=data s2=structure 假若一个单元仅存放1个字符，则上面
10、两个串的串值顺序存储如图4-5所示。 若符号表中每行包含有串名、串值的始地址、尾地址，则如图4-6（a）所示，也可以不设尾地址，而设置串和长度值。则如图4-6（b）所示。,对于链式存储串值的方式，如果要建立串变量的符号表，则只需要存入一个链表的表头指针即可。,4.3 串的基本运算及其实现 串的基本运算有赋值、联接、求串长、求子串、求子串在主串中出现的位置、判断两个串是否相等、删除子串等。在本节中，我们尽可能以C语言的库函数表示其中的一些运算，若没有库函数，则用自定义函数说明。,4.3.1 串的基本运算 （1）strcpy(str1,str2) 字符串拷贝（赋值）：把str2指向的字符串拷贝到s
11、tr1中，返回str1。库函数和形参说明如下： char * strcpy(char * str1,char * str2) （2）strcat(str1,str2) 字符串的联接：把字符串str2接到str1后面，str1最后的结尾符0被取消。返回str1。库函数和形参说明如下： char * strcat(char * str1,char * str2) （3）strlen(str) 求字符串的长度：统计字符串str中字符的个数（不包括0），返回字符的个数，若str为空串，则返回值为0。库函数和形参说明如下： unsigned int strlen(char *str) （4）strstr
12、(str1,str2) 子串的查询：找出子串str2在主串str1第一次出现的位置（不包括子串str2的结尾符），返回该位置的指针，若找不到，返回空指针NULL。库函数和形参说明,如下： char * strstr(char * str1,char * str2) （5）strcmp(str1,str2) 字符串的比较：比较两个字符串str1、str2。若str1str2，则返回负数；若str1str2，则返回正数；若str1str2，则返回0。库函数和形参说明如下： int strcmp(char * str1,char * str2) （6）substr(str1,str2,m,n) 求子
13、串：在字符串str1中，从第m个字符开始，取n个长度的子串str2；若mstrlen(str)或n0，则返回空值NULL。自定义函数和形参说明如下： int strstr(char * str1,char *str2,int m,int n) （7）delstr(str,m,n) 字符串的删除：在字符串str中，删除从第m个字符开始的n个长度的子串。自定义函数和形参说明如下： Void delstr(char *str,int m,int n) （8）Insstr(str1,m,str2 ) 字符串的插入：在字符串str1第m个位置之前开始，插入字符串str2。返回str1。自定义函数和形参说
14、明如下： Void insstr(char *str1,int m,char *str2) 对字符串的置换可以通过求串长，删除子串，字符串的联接等基本运算来实现。,4.3.2 串的基本运算及其实现 本小节中，我们将讨论串值在静态存储方式和动态存储方式下，其运算如何实现。 如前所述，串的存储可以是静态的，也可以是动态的。静态存储在程序编译时就分配了存储空间，而动态存储只能在程序执行时才分配存储空间。不论在哪种方式下，都能实现串的基本运算。本节讨论求子串运算在三种存储方式下的实现方法。,1在静态存储结构方式下求子串 C语言中用字符数组存储字符串时，结构定义如下： #define MAXNUM 80
15、 typedef struct char strMAXNUM; int length; /*串长度*/ stringtype; /* 串类型定义*/ 求主串s1中第m个字符起，长度为n的子串s2，若存在子串s2，则返回TRUE； 若mstrlen(s1)或m1或n0，则返回FALSE。算法如下,【算法4-1 在静态存储方式中求子串】 int substr(stringtype s1,stringtype * s2,int m,int n) int j,k;j=s1.length; if(mj|nk) (*s2).length=k; else (*s2).length=n; /*置子串的串长*/
16、 for(j=0;j=(*s2).length;j+,m+) (*s2).strj=s1.strm-1; (*s2).strj=0;/*置结束标记*/ return TRUE; 上述算法中使用数组存放字符串，串长用显式方式给出。,2在动态存储结构方式下求子串 （1）在链式存储结构方式下 假设链表中每个结点仅存放一个字符，则单链表定义如下 typedet struct node char str; struct node *next; slstrtype; 求子串运算的算法如下：,【算法4-2 在链式存储方式中求子串】 int substr(slstrtype s1,slstrtype *s2,int m,int n) slstrtype *p,*q,*v; int length1,j; p= ,（2）在堆存储结构方式下 堆存储结
