第 2 章　陣列與結構

2.1　陣列視同一種抽象資料型態

直觀上而言，陣列是一組序對 $\langle \textit{index}, \textit{value}\rangle$，其中每一個索引（index）定義了一個與其關連的值（value）。在數學上而言，我們稱此為對應或映射。然而，當我們視其為一種 ADT 時，我們更關心的是可以在一個陣列上執行的運算。

除了建立一個新的陣列以外，多數的程式語言只為陣列提供兩種標準運算：一個是擷取（retrieve）一個值，另一個是儲存（store）一個值。

structure Array is
  objects: A set of pairs <index, value> where for each value of index
    there is a value from the set item. Index is a finite ordered set of
    one or more dimensions, for example, {0, ... , n-1} for one dimension,
    {(0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2)} for
    two dimensions, etc.
  functions:
    for all A in Array, i in index, x in item, j, size in integer

    Array Create(j, list)  ::=  return an array of j dimensions where list
                                is a j-tuple whose ith element is the size
                                of the ith dimension. Items are undefined.
    Item  Retrieve(A, i)   ::=  if (i in index) return the item associated
                                with index value i in array A
                                else return error
    Array Store(A, i, x)   ::=  if (i in index)
                                return an array that is identical to array
                                A except the new pair <i, x> has been
                                inserted else return error.

end Array

結構 2.1：抽象資料型態 Array

基底位址與定址

在 C 語言中的一個一維陣列以變數名稱後面加上中括號來定義，例如：

int list[5], *plist[5];

宣告了兩個陣列，各包含了五個元素。第一個陣列定義了五個整數，而第二個陣列定義了五個指向整數的指標（pointer）。在 C 中，所有的陣列索引自 0 開始。

當編譯程式遇到了一個陣列宣告，它會配置五個連續的記憶位置。第一個元素 list[0] 的位址稱為基底位址（base address）。如果一個整數的大小在你的機器上可用 sizeof(int) 表示，可得到 list[] 的五個元素之記憶位址如下：

int *list1;      /* 只是一個指標，沒有預留空間  */
int list2[5];    /* 預留了五個記憶位置          */

#define MAX_SIZE 100
float sum(float [], int);
float input[MAX_SIZE], answer;
int i;
void main(void)
{
   for (i = 0; i < MAX_SIZE; i++)
     input[i] = i;
   answer = sum(input, MAX_SIZE);
   printf("The sum is: %f\n", answer);
}
float sum(float list[], int n)
{
   int i;
   float tempsum = 0;
   for (i = 0; i < n; i++)
     tempsum += list[i];
   return tempsum;
}

int one[] = {0, 1, 2, 3, 4};

void print1(int *ptr, int rows)
{
/* print out a one-dimensional array using a pointer */
   int i;
   printf("Address Contents\n");
   for (i = 0; i < rows; i++)
     printf("%8u%5d\n", ptr + i, *(ptr + i));
   printf("\n");
}

2.2　結構和聯結

2.2.1　結構 (structure)

陣列是相同型態的資料之集合。在 C 語言中，有不同的方法可以將不同型態的資料群集在一起 —— 此種方法稱為 struct，為結構（structure）的縮寫。一個結構（在許多其他的語言中稱為記錄，record）是資料項的集合，每個資料項分別以其名稱和型態定義。

struct {
        char name[10];
        int age;
        float salary;
        } person;

產生一個命名為 person 的變數，它有三個欄位：姓名（字元陣列）、年齡（整數）、薪水（float）。

我們可用如下方式指定這些欄位值。注意，點號 . 當成結構成份運算符號：

strcpy(person.name,"james");
person.age = 10;
person.salary = 35000;

我們也可以使用 typedef 指令來建立自設的結構資料型態：

typedef struct human_being {          typedef struct {
        char name[10];                        char name[10];
        int age;              或              int age;
        float salary;                        float salary;
        };                                   } human_being;

在此 human_being 是型態名稱，可以在此定義之後以它來宣告變數：human_being person1, person2;

strcpy(person1.name, person2.name);
person1.age = person2.age;
person1.salary = person2.salary;

雖然結構不能直接檢查相等或不相等，我們可以編寫函數來做這件事。假設 TRUE 和 FALSE 定義為 #define FALSE 0 與 #define TRUE 1：

int humans_equal(human_being person1,
                          human_being person2)
{
/* return TRUE if person1 and person2 are the same human
being otherwise return FALSE */
   if (strcmp(person1.name, person2.name))
     return FALSE;
   if (person1.age != person2.age)
     return FALSE;
   if (person1.salary != person2.salary)
     return FALSE;
   return TRUE;
}

程式 2.3：檢查結構是否相等的函數

巢狀結構

我們也可以將一個結構內含在另一個結構之內。例如以前述的 human_being 結構而言，我們也許會想在其中包含個人的出生日期：

typedef struct {
        int month;
        int day;
        int year;
        } date;

typedef struct human_being {
        char name[10];
        int age;
        float salary;
        date dob;
        };

一個在 1944 年 2 月 11 日出生的人，其 date struct 之值可以設定為：

person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

2.2.2　聯結 (union)

繼續以 human_being 為例，如果可以辨別男性和女性將是很美好的事。如果是男性，我們也許想知道他是否有留鬍子；如果是女性，我們也許想知道她有幾個小孩。這型成 C 的另一種特色，稱為 union。

typedef struct sex_type {
  enum tag_field {female, male} sex;
  union {
     int children;
     int beard;
     } u;
  };
typedef struct human_being {
        char name[10];
        int age;
        float salary;
        date dob;
        sex_type sex_info;
        };
human_being person1, person2;

我們可以指定欄位值給 person1 和 person2，如：

person1.sex_info.sex = male;
person1.sex_info.u.beard = FALSE;

person2.sex_info.sex = female;
person2.sex_info.u.children = 4;

2.2.3　結構的內部實作

多數情況下，我們不需要關心 C 編譯程式如何將結構中的欄位確實地存入記憶體中。一般而言，如果結構定義如下：

struct {int i,j; float a, b;};
或
struct {int i; int j; float a; float b; };

各欄位值將根據欄位在結構定義中的先後順序，以位址漸增的方式儲存在記憶體中。

2.2.4　自我參考結構

typedef struct list {
        char data;
        list *link ;
        } ;

結構 list 的每一個實體有兩個成份，data 和 link。data 為單一字元，而 link 為指向 list 結構的指標。link 之值或者是 list 的一個實體在記憶體中的位址，或者是虛指標（null pointer）。

list item1, item2, item3;
item1.data = 'a';
item2.data = 'b';
item3.data = 'c';
item1.link = item2.link = item3.link = NULL;

結構 item1、item2、item3 分別包含資料項 a、b 和 c，以及虛指標。藉著將 item2 中的虛指標欄位 link 以指向 item3 的指標取代之，將 item1 中的虛指標欄位 link 以指向 item2 的指標取代之，我們可將此三個結構連接在一起：

item1.link = &item2;
item2.link = &item3;

有關這種鏈結將在第 4 章詳細說明。

typedef struct {
  enum marital_tag {single, married, widowed, divorced} status;
  union {
    date  marriage_date;             /* married  */
    struct { date marriage, death; } w;   /* widowed  */
    struct { date divorce; int times; } d; /* divorced */
  } u;                                /* single 不需欄位 */
} marital_type;

2.3　多項式抽象資料型態

陣列不僅只是陣列資料結構而已，我們也可利用它來製作其他的抽象資料型態。例如，一種簡單而常見的資料結構：有序串列（ordered list）或線性串列（linear list）。我們可以找到此種資料結構的許多實例：

• 每週之星期：(Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday)
• 一疊紙牌之點數：(Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King)
• 建築物之樓層：(basement, lobby, mezzanine, first, second)
• 在二次世界大戰中美國參戰的年份：(1941, 1942, 1943, 1944, 1945)
• 在二次世界大戰中瑞士參戰的年份：( )

應留意瑞士的年份有些不同，因為它不包含任何項目。它是空串列的例子，空串列以 () 表示。其他的串列都有資料項，以 $(\textit{item}_0, \textit{item}_1, \ldots, \textit{item}_{n-1})$ 的格式寫出。

在串列上可以執行許多的運算，包括：找出串列的長度 $n$；由左而右（或由右而左）讀取串列中的項目；擷取／替換第 $i$ 個項目（$0 \le i \lt n$）；在第 $i$ 個位置插入一個新項目（原編號 $i, i+1, \ldots, n-1$ 變成 $i+1, i+2, \ldots, n$）；自第 $i$ 個位置刪除一個項目（原編號 $i+1, \ldots, n-1$ 變成 $i, \ldots, n-2$）。

多項式：一個需要有序串列的問題

從數學觀點來看，多項式為各項的加總，各項的格式為 $ax^e$，其中 $x$ 為變數，$a$ 為係數，而 $e$ 為指數。下面是兩個多項式的例子：

多項式最大的（或第一個）指數稱為次方（degree）。等於 0 的係數不必寫出；指數為 0 的項目不必寫出變數，因為 $x$ 的 0 次方為 1。假設有兩個多項式 $A(x)=\sum a_ix^i$ 和 $B(x)=\sum b_ix^i$，則：

結構 2.2　抽象資料型態 Polynomial

structure Polynomial is
  objects: p(x) = a1*x^e1 + ... + an*x^en; a set of ordered pairs of
    <ei, ai> where ai in Coefficients and ei in Exponents, ei are
    integers >= 0
  functions:
    for all poly, poly1, poly2 in Polynomial, coef in Coefficients,
    expon in Exponents

    Polynomial   Zero()                  ::= return the polynomial, p(x) = 0
    Boolean      IsZero(poly)            ::= if (poly) return FALSE
                                             else return TRUE
    Coefficient  Coef(poly, expon)       ::= if (expon in poly) return its
                                             coefficient else return zero
    Exponent     Lead_Exp(poly)          ::= return the largest exponent in poly
    Polynomial   Attach(poly,coef,expon) ::= if (expon in poly) return error
                                             else return the polynomial poly
                                             with the term <coef, expon> inserted
    Polynomial   Remove(poly, expon)     ::= if (expon in poly)
                                             return the polynomial poly with
                                             the term whose exponent is expon
                                             deleted else return error
    Polynomial   SingleMult(poly,coef,expon) ::= return the polynomial
                                             poly * coef * x^expon
    Polynomial   Add(poly1, poly2)       ::= return the polynomial poly1 + poly2
    Polynomial   Mult(poly1, poly2)      ::= return the polynomial poly1 * poly2

end Polynomial

結構 2.2：抽象資料型態 polynomial

/* d = a + b, where a, b, and d are polynomials */
d = Zero()
while (! IsZero(a) && ! IsZero(b)) do {
  switch COMPARE(Lead_Exp(a), Lead_Exp(b)) {
    case -1: d =
       Attach(d, Coef(b,Lead_Exp(b)), Lead_Exp(b));
       b = Remove(b, Lead_Exp(b));
       break;
    case  0: sum = Coef(a, Lead_Exp(a)) + Coef(b, Lead_Exp(b));
       if (sum) {
          Attach(d, sum, Lead_Exp(a));
          a = Remove(a, Lead_Exp(a));
          b = Remove(b, Lead_Exp(b));
          }
       break;
    case 1: d =
       Attach(d, Coef(a,Lead_Exp(a)), Lead_Exp(a));
       a = Remove(a, Lead_Exp(a));
  }
}
insert any remaining terms of a or b into d

程式 2.4：padd 函數的第一個版本

兩種表示法的取捨

#define MAX_DEGREE 101
typedef struct {
        int degree;
        float coef[MAX_DEGREE];
        } polynomial;

MAX_TERMS 100 /*size of terms array*/
typedef struct {
        float coef;
        int expon;
        } polynomial;
polynomial terms[MAX_TERMS];
int avail = 0;

圖 2.2：兩個多項式的陣列表示法 —— $A(x)=2x^{1000}+1$、$B(x)=x^4+10x^3+3x^2+1$。此例中 starta=0、finisha=1、startb=2、finishb=5、avail=6。

padd 及其分析

void padd(int starta,int finisha,int startb, int finishb,
                             int *startd,int *finishd)
{
/* add A(x) and B(x) to obtain D(x) */
   float coefficient;
   *startd = avail;
   while (starta <= finisha && startb <= finishb)
     switch(COMPARE(terms[starta].expon,
                    terms[startb].expon)) {
       case -1: /* a expon < b expon */
                attach(terms[startb].coef,terms[startb].expon);
                startb++;
                break;
       case 0: /* equal exponents */
                coefficient = terms[starta].coef +
                              terms[startb].coef;
                if (coefficient)
                   attach(coefficient,terms[starta].expon);
                starta++;
                startb++;
                break;
       case 1: /* a expon > b expon */
                attach(terms[starta].coef,terms[starta].expon);
                starta++;
   }
   /* add in remaining terms of A(x) */
   for(; starta <= finisha; starta++)
     attach(terms[starta].coef,terms[starta].expon);
   /* add in remaining terms of B(x) */
   for( ; startb <= finishb; startb++)
     attach(terms[startb].coef, terms[startb].expon);
   *finishd = avail-1;
}

程式 2.5：將兩個多項式相加的函數

void attach(float coefficient, int exponent)
{
/* add a new term to the polynomial */
   if (avail >= MAX_TERMS) {
     fprintf(stderr,"Too many terms in the polynomial\n");
     exit(1);
   }
   terms[avail].coef = coefficient;
   terms[avail++].expon = exponent;
}

程式 2.6：加入新項次的函數

2.4　稀疏矩陣抽象資料型態

2.4.1　簡介

在數學上，一個矩陣包含 $m$ 列和 $n$ 行的元素。通常寫為 $m \times n$（讀作 "m by n"）。在這樣的矩陣中，所有的元素個數為 $mn$。如果 $m$ 等於 $n$，矩陣為一個方陣。

計算機科學上，一個矩陣的標準表示法為二維陣列，如定義 a[MAX_ROWS][MAX_COLS]。以這種表示法，我們可以用 a[i][j] 快速地找到一個元素。但是，仍有一些問題存在此標準表示法中：

structure Sparse_Matrix is
  objects: a set of triples, <row, column, value>, where row and column
    are integers and form a unique combination, and value comes from the
    set item.
  functions:
    for all a, b in Sparse_Matrix, x in item, i, j, max_col, max_row in index

    Sparse_Matrix Create(max_row, max_col) ::=
        return a Sparse_Matrix that can hold up to max_items =
        max_row x max_col and whose maximum row size is max_row and
        whose maximum column size is max_col.

    Sparse_Matrix Transpose(a) ::=
        return the matrix produced by interchanging the row and column
        value of every triple.

    Sparse_Matrix Add(a, b) ::=
        if the dimensions of a and b are the same
        return the matrix produced by adding corresponding items, namely
        those with identical row and column values.
        else return error

    Sparse_Matrix Multiply(a, b) ::=
        if number of columns in a equals number of rows in b
        return the matrix d produced by multiplying a by b according to
        the formula: d[i][j] = sum(a[i][k] * b[k][j]) where d(i, j) is
        the (i, j)th element
        else return error.

end Sparse_Matrix

結構 2.3：抽象資料型態 Sparse_Matrix

Sparse_Matrix Create(max_row, max_col) ::=

     #define MAX_TERMS 101 /* maximum number of terms +1*/
     typedef struct {
             int col;
             int row;
             int value;
             } term;
     term a[MAX_TERMS];

圖 2.4：(a) 以三項式儲存的稀疏矩陣　(b) 其轉置矩陣

2.4.2　轉置矩陣

要將矩陣轉置，我們必須將行和列互換。就是說，在原始矩陣中的每一個元素 a[i][j] 變成轉置矩陣中的元素 b[j][i]。因為我們已將原始的矩陣依列序排列，我們或許會以為下列的演算法是將矩陣轉置的一個好方法：

for each row i
  take element <i, j, value> and store it
  as element <j, i, value> of the transpose;

藉著使用行索引來決定元素放在轉置矩陣中的位置，我們可避免這種資料移動。這建議下列的演算法：

for all elements in column j
  place element <i, j, value> in
  element <j, i, value>

這個演算法暗示了我們應該「找出行 0 所有的元素，而後將它們存放在轉置矩陣的列 0，找出行 1 所有的元素，而後將它們存放在轉置矩陣的列 1，等」。因為原始的矩陣以列序排列，轉置矩陣中每一列的各行也會以升冪順序排列。

void transpose(term a[], term b[])
/* b is set to the transpose of a */
{
   int n,i,j, currentb;
   n = a[0].value;          /* total number of elements */
   b[0].row = a[0].col;     /* rows in b = columns in a */
   b[0].col = a[0].row;     /* columns in b = rows in a */
   b[0].value = n;
   if (n > 0 ) { /* non zero matrix */
     currentb = 1;
     for (i = 0; i < a[0].col; i++)
     /* transpose by the columns in a */
       for (j = 1; j <= n; j++)
       /* find elements from the current column */
         if (a[j].col == i) {
         /* element is in current column, add it to b */
           b[currentb].row = a[j].col;
           b[currentb].col = a[j].row;
           b[currentb].value = a[j].value;
           currentb++;
         }
   }
}

程式 2.7：轉置一個稀疏矩陣

for (j = 0; j < columns; j++)
  for (i = 0; i < rows; i++)
    b[j][i] = a[i][j];

fast_transpose：用空間換回時間

實際上，藉著多使用一點儲存空間，我們可以建立一個更好的演算法，在 $O(\textit{columns}+\textit{elements})$ 時間內轉置完成。它首先決定在原始矩陣中每一行的元素個數（這可以決定轉置矩陣中每一列的元素個數），根據這個資訊決定轉置矩陣中每一列的起始位置，然後將原始矩陣中的元素逐一移到轉置矩陣中正確的位置上。

#define MAX_COL 50 /*maximum number of columns + 1*/

void fast_transpose(term a[], term b[])
{
/* the transpose of a is placed in b */
   int row_terms[MAX_COL], starting_pos[MAX_COL];
   int i,j, num_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) { /* nonzero matrix */
      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[0] = 1;
      for (i = 1; i < num_cols; i++)
        starting_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;
      }
   }
}

程式 2.8：一個稀疏矩陣的快速轉置

如果我們以圖 2.4(a) 之稀疏矩陣來試驗演算法，在執行第三個 for 迴圈以後，row_terms 和 starting_pos 之值為：

2.4.3　矩陣相乘

要相乘兩個以有序串列表示的稀疏矩陣，我們必須計算 $D$ 各列的元素，以便將元素儲存在適當的位置上而不必移動先前已計算的元素。做這件事，我們選擇 $A$ 中的一列並找出 $B$ 中行 $j$ 的所有元素，$j=0,1,\ldots,\texttt{cols\_b}-1$。

void mmult(term a[], term b[], term d[])
/* multiply two sparse matrices */
{
   int i, j, column, totalb = b[0].value, totald = 0;
   int rows_a = a[0].row, 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);
   /* set boundary condition */
   a[totala+1].row = rows_a;
   new_b[totalb+1].row = cols_b;
   new_b[totalb+1].col = 0;
   for (i = 1; i <= totala; ) {
     column = new_b[1].row;
     for (j = 1; j <= totalb+1;) {
     /* multiply row of a by column of b */
       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: /* go to next term in a */
             i++;  break;
          case 0: /* add terms, go to next term in a and b*/
             sum += ( a[i++].value * new_b[j++].value);
             break;
          case 1 : /* advance to next term in b */
             j++;
       }
     }  /* end of for j <= totalb+1 */
     for (; a[i].row == row; i++)
       ;
     row_begin = i; row = a[i].row;
   } /* end of for i<=totala */
   d[0].row = rows_a;
   d[0].col = cols_b; d[0].value =  totald;
}

程式 2.9：稀疏矩陣相乘

void storesum(term d[], int *totald, int row, int column,
                                     int *sum)
{
/* if *sum != 0, then it along with its row and column
position is stored as the *totald+1 entry in d */
   if (*sum)
     if (*totald < MAX_TERMS) {
       d[++*totald].row = row;
       d[*totald].col = column;
       d[*totald].value = *sum;
       *sum = 0;
     }
     else {
       fprintf(stderr,"Numbers of terms in product
                       exceeds %d\n",MAX_TERMS);
       exit(1);
     }
}

程式 2.10：storesum 函數

int t[MAX_COL], i, j, sum = 1, tmp;
for (i = 0; i < num_cols; i++) t[i] = 0;
for (i = 1; i <= num_terms; i++) t[a[i].col]++;
for (i = 0; i < num_cols; i++) {   /* prefix sum in place */
  tmp = t[i]; t[i] = sum; sum += tmp;
}

2.5　多維陣列的表示法

多維陣列的內部表示法需要更複雜的定址公式。如果陣列宣告為 $a[\textit{upper}_0][\textit{upper}_1]\cdots[\textit{upper}_{n-1}]$，則陣列中的元素個數可以很清楚地表示為：

舉例而言，如果宣告 a 為 a[10][10][10]，則需要 $10\cdot10\cdot10=1000$ 個儲存單位來保存此陣列。

二維

$A[\textit{upper}_0][\textit{upper}_1]$ 可以解釋為有 $\textit{upper}_0$ 列的二維陣列，即 $\textit{row}_0, \textit{row}_1, \ldots, \textit{row}_{\textit{upper}_0-1}$，每一列有 $\textit{upper}_1$ 個元素。

假設 $\alpha$ 為 $A[0][0]$ 的位址，則 $A[i][0]$ 的位址將是 $\alpha + i \cdot \textit{upper}_1$，因為在第 $i$ 列的第 1 個元素之前一共有 $i$ 列，每一列有 $\textit{upper}_1$ 個元素。

三維

$A[\textit{upper}_0][\textit{upper}_1][\textit{upper}_2]$ 可以解釋為有 $\textit{upper}_0$ 個二維陣列，每一個大小為 $\textit{upper}_1 \times \textit{upper}_2$。$a[i][0][0]$ 的位址為 $\alpha + i\cdot\textit{upper}_1\cdot\textit{upper}_2$：

n 維的一般式

將上述的討論一般化，一個 $n$ 維的陣列宣告為 $A[\textit{upper}_0][\textit{upper}_1]\ldots[\textit{upper}_{n-1}]$，則對於其中任何一個元素 $A[i_0][i_1]\ldots[i_{n-1}]$ 的定址公式為：

2.6　字串抽象資料型態

2.6.1　簡介

到目前為止，我們僅討論了成組元素為數值的 ADT。在本節中，我們將注意力轉到另一種資料型態，字串，其組成元素為字元。我們定義字串的形式為 $S = s_0, \ldots, s_{n-1}$，其中 $s_i$ 為程式語言字元集中的字元。如果 $n=0$，則 $S$ 為空字串或虛字串（null string）。

structure String is
  objects: a finite set of zero or more characters.
  functions:
    for all s, t in String, i, j, m in non-negative integers

    String  Null(m)        ::= return a string whose maximum length is
                               m characters, but is initially set to NULL.
                               We write NULL as "".
    Integer Compare(s, t)  ::= if s equals t return 0
                               else if s precedes t return -1
                               else return +1
    Boolean IsNull(s)      ::= if (Compare(s, NULL)) return FALSE
                               else return TRUE
    Integer Length(s)      ::= if (Compare(s, NULL))
                               return the number of characters in s
                               else return 0.
    String  Concat(s, t)   ::= if (Compare(t, NULL))
                               return a string whose elements are those
                               of s followed by those of t
                               else return s.
    String  Substr(s, i, j)::= if ((j > 0) && (i+j-1) < Length(s))
                               return the string containing the characters
                               of s at positions i, i+1, ..., i+j-1.
                               else return NULL.

end String

結構 2.4：抽象資料型態 string

在 C 語言中，字串以字元陣列表示，並以虛字元 \0 作為結束。舉例而言，如果定義了字串：

#define MAX_SIZE 100 /*maximum size of string */
char s[MAX_SIZE] = {"dog"};
char t[MAX_SIZE] = {"house"};

C 的字串函數

C 提供了其他數個字串函數，可透過指令 #include <string.h> 來存取它們。

圖 2.8：C 的字串函數

void strnins(char *s, char *t, int i)
{
/* insert string t into string s at position i */
  char string[MAX_SIZE], *temp = string;

  if (i < 0 && i > strlen(s)) {
    fprintf(stderr,"Position is out of bounds \n");
    exit(1);
  }
  if (!strlen(s))
    strcpy(s,t);
  else if (strlen(t)) {
    strncpy(temp, s,i);
    strcat(temp,t);
    strcat(temp, (s+i));
    strcpy(s, temp);
  }
}

2.6.2　樣式比對 (pattern matching)

假設有兩個字串 string 和 pat，其中 pat 是要在 string 中找尋的樣式。判斷 pat 是否在 string 中最簡單的方式是使用內建函數 strstr。

改良一：nfind —— 先比對結尾

藉著在 strlen(pat) 比 string 中剩下的字元之個數還多時結束比對工作，我們可以大幅地改良完全地樣式比對技術。在我們繼續檢查剩餘的字元之前檢查 pat 和 string 的第一個與最後一個字元是第二個改良點。

int nfind(char *string, char *pat)
{
/* match the last character of pattern first, and
then match from the beginning */
   int i,j,start = 0;
   int lasts = strlen(string)-1;
   int lastp = strlen(pat)-1;
   int endmatch = lastp;

   for (i = 0; endmatch <= lasts; endmatch++, start++) {
     if (string[endmatch] == pat[lastp])
       for (j = 0, i = start; j < lastp &&
                   string[i] == pat[j]; i++,j++)
         ;
     if (j == lastp)
       return start; /* successful */
     }
     return -1;
}

程式 2.12：首先檢查結尾索引的樣式比對程式

Knuth–Morris–Pratt 演算法

使用 Knuth、Morris 和 Pratt 的範例，假設 pat = 'abcabcacab'。令 $s = s_0s_1\ldots s_{m-1}$ 為字串，並且假設我們正在判斷從 $s_i$ 開始的位置是否有一個比對成功存在。

• 若 $s_i \ne a$，則明顯地，我們應可以繼續地比較 $s_{i+1}$ 和 $a$。
• 若 $s_i = a$，而 $s_{i+1} \ne b$，則應可以繼續地比較 $s_{i+1}$ 和 $a$。
• 若 $s_is_{i+1} = ab$ 且 $s_{i+2} \ne c$，則我們知道也許可以拿 $s_{i+2}$ 和樣式的第一個字元以比較 —— 因為已知 $s_{i+1}$ 和 pat 的第二個字元 b 相同，所以 $s_{i+1} \ne a$，我們不需要拿 $s_{i+1}$ 和字串的第一個字元來比較。

假設 pat 的前四個字元比對成功，其後有一個比對不成功，即 $s_{i+4} \ne b$：

s   = '-  a  b  c  a  ?  ?  .  .  .  .  ?'
pat = 'a  b  c  a  b  c  a  c  a  b'

經過觀察，我們發現搜尋匹配的樣式可以從比較 $s_{i+4}$ 和 pat 的第二個字元 b 再繼續。這是將樣式 pat 向右滑動可以發生部份配的第一個位置。

#include <stdio.h>
#include <string.h>
#define max_string_size 100
#define max_pattern_size 100
int pmatch();
void fail();
int failure[max_pattern_size];
char string[max_string_size];
char pat[max_pattern_size];

int pmatch(char *string, char *pat)
{
/* Knuth, Morris, Pratt string matching algorithm */
  int i = 0, j = 0;
  int lens = strlen(string);
  int lenp = strlen(pat);
  while ( i < lens && j < lenp ) {
    if (string[i] == pat[j]) {
      i++; j++; }
    else if (j == 0) i++;
        else j = failure[j-1]+1;
  }
  return ( (j == lenp) ? (i-lenp) : -1);
}

程式 2.13：Knuth、Morris、Pratt 的樣式比對演算法

快速計算失敗函數

根據 pmatch 的分析，如果我們可以在 $O(\texttt{strlen(pat)})$ 時間內計算失敗函數，則整個樣式比對過程的計算時間將和字串和樣式的長度和成正比。幸運地，有一個快速的方法可計算失敗函數。它以下列重新定義的失敗函數為依據：

（注意，$f^{\,1}(j)=f(j)$ 且 $f^{\,m}(j)=f(f^{\,m-1}(j))$。）

void fail(char *pat)
{
/* compute the pattern's failure function */
  int n = strlen(pat);
  failure[0] = -1;
  for (j=1; j < n; j++) {
    i = failure[j-1];
    while ((pat[j] != pat[i+1]) && (i >= 0))
      i = failure[i];
    if (pat[j] == pat[i+1])
      failure[j] = i+1;
    else failure[j] = -1;
  }
}

程式 2.14：計算失敗函數

2.7　精選參考文獻

2.8　綜合習題

三角矩陣 (triangular matrix)

三角矩陣是指一個方陣的主對角線以上的所有元素或主對角線以下的所有元素均為 0。在一個有 $n$ 列的下三角矩陣 $a$ 中，在列 $i$ 上不為 0 的元素個數最多 $i+1$ 個。因此，全部不為 0 的元素個數為：

本章重點回顧