《小白学数据结构》课件——第四章 数组、串和广义表.pptx

主讲教师：

第四章数组、串和广义表

1.数组的定义及顺序存储

数组的定义

线性数据存储结构存储逻辑关系为一对一的数据存储的数据元素不可分线性表、栈和队列线性数据存储结构可以包含多种“一对一”的逻辑关系存储的数据元素可分数组数组的定义

数组的定义包含的元素具有“一对一”的逻辑关系4个序列也具有“一对一”的逻辑关系

数组的定义?特点1：数组中的数据元素的数据类型相同特点2：数组是一种随机存取结构，只要给定一组下标，就可以访问与其对应的数组元素特点3：数组中数据元素的个数是固定的

数组一维数组二维数组...n维数组

数组的定义一维数组是所有数据元素属于同一类型、固定长度的线性表。?

二维数组中的数据元素是一维数组中的一维数组

数组的表现形式

例：二维数组的不同表示二维数组的不同表示形式(a)m×n矩阵形式表示

例：二维数组的不同表示(a)m×n矩阵形式表示(b)列向量的一维数组(c)行向量的一维数组二维数组的不同表示形式

数组的存储结构

顺序存储结构链式存储结构数组被建立起来，数据元素个数及元素之间的对应关系就不再发生改变。

顺序存储结构

无论数组的维度是多少，数组中的数据类型都必须一致数组一旦建立，它的维度将不再改变数组存储结构不会对内部的元素做插入和删除操作数组顺序存储结构特性

常见的操作初始化数组销毁数组取数组中的元素修改数组中的元素

a0a1…an-1一维数组的存储结构一维数组的存储结构，采用内存中一段连续的存储单元进行存储。?

?一维数组的存储结构?

以列序为主序A以行序为主序B多维数组的存储结构以二维数组存储为例说明：

二维数组的存储结构…?

以行序为主序的存储结构?共存储m个一维数组的数据元素对应任一数据元素的存储单位地址，可以通过这个公式求出:

以列序为主序的存储结构共存储n个一维数组的数据元素?对应任一数据元素的存储单位地址，可以通过这个公式求出:

数组的存储结构学生个人信息表学生个人成绩表公司员工信息的存储一组照片的存储

总结数组的定义数组的存储结构

总结

2.串的基本概念与存储

串的基本概念串的存储结构

串的基本概念串的定义串，即字符串（String），是一种特殊的线性表，是由零个或多个字符组成的有限序列。一般记为：S=“s1s2…sn”串名串的值n是串中字符的个数称为串的长度si(1≤i≤n)即字符串的值，可以是字母、数字、汉字或其他字符。(串的下标从1开始)

串的基本概念将一个串中若干个连续的字符组成的子序列称为该串的子串。包含子串的串，成为主串。长度为0的串，不包含任何字符称为空串。字符在序列中的序号，称为字符在该串中的位置。子串和主串空串和空白串S1=“hello”S=“helloworld”称S1是S的子串，S是S1的主串。位置一个串中的字符序列都是空格，称为空白串。子串在主串中的位置，以子串的第一个字符在主串中的位置来表示。

串的基本概念串与线性代表的区别线性代表串数据对象是单个字符基本操作对象是单个数据元素基本操作是查找、插入、删除、修改某个数据元素等数据对象是字符集基本操作对象是串的部分或整体基本操作是查找、插入、删除、修改某个子串等

串的存储结构串的顺序存储结构定长顺序串堆串串的链式存储结构块链存储结构

串的存储结构定长顺序存储结构，又称静态数组结构。静态数组是指用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译的时候确定的，在运行时不可改变，所以也称为定长数组结构。定长顺序存储结构

串的存储结构堆式顺序存储结构，又称动态数组结构。动态数组是指用动态内存分配的方法定义的数组。把串中字符按逻辑次序，存放在这组地址连续的存储单元里，此可用空间称为“堆”的共享空间，这种结构也称为堆分配顺序串。堆式顺序存储结构

串的存储结构链式存储结构串，是一种特殊的线性表，链表也适用于串。用链表存储串值时，每个结点可以存放一个字符，也可以存放多个字符。结点大小为1的链表：最后结点不一定全被串值占满，通常补上#结点大小为4的链表：在串的操作中，一般将串作为一个整体，在存储时与链表还有所不同。

串的存储结构块链结构headtail以链表存储串值时:头指针尾指针当前串的长度

总结串的基本概念顺序和链式存储结构

总结有一分耕耘，就有一分收获。

3.串的基本运算

目录串的基本操作串的模式匹配算法

串的基本操作

一、求串长若s是一个空串，则返回值为0。Strlen(s)非负整数返回串s的长度

二、串赋值StringAssign(s,string_constant)给串s赋值串变量串常量串常量或经过适当运算所得到的串值

三、串复制St