当前位置：文档之家 › 数据结构第四章备课讲稿

数据结构第四章备课讲稿

  • 格式：doc
  • 大小：34.50 KB
  • 文档页数：10

下载文档原格式

  / 10

合集下载

数据结构第4章串B教学ppt

数据结构第4章串B教学ppt
严蔚敏、吴伟民编著的经典教材，详细介绍了各 种数据结构及其基本操作，包括串的实现和应用。
《算法导论》
Thomas H. Cormen等编著的经典算法教材，深 入讲解了算法设计和分析的方法，包括串的模式 匹配等算法。
MOOC课程
中国大学MOOC、Coursera等在线教育平台上 提供了大量与数据结构和算法相关的课程，可以 系统地学习相关知识和技能。
压缩串处理技术
针对大规模文本数据，研究压缩串处理技术可以减少存储 空间占用，提高处理效率，是未来发展的重要方向之一。
串的并行处理技术
利用并行计算技术加速串的处理过程，提高处理效率，是 未来研究的热点之一。需要解决并行化算法设计、并行计 算框架选择等问题。
拓展学习资源推荐
1 2 3
《数据结构（C语言版）》
Sunday算法
Sunday算法是一种简单且高效的字符串匹配算法，其核心思 想是当发现不匹配的字符时，直接跳过主串中当前字符之前 的所有字符，将模式串与主串的下一个字符进行比较。
03
串的应用举例
文本编辑中的串操作
01
02
03
字符串匹配
在文本编辑中，经常需要 查找或替换特定的字符串， 这可以通过串的匹配操作 实现。
可以使用数组下标和字 符串截取函数`substr()` 实现串的截取，如`char ch = str[2];`或 `std:string sub = str.substr(2, 4);`。
Python语言实现串的基本操作
串的定义与初始化
在Python中，串使用引号（单引号、双 引号或三引号）进行定义和初始化，如`s = 'hello'`或`s = "hello"`。的比较

数据结构授课教案-第4章

数据结构授课教案-第4章
分钟
教学手段
板书、课件
总结
分钟
备注
共2学时
注：课型一栏填写理论课、实验课、习题课等
授课内容
备注
第四章串
4.1串类型的定义
一、串的基本概念
串(String)是零个或多个字符组成的有限序列。
一般记为：S=‘a1a2…an’ (n≥0)
其中S为串名，用单引号括起来的为串值，n为串的长度。
空串(Null String)：n=0时的串为空串
len>s.length-pos+1)
return error;
if(sub.ch) free(sub.ch);
if(!len){
sub.ch=null;
sub.length=0;
}
else{
sub.ch=(char *)malloc(len*sizeof(char));
sub.ch[0..len-1]=s[pos-1..pos+len-2];
t.length=s1.length+s2.length;
t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];
}
Statussubstr(hstringsub,hstrings,intpos,intlen){
if(pos<1 || pos>s.length||len<0 ||
空格串(Blank string)：由一个或多个称为空格的特殊字符组成的串。
请注意空串(Null String)和空格串(Blank string)的区别。
子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

数据结构第4章树PPT学习教案

数据结构第4章树PPT学习教案

(c)
(d)
(二叉树 (b)仅有一个根结点的二叉树 (c)右子树为空的二叉树 (d) 左子树为空的二叉树 (e)左右子树均非空的二叉树
二叉树是n(n≥0)个结点的有限集，它或者是空集
(n=0)，或者由一个根结点及两棵互不相交的、分别称
作这个根的左子树和右子树的二叉树组成。
结构的能力； 2）具有应用二叉树解决实际问题的能力。 3、素质目标 养成良好的完成工作任务、团队合作、良好沟通、创新
思维和解决问题的能力。
第1页/共47页
4.1 树的概念 树型结构是一类重要的非线性结构。树型结构是 结点之间有分支，并具有层次关系的结构。它非常类似 于自然界中的树。 树结构在客观世界中是大量存在的，在计算机领 域中也有着广泛的应用，如在编译程序中，用树来表示 源程序的语法结构；在数据库系统可用树来组织信息。 1、树的递归定义：树是n(n≥0)个结点的有限集T，T为 空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的有限子集Tl ，T2，…，Tm，其中每个子集本身又是一棵树，并称 其为根的子树(Subtree)。 注意：树的递归定义刻画了树的固有特性：一棵非空 树是由若干棵子树构成的，而子树又可由若干棵更小的
⑤点。内它树部们，结都而点是T：12B的除的根根子F结树又点。有之显两外然H棵的T互11分不是支相只结交含点的一统子个称树根为{结I}内和点部{EJ结的}，
⑥开其始本结身点又：都根是结只点含又一称个为根开结始点结的点树。。
6
第3页/共47页
2）例结如点：之间的关系
A 第1层
①孩子结点：树中某个结点B 的子C 树的根D 称为第2层该结点的

课件-数据结构讲义(严蔚敏版)第四章 串

课件-数据结构讲义(严蔚敏版)第四章 串
if(pos>0) { n=StrLength(S); m=StrLength(T); i=pos;
while(i<=n-m+1) { SubString(sub,S,i,m);//sub返回S中第i个位置起长m的子串
if(StrCompare(sub,T)!=0) ++i; //串不等,位置后移 else return(i);//返回子串在T中的位置 }//while }//if return(0);//如S中无与T相等的子串 }//index
串复制StrCopy(&T,S)
Status StrCopy(SString &T, SString S) //S是源串，T是目的串 {
for(i=0;i <=S[0];++i)//字符序列的复制 T[i] = S[i];
return OK;
} 串比较StrCompare(S,T)
int StrCompare(SString S,SString T) { for (int i=1;i<=S[0]&&i<=T[0];i++) { if (S[i]!=T[i]) return S[i]-T[i]; return S[0]-T[0];
数据对象：D={ai| ai CharacterSet, i=1,2,…,n, n0} 数据关系：R1={< ai-1 ，ai >｜ ai-1 , ai D，i=1,2,…,n} 基本操作：
StrAssign(&T, chars), DestroyString(&S)
StrCopy(&T,S) , ClearString(&S), Replace(&S,T,V)

数据结构教案第四章

数据结构教案第四章
功能：从串s中删除第start个字符起长度len为的子串
任务二、串存储和实现
一、顺序存储结构（用时20分钟）
顺序存储结构类似于C语言的字符数组，以一组地址连续的存储单元存放串值字符序列，其类型说明如下：
#define MAX 255
charch[MAX]
在数组ch中以字符‘\0’表示字符串的结束.特点是访问容易,
匹配算法1
intindex( char s[ ], char t[ ],intstart )
{inti,eq,m,n;
charsubch[MAX];
m=strlen(s); n=strlen(t);
if ( start<0||n==0||start+n>m ) return(-1);
i=start;
9）判空操作empty( s )
功能：若为空串，则返回1，否则返回0
10）串置空操作ClearString( s )
功能：将s清为空串
11)串插入操作StrInsert( s, start , t)
功能：将串t插入到串s的第start字符之前
12）串删除操作StrDelete( s, start ,len)
6）求子串位置操作index( s, t )
功能：如果s中存在与t相同的子串,则返回s中第1个这样的子串的位置，若不存在返回0
7）替换操作replace( s, t ,v )
功能：由串v替换串s中出现的所有和t相同的不重叠子串；
教
学
过
程
设
计
(续表)
8）复制串操作strcopy(s, t)
功能：由串变量s复制得到串变量t；
两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同；

数据结构课件 第4章数组和广义表

数据结构课件 第4章数组和广义表

4
4.1 多维数组
数组(array)的定义 4.1.1 数组 的定义
是由一组类型相同的数据元素构成的有序集合， 是由一组类型相同的数据元素构成的有序集合， 类型相同的数据元素构成的有序集合 每个数据元素称为一个数组元素（ 每个数据元素称为一个数组元素（简称为元 ），每个元素受 每个元素受n(n≥ 个线性关系的约束 的约束， 素），每个元素受 ≥1)个线性关系的约束， 每个元素在n个线性关系中的序号 个线性关系中的序号i 每个元素在 个线性关系中的序号 1、i2、…、in 、 称为该元素的下标，并称该数组为n维数组 维数组。 称为该元素的下标，并称该数组为 维数组。
12
4.2 矩阵的压缩存储▲
在矩阵中很多值相同的元素并且它们的分布有一定的规律， 在矩阵中很多值相同的元素并且它们的分布有一定的规律， 特殊矩阵, 我们将这样的矩阵称为特殊矩阵 我们将这样的矩阵称为特殊矩阵,如对角阵等 。 若矩阵中有很多零元素称为稀疏矩阵 若矩阵中有很多零元素称为稀疏矩阵 对于这些特殊的矩阵，怎样存储能节省存储空间， 对于这些特殊的矩阵，怎样存储能节省存储空间，同时也能 有效地进行运算
本章学习要求与重点难点
2
本章学习要求： 本章学习要求：
1)了解数组的两种顺序存储表示方法， 1)了解数组的两种顺序存储表示方法，掌握数组在以行 了解数组的两种顺序存储表示方法 为主序的存储结构中的地址计算方法 2)了解矩阵压缩存储的必要性， 2)了解矩阵压缩存储的必要性，掌握特殊矩阵压缩存储 了解矩阵压缩存储的必要性 时的下标变换公式 3) 理解稀疏矩阵的两种压缩存储方法的特点和适用范 围，理解三元组表示的稀疏矩阵在进行转置等运算处理 时使用的处理方法 4)掌握广义表的结构特点、 4)掌握广义表的结构特点、存储表示和基本逻辑运算 掌握广义表的结构特点 求表头、求表尾） （求表头、求表尾） 5)了解有关广义表的递归算法 5)了解有关广义表的递归算法

数据结构第四章

数据结构第四章

S pos
A 插入前
S
T
A
pos 插入后
MAXLEN MAXLEN
T 插入串
省级精品课程配套教材 高等学校计算机类“十二五”规划教材
(2) 插入后串长(st+st+st≥MAXLEN且pos+st＜MAXLEN，则A后移时 会有部分字符被舍
S
A
pos 插入前
MAXLEN 舍弃
如图所示：
0123
4 567
8 … MAXLEN
a b c d e f g h …z
图4.3 串 的 定 长 顺 序 存 储
省级精品课程配套教材 高等学校计算机类“十二五”规划教材
4.2.2 顺序串的基本操作
1. 串插入函数(StrInsert(S, pos,T))
在进行串的插入时，插入位置pos将串分为两部分(假设为S、A，长度为st+1、 st+1)，及待插入部分(假设为T，长度为st+1)，则串由插入前的SA变为STA， 可能有三种情况： (1) 插入后串长(st + st + st)＜MAXLEN，则将A后移st个元素位置， 再将T插入，
18 for(i=0; i<=st; i++)
19
S->ch[i+pos]=T.ch[i];
20 S->last=MAXLEN;
21 }
22 else
23 { /*串T的部分字符序列要舍弃*/
24 for(i=0; i<MAXLEN-pos; i++)
25
S->ch[i+pos]=T.ch[i];
如何标识实际长度 ？可用以下方法
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构第四章第四章习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。

给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));2. 编写算法，实现串的基本操作StrReplace(S,T,V)。

3. 假设以块链结构表示串，块的大小为1，且附设头结点。

试编写算法，实现串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)；StrCat(S,T)； SubString(Sub,S,pos,len)。

4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。

5．已知：S=”(xyz)*”,T=”(x+z)*y”。

试利用联接、求子串和置换等操作，将S转换为T. 6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。

7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。

以下算法用定长顺序串：8．编写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符。

（2）将顺序串r中所有字符按照相反的次序仍存放在r中。

（3）从顺序串r中删除其值等于ch的所有字符。

（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。

（5）从顺序串r中删除所有与串r1相同的子串。

9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。

10．写算法，实现顺序串的基本操作StrCompare(s,t)。

11．写算法，实现顺序串的基本操作StrReplace(&s,t,v)。

实习题1．已知串S和T，试以以下两种方式编写算法，求得所有包含在S中而不包含在T中的字符构成的新串R，以及新串R中每个字符在串S中第一次出现的位置。

（1）利用CONCAT、LEN、SUB和EQUAL四种基本运算来实现。

（2）以顺序串作为存储结构来实现。

2．编写一个行编辑程序EDLINE，完成以下功能：（1）显示若干行：list [[n1]-[n2]]：显示第n1行到第n2行，n1缺省时，从第一行开始，n2缺省时，到最后一行，（2）删除若干行。

del [[n1]-[n2]]： n1、n2说明同（1）。

（3）编辑第n行。

edit n：显示第n行的内容，另输入一行替换该行。

（4）插入一行。

ins n：在第n行之前插入一行。

（5）字符替换。

replace str1,str2, [[n1]-[n2]]：在n1到n2行之间用str2替换str1。

3．设计一个文学研究辅助程序，统计小说中特定单词出现的频率和位置。

第四章答案4.1 设s=’I AM A STUDENT’，t=’GOOD’，q=’WORKER’。

给出下列操作的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7) sub1=’I AM A ’;SubString(sub2,s,7,1) sub2=’ ’;StrIndex(s,4,’A’)=6;StrReplace(s,’STUDENT’,q);s=’I AM A WORKER’;StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=’I AM A GOOD WORKER’。

4.2编写算法，实现串的基本操作StrReplace(S,T,V)。

【解答】算法如下：int strReplace(SString S,SString T, SString V){/*用串V替换S中的所有子串T */int pos,i;pos=strIndex(S,1,T); /*求S中子串T第一次出现的位置*/if(pos = = 0) return(0);while(pos!=0) /*用串V替换S中的所有子串T */{switch(T.len-V.len){case 0: /*串T的长度等于串V的长度*/for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];case >0: /*串T的长度大于串V的长度*/for(i=pos+t.ien;i<S->len;i--) /*将S中子串T后的所有字符S->ch[i-t.len+v.len]=S->ch[i]; 前移T.len-V.len个位置*/for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len;case <0: /*串T的长度小于串V的长度*/if(S->len-T.len+V.len)<= MAXLEN /*插入后串长小于MAXLEN*/ { /*将S中子串T后的所有字符后移V.len-T.len个位置*/for(i=S->len-T.len+V.len;i>=pos+T.len;i--)S->ch[i]=S->ch[i-T.len+V.len];for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=S->len-T.len+V.len; }else{ /*替换后串长>MAXLEN,但串V可以全部替换*/ if(pos+V.len<=MAXLEN){ for(i=MAXLEN-1;i>=pos+T.len; i--)S->ch[i]=s->ch[i-T.len+V.len]for(i=0;i<=V.len;i++) /*用V替换T*/S->ch[pos+i]=V.ch[i];S->len=MAXLEN;}else /*串V的部分字符要舍弃*/{ for(i=0;i<MAXLEN-pos;i++)S->ch[i+pos]=V.ch[i];S->len=MAXLEN;}}/*switch()*/pos=StrIndex(S,pos+V.len,T); /*求S中下一个子串T的位置*/ }/*while()*/return(1);}/*StrReplace()*/附加题：用链式结构实现定位函数。

【解答】typedef struct Node{ char data;struct Node *next;}Node,*Lstring;int strIndex(Lstring S, int pos, Lstring T)/*从串S的pos序号起，串T第一次出现的位置 */{Node *p, *q, *Ppos;int i=0，,j=0;if(T->next= =NULL || S->next = =NULL) return(0);p=S->next;q=T->next;while(p!=NULL && j<pos) /*p指向串S中第pos个字符*/ {p=p->next; j++;}if(j!=pos) return(0);while(p!=NULL && q!=NULL){Ppos=p; /*Ppos指向当前匹配的起始字符*/if(p->data = = q->data){p=p->next; q=q->next;}else /*从Ppos指向字符的下一个字符起从新匹配*/{p=Ppos->next;q=T->head->next;i++;}}if(q= =NULL) return(pos+i); /*匹配成功*/else return(0); /*失败*/}第4章串习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。

给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));[参考答案]StrLength(s)=14; sub1=’I AM A_’; sub2=’_’; StrIndex(s,’A’,4)=6;StrReplace(s,’STUDENT’,q)=’I AM A WORKER’;StrCat(StrCat(sub1,t), StrCat(sub2,q))=’I AM A GOOD WORKER’;2. 编写算法，实现串的基本操作StrReplace(S,T,V)。

3. 假设以块链结构表示串，块的大小为1，且附设头结点。

试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)。

[说明]：用单链表实现。

4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。

5．已知：S=”(xyz)*”,T=”(x+z)*y”。

试利用联接、求子串和置换等操作，将S 转换为T.6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。

7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。

以下算法用定长顺序串：8．写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符。

（2）将顺序串r中所有字符按照相反的次序仍存放在r中。

（3）从顺序串r中删除其值等于ch的所有字符。

（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。

（5）从顺序串r中删除所有与串r1相同的子串。

9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。

[提示]：（1）用静态顺序串（2）先移位，后复制10．写算法，实现顺序串的基本操作StrCompare(s,t)。