資料結構（線性串列）

參考網站

演算法筆記

演算法動畫

Swift 演算法

線性串列抽象資料型別

線性串列是一種資料結構

包含順序儲存(陣列)或是鏈結串列都屬於線性串列

以下是線性串列的基本操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
線性串列 (LinearList)

Data
線性串列資料物件集合 = {a1,a2,a3...an}
每個元素型態皆相同

Operation
  InitList(*L)       : 初始化、建立空的線性表
  ListEmpty(L)       : 檢查 L 是否為空
  ClearList          : 清空 List 
  GetElem(L,i,*e)    : 取得 L 中第 i 個傳給 e
  LocateElem(L,e)    : 搜尋 L 中和 e 相同的元素位置
  ListInsert(*L,i,e) : 在 i 位置插入 e
  ListDelete(*L,i,*e): 刪除第 i 位置的元素
  ListLength(L)      : 傳回 L 元素個數

單向鏈結串列 (LinkedList)

一開始鏈結串列為空，所以首節點的下一個指標為NULL

可以把NULL簡寫為^

1
2
3
+----------+
|   | NULL |
+----------+

首先就要定義一個Node的資料型態

一個Node需要存資料和指標

所以定義如下

1
2
3
4
5
6
7
typedef int ElemType;
typedef struct Node* LinkList;
typedef struct Node
{
    ElemType    data;
    struct Node *nextPtr;
}Node;

以下是 Swift 建立一個 Node

<T>為泛型語法，會在真正建立時才會決定型態

而類型初始化時要保證所有屬性都初始化

所以會在加上 init 函式，next 為可選所以不用初始化(預設為 Null)

1
2
3
4
5
6
7
public class Node<T> {
  var data: T
  var next: Node?
  public init(data: T) {
    self.data = data
  }
}

原始碼

原始碼範例

PPT 解說