使用鏈結串列來製作佇列

f66666602

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. typedef struct list         /* 宣告鏈結串列結構 */
   
4. {
   
5.   int data;                 /* 資料欄位 */
   
6.   struct list *link;        /* 指標欄位 */
   
7. }node;
   
8. node *Z=NULL;
   
9. void print_list(node *);
   
10. node *create_list(int *, int);
    
11. void free_list(node *);
    
12. void concatenate(node *, node *);
    
13. void main( )
    
14. {
    
15.   node *X=NULL, *Y=NULL;
    
16.   int array1[6]={ 1, 3, 5, 7, 9, 11 };
    
17.   int array2[6]={ 2, 4, 6, 8, 10, 12 };
    
18.   X=create_list(array1, 6);                 /* 建立鏈結串列X */
    
19.   Y=create_list(array2, 6);                 /* 建立鏈結串列Y */
    
20.   printf("原來的鏈結串列X:\n");
    
21.   print_list(X);
    
22.   printf("原來的鏈結串列Y:\n");
    
23.   print_list(Y);
    
24.   concatenate(X, Y);                /* 將鏈結串列X，Y合併成Z */
    
25.   printf("合併後的鏈結串列Z:\n");
    
26.   print_list(Z);
    
27.   free_list(Z);
    
28. }
    
29. 
    
30. void print_list(node *head)     /* 印出鏈結串列的內容 */
    
31. {
    
32.   node *ptr;                /* 走訪鏈結串列所用的指標 */
    
33.   for(ptr=head; ptr!=NULL; ptr=ptr->link)
    
34.     printf("[%d]", ptr->data);   /* 印出鏈結串列節點內容 */
    
35.   printf("\n");                /* 換行 */
    
36. }
    
37.                            
    
38. node *create_list(int *array, int len)   /* 依陣列架構出鏈結串列 */
    
39. {
    
40.   node *head;                  /* 鏈結串列的起始指標 */
    
41.   node *pre_node;            /* 新節點之前節點的指標 */
    
42.   node *new_node;                   /* 新節點的指標 */
    
43.   int i;
    
44.   for(i=0; i<len; i++)
    
45.   {
    
46.     new_node=(node *)malloc(sizeof(node));  /* 配置記憶體空間給新節點 */
    
47.     if(new_node == NULL)
    
48.     {
    
49.       printf("記憶體配置失敗!\n");
    
50.       exit(1);              /* 立刻結束程式 */
    
51.     }
    
52.     new_node->data=array;  /* 將陣列內容置入鏈結串列中 */
    
53.     if(i == 0)            /* 當第一次放入時，將head指標指向第一個節點 */
    
54.     {
    
55.       new_node->link=NULL;
    
56.       head=new_node;
    
57.     }
    
58.     else                  /* 先走訪至最後一個節點，再加入新的節點 */
    
59.     {
    
60.       for(pre_node=head; pre_node->link!=NULL; pre_node=pre_node->link);
    
61.       new_node->link=pre_node->link;
    
62.       pre_node->link=new_node;
    
63.     }
    
64.   }
    
65.   return head;               /* 將改變過後的鏈結串列傳回 */
    
66. }
    
67. 
    
68. void free_list(node *head)    /* 將整個鏈結串列的記憶體歸還 */
    
69. {
    
70.   node *free_node;
    
71.   while(head != NULL)
    
72.   {
    
73.     free_node=head;
    
74.     head=head->link;
    
75.     free(free_node);
    
76.   }
    
77. }
    
78. 
    
79. void concatenate(node *X, node *Y)
    
80. {
    
81.   node *ptr;
    
82.   if(X == NULL)          /* 若X為空串列，則將Y的位址傳回 */
    
83.     Z=Y;
    
84.   else if(Y == NULL)       /* 若Y為空串列，則將X的位址傳回 */
    
85.     Z=X;
    
86.   else
    
87.   {                   /* 走訪至尾端節點 */
    
88.     for(ptr=X, Z=X; ptr->link!=NULL; ptr=ptr->link);
    
89.             /* 將鏈結串列X的尾端節點指向鏈結串列Y的開始節點 */
    
90.     ptr->link=Y;
    
91.   }
    
92. }

複製代碼