《数据结构(c语言版)课件(西安交大)》由会员分享，可在线阅读，更多相关《数据结构(c语言版)课件(西安交大)（34页珍藏版）》请在金锄头文库上搜索。
1、 数组的定义及其基本操作数组的定义及其基本操作 数组的存储结构数组的存储结构 特殊矩阵的压缩存储特殊矩阵的压缩存储 稀疏矩阵的压缩存储稀疏矩阵的压缩存储 广义链表广义链表数组的定义 数组是n(n=)个相同数据类型数据元素构成的有限序列。 一个一维数组，一旦第一个元素ai的存储地址Loc(ai)确定，而每个元素所占用的存储空间大小k为则第i个元素的地址可以由以下公式计算：一、数组的定义及其基本操作一维数组的示例一维数组的示例一维数组的数组元素可以是基 本数据类型，可以是复杂数据类型。 当基本类型也是数组时，一维数组扩 充为二维数组(矩阵)。二维数组同样满足数组的定义。 一个二维数组可以被看成是特
2、殊的一 维数组，其中，每个元素又是一个一 维数组。多维数组可以按同样的方法 类推。数组具有如下性质： 数组中的数据元素数目固定； 数组中的数据元素具有相同的数据类型； 数组中的每个数据元素都与一组唯一的下标值相对应； 数组是一种随机存储结构。二维数组二维数组( (矩阵矩阵) ) 三维数组三维数组( (书书) )行向量行向量下标下标 i i 页向量页向量下标下标i i列向量列向量下标下标 j j 行向量行向量下标下标j j列向量列向量下下 标标k k一维数组一维数组LOC ( i ) = LOC ( i -1 ) + l =+ i*l二、数组的存储结构二维数组二维数组行优先行优先 LOC LOC
3、 ( ( j j, , k k ) = ) = = = a a + ( + ( j * m + k j * m + k ) * ) * l ln n维数组维数组将其中的每一个元素映射到一维数组将其中的每一个元素映射到一维数组 的某一个位置，各维元素个数为的某一个位置，各维元素个数为 m1, m2, m3, , mn，下标为下标为 i i1 1, i, i2 2, i, i3 3, , i, , in n的数组的数组 元素的存储地址：元素的存储地址： 三、特殊矩阵的压缩存储1、对称矩阵在一个n阶方阵A中，若元素满足下述性质 ：则称A为对称矩阵。对称矩阵中的元素关于主 对角线对称，故只需要存储矩阵
4、的上三角或下 三角矩阵，这样可以节约大约一半的空间。在这个下三角矩阵中，第i行恰有i+1个元素， 元素总数为：a00a10 a11a20 a21 a22.an-1,0 . an-1,n-1因此，我们可以将这些元素存放在一个向量 san(n+1)/2中。为了便于访问方阵A中的元素 ，必须在aij和sak之间建立一个对应关系。若 aij在上三角矩阵中，则有：若aij在下三角矩阵中，则有：令I = max(i, j)，J = min(i, j)，则k和i、j的对 应关系可统一为：2、三角矩阵以主对角线划分，三角矩阵有上三角和下三角 两种：在多数情况下，三角矩阵的常数c为0。三角矩阵中的重复元素c可共
5、享一个存储空间 ，其余的元素正好有n(n+1)/2个，因此，三角 矩阵可压缩存储到向量san(n+1)/2+1中，其 中c存放到向量的最后一个分量上。上三角矩阵中，aij和sak之间的对应关系为：下三角矩阵中，aij和sak之间的对应关系为：3、对角矩阵对角矩阵中，所有非0元素都集中在以主对角线 为中心的带状区域中。对角矩阵可按行优先顺序或对角线的顺序，将 其压缩存储到一个向量中，并且也能找到每个 非0元素和向量下标的对应关系。四、稀疏矩阵的压缩存储 如果一个矩阵的非0元素个数远远小于矩阵元素的总数，则称这个矩阵为稀疏矩阵。 一般来说，稀疏矩阵非0元素的分布是无规律的。因此，在存储非0元素的同
6、时，还要存储适当的辅助信息，才能迅速确定某一指定非0元素的位置。 稀疏矩阵常用的压缩存储方式： 三元组表 十字链表1、三元组表若将表示稀疏矩阵的非0元素的三元组 按行优先顺序排列，则可得到一个其结点均 是三元组的线性表，这个顺序存储结构就称 为三元组表。显然，要唯一确定一个稀疏矩阵，还必 须存储该矩阵的行数和列数，它们与非0元 素本身一起构成三元表。#define smax 16 typedef int datatype typrdef struct int i, j;datatype v; node;typedef struct int m, n, t; /*行、列、非零元素个数*/node
7、 datasmax; spmatrix;以矩阵的转置为例说明这种压缩存储结 构是如何实现矩阵运算的。一个mn矩阵A，它的转置矩阵是一个 nm矩阵B，且Aij = Bji。矩阵的转置 不能仅交换矩阵元素下标的次序，还要重新 安排矩阵元素的位置。spmatrix *TRANSMAT(spmatrix *a) int ano,bno,col;spmatrix *b;b=malloc(sizeof(spmatrix);b-m=a-n; b-n=a-m;b-t=a-t;if (b-t0) bno=0;for (col=0; coln; col+)for (ano=0;anot;ano+)if (a-da
8、taano.j=col) b-databno.i=a-dataano.j;b-databno.j=a-dataano.i;b-databno.v=a-dataano.v;return b; 2、十字链表当非0元素的位置和个数经常发生变化时 ，三元组表就不适合做稀疏矩阵的存储结构。 因此，采用链接形式的存储结构更为恰当。十字链表是稀疏矩阵链接形式存储结构 的一种（当然还有其它形式）。在该方法中每 一个非0元素用一个结点表示，结点中除了表 示非0元素的行、列和值的三元组外，还增加 了两个链域：行指针域，用来指向本行中下一 个非0元素；列指针域，用来指向本列中下一 个非0元素。ijv/nex t行指
9、针 列指针在每一个行链表和每一个列链表增加一个 和表结点相同的表头结点，表头结点中的行、 列域置为0，并且将所有的行、列链表和他们 的头结点一起链成一个循环链表。实际实现时，两组头结点可以合用，即第i行链 表和第i列链表共享一个表头结点。因为表头结 点中值域v无用，所以可以将它作为指针域， 用来指向下一个表头结点的指针。稀疏矩阵十字链表表示法的结点说明 typedef struct lnode int i,j;struct lnode *cptr,rptr;union struct lnode *next;datatype v; uval; link;五、广义链表广义表的概念 定义：广义表是n
10、(n=0)个元素a1,a2,an的有限序列，其中ai或者是原子或者是一个广义表。 表的深度：表展开后所含括号的层数。 递归表：允许递归的表。 再入表：允许结点共享的表。 纯表：与树对应的表。 线性表： 通常用圆括号将广义表括起来，用逗号分通常用圆括号将广义表括起来，用逗号分 隔其中的元素。为了区分原子和广义表，书写隔其中的元素。为了区分原子和广义表，书写 时用大写字母表示广义表，用小写字母表示原时用大写字母表示广义表，用小写字母表示原 子。子。这里，我们仅讨论广义表的两个特殊的这里，我们仅讨论广义表的两个特殊的 基本运算：取表头和取表尾。基本运算：取表头和取表尾。把与树对应的广义表称为纯表（表
11、中成分不能共享和递归），把允许结点共享的表称为再入表，把允许递归的表称为递归表。递归表 再入表 纯表 线性表任何一个非空广义表的表头是表中的第任何一个非空广义表的表头是表中的第 一个元素，它可以是原子，也可以是子表；一个元素，它可以是原子，也可以是子表； 而其表尾必定是子表。而其表尾必定是子表。L = ( a, b )L = ( a, b )B = ( A, y ) B = ( A, y )head(L) = a tail(L) = ( b ) head(L) = a tail(L) = ( b )head(B) = A tail(B) = ( y ) head(B) = A tail(B)
12、= ( y )head(tail(L) = b head(tail(L) = btail(tail(L) = ( ) tail(tail(L) = ( )广义表的存储广义表链式存储的结点说明单链表示 typedef struct node int atom;struct node *link;union struct node *slink;datatype data;element; lists;广义表链式存储的结点说明双链表示typedef struct node datatype data;struct node *link1,*link2; lists; 工 资 应发工资扣除 实发工资
13、 基本工资 工龄工资 奖金 房租水电 国库卷 其它 扣除房水电实发工资国库卷其它工龄工资奖金基本工资head L工资收入link CREATELINKMAT() link *p, *q, *l, *cpsmax;int i, j, m, n, t, s;datatype v;scanf(“%d %d %d”, if ( m n ) s = m;else s = n;l = malloc(sizeof(link);l-i = m; l-j = n;cp0 = l;for ( i = 1; i i = 0; p-j = 0;p-rptr = p; p-cptr = p;cpi = p; cpi-1-uval.next = p; cps = x = 1;
