数据结构串数组和广义表课件教学内容

数据结构串数组和广义表课件第4章串、数组和广义表1.了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及其GetHead和GetTail的操作。4.1串串(String)----零个或多个字符组成的有限序列串名串值串长n空串n=0a=‘BEI’,b=‘JING’

c=‘BEIJING’

d=‘BEIJING’子串字符位置主串子串位置串相等空格串数据对象:数据关系:基本操作:(1)

StrAssign(&T,chars)//串赋值(2)StrCompare(S,T)//串比较(3)StrLength(S)//求串长(4)Concat(&T,S1,S2)//串联ADTString{串的抽象数据类型(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)//串销毁}ADTString顺序存储链式存储串的存储结构typedefstruct{char*ch;//若串非空,则按串长分配存储区,//否则ch为NULLintlength;//串长度}HString;

顺序存储表示链式存储表示#defineCHUNKSIZE80//可由用户定义的块大小typedefstructChunk{charch[CHUNKSIZE];structChunk*next;}Chunk;typedefstruct{Chunk*head,*tail;//串的头指针和尾指针

intcurlen;//串的当前长度}LString;链式存储表示可将多个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低实际分配的存储位串值所占的存储位存储密度=链式存储表示算法目的：BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：确定主串中所含子串第一次出现的位置（定位）串的模式匹配算法

S:ababcabcacbabT:abcijS:ababcabcacbab T:abcS:ababcabcacbabT:abci指针回溯BF算法设计思想将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值0BF算法设计思想Index(S,T,pos)intIndex(SstringS,SstringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]=T[j]){++i;++j;}else{i=i-j+2;j=1;}if(j>T[0])returni－T[0];elsereturn0;}BF算法描述（算法4.1）若n为主串长度，m为子串长度，最坏情况是BF算法时间复杂度主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次最后m位也各比较了1次总次数为：(n-m)*m+m＝(n-m+1)*m若m<<n，则算法复杂度O(n*m)例：S=‘0000000001’，T=‘0001’，pos=1利用已经部分匹配的结果而加快模式串的滑动速度？且主串S的指针i不必回溯！可提速到O(n+m)！S=‘ababcabcacbab’T=‘abcac’S=‘ab

abca

bcacbab’T=‘abca

c’S=‘ab

abcabcacbab’T=‘abcac’iiikk

a

b

aa

b

ckiiKMP算法设计思想（了解）串操作应用举例－－文本编辑文本可被看作一个字符串，称为文本串页则是文本串的子串行又是页的子串。页号起始行号页表…………行号起始地址长度行表…………《数据结构》所讨论的数组与高级语言中的数组区别：高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。4.2数组数组的抽象数据类型数据对象:数据关系:ADTArray{基本操作:

(1)InitArray(&A,n,bound1,boundn)//构造数组A(2)DestroyArray(&A)//销毁数组A(3)Value(A,&e,index1,…,indexn)//取数组元素值

(4)Assign(A,&e,index1,…,indexn)//给数组元素赋值}ADTArray

其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，元素总数为m×n。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说:

typedefelemtypearray2[m][n];

等价于：

typedefelemtypearray1[n];

typedefarray1array2[m];

数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。数组特点数组结构固定数据元素同构数组运算给定一组下标，存取相应的数据元素给定一组下标，修改数据元素的值二维数组结构的基本操作：（1）给定一组下标，修改该位置元素的内容

Assign(A,item,index1,index2)（2）给定一组下标，返回该位置的元素内容

Value(A,item,index1,index2)一维数组352749186054778341020123456789llllllllll

LOC(i)=LOC(i-1)+l=a+i*lLOC(i)=

LOC(i-1)+l=a+i*l,i>0

a,i=0

a+i*la二维数组以行序为主序数组的顺序存储以列序为主序

a[n][m]设数组开始存放位置LOC(0,0)=a

LOC(j,k)=a+j*m+k二维数组的行序优先表示①②③三维数组按页/行/列存放，页优先的顺序存储

a[m1][m2][m3]

各维元素个数为

m1,m2,m3

下标为i1,i2,i3的数组元素的存储位置：

LOC(i1,i2,i3)=a+i1*m2*m3+i2*m3+i3前i1页总元素个数第i1页的前i2行总元素个数第i2行前i3列元素个数三维数组

各维元素个数为

m1,m2,m3,…,mn

下标为i1,i2,i3,…,in

的数组元素的存储位置：

n维数组n维数组设有一个二维数组A[m][n]按行优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。设数组元素A[i][j]存放在起始地址为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.练习设有二维数组A[10,20]，其每个元素占两个字节，A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为

，按列优先顺序存储，元素A[6,6]的存储地址为

。练习352232(6*20+6)*2+100=352(6*10+6)*2+100=2321.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？

一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）特殊矩阵的压缩存储对称矩阵

对称矩阵的特点是aij=aji

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann….a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。三角矩阵

a11

00

……..0

a21a22

0

……..0

an1an2an3……..ann……………….0Loc(aij)=Loc(a11)+[(+(j-1)]*l

i(i-1)2a11a21a22a31a32an1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，一个3阶对角矩阵：对角矩阵

a11

a120

…………….0

a21

a22

a23

0

……………00

0

…an-1,n-2an-1,n-1

an-1,n0

0

……an,n-1ann.

0

a32a33

a34

0

………0……………Loc(aij)=Loc(a11)+2(i-1)+(j-1)

a11a12a21a22a23ann-1ann

…...…...k=01234n(n-1)/2n(n+1)/2-1按行序为主序：M由{(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,7）唯一确定稀疏矩阵定义：非零元较零元少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值6

7

8

121213931-3361443245218611564-7maijv012345678行列下标非零元值稀疏矩阵的压缩存储方法顺序存储结构三元组表#defineM20typedefstructnode{inti,j;intv;}JD;JDma[M];三元组表所需存储单元个数为3(t+1)其中t为非零元个数ma[0].i,ma[0].j,ma[0].v分别存放矩阵行列维数和非零元个数求转置矩阵问题描述：已知一个稀疏矩阵的三元组表，求该矩阵转置矩阵的三元组表问题分析一般矩阵转置算法：for(col=0;col<n;col++)for(row=0;row<m;row++)n[col][row]=m[row][col];T(n)=O(mn)6

7

8

121213931-3361443245218611564-7ijv012345678maijv7

6

8

13-3161521122518319342446-76314012345678mb?

解决思路：只要做到将矩阵行、列维数互换将每个三元组中的i和j相互调换重排三元组次序，使mb中元素以N的行(M的列)为主序按M的列序转置即按mb中三元组次序依次在ma中找到相应的三元组进行转置。为找到M中每一列所有非零元素，需对其三元组表ma从第一行起扫描一遍。由于ma中以M行序为主序,所以由此得到的恰是mb中应有的顺序。算法分析：T(n)=O(M的列数n非零元个数t)

若t与mn同数量级，则6

7

8

121213931-3361443245218611564-7ijv012345678ma7

6

8

13-3161521122518319342446-76314ijv012345678mbkppppppppkkkkppppppppcol=1col=2链式存储结构带行指针向量的单链表表示每行的非零元用一个单链表存放设置一个行指针数组，指向本行第一个非零元结点；若本行无非零元，则指针为空表头结点与单链表结点类型定义typedefstructnode{intcol;intval;structnode*link;}JD;typedefstructnode*TD;^13573-11-12-242^^^^需存储单元个数为3t+m十字链表设行指针数组和列指针数组，分别指向每行、列第一个非零元结点定义tpedefstructnode{introw,col,val;structnode*down,*right;}JD;rowcolvaldownright113418225234^^^^^^^4.3广义表

广义表（列表）：n(0)个表元素组成的有限序列，记作LS=(a0,a1,a2,…,an-1)

LS是表名，ai是表元素，它可以是表（称为子表），可以是数据元素（称为原子）。

n为表的长度。n=0的广义表为空表。线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构广义表与线性表的区别？

广义表是一个多层次的线性结构。例如：有A、B、C、D、E五个广义表的描述如下：

A=()A是一个空表，它的长度为零

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)广义表中的数据元素有相对次序。2)广义表的长度定义为最外层包含的元素个数。3)广义表的深度定义为所含括弧的重数。注意：“原子”的深度为“0”；“空表”的深度为1。4)表头可以是原子或列表；表尾必定是列表。5)广义表可以是一个递归的表；递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表LS=(1，2，…，n)均可分解为表头Head(LS)=1和表尾Tail(LS)=(2，…，n)两部分。广义表的基本运算（1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表（2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表练习A=()

GetHead和GetTail均无定义A=(a,b)

GetHead(A)=aGetTail(