数据结构笔记(数据结构讲义)

导语：数据结构学习笔记5

1、数组和广义表

1）数组和广义表可以视为是线性表的扩展，即线性表中的数据元素本身也是一个数据结构。

2）二维数组定义：可以定义为一个线性表 其中每个数据元素又是一个列向量的线性表。

2、广义表定义：数据元素可以是表的线性表。记为Ls=（d1，d2，...,dn） Ls

为表名 di（i=1，2，....,n）可以是单元素（用小写字母表示）也可以是广义表（称为子表，用大写字母表示）n为表的长度，当长度为0时称为空表；称非空表的第一个元素d1为表头；其余元素组成的表称为表尾。

3、数组的基本运算

1）给定下标，存取相应的数据元素；

2）给定下标，修改相应的数据元素；

4、广义表的基本运算

1）取表头HEAD（LS）；

2）取表尾TAIL（LS）

5、数组的顺序存储结构：由于数组不做插入、删除操作，所以常采用顺序存储结构来实现数组，即用一组连续的存储单元，以行主（或列主）顺序依次存放数组的数据元素。

1）不需要移动数据元素，我们可以 求长度 遍历数组 去数组元素 修改数组元素

6、稀疏矩阵：是指矩阵中含有大量的零元。

7、矩阵的压缩存储 给多个值相同的元素只分配一个存储单元 或者对值为零的元素不分配存储单元。

1）对称矩阵：满足aij=aji

2）对角矩阵：所有的非零元素集中在平行于主对角线的带状区域中。

3）稀疏矩阵：非零元素较零元素少，且分布没有规律。对每一个非零元素aij可以用一个三元组（i，j，aij）来表示，其中i，j为aij的行列号，aij为元素的值。稀疏矩阵可用一个三元组线性表和行列数描述。

8、三元组线性表的顺序存储结构称为三元组表。

9、快速矩阵转置算法：以原阵的行序产生转置后的三元组，并置入b中的恰当位置。

10、广义表的存储结构：广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构。

1）表头表尾链存储结构 有两类结点：表结点和单元素结点。

2）特点：最上层的表结点数即为广义表的长度；层次清楚；表结点数目多，与广义表中括号对的数目不匹配。

11、同层结点链存储结构

1）有两类结点：表结点和单元素结点；

2）特点：表结点的数目与广义表的括号对数目一致；写递归算法不方便。

本文内容由小梓整理编辑！