第五章 数据结构-数组和广义表

1、 本章主要介绍下列内容本章主要介绍下列内容l 数组的定义数组的定义l 数组的顺序表示和实现数组的顺序表示和实现l 矩阵的压缩存储矩阵的压缩存储l 稀疏矩阵稀疏矩阵l 广义表广义表 一、一、数组的定义和基本运算数组的定义和基本运算 数组的特点是每个数据元素可以又是一个线性表数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，中的数据元素为非结构的简单元素，则称为一维数组，即为即为向量向量；若一维数组中的数据元素又是一维数组结；若一维数组中的数据元素又是一维数组结构，则

2、称为二维数组；依次类推，若二维数组中的元构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。素又是一个一维数组结构，则称作三维数组。 结论：线性表结构是数组结构的一个特例，而数结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例：组结构又是线性表结构的扩展。举例：1, 11 , 10, 11, 111101,00100.nmmmnnnmaaaaaaaaaA图图 4-3 其中，其中，A是数组结构的名称，整个数组元素可以看是数组结构的名称，整个数组元素可以看成是由成是由m个行向量和个行向量和n个列向量组成，其元素总数为个列向量组成，其元素总数

3、为mn。在。在C语言中，二维数组中的数据元素可以表示语言中，二维数组中的数据元素可以表示成成a表达式表达式1表达式表达式2，表达式，表达式1和表达式和表达式2被称为下被称为下标表达式，比如，标表达式，比如，aij。 数组结构在创建时就确定了组成该结构的行向量数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。删除元素的操作。 二维数组结构的基本操作：二维数组结构的基本操作： （1） 给定一组下标，修改该位置元素的内容给定一组下标，修改该位置元素的内容 Assign(A,item,index1,

4、index2) （2）给定一组下标，返回该位置的元素内容）给定一组下标，返回该位置的元素内容 Value(A,item,index1,index2) 5.2 数组的顺序表示数组的顺序表示 从理论上讲，数组结构也可以使用两种存储从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。般的数组结构不使用链式存储结构。 组成数组结构的元素可以是多

5、维的，但存组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。举例：射到一维关系的问题。举例：图图 5-11, 11 , 10 , 11, 111101, 00100.nmmmnnnmaaaaaaaaaAa00a01.a0,n-1a10a11.a1,n-1.am-1,0am-1,1.am-1,n-1 第0行 第1行 第m-1行图图 4-5a00a10.am-1,0a01a11.am-1,1.a0,n-1a1,n-1.am-1,n-1

6、 第0列 第1列 第m-1列图图 4-6按行优先地址计算：按行优先地址计算：LOC(i,j)=LOC(0,0)+(n*i+j)*d按列优先地址计算：按列优先地址计算： LOC(i,j)=LOC(0,0)+(m*j+i)*d数组结构的定义：数组结构的定义：#define MAX_ROW_INDEX 10#define MAX_COL_INDEX 10typedef struct elemtype elemMAX_ROW_INDEXMAX_COL_INDEX ; ARRAY;基本操作算法举例：基本操作算法举例：（1）给数组元素赋值）给数组元素赋值void Assign(ARRAY &A,Elemt

7、ype elem,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) exit(ERROR); else A-elemindex1index2=elem;（2）返回给定位置的元素内容）返回给定位置的元素内容 int Value(ARRAY A,Elemtype &elem,int index1,int index2) if (index1=MAX_ROW_INDEX| index2=MAX_COL_INDEX) return FALSE; else *elem= A.elemindex1index2; r

8、eturn OK; 5.35.3矩阵的压缩存储矩阵的压缩存储 矩阵是在很多科学与工程计算中遇到的数学模型。矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由在数学上，矩阵是这样定义的：它是一个由sn个元个元素排成的素排成的s行（横向）行（横向）n列（纵向）的表。下面就是一列（纵向）的表。下面就是一个矩阵：个矩阵：图图5-2 sn的矩阵的矩阵它是一个它是一个sn的矩阵。的矩阵。mnmmnnaaaaaaaaa.212222111211 5.3.1 5.3.1 特殊矩阵特殊矩阵 所谓所谓特殊矩特殊矩阵就是元素值的排列具有一定规律的矩阵就是元素值的排列具有一定规律的矩阵

9、。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、阵。常见的这类矩阵有：对称矩阵、下（上）三角矩阵、对角线矩阵等等。对角线矩阵等等。 对称矩阵的特点是对称矩阵的特点是aij=aji，比如，下面就是一个对称，比如，下面就是一个对称矩阵：矩阵：图图 5-31423417232012341275173510 下（上）三角矩阵的特点是以主对角线为界的上下（上）三角矩阵的特点是以主对角线为界的上（下）半部分是一个固定的值，下（上）半部分的元（下）半部分是一个固定的值，下（上）半部分的元素值没有任何规律。比如，下面是一个下三角矩阵：素值没有任何规律。比如，下面是一个下三角矩阵：209261303010800

10、12600029图图 5-4 对角矩阵的特点是所有的非零元素都集中在以主对角矩阵的特点是所有的非零元素都集中在以主对角线为中心的带状区域中。比如，下面就是一个对角线为中心的带状区域中。比如，下面就是一个3阶阶对角矩阵：对角矩阵：11340006921000177300002059000123图图 5-5 对于这些特殊矩阵，应该充分利用元素值的分布规对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进

11、行各项基本操作。以比较容易地进行各项基本操作。 三种特殊矩阵的压缩方法：。三种特殊矩阵的压缩方法：。 （1）对称矩阵）对称矩阵 对称矩阵的特点是对称矩阵的特点是aij=aji。一个。一个nn的方阵，共有的方阵，共有n2个元素，而实际上在对称矩阵中有个元素，而实际上在对称矩阵中有n(n-1)/2个元素可个元素可以通过其他元素获得。以通过其他元素获得。 压缩的方法是首先将二维关系映射成一维关系，并压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的只存储其中必要的n(n+1)/2个（主对角线和下三角）元素个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例：内容，这些元素的存

12、储顺序以行为主序。举例： 假设定义一个数组型变量：假设定义一个数组型变量：int A10;01234567891057312201742314图图 5-6 k是对称矩阵位于（是对称矩阵位于（i，j）位置的元素在一维数组）位置的元素在一维数组中的存放位置。中的存放位置。ji 12) 1(ji 12) 1(当当ijjjiik操作算法的实现：操作算法的实现：int Value(int A,Elemtype *elem,int i,int j) if (iMAX_ROW_INDEX| jMAX_COL_INDEX) return FALSE; else if (i=j) k=i*(i-1)/2+j-1

13、; else k=j*(j-1)/2+i-1; *elem=Ak; return TRUE; （2）下（上）三角矩阵）下（上）三角矩阵 下三角矩阵的压缩存储与上面讲述的对称矩阵的下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在压缩存储一样，只是将上三角部分的常量值存储在0单单元，下三角和主对角上的元素从元，下三角和主对角上的元素从1号单元开始存放。号单元开始存放。 举例：举例：012345678910029612810301326920图图 5-7ji 0ji 2) 1(当当jiik 对于任意的（对于任意的（i，j），在一维数组中的存放位置可），在一维数组

14、中的存放位置可利用下列公式求得：利用下列公式求得：操作算法的实现：操作算法的实现：int Value(int A,Elemtype *elem,int i,int j) if (iMAX_ROW_INDEX|jMAX_COL_INDEX) return FALSE; else if (i=j) k=i*(i-1)/2+j; else k=0; *elem=Ak; return TRUE; （3）对角矩阵）对角矩阵 我们以三阶对角矩阵为例讨论一下它的压缩存储方我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零法。对于对角矩阵，压缩存储的主要思路是只存储非

15、零元素。这些非零元素按以行为主序的顺序，从下标为元素。这些非零元素按以行为主序的顺序，从下标为1 的位置开始依次存放在一维数组中，而的位置开始依次存放在一维数组中，而0位置存放数值位置存放数值0。0123456789101112130312952030717219-63411图图 5-8 下面我们讨论一下对于任意给定的（下面我们讨论一下对于任意给定的（i，j），求得），求得在一维数组中存储位置在一维数组中存储位置k的方法。的方法。否则当 011 1i - j1)-(i3ijik操作算法的实现：操作算法的实现：int Value(int A ,Elemtype *elem,int i,int j

16、) if (iMAX_ROW_INDEX|jMAX_COL_INDEX) return FALSE; else if (j=(i-1)&j=(i+1) k=3*(i-1)+j-i+1; else k=0; *elem=Ak; return TRUE; 5.4 5.4 稀疏矩阵稀疏矩阵 若一个若一个mn的矩阵含有的矩阵含有t个非零元素，且个非零元素，且t远远小远远小于于m*n，则我们将这个矩阵称为，则我们将这个矩阵称为稀疏矩阵稀疏矩阵。举例：。举例：0200000000000210010070003图图 5-9 稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法三元组表示法。三元组表示法。 矩阵中的每

17、个元素都是由行序号和列序号唯一确定矩阵中的每个元素都是由行序号和列序号唯一确定的。因此，我们需要用三项内容表示稀疏矩阵中的每个的。因此，我们需要用三项内容表示稀疏矩阵中的每个非零元素，即形式为：非零元素，即形式为：(i,j,value) 其中，其中，i表示行序号，表示行序号，j表示列序号，表示列序号，value表示非零表示非零元素的值，通常将它称为三元。我们将稀疏矩阵中的所元素的值，通常将它称为三元。我们将稀疏矩阵中的所有非零元素用这种三元的形式表示，并将它们按以行为有非零元素用这种三元的形式表示，并将它们按以行为主的顺序存放在一个一维数组中，就形成了我们所说的主的顺序存放在一个一维数组中，就

18、形成了我们所说的三元组表示法。举例：三元组表示法。举例：图图 5-10ijvalue01131157223-1331-1432-25542类型定义：类型定义：#define maxsize 100 最大的非零元素个数最大的非零元素个数 struct node int i,j; /行序号、列序号行序号、列序号 int v; /非零元素值非零元素值;typedef struct struct node datamaxsize; /存储非零元素的一维数组存储非零元素的一维数组 int rows,cols,terms; /稀疏矩阵的总行数、列数及非零元素个数稀疏矩阵的总行数、列数及非零元素个数spar

19、matrix;2、稀疏矩阵的链式存储结构（1）带行指针的链式存储结构 基本思想：把具有相同行号的非0元素用一个单链表连接起来，稀疏矩阵中的若干行组成若干个单链表，同时用一个向量存储每一行的第一个非0元素的地址。（2）十字链表 基本思想：在（1）的基础上把每一列的非0元素用一个单链表连接起来。 5.5 广义表 广义表是线性表的推广。也有人称其为列表。广泛地用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。广义表一般记作LS=（a1,a2,a3,an),LS为广义表的名称，ai可以是单元素，称为原子；也可是广义表，称为子表。习惯上用大写字母表示广义表的名称，小写字母表示原子。当广义表LS非空时，则a1是LS的表头，其余元素组成的表称为LS的表尾。（1）A=（ ） (2)B=(e) (3)C=(a,(b,c,d)（4）D=(A,B,C) (5)E=(a,E)