数据结构(串、数组和广义表)

发布于 20 天前  20 次阅读


前言

串:内容首先的线性表(数据元素只能是字符)
数组,广义表:线性结构的推广

4.1 串

4.1.1串的定义

串(String) ----零个或多个任意字符组成的有限序列

file

子串:串中任意个连续字符组成的子序列称为该串的子串
主串:包含子串的串相应的称为主串
字符位置:字符在序列中的序列号为该字符串在串中的位置
子串位置:子串第一个字符在主串中的位置
空格串:由一个或多个空格组成的串(与空串不同)
串相当:当且仅当串的长度相等并且各个位置上的字符都相等时,这两个串才是相等的。
所有的空串都是相等的。

file

file

file

4.1.2 案例引入

file

file

4.1.3 串的类型定义、存储结构及运算

file

file

file

串的顺序存储结构

file

串的链式存储结构

file

file

4.1.3 串的模式匹配算法

file

file

file

file

file

file

file

file

file

file

file

file

file

KMP算法时间复杂度:O(N+M)

file

file

file

4.2 数组

数组:按照一定格式排列起来的
具有相同类型的数据元素的集合
以为数组:若线性表中的数据元素为非结构的简单元素,则称为一维数组
一维数组的逻辑结构:线性结构。定长的线性表。
声明格式:数据类型 变量名称[长度]
例如:int num[5] = {0,1,2,3,4};

file

file

file

4.2.1 数组的抽象数据类型定义

file

file

file

4.2.2 数组的顺序存储

file

file

file

file

file

file

file

file

file

file

file

file

4.2.3 特殊矩阵的压缩存储

file

file

file

file

file

file

file

file

file

file

file

稀疏矩阵的链式存储结构:十字链表

file

file

file

4.3 广义表

file

file

file

file

file

file

file

4.4 案例分析与实现

file

file

file


擦肩而过的概率