2011年6月17日 星期五

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 





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
45
46
47
48
49
50
51
52
53
54

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





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

/* 程式範例: 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);






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

/* 程式範例: 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;   /* 插入節點指向新節點 */
        }
   }
}





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

/* 程式範例: 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);                /* 釋回刪除節點記憶體 */
}





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
45
46
47
48
49
50
51
52

/* 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; }
張貼者： 於

1 則留言:

訂閱： 張貼留言 (Atom)