---
tags: 資料結構
---
# 資料結構 第四章 鏈結

## 一、特性(characteristic)
### (一)指標
#### 1、指標(pointer):儲存Memory內容的位址(address)
#### 2、一般變數(variable):儲存Memory內容的值(value)

& the address operator 【指出指標所在位址】
* the dereferencing (or indirection) operator【指出指標所指位址中的內容】

#### 3、使用陣列為例：

【假設為32bit Memory entry 4bytes】
(1)A = 1000 【顯示陣列的起始位址】
(2)*A = 10 【顯示陣列的起始位址內的值】
(3)A[0] = 10　【顯示陣列A[0]的值】
(4)&A[0] = 1000 【顯示陣列A[0]的位址】
(5)A[2] = 30 【顯示陣列A[2]的值】
(6)&A[2] = 1008 【顯示陣列A[2]的位址】
(7)*(A+1) = 20 【顯示陣列A[0+1]位址的值】
(8)*A++ = compiler error
【程式試圖改變初始位址（被OS判定為有害程式)】
---

#### 4、使用動態存取

##### 並不需要知道配置的絕對位址，依記憶體常用分配方式(first、best、worst)只需要找到記憶體閒置空間即可配置。
##### 指標有著高度的靈活性及效率，但同時也具備一定的風險(危險)，程式設計者若企圖想讀取特權指令，或是讀取非法位址將對系統造成危害，OS通常也會有保護機制(如下圖)為記憶體(動態存取)的保護機制。
###### (來源：恐龍本 th9 Ch8 main memory)
---

## 二、鏈結串列(linked list)
### (一)Define:為節點(node)所構成之集合，node含有:
#### 1、資料區(data field):用來存放所需資料
#### 2、連結區(link field):即為指標指向下一個Node之所在。
#### 3、圖示:

### (二)性質:
#### 1、Node之間可以不連續配置
#### 2、不同的Node可存放不同的資料型態
### (三)比較

| Link list | Array |
|:-------------------------- | ---------------------------------------- |
| (優)1.可以不連續性配置 | (缺)1.連續性記憶體空間配置 |
| (優)2.Node資料型態可以不同 | (缺)2.資料型態皆要相同 |
| (優)3.插入、刪除較容易 | (缺)3.插入、刪除較不容易 |
| (優)4.串列合併共享較容易 | (缺)4.串列合併共享較不易 |
| (缺)1.多了指標的空間 | (優)1.不需要指標空間(省空間) |
| (缺)2.僅能循序存取 | (優)2.可支援循序存取即隨機存取(速度較快) |
| (結論)彈性較大 | (結論)速度較快 |

### (四)操作
#### 1、插入
##### 【程式碼】
void insert(list_pointer*ptr, list_pointer node)
{
list_pointer temp;
temp = (list_pointer)malloc(sizeof(list_node));
if(is_full(temp))
{
fprintf(stderr,"The memory is full\n");
exit(1);
}
temp→data = 50;
if(*ptr)
{
temp→link = node→link;
node→link = temp;
}
else
{
temp→link = NULL;
*ptr = temp;
}
}

#### 2、刪除
##### 【程式碼】
void delete{list—pointer*ptr, list—pointer trail, list—pointer node)
{
if(trail)
trail→link = node→link;
else
*ptr = (*ptr)→link;
free(node);
}

#### 3、反向鏈結


list_pointer invert(list_pointer lead)
{
list_pointer middle,trail;
middle = NULL ;
while (lead)
{
trail = middle;
middle = lead
lead = lead->link;
middle->link = trail;
}
return middle;
}

#### 4、串聯列表
##### 【程式碼】
list_pointer concatenate(list—pointer ptr1, list—pointer ptr2)
{
list_pointer temp;
if(is_empty(ptr1))
return ptr2;
else
{
if(!is_empty(ptr1))
{
for(temp = ptr1; temp→link; temp = temp→link);
temp→link = ptr2;
}
return ptr1;
}
}
#### 5、計算鏈結長度
##### 【程式碼】
int length(list_pointer ptr)
{
list_pointer temp;
int count = 0;
if (ptr)
{
temp = ptr;
{
count++;
temp = temp→link;
}
　while {temp != ptr);
}
　　return count;
　}

## 三、動態鏈結陣列即佇列
### (一)圖示:
### (二)程式碼:
#### 1.使用鏈結串連陣列【Add to a linked stack】
void add{stack_pointer *top, element item)
{
stack_pointer temp = (stack_pointer)malloc(sizeof(stack));
if(is_full(temp))
{
fprintf(stderr, "the memory is full\n")
exit(1);
}
temp→item = item;
temp→link = *top;
*top = temp;
}
#### 2.使用鏈結刪除陣列串列【Delete from a linked stack】
element delete{stack_pointer　＊top)
{
stack_opinter temp = *top;
element itm;
if(is_empty(temp))
{
fprintf(stderr, "the stack is empty\n");
}
item = temp→item;
*top = temp→link;
free(temp)
return item;
}
#### 3.使用鏈結串連佇列【Add to the rear of a linked queue】
void addq{queue_pointer *front, queue_pointer *rear, element item)
{
queue_pointer temp = (queue_pointer)malloc(sizeof(queue));
if(is_full(temp))
{
fprintf(stderr, "the memory is full\n")
exit(1);
}
temp→item = item;
temp→link = NULL;
if(*front)
(*rear)→link = temp;
else
*front = temp;
*rear = temp;
}
#### 4.使用鏈結刪除佇列串列【Delete from the front of a linked queue】
element delete{queue_pointer　＊front)
{
queue_opinter temp = *front;
element itm;
if(is_empty(*front))
{
fprintf(stderr, "the queue is empty\n");
exit(1);
}
item = temp→item;
*front = temp→link;
free(temp)
return item;
}
## 四、多項式
### (一)介紹
1、定義節點型態

| 係數 | 指數 | 指標link(連結下一個節點位址) |
| -------- | -------- | -------- |

a = 3x^14^+2X^8^+1
b = 8x^14^-3x^10^+10x^6^
表達兩個多項式如下圖:


### (二)多項式加法
A+B=C
step1:比較(A、B)指數欄位是否相同
step2:係數相加
指數相同:新增一個節點值為(將AB兩個多項式係數相加)
指數不同:複製一個一模一樣的節點
step2:將所有結果定義成多項式C

【程式碼】多項式加法(Add two polynomials)

poly＿pointer padd(poly＿pointer a, poly＿pointer b)
{
poly_pointer front, rear, temp;
int sum;
rear = (poly_pointer)malloc(sizeof(poly_nide));
if (is_full(rear))
{
fprintf(stderr, "the memory is full\n");
exit(1);
}
front = rear;
while(a&&b)
switch(compare(a→expon < b→expon))
{
case -1:
attach(b→coef,b→expon, &rear);
b = b→link;
break;
case 0：
sum = a→coef + b→coef;
if(sum) attach(sum,a→expon, &rear);
a = a→link;
}
for(; a; a = a→link) attach(a→coef, a→expon, &rear);
for(; b; b = b→link) attach(b→coef, b→expon, &rear);
rear→link = NULL;
trmp = front;
front = front→link;
free(temp);
return front;
}

void attach(float coefficient, int exponent, poly—pointer *ptr)
{
poly_pointer remp;
temp = (poly_pointer)malloc(sizeof(poly_node));
if (is_full(temp))
{
fprintf(stderr, "The memory is full\n");
exit(1);
}
temp→coef = coefficient;
temp→expon = expont;
(*ptr)→link = temp;
*ptr = temp;
}

### (三)回收(節點)多項式
void erase(poly_pointer *ptr)
{
poly_pointer temp;
while (*ptr)
{
temp = *ptr;
*ptr = (*ptr)→link;
free(temp);
}
}
### (四)多項式使用循環鏈結串接
#### 1、圖示:
#### 2、【程式碼】
##### (1)提供可用的節點
poly_pointer get_node(void)
{
poly_pointer node;
if(avail)
{
node = avail;
avail = avail→link;
}
else
{
node = (poly_pointer)malloc(sizeof(poly_node));
if(is_full(node))
{
fprint(stderr, "the memory is full\n");
exit(1);
}
}
return node;
}

##### (2)回傳節點所在串列
void ret_node(poly_pointer ptr)
{
ptr→link = avail;
avail = ptr;
}

##### (3)回收循環串列
void cerase(poly_pointer *pty)
{
poly_pointer temp;
if(*ptr)
{
temp = (*ptr)→link;
(*ptr)→link = avail;
avail = temp;
*ptr = NULL;
}
}
### 3、循環多項式相加

## (五)等價關係
### 1、定義
(1)需具反身性 a = a
(2)需具對稱性 (a,b)=(b,a)
(3)需具備遞移性 a=b, b=c , a=c
### 2、【程式碼】

void equivalence()
{
initialize seq to NULL and out to TRUE;
while (there are more pairs)
{
read the next pair, <i,j>;
put j on the seq[i] list;
put i on the seq[j] list;
}
for(i=0; i<n; i++)
if(out[1])
{
out[i] = false;
output this equivalence class;
}
}
### 3、圖示

## (六)稀疏矩陣
### 1、定義節點
### 2、圖示舉例:
#### (1)以4x4矩陣為例
#### (2)鏈結矩陣表示
#### (3)【程式碼】

## (七)雙向鏈結
### 1、插入
#### (1)圖示:
#### (2)【程式碼】
Step1：t→Rlink = x→Rlink;
Step2：t→Llink = x;
Step3：(x→Rlink)→Llink = t;
Step4：x→Rlink = t;
//更動4個指標
### 2、刪除
#### (1)圖示:
#### (2)【程式碼】
Step1：(t→Rlink)→Llink = t→Llink;
Step2：(t→Llink)→Rlink = t→Rlink;
Step3：ret(t); //回收節點
//更動2個指標

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