读书笔记: Link List

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct list_node *list_pointer;
typedef struct list_node{
    char *data;
    list_pointer link;
}list_node;

list_pointer create_list_pointer(char *data){
    list_pointer temp;
    temp = (list_pointer) malloc(sizeof(list_node));
    temp->data = data;
    return temp;
}

翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
//翻转单链表 O(length)
list_pointer invert(list_pointer lead){
    list_pointer trail,middle;
    middle = NULL;
    while(lead){
        trail = middle;
        middle = lead;
        middle->link = trail;

        lead = lead->link;
    }
    return middle;
}

串联

1
2
3
4
5
6
7
8
//串联单链表  O(ptr1.length)
list_pointer concaenate(list_pointer ptr1,list_pointer ptr2){
    list_pointer temp;
    temp = ptr1;
    for(;ptr1->link;ptr1=ptr1->link);
    ptr1->link = ptr2;
    return temp;
}

Print

1
2
3
4
5
6
7
8
void print_list(list_pointer ptr){
    printf("The list:");
    while(ptr){
        printf("%s ",ptr->data);
        ptr=ptr->link;
    }
    printf("\n");
}

Test

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
int main (int argc, const char * argv[]){
    list_pointer a,b,c,d;
    a=create_list_pointer("test1");
    b=create_list_pointer("test2");
    a->link = b;
    b->link = NULL;
    
    c=create_list_pointer("c");
    d=create_list_pointer("d");
    c->link=d;
    
    printf("Init list: \n");
    printf("List 1: ");
    print_list(a);
    printf("List 2: ");
    print_list(c);
    
    printf("Invert the list: \n");
    list_pointer invert_list;
    invert_list= invert(a);
    print_list(invert_list);
    
    printf("comebine two list: \n");
    list_pointer combine_list;
    combine_list = concaenate(c, invert_list);
    print_list(combine_list);
}

循环链表

Insert

1
2
3
4
5
6
7
8
9
10
//在表前端插入节点
void insert_front(list_pointer *ptr,list_pointer node){
    if (!(*ptr)){
        *ptr = node;
        node->link = node;           //自循环
    } else {
        node->link = (*ptr)->link;
        (*ptr)->link = node;
    }
}

Length

1
2
3
4
5
6
7
8
9
10
11
12
13
//求循环链表长度
int length(list_pointer ptr){
    list_pointer temp;
    int count = 0;
    if(ptr){
        temp = ptr;
        do {
            count++;
            temp=temp->link;
        }while(temp != ptr);
    }
    return count;
}

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main (int argc, const char * argv[]){
    list_pointer c1,c2,c3;
    c1=create_list_pointer("c1");
    c2=create_list_pointer("c2");
    c3=create_list_pointer("c3");
    
    list_pointer c_ptr=NULL;  //关键的设NULL,不然下面判断ptr是否存在会是存在
    insert_front(&c_ptr,c1);
    insert_front(&c_ptr,c2);
    insert_front(&c_ptr,c3);
    
    printf("the circule list's lenght is: ");
    int c_length = length(c_ptr);
    printf("%d",c_length);
}