文档详情

9串数组和广义表.pptx

发布:2020-02-23约2.72千字共62页下载文档
文本预览下载声明
串、数组和广义表;4.1 串类型的定义 4.2 串的表示和实现 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4广义表的定义 ;内容回顾;串和基本概念 串(String):零个或多个字符组成的有限序列.如:S=‘a1a2a3…an’(n≥0),其中,S是串的名,单引号括起来的字符序列是串的值;ai(1≤i≤n)可以是字母、数字或其它字符,单引号本身不属于串,它的作用只是为了避免与变量名或数的常量混淆。 串长(string length):串中所包含的字符个数。 strLength(s)=n ;空串(Empty String):0个字符的串,串的长度??零,它不包含任何字符,一个空串用 ¢ 表示。 空格串(Blank String):由一个或多个空格组成的串。 注意:空串和空格串的不同,例如’ ’和’’分别表示长度为1的空格串和长度为0的空串。;子串:串中任意个连续字符组成的子序列。 主串:包含子串的串。 如求 S=‘abc’的子串? 一个长度为n的串有多少个子串? 子串在主串中的位置:以子串的第一个字符在主串中的位置来表示.如:a,b,c,d分别为: a=‘BEI’, b=‘JING’, c=‘BEIJING’, d=‘BEI JING’, 长度分别为?子串?主串?子串在主串中的位置? ;称两个串是相等的,当且仅当这两个串的值相等,即只有当两个串的长度相等,并且各个对应位置的字符相等时才相等。 注意:空串是任意串的子串,任意串是其自身的子串。 串常量:和整常数、实常数一样,在程序中只能被引用但不能改变其值,即只能读不能写。如:const char ch[]=“hello”,串变量:其取值是可以改变的。;2.串的抽象数据类型的定义; 基本操作; ;例1: SubString( sub, ?commander?, 4, 3) 求得 sub = ?man? ; SubString( sub, ?commander?, 1, 9) 求得 sub = ?commander?; SubString( sub, ?commander?, 9, 1) 求得 sub = ?r?;;SubString(sub, ?commander?, 4, 7) sub = ? ;Index (S, T, pos) 初始条件:串S和T存在,T是非空串, 1≤pos≤StrLength(S)。 操作结果: 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置; 否则函数值为0。 ;例2: S = ?abcaabcaaabc?, T = ?bca? ; Replace (S, T, V) 初始条件:串S, T和 V 均已存在,且 T 是非空串。 操作结果:用V替换主串S中出现的所有与(模式串)T相等的不重叠的子串。 ;例3:; StrInsert (S, pos, T) 初始条件:串S和T存在, 1≤pos≤StrLength(S)+1。 操作结果:在串S的第pos个字符之前 插入串T。;; 在上述抽象数据类型定义的13种操作中, 串赋值StrAssign、串比较StrCompare、 求串长StrLength、串联接Concat、 求子串SubString 等五种操作构成串类型的最小操作子集。 即:这些操作不可能利用其他串操作来实现,反之,其他串操作(除串清空ClearString和串销DestroyString 外)可在这个最小操作子集上实现。; 串的逻辑结构和线性表极为相似,区别 仅在于串的数据对象约束为字符集。; 在程序设计语言中,串只是作为输入或输出的常量出现,则只需存储此串的串值,即字符序列即可。但在多数非数值处理的程序中,串也以变量的形式出现。; 按这种串的表示方法实现串的运算时,其基本操作为 “字符序列的复制”。;导入 ;1、数组的定义   数组:它是n(n1)个相同数据类型的数据元素a0,a1,a2,…an-1构成的占用一块地址连续的内存单元的有限序列。 注意: (1)C语言的数组定义下标从0开始。 (2)数组元素的下标一般具有固定的上界和下界,即数组一旦被定义,它的维数和维界就不再改变。 (3)一个二维数组可以看作每个数据元素是一个一维数组的 一维数组。二维数组是两维的,内存单元是一维的,存在向内存存储时二维数组中数
显示全部
相似文档