数据结构复习3: 链表(C语言实现)

单链表

链表，顾名思义，将数据向链子一样的窜起来。可以从中间提取数据，也可以从中间插入数据。当然，链表分为单向链表，双向链表，以及循环链表。今天我们来看看那单链表该如何实现。链表的插入方法分为两种一种为头插法，另一种是尾插法。下面我们来看一下这两种插入方法。

头插法

首先我们先来看一看头插法。其实我并不喜欢这个名称，这个名称乍一听上去根本不明白什么意思。头插法简单一点来说就是，每个新节点都在头节点后面插入，而不是尾节点后面插入。这就造就了，使用头插法之后，数据会被以逆序保存。插入方式如下所示:

1. 假设链表中已经有一个节点:
   
2. 生成一个新的节点
   新节点的插入分为两步:
   1. 将新节点的next指向head的next
   2. 将head的next指向新节点
      注意！操作顺序不要错！
      
3. 插入完成
   

尾插法

尾插法比起头插法，在理解上简单的多。简单的来说，就是在数据节点的后方插入。这不会出现数据逆序保存的情况。插入放下如下图所示:

1. 假设当前有一个节点存在：
   
2. 创建一个新节点:
   1. 首先将新节点的next指向NULL
   2. 接下来将前一个节点的next指向新节点
      
3. 插入完成

C语言 实现

//
//  Linked_list.c
//  Data_structure
//
//  Created by 真的木有鱼丸啊 on 2020/05/23.
//  Copyright © 2020 양송. All rights reserved.
//

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

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

void list_init(List* head)
{
    List *temp = head;
    temp->next = NULL;
    temp->data = -1;
}

void list_destory(List* head)
{
    free(head);
}

void insert_one_by_one(List* head,int num)//头插法
{
    if(head == NULL)
    {
        printf("List is NULL\n");
        assert(0);
    }
    else
    {
        List* temp = head;
        List* new_node = (List*)malloc(sizeof(List));
        
        new_node->data = num;
        new_node->next = temp->next;
        temp->next = new_node;
        
        
    }
}

void insert_element(List* head, int num)//尾插法
{
    if(head == NULL)
    {
        printf("List is NULL\n");
        assert(0);
    }
    else
    {
        List* temp = head;
        while(temp->next!=NULL)
        {
            temp = temp->next;
        }
        
        List* new_node = (List*)malloc(sizeof(List));
        new_node->data = num;
        new_node->next = NULL;
        temp->next = new_node;
    }
}
int delete_element(List* head, int num)
{
    if(head == NULL)
    {
        printf("List is NULL\n");
        assert(0);
    }
    else{
        List* slow = head;
        List* finder = head->next;//快指针
        while(finder != NULL)
        {
                if(finder->data == num)
                {
                    slow->next = finder->next;
                    free(finder);
                }
            slow = slow->next;
            finder = finder ->next;
        }
    }
    return 0;//没找到指定元素
}

int delete_same_element(List* head)
{
    if(head == NULL)
    {
        printf("List is NULL\n");
        assert(0);
    }
    else
    {
        List* slow = head->next;
        List* fast = slow->next;
        
        while(slow->next != NULL)
        {
            List* finder = fast;
            List* slower = slow;
            while(finder != NULL)
            {
                if(slow->data == finder->data)
                {
                    slower->next = finder->next;
                    free(finder);
                    break;
                }
                else
                {
                    finder = finder->next;
                    slower = slower->next;
                }
            }
            slow = slow->next;
            fast = fast->next;
        }
    }
    
    return 0;
}
void print_list(List* head)
{
    List* temp = head->next;//从第二个节点开始遍历
    while(temp!=NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}


int get_list_length(List *head)
{
    List *temp = head->next;
    int count = 0;
    while(temp!=NULL)
    {
        count++;
        temp = temp->next;
    }
    return count;
}
int main()
{
    List * l;
    l = (List*)malloc(sizeof(List));
    
    list_init(l);
    
    for(int i = 0; i < 5; i++)
    {
        insert_one_by_one(l,i);
    }
    print_list(l);
    
    delete_element(l, 0);
    
    print_list(l);
    printf("the size of list : %d \n", get_list_length(l));
    
    insert_one_by_one(l, 3);
    print_list(l);
    
    delete_same_element(l);
    print_list(l);
    
    for(int i = 0; i < 5; i++)
    {
        insert_element(l,i);
    }
    print_list(l);
    
    
    return 0;
    
}