連結清單學習筆記

連結清單是由若幹個節點構成的，且連結清單在記憶體中的存儲位置是不連續的，連結清單的兩個節點之間一般通過一個指針來從一個結點指向另一個結點。

C語言實作不帶頭結點的單向連結清單（頭插法）

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int             data;
    struct node     *next;
}node_t;

int search_node(node_t *head, int x);
void insert(node_t *head, int position, int x);
void delete_node(node_t *head,int x);

int main(int argc, char argv)
{
    node_t      *head = NULL;
    node_t      *node = NULL;
    int         i;

    for(i=0; i<5; i++)
    {
        node = (node_t *)malloc(sizeof(node_t));
        if(node == NULL)
        {
            printf("malloc failure!\n");
            return -1;
        }
        else
        {
            node -> data = i;
            node -> next = NULL;

            if(NULL == head)
            {
                head = node;
                printf("add node[%d]:node data =%d\n", i, i);
            }
            else
            {
                printf("add node[%d]:node data = %d\n", i, i);
                node -> next = head; //頭插
                head = node;
            }
        }
     }
     
    travel_node(head);
    search_node(head, 2);
    insert(head,5,11);
    delete_node(head,3);
    travel_node(head);
    destroy_node(head);

    return 0;
}

int travel_node(node_t *head)
{
    node_t *temp = head;
    if(NULL == head)
    {
        printf("travel node failure!\n");
        return -1;
    }
     while(temp != NULL)
    {
        if(temp -> next == NULL)
        {
            printf("node data = %d\n", temp->data);
            printf("travel node finish!\n");
            return 0;
        }
        else
        {
            printf("node data = %d\n", temp->data);
            temp = temp->next;
        }
    }

    return 0;
}

/* 查找元素 */
int search_node(node_t *head, int x)
{
    int count = 0;
    node_t *p = head;
    while(p != NULL)
    {       
        if(p->data == x)
        {   
            count++;
        }   
        p = p -> next;
    }
    printf("count = %d\n", count);

    return 0;
}

/*插入元素*/
void insert(node_t *head, int position, int x)
{
    node_t *p = head;
    node_t *q = NULL;
    int         i;

    for(i=0; i<position-1;i++)      //找到要插入結點的位置的前一個結點
    {
        p = p->next;

    }

    q = (node_t *)malloc(sizeof(node_t));
    q->data = x;
    q->next = p->next;
    p->next = q;

}

/*删除資料域為x的元素*/
void delete_node(node_t *head,int x)
{
    node_t *p = head;
    node_t *pre = head;
    while(p != NULL)
    {
        if(p->data == x)
        {
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else
        {
            pre = p;
            p = p->next;

        }
    }
}

/*銷毀連結清單*/
int destroy_node(node_t *head)
{
    node_t *node = head;

    while(node != NULL)
    {
        head = head->next;
        free(node);
        node = head;
    }
    retur
           

2.不帶頭結點的單向連結清單（尾插法）

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
    int     data;
    struct  node *next;
}node_t;
void travel_list(node_t *head);
void destroy_node(node_t *head);
void delete_node(node_t *head, int x);
void insert_node(node_t *head, int position, int x);
void search_node(node_t *head, int x);

int main(int argc, char **argv)
{
    node_t  *head = NULL;
    node_t  *node = NULL;
    node_t  *tail = NULL;
    int         i;

    for(i = 0;i<5;i++)
    {
        node = (node_t *)malloc(sizeof(node_t));
        if(node == NULL)
        {
            printf("malloc failure!\n");
            return -1;
        }
        node->data = i;
        node->next = NULL;
        
        if(head == NULL)
        {
            head = node;
            tail = node;
            printf("add node data:%d\n",node->data);
        }
        else
        {
            tail->next = node;
            tail = node;
            printf("add node data:%d\n",node->data);

        }

    }
      travel_list(head);
    delete_node(head, 2);
    printf("\n");
    travel_list(head);
    insert_node(head,2,8);
    printf("\n");
    travel_list(head);
    destroy_node(head);

    return 0;
}
void travel_list(node_t *head)
{
    node_t *p = head;
    while(p !=  NULL)
    {
        printf("node data: %d\n",p->data);
        p = p->next;
    }

    return ;
}

/* 删除資料域為x的結點 */
void delete_node(node_t *head, int x)
{
    node_t *p = head;
    node_t *pre = head;

    while(p != NULL)
    {
        if(p->data == x)
        {
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else
        {
            pre = p;
            p = p->next;
        }
        }
        
    return ;
}
void destroy_node(node_t *head)
{
    node_t *p = head;
    while(p != NULL)
    {
        free(p);
        p=p->next;
    }
    return ;
}

void insert_node(node_t *head, int position, int x)
{
    node_t  *p = head;
    node_t  *new_node = NULL;
    int      i;

    new_node = (node_t *)malloc(sizeof(node_t));

    for(i=0; i<position-1; i++)
    {
        p = p->next;
    }

    new_node->data = x;
    new_node->next = p->next;
    p->next = new_node;

    return ;
    }