Programming Practice

使用雙向連結表 (double-linked list) 寫一個 C 語言的程式以檢查一個字串是否為迴文。這個雙向連結表節點 (node) 與雙向連結表 (dlist) 的資料型態定義如下:

typedef struct Node {

  char elem;

  struct Node* left;

  struct Node* right;

} node;

 

typedef struct Double_List {

  node* tail = NULL;

  node* head = NULL;

} dlist;

而且,雙向連結表有如下的三個運算:

void add_to_tail (dlist *, char);           // 加入一個節點到尾部

void remove_from_tail (dlist *);          // 從尾部移除一個節點

void remove_from_head (dlist*);       // 從頭部移除一個節點

檢查迴文的方法為:

1          將字串的所有字元依序放入一個雙向連結表,

2          比較雙向連結表的頭部和尾部所指的節點,

2.1        如果頭部和尾部指向同一個節點,則所檢查的字串是一個迴文:

2.2        如果頭部和尾部指向不同的節點則

2.2.1          如果頭部和尾部所指節點的字元相等,則從頭部和尾部各移除一個節點,並回到步驟 2

2.2.2          如果頭部和尾部所指節點的字元不等,則所檢查的字串不是一個迴文。

以下為程式執行範例:

Enter a string: abcdedcba

 

"abcdedcba" is a palindrome.

 

**************************************************************

 

Enter a string: 945626549

 

 

945626549" is a palindrome.

 

**************************************************************

 

Enter a string: abcd

 

"abcd" is a not palindrome.

 

**************************************************************

 

Enter a string: 000