---
tags: 資料結構
---
# 資料結構 第二章 陣列結構

## 一、陣列抽象資料型態(The Array As An Abstract Data Type)
陣列是一組成對的<index，value>，每個索引都有關聯的值(映射)。
### 定義陣列操作
【變數設定】
for all A belong to Array, i belong to index, x belong to item, j, size belong to integer

(一)Array Create(j, list)：創造一個陣列（J:陣列名稱、list:陣列大小)

(二)Item Retrieve(A, i)：前提假設(i屬於陣列的索引)，將取出陣列A[i]的值，若前提假設不成立則回傳error

(三)Array Store(A,i,x)：前提假設(i屬於陣列的索引)，將x取代原本陣列A[i]裡面的值，若前提假設不成立則回傳error

## 二、多項式抽象資料型態(The Polynomial Abstract Data Type)
### 定義多項式操作
【變數設定】
for all poly, poly1, poly2 belong to Polynomial, coefe belong to Coefficients, expon belong to Exponents
（一）Polynomial Zero()：回傳多項式為零（F(x)=0）
（二）Boolean IsZero(poly)：判斷多項式是否為零（零回傳True，otherwise回傳False）
（三）Coefficient Coef(poly,expon)：前提假設（指數屬於poly），回傳該指數的係數，若前提假設不成立（代表該多項式沒有這個指數項）則回傳零。
（四）Exponent Lead-Exp(poly)：回傳最大的指數項。
（五）Polynomial Attach(poly, coef, expon)：前提假設（指數屬於多項式）回傳error，前提假設不成立，則插入指定coef x^expon項
（六）Polynomial Remove(poly, expon)：前提假設（指數屬於多項式）將刪除指定的指數項，若前提假設不成立則回傳error
（七）Polynomial SingleMult(poly, coef, expon)：回傳整個多項式
（八）Polynomial Add(poly1, poly2)：回傳兩個多項式相加
（九）Polynomial Mult(poly1, poly2)：回傳兩個多項式相乘
### 多項式儲存方式
#### 【課本範例】
#### 【其他方法】

【加法操作】
void padd(int starta, int finisha, int startb, int finishb, int *startd, int *finishd)
{
　while(starta <= finisha && startb <= finishb)
　switch(COMPARE(terms[starta].expon,terms[startb].expon))
{
　case -1:
attach(terms[startb].coef, terms[startb].expon);
startb++;
break;
　case 0:
coefficient =terms[starta].coef+terms[startb].coef
if(coefficient)
attach(terms[starta].coef,terms[starta].expon);
starta++;
}
　for(; starta <= finisha; starta++)
attach(terms[starta].coef,terms[starta.expon]);
　for(; startb <= finishb; startb++)
attach(terms[startb].coef,terms[startb].expon);
　*finishd= avail-1;
}

void attach(float coefficient, int exponent)
{
if(avail >= Max_Terms)
{
　fprint(stderr,"Too many terms in the polynomial\n");
　exit(1);
}
terms[avail].coef = coefficient;
terms[avail++].expon = exponent;
}

## 三、稀疏矩陣抽象資料型態(The Sparse Matrix Abstract Data Type)
### （一）定義多項式操作
【變數設定】
for all a,b　belong to Sparse_Matrix, x belong to item, i, j, max_col, max_row belong to index
（一）Sparse-Matrix Crcate(max-row, max-col) ：創造一個矩陣（列＊行）
（二）Sparse-Matrix Transpose(a)：將矩陣轉置（行列互換）
（三）Sparse-Matrix Add(ａ, b)：前提假設(兩個矩陣大小要一致)，回傳兩個矩陣相加，若前提假設不成立回傳error
（四）Sparse-Matrix Multiply(a, b)：前提假設（Ａ矩陣行數＝Ｂ矩陣的列數）回傳兩個矩陣相成，若前提不成立則回傳error

### （二）轉置矩陣(Transposing A Matrix)
void transpose(term a[], term b[])
{
int n, i, j, currentb;
n = a[0].value;
b[0].row = a[0].col;
b[0].col = a[0].row;
b[0].value = n;
if (n>0)
{
currentb = 1;
for(i = 0; i < a[0].col; i++)
for(j = 1; j<=n; j++)
if(a[j].col == i)
{
b[currentb].row = a[j].col;
b[currentb].col = a[j].row;
b[currentb].value = a[j].value;
currentb++;
}
}
}

---
void fast_transpose(term a[], term b[])
{
int row_terms[MAX_COL], starting_pos[MAX_COL];
int i, j, nim_cols = a[0].col, num_terms = a[0].value;
b[0].row = num_cols; b[0].col = a[0].row;
b[0].value = num_terms;
if(num_terms > 0)
{
for(i = 0; i < num_cols; i++)
row_terms[i] = 0;
for (i = 1; i <= num_terms; i++)
row_terms[a[i].col]++;
starting_pos[i] = starting_pos[i-1] + row_terms[i-1];
for(i = 1; i < num_cols; i++)
srarting_pos[i] = starting_pos[i-1] + row_terms[i-1];
for(i = 1; i <= num_terms; i++)
{
j = starting_pos[a[i].col]++;
b[j].row = a[i].col;
b[j].col = a[i].row;
b[j].value = a[i].value;
}
}
}

---

### （三）矩陣相乘 (Matrix Multiplication)
void mmult(term a[], term b[], term d[])
{
int i, j, column, totalb = b[0].value, totald = 0;
int rows_a = a[0].value; int cols_a = a[0].col, totala = a[0].value; int cols_b = b[0].col, int row_begin = 1, row = a[1].row, sum = 0;
int new_b[MAX_TERMS][3];
if(cols_a =! b[0].row)
{
fprintf(stderr,"Incompatible matrices\n");
exit(1);
}
fast_transpose(b,new_b);
a[totala+1].row = row_b;
new_b[totalb+1].col = 0;
for(i = 1; i <= totala;)
{
colum = new_b[1].row;
for(j = 1; j<= totalb+1;)
{
if (a[i].row != row)
{
storesum(d,&totald,row,column,&sum);
i = row_begin;
for(; new_b[j].row == column; j++);
column = new_b[j].row;
}
else if (new_b[j].row != column)
{
storesum(d, &totald, row, column, &sum);
i = row_begin;
column = new_b[j].row;
}
else switch(COMPARE(a[i].col, new_b[j].col))
{
case　-1：
i++;
break;
case　0：
sum += (a[i++].value * new_b[j++].value)
break;
case　1：
j++;

}
}
for(; a[i].row == row; i++);
row_begin = i;
row = a[i].row;
}
d[0].row = rows_a;
d[0].col = clo_b;
d[0].vale = totald;
}

### （四）特性
#### 1、討論矩陣特性【假設為n*n矩陣】
創造矩陣共計需準備n^2^格位置
##### (1)稀疏矩陣：因非零值個數不多導致浪費空間
##### (2)對稱矩陣：因是對稱矩陣所以Ａ~i~~j~=A~j~~i~故儲存空間只需準備一半
##### (3)上下三角矩陣：上三角(右上半部有值其餘為零)、下三角(左下半部有值其餘為零)
##### (4)寬待矩陣：對角線(含)左下x條斜線，右上y條斜線皆有值，其餘為零。

#### 2、儲存方式
##### (1)column-major：儲存方式以行為主（先儲存A~1~~1~,A~2~~1~,A~3~~1~....）
##### (2)Row-major：儲存方式以列為主（先儲存A~1~~1~,A~1~~2~,A~1~~3~....）

## 四、多維陣列(Multidimensional Arrays)
### (一)表示如下：
#### 三維陣列（立體）：A[i,j,k]
#### 四維陣列：A[i,j,k,l]
#### 多維陣列：A[i,j,k,l,....,z]
### (二)計算位址【以三維陣列為例】
#### A(1...u~1~, 1...u~2~, 1...u~3~)
#### **1.Row-major（由右至左）**
##### A[i,j,k]=l~0~+[(i-1)*(u~2~*u~3~)+(j-1)*u~3~+(k-1)]*d
#### **2.Column-major(由左至右)**
##### A[i,j,k]=l~0~+[(k-1)*(u~1~*u~2~)+(j-1)*u~1~+(i-1)]*d
##### l~0~ ：初始位址、ｄ：為一個位置的空間大小

## 字串抽象數據型態(The String Abstract Data Type)
### 定義多項式操作
（一）String Null(m)：回傳空字串(長度為m)
（二）Integer Compare(s, t)：前提假設(s字串 = t字串)回傳0，(若s字串 > t字串)回傳1，否則皆回傳-1。
（三）Boolean IsNull(s)：若s字串為空回傳True，否則回傳False。
（四）Integer Length(s)：回傳字串長度。
（五）String Concat(ｓ, t):前提假設(t = null)則回傳s字串，否則回傳一個字串(元素包含s字串元素及t字串元素)回傳一個字串其元素為t與s，否則回傳s
（六）String Substr(s, i, j)：前提假設((j>0與i+j-1)<length(s))回傳包含s字串的子字串，假設前提不成立則回傳 Null

### Pattern Matching (類型匹配)
#### 暴力法
#### KMP(Knuth, Morris, Pratt pattern matching algorithm)

相較於暴力法差異，搜尋失敗後會利用之前所比較過的紀錄，減少比較的次數，依課本例題做操作討論

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed