数据结构 C语言版 教学课件 ppt 作者 严蔚敏 李冬梅 吴伟民 第4章 串、数组和广义表

*北京林业大学信息学院李冬梅数据结构北京林业大学信息学院**北京林业大学信息学院可 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为：（a1,a2,……,an）线性结构 第2章线性表 第3章栈和队列 第4章串、数组和广义表北京林业大学信息学院*北京林业大学信息学院串比较，strcmp(chars1,chars2)串复制，strcpy(charto,charfrom)串连接，strcat(charto,charfrom)求串长，strlen(chars)……调用 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 库函数#include<string.h>补充：C语言中常用的串运算北京林业大学信息学院*北京林业大学信息学院第4章　串、数组和广义表4.1串4.2数组4.3广义表教学 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 北京林业大学信息学院*北京林业大学信息学院1.掌握串的存储方法，理解串的两种模式匹配算法；2.明确数组和广义表这两种数据结构的特点，掌握数组存储时地址计算方法，了解几种特殊矩阵的压缩存储方法。教学目标1.了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及其GetHead和GetTail的操作。北京林业大学信息学院*北京林业大学信息学院4.1串串(String)----零个或多个字符组成的有限序列串名串值串长n空串n=0北京林业大学信息学院**北京林业大学信息学院a=‘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)//子串的位置(11)Replace(&S,T,V)//串替换(12)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;链式存储表示北京林业大学信息学院*北京林业大学信息学院可将多个字符存放在一个结点中，以克服其缺点优点：操作方便缺点：存储密度较低链式存储表示北京林业大学信息学院*北京林业大学信息学院算法目的：确定主串中所含子串第一次出现的位置（定位）即如何实现教材P72Index(S,T,pos)函数串的模式匹配算法北京林业大学信息学院*北京林业大学信息学院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北京林业大学信息学院*北京林业大学信息学院KMP（KnuthMorrisPratt）算法http://www-cs-faculty.stanford.edu/~knuth/《计算机程序设计艺术第1卷基本算法》   98元《计算机程序设计艺术第2卷半数值算法》98元《计算机程序设计艺术第3卷排序与查找》98元北京林业大学信息学院*北京林业大学信息学院利用已经部分匹配的结果而加快模式串的滑动速度？且主串S的指针i不必回溯！可提速到O(n+m)！S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’S=‘ababcabcacbab’T=‘abcac’abaabcKMP算法设计思想（了解）北京林业大学信息学院*北京林业大学信息学院串操作应用举例－－文本编辑 文本可被看作一个字符串，称为文本串 页则是文本串的子串 行又是页的子串。北京林业大学信息学院*北京林业大学信息学院本节所讨论的数组与高级语言中的数组区别： 　高级语言中的数组是顺序结构； 　而本章的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。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北京林业大学信息学院**北京林业大学信息学院一维数组352749186054778341020123456789llllllllllLOC(i)=LOC(i-1)+l=a+i*lLOC(i)=LOC(i-1)+l=a+i*l,i>0a,i=0a+i*la北京林业大学信息学院*北京林业大学信息学院二维数组北京林业大学信息学院*北京林业大学信息学院 以行序为主序C,PASCAL数组的顺序存储北京林业大学信息学院*北京林业大学信息学院 以列序为主序FORTRAN北京林业大学信息学院*北京林业大学信息学院a[n][m]设数组开始存放位置LOC(0,0)=aLOC(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=232北京林业大学信息学院*北京林业大学信息学院1.什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？一些特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）特殊矩阵的压缩存储北京林业大学信息学院*北京林业大学信息学院4.3广义表广义表（列表）：n(0)个表元素组成的有限序列，记作LS=(a0,a1,a2,…,an-1)LS是表名，ai是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。n为表的长度。n=0的广义表为空表。北京林业大学信息学院*北京林业大学信息学院 线性表的成分都是结构上不可分的单元素 广义表的成分可以是单元素，也可以是有结构的表 线性表是一种特殊的广义表 广义表不一定是线性表，也不一定是线性结构广义表与线性表的区别？北京林业大学信息学院*北京林业大学信息学院广义表的基本运算 （1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表 （2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表北京林业大学信息学院*北京林业大学信息学院练习A=()　　　　　　　A=(a,b)　　　　　　　A=(a)　　　　　　　A=((a))　　　　　　　d北京林业大学信息学院*北京林业大学信息学院 有次序性 有长度 有深度 可递归 可共享一个直接前驱和一个直接后继＝表中元素个数＝表中括号的重数自己可以作为自己的子表可以为其他广义表所共享广义表的特点北京林业大学信息学院*北京林业大学信息学院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=(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)))，共享表练习：求下列广义表的长度北京林业大学信息学院*北京林业大学信息学院1.了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及其GetHead和GetTail的操作。小结北京林业大学信息学院****