數(shù)組的定義
數(shù)組是由n個(gè)類(lèi)型相同的數(shù)據(jù)元素組成的有限序列汁尺。其中法精，這n個(gè)數(shù)據(jù)元素占用一塊地址連續(xù)的存儲(chǔ)空間。數(shù)組中的數(shù)據(jù)元素可以是原子類(lèi)型均函，如整型亿虽、字符型、浮點(diǎn)型等苞也，統(tǒng)稱(chēng)為一維數(shù)組洛勉；也可以是一個(gè)線(xiàn)性表，這種類(lèi)型的數(shù)組稱(chēng)為二維數(shù)組如迟。
數(shù)組的抽象類(lèi)型定義如下：
ADT Array{
數(shù)據(jù)對(duì)象收毫；
數(shù)據(jù)關(guān)系；
基本操作：
InitArray(Array &A,int dim,...)
操作結(jié)果：若維數(shù)dim和隨后的各維長(zhǎng)度合法殷勘，則構(gòu)造相應(yīng)的數(shù)組A
DestroyArray(Array &A)
初始條件：存在數(shù)組
操作結(jié)果：銷(xiāo)毀數(shù)組A
Value(Array A,ElemType &e,...)
初始條件：存在數(shù)組
操作結(jié)果：A是n維數(shù)組此再，e為元素變量，隨后是n個(gè)下標(biāo)值玲销；若下表不超界输拇，則將e賦值為所指定的A的元素
Assign(Array &A,ElemType e,...)
初始條件：存在數(shù)組
操作結(jié)果：A是n維數(shù)組，e為元素變量贤斜，隨后是n個(gè)下標(biāo)值策吠；若下表不超界，則將e賦值給所指定的A的元素
}
數(shù)組的順序表示與實(shí)現(xiàn)
1.宏定義解釋
#include<stdarg.h> 標(biāo)準(zhǔn)頭文件瘩绒，提供va_start猴抹、va_arg等
#define MAX_ARRAY_DIM 8 //假設(shè)數(shù)維數(shù)最大值為8
2.結(jié)構(gòu)類(lèi)型
typedef struct{
ElemType *base; //數(shù)組元素的基址
int dim; //數(shù)組維數(shù)
int *bounds; //數(shù)組維屆基址
int *constants; //數(shù)組映像函數(shù)常量基址
}Array;
特殊矩陣的壓縮存儲(chǔ)
在矩陣的運(yùn)算中往往會(huì)出現(xiàn)階數(shù)很高的矩陣中存在許多相同的元素或者值為0的元素。為了節(jié)省空間需要將這些矩陣進(jìn)行壓縮存儲(chǔ)锁荔。
1.對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)
如果一個(gè)n階矩陣A中的元素滿(mǎn)足性質(zhì)aij = aji蟀给，則稱(chēng)這樣的矩陣為n階對(duì)稱(chēng)矩陣。由于對(duì)稱(chēng)矩陣中的元素關(guān)于主對(duì)角線(xiàn)對(duì)稱(chēng)阳堕，因此在對(duì)矩陣存儲(chǔ)時(shí)跋理，可以只存儲(chǔ)對(duì)稱(chēng)矩陣中的上三角或者下三角元素，使得對(duì)稱(chēng)的元素共享一個(gè)存儲(chǔ)單元恬总，這樣就可以實(shí)現(xiàn)壓縮的目的前普。
假設(shè)一維數(shù)組s存儲(chǔ)對(duì)稱(chēng)矩陣A的上三角或者下三角元素，則一維數(shù)組s的下標(biāo)k與n階對(duì)稱(chēng)矩陣A的元素aij之間的對(duì)稱(chēng)關(guān)系為：
其中當(dāng)i>=j時(shí)表示的是下三角的情況越驻，而i<j時(shí)表示的是上三角的情況。
2.三角矩陣的壓縮存儲(chǔ)
三角矩陣分為兩種：上三角矩陣和下三角矩陣。其中缀旁，下三角元素均為常數(shù)或0的n階矩陣稱(chēng)為上三角矩陣记劈，反之則稱(chēng)為下三角矩陣。在三角矩陣中并巍，重復(fù)元素可以用一個(gè)存儲(chǔ)單元來(lái)進(jìn)行存儲(chǔ)目木，而其他的元素可以用對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)方式來(lái)存儲(chǔ)。
如果用一維數(shù)組來(lái)存儲(chǔ)三角矩陣懊渡，則需要存儲(chǔ)n* (n+1)/2+1個(gè)元素刽射。一維數(shù)組的下標(biāo)k與矩陣的下標(biāo)(i,j)的對(duì)應(yīng)關(guān)系為：
其中n*(n+1)/2這個(gè)位置是用來(lái)存放常數(shù)或者0元素的。
3.對(duì)角矩陣的壓縮存儲(chǔ)
對(duì)角矩陣就是所有的非0元素都集中在主對(duì)角線(xiàn)兩側(cè)的帶狀區(qū)域內(nèi)（對(duì)角線(xiàn)的個(gè)數(shù)為奇數(shù)）剃执。也就是說(shuō)除了主對(duì)角線(xiàn)和其兩邊的對(duì)角線(xiàn)外誓禁，其他元素的值均為0。
對(duì)角矩陣具有如下特點(diǎn)：
- 第一行和最后一行有2個(gè)非零元素肾档，第2-n-1行有3個(gè)非零元素摹恰。
- 前i-1行有3*(i-1)-1個(gè)非零元素，第i行的非零元素個(gè)數(shù)為j-i+1當(dāng)j<i時(shí)怒见，j-i = -1當(dāng)j>i時(shí)j-i=1俗慈。
- 使用一維數(shù)組存儲(chǔ)，需要存儲(chǔ)3*n-2個(gè)元素遣耍。
- 一維數(shù)組s[k]和A[i][j]的對(duì)應(yīng)關(guān)系為：k = 2*i+j闺阱。
4.稀疏矩陣的壓縮存儲(chǔ)
稀疏矩陣是指在m x n矩陣中，有t個(gè)元素不為0舵变，且t/(m+n)<=0.05酣溃，我們把這樣的矩陣叫做稀疏矩陣。也就是說(shuō)矩陣中存在大多數(shù)為0的元素棋傍，只有很少的非0元素救拉，這樣的矩陣就是稀疏矩陣。由于稀疏矩陣中的非0元素很少瘫拣，因此稀疏矩陣也需要進(jìn)行壓縮存儲(chǔ)亿絮。
稀疏矩陣的抽象類(lèi)型定義如下：
ADT SparseMatrix{
數(shù)據(jù)對(duì)象；
數(shù)據(jù)關(guān)系麸拄；
基本操作：
CreateMatrix(&M)
操作結(jié)果：創(chuàng)建稀疏矩陣
DestroyMatrix(&M)
初始條件：存在稀疏矩陣
操作結(jié)果：銷(xiāo)毀稀疏矩陣M
PrintSMatrix(M)
初始條件派昧；存在稀疏矩陣
操作結(jié)果：輸出稀疏矩陣M
CopyMatrix(M,&N)
初始條件：存在稀疏矩陣
操作結(jié)果：由稀疏矩陣M復(fù)制得到T
TransposeSMatrix(M,&N)
初始條件：存在稀疏矩陣
操作結(jié)果：求稀疏矩陣M的轉(zhuǎn)置矩陣T
}
稀疏矩陣的表示與實(shí)現(xiàn)
為了實(shí)現(xiàn)壓縮存儲(chǔ)，可以只存儲(chǔ)稀疏矩陣中的非0元素拢切。在存儲(chǔ)稀疏矩陣中的非0元素時(shí)蒂萎，還必須存儲(chǔ)非0元素對(duì)應(yīng)的行和列的位置(i,j)。也就是說(shuō)淮椰，存儲(chǔ)一個(gè)非0元素需要存儲(chǔ)元素的行號(hào)列號(hào)和元素的值五慈。在這里我們可以采用三元組的方式來(lái)進(jìn)行存儲(chǔ)纳寂。
1.宏定義解釋
#define MaxSize 200 //三元組的個(gè)數(shù)
#typedef DataType int; //定義為int類(lèi)型
2.結(jié)構(gòu)類(lèi)型
typedef struct{
int i; //行號(hào)
int j; //列號(hào)
DataType e; //值
}Triple;
//定義矩陣
typedef struct{
Triple data[Maxsize];
int m; //矩陣的行數(shù)
int n; //矩陣的列數(shù)
int len; //非0元素的個(gè)數(shù)
}TriSeqMatrix;
3.基本操作的實(shí)現(xiàn)
（1）創(chuàng)建稀疏矩陣CreatMatrix
int CreatMatrix(TriSeqMatrix *M){
int i,m,n;
DataType e;
int flag; //設(shè)置標(biāo)志位
cout<<"Enter the number of rows, columns, and non-zero elements:"<<endl; //輸入行數(shù)、列數(shù)和非0元素的個(gè)數(shù)
cin>>M->m;
cin>>M->n;
cin>>M->len;
if(M->len>Maxsize){ //如果超過(guò)最大容量則返回0
return 0;
}
for(i=0;i<M->len;i++){ //開(kāi)始輸入
do{
cout<<"Enter the number of rows,columns and values for the NO."<<i+1<<"number"<<endl; //輸入每一個(gè)非0元素的行數(shù)列數(shù)與數(shù)值
cin>>m;
cin>>n;
cin>>e;
flag=0; //初始化標(biāo)志位
if(m<0||m>M->m||n<0||n>M->n){ //如果輸入錯(cuò)誤泻拦，則標(biāo)志位為0
flag=0;
}
if(i>0&&m<M->data[i-1].i||m==M->data[i-1].i&&n<=M->data[i-1].j){
flag=1;
}
}while(flag)
M->data[i].i=m;
M->data[i].j=n;
M->data[i].e=e;
}
return 1;
}
（2）銷(xiāo)毀稀疏矩陣DestroyMatrix
void DestroyMatrix(TriSeqMatrix *M){
M->m=M->n=M->len=0; //全部置為零
}
（3）矩陣的復(fù)制CopyMatrix
void CopyMatrix(TriSeqMatrix M,TriSeqMatrix *N){
//稀疏矩陣M復(fù)制得到另一個(gè)矩陣N
int i;
N->len = M.len;
N->m = M.m;
N->n = M.n;
for(i=0;i<M.len;i++){
N->data[i].i=M.data[i].i;
N->data[i].j=M.data[i].j;
N->data[i].e=M.data[i].e;
}
}
（4）矩陣的轉(zhuǎn)置TransposeMatrix
void TransposeMatrix(TriSeqMatrix M,TriSeqMatrix *N){
int i,k,col;
N->m=M.n;
N->n=M.m;
N->len=M.len;
if(N->len){
k=0;
for(col=0;col<M.n;col++){ //按照列號(hào)開(kāi)始掃描三元組
for(i=0;i<M.len;i++){
if(M.data[i].j==col){ //如果列號(hào)是當(dāng)前的列毙芜，則進(jìn)行轉(zhuǎn)置
N->data[k].i=M.data[i].j;
N->data[k].j=M.data[i].i;
N->data[k].e=M.data[i].e;
k++;
}
}
}
}
}
稀疏矩陣的十字鏈表表示與實(shí)現(xiàn)
稀疏矩陣的十字鏈表表示就是采用鏈?zhǔn)酱鎯?chǔ)的方式來(lái)進(jìn)行的，鏈表中的每個(gè)結(jié)點(diǎn)存儲(chǔ)稀疏矩陣中的每個(gè)非0元素争拐。每個(gè)結(jié)點(diǎn)包含5個(gè)域：3個(gè)數(shù)據(jù)域和2個(gè)指針域腋粥。其中3個(gè)數(shù)據(jù)域分別表示非0元素的行號(hào)、列號(hào)以及元素值架曹；2個(gè)指針域是right域和down域隘冲，right指向同一行中的下一個(gè)非0元素，down指向同一列的非0元素绑雄。
1.宏定義解釋
#typedef int DataType; //定義為int類(lèi)型
2.結(jié)構(gòu)類(lèi)型
typedef struct OLNode{ //定義結(jié)點(diǎn)
int i,j; //非0元素行號(hào)與列號(hào)
DataType e; //非0元素值
struct OLNode *right,*down; //同一行與同一列下一個(gè)非0元素
}OLNode,*OLink;
typedef struct{ //定義鏈表
OLink *rowhead,*colhead; //指向行鏈表與列鏈表的指針
int m,n,len; //稀疏矩陣的行數(shù)展辞、列數(shù)與非0元素的個(gè)數(shù)
}CrossList;
3.具體操作的實(shí)現(xiàn)
（1）初始化稀疏矩陣InitMatrix
void InitMatrix(CrossList *M){
M->rowhead=M->colhead=NULL;
M->m=M->n=M->len=0;
}
**（2）創(chuàng)建稀疏矩陣CreatMatrix
void CreateMatrix(CrossList *M){
int i,k;
int m,n,num;
OLNode *p,*q;
cout<<"enter the number of rows, columns, and non-zero elements:"<<endl;
cin>>m;
cin>>n;
cin>>num;
M->m=m;
M->n=n;
M->len=num;
M->rowhead=(OLink*)malloc(m*sizeof(OLink));
if(!M->rowhead){
exit(-1);
}
for(k=0;k<m;k++){
M->rowhead[k]=NULL;
}
for(k=0;k<n;k++){
M->colhead[k]=NULL;
}
printf("按照次序輸入%d個(gè)非0元素的行號(hào)、列號(hào)以及元素值:",M->len);
for(k=0;k<num;k++){
p=(OLNode*)malloc(sizeof(OLNode));
if(!p){
exit(-1);
}
scanf("%d %d %d",&p->i,&p->j,&p->e);
if(M->rowhead[p->i]==NULL||M->rowhead[p->i]->j>p->j){
p->right=M->rowhead[p->i];
M->rowhead[p->i]=p;
}
else{
q=M->rowhead[p->i];
while(q->right&&q->right->j<p->j)
q=q->right;
p->right=q->right;
q->right=p;
}
q=M->colhead[p->j];
if(!q||p->i<q->i){
p->down=M->colhead[p->j];
M->colhead[p->j]=p;
}
else{
while(q->down&&q->down->i<p->i)
q=q->down;
p->down=q->down;
q->down=p;
}
}
}
**（3）稀疏矩陣的插入InsertMatrix
void InsertMatrix(CrossList *M,OLink p){
//按照行序?qū)插入到稀疏矩陣中
OLink q=M->rowhead[p->i];
if(!q||p->j<q->j){
p->right=M->rowhead[p->i];
M->rowhead[p->i]=p;
}
else{
while(q->right&&q->right->j<p->j){
q=q->right;
}
p->right=q->right;
q->right=p;
}
q=M->colhead[p->i];
if(!q||p->i<q->i){
p->down=M->colhead[p->j];
M->colhead[p->j]=p;
}
else{
while(q->down&&q->down->i<p->i){
q=q->down;
}
p->down=q->down;
q->down=p;
}
M->len++;
}
**（4）稀疏矩陣的銷(xiāo)毀DestroyMatrix
void DestroyMatrix(CrossList *M){
int i;
OLink p,q;
for(i=0;i<M->m;i++){ //開(kāi)始按照行釋放結(jié)點(diǎn)
p=*(M->rowhead+i);
while(p){
q=p;
p=p->right;
free(q);
}
}
free(M->rowhead); //釋放行鏈表
free(M->colhead); //釋放列鏈表
InitMatrix(M);
}
