9串数组和广义表.pptx
文本预览下载声明
串、数组和广义表;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)一个二维数组可以看作每个数据元素是一个一维数组的
一维数组。二维数组是两维的,内存单元是一维的,存在向内存存储时二维数组中数
显示全部