第 4 章　串列

4.1　指標

在前面各章中我們已學習使用陣列和循序映射的簡易資料結構表示法。這些表示法將資料物件的連續元素以一定的距離來儲存。因而：

• 對環狀表示法而言，如果佇列中第 $i$ 個元素位在 $\text{Loc}_i$，則第 $(i+1)$ 個元素將位在 $(\text{Loc}_i + c)\ \%\ \texttt{MAX\_QUEUE\_SIZE}$。
• 如果堆疊的頂端元素位在 $\text{Loc}_{\text{top}}$，其下的元素位在 $\text{Loc}_{\text{top}} - c$。

C 的指標運算符號

在指標上還有其他的運算。因為指標是一個非負的整數，C 允許我們在指標上進行算術運算，如加、減、乘、除。我們也可以判斷一個指標是否大於、小於或等於另一個指標，以及可將指標轉換成整數。

4.1.1　指標可能是危險的

4.1.2　使用動態配置的記憶體

int i, *pi;
float f, *pf;
pi = (int *) malloc(sizeof(int));
pf = (float *) malloc(sizeof(float));
*pi = 1024;
*pf = 3.14;
printf("an integer = %d, a float = %f\n", *pi, *pf);
free(pi);
free(pf);

程式 4.1：指標的配置和釋回

對 malloc 的呼叫包含一個參數，它決定了用以保存一個 int 或 float 所需的記憶體大小。其結果是一個指標，指向適當大小之記憶區間的起始位置。結果的型態可以是不同的。在有些系統中，malloc 的結果是 char* 即指向 char 的指標。但是，對使用 ANSI C 的人而言，將會發現結果是 void*。

pf = (float *) malloc(sizeof(float));

4.2　單向鏈結串列

鏈結串列畫出時如一連串節點，其中箭頭表示指標鏈結。指向串列第一個節點的指標之名稱也是串列的名稱。注意，我們並未明確地寫出指標的值，僅畫出一個箭頭表示它們。這樣做的目的在加強下列的事實：

1. 節點沒有按照循序位置儲存
2. 節點的位置在每次執行程式時可以改變

現在假設我們想要自串列中刪除 mat。我們只要找到在 mat 之前的元素，即 cat，設定其鏈結欄位，使其指向 mat 的鏈結欄位。我們沒有移動任何資料，而且，雖然 mat 的鏈結欄位仍指向 sat，mat 已不再存於串列中。

typedef struct list_node *list_pointer;
typedef struct list_node {
        char data[4];
        list_pointer link;
        };
list_pointer ptr = NULL;

#define IS_EMPTY(ptr) (!(ptr))

ptr = (list_pointer) malloc(sizeof(list_node));

strcpy(ptr->data,"bat");
ptr->link = NULL;

typedef struct list_node *list_pointer;
typedef struct list_node {
        int data;
        list_pointer link;
        };
list_pointer ptr = NULL;

list_pointer create2()
{
/* create a linked list with two nodes */
   list_pointer first, second;
   first = (list_pointer)malloc(sizeof(list_node));
   second = (list_pointer)malloc(sizeof(list_node));
   second->link = NULL;
   second->data = 20;
   first->data = 10;
   first->link = second;
   return first;
}

insert 與 delete

void insert(list_pointer *ptr, list_pointer node)
{
/* insert a new node with data = 50 into the list
ptr after 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;
   }
}

void delete(list_pointer *ptr, list_pointer trail,
                                 list_pointer node)
{
/* delete node from the list, trail is the preceding node
ptr is the head of the list */
   if (trail)
      trail->link = node->link;
   else
      *ptr = (*ptr)->link;
   free(node);
}

void print_list(list_pointer ptr)
{
   printf("The list contains: ");
   for (; ptr; ptr = ptr->link)
      printf("%4d",ptr->data);
   printf("\n");
}

z = NULL; tail = NULL;
while (x && y) {
  if (x->data <= y->data) { t = x; x = x->link; }
  else                    { t = y; y = y->link; }
  if (!z) z = tail = t; else { tail->link = t; tail = t; }
}
tail->link = (x ? x : y);       /* 接上剩下的那一條 */

4.3　動態鏈結的堆疊與佇列

先前我們曾以循序的方式表示堆疊和佇列。這種表示法已證實在僅有一個堆疊或一個佇列時是有效率的。然而，如果有多個堆疊和佇列同時存在，則沒有任何一種方法可以有效率地將它們以循序方式儲存。

n 個堆疊

#define MAX_STACKS 10 /*maximum number of stacks*/
typedef struct {
        int key;
        /* other fields */
        } element;
typedef struct stack *stack_pointer;
typedef struct stack {
        element item;
        stack_pointer link;
        };
stack_pointer top[MAX_STACKS];

啟始狀況：top[i] = NULL，$0 \le i \lt \texttt{MAX\_STACKS}$。邊界條件：top[i] == NULL 若且唯若第 $i$ 個堆疊是空的；IS_FULL(temp) 若且唯若記憶體已滿載。

void add(stack_pointer *top, element item)
{
/* add an element to the top of the stack */
   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;
}

程式 4.6：在鏈結的堆疊中加入元素 —— 典型呼叫 add(&top[stack_no],item)

element delete(stack_pointer *top) {
/* delete an element from the stack */
   stack_pointer temp = *top;
   element item;
   if (IS_EMPTY(temp)) {
      fprintf(stderr, "The stack is empty\n");
      exit(1);
   }
   item = temp->item;
   *top = temp->link;
   free(temp);
   return item;
}

程式 4.7：自鏈結的堆疊中刪除元素

m 個佇列

#define MAX_QUEUES 10 /* maximum number of queues */
typedef struct queue *queue_pointer;
typedef struct queue {
        element item;
        queue_pointer link;
        };
queue_pointer front[MAX_QUEUES], rear[MAX_QUEUES];

void addq(queue_pointer *front, queue_pointer *rear,
                                       element item)
{
/* add an element to the rear of the queue */
   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.8：在鏈結佇列的後端加入元素 —— addq 較 add 複雜，因為它必須檢查空的佇列

element deleteq(queue_pointer *front)
{
/* delete an element from the queue */
   queue_pointer temp = *front;
   element item;
   if (IS_EMPTY(*front)) {
      fprintf(stderr, "The queue is empty\n");
      exit(1);
   }
   item = temp->item;
   *front= temp->link;
   free(temp);
   return item;
}

程式 4.9：自鏈結佇列的前端刪除元素

4.4　多項式

4.4.1　以單向鏈結串列表示多項式

正如在第 2 章討論的，只要記憶體夠用，我們希望表示任何數目的、不同的多項式。一般而言，我們要表示的多項式為：

其中 $a_i$ 為非零的係數，$e_i$ 為非零的整數之指數，且 $e_{m-1} \gt e_{m-2} \gt \cdots \gt e_1 \gt e_0 \ge 0$。

typedef struct poly_node *poly_pointer;
typedef struct poly_node {
        int coef;
        int expon;
        poly_pointer link;
        };
poly_pointer a,b,d;

4.4.2　多項式相加

要將兩個多項式相加，我們從 a 和 b 所指的節點開始檢查它們的項次。三種情況：

poly_pointer padd(poly_pointer a, poly_pointer b)
{
/* return a polynomial which is the sum of a and b */
   poly_pointer front, rear, temp;
   int sum;
   rear = (poly_pointer)malloc(sizeof(poly_node));
   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: /* a->expon < b->expon */
                  attach(b->coef,b->expon,&rear);
                  b = b->link;
                  break;
         case 0: /* a->expon = b->expon */
                  sum = a->coef + b->coef;
                  if (sum) attach(sum,a->expon,&rear);
                  a = a->link;  b = b->link; break;
         case 1: /* a->expon > b->expon */
                  attach(a->coef,a->expon,&rear);
                  a = a->link;
      }
   /* copy rest of list a and then list b */
   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;
   /* delete extra initial node */
   temp = front; front = front->link;  free(temp);
   return front;
}

程式 4.10：兩個多項式相加 ——「這是我們的第一個串列處理的完整範例，你應該仔細地研習」

void attach(float coefficient, int exponent, poly_pointer
                                                  *ptr)
{
/* create a new node with coef = coefficient and expon =
exponent, attach it to the node pointed to by ptr.  ptr is
updated to point to this new node */
   poly_pointer temp;
   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 = exponent;
   (*ptr)->link = temp;
   *ptr = temp;
}

程式 4.11：將一個節點附加在串列的結尾

4.4.3　刪除多項式

一個假想的使用者希望讀取多項式 $a(x)$、$b(x)$ 和 $d(x)$，而後計算 $e(x) = a(x) \cdot b(x) + d(x)$：

poly_pointer a, b, d, e
a = read_poly();
b = read_poly();
d = read_poly();
temp = pmult(a,b);
e = padd(temp,d);
print_poly(e);

「如果我們希望計算更多的多項式，回收用來儲存 temp(x) 的節點是很有幫助的，因 temp(x) 是為保存 d(x) 的部份結果而建立的。」

void erase(poly_pointer *ptr)
{
/* erase the polynomial pointed to by ptr */
   poly_pointer temp;
   while (*ptr) {
      temp = *ptr;
      *ptr = (*ptr)->link;
      free(temp);
   }
}

程式 4.12：刪除一個多項式 —— 逐一將節點釋回，時間 $O(\text{節點數})$

4.4.4　以環狀鏈結串列表示法多項法

avail 可用空間串列

「藉著將釋回的節點視為一個串列（鏈），我們既可達成這個目標，又可獲得一個有效率的環形串列之刪除演算法。當需要一個新的節點時，檢查此串列。如果串列不為空的，則可以使用其中的一個節點。只有在這個串列是空的時，我們才需要利用 malloc 來建立新的節點。」

poly_pointer get_node(void)
/* provide a node for use */
{
   poly_pointer node;
   if (avail) {
      node = avail;
      avail = avail->link;
   }
   else {
      node = (poly_pointer) malloc(sizeof(poly_node));
      if (IS_FULL(node)) {
         fprintf(stderr, "The memory is full\n");
         exit(1);
      }
   }
   return node;
}

程式 4.13：get_node 函數

void ret_node(poly_pointer ptr)
{
/* return a node to the available list */
   ptr->link = avail;
   avail = ptr;
}

程式 4.14：ret_node 函數 —— 注意它就是「推入一個堆疊」

void cerase(poly_pointer *ptr)
{
/* erase the circular list ptr */
   poly_pointer temp;
   if (*ptr) {
      temp = (*ptr)->link;
      (*ptr)->link = avail;
      avail = temp;
      *ptr = NULL;
   }
}

程式 4.15：刪除一個環形串列

標頭節點 head node

poly_pointer cpadd(poly_pointer a, poly_pointer b)
{
/* polynomials a and b are singly linked circular lists
with a head node. Return a polynomial which is the sum
of a and b */
   poly_pointer starta, d, lastd;
   int sum, done = FALSE;
   starta = a;              /* record start of a */
   a = a->link;             /* skip head node for a and b*/
   b = b->link;
   d = get_node();          /* get a head node for sum */
   d->expon = -1; lastd = d;
   do {
      switch (COMPARE(a->expon, b->expon)) {
         case -1: /* a->expon < b->expon */
               attach(b->coef,b->expon,&lastd);
               b = b->link;
               break;
         case 0:  /* a->expon = b->expon */
               if (starta == a)  done = TRUE;
               else {
                  sum = a->coef + b->coef;
                  if (sum) attach(sum,a->expon,&lastd);
                  a = a->link; b = b->link;
               }
               break;
         case 1:  /* a->expon > b->expon */
               attach(a->coef,a->expon,&lastd);
               a = a->link;
      }
   } while (!done);
   lastd->link = d;
   return d;
}

4.5　更多的串列運算

4.5.1　有關鏈的運算

typedef struct list_node *list_pointer;
typedef struct list_node {
        char data;
        list_pointer link;
        };

list_pointer invert(list_pointer lead)
{
/* invert the list pointed to by lead */
   list_pointer middle,trail;
   middle = NULL;
   while (lead) {
      trail = middle;
      middle = lead;
      lead = lead->link;
      middle->link = trail;
   }
   return middle;
}

程式 4.17：將單向鏈結串列反向

list_pointer concatenate(list_pointer ptr1,
                                  list_pointer ptr2)
{
/* produce a new list that contains the list ptr1 followed
by the list ptr2. The list pointed to by ptr1 is changed
permanently */
   list_pointer temp;
   if (IS_EMPTY(ptr1)) return ptr2;
   else {
      if (!IS_EMPTY(ptr2)) {
         for (temp = ptr1; temp->link; temp = temp->link)
            ;
         temp->link = ptr2;
      }
      return ptr1;
   }
}

程式 4.18：合併單向鏈結串列 —— 複雜度 $O(\text{ptr1 的長度})$

4.5.2　有關環狀鏈結串列的運算

void insert_front(list_pointer *ptr, list_pointer node)
/* insert node at the front of the circular list ptr,
where ptr is the last node in the list */
{
   if (IS_EMPTY(*ptr)) {
   /* list is empty, change ptr to point to new entry */
      *ptr = node;
      node->link = node;
   }
   else {
   /* list is not empty, add new entry at front */
      node->link = (*ptr)->link;
      (*ptr)->link = node;
   }
}

程式 4.19：在串列之前插入節點

int length(list_pointer ptr)
{
/* find the length of the circular list ptr */
   list_pointer temp;
   int count = 0;
   if (ptr) {
      temp = ptr;
      do {
         count++;
         temp = temp->link;
      } while (temp != ptr);
   }
   return count;
}

程式 4.20：找出一個環形串列的長度 —— 注意用 do...while 而非 while，因為起點本身也要數進去

list_pointer cconcat(list_pointer p1, list_pointer p2)
{
   list_pointer temp;
   if (!p1) return p2;
   if (!p2) return p1;
   temp = p1->link;        /* p1 的第一個節點 */
   p1->link = p2->link;    /* p1 的尾接到 p2 的頭 */
   p2->link = temp;        /* p2 的尾接回 p1 的頭 */
   return p2;              /* p2 現在是新環的最後一個節點 */
}

4.6　等價關係

讓我們將一些鏈結和循序表示法的觀念結合在一起，以便解決在設計和製造超大型積體電路（VLSI）時會遭遇的問題。在製造 VLSI 線路的過程中的一個步驟是將矽晶的簿層以一系列的罩遮來曝光。每一個罩遮由數個多邊形構成。電氣重疊的多邊形是等價的（equivalent），而電氣等價表示罩遮多邊形之間的一種關係。

兩階段演算法

void equivalence()
{
   initialize;
   while (there are more pairs) {
      read the next pair <i,j>;
      process this pair;
   }
   initialize the output;
   do
      output a new equivalence class;
   while (not done);
}

程式 4.21：等價演算法第一階段

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[i]) {
         out[i] = FALSE;
         output this equivalence class;
      }
}

程式 4.22：等價演算法更詳細的版本 —— 注意每一個序對 放進兩個串列（對稱性）

#include <stdio.h>
#include <alloc.h>
#define MAX_SIZE 24
#define IS_FULL(ptr) (!(ptr))
#define FALSE 0
#define TRUE 1

typedef struct node *node_pointer;
typedef struct node {
        int data;
        node_pointer link;
        };
void main(void)
{
   short int out[MAX_SIZE];
   node_pointer seq[MAX_SIZE];
   node_pointer x,y,top;
   int i,j,n;

   printf("Enter the size (<= %d) ",MAX_SIZE);
   scanf("%d",&n);
   for (i = 0; i < n; i++) {
   /* initialize seq and out */
      out[i] = TRUE;   seq[i] = NULL;
   }

   /* Phase 1: Input the equivalence pairs: */
   printf("Enter a pair of numbers (-1 -1 to quit): ");
   scanf("%d%d",&i,&j);
   while (i >= 0) {
      x = (node_pointer)malloc(sizeof(node));
      if (IS_FULL(x)) {
         fprintf(stderr,"The memory is full\n");
         exit(1);
      }
      x->data = j;   x->link = seq[i];   seq[i] = x;
      x = (node_pointer)malloc(sizeof(node));
      if (IS_FULL(x)) {
         fprintf(stderr, "The memory is full\n");
         exit(1);
      }
      x->data = i;   x->link = seq[j];   seq[j] = x;
      printf("Enter a pair of numbers (-1 -1 to quit): ");
      scanf("%d%d",&i,&j);
   }

   /* Phase 2: output the equivalence classes */
   for (i = 0; i < n; i++)
      if (out[i]) {
         printf("\nNew class: %5d",i);
         out[i] = FALSE;   /* set class to false */
         x = seq[i];  top = NULL; /* initialize stack */
         for (;;) {        /* find rest of class */
            while (x) {   /* process list */
               j = x->data;
               if (out[j]) {
                  printf("%5d",j);   out[j] = FALSE;
                  y = x->link; x->link = top; top = x; x = y;
               }
               else x = x->link;
            }
            if (!top) break;
            x = seq[top->data]; top = top->link; /*unstack*/
         }
      }
}

程式 4.23：用來找出等價類的程式

4.7　稀疏矩陣

在第 2 章，我們看到只要儲存稀疏矩陣中不為零的元素，即可節省空間和計算時間。然而，我們發現當執行加，減，乘等矩陣運算時，非零項個數會改變。就像多項式的情況一樣，稀疏矩陣表示法局部的運算會先建立，而後加以清除以便提供空間給其他的矩陣使用。所以，稀疏矩陣的循序表示法和多項式的循序表示法受困於相同的缺點。

#define MAX_SIZE 50 /*size of largest matrix*/
typedef enum {head,entry} tagfield;
typedef struct matrix_node *matrix_pointer;
typedef struct entry_node {
        int row;
        int col;
        int value;
        };
typedef struct matrix_node {
        matrix_pointer down;
        matrix_pointer right;
        tagfield tag;
        union {
            matrix_pointer next;
            entry_node entry;
            } u;
        };
matrix_pointer hdnode[MAX_SIZE];

「因為我們的表示法中有兩種不同的節點形式，我們使用 union 來建立適當的資料結構。也就是說，這個資料結構比以前曾建立的任一種資料結構複雜。」—— 這是第 2 章 2.2.2 節 union 的第一個真正重要的應用。

三個運算及其分析

matrix_pointer new_node(void)
{
   matrix_pointer temp;
   temp = (matrix_pointer) malloc(sizeof(matrix_node));
   if (IS_FULL(temp)) {
      fprintf(stderr, "The memory is full\n");
      exit(1);
   }
   return temp;
}

程式 4.25：取得一個新的矩陣節點

void merase(matrix_pointer *node)
{
/* erase the matrix, return the nodes to the heap */
   matrix_pointer x,y, head = (*node)->right;
   int i, num_heads;
   /* free the entry and head nodes by row */
   for (i = 0; i < (*node)->u.entry.row; i++) {
      y = head->right;
      while (y != head) {
         x = y; y = y->right; free(x);
      }
      x = head; head = head->u.next; free(x);
   }
   /* free remaining head nodes*/
   y = head;
   while (y != *node) {
      x = y; y = y->u.next; free(x);
   }
   free(*node);  *node = NULL;
}

程式 4.27：清除一個稀疏矩陣

4.8　雙向鏈結串列

typedef struct node *node_pointer;
typedef struct node {
        node_pointer llink;
        element item;
        node_pointer rlink;
        };

dinsert 與 ddelete

void dinsert(node_pointer node, node_pointer newnode)
{
/* insert newnode to the right of node */
   newnode->llink = node;
   newnode->rlink = node->rlink;
   node->rlink->llink = newnode;
   node->rlink = newnode;
}

程式 4.28：插入節點到雙向鏈結環狀串列 —— 四行，常數時間，不需要區分空／非空

void ddelete(node_pointer node, node_pointer deleted)
{
/* delete from the doubly linked list */
   if (node == deleted)
      printf("Deletion of head node not permitted.\n");
   else {
      deleted->llink->rlink = deleted->rlink;
      deleted->rlink->llink = deleted->llink;
      free(deleted);
   }
}

程式 4.29：從一個雙向鏈結環形串列刪除節點

newnode->llink = node;           /* 1. 新節點向左指 */
newnode->rlink = node->rlink;    /* 2. 新節點向右指（此時 node->rlink 還沒被改） */
node->rlink->llink = newnode;    /* 3. 右鄰居向左指回新節點 */
node->rlink = newnode;           /* 4. 最後才改 node 向右 */

4.9　精選參考文獻

4.10　綜合習題

本章重點回顧