当前位置：文档之家 › 数据结构第4章

数据结构第4章

  • 格式：ppt
  • 大小：368.50 KB
  • 文档页数：44

下载文档原格式

  / 44

合集下载

严蔚敏数据结构-第四章 串

严蔚敏数据结构-第四章 串
S1 4 a b c d S2 2 e f T 6 a b c d e f
15
(2)S1串长 最大串长 串长<最大串长 串长 最大串长; S1,S2串长和 最大串长 串长和>最大串长 串长和 最大串长;
S1 6 a b c d e f S2 6 g h i j k l T 8 a b c d e f g h
3
串的抽象数据类型的定义： 串的抽象数据类型的定义： ADT String{ 数据对象： 数据对象：D={ai|ai∈CharacterSet, i=1,2,...,n, n>=0} 数据关系： 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=2,...,n} 基本操作： 基本操作： StrAssign(&T, chars)
11
作业： 作业： 1.用5种串的基本操作（StrAssign、StrCompare、StrLen Concat、SubString）来逻辑实现StrInsert(&S, pos, T)操作 、 操作. ）
Status StrInsert(String S, int pos , String T) { if ……….. return error; , , ); ); ); );
chars是字符串常量。生成一个其值等于chars的串 。 是字符串常量。生成一个其值等于 的串T。 是字符串常量 的串
StrCopy(&T, S)
存在则由串S复制得串 串S存在则由串 复制得串 存在则由串 复制得串T
StrEmpty(S)
存在则若S为空串 串S存在则若 为空串 返回真否则返回假 存在则若 为空串,返回真否则返回假
Sub返回串 的第pos个字符起长度为 返回串S的第 个字符起长度为len的子串 用Sub返回串S的第pos个字符起长度为len的子串

数据结构答案第4章

数据结构答案第4章

第 4 章广义线性表——多维数组和广义表2005-07-14第 4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。

【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。

【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。

⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

【解答】三元组顺序表，十字链表⑸广义表((a), (((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。

【解答】3，4，(a)，((((b),c)),(d))⑹已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。

【解答】Head(Head(Tail(LS)))2. 选择题⑴二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。

数据结构——第4章 串(C#)

数据结构——第4章 串(C#)
将当前链串的所有结点?nstr将q结点插入到尾部将q结点插入到尾部将链串t的所有结点?nstr将q结点插入到尾部尾结点的next置为null返回新建的链串5求子串substrij返回当前串中从第i个字符开始的连续j个字符组成的子串ຫໍສະໝຸດ 第4章 串4.1 串的基本概念
4.1.1 什么是串 串（或字符串）是由零个或多个字符组成的有限序列。 记作str="a1a2…an"（n≥0），其中str是串名，用双引号括 起来的字符序列为串值，引号是界限符，ai（1≤i≤n）是一 个任意字符（字母、数字或其他字符），它称为串的元素， 是构成串的基本单位，串中所包含的字符个数n称为串的 长度，当n=0时，称为空串。
4.2 串的存储结构
4.2.1 串的顺序存储结构－顺序串
和顺序表一样，用一个data数组（大小为MaxSize）和 一个整型变量length来表示一个顺序串，length表示data数 组中实际字符的个数。 定义顺序串类SqStringClass如下：
class SqStringClass { const int MaxSize=100; public char[] data; //存放串中字符 public int length; //存放串长 public SqStringClass() //构造函数,用于顺序串的初始化 { data=new char[MaxSize]; length=0; } //顺序串的基本运算 }
（9）串输出DispStr() 将当前串s的所有字符构成一个字符串并输出。对应的算 法如下：
public string DispStr() { int i; string mystr=""; if (length==0) mystr = "空串"; else { for (i=0;i<length;i++) mystr+=data[i].ToString(); } return mystr; }

数据结构 第4章 矩阵乘法

数据结构 第4章 矩阵乘法

用经典算法。
α11 A α21
α31
α12 α22 α32
α13 α23 α33
α14
α24
B
α34
b11 b21 b31 b41
b12 b22 b32 b42
b13
b23
b33
Q
b43
A*B
c11 c21 c31
c12 c22 c32
c13
c23
c33
4
cij aik bkj ai1b1 j ai2b2 j ai3b3 j ai4b4 j , i 1,2,3, j 1,2,3
ci1 ai1b11 ai2b21 ai3b31 ai4b41 ci2 ai1b12 ai2b22 ai3b32 ai4b42 ci3 ai1b13 ai2b23 ai3b33 ai4b43
注意：对任意k=1,2,3,4，乘 积项aikbkj 必是且只能是cij求 和公式中的一项， 故可改变 计算aikbkj 的次序。
b23
b33 b43
C
A*B
c11 c21
c31
c12 c22 c32
c13
c23
c33
cij aik bkj ai1b1 j ai2b2 j ai3b3 j ai4b4 j , i 1,2,3, j 1,2,3
k 1
经典算法中乘积项aikbkj计算次序
ci1 ai1b11 ai2b21 ai3b31 ai4b41 ci2 ai1b12 ai2b22 ai3b32 ai4b42
b12 b22 b32 b42
b13
b23
C
b33
b43
A*B
c11 c21 c31

数据结构第4章 串

数据结构第4章 串
ring s, SString t)
/*若串s和t相等则返回0；若s>t则返回正数；若s<t则返 回负数*/
{ int i;
for (i=0;i<s.len&&i<t.len;i++)
if (s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]);
初 始 条 件 : 串 S 存 在 ,1≤pos≤StrLength(S) 且 1≤len≤StrLength(S)-pos+1
操作结果:用Sub返回串S的第pos个字符起长度为len的子串
返回主目录
（11）StrIndex(S,T,pos)
初始条件: 串S和T存在,T是非空串, 1≤pos≤StrLength(S)
return(s.len); }
返回主目录
（7）清空函数
StrClear(SString *s) /*将串s置为空串*/ {
s->len=0; }
返回主目录
（8）连接函数
(1) 连接后串长≤MAXLEN，则直接将B加在A的 后面。 (2) 连接后串长>MAXLEN且LA<MAXLEN，则B 会有部分字符被舍弃。 (3) 连接后串长>MAXLEN且LA=MAXLEN，则B 的全部字符被舍弃（不需连接）。
for (i=s->len + t.len-1;i>=t.len + pos;i--)
s->ch[i]=s->ch[i-t.len];
for (i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i];
s->len=s->len+t.len;

数据结构-第4章 串

数据结构-第4章 串
真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章-学习指导材料

《数据结构与算法》第四章串知识点及例题精选串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。

一般记作：s=＂s1 s2 … s n＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；a i(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。

包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256char s[MAXSIZE];则串的最大长度不能超过256。

如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct{ char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqString s;这种存储方式可以直接得到串的长度：s.curlen+1。

如图4.1所示。

s.dataMAXSIZE-1图4.1 串的顺序存储方式12. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。

数据结构第四章串

数据结构第四章串

(2) 置换操作：用联接算法来实现。用在求子串序号（a,b，h）中得到的 ind 将a分成3部分：第一部分是b在a中的第一个位置前的子串substr （a,1,ind－1）;第二部分是b（以c来代替）；第三部分是b在a中的最后一个 位置后的子串substr（a,ind+m,n）。 即 a substr(a,I,ind-1)||c||substr(a,ind+m,n)
4. 2 串的基本运算
对于串的基本操作，许多高级语言均提供了相应的运算或标准 库函数来实现。下面仅介绍几种常用的串运算。 (1)联接(concatenation) 联接是串的最基本，最重要的运算。两个串的联接是将一个串 紧接着放在另一个串的末尾。联接用符号“||”表示。 例如：a＝”bei” b=“jing” a || b=“beijing” (2)求子串(substr) SUBSTR(a，m，n)功能: 从a 中截取子串，从第m个字符到第n个 字符的子串（m<n)。子串应是将串a中取出从标号m开始的连续n －m＋1个字符。 例：SUBSTR(“ABCDEFG”,2,3)＝”BC” 利用求子串及联接两种运算可以完成对串的插入、删除和修改。 例如： a＝“bejing” b=“iy” ，将b插入到a的第二个字符之后 得到新的串s，则 s=substr(a,1,2) || b || substr(a,3,6) =“beiyjing”
（5）置换(repleace) 置换运算repleace(a,b,c)表示在a中搜索b，若b是a的 子串，就以c代替b，若不是，则经置换后，a不变。 例如：a=“monday”, b=“mon”, c=“thurs” repleace(a,b,c)=“thursday” 置换运算是将串a中所有的子串b用c来代替。 在一部分程序设计语言中没有实现，仍可用前三种运 算来完成。 置换算法过程：实现置换运算repleace（a,b,c），同 样也是在a中搜索是否与b相同的子串，若有，以c来代 替，再继续向下搜，直到在a中找不到和b相同的子串 为止。

数据结构第四章：串

数据结构第四章：串

例2、串的定位 、串的定位index(s,t,pos)
在主串s中取从第 个字符起、 相等的子串和T比较 在主串 中取从第pos个字符起、长度和串 相等的子串和 比较，若 中取从第 个字符起 长度和串T相等的子串和 比较， 相等，则求得函数值为i，否则值增1直至 中不存在和串T相等的子串 直至S中不存在和串 相等，则求得函数值为 ，否则值增 直至 中不存在和串 相等的子串 为止。 为止。
}
4.2 串的表示和实现
首先强调：串与线性表的运算有所不同，是以“串的整体” 首先强调：串与线性表的运算有所不同，是以“串的整体”作 为操作对象，例如查找某子串， 为操作对象，例如查找某子串，在主串某位置上插入一个子串 等。 串有三种机内表示方法： 串有三种机内表示方法：
定长顺序存储表示
顺序 存储 ——用一组地址连续的存储单元存储串值的字 用一组地址连续的存储单元存储串值的字 符序列， 静态存储方式 方式。 符序列，属静态存储方式。
4.1 串类型的定义 4.2 串的表示和实现
4.1 串的类型定义
4.1.1串的定义
定义：串(string)是由零个或多个任意字符组成的字 符序列，是数据元素为单个字符的特殊线性表。 的特殊线性表。 是数据元素为单个字符的特殊线性表 记为：an”
(n≥0 )
第4章 串（String） 章 ）
本章主题：串的各种基本运算及其实现 本章主题： 教学目的：了解数据结构的基本概念， 教学目的：了解数据结构的基本概念，理解常用术语 教学重点： 教学重点： 掌握串的基本概念及其基本运算 掌握串的存储结构 主要内容： 主要内容： 1.串的基本概念 2.串的存储结构 2.串的存储结构 3.串的基本运算及其实现 3.串的基本运算及其实现
串其中0<=pos<=strlen(s)-1,且数组 且数组sub至少可容纳 至少可容纳len+1个字符。*/ 个字符。 串其中 且数组 至少可容纳 个字符

数据结构第四章串习题及答案

数据结构第四章串习题及答案

习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“software”,其子串的个数是（）。

A．8 B．37 C．36 D．9二、填空题1．含零个字符的串称为______串。

任何串中所含______的个数称为该串的长度。

2．空格串是指__ __，其长度等于__ __。

3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。

一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。

4．INDEX（‘DATASTRUCTURE’，‘STR’）=________。

5．模式串P=‘abaabcac’的next函数值序列为________。

6．下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；int f((1)__ ______){int i=0,j=0;while (s[j])(2)___ _____;for(j--; i<j && s[i]==s[j]; i++,j--);return((3)___ ____)}7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。

void maxcomstr(orderstring *s,*t; int index, length){int i,j,k,length1,con;index=0;length=0;i=1;while (i<=s.len){j=1;while(j<=t.len){ if (s[i]= =t[j]){ k=1;length1=1;con=1;while(con)if (1) _ { length1=length1+1;k=k+1; }else (2) __;if (length1>length) { index=i; length=length1; }(3)__ __;}else (4) ___;}(5) __} }第四章串一、单项选择题1．B2. B3．B4．C5. C二、填空题1．空、字符2．由空格字符（ASCII值32）所组成的字符串空格个数3．长度、相等、子、主4．55．011223126．（1）char s[ ] (2) j++ (3) i >= j7．[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。

数据结构 第4章

数据结构 第4章



例子

假设要建立一个地址区间长度为13的哈希表，哈希函数为 H(key) = Ord(关键字第一个字母)-1)/2 其中函数Ord求字母在字母表中的序号。例如，字母A在 字母表中的序号为1， Ord(‘A’)=1。 现将关键字依次为Zhao, Qian, Sun, Li, Wu, Chen, Han的 7 个记录插入该哈希表。


例子

例如构造一个数据元素个数n = 60，哈希地址空间长度m = 100 的哈希表。 对关键字分析发现，关键字的第 1、2、3、6位取值比较集中，不 宜作为哈希地址，
…… 8 8 8 8 8 8 8 8 1 1 2 1 2 2 1 1 3 3 7 3 7 7 3 3 1 2 3 4 0 7 8 7 6 9 3 6 4 1 6 8 6 6 8 6 2 0 7 2 3 1 3 6 2 5 8 4 5 8 2
数据结构
广东工业大学 计算机学院
第4章 哈希表
第4章 哈希表


4.1 哈希表的概念 4.2 哈希函数的构造方法

4.2.1 直接定址法 4.2.2 除留余数法 4.2.3 数字分析法 4.2.4 折叠法 4.2.5 平方取中法 4.3.1 开放定址法 4.3.2 链地址法 链地址哈希表的实现 开放定址哈希表的实现
移位叠加 0040 1108 1053 0216 + 9891 (1)2308

Z形叠加 0040 8011 1053 6120 + 9891 (2)5115
4.2.5 平方取中法


平方取中法先取关键字的平方，然后根据哈希表地址区 间长度m的大小，选取平方数的中间若干位作为哈希地 址。通过取平方扩大关键字之间的差别，而平方值的中 间若干位和这个数的每一位都相关，使得不同关键字的 哈希函数值分布较为均匀，不易产生冲突。 设哈希表地址区间长度为1000，可取关键字平方值的中 间三位。

数据结构复习资料 第4章

数据结构复习资料 第4章

第4章栈和队列一、复习要点本章主要讨论3种线性结构：栈、队列与优先级队列。

这3种结构都是顺序存取的表，而且都是限制存取点的表。

栈限定只能在表的一端（栈顶）插入与删除，其特点是先进后出。

队列和优先级队列限定只能在表的一端（队尾）插入在另一端（队头）删除，不过优先级队列在插入和删除时需要根据数据对象的优先级做适当的调整，令优先级最高的对象调整到队头，其特点是优先级高的先出。

而队列不调整，其特点是先进先出。

这几种结构在开发各种软件时非常有用。

本章复习的要点：1、基本知识点要求理解栈的定义和特点，栈的抽象数据类型和在递归和表达式计算中的使用，在栈式铁路调车线上当进栈序列为1, 2, 3, , n时，可能的出栈序列计数，栈的顺序存储表示和链接存储表示，特别要注意，链式栈的栈顶应在链头，插入与删除都在链头进行。

另外，需要理解队列的定义和特点，队列的抽象数据类型和在分层处理中的使用，队列的顺序存储表示（循环队列）和链接存储表示，需要注意的是，链式队列的队头应在链头，队尾应在链尾。

还需要理解优先级队列的定义和特点。

优先级队列的最佳存储表示是堆（heap），本章介绍的表示看懂即可。

2、算法设计➢栈的5种操作（进栈、退栈、取栈顶元素、判栈空、置空栈）的在顺序存储表示下的实现，以及在链接存储表示下的实现。

➢使用栈的后缀表达式计算算法➢循环队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现➢链式队列的进队列、出队列、取队头元素、判队列空、置空队列操作的实现二、难点和重点1、栈：栈的特性、栈的基本运算➢栈的数组实现、栈的链表实现➢栈满及栈空条件、抽象数据类型中的先决条件与后置条件2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示3、队列：队列的特性、队列的基本运算➢队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件➢队列的链表实现：链式队列中的队头与队尾指针的表示、三、习题的解析4-2 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。

数据结构(CC++语言版)第4章串

数据结构(CC++语言版)第4章串

•
else return -1;
•}
34
4.3 模式匹配
35
4.3 模式匹配
朴素的模式匹配——BF算法分析
为什么BF算法时间性能低？
在每趟匹配不成功时存在大量回溯，没有利用已经 部分匹配的结果。
如何在匹配不成功时主串不回溯？
主串不回溯，模式就需要向右滑动一段距离。
如何确定模式的滑动距离？
36
4.3 模式匹配
T[strLength(S1) +i]=S2[i]; strLength(T) =MAXSTRLEN; return FALSE; } }
CompStr (S, T)
初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0；
若S T，则返回值 0； 若S T，则返回值 0
例如：CompStr(data, state) < 0 CompStr(capture, case) > 0
• 由于在计算机科学、生物信息学等许多领域的重要应用， 串模式匹配已经变成了一个非常重要的计算问题
28
4.3 模式匹配
常用的模式匹配算法： • 朴素的模式匹配（BF算法） • 无回溯的模式匹配（KMP算法） 其他模式匹配算法
29
4.3 模式匹配
朴素的模式匹配——BF算法
基本思想：从主串S的第一个字符开始和模式T 的第 一个字符进行比较，若相等，则继续比较两者的后 续字符；否则，从主串S的第二个字符开始和模式T 的第一个字符进行比较，重复上述过程，直到T 中的 字符全部比较完毕，则说明本趟匹配成功；或S中字 符全部比较完，则说明匹配失败。
S1="ab12 cd " S2="ab12" S3=“cd"

数据结构课件 第四章 串和数组

数据结构课件 第四章 串和数组

else {
s->str=(char*)malloc((len+1)*sizeof(char));
//分配空间
if (!s->str) return ERROR;
s->str[0..len]=string_constant[0..len];
//对应的字符赋值
s->length=len;
//赋予字符串长度
串的抽象数据类型定义
functions:
// 有13种之多
StrAssign(&T, chars) // 串赋值，生成值为chars的串T
StrCompare(S,T)
// 串比较，若S>T，返回值大于0…
StrLength(S)
// 求串长，即返回S的元素个数
Concat(&T, S1, S2) // 串连接，用T返回S1＋S2的新串
type unsigned char String[MAX_STRING];
第二种是在程序执行过程中，利用标准函数malloc和free动态
地分配或释放存储字符串的存储单元，并以一个特殊的字符作为字符串
的结束标志，它的好处在于：可以根据具体情况，灵活地申请适当数目
的存储空间，从而提高存储资源的利用率。类型定义如下所示：
（4）串连接 int Concat(STRING *s1,STRING s2) { STRING s; StringAssign(&s,s1->str); //将s1原来的内容保留在s中 len=Length(s1)+Length(s2); //计算s1和s2的长度之和 free(s1->str); //释放s1原来占据的空间 s1->str=(char*)malloc((len+1)*sizeof(char)); //重新为s1分配空间

数据结构-第四章串

数据结构-第四章串

数据结构-第四章串串也叫字符串，它是由零个或多个字符组成的字符序列。

基本内容1 串的有关概念串的基本操作2 串的定长顺序存储结构，堆分配存储结构；3 串的基本操作算法；4 串的模式匹配算法;5 串操作的应⽤。

学习要点1 了解串的基本操作，了解利⽤这些基本操作实现串的其它操作的⽅法；2 掌握在串的堆分配存储结构下，串的基本操作算法；3 掌握串的模式匹配算法；第四章串 4.1 串的基本概念4.2 串存储和实现4.3 串的匹配算法4.4 串操作应⽤举例第四章串 4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 4.4 串操作应⽤举例第四章串4.1 串的基本概念 4.2 串存储和实现 4.3 串的匹配算法 4.4 串操作应⽤举例4. 1 串类型的定义⼀、串的定义1 什么是串串是⼀种特殊的线性表，它是由零个或多个字符组成的有,a2, a3, ... a n’限序列，⼀般记作s = ‘a1其中 s----串名， a1,a2, a3, ... a n----串值串的应⽤⾮常⼴泛，许多⾼级语⾔中都把串作为基本数据类型。

在事务处理程序中，顾客的姓名、地址；货物的名称、产地。

可作为字符串处理，⽂本⽂件中的每⼀⾏字符等也可作为字符串处理。

下⾯是⼀些串的例⼦：（1）a = ‘ LIMING’（2）b = ‘NANJING UNIVERSITY OF SCIENCE &TECHNOLOGY’（3）c = ‘ DATA STRUCTURE’（4）d = ‘’说明：1) 串中包含的字符个数，称为串的长度。

长度为0的串称为空串，它不包括任何字符，上⾯（4）中的串d 是空串,(5)中的e 是包含⼀个空格符的空格串；2）串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。

2 串的有关术语1）⼦串串中任意连续的字符组成的⼦序列称为该串的⼦串例：c = ‘ DATA STRUCTURE’，f=‘DATA’ f是c的⼦串2）⼦串的位置⼦串T 在主串S中的位置是指主串S中第⼀个与T相同的⼦串的⾸字母在主串中的位置。

数据结构课后习题及解析第四章

数据结构课后习题及解析第四章

第四章习题’。

给出下列操作得结果:1、设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKERStrLength(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); Strpare(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.写算法,实现顺序串得基本操作Strpare(s,t)。

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

数据结构 第四章 串

数据结构 第四章 串

第四章串串又称字符串，是一种特殊的线性表，它的每个元素仅由一个字符组成。

计算机上非数值处理的对象基本上是字符串数据。

在较早的程序设计语言中，字符串仅作为输入和输出的常量出现。

随着计算机应用的发展，在越来越多的程序设计语言中，字符串也可作为一种变量类型出现，并产生了一系列字符串的操作。

在信息检索系统、文字编辑程序、自然语言翻译系统等等应用中，都是以字符串数据作为处理对象的。

本章将讨论串的存储结构和基本操作。

4.1 串的基本概念4.1.1 串的自然语言定义串(string)(或字符串)是由零个或多个字符组成的有限序列，一般记为：S="a1 a2 …… a n" (n≥0)其中，S是串名，用双引号括起来的字符串序列是串的值；a i(1≤i≤n)可以是字母、数字或其他字符；串中字符的个数n称为串的长度。

长度为0的串称为空串。

需要注意的是，串值必须用一对双引号括起来，但双引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆。

如"tempt"是个串,tempt则是变量名；"23"是串,而23则是一个常量.串中任意个连续的字符组成的子序列称为该串的子串，如：串S＝"This is a string"，其中"This"是一个子串，"string"也是一个子串。

求子串在串中的起始位置称为子串定位或模式匹配。

例如，设A，B，C为如下三个串：A＝"data"，B="structure"，C＝"data structure"，则它们的长度分别是4,9，14，A和B都是C的子串，A在C中的位置是1，而B在C中的位置是6。

下面注意区别空格串与空串的概念。

在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其他字符中间。

由一个或多个空格组成的串称为空格串，也就是说空格串中只有空格字符，空格串的长度不为零。

数据结构课后题答案(第4章).

数据结构课后题答案(第4章).

数据结构部分课后习题答案第四章4.1广度优先生成树(黑体加粗边:深度拓扑排序序列:v0-v2-v3-v1-v4 4.2广度深度(1(2加边顺序a-b b-e e-d d-f f-c4.3、如图所示为一个有6个顶点{u1,u2,u3,u4,u5,u6}的带权有向图的邻接矩阵。

根据此邻接矩阵画出相应的带权有向图,利用dijkstra 算法求第一个顶点u1到其余各顶点的最短路径,并给出计算过程。

带权有向图:4.4证明在图中边权为负时Dijkstra算法不能正确运行若允许边上带有负权值,有可能出现当与S(已求得最短路径的顶点集,归入S内的结点的最短路径不再变更内某点(记为a以负边相连的点(记为b确定其最短路径时,它的最短路径长度加上这条负边的权值结果小于a原先确定的最短路径长度,而此时a在Dijkstra算法下是无法更新的。

4.5P.198 图中的权值有负值不会影响prim和kruskal的正确性如图:KRUSKAL求解过程:4.6 Dijkstra算法如何应用到无向图?答:Dijkstra算法通常是运用在带非负权值的有向图中,但是无向图其实就是两点之间两条有向边权值相同的特殊的有向图,这样就能将Dijkstra算法运用到无向图中。

4.7用FLOYD算法求出任意两顶点的最短路径(如图A(6所示。

A(0= A(1= A(2=A(3= A(4=A(5= A(6= V1 到 V2、V3、V4、V5、V6 往返路径长度分别为 5，9，5，9，9，最长为 9，总的往返路程为 37 同理 V2 到 V1、V3、V4、V5、V6 分别为 5，8，4，4，13，最长为 13，总和 34 V3 对应分别为 9，8，12，8，9，最长为 12，总和为 46 V4 对应分别为 5，4，12，4，9，最长为 12，总和为 34 V5 对应分别为9，4，8，4，9，最长为 9，总和为 34 V6 对应分别为 9，13，9，9，9，最长为13，总和为 49 题目要求娱乐中心“距其它各结点的最长往返路程最短” ，结点V1， V5 最长往返路径最短都是 9。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
北华航天工业学院计算机系 制作
4.2.4 基于堆结构的串的基本运算
总结： 总结： 以上堆空间和算法是由算法编写者自己 设计和编写来实现的，在这里， 设计和编写来实现的，在这里，重点介绍这 种存储的处理思想， 种存储的处理思想，很多问题及细节尚未涉 如废弃串的回收、自由区的管理等。 及，如废弃串的回收、自由区的管理等。 在常用的高级语言及开发环境中， 在常用的高级语言及开发环境中，大多 数系统本身都提供了串类型及大量的库函数 提供了串类型及大量的库函数， 数系统本身都提供了串类型及大量的库函数， 用户可直接使用。 用户可直接使用。
北华航天工业学院计算机系 制作
4.2.3 串的堆存储结构
建立索引项的方法： 建立索引项的方法： 1.带串长度的索引表 1.带串长度的索引表 索引项的结点类型： 索引项的结点类型：
typedef struct { char name[MAXNAME]; /*串名 串名*/ 串名 int length; /*串长 串长*/ 串长 char *stradr; /*起始地址 起始地址*/ 起始地址 } LNode;
北华航天工业学院计算机系 制作
本章内容
4.1 串及其基本运算
4.2 串的存储结构及基本运算
4.3 模式匹配算法
北华航天工业学院计算机系 制作
4.2 串的存储结构及基本运算
4.2.1 串的定长顺序存储结构 4.2.2 定长顺序串的基本运算 4.2.3 串的堆存储结构 4.2.4 基于堆结构的串的基本运算
建立索引项的方法： 建立索引项的方法： 2.带未尾指针的索引表 2.带未尾指针的索引表
北华航天工业学院计算机系 制作
4.2.3 串的堆存储结构
建立索引项的方法： 建立索引项的方法： 3.带特征位的索引表 3.带特征位的索引表 索引项的结点类型为： 索引项的结点类型为：
typedef struct { char name[MAXNAME]; int tag; /*特征位 特征位*/ 特征位 union /*起始地址或串值 起始地址或串值*/ 起始地址或串值 { char *stradr; char value[4]；}uval; ； } TNode;
北华航天工业学院计算机系 制作
4.2.1 串的定长顺序存储结构
定长顺序存储结构的实现： 用一组地址连 定长顺序存储结构的实现 ： 用一 组地址连 续的存储单元存储串值中的字符序列 存储串值中的字符序列。 续的存储单元存储串值中的字符序列。 定长是指按预定义的大小， 定长是指按预定义的大小 ， 为每一个串变 量分配一个固定长度的存储区 固定长度的存储区。 量分配一个固定长度的存储区。 通常用数组实现。 通常用数组实现。 用数组实现
北华航天工业学院计算机系 制作
4.2 串的存储结构及基本运算
4.2.1 串的定长顺序存储结构 4.2.2 定长顺序串的基本运算 4.2.3 串的堆存储结构 4.2.4 基于堆结构的串的基本运算
北华航天工业学院计算机系 制作
4.2.3 串的堆存储结构
串索引存储： 串索引存储：将所有的串存储在一个大的 存储空间内，为区分每个串， 存储空间内，为区分每个串，给每个串建 立一个索引项，多个索引项组成索引表。 立一个索引项，多个索引项组成索引表。 建立索引项的方法： 建立索引项的方法： 1.带串长度的索引表 1.带串长度的索引表 2.末尾指针的索引表 2.末尾指针的索引表 3.带特征位的索引表 3.带特征位的索引表
北华航天工业学院计算机系 制作
4.2.3 串的堆存储结构
堆结构
堆空间示意图
北华航天工业学院计算机系 制作
4.2.3 串的堆存储结构
堆结构类型定义
设堆空间： 设堆空间： char store[SMAX+1]; 自由区指针： 自由区指针：int free; 串的索引项结点类型： 串的索引项结点类型： typedef struct { int length; int stradr; } HString;
北华航天工业学院计算机系 制作
/*串长 串长*/ 串长 /*起始地址 起始地址*/ 起始地址
4.2 串的存储结构及基本运算
4.2.1 串的定长顺序存储结构 4.2.2 定长顺序串的基本运算 4.2.3 串的堆存储结构 4.2.4 基于堆结构的串的基本运算
北华航天工业学院计算机系 制作
4.2.4 基于堆结构的串的基本运算
北华航天工业学院计算机系 制作
本章内容
4.1 串及其基本运算
4.2 串的存储结构及基本运算
4.3 模式匹配算法
2、求子串
StrSub (char *t, char *s, int i, int len)
3、串比较
int StrComp(char *s1, char *s2) 注意：字符串以‘\0’作为结束标志。 注意：字符串以‘ 作为结束标志。 作为结束标志
北华航天工业学院计算机系 制作
4.2.2 定长顺序串的基本运算
串连接 完成的功能： 把串s 完成的功能 ： 把串 s1 和 s2 首尾连接成一个 新串s 新串s。 分析： 分析： 判断是否会发生溢出 发生溢出。 （ 1 ） 判断是否会 发生溢出 。 S 的空间是否 足够存储s 的所有元素。 足够存储s1和s2的所有元素。 连接过程： 先将s 的所有元素送到s （ 2 ） 连接过程 ： 先将 s1 的所有元素送到 s 再将s 的所有元素送到s 中；再将s2的所有元素送到s中现有元素的后 置结束符。 面；给s置结束符。
北华航天工业学院计算机系 制作
4.2.4 基于堆结构的串的基本运算
int StrCopy(Hstring *s1,Hstring s2) { 串赋值 int i; 算法： 算法： if (free+s2.length-1>SMAX) return 0 ; else { for(i=0; i<s2.length;i++) store[free+i]=store[s2.stradr+i]; s1->length=s2.length; s1->stradr=free; free=free+s2.length; return 1; } }
typedef struct { char name[MAXNAME]; /*串名 串名*/ 串名 char *stradr; char *enadr } ENode;
北华航天工业学院计算机系 制作
/*起始地址 起始地址*/ 起始地址 /*末尾地址 末尾地址*/ 末尾地址
4.2.3 串的堆存储结构
串赋值 完成的功能：将堆store中的一个串s2 复制 中的一个串s 完成的功能 ： 将堆 中的一个串 到一个新串s 到一个新串s1中。 分析： 分析： 判断堆中是否有足够空间存储串s （1）判断堆中是否有足够空间存储串s1； 的所有元素送到堆中给s （2）将s2的所有元素送到堆中给s1分配的 空间中； 空间中； 建立新串s 的索引项； （3）建立新串s1的索引项； 修改自由区指针的值。 （4）修改自由区指针的值。
北华航天工业学院计算机系 制作
4.2.2 定长顺序串的基本运算
int串连接 StrConcat1(char s1[ ], char s2[ ], char s[ ]) { int i=0 , j, len1, len2; 算法 len1= StrLength(s1); len2= StrLength(s2) if (len1+ len2>MAXSIZE-1) return 0 ; j=0; while(s1[j]!=’\0’) { s[i]=s1[j]; i++; j++; } j=0; while(s2[j]!=’\0’) { s[i]=s2[j]; i++; j++; } s[i]=’\0’; return 1; }
typedef struct { char data[MAXSIZE]; int curlen; //下标 下标 } SeqString;
例：SeqString s; 串的长度=s.curlen+1
北华航天工业学院计算机系 制作
4.2.1 串的定长顺序存储
如何标识实际长度？ 如何标识实际长度？
用指针指向串最后一个字符。 用指针指向串最后一个字符。
⒈求串长 StrLength(s) ⒉串赋值 StrAssign(s1,s2) ⒊连接操作 StrConcat (s1,s2,s) 或 StrConcat (s1,s2)
⒋求子串 SubStr (s,i,len)
⒌串比较 StrCmp(s1,s2) ⒍子串定位 StrIndex(s,t) ⒎串插入 StrInsert(s,i,t) ⒏串删除 StrDelete(s,i,len) ⒐串替换 StrRep(s,t,r)
数据结构
—— 第4章 串
目标
理解串的定义； 理解串的定义； 理解串的存储方式； 理解串的存储方式； 掌握模式匹配算法。 掌握模式匹配算法。
北华航天工业学院计算机系 制作
本章内容
4.1 串及其基本运算
4.2 串的存储结构及基本运算
4.3 模式匹配算法
北华航天工业学院计算机系 制作
4.1 串及其基本运算
#define MAXSIZE 100 char ch[MAXSIZE]; 如何标识字符串 的实际长度？ 的实际长度？
北华航天工业学院计算机系 制作
4.2.1 串的定长顺序存储
标识实际长度的方法 类似顺序表，用一个指针来指向最后一 1. 类似顺序表，用一个指针来指向最后一 个字符，串描述如下： 个字符，串描述如下：
北华航天工业学院计算机系 制作
4.2 串的存储结构及基本运算
4.2.1 串的定长顺序存储结构 4.2.2 定长顺序串的基本运算 4.2.3 串的堆存储结构 4.2.4 基于堆结构的串的基本运算