计算机软件技术基础-课件 05ch2(4)-DS

线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容2.3串2.3.1串及其基本运算

1.串的基本概念

2.串的基本运算2.3.2串的定长顺序存储及基本运算

1.串的定长顺序存储

2.定长顺序串的基本运算2.3.1串及其基本运算:串的基本概念

S=“a1,a2,……..,an”(n≥0)

串名串值（用“”括起来，引号不是串值。）串（String）是由零个或多个任意字符（含空格）组成的有限序列。记作:S=“a1a2…an”S是串的名字“a1a2…an”是串的值，必须用引号括起来ai是串中的字符，可以是字母、数字或其他字符n是串的长度2.3.1串及其基本运算:串的基本概念子串：串S中任意个连续的字符组成的子序列。包含子串的串S称为主串。子串（在主串中）的位置：子串的第一个字符在主串中的位置。两个串相等：两个串长度相等且每个对应位置上字符相等。字符位置：字符在串中的序号。串长：串中字符个数（n≥0），n=0时称为空串

。2.3.1串及其基本运算:串的基本概念区分空串和空格串：空串：n（串的长度）＝0时的串空格串：由一个或多个空格组成的串空串的长度一定为0；空格串的长度一定大于0，但具体值由空格的个数决定示例串A＝“ChinaNanjing”，

B＝“Nanjing”，C＝“China”，D＝“inaN”，E＝“iij”,F＝“iij”问：1）其中，B、C、D、E、F中哪些是A的子串，哪些不是？

2）如果是A的子串，则在A中的位置分别是多少？

3）D、E、F的长度分别是多少？E是否与F相等？B、C、D是A的子串，E、F不是A的子串。字串B的位置为7，字串C的位置为1，字串D的位置为3。D、E、F的长度分别是5、3、4。字串E与字串F不相等。2串的基本运算1)求串长StrLength(s)操作条件：串s存在操作结果：求出串s的长度。2)串赋值StrAssign(s1,s2)操作条件：s1是一个串变量，s2或者是一个串常量，或者是一个串变量。操作结果：将s2的串值赋值给s1，s1原来的值被覆盖掉。2串的基本运算3)串的连接(concatenation

)操作：StrConcat(s1,s2,s)或StrConcat(s1,s2)操作条件：串s1,s2存在。操作结果：两个串的连接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。4)求子串SubStr(s,i,len)：操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果：返回从串s的第i个字符开始的长度为len的子串。len=0得到的是空串。例如：SubStr(“abcdefghi”,3,4)=“cdef”2串的基本运算5)串比较StrCmp(s1,s2)操作条件：串s1,s2存在。操作结果：若s1==s2，操作返回值为0；若s1<s2,返回值<0；若s1>s2,返回值>0。6)子串定位StrIndex(s,t)：找子串t在主串s中首次出现的位置操作条件：串s,t存在。操作结果：若t∈s，则操作返回t在s中首次出现的位置，否则返回值为-1。例如：StrIndex(“abcdebda”,“bc”)=2StrIndex(“abcdebda”,“ba”)=-1给定两个串s1=“a1a2…an”,s2=“b1b2…bm”，s1<s2表示两个串中第一个不匹配的字符ai和bj，有ai<bj。2串的基本运算7)串插入StrInsert(s,i,t)操作条件：串s,t存在，且1≤i≤StrLength(s)+1。操作结果：将串t插入到串s的第i个字符位置上，s的串值发生改变。例如：s=“Thisabook”,t=“is” StrInsert(s,6,t)=“Thisisabook”8)串删除StrDelete(s,i,len)操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果：删除串s中从第i个字符开始的长度为len的子串，s的串值改变。例如：s=“Thisabook”

StrDelete(s,6,2)=“Thisbook”2串的基本运算9)串替换StrRep(s,t,r)操作条件：串s,t,r存在，t不为空。操作结果：用串r替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。例如：s=“Heisastudent”,t=“He”,r=“She” StrRep(s,t,r)=“Sheisastudent”设s

=“IAMASTUDENT”,t

=“GOOD”,q=“WORKER”。求：练习：(1)StrLength(s)=

(2)StrLength(t)=(3)SubString(s,8,7)=(4)SubString(t,2,1)=(5)StrIndex(s,“A”)=(6)StrIndex(s,t

)=(7)StrRep(s,“STUDENT”,q)=144“STUDENT”“O”3-1（s中没有t！）“IAMAWORKER”2.3.2串的定长顺序存储及基本运算强调：串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。串存储方法有：

定长顺序存储结构、块链式存储结构等。2.3.2串的定长顺序存储及基本运算1.串的定长顺序存储定长顺序存储表示——用一组地址连续的存储单元存储串值中的字符序列。定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区。例如：#defineMAXSIZE256 chars[MAXSIZE];

则串的最大长度不能超过256。问题：如何标识实际长度？

2.3.2串的定长顺序存储及基本运算1.串的定长顺序存储如何标识实际长度：方法1：专用变量，指向最后一个字符的指针方法2：在串尾存储特殊字符作为串的终结符方法3：用s[0]存放串的实际长度方法1.

用一个指示变量来指向最后一个字符。这样表示的串描述如下：typedefstruct{chardata[MAXSIZE];intstrlen;}SeqString;…s.strlen=10012345678910...

MAXSIZE-1abcdefghijk

2.3.2串的定长顺序存储及基本运算例如：SeqStrings;这种存储方式可以直接得到串的长度=(s.strlen+1)。如图所示:方法2.

在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。\0012345678910...

MAXSIZE-1abcdefghijk

…

2.3.2串的定长顺序存储及基本运算比如C语言用’\0’(ascii码值为0的NULL字符)来表示串的结束。这种存储方法不能直接得到串的长度，是用判断当前字符是否是’\0’来确定串是否结束，从而求得串的长度。

chars[MAXSIZE];注意：字符‘\0’标识串的结束，不在串长计算范围之内。

方法3.设定长串存储空间：chars[MAXSIZE+1];用s[0]存放串的实际长度，串值存放在s[1]~s[MAXSIZE]。2.3.2串的定长顺序存储及基本运算串的定长顺序存储（串的定长顺序存储）缺点：

1)需要预先定义一个串允许的最大字符个数，当估计过大时存储效率就降低。

2)插入与删除操作需要移动字符。2.定长顺序串的基本运算

(1)串的联接

(2)求子串

(3)串比较其他：串的块链式存储结构小结

串是零个或多个字符组成的有限序列，是一种特殊的线性表。它的每个结点元素仅由一个字符组成。另外，串上的操作主要针对串的整体或串的某一部分子串进行，不同于一般线性表是针对表中某一结点元素进行的。数据结构课程的内容线性结构（线性表、栈、队、串、数组）逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算第2章2.4数组、特殊矩阵2.4.1多维数组

1.数组的逻缉结构

2.数组的内存映象2.4.2特殊矩阵的压缩存储*

1.对称矩阵

2.三角矩阵

3.稀疏矩阵数组可以看作线性表的推广。数组作为一种数据结构其特点是数据元素本身可以是一个数据结构（具有某种结构的数据，但属于同一数据类型）。数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识。在数组上不能做插入、删除数据元素的操作。在数组中通常做下面两种操作：(1)取值操作：给定一组下标，读取对应的数据元素(2)赋值操作：给定一组下标，修改与其相对应的数据元素第2章2.4数组、特殊矩阵2.4.1多维数组1.数组的逻辑结构注意：

数据结构中数组与高级语言中数组的区别：高级语言中的数组是顺序结构；而数据结构中的数组既可以是顺序的，也可以是链式结构，用户可根据需要选择。数组是n(n≥0)个相同数据类型数据元素构成的有限序列。一维数组是一个线性表。二维数组的任何一行/列都是一个线性表。a11a12…a1n

a21a22…a2n

…………

am1am2…amn

Amn=一维数组的特点：定长线性表（别名向量）除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。

数组的逻辑结构a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,ai2,……..,ain)(1<=i<=m)——行向量数组是线性表的推广二维数组的定义:数据元素是一维数组的一维数组。

数组的逻辑结构ßi=(ß1i,

ß2i,

……..

,

ßmi)(1<=i<=n)——列向量ß1a11a21……am1ß2a12a22……am2ßna1na2n……amn…………………………

数组的逻辑结构二维数组的定义:数据元素是一维数组的一维数组。

二维数组三维数组行向量下标

i页向量下标

i列向量下标

j行向量下标

j

列向量下标

k

数组的逻辑结构讨论：“数组的处理比其它复杂的结构要简单”，对吗？答：对的。因为：①数组中各元素具有统一的数据类型；②数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有读取元素（取值）和赋值的操作。2.数组的顺序表示（数组的内存映象）数组建立后，数据元素个数和元素之间的关系就不再发生变动，因而非常适合采用顺序存储结构。问题：内存的地址空间是一维的，对应一维数组（向量）；数组可以是多维的；两者之间的对应关系： 通过映象函数实现，根据数组元素的下标得到它的存储地址。2.数组的内存映象一维数组的特点：二维数组的特点：2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：一个m×n的二维数组可以看成是m行的一维数组（向量），或者n列的一维数组（向量）。N维数组的特点：

n个下标，每个元素受到n个关系约束一个n维数组可以看成是由若干个n－1维数组组成的线性表。1个下标，ai是ai+1的直接前驱数组的顺序存储表示和实现问题：计算机的存储结构是一维的，而数组一般是多维的，怎样存放？解决办法：事先约定按某种次序将数组元素排成一个线性序列（向量），然后将这个线性序列存入存储器中。例如：在二维数组中，我们既可以规定按行存储，也可以规定按列存储。注意：若规定好了次序，则数组中任意一个元素的存放地址便有规律可寻，可形成地址计算公式；约定的次序不同，则计算元素地址的公式也有所不同；⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn

通常有两种顺序存储方式：amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a11

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….任意元素aij的存储位置：loc(aij)=loc(a11)+[]×LL为每个元素的存储大小

按行优先顺序存放(i-1)×n+(j-1)⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后，二维数组A的m*n个元素按列优先顺序存储的线性序列为：a11,a21,…,am1,a12,a22,…am2,……,an1,an2,…,anmamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11

a11

a12

……..

a1n

a21

a