串、数组和广义表概述

1、 2022年7月23日 串、数组和广义表概述 4.1 串4.2 数组4.3 教学内容 2022年7月23日 1. 掌握串的存储方法，理解串的两种模式匹配算法；2. 明确数组和广义表这两种数据结构的特点，掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。 教学目标1. 了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2. 明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和GetTail的操作。 2022年7月23日 4.1 串串(String)-零个或多个字符组成的有限序列串名串值串

2、长n空串n=0 2022年7月23日 a=BEI, b=JING c=BEIJING d=BEI JING子串字符位置主串子串位置串相等空格串 2022年7月23日 数据对象:数据关系:基本操作:(1) StrAssign (&T,chars) /串赋值(2) StrCompare (S,T) /串比较(3) StrLength (S) /求串长(4) Concat(&T,S1,S2) /串联 ADT String 串的抽象数据类型 2022年7月23日 北京林业大学信息学院 (5) SubString(&Sub,S,pos,len) /求子串 (6) StrCopy(&T,S) /串拷贝 (

3、7) StrEmpty(S) /串判空 (8) ClearString (&S) /清空串 (9) Index(S,T,pos) /子串的位置 (11) Replace(&S,T,V) /串替换 (12) StrInsert(&S,pos,T) /子串插入 (12) StrDelete(&S,pos,len) /子串删除 (13) DestroyString(&S) /串销毁ADT String 2022年7月23日 顺序存储链式存储串的存储结构 2022年7月23日 typedef struct char *ch; /若串非空,则按串长分配存储区, /否则ch为NULL int length

4、; /串长度HString; 顺序存储表示 2022年7月23日 链式存储表示 2022年7月23日 可将多个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低实际分配的存储位串值所占的存储位存储密度=链式存储表示 2022年7月23日 #define CHUNKSIZE 80 /可由用户定义的块大小typedef struct Chunk char chCHUNKSIZE; struct Chunk *next;Chunk;typedef struct Chunk *head,*tail; /串的头指针和尾指针 int curlen; /串的当前长度LString; 链式存储

5、表示 2022年7月23日 算法目的：BF算法（又称古典的、经典的、朴素的、穷举的）KMP算法（特点：速度快）算法种类：确定主串中所含子串第一次出现的位置（定位）即如何实现教材P72 Index(S,T,pos)函数串的模式匹配算法 2022年7月23日 S : a b a b c a b c a c b a bT : a b cijS : a b a b c a b c a c b a b T : a b cS : a b a b c a b c a c b a bT : a b ci指针回溯BF算法设计思想 2022年7月23日 将主串的第pos个字符和模式的第一个字符比较， 若相等，继续

6、逐个比较后续字符； 若不等，从主串的下一字符起，重新与模式的第一个字符比较。 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0BF算法设计思想Index(S,T,pos) 2022年7月23日 int Index(Sstring S,Sstring T,int pos) i=pos; j=1; while (i=S 0 & j T 0 ) return iT0; else return 0;BF算法描述（算法） 2022年7月23日 若n为主串长度，m为子串长度，最坏情况是BF算法时间复杂度主串前面n-m个位置都部

7、分匹配到子串的最后一位，即这n-m位各比较了m次最后m位也各比较了1次总次数为：(n-m)*m+m(n-m+1)*m若mn，则算法复杂度O(n*m)例： S=0000000001，T=0001，pos=1 2022年7月23日 利用已经部分匹配的结果而加快模式串的滑动速度，且主串S的指针i不必回溯！亲！可提速到O(n+m)哦！S=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a cS=a b a b c a b c a c b a bT=a b c a ciiikk a b aa b ckiiKMP

8、算法设计思想（了解）KMP算法的时间复杂度可以达到O(m+n) 当 Si Tj 时，已经得到的结果: Si-j+1.i-1 = T1.j-1 若已知 T1.k-1 = Tj-k+1.j-1 则有 Si-k+1.i-1 = T1.k-1三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法定义：模式串的next函数 int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i = S0 & j T0) return i-T0; / 匹配成功 else

9、return 0; / Index_KMP这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串求next函数值的过程是一个 递推过程，分析如下:已知：next1 = 0；假设：nextj = k；又 Tj = Tk则： nextj+1 = k+1若： Tj Tk则需往前回朔，检查 Tj = T ？ void get_next(SString &T, int &next ) / 求模式串T的next函数值并存入数组next。 i = 1; next1 = 0; j = 0; while (i T0) if (j = 0 | Ti = Tj) +i; +j; nexti = j; else

10、 j = nextj; / get_next还有一种特殊情况需要考虑：例如： S = aaabaaabaaabaaabaaab T = aaaab nextj= 01234 nextvalj=00004void get_nextval(SString &T, int &nextval) i = 1; nextval1 = 0; j = 0; while (i 0 a, i = 0 a+i*la 2022年7月23日 二维数组 2022年7月23日 以行序为主序C, PASCAL数组的顺序存储 2022年7月23日 以列序为主序FORTRAN 2022年7月23日 anm设数组开始存放位置 LO

11、C( 0, 0 ) = a LOC ( j, k ) = a + j * m + k二维数组的行序优先表示 2022年7月23日 设有二维数组A10,20，其每个元素占两个字节， A00存储地址为100，若按行优先顺序存储，则元素A6,6的存储地址为 ，按列优先顺序存储，元素A6,6的存储地址为 。 课堂任务（经验值200）352232(6*20+6)*2+100=352(6*10+6)*2+100=232 2022年7月23日 设有一个二维数组Amn按行优先顺序存储，假设A00存放位置在644(10)，A22存放位置在676(10)，每个元素占一个空间，问A33(10)存放在什么位置？脚注(

12、10)表示用10进制表示。设数组元素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.课堂任务（经验值200） 2022年7月23日 1. 什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2. 什么样的矩阵能够压缩？ 一些值相

13、同的元素或零元素在矩阵中分布有规律的特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3. 什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）特殊矩阵的压缩存储(课堂自学，完成以下任务，每任务200经验值) 2022年7月23日 4.3 广义表 广义表（列表）： n ( 0 )个表元素组成的有限序列， 记作LS = (a0, a1, a2, , an-1) LS是表名，ai是表元素，它可以是表 (称为子表)，可以是数据元素(称为原子)。 n为表的长度。n = 0 的广义表为空表。 2022年7月23日 线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表

14、线性表是一种特殊的广义表广义表不一定是线性表，也不一定是线性结构广义表与线性表的区别？（每答出一条区别加经验值100） 2022年7月23日 广义表的基本运算（1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表（2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表。 2022年7月23日 练习求表头表尾（每题100经验值）A=( ) GetHead 和 GetTail均无定义A=(a,b) GetHead(A)=a GetTail(A)=(b) A=(a) GetHead(A)=a GetTail(A)=( )

15、A=(a) GetHead(A)=(a) GetTail(A)=( ) GetHead(GetTail(GetHead(GetTail(GetTail(A) =？A=(a,b,(c,d),(e,(f,g) d 2022年7月23日 有次序性有长度有深度可递归可共享一个直接前驱和一个直接后继表中元素个数表中括号的重数自己可以作为自己的子表可以为其他广义表所共享广义表的特点 2022年7月23日 E=(a,E)=(a,(a,E)= (a,(a,(a,.)，E为递归表1）A =( )2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C )5）E=(

16、a, E)n=0，因为A是空表n=1，表中元素e是原子n=2，a 为原子，(b,c,d)为子表n=3，3个元素都是子表n=2，a 为原子，E为子表D=(A,B,C)=( ),(e),(a,(b,c,d)，共享表练习：求下列广义表的长度（每题经验值100） 2022年7月23日 1. 了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2. 明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和GetTail的操作。小结进阶任务（每任务100经验值）（1）串是一种特殊的线性表，其特殊性体现在（ ）。

17、A可以顺序存储 B数据元素是一个字符 C可以链式存储 D数据元素可以是多个字符若 （2）串下面关于串的的叙述中，（ ）是不正确的？ A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储（3）串“ababaaababaa”的next数组为（ ）。 A9 B2 C6 D45进阶任务（每任务100经验值）（4）串“ababaabab”的nextval为（ ）。 A010104101 B010102101 C010100011 D010101011 （5）串的长度是指（ ）。 A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不

18、同字符的个数 D串中所含非空格字符的个数（6）假设以行序为主序存储数组A=array1.100,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=（ ）。 A808 B818 C1010 D1020进阶任务（每任务100经验值）（7）设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（ ）。 ABA+141 BBA+180 CBA+222 DBA+225（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占

19、一个地址空间，则a85的地址为（ ）。 A13 B33 C18 D40（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为（ ）。 Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i进阶任务（每任务100经验值）（10）AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组TN(N+1)/2中，则对任一上三角元素aij对应Tk的下标k是（ ）。 Ai(i-1)/2+j Bj(j-1)/2+i Ci(j-i)/2+1

20、 Dj(i-1)/2+1（11）设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. m*n中，则二维数组元素Ai,j在一维数组B中的下标为（ ）。 A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1（12）数组A0.4,-1.-3,5.7中含有元素的个数（ ）。 A55 B45 C36 D16进阶任务（每任务100经验值）（13）广义表A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail(A)的值为（ ）。 A(g) B(d) Cc Dd（14）广义表(a,b,c,d)的表头是（ ），表尾是（ ）。 Aa

21、B( ) C(a,b,c,d) D(b,c,d)（15）设广义表L=(a,b,c)，则L的长度和深度分别为（ ）。 A1和1 B1和3 C1和2 D2和3 进阶任务（每任务200经验值）（1）已知模式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next和nextval函数值。模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5进阶任务（每任务200经验值）（3）数组A中，每个元素Ai,j的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： 存放该数组所需多少单元？ 存放数组第4列所有元素至少需多少单元？ 数组按行存放时，元素A7,4的起始地址是多少？ 数组按列存放时，元素A4,7的起始地址是多少？ 每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11(共11行，11列)。