資料結構基礎—陣列和廣義表

一、陣列

1.資料的定義

陣列類似于線性表，就是多維結構的順序表，

2.稀疏陣列

a.稀疏陣列的定義：

假設m行n列的矩陣中含有t個非零元素若t/(m*n) <= 0.05，則稱該矩陣為稀疏矩陣

稀疏矩陣也分為特殊矩陣和隨機矩陣隨機

特殊矩陣：三角，對角...
隨機矩陣：非零元素隨機出現

b.隨機稀疏矩陣的壓縮存盤方式

三元組順序表：

又稱為雙下標法，特點是有序存盤，便于依次處理矩陣，隨機性不夠高

typedef struct{
    int i,j;//非零的行下標和列下標
    ElemType e;//非零的值
}Triple;//三元組
typedef union{
    Triple data[MaxSize+1];//非零元素資訊
    int mu,nu,tu;//矩陣的行，列，和非零個數
}TSMatrix;//稀疏矩陣

小應用：如何求轉置

利用三元組來實作

T.data[p].i = M.data[p].j;
T.data[p].j = M.data[p].i;
T.data[p].e = M.data[p].e;

問題，行列非零順序不同(一個按行，一個按列放)

將原矩陣按列放

num原矩陣按列，轉置矩陣按行做標記(有非零元，則該位置+1)

先全部置零，然后遍歷所有非零元，讓num[其列數]++，這樣就記錄了轉置后矩陣每行非零元的個數

cpot:其初值值代表了，在轉置矩陣的新行中首次出現的位置(，在該位置前已經有了所有非零原的位置(個數)，即，該數就是新轉置矩陣的第spot個元素)，每次匹配完記得讓其值++(原矩陣中某列可能含有多個元素，匹配完一個后數值要增加，僅僅對該行(列產生影響)，后一行(列的數不受影響))

//已知 TSMatrix T;
//求轉置
	TSMatrix GetTran(){
		TSMatrix M;//轉置矩陣
		M.mu = T.nu;
		M.nu = T.mu; 
		M.tu = T.tu;
		int col; 
		int num[MaxSize+1];
		int cpot[MaxSize+1];
		
		if(M.tu){
		    for(col = 1;col <= T.nu;col++) {
			    num[col] = 0; //先把陣列置零			
		    }
		    for(int t = 1;t <= T.tu;t++) {
			    num[T.data[t].j]++; //記錄每一列非零元素個數 []中是列數，而陣列的大小則是每列的個數(桶排序，標記)		
		    }
		    cpot[1]=1; 
		    //在轉置矩陣的col行中首次出現的位置
	    	for(col = 2;col <= T.nu;col++) 
		    	cpot[col] = cpot[col-1]+num[col-1];
		    //轉置開始
		    for(int p = 1;p <= T.tu;p++){
			    col=T.data[p].j; //讀取原三元組第p個元素的列
			    int q = cpot[col]; //q：p在轉置矩陣的col行中非零首次出現的位置(次序)
		    	M.data[q].i=T.data[p].j;
			    M.data[q].j=T.data[p].i;
			    M.data[q].e=T.data[p].e;
			    cpot[col]++;
		    }
	    }
		return M; 
	}

行邏輯聯接的順序表

typedef struct {
        int i,j;//非零元的行列 
        int e;//元素大小 
    }triple;//三元組
typedef struct{
	triple data[MaxSize+1];//非零資訊 
	int rpos[MAXRC+1];//行每行首非零元的位置(就是該行第一個非零元素是第幾個非零元和那個求轉置時是一樣的) 
	int mu, nu, tu;//行，列，個數 
}RLSMatrix;// 行邏輯鏈接順序表型別

十字鏈表

typedef struct Lnode{ 
    int row, col;
    int element;
    struct Lnode* right;
    struct Lnode* down;
}Node, *LNode;

//十字鏈表
typedef struct { //十字鏈表
    LNode* rowHead;
    LNode* colHead;
    int rows, cols, nzeroNums; //行數、列數、非0元素個數
}Cross, *LCross;