青岛理工大学数据结构课件第四章串

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是哪个串的子串？在主串中的位置是多少？

第四章串串是字符串的简称，可以将它看作一种特殊的线性表，其数据元素仅由一个字符组成。

计算机非数值处理的对象经常是字符串，如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事件处理程序中，顾客的姓名、地址、货物的产地、名称等，一般也是作为字符串处理的。

另外串还具有自身的特性，常常把一个串作为一个整体来处理，因此，一般线性表和串的操作有较大区别，本章主要讨论串的基本概念和存储结构，通过本章的学习，读者应掌握串的一些基本运算。

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

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

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

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

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

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

例如：A＝”China Beijing”，B=”Beijing”，C=”China”，则它们的长度分别为13、7和5，B和C是A的子串，B在A中的位置是7，C在A中的位置是1。

由一个或多个空格字符组成的串，称为空格串，其长度为串中空格字符的个数。

请注意空串和空格串的区别。

4.1.2 串的基本运算串的运算有很多，下面介绍部分基本运算：１．求串长StrLength(s)操作条件：串s存在操作结果：求出串s的长度。

２．串赋值StrAssign(s1,s2)操作条件：s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值，是一个串变量称为串拷贝）。

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 串的存储结构
串是一种特殊的线性表，其存储结构与线性表的存储结构 类似，只不过组成串的结点是单个字符。串的存储结构表示

将电路中的元件和连线抽象为图中的顶点和 边，利用图算法进行电路分析和优化。
路由算法
生物信息学
利用图数据结构表示计算机网络中的拓扑结 构，利用最短路径算法进行路网络、 基因调控网络等复杂生物系统，进行生物信 息学分析和挖掘。
05
查找与排序
查找的基本概念与分类
选择排序算法
简单选择排序
每次从待排序的数据元素中选出最小（或最大）的一个 元素，存放在序列的起始位置，直到全部待排序的数据 元素排完。
堆排序
利用堆这种数据结构所设计的一种排序算法，是选择排 序的一种。可以利用数组来模拟堆的结构，通过构造大 顶堆或小顶堆来实现排序。
归并排序算法
归并排序的思想
将两个（或更多）有序表合并成一个新的有序表，即把 待排序序列分为若干个子序列，每个子序列是有序的。 然后再把有序子序列合并为整体有序序列。
开放寻址法、链地址法等。
排序的基本概念与分类
排序的定义
将一组无序的记录序列调整为有序的记录序 列。
排序的分类
内部排序和外部排序，内部排序包括插入排 序、交换排序、选择排序、归并排序等。
插入排序算法
要点一
直接插入排序
每次将一个待排序的元素插入到前面已经排好序的序列中， 寻找合适的位置。
要点二
希尔排序
二叉树的遍历算法
先序遍历
先访问根节点，然后遍 历左子树，最后遍历右
子树。
中序遍历
先遍历左子树，然后访 问根节点，最后遍历右
子树。
后序遍历
层次遍历
先遍历左子树，然后遍 历右子树，最后访问根
节点。
按照层次顺序从上到下、 从左到右遍历二叉树中
的所有节点。
树和森林的遍历算法