串、数组和广义表的概念和基本操作

1、串、数组和广义表的概念和基本操作学习目标：1.掌握串、空串、空格串、子串、主串、位置、两串相等的概念；了解串有哪些基本操作。 2.掌握数组的概念；理解数组的顺序存储的含义，掌握顺序存储的定位公式。3.掌握广义表的概念及其结构特点，了解广义表的递归算法。重点难点：串的概念，串的表示，矩阵的压缩存储。4.1 串类型的定义4.2 串的表示和实现5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储 教学内容内容回顾栈的特点及其表示实现队列的特点及其表示实现串和基本概念串(String):零个或多个字符组成的有限序列.如：S=a1a2a3an(n0),其中，S是串的名，单引号括起来的字符

2、序列是串的值；ai（1in）可以是字母、数字或其它字符，单引号本身不属于串,它的作用只是为了避免与变量名或数的常量混淆。串长(string length)：串中所包含的字符个数。 strLength(s)=n第四章 串空串(Empty String):0个字符的串，串的长度为零，它不包含任何字符,一个空串用 表示。空格串(Blank String)：由一个或多个空格组成的串。注意：空串和空格串的不同，例如 和分别表示长度为1的空格串和长度为0的空串。子串:串中任意个连续字符组成的子序列。主串:包含子串的串。如求 S=abc的子串？一个长度为n的串有多少个子串？子串在主串中的位置:以子串的第一个

3、字符在主串中的位置来表示.如：a,b,c,d分别为: a=BEI, b=JING, c=BEIJING, d=BEI JING, 长度分别为？子串？主串？子串在主串中的位置？称两个串是相等的，当且仅当这两个串的值相等，即只有当两个串的长度相等，并且各个对应位置的字符相等时才相等。注意：空串是任意串的子串，任意串是其自身的子串。串常量：和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。如：const char ch=“hello”，串变量：其取值是可以改变的。2.串的抽象数据类型的定义ADT String 数据对象：D ai |aiCharacterSet, i=1,2,.

4、,n, n0 数据关系：R1 | ai-1, ai D, i=2,.,n 串是有限长的字符序列，由一对单引号相括，如: a string 基本操作 StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos

5、, len) ClearString (&S) ADT String SubString (&Sub, S, pos, len)初始条件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。 基本操作例1： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 1, 9)求得 sub = commander； SubString( sub, commander, 9, 1

6、)求得 sub = r；子串为“串”中的一个字符子序列SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(sub，student, 5, 0) = 起始位置和子串长度之间存在约束关系0lenStrLength(S)-pos+1长度为 0 的子串为“合法”串Index (S, T, pos)初始条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出

7、现的位置； 否则函数值为0。 例2： S = abcaabcaaabc, T = bca Index(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0； “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。 Replace (&S, T, V) 初始条件：串S, T和 V 均已存在，且 T 是非空串。 操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。 例3：假设 S = abcaabcaaabca，T =bca若 V = x， 则经置换后得到 S = axaxaax若 V = bc，则经置换后得到 S = abc

8、abcaabc StrInsert (&S, pos, T)初始条件：串S和T存在， 1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例4：S = chater，T = rac， 则执行 StrInsert(S, 4, T)之后得到 S = character 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。 gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str

9、1, str2) 串比较函数； strlen(str) 求串长函数；例如：C语言函数库中提供下列串处理函数： 在上述抽象数据类型定义的13种操作中， 串赋值StrAssign、串比较StrCompare、 求串长StrLength、串联接Concat、 求子串SubString 等五种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清空ClearString和串销DestroyString 外）可在这个最小操作子集上实现。 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大

10、多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。 在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。3. 串的表示和实现 按这种串的表示方法实现串的运算时，其基本操作为 “字符序列的复制”。 用一组地址连续的存储单元存储串值的字符序 列，即按照预定义大小，为每一个定义的串变量分配一个固定长度的存储区。串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断” 。串的定长顺序存储表示导入 线性表、栈、队列、串：要求数据结构中的元素必须有相同的

11、属性，即数据类型；其中元素的数据类型只要相同即可，当然也可以就是一个数据结构。第五章 数组和广义表1、数组的定义数组：它是n（n1)个相同数据类型的数据元素a0,a1,a2,an-1构成的占用一块地址连续的内存单元的有限序列。注意：（1）C语言的数组定义下标从0开始。（2）数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。（3）一个二维数组可以看作每个数据元素是一个一维数组的一维数组。二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，C语言采用以行序为主序的方法存储。 数组逻辑上是线性结构的推广； 数组是以线性表为元素的线性

12、结 构，而且元素的结构相同； 数组可以看作是下标和值的偶对的集合； 数组是一种逻辑结构。 例1 高级语言中的数组int a10; a0 a1 a2 a3 a10-1char B45 B00 B01 B02 B03 B05-1B10 B11B15-1B20 B21B25-1二维数组int a23; 两个变量组成的一个数组，其中每一个变量都是数组。其中a0，a1都是数组的名字，也就是地址。一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。 a01a00a12a11a10a022.数组的抽象数据类型ADT Array 数据对象：ji=0,bi-1,i=1,2,n, D= aj1j2,j

13、n| n(0)称为数组的维数，bi是数组第i维 的长度, ji 是第i维的下标, aj1j2,jn| ElemSet 数据关系： 1jkbk,1kn且ki,1jibi-1 基本操作： InitArray(&A,n bound1,boundn) DestroyArray(&A) Value(A,index1,indexn) Assign(A,e,index1,indexn) ADT Array 数组一旦被定义，它的维数和维界就不再改变，因此除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。3.数组的顺序表示和实现 数组一般不做插入和删除操作 ,因此采用顺序存储结构表示数组是自然的事

14、了，数组顺序存储时，必须确定按行序或列序存储： （1） PASCAL、C 以行序为主存储 （2）FORTRAN 以列序为主存储a11 a12 a1n a21 a22 a2n am1 am2 amn a11 a21 am1 a12 a22 am2 a1n a2n amn 以行为主序 以列为主序例如： 称为基地址或基址。以“行序为主序”的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j) = LOC(0,0) + (b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 例2：设数组a67的基地址为2000，每个元素占2个存

15、储单元，若以行序为主序顺序存储，则元素a5,6的存储地址为 。答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)得：LOC(a5,6)=2000+(5*7+6)*22082注：只要知道以下三要素便可随时求出任一元素的地址（意义：数组中的任一元素可随机存取）开始结点的存放地址（即基地址）；维数和每维的上、下界；每个数组元素所占用的单元数例3 一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是 个字节。288答：Volume=m*n*L=(6-1+1)*(7- 0 +1)

16、*6 =48*6=2884.矩阵的压缩存储当矩阵的阶数较高，而且矩阵中的一些元素有特殊的性质时，可以采用节省空间的存储办法（压缩存储） 两类矩阵： 特殊矩阵：值相同的元素或非零元素分布有一定的规律； 稀疏矩阵：非零元素少且分布无规律；特殊矩阵对称矩阵 若n阶矩阵A中的元素满足下述性质 aij=aji 1i , jn 则称A为n阶对称矩阵 a11 a21 a22 a31 an1 ann k= 0 1 2 3 n2个元素可以压缩到n(n+1)/2个空间中；以行序为主序将其下三角（包括对角线）中的元素存储到一个向量Bn(n+1)/2中: 向量Bk和矩阵中的元素aij之间存在着一一对应关系： 下面按下

17、标从0开始讨论。 特殊矩阵（对称矩阵）向量Bk和矩阵中的元素aij之间的关系：由i和j推导k：特殊矩阵（三角矩阵 ）三角矩阵 : 下(上)三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元素均为常数c或零的n阶矩阵 下（上）三角矩阵的存储公式除了和对称矩阵一样，只存储其下（上）三角中元之外，再加上一个存储常数c的存储空间即可。 注意：上（下）三角矩阵的下（上）三角部分，可以全是0，也可以全是常数c.对角矩阵 :所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，所有其它的元素均为零。 特殊矩阵（对角矩阵 ）b条对角线n行n列(a)

18、a11 a12 a21 a22 a23 an-1,n an,n an,n-1 OO(b)三对角矩阵a00 a01 a10 a11 a12 an-1,n an,n an,n-1 OO 三对角矩阵:共3(n+1)-2个非零元素，存入B3n+1中,元素在一维数组B中的下标k和元素在矩阵中的下标i和j的对应关系为： k = 3i-1 (主对角线左下角，即i=j+1) k = 3i (主对角线，即i=j) k = 3i+1(主对角线右上角，即i=j-1) 由以上三式，得 k=2i+j (0i,jn; 0k3n) 稀疏矩阵非零元素较少，分布无规律 假设 m 行 n 列的矩阵含 t 个非零元素，稀疏因子：

19、= t/(m*n) = 0.05 存储结构 顺序存储结构三元组表（行，列，值）链式存储结构十字链表 ije 1 2 6 1 6 -2 3 4 -8 4 2 3 4 6 7 5 1 -12 5 3 9 例子：三元组表示稀疏矩阵: 十字链表十字链表中非零元结点的结构 :row col e down right 0 0 next down right row col next 元素结点行列表头总表头结点十字链表的结构类型typedef struct OLNode int i , j; ElemType e; struct OLNode *down, *right; OLNode;*OLink; ty

20、pedef struct OLink *rhead, *chead ; /行、列链表头指针 int mu, nu , tu ; CrossList;3 0 0 50 -1 0 02 0 0 011314522-1312思考：数组与线性表的区别与联系相同之处：它们都是若干个相同数据类型的数据元素a0,a1,a2,，an-1构成的有限序列。不同之处：(1)数组要求其元素占用一块地址连续的内存单元空间，而线性表无此要求；(2)线性表的元素是逻辑意义上不可再分的元素，而数组中的每个元素还可以是一个数组；(3)数组的操作主要是向某个下标的数组元素中存放数据和取某个下标的数组元素，这与线性表的插入和删除操

21、作不同。广义表的定义广义表是由零个或多个原子或子表组成的有限序列，是线性表的推广 广义表的概念广义表般记作： LS(d1，d2，dn) LS是广义表(d1，d2，dn)的名称，n是它的长度。di可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。 用大写字母表示广义表的名称，用小写字母表示原子 当广义表LS非空时，称第一个元素d1为LS的表头(Head)，称其余元素组成的子表(d2，dn)是LS的表尾(Tail) 非空广义表可唯一分解成表头和表尾；反过来，由表头和表尾可唯一组成一个广义表 广义表括号的层数定义为广义表的深度。广义表举例A=( ) A是一个空表，它的长度为零 B=(e

22、,f) B有两个原子e,f，B的长度为2 C=(a,(b,c) C有一个原子a和一个子表(b,c)，C的长度为2 D=(B,A,C) D有三个子表B、A、C，D的长度为3 E=(a,E) E是一个递归的表，E的长度为2，E相当于一个无限的表(a,(a,(a,) 广义表是一个多层次的线性结构例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( )d( )bce广义表 LS = ( 1, 2, , n )的结构特点:1) 广义表中的数据元素有相对次序；2) 广义表的长度定义为最外层包含元素个数；3) 广义表的深度定义为所含括弧的重数； 注意：“原子”的深度为 0 “

23、空表”的深度为 1 4) 广义表可以共享；5) 广义表可以是一个递归的表。 递归表的深度是无穷值，长度是有限值。6) 任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为 表头 Head(LS) = 1 和 表尾 Tail(LS) = ( 2, , n) 两部分。例如: D = ( E, F ) = (a, (b, c)，F )Head( D ) = E Tail( D ) = ( F )Head( E ) = a Tail( E ) = ( ( b, c) )Head( ( b, c) ) = ( b, c) Tail( ( b, c) ) = ( )Head( ( b, c) ) = b Tail( ( b, c) ) = ( c )Head( ( c ) ) = c Tail( ( c ) ) = ( )求下列广义表操作的结果 GetHead( (a,b,c)