【精品数据结构课件】串.pptVIP

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