單循環鏈表(用尾指針表示)，尾指針

單循環鏈表(用尾指針表示)，尾指針

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 /* 用尾指針表示的單循環鏈表，相比於使用頭指針表示的單循環鏈表：
 4  * 後者在尋找鏈表的第一個節點的時候，時間復雜度是O(1),在尋找鏈
 5  * 表的最後一個元素的時候，時間復雜度是O(n)。
 6  * 前者在尋找鏈表的第一個節點的時候，事件復雜度是O(1)(tail->next
 7  * ->next->data即為第一個元素的值)，在尋找最後一個節點的時候，時間
 8  * 復雜度為O(1).
 9  * */
10 typedef struct Node{
11     int data;
12     struct Node* next;
13 }Node;
14 typedef struct Node* LinkList;
15 
16 void Initial_SCL_tail(LinkList* L){
17     *L = (LinkList)malloc(sizeof(struct Node));
18     if(!(*L)){
19         printf("Error:Initial:malloc!\n");
20         exit(1);
21     }
22     (*L)->next = *L;
23 }
24 void Create_SCLtail(LinkList* L,int number){
25     int i;
26     LinkList new;
27     LinkList tail = *L;
28     printf("---Create LinkList---\n");
29     for(i = 1;i <= number; i++){
30         new = (LinkList)malloc(sizeof(struct Node));
31         if(!new){
32             printf("Error:Create_SCLtail:malloc:%d\n",i);
33             exit(1);
34         }
35         printf("please enter %d element: ",i);
36         scanf("%d",&(new->data));
37         tail->next = new;
38         new->next = (*L);
39         tail = new;
40     }
41     *L = new;
42 }
43 void connect(LinkList LA,LinkList *LB){
44 /* 將LB鏈接到LA的後面
45  * */
46     LinkList temp,temp1;
47     temp = LA->next;
48     temp1 = (*LB)->next;
49     LA->next = (*LB)->next->next;
50     (*LB)->next = temp;
51     free(temp1);
52 }
53 void Display_SCLtail(LinkList L){
54     LinkList temp;
55     printf("Element of List is:");
56     temp = L->next->next;//temp now point to first node;
57     while(temp != L->next){
58         printf("%d ",temp->data);
59         temp = temp->next;
60     }
61     printf("\n");
62 }
63 int main(){
64     LinkList L1,L2;
65     Create_SCLtail(&L1,5);
66     Create_SCLtail(&L2,8);
67     Display_SCLtail(L1);
68     Display_SCLtail(L2);
69     connect(L1,&L2);
70     Display_SCLtail(L2);
71     return 0;
72 }