第4章串、数组和广义表

时间：2025-07-11

数据结构

数据结构陈文森

2013年7月12日

数据结构

第4章

串、数组和广义表

教学内容4.1 4.2 4.3 串数组广义表

2013年7月12日

数据结构

教学目标1. 了解串的存储方法，理解串的两种模式匹配 1. 掌握串的存储方法，理解串的两种模式匹算法，重点掌握BF算法。配算法； 2. 明确数组和广义表这两种数据结构的特点， 2. 明确数组和广义表这两种数据结构的特点掌握数组地址计算方法，了解几种特殊矩阵，掌握数组存储时地址计算方法，了解几种的压缩存储方法。特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和 GetTail的操作。2013年7月12日

数据结构

4.1 串串(String)----零个或多个字符组成的有限序列

s ' a1a2 an '串名串值串长

空串2013年7月12日

n=0

数据结构

串的存储结构顺序存储链式存储

2013年7月12日

数据结构

顺序存储表示typedef struct{

char *ch; int length;

//若串非空,则按串长分配存储区,//否则ch为NULL

//串长度

}HString;

2013年7月12日

数据结构

链式存储表示head

A B C Dhead

E F G H

I # # #

...

2013年7月12日

数据结构

链式存储表示#define CHUNKSIZE 80 typedef struct Chunk{ char ch[CHUNKSIZE]; struct Chunk *next; }Chunk; //可由用户定义的块大小

typedef struct{ Chunk *head,*tail; //串的头指针和尾指针 int curlen; //串的当前长度 }LString;2013年7月12日

数据结构

串的模式匹配算法算法目的：确定主串中所含子串第一次出现的位置(定位) 即如何实现教材P72 Index(S,T,pos)函数

算法种类： BF算法(又称古典的、经典的、朴素的、穷举的)

KMP算法(特点：速度快)

2013年7月12日

数据结构

BF算法设计思想 i S :ababcabcacbabT :abc j

i指针回溯

S :ababcabcacbab

T : abcS :ababcabcacbab T : abc2013年7月12日

数据结构

BF算法设计思想Index(S,T,pos) 将主串的第pos个字符和模式的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较。直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。

否则，匹配失败，返回值 02013年7月12日

数据结构

BF算法描述(算法4.1)int Index(Sstring S,Sstring T,int pos){ 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 ]) return i-T[0]; else return 0; }

2013年7月12日

数据结构

BF算法时间复杂度例： S=‘0000000001’,T=‘0001’,pos=1 若n为主串长度，m为子串长度，最坏情况是主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次最后m位也各比较了1次

总次数为：(n-m)*m+m=(n-m+1)*m 若m<<n,则算法复杂度O(n*m)2013年7月12日

数据结构

4.2 数组本节所讨论的数组与高级语言中的数组区别：

高级语言中的数组是顺序结构；而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。

2013年7月12日

数据结构

一维数组

LOC(i) =0 1 2

a,3 4