数据结构教程第4章 数组.doc

第4章 数组本章主要介绍下列内容(教材第5章)1数组的定义和基本运算2数组的存储结构3矩阵的压缩存储课时分配：第1、2节两个学时，第3节四个学时重点、难点：特殊矩阵的压缩存储第一节 数组的定义和基本运算数组的特点是每个数据元素可以又是一个线性表结构。因此，数组结构可以简单地定义为：若线性表中的数据元素为非结构的简单元素，则称为一维数组，即为向量；若一维数组中的数据元素又是一维数组结构，则称为二维数组；依次类推，若二维数组中的元素又是一个一维数组结构，则称作三维数组。结论：线性表结构是数组结构的一个特例，而数组结构又是线性表结构的扩展。举例： 其中，A是数组结构的名称，整个数组元素可以看成是由m个行向量和n个列向量组成，其元素总数为mn。在C语言中，二维数组中的数据元素可以表示成a表达式1表达式2，表达式1和表达式2被称为下标表达式，比如，aij。 数组结构在创建时就确定了组成该结构的行向量数目和列向量数目，因此，在数组结构中不存在插入、删除元素的操作。 二维数组结构的基本操作（1）给定一组下标，修改该位置元素的内容 Assign(A,elem,index1,index2)（2）给定一组下标，返回该位置的元素内容 Value(A,elem,index1,index2)第二节 数组的存储结构 从理论上讲，数组结构也可以使用两种存储结构，即顺序存储结构和链式存储结构。然而，由于数组结构没有插入、删除元素的操作，所以使用顺序存储结构更为适宜。换句话说，一般的数组结构不使用链式存储结构。 组成数组结构的元素可以是多维的，但存储数据元素的内存单元地址是一维的，因此，在存储数组结构之前，需要解决将多维关系映射到一维关系的问题。举例： 讲清公式LOC(i,j)=LOC(0,0)+(n*i+j)*L含义，同时介绍多维数组地址计算公式用法。数组结构的定义#define MAX_ROW_INDEX 10 #define MAX_COL_INDEX 10typedef struct Elemtype elemMAX_ROW_INDEXMAX_COL_INDEX ; ARRAY; 基本操作算法举例（了解）（1）给数组元素赋值 void Assign(ARRAY *A,Elemtype 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;return OK;第三节 矩阵的压缩存储矩阵是在很多科学与工程计算中遇到的数学模型。在数学上，矩阵是这样定义的：它是一个由mn个元素排成的m行（横向）n列（纵向）的表。下面就是一个矩阵 对于这些特殊矩阵，应该充分利用元素值的分布规律，将其进行压缩存储。选择压缩存储的方法应遵循两条原则：一是尽可能地压缩数据量，二是压缩后仍然可以比较容易地进行各项基本操作。 三种特殊矩阵的压缩方法（时间允许，则补充教研论文内容） （1）对称矩阵 对称矩阵的特点是aij=aji。一个nn的方阵，共有n2个元素，而实际上在对称矩阵中有n(n-1)/2个元素可以通过其他元素获得。 压缩的方法是首先将二维关系映射成一维关系，并只存储其中必要的n(n+1)/2个（主对角线和下三角）元素内容，这些元素的存储顺序以行为主序。举例： 假设定义一个数组型变量：int A10;k是对称矩阵位于（i，j）位置的元素在一维数组中的存放位置。 操作算法的实现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; else k=j*(j-1)/2+i-1; *elem=Ak; return TRUE; （2）下（上）三角矩阵 下三角矩阵的压缩存储与上面讲述的对称矩阵的压缩存储一样，只是将上三角部分的常量值存储在0单元，下三角和主对角上的元素从1号单元开始存放。 举例： 对于任意的（i，j），在一维数组中的存放位置可利用下列公式求得：操作算法的实现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）对角矩阵我们以三阶对角矩阵为例讨论一下它的压缩存储方法。对于对角矩阵，压缩存储的主要思路是只存储非零元素。这些非零元素按以行为主序的顺序，从下标为1 的位置开始依次存放在一维数组中，而0位置存放数值0。操作算法的实现int Value(int A ,Elemtype *elem,int i,int j)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;类型定义：#define MAX_SIZE 100 最大的非零元素个数typedef structint i,j; /行序号、列序号Elemtype value; /非零元素值 Three_Elem;typedef struct Three_Elem ElemMAXSIZE; /存储非零元素的一维数组int rows,cols,tu; /稀疏矩阵的总行数、列数及非零元素个数 Matrix;操作算法的实现：（1）返回元素内容 int Value(Matrix M,Elemtype *elem,int i,int j) if (irows|jcols) exit(ERROR);else for (p=0;pi|M.elemp.i=i&M.Elemp.jj) break;*elem=0;return OK;（2）输出三元组表示的稀疏矩阵 void Print(Matr