数据结构课件4

将当前链串的所有结点?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; }

pos len
堆分配存储特点：仍用一组连续的存储单元来存放串，
但存储空间是在程序执行过程中动态分配而得。
思路：利用malloc函数合理预设串长空间。
有的语言允许对串常量命名，以使程序易读、易写。 【例】C++中，可定义串常量path
const char path[]="dir/bin/appl";
5
练1：串是由
字符组成的序
列，一般0记个或多个
为 S=’a1a2……an’
练2：现。有以下4个字符串：
a =‘BEI’
b =‘JING’ c = ‘BEIJING’
数据结构课程的内容
第4章 串 （String）
1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式
4.1 串类型的定义
4.2 串的表示和实现 4.3 串的模式匹配算法
4.1 串类型的定义
串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为单个字符的特殊线性表。
记为： s =‘ a1 , a2 , …….. , an’ (n≥0 )
讨论：想存放超长字符串怎么办？——静态数组有缺陷！
改用动态分配的一维数组—— “堆”！
例：用顺序存储方式实现求子串函数SubString(&Sub, S, pos,
len)
将串S中从第pos个字符开始长度为len的字符序列复 制到串Sub中（注：串Sub的预留长度与Ssub, SString S, int pos, int len )
d
= ‘问B：EI①JI他NG们’各自的长度？ a =3，b =4，c = 7，d=8
② a是哪个串的子串？在主串中的位置是多少？

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;

30
树形数据结构的查找算法
二叉排序树的查找
从根节点开始，若查找值小于当前节点 值，则在左子树中查找；若大于当前节 点值，则在右子树中查找。
VS
平衡二叉树的查找
在保持二叉排序树特性的基础上，通过旋 转操作使树保持平衡，提高查找效率。
2024/3/26
31
散列表的查找算法
散列函数的设计
将关键字映射为散列表中位置的函数。
过指针来表示。
链式存储的特点
逻辑上相邻的元素在物理位置上 不一定相邻；每个元素都包含数
据域和指针域。
链式存储的优缺点
优点是插入和删除操作不需要移 动元素，只需修改指针；缺点是
存储密度小、空间利用率低。
2024/3/26
11
线性表的基本操作与实现
插入元素
在线性表的指定位 置插入一个元素。
查找元素
在线性表中查找指 定元素并返回其位 置。
自然语言处理的应用
在自然语言处理中，需要处理大量的文本数据，数据结构中的字符 串、链表、树等可以很好地支持文本的处理和分析。
41
数据结构在计算机网络中的应用
2024/3/26
路由算法的实现
计算机网络中的路由算法需要大量的数据结构支持，如最短路径 树、距离向量等。
网络流量的控制
在计算机网络中，需要对网络流量进行控制和管理，数据结构中的 队列、缓冲区等可以很好地支持流量的控制。
37
06
数据结构的应用与拓展
2024/3/26
38
数据结构在算法设计中的应用
01
作为算法设计的基 础
数据结构为算法提供了基本操作 和存储方式，是算法实现的重要 基础。
02
提高算法效率

2．基本运算在顺序存储结构上的实现
在顺序存储结构中，串的类型定义描述如下：
#define MaxLen <最大串长>; //定义能处理的最大的串长度
typedef struct {
char str[MaxLen];
//定义可容纳MaxLen个字符的字符数组
int curlen;
//定义当前实际串长度
char data[4]; struct node *next; } lstring;
采用链式存储结构（结点大小为1），实现串的联接、求子串
以及串的置换基本运算见教科书 P83 。
2019/8/31
19
4.2.3 串的堆分配存储结构及其基本运算的实现
1．堆分配存储结构
堆存储结构的特点是，仍以一组空间足够大的、地址连续的 存储单元存放串值字符序列，但它们的存储空间是在程序执行过 程中动态分配的。所以也称为动态存储分配的顺序表。每当产生 一个新串时，系统就从剩余空间的起始处为串值分配一个长度和 串值长度相等的存储空间。
typedef struct Chunk {
//结点结构
char str[CHUNKSIZE];
struct Chunk *next;
} Lstring;
一个链串由头指针唯一确定。
这种结构便于进行插入和删除运算，但存储空间利用率太低。
为了提高存储密度，可使每个结点存放多个字符。通常将结
点数据域存放的字符个数定义为结点的大小，显然，当结点大小
}
}
return(0);
}2019/8/31
10
4.2 串的存储结构
串是一种特殊的线性表，其存储结构与线性表的存储结构 类似，只不过组成串的结点是单个字符。串的存储结构表示

第二章 线性表
1
线性表的顺序存储结构
2
线性表的顺序存储结构使用数组来存储元素，
可以快速随机访问元素。
3
线性表的常见操作
4
线性表支持常见的操作，包括插入、删除、 查找等，可以灵活地操作其中的元素。
线性表的定义和实现
线性表是一种数据结构，它包含一组有序的 元素，可以通过数组和链表来实现。
线性表的链式存储结构
线性表的链式存储结构使用链表来存储元素， 支持动态扩展和插入删除操作。
第三章 栈与队列
栈的定义和实现
栈是一种特殊的线性表，只能在一 端进行插入和删除操作，遵循后进 先出的原则。
队列的定义和实现
队列是一种特殊的线性表，只能在 一端进行插入操作，在另一端进行 删除操作，遵循先进先出的原则。
栈和队列的应用场景和操作
哈希表是一种高效的查找数据结构， 通过哈希函数将关键字映射到数组 中，实现快速查找。
排序算法包括冒泡排序、插入排序 和快速排序等，可以根据数据规模 和性能要求选择合适的算法。
结语
数据结构的学习心得 总结
学习数据结构需要掌握基本概念 和常见操作，通过实践和练习加 深理解和熟练度。
下一步学习计划的安 排
在掌握基本数据结构的基础上， 可以进一步学习高级数据结构和 算法，提升编程技能。
相关学习资源推荐
推荐一些经典的数据结构教材和 在线学习资源，如《算法导论》 和LeetCode等。
栈和队列在计算机科学中有许多应 用，如函数调用、表达式求值和作 业调度等。
第四章 树与二叉树
树的定义和性质
树是由节点和边组成的一种非线性数据结构，每个 节点可以有多个子节点。
二叉树的遍历方式
二叉树的遍历方式包括前序遍历、中序遍历和后序 遍历，可以按不同顺序输出节点的值。

数据结构是计算机中存储、组织 数据的方式，它定义了数据元素 之间的逻辑关系以及如何在计算 机中表示这些关系。
数据结构分类
根据数据元素之间关系的不同， 数据结构可分为线性结构、树形 结构、图形结构等。
4
数据结构重要性
01
02
03
提高算法效率
合理的数据结构可以大大 提高算法的执行效率，减 少时间和空间复杂度。
33
案例三：最小生成树在通信网络优化中应用
Kruskal算法
基于并查集实现，按照边的权值从小到大依次添加边，直到生成 最小生成树。
Prim算法
从某一顶点开始，每次选择与当前生成树最近的顶点加入，直到 所有顶点都加入生成树。
通信网络优化
最小生成树算法可用于通信网络优化，通过选择最优的通信线路 和节点，降低网络建设和维护成本。
2024/1/28
简化程序设计
数据结构的设计和实现可 以简化程序设计过程，提 高代码的可读性和可维护 性。
解决实际问题
数据结构是解决实际问题 的基础，如排序、查找、 图论等问题都需要依赖于 特定的数据结构。
5
相关术语解析
数据元素
数据元素是数据的基本 单位，通常作为一个整
体进行考虑和处理。
2024/1/28
02
队列的基本操作包括入队（enqueue）、出队（ dequeue）、查看队首和队尾元素等。
03
队列的特点
2024/1/28
04
数据从队尾入队，从队首出队。
05
队列中元素的插入和删除操作分别在两端进行，因此也称 为双端操作。
06
队列中没有明显的头尾标记，通常通过计数器或循环数组 等方式实现。
15
栈和队列应用举例

T 插入串
S pos
T 插入后
A
A串部分被舍弃
MAXLEN
(3) 插入后串长(st+st+st≥MAXLEN且pos+st＞MAXLEN，则A全部 字符被舍弃(不需后移)，并且T在插入时也有部分字符被舍弃
S pos
A 插入前
S pos
T 插入后
MAXLEN 舍弃
T 插入串
S.ch 0 1 2 3 4 5 6 7 8 9 10 … abcde fgh i j k
st
MAXLEN-1 …
串的长度st+1
省级精品课程配套教材 高等学校计算机类“十二五” 规划2教. 在材串尾存储一个特殊字符作为串的终结符
比如C语言中用’\0’来表示串的结束。 char s[MAXLEN];
5 { /*连接后串长小于MAXLEN */
6 for(i=S->last; i<=S->last+st; i++)
7
S->ch[i+1]=T.ch[i-S->last];
8 S->last=S->last+st+1;
省级精品课程配套教材
高等学校计算机类“十二五”
规划教材
第四章 串
1．教学目的：
掌握串的定义、基本运算的实现及基本串匹配算法。
2．教学要求：
①理解串的七种基本运算的定义。 ②掌握利用这些基本运算来实现串的其它各种运算的方法。 ③掌握在顺序存储结构上实现串的各种操作的方法。 ④理解KMP算法，了解NEXT函数和改进NEXT函数的定义和计算。 ⑤理解串名的存储映象和在堆存储结构实现串操作的方法。

• (12)StrReplace(S,T,pos,len)：串替换操作。当1≤pos≤StrLength(S)且0≤len≤StrLength(S)pos+1时，用串T替换串S中从第pos个字符开始的len个字符。
• (13)StrDestroy(S)：串销毁操作。销毁串S。
10
第10页/共33页
4.2 串的存储结构
4.1 串的定义及基本操作
• 串即字符串，计算机处理的对象分为数值数据和非数值数据，字符串是最基本的非数值数据。 • 字符串的应用非常广泛，它是许多软件系统(如字符编辑、情报检索、词法分析、符号处理、自然语言翻译
等系统)的操作对象。 • 在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的。字符
• 线性表的顺序和链式存储结构对于串都是适用的。但任何一种存储结构对于串的不同运 算并非都是十分有效的。
• 对于串的插入和删除操作，顺序存储结构是不方便的，而链式存储结构则显得方便些。 如果访问串中单个字符，对链表来说是不困难的；当要访问一组连续的字符时，用链式 存储结构要比用顺序存储结构麻烦。
11
9
第9页/共33页
串的基本操作
• (10)SubString(Sub,S,pos,len)：求子串操作。若存在位置1≤pos≤StrLength(S)且 1≤len≤StrLength(S)-pos+1，则用Sub返回串S的第pos个字符起长度为len的子串。
• (11)StrIndex(S,T)：串定位操作。若串S中存在和串T相同的子串，则返回它在串S中第一次出现的位 置；否则返回0。
•
同样存储S=＂
String Structure＂，用
紧凑格式一个地址能存四

l->next=NULL; return 1;
}
L
L∧
L∧
L∧
L∧
∧
p->next=l->next;
ll-->>nneexxtt==pp;; cciinn>>>>cchh;;
a
b
c
d
e∧
p
p
p
p
p
}
算法2.10 前插法创建单链表 S3_2
}
TKS 8 18:18
2、查找
(1) 算法2.6 在带头结点的单链表l中查找第i个元素
r->next=p;
p
p
p
p
p
rr==pp;; cciinn>>>>cchh;;
算法2.11 后插法创建单链表 S3_1
}
}
TKS 7 18:18
(3) 算法2.11 前插法创建单链表及其演示
void createlist_l(linklist l) int initlist_l(linklist
当输入‘*’时结束，‘*’不是元素。
TKS 6 18:18
(2) 算法2.11 后插法创建单链表及其演示
void createlist_l(linklist l) int initlist_l(linklist
{ // 输入若干个元素的值，后插 &l)
// 法建立带表头结点的单链表 { // 生成新结点作为头结点，
存储前趋结 点的地址
指针域 数据域 指针域
结点
2、双向链表的存储结构
typedef struct dulnode { ElemType data;

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分配空间

重要性
良好的数据结构可以带来更高的运 行或存储效率，是算法设计的基础， 对程序设计的成败起到关键作用。
常见数据结构类型介绍
线性数据结构
如数组、链表、栈、队 列等，数据元素之间存
在一对一的关系。
树形数据结构
如二叉树、多叉树、森 林等，数据元素之间存
在一对多的关系。
图形数据结构
由顶点和边组成，数据 元素之间存在多对多的
队列定义、特点及应用场景
队列的特点 只能在队尾进行插入操作，队头进行删除操作。
队列是一种双端开口的线性结构。
队列定义、特点及应用场景
应用场景 操作系统的任务调度。 缓冲区的实现，如打印机缓冲区。
队列定义、特点及应用场景
广度优先搜索（BFS）。
消息队列和事件驱动模型。
串定义、基本操作及实现方法
最短路径问题 求解图中两个顶点之间的最短路径，即路径上边 的权值之和最小。
3
算法介绍 Prim算法、Kruskal算法、Dijkstra算法、Floyd 算法等。
拓扑排序和关键路径问题探讨
拓扑排序
对有向无环图（DAG）进行排序， 使得对每一条有向边(u,v)，均有
u在v之前。
关键路径问题
求解有向无环图中从源点到汇点 的最长路径，即关键路径，它决
遍历二叉树和线索二叉树
遍历二叉树
先序遍历、中序遍历和后序遍历。遍历算 法可以采用递归或非递归方式实现。
VS
线索二叉树
利用二叉链表中的空指针来存放其前驱结 点和后继结点的信息，使得在遍历二叉树 时可以利用这些线索得到前驱和后继结点， 从而方便地遍历二叉树。
树、森林与二叉树转换技巧
树转换为二叉树
加线、去线、层次调整。将树中的每个结点的所有孩子结点用线连接起来，再去掉与原结点相连的线，最后 将整棵树的层次进行调整，使得每个结点的左子树为其第一个孩子，右子树为其兄弟结点。