跳到主要内容

第四章 串、数组和广义表

4.1 串的定义​

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

S="a1a2a3···an" (n>=0)

  • S为串名
  • a1a2a3···an为串值
  • n为串长
    • n=0为空串

串的术语​

  • 子串：串中任意个连续字符组成的子序列(含空串)称为该串的子串
    • 例："abcde"的子串有：""、"a"、"ab"、"abc"、"abcd"和"abcde"等
    • 真子串是指不包含自身的所有子串
  • 主串：包含子串的串相应地称为主串
  • 字符位置：字符在序列中的序号为该字符在串中的位置
  • 子串位置：子串第一个字符在主串中的位置
  • 空格串：由一个或多个空格组成的串，与空串不同
  • 串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，这两个串才是相等的

4.4 数组​

按一定格式排列起来的具有相同类型的数据元素的集合

数组的特点：结构固定-定义后，维数和维界不再改变

数组的基本操作：除了结构和初始化及销毁外，只有取元素和修改元素值的操作

一维数组​

若线性表中的数据元素为非结构的简单元素，则称为一维数组

一维数组的逻辑结构：线性结构，定长的线性表

声明格式：数据类型 变量名[长度]

​ 例：int num[5] = 5;

二维数组​

若一维数组中的数据元素又是一维数组结构，则称为二维数组

二维数组的逻辑结构：

  • 非线性结构
    • 每一个数据元素既在一个行表中，又在一个列表中
  • 线性结构(定长的线性表)
    • 该线性表的每个数据元素也是一个定长的线性表

声明格式：数据类型 变量名[行数][列数]

  • 例：int num[5][8]

  • 在C语言中，一个二维数组类型也可以定义为一维数组类型(其分量类型为一维数组类型)，即：

    • typedef elemtype array2[m][n];
    • 也等价于：typedef elemtype array1[n]; typedef array1 array2[m];

三维数组及n维数组​

三维数组：若二维数组中的元素又是一个一维数组，则称为三维数组

n维数组：若n-1维数组中的元素又是一个一维数组结构，则称作n维数组

结论​

线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展

4.4.1 数组的抽象数据类型定义​

n维数组的抽象数据类型​

ADT Array { 数据对象: ji=0, ···, bi-1，i=1, 2, ···, n

​ D={aj1j2j3···jn | aj1j2···jn ∈ ElemSet}

​ 数据关系:

​ R1={<aj1···ji···jn, aj1···ji+1···jn> | 0≤jk≤bk-1, 1≤k≤n, 且k≠i, 0≤ji≤bk-2, aj1···ji···jn, aj1···ji+1···jn∈D, i=2, ···,n}

​ 基本操作:

​ InitArray(&A, bound1, ..., boundn) - 构造数组A

​ DestroyArray(&A) - 销毁数组A

​ Value(A, &e, index1, ..., indexn) - 取数组元素值

​ Assign(A, &e, index1, ..., indexn) - 给数组元素赋值

}ADT Array

  • n为数组的维数
  • bi为数组的第i维的长度
  • ji为数组元素第i维的下标

例：二维数组的抽象数据类型的数据对象与数据关系的定义​

  • n=2(维数为2)
  • b1：第1维长度(行数)，b2：第2维长度(列数)
  • aj1j2：第1维下标为j1，第2维下标为j2

数据对象:

​ D={aij | 0≤j1≤b1-1, 0≤j2≤b2-1}

数据关系:

​ R={ROW, COL}

​ ROW={<aj1,j2, aj1+1,j2> | 0≤j1≤b1-2, 0≤j2≤b2-1}

​ COL={<aj1,j2, aj1,j2+1> | 0≤j1≤b1-1, 0≤j2≤b2-2}

4.4.2 数组的顺序存储​

[!TIP]

该章节未完结，后续内容待完善……