數據結構基礎—數組和廣義表

一、數組

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;

二、廣義表：

1.廣義表的定義

遞歸定義的線性結構

是一個集合：每一個元素要不是一個原子，要不就是一個廣義表(遞歸)

• 有順序：一一對應，和線性表不同，元素類型不同

• 線性表：特殊的廣義表，深度為1(一個括弧一個深度)

原子的深度是0，一個括弧一個深度(空表 S = ()：長度0，深度為1,但是S1 = (S) =（())不是空表，深度為1)

2.性質：

• 遞歸定義的線性結構：兩層含義：元素是一個另一個廣義表，元素可以是本身

• 長度為最外層的元素個數

• 深度為括弧數(括弧的重數) = max子表深度 +1(原子深度為零)

• 多層次的線性表，有相對次序

• 可以共用

• 任何一個非空表可以分為頭尾表示

3.頭尾表示

表頭是第一個元素，表尾剩餘所有元素組成的表(永遠是表)

4.表示方法（存儲）

• 頭尾指針鏈表

每個節點：表結點，原子結點(共用體)

表結點：兩個指針：頭、尾

• 子表分析法(孩子兄弟分析法)