# 資結 ch2&ch4
[TOC]

### Array 元素儲存位址計算

#### 一維陣列
(1)宣告方式:A[1...n] of items
(2)A[i] = l~0~ + (i - 1)*d

#### 二維陣列
(1)宣告方式:A[1...m 1...n] of items
有m列(Row),有n行(column)

(2)分row-major&column-major

(3)一般化宣告方式
A:[l~1~....u~1~,l~2~...u~2~] of items
有u~1~-l~1~+1列,有u~2~-l~2~+1行

[1]Row-major公式
A[i,j] = l~0~ + [<font color="red">(i - l~1~)* (u~2~ - l~2~ + 1)</font> + <font color="purple">(j - l~2~)</font>] * d

[2]Column-major公式
A[i,j] = l~0~ + [<font color="red">(j - l~2~)* (u~1~ - l~1~ + 1)</font> + <font color="purple">(i - l~1~)</font>] * d

<font color="green">note:有時類似c之宣告A[m][n]:m列n行 從0開始index即[0....m-1,0...n-1]</font>

#### 四大題型
[型一]給予所有必要info,求A[i,j]之location
ex:給l~0~ ,d ,A[1..n,1..m]

[型二]給予兩個元素之loc,求其他資訊
<font color="red">關鍵:自己判斷出Row-ajor或column-major</font>
ex:給A[3,2] = 1110,A[2,3] = 1115
因1115>1110且3>2故我們知道是column-major

[型三]給予兩元素位址
但是判斷Row及column-major皆有可能
所以兩者皆必須算
ex:給A[3,3] = 121 , A[6,4] = 159
無法判斷是甚麼major

[型四]給予三元素位址,求所有未知數
判斷Row及column-major

#### 三維以上陣列
(1)凡是大於等於2維陣列,元素儲存方式分兩種
row-major或col-major

(2)
row-major:由左而右看待→
col-major:由右而左看待←

(3)表示法
A[1..u~1~,1...u~2~,1...u~3~] of items

[1]row-major
A[i ,j ,k]=l~0~+[<font color="red">(i - 1)* u~2~ * u~3~ </font>+ <font color="purple">(j - 1)* u~3~</font> + (k - 1)]

[2]col-major
A[i ,j ,k]=l~0~+[<font color="red">(k - 1)* u~2~ * u~1~ </font>+ <font color="purple">(j - 1) * u~1~ </font> + (i - 1)]

### 特殊矩陣之儲存

#### 下三角矩陣
(1)
def:A是n * n矩陣,對角線(不含)右上方均為0元素,其餘為元素
即A[i , j] = 0, if(i < j)

(2)元素個數=1+2+....n = $\dfrac{n(n+1)}{2}$個

(3)存放方式分col&row
row-major
A[i,j] = (1+2+....(i-1)) + j = $\dfrac{i(i-1)}{2}$ + j

col-major
=>先填滿再來扣
A[i,j] = (j - 1) * n - (0+1+2+..(j-2)) + (i-(j-1))
= n * (j - 1) - $\dfrac{j(j-1)}{2}$ + i

#### 上三角矩陣
(3)存放方式分col&row
全部都跟下三角i,j互換即可

row-major
A[i,j] = $\dfrac{j(j-1)}{2}$ + i

col-major
A[i,j] = n(i - 1) + $\dfrac{i(i-1)}{2}$ + j

#### symmetric(對稱) matrix
(1)
def:A是n * n矩陣且A[i,j] = A[j,i]
即下三角元素 = 上三角元素
故有效儲存方式<font color="red">只要存放下(上)三角元素空間即可,即$\dfrac{n(n+1)}{2}大小$</font>

#### Band matrix(帶狀,寬帶矩陣)
(一)
def:An,a,b是bandMatrix代表A是n * n矩陣且
[1]對角線(含)左下<font color="red">a條斜線</font>為元素
[2]對角線(含)右上<font color="red">b條斜線</font>為元素
[3]其餘為0元素

(二)An,a,b之元素個數
[1]a部分元素個數
n + (n-1) + (n-2) +... (n-a+1) = $\dfrac{a(2n-a+1)}{2}$
[2]b部分元素個數
n + (n-1) + (n-2) +... (n-b+1) = $\dfrac{b(2n-b+1)}{2}$
故元素個數= $\dfrac{a(2n-a+1)}{2}$ + $\dfrac{b(2n-b+1)}{2}$ - n(中間那條多算一次)

### link list種類與操作

#### single link list
(一)定義
def:linking方向只有一個

(二)運作
例:計算串列長度(node個數)

Len(s:single link list)
{
    c=0;
    p=s;
    while(p ≠ Nil) do:
    {
        c++;
        p = p -> link;
    }
    return c;
}

Time:O(n)

例2:回收整條single link list:s

Release(s:single link list)
{
    if(s≠Nil) then
    {
        p =s;
        while(p->link ≠ Nil) do
            p = p -> link;  //到串列最尾巴
        p -> link = AV;     //將最尾巴的link next指向av
        AV = S;             //av頭在指向s
    }
}

Time:O(n)

<font color="red">例3:反轉整個link list</font>

Invert(S:single link list)
{
    q = Nil;
    p = s;             //p只是一個探路人
    while (p ≠ Nil) do
    {
        r = q;
        q = p;
        p = p -> link;
        q ->link = r;  //主要是q跟r再link
    }
    s = q;             //因主要是連線的是q的link list
}
while迴圈Time:O(n)

#### Circular link list
(一)定義:
Def:single link list中最後一個Node的pointer(link)指回第一個Node稱之

(二)特性:
(1)不論從哪個node開始,皆可經過所有nodes
(2)回收整條串列之Time為O(1)
(3)連結(concatenate)兩條環狀link list成一條只需要Time:O(1)
<font color="gree"><note>single link list:O(n)</font>

(三)例題
[例題一]回收整條circular link list

Release)(C:Circular link list)
{
    if(C ≠ Nil)then
    {
        p = C -> link;
        p -> link = AV;
        AV = p;
    }

}

[例題二]連結兩條circular link list

Concatenate(A,B,C:Circular link list)
{
    C = Nil;
    if(A ≠ Nil and B == Nil)then C = A;
    else if(A == Nil and B ≠ Nil) then C = B;
    else if(A ≠ Nil and B ≠ Nil) then
    {
        P = A -> link;         #紀錄
        A -> link = B -> link; #A指過去
        B -> link = P;         #B指回來
        C = P;                 #C直接收割頭
    }
    return C;
}

Time:O(1)

[例題三]求串列長度

Len(C:circular link list)
{
    if(C == Nil) then return 0;
    else{
            s = 0;
            p = c;
            repeat 
                s++;
                p = p -> link;
            until(p == c)
            return s;
        }
}

#### Double link list
(一)定義
def:linking具有兩個方向
node structure為:
|Llink|Data|Rlink|
|---|---|---|

Llink,Rlink = pointer分指向前(左)及後(右)一個node
此外,一般使用上會再額外多加一個head node(不存data)

(二)insert and delete node動作
insert

(1)t -> RLink = x -> RLink;
(2)t->Link = x;
(3)x -> RLink ->Llink = t;
(4)x -> RLink = t;

<font color="gree"><note>single link list insert node 只須改兩個pointer</font>
delete x node

(1) x ->LLink ->RLink = x -> RLink;
(2) x ->RLink ->LLink = x -> LLink;
(3) free(x);

#### link list比較表
|single |double|
|----|----|
|linking只有一個方向|2個方向|
|僅能夠知道後一個node所在|可知道前後|
|必須從頭開始才能拜訪所有node|從任何node開始皆可拜訪所有Node|
|可靠度差|佳|
|Insert及delete node方便/容易(分別1個及2個)|困難/麻煩(須改4個及2個)|
|linking space較省|耗費較多|

#### array與link list比較表
|Array |link list|
|----|----|
|占用連續的memory space|各node不一定佔連續之space可以非連續|
|各元素之型態皆須相同|各Node之type不一定要相同
|array支持random access及sequential access|只支援sequential access不支援random access|
|循序存取速度較快|慢(要先read link info)|
|可靠度佳|差(可能斷掉)|
|array使用前,大小需事先宣告,無法動態增加|可以動態增加,刪node space|
|insert 及 delete元素麻煩,因須挪動其他元素,Time:O(n)|容易(因改變pointer即可),time:O(1)|
### Generalize list(一般化串列)
#### (一)定義:
def:令A=(a~1~,a~2~....a~n~)是一generalize list,其中a~i~,1<=i<=n是A的元素且a~i~可分成兩種types:
(1)atomic data
(2)sublist,sublist 也是一個generalize list

#### (二)相關術語
(1) |A|:A的長度,即A的元素個數
(2) Head of A
=>串列之第一個元素
(3) Tail of A
=>除了Head以外的元素集合

#### (三)data structure design
|tag|變動欄位 |link|
|----|----|----|

當tag =
(1)True:dllink欄位:pointer指向sublist元素
(2)False:data欄位:存atomic data元素

#### (四)三個基本操作
(1)copy一條generalize list

Copy(orig:G.list)
{
    if(orig == Nil) then t = Nil;
    else
    {
        new(t);
        t -> Tag = orig -> Tag;
        if(orig -> Tag == False) then
            t -> data = orig -> data;
        else
            t -> dlink = Copy(orig -> dlink);
        t -> link = Copy(orig -> link);
    }
    return t;
}

(2)

Equal(S,T:G.list)
{
    res = False;
    if(S == Nil and T == Nil)then res = True;
    else if(S ≠ Nil and T ≠ Nil)then
        if(S -> Tag == T -> Tag)then
            {
                if(S -> Tag == False)then
                    if(S -> Data == T -> Data)then Head = True;
                    else Head=False;
                else
                    Head = Equal(S -> dlink,T -> dlink);
                if(Head == True)then res = Equal(s -> link,T -> link);
            }
    return res;        
}                

(3)求G.list之深度(depth)
depth =
0,if s 為 nil
1 + MAX{depth(a~i~)|a~i~是s中的sublist元素}

Depth(S:G.list)
{
    if(S == Nil)then return 0;
    else
    {
        p = s;
        MAX = 0;
        while(p ≠ Nil)do
        {
            if(p -> Tag == True)then
            {
                n = Depth(p -> dlink);
                if(n > MAX) then MAX = n;
            }
            p = p -> link;
        }
    return (MAX + 1);
    }
}

### 多項式之表示方法
分別用array,list
#### array有分兩種
##### 一種對很少0的比較有利(每一項的係數都存)
##### 一種對很多0的比較有利(只存不是0的係數)

#### list只有一種
##### 利用前面的generalize list來做
|tripple|變動欄位 |exp|link|
|----|----|----|-----|

變動欄位:
(1)var 存變數名稱 不存值
(2)ptr dlink攔 pointer to sublist
(3)No coefficient攔 存簡單的係數值(int)

### sparse matrix之表示方法
#### array有兩種方法
##### (1)用一個陣列儲存
##### (2)用一個圖表儲存值每一列儲存三個元素row,col,value
#### double link list有一種方法
##### 分成head node(串列首)及element node(元素node)
###### tags: `data structure` `chp2` `chp4` `list` `array`