数据结构郝春梅C语言版第5章

1、2第5章 数组和广义表学习目标与要求：了解数组的概念及基本操作。掌握二维数组的行主序和列主序两种存储方式。 了解特殊矩阵的特点并掌握特殊矩阵的存储形式及基本运算。了解广义表的概念及相关术语。掌握广义表的存储形式。3数组数组是一种扩展的线性数据结构。线性表、数组是一种扩展的线性数据结构。线性表、栈、队列、串的数据元素都是不可再分的栈、队列、串的数据元素都是不可再分的原子类型，而数组中的数据元素是可以再原子类型，而数组中的数据元素是可以再分的。数组可以分为一维数组和多维数组，分的。数组可以分为一维数组和多维数组，一维数组中的元素是由原子构成的，多维一维数组中的元素是由原子构成的，多维数组中的元素又

2、是一个线性表。因此，数数组中的元素又是一个线性表。因此，数组是一种特殊的线性表。组是一种特殊的线性表。4数组是由数组是由n个类型相同的数据元素组成的个类型相同的数据元素组成的有限序列。其中，这有限序列。其中，这n个数据元素占用一个数据元素占用一块地址连续的存储空间。数组中的数据元块地址连续的存储空间。数组中的数据元素可以是原子类型的，如整型、字符型、素可以是原子类型的，如整型、字符型、浮点型等，这种类型的数组称为一维数组；浮点型等，这种类型的数组称为一维数组；也可以是一个线性表，这种类型的数组称也可以是一个线性表，这种类型的数组称为二维数组。二维数组可以看成是线性表为二维数组。二维数组可以看成

3、是线性表的线性表。的线性表。5.1 数组的定义数组的定义5一个含有一个含有n个元素的一维数组可以表示成个元素的一维数组可以表示成线性表线性表A=（a0,a1,an-1）。其中，）。其中，ai(0=i=j当当ij235.3.1 特殊矩阵 245.3.1 特殊矩阵 255.3.1 特殊矩阵 k=（i-1）*(2n-i+2)/2 +j-i+10 当ij上三角矩阵上三角矩阵k=i*(i-1)/2 +j0当i=j当icol=pb-col,且且pa-v+pb-v!=0,则只需用则只需用aij+bij的值改写的值改写pa所指结点的值域即可。所指结点的值域即可。（2）若）若pa-col=pb-col,且且pa

4、-v+pb-v=0,则只需在矩阵则只需在矩阵A的十字链表中删除的十字链表中删除pa所指结点，此时需改变该行链表中前驱结所指结点，此时需改变该行链表中前驱结点的点的right域，以及该列链表中前驱结点的域，以及该列链表中前驱结点的down域。域。（3）若）若pa-colcol,且且pa-col!=0(即不是表头结点即不是表头结点)，则，则只需将只需将pa指针向右推进一步，并继续进行比较。指针向右推进一步，并继续进行比较。（4）若）若pa-colpb-col或或pa-col=0(即是表头结点即是表头结点)，则需，则需要在矩阵要在矩阵A的十字链表中插入一个的十字链表中插入一个pb所指结点。所指结点。52本 章 小 结(1)数组可看作线性表的推广，数组在计算机中数组可看作线性表的推广，数组在计算机中采用顺序存储结构表示，通常有两种存储顺序：采用顺序存储结构表示，通常有两种存储顺序：以行序为主序和以列序为主序。以行序为主序和以列序为主序。(2)为了节省存储空间，可以对特殊矩阵和稀疏为了节省存储空间，可以对特殊矩阵和稀疏矩阵进行压缩存储。矩阵进行压缩存储。(3)广义表是线性表的推广，有两种表示方法：广义表是线性表的推广，有两