第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 '串名 串值 串长

n

空串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 # # #

A

B

C

...

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

i=05 6 7 8 9

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

a 35 27 49 18 60 54 77 83 41 02l l l l l l l a+i*l l l l

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

2013年7月12日

数据结构

二维数组A ( 1, 2 , , p ) (p m或n)

Am n i (ai1, ai 2 , , ain ) 1 i m

a11 a12 a1n a a22 a2 n 21 am1 am 2 amn a11 a12 a1n a a22 a2 n 21 am1 am 2 amn 2013年7月12日

j (a1 j , a2 j , , amj ) 1 j n

Am n

…… 此处隐藏:25字,全部文档内容请下载后查看。喜欢就下载吧 ……
第4章 串、数组和广义表.doc 将本文的Word文档下载到电脑

    精彩图片

    热门精选

    大家正在看

    × 游客快捷下载通道(下载后可以自由复制和排版)

    限时特价:7 元/份 原价:20元

    支付方式:

    开通VIP包月会员 特价:29元/月

    注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
    微信:fanwen365 QQ:370150219