2011年6月17日 星期五

EX12. 鏈結串列insertNode

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




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

/* 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; 
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/* 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);






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

/* 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;                 /* 沒有找到 */






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/* 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
請按任意鍵繼續 . . .
張貼者： 於

1 則留言:

訂閱： 張貼留言 (Atom)