劍指offer之C語言實作連結清單（兩種方式）

1 問題

用C語言實作連結清單

2 代碼實作

#include <stdio.h>
#include <stdlib.h>
 
#define true 0
#define false -1
 
typedef struct Node
{
    int value;
    struct Node *next;
} List;
 
/**
 *初始化連結清單
 */
struct Node* init_list()
{
    struct Node *head = (struct Node*)malloc(sizeof(struct Node));
    if (head)
    {
        head->next = NULL;
        return head;
    }
    return NULL;
}
 
/*
 *建立節點
 */
struct Node* create_node(int value)
{
    struct Node *node = (struct Node*)malloc(sizeof(struct Node));
    if (node)
    {
        node->value = value;
        return node;
    }
    return NULL;
}
 
/*
 *第一種方法插入節點
 */
int insert_list(struct Node **head, List* node)
{
    if (*head == NULL || node == NULL)
    {
        printf("head or node is NULL");
        return false;
    }
    node->next = *head;
    *head = node;
    return true;
}
 
/*
 *第二種方法插入節點
 */
int insert_list1(struct Node *head, List* node)
{
    if (head == NULL || node == NULL)
    {
        printf("head or node is NULL");
        return false;
    }
    node->next = head->next;
    head->next = node;
    return true;
}
 
/*
 *第一種方法列印
 */
void print_list(List *head)
{
    if (head == NULL)
    {
        printf("head is NULL\n");
        return; 
    }
    while (head->next != NULL)
    {
        printf("value is %d\n", head->value);
        head = head->next;
    }
}
 
/*
 *第二種方法列印
 */
void print_list1(List *head)
{
    if (head == NULL)
    {
 
        printf("head is NULL\n");
        return; 
    }
    struct Node *p = head->next;
    while (p != NULL)
    {
        printf("value is %d\n", p->value);
        p = p->next;    
    }
 
 
}
 
/*
 *更具這個值能否能到節點
 */
struct Node* get_node(List *head, int value)
{
 
    if (head == NULL)
        return NULL;
    struct Node *p = head;
    while (p != NULL)
    {
        if (p->value == value)
        {
            return p;   
        }
        p = p->next;    
    }
    return NULL;    
}
 
/*
 *第一種方法删除節點
 */
int delete_node(struct Node **head, struct Node *node)
{
    if (*head == NULL)
        return false;
    if ((*head) == node)
    {
        *head = (*head)->next;
        return true;
    }
    struct Node *p = *head;
    while ((*head)->next != NULL)
    {   
        if ((*head)->next == node)
        {   
            (*head)->next =(*head)->next->next;
            *head = p;
            return true;
        }
        *head = (*head)->next;
    }
    *head = p;
    return false;
}
 
/*
 *第二種方法删除節點
 */
int delete_node1(struct Node *head, struct Node *node)
{
    if (head == NULL)
        return false;
    while (head->next != NULL)
    {
        if (head->next == node)
        {
            head->next = head->next->next;
            return true;
        }
        head = head->next;
    }
    return false;
}
 
/*
 *釋放連結清單
 */
int free_list(List *head)
{
    if (head == NULL)
        return false;
    struct Node *p = NULL;
    while(head != NULL)
    {
        p = head;
        head = head->next;  
        free(p);
    }
    return true;
}
 
int main()
{
    struct Node* head = NULL;
    struct Node* node1 = NULL, *node2 = NULL, *node3 = NULL;
    struct Node* node4 = NULL, *node5 = NULL, *node6 = NULL;
    head = init_list();
    if (!head)
    {
        printf("init head fail\n"); 
    }
    node1 = create_node(5);
    node2 = create_node(4);
    node3 = create_node(3);
    node4 = create_node(2);
    node5 = create_node(1);
    node6 = create_node(3);
 
    insert_list1(head, node1);
    insert_list1(head, node2);
    insert_list1(head, node3);
    insert_list1(head, node4);
    insert_list1(head, node5);
    insert_list1(head, node6);
    print_list1(head);
    printf("first print_list---------------\n");
    delete_node1(head, node1);
    print_list1(head);
    printf("second print_list--------------\n");
    free_list(head);
    head = NULL;
 
    head = init_list();
    if (!head)
    {
        printf("init head fail\n"); 
    }
    node1 = create_node(5);
    node2 = create_node(4);
    node3 = create_node(3);
    node4 = create_node(2);
    node5 = create_node(1);
    node6 = create_node(3);
    
    insert_list(&head, node1);
    insert_list(&head, node2);
    insert_list(&head, node3);
    insert_list(&head, node4);
    insert_list(&head, node5);
    insert_list(&head, node6);
    print_list(head);
    printf("third print_list---------------\n");
    delete_node(&head, node4);
    print_list(head);
    printf("four print_list---------------\n");
    struct Node *result = get_node(head, 4);
    if (result)
    {
        printf("list contain node and the value of node is %d\n", result->value);
    }
    else
    {
        printf("list do not contain the node\n");   
    }
    free_list(head);
    head = NULL;
    return 0;   
}      

3 運作結果

value is 3
value is 1
value is 2
value is 3
value is 4
value is 5
first print_list---------------
value is 3
value is 1
value is 2
value is 3
value is 4
second print_list--------------
value is 3
value is 1
value is 2
value is 3
value is 4
value is 5
third print_list---------------
value is 3
value is 1
value is 3
value is 4
value is 5
four print_list---------------
list contain node and the value of node is 4