数据结构2第4章幻灯片.ppt

习 题 四 1．简述空串与空格串、串变量与串常量、主串与子串、串名与串值每对术语的区别？ 2．两个字符串相等的充要条件是什么？ 3．串有哪几种存储结构？ 4．已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。 5．已知：s1=〃I’m a student〃，s2=〃student〃，s3=〃teacher〃，试求下列各运算的结果： strstr(s1,s2)； strlen(s1)； strcat(s2,s3)； delstr(s1,4,10)； 6．设s1=”AB”，s2=”ABCD”，s3=”EFGHIJK，试画出堆存储结构下的存储映象图。 7．试写出将字符串s2中的全部字符拷贝到字符串s1中的算法，不允许利用库函数strcpy()。 8．设s1和s2是用结点大小为1的单链表表示的串，试写出找出s2中第一个不在s1中出现的字符的算法。 9．设字符串采用块链存储结构，块链中每个结点存放m（m=4）个字符，试写出实现字符串删除的算法。 ? 1 串的基本概念 2 串的存储结构 3 串基本操作的实现 5 串的应用-文本编辑 第四章 串 4 串的模式匹配算法 在计算机的各方面应用中，非数值处理问题的应用越来越多。如在汇编程序和编译程序中，源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中，用户的姓名和地址及货物的名称、规格等也是字符串数据。 字符串一般简称为串，可以将它看作是一种特殊的线性表，这种线性表的数据元素的类型总是字符型的，字符串的数据对象约束为字符集。在一般线性表的基本操作中，大多以“单个元素”作为操作对象，而在串中，则是以“串的整体”或一部分作为操作对象。因此，一般线性表和串的操作有很大的不同。本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。 4.1 串的基本概念 4.1.1 串的定义 串（或字符串）（String）是由零个或多个字符组成的有限序列。一般记作 s=〃s0s1s2…sn-1〃 (n≥0) 其中：s为串名，用双引号括起来的字符序列是串的值；si(0≤i≤n-1)可以是字母、数字或其它字符；双引号为串值的定界符，不是串的一部分；字符串字符的数目n称为串的长度。零个字符的串称为空串，通常以两个相邻的双引号来表示空串，如：s=〃〃，它的长度为零；仅由空格组成的的串称为空格串，如：s=〃└┘〃；若串中含有空格，在计算串长时，空格应计入串的长度中，如：s=〃I’m a student〃的长度为13。 请读者注意，在C语言中，用单引号引起来的单个字符与单个字符的串是不同的， 如s1=＇a＇与s2=〃a〃两者是不同的，s1表示字符，而s2表示字符串。 4.1.2 串的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result; （1）串复制 Assign(s,t) strcpy(str1,str2) （赋值）：把str2指向的字符串拷贝到str1中，返回str1。库函数和形参说明如下： char * strcpy(char * str1,char * str2) 例如：strcpy(s3,s1); //s3=“dirtreeformat” (2) 求串长 length(s) strlen(str) 求字符串的长度：统计字符串str中字符的个数（不包括 ＇\0＇），返回字符的个数，若str为空串，则返回值为0。库函数和形参说明如下： unsigned int strlen(char *str) 例如：printf(“%d”,strlen(s1)); 输出13 (3)串比较 equal(s,t) c函数：int strcmp(char s1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2\s1=s2或s1s2 例如：result=strcmp(“baker”,”Baker”) result0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result0 (4)联接 concat(s,t) char strcat(char