数据结构 - 数组的存储表示和实现

1. 采用书上第93页定义的数组的顺序存储表示，编程实现数组的下列基本操作
   （1） 构造数组 （2）销毁数组 （3）取数组元素值 （4） 给数组元素赋值
   2.采用书上第98页定义的稀疏矩阵的三元组顺序表存储表示，编程实现矩阵的转置运算算法和快速转置算法。

7.1

#include<malloc.h>
#include<stdio.h>
#include<process.h>
#include<math.h>
#include<stdarg.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAX_ARRAY_DIM 8
typedef int Status;
typedef int Boolean;
typedef int ElemType;
typedef struct {
ElemType* base; //锟斤拷锟斤拷幕锟斤拷锟街?
int dim;
int* bounds; //锟斤拷维锟侥斤拷
int* constants; //锟斤拷址锟斤拷锟斤拷锟斤拷系锟斤拷
}Array;
Status InitArray(Array* A, int dim, ...) {
int elemtotal = 1;
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);
va_start(ap, dim);
for (int 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 (int 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) {
free((*A).base);
(*A).base = NULL;
}
else return ERROR;
if ((*A).bounds) {
free((*A).bounds);
(*A).bounds = NULL;
}
else return ERROR;
if ((*A).constants) {
free((*A).constants);
(*A).constants = NULL;
}
else return ERROR;
return OK;
}
Status Locate(Array A, va_list ap, int* off) {
int ind;
*off = 0;
for (int 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 , ...)
{
va_list ap;
Status result;
int off;
va_start(ap, e);
if ((result = Locate(*A, ap, &off)) == OVERFLOW)
return result;
*e = *((*A).base + off);
return OK;
}
Status Assign(Array* A, ElemType e, ...) {
va_list ap;
Status result;
int off;
va_start(ap, e);
if ((result = Locate(*A, ap, &off)) == OVERFLOW)
return result;
*((*A).base + off) = e;
return OK;
}
int main() {
Array A;
ElemType e = 0;
InitArray(&A, 3, 3, 3, 3);
Assign(&A, 10, 0, 1, 2);
if (Value(&A, &e, 0, 1, 2) == OK) printf("锟斤拷锟絜锟斤拷值: %dn", e);
if (DestroyArray(&A) == OK) printf("锟斤拷锟斤拷A锟斤拷锟劫成癸拷! n");
return 0;
}

7.2

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 12500
#define MU 5
#define NU 6
#define OK 1
typedef struct {
int i,j;
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
int CreateMatrix(TSMatrix &M){
int e,i,j,k=1;
M.mu=MU;
M.nu=NU;
srand((unsigned)time(NULL));
M.tu=rand()%15;
if(M.tu<1) return 0;
for(i=1;i<=M.mu;i++)
for(j=1;j<=M.nu;j++)
{e=rand()%30;
if(e!=0){
M.data[k].i=i;
M.data[k].j=j;
M.data[k].e=e;
k++;
}
if(k-1==M.tu) return OK;
}
return OK;
}
void print(TSMatrix M){
int k;
printf("mu=%-2d, nu=%-2d, tu=%-2d",M.mu,M.nu,M.tu);
printf("n");
for(k=1;k<=M.tu;k++)
{printf("i=%-2d, j=%-2d, e=%-2d",M.data[k].i,M.data[k].j,M.data[k].e);
printf("n");
}
}
int TransposeSMatrix(TSMatrix M,TSMatrix &T){
int p,q=1,col;
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
if(T.tu){
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 FastTransposeSMatrix(TSMatrix M,TSMatrix &T){
T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;
int num[NU+1]={0};
int cpot[NU+1]={0};
int p,q,col;
for(q=1;q<=M.tu;q++) num[M.data[q].j]++;
cpot[1]=1;
for(q=2;q<=M.nu;q++) cpot[q]=cpot[q-1]+num[q-1];
for(p=1;p<=M.tu;p++)
{col=M.data[p].j;
q=cpot[col];
T.data[q].e=M.data[p].e;
T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
++cpot[col];
}
return OK;
}
int main(){
TSMatrix M,T,S;
CreateMatrix(M);
TransposeSMatrix(M,T);
FastTransposeSMatrix(M,S);
printf("输出稀疏矩阵M：n");
print(M);
printf("输出转置矩阵T：n");
print(T);
printf("输出转置矩阵S：n");
print(S);
return 0;
}

最后

以上就是清新火龙果为你收集整理的数据结构 - 数组的存储表示和实现的全部内容，希望文章能够帮你解决数据结构 - 数组的存储表示和实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。