1、数据结构串数组和广义表课件数据结构串数组和广义表课件第第4 4章章串、数组和广义表串、数组和广义表 1.了解串的存储方法，理解串的两种模式匹配了解串的存储方法，理解串的两种模式匹配算法，重点掌握算法，重点掌握BF算法算法。2.明确数组和广义表这两种数据结构的特点，明确数组和广义表这两种数据结构的特点，掌握掌握数组地址计算方法数组地址计算方法，了解几种特殊矩阵，了解几种特殊矩阵的压缩存储方法。的压缩存储方法。3.掌握广义表的定义、性质及其掌握广义表的定义、性质及其GetHead和和GetTail的操作的操作。4.1 4.1 串串串串(String)-(String)-零个或多个字符组成的有限序列
2、零个或多个字符组成的有限序列21naaas串名串名串值串值串长串长n空串空串n=0a=a=BEIBEI,b=b=JINGJING c=c=BEIJINGBEIJING d=d=BEI JINGBEI JING子串子串字符位置字符位置主串主串子串位置子串位置串相等串相等空格串空格串0n ,2,1,|nietCharacterSaaDii数据对象数据对象:数据关系数据关系:,2,1,|,111niDaaaaRiiii基本操作基本操作:(1)StrAssign(&T,chars)/串赋值串赋值(2)StrCompare(S,T)/串比较串比较(3)StrLength(S)/求串长求串长(4)Conc
3、at(&T,S1,S2)/串联串联 ADT String 串的抽象数据类型串的抽象数据类型 (5)SubString(&Sub,S,pos,len)/求子串求子串 (6)StrCopy(&T,S)/串拷贝串拷贝 (7)StrEmpty(S)/串判空串判空 (8)ClearString(&S)/清空串清空串 (9)Index(S,T,pos)/子串的位置子串的位置 (10)Replace(&S,T,V)/串替换串替换 (11)StrInsert(&S,pos,T)/子串插入子串插入 (12)StrDelete(&S,pos,len)/子串删除子串删除 (13)DestroyString(&S)/
4、串销毁串销毁ADT Stringp 顺序存储顺序存储p 链式存储链式存储串的存储结构串的存储结构typedef structtypedef struct char char*ch;/ch;/若串非空若串非空,则按串长分配存储区则按串长分配存储区,/否则否则chch为为NULLNULL int length;/int length;/串长度串长度 HString;HString;顺序存储表示顺序存储表示ABCDEFGHI#headABCIhead.链式存储表示链式存储表示#define CHUNKSIZE 80 /可由用户定义的块大小可由用户定义的块大小typedef struct Chunk
5、char chCHUNKSIZE;struct Chunk*next;Chunk;typedef struct Chunk*head,*tail;/串的头指针和尾指针串的头指针和尾指针 int curlen;/串的当前长度串的当前长度LString;链式存储表示链式存储表示可将多个字符存放在一个结点中，以克服其缺点可将多个字符存放在一个结点中，以克服其缺点优点：操作方便优点：操作方便缺点：存储密度较低缺点：存储密度较低实际分配的存储位实际分配的存储位串值所占的存储位串值所占的存储位存储密度存储密度 ABCDEFGHI#headABCIhead.链式存储表示链式存储表示算法目的：算法目的：BFB
6、F算法算法（又称古典的、经典的、朴素的、穷举的）（又称古典的、经典的、朴素的、穷举的）KMPKMP算法（特点：速度快）算法（特点：速度快）算法种类：算法种类：确定主串中所含子串第一次出现的位置（定位）确定主串中所含子串第一次出现的位置（定位）串的模式匹配算法串的模式匹配算法 BFBF算法设计思想算法设计思想 将主串的第将主串的第pospos个字符和模式的第一个字符比较，个字符和模式的第一个字符比较，若若相等相等，继续逐个比较后续字符；，继续逐个比较后续字符；若若不等不等，从主串的下一字符起，重新与模式的第，从主串的下一字符起，重新与模式的第一个字符比较。一个字符比较。直到主串的一个连续子串字符
7、序列与模式相等直到主串的一个连续子串字符序列与模式相等 。返回值为返回值为S S中与中与T T匹配的子序列匹配的子序列第一个字符的序号第一个字符的序号，即匹配成功。即匹配成功。否则，匹配失败，返回值否则，匹配失败，返回值 0 0BFBF算法设计思想算法设计思想Index(S,T,pos)int Index(Sstring S,Sstring T,int pos)i=pos;j=1;while(i=S 0&j T 0)return iT0;else return 0;BFBF算法描述（算法算法描述（算法4.14.1）若若n n为主串长度，为主串长度，m m为子串长度，最坏情况是为子串长度，最坏情
8、况是BFBF算法时间复杂度算法时间复杂度主串前面主串前面n-mn-m个位置都部分匹配到子串的最后一个位置都部分匹配到子串的最后一位，即这位，即这n-mn-m位各比较了位各比较了m m次次最后最后m m位也各比较了位也各比较了1 1次次总次数为：总次数为：(n-m)*m+m(n-m+1)*m若若m 0 a,i=0 a+i*lamnmmnnnmaaaaaaaaaA212222111211mnmmnnnmaaaaaaaaaA212222111211naaamjjjjj1 ),(21miaaainiii1 ),(21n)m(p ),(21或pA二维数组二维数组以行序为主序以行序为主序数组的顺序存储数组
9、的顺序存储以列序为主序以列序为主序111101121202111101101000mnananamaaamaaamaaaa设数组开始存放位置设数组开始存放位置 LOC(0,0)=a LOC(j,k)=a+j*m+k二维数组的行序优先表示二维数组的行序优先表示l1u1l2u2l3u3三维数组三维数组按页按页/行行/列存放，页优先的顺序存储列存放，页优先的顺序存储各维元素个数为各维元素个数为 m1,m2,m3F 下标为下标为 i1,i2,i3的数组元素的存储位置：的数组元素的存储位置：LOC(i1,i2,i3)=a+i1*m2*m3+i2*m3+i3前前i1页总页总元素个数元素个数第第i1页的页的
10、前前i2行总行总元素个数元素个数第第 i2 行前行前 i3 列列元素个数元素个数三维数组三维数组各维元素个数为各维元素个数为 m1,m2,m3,mnF 下标为下标为 i1,i2,i3,in 的数组元素的存储位置：的数组元素的存储位置：nnjnjkkjnnnnnnimiimimmmimmmiiiiLOC111143232121 a a),(n n维数组维数组 L0,0,0,121niiinjcLOCjjjLOCni1 ,1iiincbcLcn n维数组维数组设有一个二维数组设有一个二维数组A A m mn n 按行优先按行优先顺序存储顺序存储，假设，假设A A0000存放位置在存放位置在6446
11、44(10)(10)，A A2222存放位置在存放位置在676676(10)(10)，每个元素占一个空间，问，每个元素占一个空间，问A A3333(10)(10)存放在存放在什么位置？脚注什么位置？脚注(10)(10)表示用表示用1010进制表示。进制表示。设数组元素设数组元素Aij存放在起始地址为存放在起始地址为Loc(i,j)的存储单元中的存储单元中 Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.n=(676-2-644)/2=15 Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.练习练习设有二维数组设有二维数组A10,20A10,
12、20，其每个元素占两个字节，其每个元素占两个字节，A A0000存储地址为存储地址为100100，若，若按行优先按行优先顺序存储，则顺序存储，则元素元素A6,6A6,6的存储地址为的存储地址为 ，按列优先按列优先顺序顺序存储，元素存储，元素A6,6A6,6的存储地址为的存储地址为 。练习练习352352232232(6(6*20+6)20+6)*2+100=3522+100=352(6(6*10+6)10+6)*2+100=2322+100=2321.什么是压缩存储？什么是压缩存储？若多个数据元素的若多个数据元素的值都相同值都相同，则只分配一个元素，则只分配一个元素值的存储空间，且零元素不占存
13、储空间。值的存储空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？什么样的矩阵能够压缩？一些特殊矩阵，如：对称矩阵，对角矩阵，三角一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。矩阵，稀疏矩阵等。3.什么叫稀疏矩阵？什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%5%）特殊矩阵的压缩存储特殊矩阵的压缩存储对称矩阵对称矩阵 对称矩阵的特点是对称矩阵的特点是aij=ajijiijjjijiik,12/)1(12/)1(，a11 a12 .a1n a21 a22.a2n an1 an2 .ann .a11 a21 a22 a31 a32 an1
14、 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 按行序为主序：按行序为主序：下（上）三角矩阵下（上）三角矩阵的特点是以主对角线为界的上（下）半的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何部分是一个固定的值，下（上）半部分的元素值没有任何规律。规律。三角矩阵三角矩阵 a11 0 0.0 a21 a22 0.0 an1 an2 an3.ann .0Loc(aij)=Loc(a11)+(+(j-1)*l i(i-1)2a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
15、 按行序为主序：按行序为主序：对角矩阵对角矩阵的特点是所有的非零元素都集中在以主对角线为的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。中心的带状区域中。比如，一个比如，一个3 3阶对角矩阵：阶对角矩阵：对角矩阵对角矩阵 a11 a12 0 .0 a21 a22 a23 0 0 0 0 an-1,n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann.0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+2(i-1)+(j-1)a11 a12 a21 a22 a23 ann-1 ann .k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1
16、 按行序为主序：按行序为主序：7600070015000001800000240001400003000000000009120MM M由由(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(1,2,12),(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)(6,1,15),(6,4,-7)和矩阵维数（和矩阵维数（6,76,7）唯一确定）唯一确定稀疏矩阵稀疏矩阵 定义：非零元较零元少，且分布没有一定规律的矩阵定义：非零元较零元少，且分布没有一定规律的矩阵 压缩存储原则
17、：只存矩阵的行列维数和每个非零元的行压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值列下标及其值6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 ma i j v0 1 2 3 4 5 6 7 8行列下标行列下标非零元非零元值值 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法顺序存储结构顺序存储结构 三元组表三元组表#define M 20typedef struct node int i,j;int v;JD;JD maM;76000700150000018000002400014000030000000000
18、09120M三元组表所需存储单元个数三元组表所需存储单元个数为为3(t+1)3(t+1)其中其中t t为非零元个数为非零元个数ma0.i,ma0.j,ma0.vma0.i,ma0.j,ma0.v分别存放矩阵行列维数和分别存放矩阵行列维数和非零元个数非零元个数 求转置矩阵求转置矩阵Y问题描述：已知一个稀疏矩阵的三元组表，求该矩问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表阵转置矩阵的三元组表Y问题分析问题分析一般矩阵转置算法：一般矩阵转置算法：for(col=0;coln;col+)for(row=0;rowm;row+)ncolrow=mrowcol;T(n)=O(m n)7
19、600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8mai j v7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8 mb?Y 解决思路：只要做到解决思路：只要做到 将矩阵行、列维数
20、互换将矩阵行、列维数互换 将每个三元组中的将每个三元组中的i和和j相互调换相互调换 重排三元组次序，使重排三元组次序，使mb中元素以中元素以N的行的行(M的列的列)为主序为主序按按M的列序转置的列序转置 即按即按mb中三元组次序依次在中三元组次序依次在ma中找到相应的三元组进中找到相应的三元组进行转置。为找到行转置。为找到M中每一列所有非零元素，需对其三元组表中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于从第一行起扫描一遍。由于ma中以中以M行序为主序行序为主序,所以由所以由此得到的恰是此得到的恰是mb中应有的顺序。中应有的顺序。Y 算法分析：算法分析：T(n)=O(M的列数
21、的列数n 非零元个数非零元个数t)若若 t 与与m n同数量级，则同数量级，则)()(2nmOnT6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j v0 1 2 3 4 5 6 7 8ma7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j v0 1 2 3 4 5 6 7 8mbkppppppppkkkkppppppppcol=1col=2 链式存储结构链式存储结构 带行指针向量的单链表表示带行指针向量的单链表表示Y 每行的非零元用一个单
22、链表存放每行的非零元用一个单链表存放 Y 设置一个行指针数组，指向本行第一个非设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空零元结点；若本行无非零元，则指针为空Y 表头结点与单链表结点类型定义表头结点与单链表结点类型定义typedef struct node int col;int val;struct node *link;JD;typedef struct node *TD;0200000000000210010070003A1 35 73 -11 -12 -24 2需存储单元个数为需存储单元个数为3t+m 十字链表十字链表Y 设行指针数组和列指针数组，分别指向每
23、行、列第一个非零元设行指针数组和列指针数组，分别指向每行、列第一个非零元Y 结点定义结点定义tpedef struct node int row,col,val;struct node *down,*right;JD;row col valdownright34008000450003A1134182252344.3 4.3 广义表广义表n 广义表（列表）：广义表（列表）：n(0)个表元素组成的有限序列个表元素组成的有限序列，记作记作LS=(a0,a1,a2,an-1)LS是表名，是表名，ai是表元素，它可以是表是表元素，它可以是表（称为（称为子表子表），可），可以是数据元素（以是数据元素（称
24、为称为原子原子）。）。n n为表的长度。为表的长度。n=0 的广义表为空表。的广义表为空表。线性表的成分都是结构上不可分的单元素线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表广义表的成分可以是单元素，也可以是有结构的表线性表是一种特殊的广义表线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构广义表不一定是线性表，也不一定是线性结构广义表与线性表的区别？广义表与线性表的区别？广义表是一个广义表是一个多层次多层次的的线性结构线性结构。例如：例如：有有A、B、C、D、E五个广义表的描述如下：五个广义表的描述如下：A=()A是一个空表，它的长度为零是一个
25、空表，它的长度为零 B=(e)列表列表B只有一个原子只有一个原子e，B的长度为的长度为1 C=(a，(b，c，d)列表列表C的长度为的长度为2，两个元素分别为原子，两个元素分别为原子a和子表和子表(b，c，d)D=(A，B，C)列表列表D的长度为的长度为3，三个元素都是列表，三个元素都是列表,显然显然,将子表的将子表的值代入后，则有值代入后，则有D=()，(e)，(a，(b，c，d)E=(a，E)这是一个递归的表这是一个递归的表,它的长度为它的长度为2，E相当于一个无限的列相当于一个无限的列表表E=(a，(a，(a，.)广义表的结构特点：广义表的结构特点：1)广义表中的数据元素有相对广义表中的
26、数据元素有相对次序次序。2)广义表的广义表的长度长度定义为最外层包含的元素个数。定义为最外层包含的元素个数。3)广义表的广义表的深度深度定义为所含括弧的重数。定义为所含括弧的重数。注意：注意：“原子原子”的深度为的深度为“0”；“空表空表”的深度为的深度为1。4)表头可以是原子或列表；表尾必定是列表。表头可以是原子或列表；表尾必定是列表。5)广义表可以是一个广义表可以是一个递归递归的表；递归表的深度是无穷值，长度的表；递归表的深度是无穷值，长度是有限值。是有限值。6)任何一个非空广义表任何一个非空广义表 LS=(1，2，n)均可分解为均可分解为表头表头Head(LS)=1和和表尾表尾Tail(
27、LS)=(2，n)两两部分。部分。广义表的基本运算广义表的基本运算（1）求表头）求表头GetHead(L)：非空广义表的第一个元：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表素，可以是一个单元素，也可以是一个子表（2）求表尾）求表尾GetTail(L)：非空广义表除去表头元素：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表以外其它元素所构成的表。表尾一定是一个表练习练习A=()GetHead和和GetTail均无定义均无定义A=(a,b)GetHead(A)=a GetTail(A)=(b)A=(a)GetHead(A)=a GetTail(A)=()A=(a)G
28、etHead(A)=(a)GetTail(A)=()GetHead(GetTail(GetHead(GetTail(GetTail(A)A=(a,b,(c,d),(e,(f,g)d 求下列广义表操作的结果：求下列广义表操作的结果：（1）GetHead(a，b，c)（2）GetTail(a，b，c，d)（3）GetHead(a，b)，(d)（4）GetTail(a，b)，(d)（5）GetHead(GetTail(a，b)，(c，d)（6）GetTail(GetHead(GetTail(a，b)，(c，d)（1）a （2）(b,c,d)（3）(a,b)（4）(d)（5）(c,d)（6）(d)例如
29、：例如：已知广义表已知广义表LS=LS=（a a，（，（b b，c c，d d），），c c），运用），运用GetHeadGetHead和和GetTailGetTail函数取出原子函数取出原子d d的运算过程为：的运算过程为：GetHead(GetTail(GetTail(GetHead(GetTail(LS)注意广义表（注意广义表（）和）和()()不同。前者是长度为不同。前者是长度为0 0的空的空表，对其不能做求表头的和表尾的运算；而后者是长度为表，对其不能做求表头的和表尾的运算；而后者是长度为1 1的非空表（只不过该表中唯一的一个元素是空表）。对其的非空表（只不过该表中唯一的一个元素是空表
30、）。对其可进行分解，得到表头和表尾均为空表（可进行分解，得到表头和表尾均为空表（）。）。5.5 广义表的表示方法广义表的表示方法 头、尾指针的链表结构头、尾指针的链表结构构造存储结构的两种分析方法构造存储结构的两种分析方法:有次序性有次序性 有长度有长度 有深度有深度 可递归可递归 可共享可共享一个直接前驱和一个直接后继一个直接前驱和一个直接后继表中元素个数表中元素个数表中括号的重数表中括号的重数自己可以作为自己的子表自己可以作为自己的子表可以为其他广义表所共享可以为其他广义表所共享广义表的特点广义表的特点小小 结结串类型的定义串类型的定义串的定义，特点，串的抽象数据类型定义串的定义，特点，串的抽象数据类型定义串的表示和实现串的表示和实现定长顺序存储表示定长顺序存储表示堆分配存储表示堆分配存储表示块链存储表示块链存储表示串的模式匹配定义串的模式匹配定义 数组数组定义，特点定义，特点数组元素存储位置的计算数组元素存储位置的计算广义表的定义，特点广义表的定义，特点此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢
