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

使用C语言实现单链表

  • 单链表
    • 头插法
    • 尾插法
  • C语言 实现

单链表

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

头插法

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

  1. 假设链表中已经有一个节点:
    数据结构复习3: 链表(C语言实现)_第1张图片
  2. 生成一个新的节点
    新节点的插入分为两步:
    1. 将新节点的next指向head的next
    2. 将head的next指向新节点
      注意!操作顺序不要错!
      数据结构复习3: 链表(C语言实现)_第2张图片
  3. 插入完成
    数据结构复习3: 链表(C语言实现)_第3张图片

尾插法

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

  1. 假设当前有一个节点存在:
    数据结构复习3: 链表(C语言实现)_第4张图片
  2. 创建一个新节点:
    1. 首先将新节点的next指向NULL
    2. 接下来将前一个节点的next指向新节点
      数据结构复习3: 链表(C语言实现)_第5张图片
  3. 插入完成数据结构复习3: 链表(C语言实现)_第6张图片

C语言 实现

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

#include 
#include 
#include 

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);
                    break;
                }
            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;
    
}

你可能感兴趣的