数据结构【第四章知识点小结】

文章目录

• 前言

前言

提示：第四章知识点小结记录了我认为的重点：

一、已知数组下标(i,j)，确定其存储地址k

1. 对称矩阵

[特点] 在n✖n的矩阵a中，满足性质：aij=aji (1<=i, j<=n)

[存储方法] 只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。

1. 三角矩阵

[特点] 对角线以下(或者以上)的数据元素(不包括对角线)全部为常数c。

[存储方法] 重复元素c共享一个存储空间，共占用n(n+1)/2+1个元素空间

K= 1 2 3 4 5 6 7

K= 1 2 3 4 5 6 7

1. 广义表

1.广义表，也称列表，即线性表的推广。

2.广义表（列表）：n (>=0 )个表元素组成的有限序列，

记作LS = (a0, a1, a2, …, an-1)

LS是表名，ai是表元素，它可以是数据元素(称为原子)，也可以是表 (称为子表)。习惯上，大写字母表示表名， 小写字母表示原子。

n为表的长度。

n = 0 的广义表为空表。

此处举个栗子:(供大家举一反三)

（1）A=（）—A是一个空表，长度为0。

（2）B=（e）—B只有一个原子，表长为1。

（3）C=（a,(b,c)）—表长为2，两个元素分别是原子和子表。

（4）D=（A,B,C）—表长为3，三个元素均为子表。

D=（（）,（e），（a,（b,c）））

1. E=（a,E）—递归表，表长为2.
2. 广义表与线性表的区别

线性表的成分都是结构上不可分的单元素

广义表的成分可以是单元素，也可以是有结构的表

线性表是一种特殊的广义表

广义表不一定是线性表，也不一定是线性结构

4.广义表的基本运算

（1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表

（2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表

5.广义表的特点

此处举个栗子(同学们可以练习一下)

终于结束啦！同学们继续加油噢，这本书已经过半了。