串数组和广义表.pptx

《串数组和广义表.pptx》由会员分享，可在线阅读，更多相关《串数组和广义表.pptx（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 串类型的定义串类型的定义4.2 串的表示和实现串的表示和实现5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储5.4广义表的定义广义表的定义 教学内容第1页/共62页内容回顾栈栈的的特点及其特点及其表示实现表示实现队列队列的的特点及其特点及其表示实现表示实现第2页/共62页1.1.串和基本概念串和基本概念v串串(String):(String):零个或多个字符组成的有限零个或多个字符组成的有限序列序列.如：如：S=S=a a1 1a a2 2a a3 3a an n(n n0),0),其中，其中，S S是是串的名，单引号括起

2、来的字符序列是串的值；串的名，单引号括起来的字符序列是串的值；a ai i（1in1in）可以是字母、数字或其它字符，）可以是字母、数字或其它字符，单引号本身不属于串单引号本身不属于串,它的作用只是为了避免它的作用只是为了避免与变量名或数的常量混淆。与变量名或数的常量混淆。v串长串长(string length)(string length)：串中所包含串中所包含的字符个数。的字符个数。strLength(s)=nstrLength(s)=n第四章第四章 串串第3页/共62页v空串空串(Empty String):(Empty String):0 0个字符的串，个字符的串，串的长度为零，它不包

3、含任何字符串的长度为零，它不包含任何字符,一个空串用一个空串用 表示。表示。v空格串空格串(Blank String)(Blank String)：由一个或多由一个或多个空格组成的串。个空格组成的串。注意：注意：空串和空格串的不同，例如空串和空格串的不同，例如 和和分别表示长度为分别表示长度为1 1的空格串和长度为的空格串和长度为0 0的空的空串。串。第4页/共62页v子串子串:串中串中任意个连续任意个连续字符组成的子序列。字符组成的子序列。v主串主串:包含子串的串。包含子串的串。如求如求 S=S=abcabc的子串？的子串？一个长度为一个长度为n n的串有多少个子串？的串有多少个子串？v子串

4、在主串中的位置子串在主串中的位置:以子串的第一个字符在主串中的位置来表示以子串的第一个字符在主串中的位置来表示.如：如：a,b,c,da,b,c,d分别为分别为:a=a=BEIBEI,b=,b=JINGJING,c=,c=BEIJINGBEIJING,d=,d=BEI JINGBEI JING,长度分别为？子串？主串？子串在主串中的位置？长度分别为？子串？主串？子串在主串中的位置？第5页/共62页v称两个串是相等的称两个串是相等的，当且仅当这两个串的值相等，即只有当两个串的，当且仅当这两个串的值相等，即只有当两个串的长度相等长度相等，并且并且各个对应位置的字符相等各个对应位置的字符相等时才相等

5、。时才相等。注意：注意：空串是任意串的子串，任意串是其自身的子串。空串是任意串的子串，任意串是其自身的子串。v串常量：串常量：和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只和整常数、实常数一样，在程序中只能被引用但不能改变其值，即只能读不能写。如：能读不能写。如：const char ch=const char ch=“hellohello”，串变量：其取值是可以改，串变量：其取值是可以改变的。变的。第6页/共62页2.串的抽象数据类型的定义串的抽象数据类型的定义ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据

6、关系：R1|ai-1,ai D,i=2,.,n 串是有限长的字符序串是有限长的字符序列，由一对单引号相列，由一对单引号相括，如括，如:a string 第7页/共62页 基本操作基本操作 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,len)ClearStri

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

8、得 sub=r；子串为子串为“串串”中的一个字符子序列中的一个字符子序列第10页/共62页SubString(sub,commander,4,7)sub=?SubString(sub,beijing,7,2)=?sub=?SubString(sub，student,5,0)=起始位置和子串长度之间存在约束关系起始位置和子串长度之间存在约束关系0lenStrLength(S)-pos+1长度为长度为 0 的子串为的子串为“合法合法”串串第11页/共62页Index(S,T,pos)初始初始条件：条件：串串S和和T存在，存在，T是非空串，是非空串，1posStrLength(S)。操作结果：操作结

9、果：若主串若主串 S 中存在和串中存在和串 T 值相同值相同 的子串的子串,则返回它在主串则返回它在主串 S 中第中第pos个个 字符之后第一次出现的位置；字符之后第一次出现的位置；否则函数值为否则函数值为0。第12页/共62页例2：S=abcaabcaaabc,T=bca Index(S,T,1)=2；Index(S,T,3)=6；Index(S,T,8)=0；“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。第13页/共62页 Replace(&S,T,V)初始条件：初始条件：串串S,T和和 V 均已存在，且均已存在，且 T 是非空串。是非空串。操作结果：操

10、作结果：用用V替换主串替换主串S中出现的所中出现的所有与（模式串）有与（模式串）T相等的不重叠的子串。相等的不重叠的子串。第14页/共62页例例3 3：假设 S=abcaabcaaabca，T=bca若 V=x，则经置换后得到 S=axaxaax若 V=bc，则经置换后得到 S=abcabcaabc第15页/共62页 StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符之前 插入串T。例例4：S=chater，T=rac，则执行 StrInsert(S,4,T)之后得到 S=character第16页/共62页 对于

11、串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准以该语言的参考手册为准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,str2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：第17页/共62页 在上述抽象数据类型定义的13种操作中，串赋值串赋值StrAssignStrAssign、串比较、串比较StrCompareStrCompare、求串长求串长StrLengthStrLe

12、ngth、串联接、串联接ConcatConcat、求子串求子串SubString SubString 等五种操作构成串等五种操作构成串类型的最小操作子集类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串操作（除串清空ClearString和串销DestroyString 外）可在这个最小操作子集上实现。第18页/共62页 串的逻辑结构和线性表极为相似，区别串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为仅在于串的数据对象约束为字符集字符集。串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以在线性表的基本操作中，大多以“单

13、个单个元素元素”作为操作对象；作为操作对象；在串的基本操作中，通常以在串的基本操作中，通常以“串的整体串的整体”作为操作对象。作为操作对象。第19页/共62页 在程序设计语言中，串只是作在程序设计语言中，串只是作为输入或输出的常量出现，则只需存为输入或输出的常量出现，则只需存储此串的储此串的串值串值，即字符序列即可。但，即字符序列即可。但在多数非数值处理的程序中，串也以在多数非数值处理的程序中，串也以变量的形式出现。变量的形式出现。3.串的表示和实现串的表示和实现第20页/共62页 按这种串的表示方法实现串的运算时，其基本操作为“字符序列的复制字符序列的复制”。用一组地址连续的存储单元存储串值

14、用一组地址连续的存储单元存储串值的字符序的字符序 列，即按照预定义大小，为每列，即按照预定义大小，为每一个定义的串变量分配一个一个定义的串变量分配一个固定长度的存固定长度的存储区储区。串。串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断截断”。串的定长顺序存储表示串的定长顺序存储表示第21页/共62页导入导入 线性表、栈、队列、串：要求数据线性表、栈、队列、串：要求数据结构中的元素必须有结构中的元素必须有相同的属性，即相同的属性，即数据类型；数据类型；其中元素的数据类型只要其中元素的数据类型只要相同即可，当然也可以就是一个相同即可，当然也可以就是一个数

15、据数据结构。结构。第五章第五章 数组和广义表数组和广义表第22页/共62页1、数组的定义、数组的定义数组：数组：它是它是n（n1)个个相同数据类型相同数据类型的数的数据元素据元素a0,a1,a2,an-1构成的占用一块地址连构成的占用一块地址连续的内存单元的有限序列。续的内存单元的有限序列。注意：注意：（1）C语言的数组定义下标语言的数组定义下标从从0开始。开始。（2）数组元素的下标一般具有固定的）数组元素的下标一般具有固定的上界上界和和下下界，即数组一界，即数组一旦被定义，它的维数和维界就不再改变。旦被定义，它的维数和维界就不再改变。（3）一个二维数组可以看作）一个二维数组可以看作每个数据元

16、素是一个一维数组的每个数据元素是一个一维数组的一维数组一维数组。二维数组是两维的，内存单元是一维的，存在向。二维数组是两维的，内存单元是一维的，存在向内存存储时二维数组中数据元素的存储方法问题，内存存储时二维数组中数据元素的存储方法问题，C语言采用语言采用以行序为主序的方法存储。以行序为主序的方法存储。第23页/共62页 数组数组逻辑上是线性结构的推广；逻辑上是线性结构的推广；数组数组是以是以线性表为元素线性表为元素的线性结的线性结 构，而且元素的结构相同；构，而且元素的结构相同；数组数组可以看作是可以看作是下标和值的偶对下标和值的偶对的的集合；集合；数组数组是一种是一种逻辑结构逻辑结构。第2

17、4页/共62页例例1 1 高级语言中的数组高级语言中的数组wint a10;a0 a1 a2 a3 a10-1wchar B45 B00 B01 B02 B03 B05-1B10 B11B15-1B20 B21B25-1第25页/共62页二维数组wint a23;n两个变量组成的一个数组，其中两个变量组成的一个数组，其中每一个变量都是数组。其中每一个变量都是数组。其中a0，a1都是数组的名字，也就是地址。都是数组的名字，也就是地址。一个一个mn的二维数组可以看成是的二维数组可以看成是m行的一维数组，或者行的一维数组，或者n列的一维列的一维数组。数组。a01a00a12a11a10a02第26页

18、/共62页2.2.数组的抽象数据类型数组的抽象数据类型ADT ArrayADT Array 数据数据对象象：j ji i=0,=0,b,bi-1i-1,i=1,2,i=1,2,n,n,D=aj1j2,jn|n(0)称为数组的维数，b bi i是数组第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 Arr

19、ay ADT Array 数数组一旦被定一旦被定义，它的，它的维数和数和维界就不再改界就不再改变，因此除了，因此除了结构的构的初始化和初始化和销毁之外，数之外，数组只有只有存取元素存取元素和和修改元素修改元素值的操作。的操作。第27页/共62页3.数组的顺序表示和实现 数组一般不做插入和删除操作数组一般不做插入和删除操作,因因此采用此采用顺序存储顺序存储结构表示数组是自然的结构表示数组是自然的事了，事了，数组顺序存储时，必须确定按数组顺序存储时，必须确定按行行序或序或列列序存储序存储：（1）PASCAL、C 以以行序为主行序为主存储存储 （2）FORTRAN 以以列序为主列序为主存储存储第28

20、页/共62页a11 a12 a1n a21 a22 a2n am1 am2 amn a11 a21 am1 a12 a22 am2 a1n a2n amn 以行为主序 以列为主序第29页/共62页例如：例如：称为基地址基地址或基址。以以“行序为主序行序为主序”的存储映象的存储映象二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(b2ij)a0,1a0,0a0,2a1,0a1,1a1,2a0,1a0,0a0,2a1,0a1,1a1,2L L 第30页/共62页 例2：设数组a67的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a5,6的存储

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

22、么，这个数组的体积是这个数组的体积是 个字节。个字节。288答：Volume=m*n*L=(6-1+1)*(7-0+1)*6 =48*6=288第32页/共62页4.矩阵的压缩存储w当矩阵的阶数较高，而且矩阵中的一些元素当矩阵的阶数较高，而且矩阵中的一些元素有特殊的性质时，可以采用节省空间的存储有特殊的性质时，可以采用节省空间的存储办法（压缩存储）办法（压缩存储）w两类矩阵：两类矩阵：n特殊矩阵：特殊矩阵：值相同的元素或非零元素分值相同的元素或非零元素分布有一定的规律；布有一定的规律；n稀疏矩阵：稀疏矩阵：非零元素少且分布无规律；非零元素少且分布无规律；第33页/共62页特殊矩阵w对称矩阵对称

23、矩阵 n若若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中中:第34页/共62页 向量向量Bk和矩阵中的元素和矩阵中的元素aij之间存在着一一对应关系：之间存在着一一对应关系：下面按下标从下面按下标从0开始讨论。开始讨论。特殊矩阵（对称矩阵对称矩

24、阵）向量向量Bk和矩阵中的元素和矩阵中的元素aij之间的关系：之间的关系：由由i和和j推导推导k：第35页/共62页特殊矩阵（三角矩阵三角矩阵 ）w三角矩阵三角矩阵:下下(上上)三角矩阵是指矩阵的上（下）三角矩阵是指矩阵的上（下）三角（不包括对角线）中的元素均三角（不包括对角线）中的元素均为为常数常数c或或零零的的n阶矩阵阶矩阵 第36页/共62页下（上）三角矩阵的下（上）三角矩阵的存储公式除了和对称矩阵一样，只存储其下（上）三角中元存储公式除了和对称矩阵一样，只存储其下（上）三角中元之外，再加上一个存储常数之外，再加上一个存储常数c的存储空间即可。的存储空间即可。注意：注意：上（下）三角矩阵

25、的下（上）三角部分，可以全是上（下）三角矩阵的下（上）三角部分，可以全是0，也可以全是常数，也可以全是常数c.第37页/共62页w对角矩阵对角矩阵:所有非零元素都集中在以主对角线为中心所有非零元素都集中在以主对角线为中心的带状区域中。即除了主对角线上和直接在对角线上、的带状区域中。即除了主对角线上和直接在对角线上、下方若干条对角线上的元素之外，所有其它的元素均下方若干条对角线上的元素之外，所有其它的元素均为零。为零。特殊矩阵（对角矩阵对角矩阵 ）b条对角线n行n列(a)a11 a12 a21 a22 a23 an-1,n an,n an,n-1 OO(b)第38页/共62页三对角矩阵a00 a

26、01 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 (0 i,j n;0 k 3n)第39页/共62页稀疏矩阵w非零元素较少，分布无规律非零元素较少，分布无规律 n假设假设 m 行行 n 列列的矩阵含的矩阵含 t 个非零元素个非零元素，稀疏因子：稀疏因子：=t/(m*n)=0.05 w存储结构存储结

27、构 n顺序存储结构三元组表（行，列，值）顺序存储结构三元组表（行，列，值）n链式存储结构十字链表链式存储结构十字链表 第40页/共62页ije 1 2 6 1 6-2 3 4-8 4 2 3 4 6 7 5 1-12 5 3 9 例子：三元组表示第41页/共62页稀疏矩阵:十字链表十字链表中非零元结点的结构十字链表中非零元结点的结构 :row col e down right 0 0 next down right row col next 元素结点行列表头总表头结点第42页/共62页十字链表的结构类型十字链表的结构类型typedef struct OLNode int i,j;ElemTyp

28、e e;struct OLNode *down,*right;OLNode;*OLink;typedef struct OLink *rhead,*chead;/行、列行、列链表表头指指针 int mu,nu,tu ;CrossList;第43页/共62页3 0 0 50-1 0 02 0 0 01 1 31 4 52 2-13 1 2 第44页/共62页广义表的定义w广义表是由零个或多个原子或子表组成的有限序列，是线性表的推广 第46页/共62页广义表的概念w广义表般记作：LSLS(d(d1 1，d d2 2，d dn n)LS是广义表(d1，d2，dn)的名称，n是它的长度。di可以是单个

29、元素，也可以是广义表，分别称为广义表LS的原子和子表。w用大写字母表示广义表的名称，用小写字母表示原子 w当广义表LSLS非空时，称第一个元素d d1 1为LSLS的表头(Head)(Head)，称其余元素称其余元素组成的子表成的子表(d(d2 2，d dn n)是是LSLS的的表尾(Tail)(Tail)w非空广义表可唯一分解成表头和表尾；反过来，由表头和表尾可唯一组成一个广义表 w广义表括号的层数定义为广义表的深度。第47页/共62页广义表举例wA=()A A是一个空表，它的是一个空表，它的长度度为零零 wB=(e,f)B B有两个原子有两个原子e,fe,f，B B的的长度度为2 2 wC

30、=(a,(b,c)C C有有一一个个原原子子a a和和一一个个子子表表(b,c)(b,c)，C C的的长度度为2 2 wD=(B,A,C)D D有有三三个个子子表表B B、A A、C C，D D的的长度度为3 3 wE=(a,E)E E是一个递归的表，E E的长度为2 2，E E相当于一个无限的表(a,(a,(a,(a,(a,(a,)第48页/共62页广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E,F)其中:E=(a,(b,c)F=(d,(e)DEFa()d()bce第49页/共62页广义表广义表 LS=(1,2,n)的结构特点的结构特点:1)广义表中的数据元素有相对次序次序；

31、2)广义表的长度长度定义为最外层包含元素个数；3)广义表的深度深度定义为所含括弧的重数括弧的重数；注意：“原子”的深度为 0 “空表”的深度为 1 4)广义表可以共享共享；5)广义表可以是一个递归递归的表。递归表的深度是无穷值，长度是有限值。第50页/共62页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)=()H

32、ead(b,c)=b Tail(b,c)=(c)Head(c)=c Tail(c)=()第51页/共62页求下列广义表操作的结果 wGetHead(a,b,c)wGetTail(a,b,c,d)wGetHead(a,b),(d)wGetTail(a,b),(d)wGetHead(GetTail(a,b),(c,d)a(b,c,d)(a,b)(d)(c,d)第52页/共62页广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data第53页/共62页1 广义表的头尾链表存储表示：广义表的头尾链表存储表示：typedef

33、 enum ATOM,LIST ElemTag;/ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/标志域 union AtomType atom;/原子结点的数据域 struct struct GLNode*hp,*tp;ptr;*GListtag=1 hp tpptr表结点第54页/共62页1)表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法:若表头为原子，则为若表头为原子，则为空表空表 ls=NULL非空表非空表 lstag=1 指向表头的指针指向表尾的指针tag=0 data否则，依次类推。否则，依次类推。

34、第55页/共62页第56页/共62页L=(a,(x,y),(x)a(x,y)()1 LL=()0 a 1 1 1 1 1 0 x ()x0 x 1 0 y 第57页/共62页2)子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表 1 指向子表1 的指针tag=0 data否则，依次类推。否则，依次类推。1 指向子表2 的指针 1 指向子表n 的指针ls 第58页/共62页例如例如:a (x,y)(x)LS=(a,(x,y),(x)ls第59页/共62页课堂总结课堂总结主要内容：1.串、空串、空格串、子串、主串、位置、两串相等的概念 2.数组的概念；理解数组的顺序存储的含义，掌握顺序存储的定位公式。3.广义表的概念及其结构特点。第60页/共62页课堂练习课堂练习 设数组a60,70的基地址为2048，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a32,58的存储地址为 。答：根据行优先公式 LOC(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)得：LOC(a32,58)=2048+(32*71+58)*26708第61页/共62页谢谢大家观赏！第62页/共62页