1. 线性表：L=(a1,a2,…,an)，ai是同类型的元素，1≤i≤n
  2. 数组: A= (a1,a2,…,an) 若ai是同类型的元素，A是一维数组，1≤i≤n 若ai是同类型的定长线性表，A是多维数组，1≤i≤n
  3. 广义表：Ls= (a1,a2,…,an) ai可以是同类型的元素或广义表，1≤i≤n

    数组的基本概念及其操作

    数组的递归定义

1.一维数组： 是一个定长线性表(a1,a2,…,an)。 其中：ai为数据元素，i为下标/序号，1≤i≤n (a1,a2,…,an )又称为向量

**2.二维数组: **
image.png

3.三维数组
image.png

数组的操作

  • 1.生成一个数组： int a[7]；//生成静态一维数组
  • 2.赋值/修改 a[1]=15；(a[1])++；
  • 3.取元素的值： a[0]=a[1]*2；
  • 4.销毁一个数组

int a[10];属于静态分配；
静态分配的内存在栈里，每进入一个函数时都会建栈，栈里会存放函数用到的参数、局部变量等信息，函数执行完以后，会出栈销毁栈，这个过程就会释放你静态分配的数组内存，这是由系统自动完成的。

pa=(int )malloc(nsizeof(int))；//生成动态数组*pa
pa = new int[n];//生成动态数组
动态分配的内存，实际在堆上，系统没法自动帮你去释放堆上的内存，需要你自己写free或者delete来告诉操作系统需要帮你去释放堆上哪个位置的内存

数组的顺序表示和实现

顺序表示(顺序存储结构）

  • 1.以行序为主序的顺序存储方式，按行向量排列 左边的下标后变化，右边的下标先变化
  • 2.以列序为主序的顺序存储方式，按列向量排列 左边的下标先变化，右边的下标后变化

image.png
image.png

数组的映象函数

image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

矩阵的压缩存储

1.n阶对称矩阵

image.png

image.png
image.png

2.对角矩阵

image.png

3.稀疏矩阵的压缩存储

三元组表

注意三元组表查找元素只能靠遍历并且三元组表不存储节点个数
image.png

转置矩阵
image.png

image.png

十字链接表

image.png

广义表

广义表的定义和术语：

  • n(n≥0)个数据元素或广义表的一个有限序列叫做广义表。
  • 记作: LS=(e1,e2,…,en)。 n为LS的长度。
  • 其中: LS—-广义表名
  • ei—-单元素、原子,约定用小写, 既可以代表单个元素，也可以代表另一个广义表
  • 1≤i≤n ei—-广义表，约定用大写, 1≤i≤n
  • (1)空表 LS=( ),n=0
  • (2)非空表 LS=(e1,e2,…,en) n>0 注意，A = ( ) 和 A = ( ( ) ) 是不一样的。前者是空表，而后者是包含一个子表的广义表，只不过这个子表是空表。
  • 其中: e1—LS的表头/首部，记作: Head(LS)=e1 ；；而 (e2,…,en)— LS的表尾/尾部, 记作： Tail(LS)=(e2,…,en)
  • 当广义表不是空表时，称第一个数据（原子或子表）为”表头”，剩下的数据构成的新广义表为”表尾”。

广义表的存储结构

广义表的元素具有不同结构，一般用链式存储结构。
image.png
image.png