数据结构C语言版第五章 数组和广义表.doc
文本预览下载声明
第五章 数组和广义表
重点难点
理解数组和广义表两种数据结构的特点，并掌握数组在以行为主的存储表示中的地址计算方法；掌握特殊矩阵的存储压缩表示方法；了解广义表的两种链式存储结构。
典型例题
1. 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：
(1)用i , j 表示k的下标变换公式。
(2)用 k 表示 i,j 的下标变换公式。
解(1)?
要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为：
(i*3-1)+j-(i+1)?
其中 (i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数
化简可得：
k=2i+j; // c下标是从0开始的。
(2) 因为K和i,j是一一对应的关系，因此这也不难算出：
i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号
j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素，
//加上前面的0元素所点列数就是当前列号 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?
解：
? (1)因含5*6=30个元素，因此A共占30*4=120个字节。
? (2)a45的起始地址为：
???? Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116
? (3)按行优先顺序排列时，
???? a25=1000+(2*6+5)*4=1068
? (4)按列优先顺序排列时：(二维数组可用行列下标互换来计算)
???? a25=1000+(5*5+2)*4=1108 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。
解：
矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。
#define MaxSize 10 //用户自定义
typedef int DataType; //用户自定义
typedef struct
{ //定义三元组
int i,j;
DataType v;
}TriTupleNode;
typedef struct
{ //定义三元组表
TriTupleNode data[MaxSize];
int m,n,t;//矩阵行，列及三元组表长度
}TriTupleTable;
//以下为矩阵加算法?
void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C)
{//三元组表表示的稀疏矩阵A,B相加
int k,l;
DataType temp;
C-m=A-m;//矩阵行数
C-n=A-n;//矩阵列数
C-t=0; //三元组表长度
k=0; l=0;
while (kA-tlB-t)
{if((A-data[k].i==B-data[l].i)(A-data[k].j==B-data[l].j))
{temp=A-data[k].v+B-data[l].v;
if (!temp)//相加不为零，加入C
{C-data[c-t].i=A-data[k].i;
C-data[c-t].j=A-data[k].j;
C-data[c-t++].v=temp;
}
k++;l++;
}
if ((A-data[k].i==B-data[l].i)(A-data[k].jB-data[l].j))
||(A-data[k].iB-data[l].i)//将A中三元组加入C
{C-data[c-t].i=
显示全部