資料結構學習網誌

2011年6月17日星期五

EX18. 使用陣列建立佇列

修改程式範例: Ch6-2-1.c 為 Ch6-2-1e.c
1.請使用陣列方式建立佇列
2.請於程式中加入功能如下: [1]存入 [2]取出 [3]顯示全部…
[1]存入 : 詢問輸入存入值
[2]取出 : 顯示取出佇列元素
[3]顯示全部 :顯示輸入佇列的元素/取出佇列的元素/剩下佇列的元素
3.功能參考(ch6-2-2.c)

/* 程式範例: Ch6-2-1.h */
#define MAXQUEUE 10          /* 佇列的最大容量 */
int queue[MAXQUEUE];         /* 佇列的陣列宣告 */
int front = -1;              /* 佇列的前端 */
int rear = -1;               /* 佇列的尾端 */
/* 抽象資料型態的操作函數宣告 */
extern int isQueueEmpty(); 
extern int enqueue(int d);
extern int dequeue();

/* 程式範例: Ch6-2-1e.c */
#include <stdio.h>
#include <stdlib.h> 
#include "Ch6-2-1.h"
/* 函數: 檢查佇列是否是空的 */
int isQueueEmpty() {
   if ( front == rear ) return 1;
   else                 return 0;
}
/* 函數: 將資料存入佇列 */
int enqueue(int d) {
   if ( rear >= MAXQUEUE )  /* 是否超過佇列容量 */
     return 0;
   else {
      queue[++rear] = d;    /* 存入佇列 */
      return 1;
   }
}
/* 函數: 從佇列取出資料 */
int dequeue() {
   if ( isQueueEmpty() )   /* 佇列是否是空的 */
      return -1;
   else
      return queue[++front];/* 取出資料 */
}
/* 主程式 */
int main() {   
   int input[100], output[100]; /* 儲存輸入和取出元素 */
   int select = 1;              /* 選項 */
   int numOfInput  = 0;         /* 陣列的元素數 */
   int numOfOutput = 0;
   int i, temp;
   printf("鏈結串列的佇列處理......\n");                 
   while ( select != 3 ) {       /* 主迴圈 */
      printf("[1]存入 [2]取出 [3]顯示全部內容 ==> ");
      scanf("%d", &select);      /* 取得選項 */
      switch ( select ) {
         case 1: /* 將輸入值存入佇列 */
            printf("請輸入存入值(%d) ==> ", numOfInput);
            scanf("%d", &temp);  /* 取得存入值 */
            enqueue(temp); 
            input[numOfInput++] = temp;
            break;
         case 2: /* 取出佇列的內容 */
            if ( !isQueueEmpty() ) {
               temp = dequeue();
               printf("取出佇列元素: %d\n", temp);
               output[numOfOutput++] = temp;
            }
            break;
      }
   }
   printf("輸入佇列的元素: ");    /* 輸入元素 */
   for ( i = 0; i < numOfInput; i++ )
      printf("[%d]", input[i]);
   printf("\n取出佇列的元素: ");  /* 輸出元素 */
   for ( i = 0; i < numOfOutput; i++ )
      printf("[%d]", output[i]);
   printf("\n剩下佇列的元素: ");  /* 取出剩下佇列元素 */
   while ( !isQueueEmpty() )
      printf("[%d]", dequeue()); 
   printf("\n");
   system("PAUSE");
   return 0; 
}

執行結果：
鏈結串列的佇列處理......
[1]存入 [2]取出 [3]顯示全部內容 ==> 1
請輸入存入值(0) ==> 1
[1]存入 [2]取出 [3]顯示全部內容 ==> 1
請輸入存入值(1) ==> 2
[1]存入 [2]取出 [3]顯示全部內容 ==> 1
請輸入存入值(2) ==> 3
[1]存入 [2]取出 [3]顯示全部內容 ==> 1
請輸入存入值(3) ==> 4
[1]存入 [2]取出 [3]顯示全部內容 ==> 1
請輸入存入值(4) ==> 5
[1]存入 [2]取出 [3]顯示全部內容 ==> 2
取出佇列元素: 1
[1]存入 [2]取出 [3]顯示全部內容 ==> 2
取出佇列元素: 2
[1]存入 [2]取出 [3]顯示全部內容 ==> 2
取出佇列元素: 3
[1]存入 [2]取出 [3]顯示全部內容 ==> 3
輸入佇列的元素: [1][2][3][4][5]
取出佇列的元素: [1][2][3]
剩下佇列的元素: [4][5]
請按任意鍵繼續 . .

EX17. 河內塔問題

修改程式範例: Ch5-5.c 為 Ch5-5e.c

1. 請建立遞迥函數解出5個盤子的河內塔問題
2. 請參考如下方式用Excel寫出所有完整的遞迥呼叫的執行過程
3. 執行過程Excel檔請在Google 文件設為共用並將url置於網頁上

https://spreadsheets.google.com/spreadsheet/ccc?key=0ApUm9nzN2PbqdEthRmYyZURuTjM2ODRjSmlNUFdnS2c&hl=en_US

/* 程式範例: Ch5-5e.c */
#include <stdio.h>
#include <stdlib.h>
/* 河內塔問題的遞迴函數 */
int hanoiTower(int dishs,int peg1,int peg2,int peg3) {
   if ( dishs == 1)             /* 終止條件 */
     printf("盤子從 %d 移到 %d\n", peg1, peg3);
   else {
     hanoiTower(dishs - 1,peg1,peg3,peg2); /* 第1步驟 */
     printf("盤子從 %d 移到 %d\n", peg1, peg3);
     hanoiTower(dishs - 1,peg2,peg1,peg3); /* 第3步驟 */
   }
}
/* 主程式 */
int main() {
   hanoiTower(5,1,2,3);          /* 呼叫遞迴函數 */
   system("PAUSE");
   return 0; 
}

執行結果：
盤子從 1 移到 3
盤子從 1 移到 2
盤子從 3 移到 2
盤子從 1 移到 3
盤子從 2 移到 1
盤子從 2 移到 3
盤子從 1 移到 3
盤子從 1 移到 2
盤子從 3 移到 2
盤子從 3 移到 1
盤子從 2 移到 1
盤子從 3 移到 2
盤子從 1 移到 3
盤子從 1 移到 2
盤子從 3 移到 2
盤子從 1 移到 3
盤子從 2 移到 1
盤子從 2 移到 3
盤子從 1 移到 3
盤子從 2 移到 1
盤子從 3 移到 2
盤子從 3 移到 1
盤子從 2 移到 1
盤子從 2 移到 3
盤子從 1 移到 3
盤子從 1 移到 2
盤子從 3 移到 2
盤子從 1 移到 3
盤子從 2 移到 1
盤子從 2 移到 3
盤子從 1 移到 3
請按任意鍵繼續 . . .

EX16. 使用遞迥走迷宮

參考程式範例: Ch5-4-2.c
1. 請寫出所有完整的遞迥呼叫的執行過程：

執行過程：

https://spreadsheets.google.com/spreadsheet/ccc?key=0ApUm9nzN2PbqdERUemNMeXBZWG50YWs1WTZDdlFwa0E&hl=zh_TW

/* 程式範例: Ch5-4-2.c */
#include <stdio.h>
#include <stdlib.h>
int maze[7][10] = { /* 迷宮陣列,數字0可走, 1不可走 */
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 0, 1, 0, 1, 0, 0, 0, 0, 1,
        1, 0, 1, 0, 1, 0, 1, 1, 0, 1,
        1, 0, 1, 0, 1, 1, 1, 0, 0, 1,
        1, 0, 1, 0, 0, 0, 0, 0, 1, 1,
        1, 0, 0, 0, 1, 1, 1, 0, 0, 1,
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
/* 走迷宮的遞迴函數 */
int findPath(int x,int y) {
   if ( x == 1 && y == 1 ) {      /* 是否是迷宮出口 */
      maze[x][y] = 2;             /* 記錄最後走過的路 */
      return 1;
   }
   else if ( maze[x][y] == 0 ) {  /* 是不是可以走的路 */
          maze[x][y] = 2;         /* 記錄己經走過的路 */
          if ( ( findPath(x - 1,y) +       /* 往上 */
                 findPath(x + 1,y) +       /* 往下 */
                 findPath(x,y - 1) +       /* 往左 */
                 findPath(x,y + 1) ) > 0 ) /* 往右 */
              return 1;
          else {
              maze[x][y] = 0;    /* 此路不通取消記號 */
              return 0;
          }
        }
        else return 0;
}
/* 主程式: 使用遞迴函數在陣列走迷宮 */
int main() {
   int i,j;
   findPath(5,8);                   /* 呼叫遞迴函數 */
   printf("迷宮路徑圖(從右下角到左上角): \n");
   for ( i = 0; i <= 6; i++) {      /* 顯示迷宮圖形 */
      for ( j = 0; j <= 9; j++)
         printf("%d ", maze[i][j]); /* 顯示座標值 */
      printf("\n");
   }
   printf("\n數字 1: 牆壁\n數字 2: 走過的路徑\n");  
   system("PAUSE");
   return 0; 
}

EX15.使用堆疊的回溯控制- 走迷宮

修改程式範例: Ch5-4-1.c 為 Ch5-4-1e.c
1. 請使用堆疊方式找出走出迷宮的路，如下所示：
2. 可走的路自行設定。

/* 程式範例: Stack.c */
#include "Ch5-2-2.h"
/* 函數: 檢查堆疊是否是空的 */
int isStackEmpty() {
   if ( top == NULL ) return 1;
   else               return 0;
}
/* 函數: 將資料存入堆疊 */
void push(int d) {
   LStack new_node;            /* 新節點指標 */
   /* 配置節點記憶體 */
   new_node = (LStack)malloc(sizeof(SNode));
   new_node->data = d;         /* 建立節點內容 */
   new_node->next = top;       /* 新節點指向原開始 */
   top = new_node;             /* 新節點成為堆疊開始 */   
}
/* 函數: 從堆疊取出資料 */
int pop() {
   LStack ptr;                 /* 指向堆疊頂端 */
   int temp;
   if ( !isStackEmpty()  ) {   /* 堆疊是否是空的 */
      ptr = top;               /* 指向堆疊頂端 */
      top = top->next;         /* 堆疊指標指向下節點 */
      temp = ptr->data;        /* 取出資料 */
      free(ptr);               /* 釋回節點記憶體 */
      return temp;             /* 堆疊取出 */
   }
   else return -1;
}

/* 程式範例: Ch5-2-2.h */
struct Node {                  /* 堆疊節點的宣告 */
   int data;                   /* 儲存堆疊資料 */
   struct Node *next;          /* 指向下一節點 */
};
typedef struct Node SNode;     /* 堆疊節點的新型態 */ 
typedef SNode *LStack;         /* 串列堆疊的新型態 */
LStack top = NULL;             /* 堆疊頂端的指標 */
/* 抽象資料型態的操作函數宣告 */ 
extern int isStackEmpty();
extern void push(int d);
extern int pop();

/* 程式範例: Ch5-4-1e.c */
#include <stdio.h>
#include <stdlib.h>
#include "stack.c"
/* 主程式: 使用回溯方法在陣列走迷宮 */
int main() {
   int maze[8][11] = { /* 迷宮陣列,數字0可走, 1不可走 */
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
            1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1,
            1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1,
            1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1,
            1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1,
            1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
            1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1,
            1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
   int i,j;
   int x = 6;                     /* 迷宮入口座標 */
   int y = 9;
   while ( x != 1 || y != 1 ) {   /* 主迴圈 */
      maze[x][y] = 2;             /* 標示為已走過的路 */
      if ( maze[x-1][y] <= 0 ) {  /* 往上方走 */
         x = x - 1;               /* 座標x減1 */
         push(x);                 /* 存入路徑 */
         push(y);
      }
      else if ( maze[x+1][y] <= 0 ) { /* 往下方走 */
           x = x + 1;            /* 座標x加1 */
           push(x);              /* 存入路徑 */
           push(y);
         }
         else if ( maze[x][y-1] <= 0 ) { /* 往左方走 */
              y = y - 1;            /* 座標y減1 */
              push(x);              /* 存入路徑 */
              push(y);
           }
           else if ( maze[x][y+1] <= 0 ) {/* 往右方走 */
                y = y + 1;             /* 座標y加1 */
                push(x);               /* 存入路徑 */
                push(y);
             }
             else {  /* 沒有路可走:迴溯 */
                  maze[x][y] = 3;   /* 表示是迴溯的路 */
                  y = pop();        /* 退回一步 */
                  x = pop();
               }
   }
   maze[x][y] = 2;                /* 標示最後位置 */
   printf("迷宮路徑圖(從右下角到左上角): \n");
   for ( i = 0; i <= 7; i++) {    /* 顯示迷宮圖形 */
      for ( j = 0; j <= 10; j++)
         printf("%d ", maze[i][j]); /* 顯示座標值 */
      printf("\n");
   }
   printf("\n數字 1: 牆壁\n數字 2: 走過的路徑\n");
   printf("數字 3: 回溯路徑\n");
   system("PAUSE");
   return 0; 
}

執行結果：
迷宮路徑圖(從右下角到左上角):
1 1 1 1 1 1 1 1 1 1 1
1 2 1 2 2 2 1 1 1 1 1
1 2 2 2 1 2 2 1 1 1 1
1 1 3 1 1 1 2 2 1 1 1
1 1 3 1 1 1 1 2 2 1 1
1 3 2 3 3 3 3 1 2 2 1
1 3 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 1 1 1 1
數字 1: 牆壁
數字 2: 走過的路徑
數字 3: 回溯路徑
請按任意鍵繼續 . . .

EX14. 鏈結串列的應用- 多項式表示法

修改程式範例: Ch4-6.c 為 Ch4-6e.c
請使用含開頭節點的環狀串列結構儲存下列多項式，如下所示：
(1) f(x) = X4+5X3+4X+3
(2) g(x) = 5X2+2X+5

/* Ch4-6e.c */
#include <stdio.h>
#include <stdlib.h>
#include "Ch4-6.h"
#include "createPoly.c"
/* 主程式 */
int main() 
{
   PList a = NULL;    /* 多項式串列1的開頭指標 */
   PList b = NULL;    /* 多項式串列2的開頭指標 */
   /* 建立多項式物件所需的陣列 */
   float list1[5] = { 3, 4, 0, 5, 1 };
   float list2[5] = { 5, 2, 5, 0, 0 };
   a = createPoly(5, list1);  /* 建立多項式串列1 */
   b = createPoly(5, list2);  /* 建立多項式串列2 */
   printf("f(x) = "); /* 顯示多項式1 */
   printPoly(a); 
   printf("g(x) = "); /* 顯示多項式2 */   
   printPoly(b);     
   system("PAUSE");
   return 0; 
}

/* Ch4-6.h */
struct Node                 /* Node節點結構 */
{               
   float coef;  int exp;    /* 結構變數宣告 */
   struct Node *next;       /* 指向下一個節點 */
};
typedef struct Node PNode;  /* 多項式串列節點的新型態 */
typedef PNode *PList;       /* 多項式串列的新型態 */
/* 抽象資料型態的操作函數宣告 */
extern PList createPoly(int len, float *array);
extern void printPoly(PList first);

/* createPoly.c */
/* 函數: 建立多項式的串列 */
PList createPoly(int len, float *array) 
{
   int i;
   PList first, ptr, newnode;   /* 建立開頭節點 */
   first = (PList) malloc(sizeof(PNode));
   first->coef = 0.0;     /* 建立開頭節點的內容 */
   first->exp = -1;  
   ptr = first;               /* 前一個節點指標 */
   for ( i = len-1; i >= 0; i-- ) 
   {
      if ( array[i] != 0.0 )  /* 配置節點記憶體 */
      {     
         newnode = (PList) malloc(sizeof(PNode));
         newnode->coef = array[i]; /* 建立節點的內容 */
         newnode->exp = i;         
         ptr->next = newnode;      /* 連結新節點 */ 
         ptr = newnode;            /* 成為前一個節點 */ 
      }   
   }
   ptr->next = first; /* 連結第1個節點, 建立環狀串列 */
   return first;
}
/* 函數: 顯示多項式 */
void printPoly(PList first) 
{
   PList ptr = first->next;  /* 串列真正的開頭 */
   float c;
   int e;
   while ( ptr != first )    /* 顯示主迴圈 */
   {  
      c = ptr->coef;
      e = ptr->exp;
      printf("%3.1fX^%d", c, e);
      ptr = ptr->next;       /* 下一個節點 */
      if ( ptr != first ) printf(" + ");
   }
   printf("\n");   
}

/* OUTPUT */

f(x) = 1.0X^4 + 5.0X^3 + 4.0X^1 + 3.0X^0
g(x) = 5.0X^2 + 2.0X^1 + 5.0X^0
請按任意鍵繼續 . . .

EX13. 雙向鏈結串列

修改程式範例: Ch4-5-3.c 為 Ch4-5-3e.c
1.將雙向鏈結串列的所有操作整合
2.整合的功能如下:
[F] 往下移動
[B] 往前移動
[A] 新增節點
[D] 刪除節點
[R] 重設
[V] 節點值
[E] 離開
3.參考Ch4-5-1.c Ch4-5-2.c Ch4-5-3.c

/* Ch4-5-3.c */
#include <stdio.h>
#include <stdlib.h>
#include "Ch4-5.h"
#include "createDList.c"
#include "deleteDNode.c"
#include "insertDNode.c"
/* 主程式 */
int main()
{
   int temp;  /* 宣告變數 */
   char choice;
   int data[6]={ 1, 2, 3, 4, 5, 6 };/* 建立串列的陣列 */
   createDList(6, data);      /* 建立雙向串列 */ 
   while ( choice != 'E' ) 
   {  
      printf("現在的串列 : ");
      printDList();              /* 顯示串列 */     
      printf("[H]新增為第一個節點   [F]往下移動  [B]往前移動\n");
      printf("[A]新增節點  [D]刪除節點  [R]重設  [V]節點值  ");
      printf("[E]離開 ==> ");
      scanf(" %c",&choice);      /* 讀入選項 */
      switch ( choice )  
      {
         case 'H':/* 新增為第1個節點 */    
            printf("\n請輸入新號碼(7~100) ==> ");
            scanf("%d", &temp); /* 讀取新編號 */
            insertDNode(NULL, temp);           
            break;                   
         case 'F': nextNode();    /* 往下移動 */
            break;
         case 'B': previousNode();/* 往前移動 */ 
            break;
         case 'A': /* 新增節點 */
            printf("\n請輸入新號碼(7~100) ==> ");
            scanf("%d", &temp); /* 讀取新編號 */
            insertDNode(readNode(),temp);            
            break;   
         case 'D': /* 刪除節點 */
            deleteDNode(readNode());
            resetNode();      /* 重設目前指標 */           
            break;
         case 'R': resetNode();   /* 重設指標 */ 
            break;
         case 'V': /* 讀取節點值 */
            printf("\n節點值: %d\n", readNode()->data); 
            break;         
      }
      printf("\n");
      
   }       
   system("PAUSE");
   return 0; 
}

/* 程式範例: Ch4-5.h */
struct Node /* Node節點結構 */
{             
   int data;              /* 結構變數宣告 */ 
   struct Node *next;     /* 指向下一個節點 */
   struct Node *previous; /* 指向前一個節點 */ 
};
typedef struct Node DNode;   /* 雙向串列節點的新型態 */
typedef DNode *DList;        /* 雙向串列的新型態 */
DList first = NULL;          /* 雙向串列的開頭指標 */
DList now = NULL;            /* 雙向串列目前節點指標 */ 
/* 抽象資料型態的操作函數宣告 */
extern void createDList(int len, int *array);
extern void printDList();
extern void nextNode();
extern void previousNode();
extern void resetNode();
extern DList readNode();
extern void insertDNode(DList ptr, int d);
extern void deleteDNode(DList ptr);

/* 程式範例: insertDNode.c */
/* 函數: 插入節點 */
void insertDNode(DList ptr, int d) 
{ 
   /* 配置節點記憶體 */
   DList newnode = (DList) malloc(sizeof(DNode));
   newnode->data = d;      /* 建立節點內容 */ 
   if ( first == NULL )         /* 如果串列是空的 */
      first = newnode;          /* 傳回新節點指標 */
   if ( ptr == NULL ) 
    {
      /* 情況1: 插在第一個節點之前, 成為串列開始 */
      newnode->previous = NULL; /* 前指標為NULL */ 
      newnode->next = first;    /* 新節點指向串列開始 */
      first->previous = newnode;/* 原節點指向新節點 */
      first = newnode;          /* 新節點成為串列開始 */
    }
   else 
    {
      if ( ptr->next == NULL )/* 是否是最後一個節點 */
        {
          /* 情況2: 插在串列的最後 */
          ptr->next = newnode;   /* 最後節點指向新節點 */
          newnode->previous=ptr; /* 新節點指回最後節點 */
          newnode->next = NULL;  /* 後回指標為NULL */ 
        }
      else 
        {
          /* 情況3: 插入節點至串列的中間節點 */
          ptr->next->previous = newnode; /* 指回新節點 */
          newnode->next = ptr->next;  /* 指向下一節點 */
          newnode->previous=ptr; /* 新節點指回插入節點 */
          ptr->next = newnode;   /* 插入節點指向新節點 */
        }
   }
}

/* 程式範例: deleteDNode.c */
/* 函數: 刪除節點 */
void deleteDNode(DList ptr) 
{
   if ( ptr->previous == NULL )/* 是否有前一個節點 */ 
   { 
      /* 情況1: 刪除第一個節點 */
      first = first->next;      /* 指向下一個節點 */
      first->previous = NULL;   /* 設定指向前節點指標 */
   }
   else 
   {
      if ( ptr->next == NULL )  /* 是否有下一個節點 */
      {  
         /* 情況2: 刪除最後一個節點 */
         ptr->previous->next = NULL;/* 前節點指向NULL */
      }
      else 
      {
         /* 情況3: 刪除中間的節點 */
         /* 前節點指向下一節點 */
         ptr->previous->next = ptr->next;
         /* 下一節點指向前節點 */
         ptr->next->previous = ptr->previous;
      }
   }
   free(ptr);                /* 釋回刪除節點記憶體 */
}

/* createDList.c */
/* 函數: 建立雙向串列 */
void createDList(int len, int *array)
{
   int i;
   DList newnode, before;    /* 配置第1個節點 */
   first = (DList) malloc(sizeof(DNode));
   first->data = array[0];   /* 建立節點內容 */ 
   first->previous = NULL;   /* 前節點指標為NULL */ 
   before = first;           /* 指向第一個節點 */
   now = first;              /* 重設目前節點指標 */
   for ( i = 1; i < len; i++ ) 
   {
      /* 配置節點記憶體 */
      newnode = (DList) malloc(sizeof(DNode));
      newnode->data = array[i]; /* 建立節點內容 */ 
      newnode->next = NULL;     /* 下節點指標為NULL */ 
      newnode->previous=before; /* 將新節點指向前節點 */
      before->next=newnode;     /* 將前節點指向新節點 */
      before = newnode;         /* 新節點成為前節點 */
   }
}
/* 函數: 顯示雙向串列的節點資料 */
void printDList() 
{
   DList current = first;       /* 目前的節點指標 */
   while ( current != NULL ) 
   {  /* 顯示主迴圈 */
      if ( current == now )
         printf("#%d#", current->data);
      else 
         printf("[%d]", current->data);
      current = current->next;  /* 下一個節點 */
   }
   printf("\n");
}
/* 函數: 移動節點指標到下一個節點 */
void nextNode() 
{
   if ( now->next != NULL )
      now = now->next;          /* 下一個節點 */
}
/* 函數: 移動節點指標到上一個節點 */ 
void previousNode() 
{
   if ( now->previous != NULL )
      now = now->previous;      /* 前一個節點 */
}
/* 函數: 重設節點指標 */
void resetNode() {  now = first; }
/* 函數: 取得節點指標 */
DList readNode() { return now; }

EX12. 鏈結串列insertNode

修改程式範例: Ch4-3-3.c 為 Ch4-3-3e.c
1.修改 Ch4-3-3.c 中include的 “insertNode.c”程式
2.將”情況2: 插入最後一個節點”及”
情況3: 插入成為中間節點 “的程式碼判斷改為同時指向ptr->next.

/* Ch4-3-3e.c */
#include <stdio.h>
#include <stdlib.h>
#include "Ch4-3.h"
#include "createList.c"
#include "insertNode.c"
/* 主程式 */
int main()
{
   int temp;  /* 宣告變數 */
   int data[6]={ 1, 2, 3, 4, 5, 6}; /* 建立串列的陣列 */
   List ptr;
   createList(6, data); /* 建立串列 */
   printf("原來的串列: ");
   printList();         /* 顯示串列 */ 
   /* 4-3-3: 節點插入 */
   temp = 0;
   insertNode(NULL, 50); /* 插入第一個節點 */
   printf("插入後串列: ");
   printList();          /* 顯示插入後串列 */
   while ( temp != -1 ) 
    {
      printf("請輸入插入其後的郵寄編號(-1結束) ==> ");
      scanf("%d", &temp);          /* 讀取郵寄編號 */
      if ( temp != -1 ) 
       {
         ptr = searchNode(temp);       /* 找尋節點 */
         if ( ptr != NULL ) 
            printf("請輸入新的郵寄編號(0~100) ==> ");
            scanf("%d", &temp);/* 讀取新的郵寄編號 */
            insertNode(ptr, temp);
            printf("插入後串列: ");
            printList();         /* 顯示插入後串列 */
       } 
    }
   system("PAUSE");
   return 0; 
}

/* Ch4-3.h */
struct Node 
{  /* Node節點結構 */
   int data;          /* 結構變數宣告 */ 
   struct Node *next; /* 指向下一個節點 */
};
typedef struct Node LNode;   /* 串列節點的新型態 */
typedef LNode *List;         /* 串列的新型態 */
List first = NULL;           /* 串列的開頭指標 */
/* 抽象資料型態的操作函數宣告 */
extern void creatList(int len, int *array);
extern int isListEmpty();
extern void printList();
extern List searchNode(int d);
extern int deleteNode(List ptr);
extern void insertNode(List ptr, int d);

/* createList.c */
/* 函數: 建立串列 */
void createList(int len, int *array) 
{
   int i;
   List newnode;
   for ( i = 0; i < len; i++ ) 
     {
      /* 配置節點記憶體 */
      newnode = (List) malloc(sizeof(LNode));
      newnode->data = array[i]; /* 建立節點內容 */ 
      newnode->next = first;
      first = newnode;
     }
}
/* 函數: 檢查串列是否是空的 */
int isListEmpty() 
{
   if ( first == NULL ) return 1;
   else                 return 0;
}
/* 函數: 顯示串列資料 */
void printList() 
{
   List current = first;        /* 目前的串列指標 */
   while ( current != NULL ) 
   {   /* 顯示主迴圈 */
      printf("[%d]", current->data);
      current = current->next;  /* 下一個節點 */
   }
   printf("\n");
}
/* 函數: 搜尋節點資料 */
List searchNode(int d) 
{
   List current = first;        /* 目前的串列指標 */
   while ( current != NULL ) 
   {   /* 搜尋主迴圈 */
      if ( current->data == d ) /* 是否找到資料 */
         return current;        /* 找到 */
      current = current->next;  /* 下一個節點 */
   }
   return NULL;                 /* 沒有找到 */

/* insertNode.c */
/* 函數: 插入節點 */
void insertNode(List ptr, int d) 
{   
   List newnode;
   /* 配置節點記憶體 */
   newnode = (List) malloc(sizeof(LNode));
   newnode->data = d;          /* 指定節點值 */ 
   if ( ptr == NULL ) 
     {
       /* 情況1: 插入第一個節點 */
      newnode->next = first;   /* 新節點成為串列開始 */
      first = newnode;
     }
   else 
     {
      /* 情況2: 插入中間節點或最後一個節點 */
        newnode->next=ptr->next;/* 新節點指向下一節點 */
        ptr->next = newnode;    /* 節點ptr指向新節點 */
     }
}

/* OUTPUT */

原來的串列: [6][5][4][3][2][1]
插入後串列: [50][6][5][4][3][2][1]
請輸入插入其後的郵寄編號(-1結束) ==> 5
請輸入新的郵寄編號 (0~100) ==> 17
插入後串列: [50][6][5][17][4][3][2][1]
請輸入插入其後的郵寄編號 (-1結束) ==> 1
請輸入新的郵寄編號(0~100) ==> 18
插入後串列: [50][6][5][17][4][3][2][1][18]
請輸入插入其後的郵寄編號(-1結束) ==> -1
請按任意鍵繼續 . . .

訂閱：文章 (Atom)

2011年6月17日 星期五