[C語言] 連結串列(link list)

原始碼

1. /* link list (連結串列) */ 
2. #include<stdio.h> 
3. #include<string.h> 
4. #include<stdlib.h> 
5.  
6. /* 定義結構型態 */ 
7. typedef struct link_node{ 
8.    int data; 
9.    struct link_node *link; 
10. } LINK_NODE; 
11.  
12.  
13.  
14. /* 產生新節點 */ 
15. LINK_NODE *new_node(int data){ 
16.    LINK_NODE *node; 
17.    node=(LINK_NODE *) malloc(sizeof(LINK_NODE));/*<stdlib.h>*/ 
18.  
19.    // 記憶體不足 
20.    if(node == NULL){ return NULL;} 
21.  
22.    node->data=data;   
23.    node->link=NULL;      
24.    return node; 
25. } 
26.  
27.  
28. /* 加入新的資料於最後 */ 
29. LINK_NODE *push_node(LINK_NODE *list, int data){ 
30.    /*產生新節點*/ 
31.    LINK_NODE *node=new_node(data);   
32.  
33.    // 加入第一個新節點 
34.    if(list==NULL){     
35.        list=node; 
36.    }else{ 
37.        LINK_NODE *p=list;   
38.        // 取得最後一個節點 
39.        while(p->link!=NULL){p=p->link;} 
40.        p->link=node; 
41.    }    
42.    return list; 
43. } 
44.  
45.  
46. /* 排序插入新節點 */ 
47. LINK_NODE *sort_insert(LINK_NODE *list,int data){ 
48.    // 加入第一筆資料 
49.  
50.    // 產生新節點 
51.    LINK_NODE *node=new_node(data);     
52.    if(list==NULL){ list=node; return list; }   
53.  
54.    // 尋找大於資料(data)的位址 
55.    LINK_NODE *r=list,*q=list;     
56.    while(r!=NULL && r->data<data){ q=r; r=r->link; } 
57.  
58.    if(r==list){ // 首節點 
59.        node->link=list; list=node;  
60.    }else{ // 加入新節點於中間 
61.        node->link=q->link;  
62.        q->link=node;  
63.    }     
64.    return list;  
65. } 
66.  
67.  
68. /* 計算串列長度 */ 
69. int get_length(LINK_NODE *list){ 
70.    LINK_NODE *p=list; 
71.    int count=0;   
72.    while(p!=NULL){     
73.        count++;   
74.        p=p->link;   
75.    } 
76.  
77.    return count; 
78. } 
79.  
80.  
81. /* 搜尋資料(data)的節點位子 */ 
82. LINK_NODE *search_node(LINK_NODE *list, int data){ 
83.    LINK_NODE *p=list;   
84.    while(p!=NULL && p->data!=data){ p=p->link; } 
85.    return p ; 
86. } 
87.  
88.  
89. /* 印出所有串列的所有資料 */ 
90. int display(LINK_NODE *list){ 
91.    LINK_NODE *p=list; 
92.    while(p!=NULL){  
93.        printf("%d\n",p->data);/*<stdio.h>*/ 
94.        p=p->link;   
95.    } 
96.    return 1; 
97. } 
98.  
99.  
100.  
101.  
102. /*主程式*/ 
103. int main(){ 
104.    LINK_NODE *list=NULL; 
105.  
106.    list=sort_insert(list,4); 
107.    list=sort_insert(list,2); 
108.    list=sort_insert(list,7); 
109.    list=sort_insert(list,9); 
110.    list=sort_insert(list,14); 
111.    display(list); 
112.  
113.    printf("--------------------------\n"); 
114.  
115.    list=push_node(list,4); 
116.    list=push_node(list,2); 
117.    list=push_node(list,7); 
118.    list=push_node(list,9); 
119.    list=push_node(list,14); 
120.    display(list); 
121.  
122.    _getch();   
123.    return 0; 
124. } 

/* link list (連結串列) */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

/* 定義結構型態 */
typedef struct link_node{
    int data;
    struct link_node *link;
} LINK_NODE;



/* 產生新節點 */
LINK_NODE *new_node(int data){
    LINK_NODE *node;
    node=(LINK_NODE *) malloc(sizeof(LINK_NODE));/*<stdlib.h>*/
    
    // 記憶體不足
    if(node == NULL){ return NULL;}
    
    node->data=data;  
    node->link=NULL;     
    return node;
}


/* 加入新的資料於最後 */
LINK_NODE *push_node(LINK_NODE *list, int data){
    /*產生新節點*/
    LINK_NODE *node=new_node(data);  

    // 加入第一個新節點
    if(list==NULL){    
        list=node;
    }else{
        LINK_NODE *p=list;  
        // 取得最後一個節點
        while(p->link!=NULL){p=p->link;}
        p->link=node;
    }   
    return list;
}


/* 排序插入新節點 */
LINK_NODE *sort_insert(LINK_NODE *list,int data){
    // 加入第一筆資料
    
    // 產生新節點
    LINK_NODE *node=new_node(data);    
    if(list==NULL){ list=node; return list; }  

    // 尋找大於資料(data)的位址
    LINK_NODE *r=list,*q=list;    
    while(r!=NULL && r->data<data){ q=r; r=r->link; }

    if(r==list){ // 首節點
        node->link=list; list=node; 
    }else{ // 加入新節點於中間
        node->link=q->link; 
        q->link=node; 
    }    
    return list; 
}


/* 計算串列長度 */
int get_length(LINK_NODE *list){
    LINK_NODE *p=list;
    int count=0;  
    while(p!=NULL){    
        count++;  
        p=p->link;  
    }
    
    return count;
}


/* 搜尋資料(data)的節點位子 */
LINK_NODE *search_node(LINK_NODE *list, int data){
    LINK_NODE *p=list;  
    while(p!=NULL && p->data!=data){ p=p->link; }
    return p ;
}


/* 印出所有串列的所有資料 */
int display(LINK_NODE *list){
    LINK_NODE *p=list;
    while(p!=NULL){ 
        printf("%d\n",p->data);/*<stdio.h>*/
        p=p->link;  
    }
    return 1;
}




/*主程式*/
int main(){
    LINK_NODE *list=NULL;
    
    list=sort_insert(list,4);
    list=sort_insert(list,2);
    list=sort_insert(list,7);
    list=sort_insert(list,9);
    list=sort_insert(list,14);
    display(list);
    
    printf("--------------------------\n");
    
    list=push_node(list,4);
    list=push_node(list,2);
    list=push_node(list,7);
    list=push_node(list,9);
    list=push_node(list,14);
    display(list);
    
    _getch();  
    return 0;
}