数据结构 串与数组.ppt

第4章 串和数组 本章主要介绍下列内容： 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储 退出 4.1 串 串的定义和基本运算 串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。 串一般记作： s= “a1a2...an” (n?0) 串中字符的数目n被称作串的长度。当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。 s1= “” s2= “ ” 子串、主串： 串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。 a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcometo” 子串的位置：子串在主串中第一次出现的第一个字符的位置。 两个串相等：两个串的长度相等，并且各个对应的字符也都相同。 a= “program” b= “Program” c= “pro” d= “program ” 串的基本操作： （1） 创建串 StringAssign (s,string_constant) （2）判断串是否为空 StringEmpty(s) （3）计算串长度 Length(s) （4）串连接 Concat(s1,s2) （5）求子串 SubStr(s1,s2start,len) （6）串的定位 Index(s1,s2) 将s2串插入到串s1的第i个字符后面： SubStr(s3,s1,1,i); SubStr(s4,s1,i+1,Length(s1)-i); Concat(s3,s2); Concat(s3,s4); StringAssign (s1,s3); 删除串s中第i个字符开始的连续j个字符： SubStr(s1,s,1,i-1); SubStr(s2,s,i+j,Length(s)-i-j+1); Concat(s1,s2); StringAssign(s,s1); 串的存储结构 1. 顺序存储结构 串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。 第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下： #define MAX_STRING 255 type unsigned char String[MAX_STRING]; 2. 链式存储结构 由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。 s t r i n g ^ S 优点是操作方便；不足之处是存储密度较低。所谓存储密度为： 若要将多个字符存放在一个结点中，就可以缓解这个问题。 S s t r i n g # # # # ^ 这种存储形式优点是存储密度高于结点大小为1 的存储形式；不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。 4．2数组 存储数据的方式： 为了方便地存取大量的相关性数，在计算机系统内定义连续的存储区域并为 其编号，通过循序编号的方式来存储数据。 定义： 连续的、有限的、有序的同种元素的集合。 特点： 每个数据元素可以又是一个线性表结构。因此，若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。 结论： 数组结构是线性表结构的一个特例，而线性表结构又是数组结构的扩展。 数组的存储结构 从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。一般的数组结构不使用链式存储结构。 组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。 数组的表示 1. 一维