文档介绍：本章主题:串的各种基本运算及其实现
教学目的:了解数据结构的基本概念,理解常用术语
教学重点:l  掌握串的基本概念及其基本运算
l 掌握串的存储结构
主要内容:
第4章串
2017/12/5
1
在计算机的应用中,非数值处理问题的应用越来越多。如在汇编程序和编译程序中,源程序和目标程序都是作为一种字符串数据进行处理的。在事务处理系统中,用户的姓名和地址及货物的名称、规格等也是字符串数据。
字符串一般简称为串,可以将它看作是一种特殊的线性表,这种线性表的数据元素的类型总是字符型的,字符串的数据对象约束为字符集。
在线性表的基本操作中,大多以“单个元素”作为操作对象,而在串中,则是以“串的整体”或一部分作为操作对象。因此,线性表和串的操作有很大的不同。
本章主要讨论串的基本概念、存储结构和一些基本的串处理操作。
本章学习导读
2017/12/5
2
串是一种特殊的线性表,它的数据对象是字符集合。
串的定义
串(或字符串)是由零个或多个字符组成的有限序列。一般记作: s=〃-1〃(n≥0)
其中:s为串名,用双引号括起来的字符序列是串的值;ci(0≤i≤n-1)可以是字母、数字或其它字符;双引号为串值的定界符,不是串的一部分;字符串字符的数目n称为串的长度。
零个字符的串称为空串,通常以两个相邻的双引号来表示空串
如:s=〃〃,它的长度为零;
仅由空格组成的的串称为空格串如:s=〃〃;
串及其运算
2017/12/5
3
若串中含有空格,在计算串长时,空格应计入串的长度中
如:s=〃I’m a student〃的长度为13。
注意:在C语言中,用单引号引起来的单个字符与单个字符的串是不同的, 如s1=‘a’与s2=〃a〃两者是不同的,s1表示字符,s2表示字符串。
当两个串的长度相等且各对应位置上的字符都相同时,这两个串是相等的。
串中任意个连续字符组成的序列称为该串的子串。包含子串的串被称为主串。
例如,"com"、"om"、"a"和"man"mander"的子串。子串在主串中的位置是指子串中第一个字符在主串中的位置序号。如子串"man"mander"中的位置为4。
2017/12/5
4
串是一种简单的数据结构,它的逻辑结构与线性表十分相似,区别仅在于串的数据对象是字符集。
串的基本运算与线性表的基本运算有很大差别。通常在串的基本运算中,以“串的整体”作为操作对象;而在线性表的基本运算中,大多以“单个元素”作为操作对象。
串的基本运算
串的常用基本运算主要有:
(s,chars)
功能:赋值运算将串常量chars的值赋给串变量s。
例如:执行strassign(s,"abcd")运算之后,s的值为"abcd"。
2017/12/5
5
(s,t)
功能:赋值运算。将串变量t的值赋给串变量s。
例如:t="abcd",则执行Assign(s,t)运算之后,s的值为"abcd"。
(s,t)
功能:判相等运算。若s与t的值相等则运算结果为1,否则为0。
(s)
功能:求串长运算。求串 s序列中字符的个数,即串的长度。
(s,t)
功能:联接运算。将串t的第一个字符紧接在串 s的最后一个字符之后,联接得到一个新串。例如s="man",t="kind",则执行Concat (s,t)运算后得到的新串为"mankind"。
2017/12/5
6
(s,pos, t)
功能:插入运算,当1≤pos ≤ Length (s)+1时,在串 s的第 pos 个字符之前插入串 t。
(s,pos,len)
功能:删除运算。当1≤pos≤Length(s)且0≤len≤Length (s)-pos+1时,从串s中删去从第pos个字符起长度为len的子串。
(s,pos,len,t)
功能:置换运算。当1≤pos≤Length (s)且0≤len≤Length(s)-pos+1时,用串t替换串s中从第 pos 个字符起长度为len的子串。
对于串的基本操作,许多高级语言均提供了相应的运算或标准库函数来实现。
下面仅介绍几种在C语言中常用的串运算,其它的串操作见文件。
2017/12/5
7
定义下列几个变量:
char s1[20]=“dirtreeformat”, s2[20]=“”;
char s3[30],*p;
int result;
(1)求串长(length)
int st