[数据结构]第五章
第五章-数组和广义表
数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。
5.1 数组的定义
当n=1时，n维数组就退化为定长的线性表。反之，n维数组也可以看成是线性表的推广。数组一旦被定义，它的维数和维界就不再改变。
typedef ElemType Array2[m][n]；
等价于
typedef ElemType Array1[n]；
typedef Array1 Array2[m]；
5.2 数组的顺序表示和实现
对于数组，一旦规定了它的维数和各维的长度，便可为它分配存储空间。下面是顺序存储表示和实现。
#include <stdarg.h>
#define MAX_ARRAY_DIM 8
typedef int ElemType;
typedef struct{
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
Status InitArray(Array *A, int dim,...)
{
int elemtotal;
int i;
va_list ap;
if ( dim < 1 || dim > MAX_ARRAY_DIM ){
return ERROR;
}
A->dim = dim;
A->bounds = (int *)malloc(dim * sizeof(int));
if (!A->bounds){
exit(OVERFLOW);
}
elemtotal = 1;
va_start(ap,dim);
for (i = 0; i < dim; ++i){
A->bounds[i] = va_arg(ap,int);
if (A->bounds[i] < 0){
return UNDERFLOW;
}
elemtotal += A->bounds[i];
}
va_end(ap);
A->base = (ElemType*)malloc(elemtotal * sizeof(ElemType));
if (!A->base){
exit(OVERFLOW);
}
A->constants = (int *)malloc(dim * sizeof(int));
if(!A->constants){
exit(OVERFLOW);
}
A->constants[dim - 1] = 1;
for(i = dim - 2; i >= 0; --i){
A->constants[i] = A->bounds[i+1] * A->constants[i+1];
}
return OK;
}
Status DestroyArray(Array *A)
{
if(!A->base){
return ERROR;
}
free(A->base);
A->base = NULL;
if(!A->bounds){
return ERROR;
}
free(A->bounds);
A->bounds = NULL;
if(!A->constants){
return ERROR;
}
free(A->constants);
A->constants = NULL;
return OK;
}
Status Locate(Array A,va_list ap,int &off)
{
int i;
int ind;
off = 0;
for (i = 0;i < A.dim; i++){
ind = va_arg(ap, int);
if (ind < 0 || ind >= A.bounds[i]){
return OVERFLOW;
}
off += A.constants[i] * ind;
}
return OK;
}
Status Value(Array *A, ElemType *e,...)
{
Status result;
int off;
va_list ap;
va_start(ap,e);
if ((result = Locate(*A,ap,off)) <= 0){
return result;
}
*e = *(A->base + off);
return OK;
}
Status Assign(Array *A, ElemType e,...)
{
Status result;
int off;
va_list ap;
va_start(ap,e);
if ((result = Locate(*A,ap,off)) <= 0){
return result;
}
*(A->base + off) = e;
return OK;
}
int _tmain(int argc, _TCHAR* argv[])
{
Array A;
int i,j,k,*p,dim = 3,bound1 = 3,bound2 = 4,bound3 = 2;
ElemType e,*p1;
InitArray(&A,dim,bound1,bound2,bound3);
p=A.bounds;
printf("A.bounds=");
for(i=0;i<dim;i++)
printf("%d ",*(p+i));
p=A.constants;
printf("nA.constants=");
for(i=0;i<dim;i++)
printf("%d ",*(p+i));
printf("n%d页%d行%d列矩阵元素如下:n",bound1,bound2,bound3);
for(i=0;i<bound1;i++)
{
for(j=0;j<bound2;j++)
{
for(k=0;k<bound3;k++)
{
Assign(&A,i*100+j*10+k,i,j,k);
Value(&A,&e,i,j,k);
printf("A[%d][%d][%d]=%2d ",i,j,k,e);
}
printf("n");
}
printf("n");
}
p1=A.base;
printf("A.base=n");
for(i=0;i<bound1*bound2*bound3;i++)
{
printf("%4d",*(p1+i));
if(i%(bound2*bound3)==bound2*bound3-1)
printf("n");
}
DestroyArray(&A);
return 0;
}
5.3 矩阵的压缩存储
矩阵的压缩存储：为多个值相同的元只分配一个存储空间，对零元不分配空间。假若值相同的元素或者零元素在矩阵中的分布有一定规律，则我们称此类矩阵为特殊矩阵；反之称为稀疏矩阵。
5.3.1 特殊矩阵
对于对称矩阵，我们可以为每一对对称元分配一个存储空间，则可将n2个元压缩存储到n(n+1)/2个元的空间中。
所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c或零的n阶矩阵。
对这类矩阵，我们也可按某个原则(或以行为主，或以对角线的顺序)将其压缩存储到一维数组上。
5.3.2 稀疏矩阵
其非零元较零元少，且分布没有一定规律，我们称之为稀疏矩阵。按照压缩存储的概念，只存储稀疏矩阵的非零元。因此除了存储非零元的值之外，还必须同时记下它所在行和列的位置(i,j)。
typedef int ElemType;
#define MAXSIZE 100
typedef struct {
int i,j;
ElemType e;
}Triple;
typedef struct {
Triple data[MAXSIZE + 1];
int mu,nu,tu;
}TSMatrix;
Status CreateSMatrix(TSMatrix *M)
{
int i;
int m,n,e;
Status k;
printf("请输入矩阵的行数,列数,非零元素数：");
scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);
(*M).data[0].i = 0;
for(i = 1; i <= (*M).tu; i++){
do{
printf("请按行序顺序输入第%d个非零元素所在的行(1～%d),列(1～%d),元素值：",i,(*M).mu,(*M).nu);
scanf("%d,%d,%d", &m, &n, &e);
k = 0;
if(m < 1 || m > (*M).mu || n < 1 || n > (*M).nu){
k = 1;
}
if(m <= (*M).data[i-1].i && n <= (*M).data[i-1].j){
k = 1;
}
}while(k);
(*M).data[i].i = m;
(*M).data[i].j = n;
(*M).data[i].e = e;
}
return OK;
}
void DestroySMatrix(TSMatrix *M)
{
(*M).mu = 0;
(*M).nu = 0;
(*M).tu = 0;
}
void PrintSMatrix(TSMatrix M)
{
int i;
printf("%d行%d列%d个非零元素。n", M.mu, M.nu, M.tu);
printf("行 列 元素值n");
for(i = 1; i <= M.tu; i++){
printf("%2d%4d%8dn", M.data[i].i, M.data[i].j, M.data[i].e);
}
}
Status CopySMatrix(TSMatrix M,TSMatrix *T)
{
(*T) = M;
return OK;
}
Status TransposeSMatrix(TSMatrix M, TSMatrix *T)
{
int q;
int col,p;
(*T).mu = M.mu;
(*T).nu = M.nu;
(*T).tu = M.tu;
if ((*T).tu != 0){
q = 1;
for(col = 1; col <= M.nu; col++){
for(p = 1; p <= M.tu; p++){
if (M.data[p].j == col){
T->data[q].i = M.data[p].j;
T->data[q].j = M.data[p].i;
T->data[q].e = M.data[p].e;
++q;
}
}
}
}
return OK;
}
int comp(int c1,int c2)
{
int i;
if(c1 < c2){
i = 1;
}
else if(c1 == c2){
i = 0;
}
else{
i = -1;
}
return i;
}
Status AddSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)
{
Triple *Mp,*Me,*Np,*Ne,*Qh,*Qe;
if(M.mu != N.mu || M.nu != N.nu){
return ERROR;
}
(*Q).mu = M.mu;
(*Q).nu = M.nu;
Mp = &M.data[1];
Np = &N.data[1];
Me = &M.data[M.tu];
Ne = &N.data[N.tu];
Qh = Qe = (*Q).data;
while( Mp <= Me && Np <= Ne ){
Qe++;
switch(comp(Mp->i, Np->i)){
case 1:
*Qe = *Mp;
Mp++;
break;
case 0:
switch(comp(Mp->j,Np->j)){
case 1:
*Qe = *Mp;
Mp++;
break;
case 0:
*Qe = *Mp;
Qe->e += Np->e;
if(!Qe->e){
Qe--;
}
Mp++;
Np++;
break;
case -1:
*Qe = *Np;
Np++;
break;
}
break;
case -1:
*Qe = *Np;
Np++;
break;
}
}
if(Mp > Me){
while(Np <= Ne){
Qe++;
*Qe = *Np;
Np++;
}
}
if(Np > Ne){
while(Mp <= Me){
Qe++;
*Qe = *Mp;
Mp++;
}
}
(*Q).tu = Qe - Qh;
return OK;
}
Status SubtSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)
{
int i;
for(i = 1; i <= N.tu; i++){
N.data[i].e *= -1;
}
AddSMatrix(M,N,Q);
return OK;
}
Status MultSMatrix(TSMatrix M, TSMatrix N, TSMatrix *Q)
{
int i,j,h=M.mu,l=N.nu,Qn=0;
ElemType *Qe;
if(M.nu != N.mu){
return ERROR;
}
(*Q).mu = M.mu;
(*Q).nu = N.nu;
Qe = (ElemType *)malloc(h * l * sizeof(ElemType));
for(i = 0; i < h * l; i++){
*(Qe + i) = 0;
}
for(i = 1; i <= M.tu; i++){
for(j = 1; j <= N.tu; j++){
if(M.data[i].j == N.data[j].i){
*(Qe + (M.data[i].i - 1) * l + N.data[j].j - 1) += M.data[i].e * N.data[j].e;
}
}
}
for(i = 1; i <= M.mu; i++){
for(j = 1;j <= N.nu; j++){
if(*(Qe+(i-1)*l+j-1)!=0){
Qn++;
}
(*Q).data[Qn].e = *(Qe + (i - 1) * l + j - 1);
(*Q).data[Qn].i = i;
(*Q).data[Qn].j = j;
}
}
free(Qe);
(*Q).tu = Qn;
return OK;
}
int _tmain(int argc, _TCHAR* argv[])
{
TSMatrix A,B,C;
printf("创建矩阵A: ");
CreateSMatrix(&A);
PrintSMatrix(A);
printf("由矩阵A复制矩阵B: ");
CopySMatrix(A,&B);
PrintSMatrix(B);
DestroySMatrix(&B);
printf("销毁矩阵B后:n");
PrintSMatrix(B);
printf("创建矩阵B2:(与矩阵A的行、列数相同，行、列分别为%d,%d)n",A.mu,A.nu);
CreateSMatrix(&B);
PrintSMatrix(B);
printf("矩阵C1(A+B): ");
AddSMatrix(A,B,&C);
PrintSMatrix(C);
DestroySMatrix(&C);
printf("矩阵C2(A-B): ");
SubtSMatrix(A,B,&C);
PrintSMatrix(C);
DestroySMatrix(&C);
printf("矩阵C3(A的转置): ");
TransposeSMatrix(A,&C);
PrintSMatrix(C);
DestroySMatrix(&A);
DestroySMatrix(&B);
DestroySMatrix(&C);
printf("创建矩阵A2: ");
CreateSMatrix(&A);
PrintSMatrix(A);
printf("创建矩阵B3:(行数应与矩阵A2的列数相同=%d)n",A.nu);
CreateSMatrix(&B);
PrintSMatrix(B);
printf("矩阵C5(A*B): ");
MultSMatrix(A,B,&C);
PrintSMatrix(C);
DestroySMatrix(&A);
DestroySMatrix(&B);
DestroySMatrix(&C);
return 0;
}
相关知识
数据结构
Android数据结构与算法之一 基础简介
重读《学习JavaScript数据结构与算法
浅谈Python数据结构(三)
第五章杂交育种
第五章花卉繁殖
第五章西方插花艺术
第五章花卉的应用.pptx
第五章花卉的繁殖.ppt
第五章 西方传统插花艺术
网址: [数据结构]第五章 https://m.huajiangbk.com/newsview1031170.html
| 上一篇: 种南瓜的方法和技术 |
下一篇: 白果市场分析报告 |
