linear list 线性表的 链式存储方式 C语言实现

本文内容

1.单向链表

  • 各类操作复杂度分析
  • 各类操作的代码实现
  • 链表逆序的解决思路->头插法

2.双向链表

  • 各类操作的代码实现
  • 注意!插入、删除方法实现的特殊处理逻辑

-------------------------------------------------------------------------------------------------------------

单向链表

基于链式存储方式实现线性表 查询、插入、删除等操作的时间复杂度分析

  • 按位查找、按值查找、求单链表长度时间复杂度均为O(n)
设计链表的实现,在链表类中实现这些功能:
get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

题目作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetb...
题目来源:力扣(LeetCode)
题解作者:WildDuck
基于链式存储方式实现线性表的代码实现

//有头结点!有头节点!有头节点!
//链表中元素的插入为亮点设计,不需要获取待插入位置前一个元素的指针即可实现
//以下代码在均在Leetcode中可执行的,带有头结点的单向链表结构

#define Elemtype int
struct MyLinkedList
{
    Elemtype val;
    struct MyLinkedList* next;
};
typedef struct MyLinkedList MyLinkedList;
//Leetcode中服务器存储的程序主体结构直接使用了MyLinkedList 因此需要再次重命名保证子函数可以正确执行

/** Initialize your data structure here. */
struct MyLinkedList* myLinkedListCreate()
{
    struct MyLinkedList* head_pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
    if (head_pointer != NULL)
    {
        head_pointer->val = 0;//头结点值用于存储链表中元素个数!
        head_pointer->next = NULL;
    }
    return head_pointer;
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
//按结点下标 get
int myLinkedListGet(struct MyLinkedList* obj, int index)
{
    if (index >= obj->val || index < 0)
    {
        return -1;
    }
    else
    {
        struct MyLinkedList* temp_head = obj;
        //因为有头结点,所以多走一步
        for (int i = 0; i <= index; i++)
        {
            temp_head = temp_head->next;
        }
        return temp_head->val;
    }
}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
//附单向链表的头插法经常用于解决链表逆置问题
void myLinkedListAddAtHead(struct MyLinkedList* obj, int val)
{
    struct MyLinkedList* pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
    if (pointer != NULL)
    {
        pointer->val = val;
        pointer->next = NULL;
    }
    struct MyLinkedList* temp_head = obj->next;
    obj->next = pointer;
    pointer->next = temp_head;
    obj->val = obj->val + 1;
}

/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(struct MyLinkedList* obj, int val)
{
    struct MyLinkedList* pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
    if (pointer != NULL)
    {
        pointer->val = val;
        pointer->next = NULL;
    }

    struct MyLinkedList* temp_head = obj;
    while (temp_head->next != NULL)
    {
        temp_head = temp_head->next;
    }
    temp_head->next = pointer;
    obj->val = obj->val + 1;

}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
//链表中元素的插入为亮点设计,不需要获取待插入位置前一个元素的指针即可实现
void myLinkedListAddAtIndex(struct MyLinkedList* obj, int index, int val)
{
    if (index <= 0)
    {
        myLinkedListAddAtHead(obj, val);
    }

    else if (index > 0 && index < obj->val)
    {
        struct MyLinkedList* temp_head = obj;
        for (int i = 0; i <= index; i++)
        {
            temp_head = temp_head->next;
        }

        struct MyLinkedList* pointer = (struct MyLinkedList*)malloc(sizeof(struct MyLinkedList));
        pointer->val = temp_head->val;
        pointer->next = temp_head->next;
        temp_head->val = val;
        temp_head->next = pointer;
        obj->val = obj->val+1;
    }

    else if (index == obj->val)
    {
        myLinkedListAddAtTail(obj, val);
    }
}

/** Delete the index-th node in the linked list, if the index is valid. */
void myLinkedListDeleteAtIndex(struct MyLinkedList* obj, int index)
{
    //按下标删除,index不可能大于元素个数
    if (index < obj->val && index >= 0)
    {
        struct MyLinkedList* temp_head = obj;
        struct MyLinkedList* temp_next = NULL;
        //找到index之前的一个元素
        for (int i = 0; i < index; i++)
        {
            temp_head = temp_head->next;
        }
        temp_next = temp_head->next->next;

        if (temp_head->next != NULL) free(temp_head->next);
        temp_head->next = temp_next;
        obj->val = obj->val-1;
    }
}

void myLinkedListFree(struct MyLinkedList* obj)
{
    struct MyLinkedList* temp_head = obj;
    struct MyLinkedList* temp_free = NULL;

    while (temp_head->next!=NULL)
    {
        temp_free = temp_head;
        temp_head = temp_head->next;
        free(temp_free);
    }

}

image.png

附经典问题链表逆置——头插法处理链表逆置问题:

注意要点和原理
image.png

//迭代形式处理问题
struct ListNode* AddAtHead(struct ListNode* source,struct ListNode* new_head)
{
    struct ListNode* pointer = new_head->next;
    new_head->next = source;
    source->next = pointer;
    return new_head;
}

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* new_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    //此为虚假头,最后需要被释放、移动指针再返回
    new_head->next = NULL;
    struct ListNode* temp_head = head;
    struct ListNode* temp_next = NULL;
    while (temp_head != NULL)
    {
        temp_next = temp_head->next;
        new_head = AddAtHead(temp_head,new_head);
        temp_head = temp_next;
    }
    temp_head = new_head;
    head = new_head->next;
    free(temp_head);
    return head;
}

image.png

-------------------------------------------------------------------------------------------------------------

双向链表

双向链表的代码实现

#define Elemtype int
struct MyLinkedList
{
    Elemtype data;
    struct MyLinkedList* next;
    struct MyLinkedList* prev;
};

typedef struct MyLinkedList MyLinkedList;
/** Initialize your data structure here. */

MyLinkedList* myLinkedListCreate() 
{
    MyLinkedList* new_head = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    //初始化的头结点用于存储链表中的元素个数
    if(new_head != NULL)
    {
        new_head->data = 0;
        new_head->next = NULL;
        new_head->prev = NULL;
        return new_head;
    }
    else 
    {
        return NULL;
    }
}

/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
//按下标搜索,所以index不可能超过头节点保存的链表元素个数
int myLinkedListGet(MyLinkedList* obj, int index) 
{
    if(index >= obj->data || index < 0)
    {
        return -1;
    }
    else 
    {
        MyLinkedList* temp_head = obj->next;
        for(int i=0;i != index;i++)
        {
            temp_head = temp_head->next;
        }
        return temp_head->data;
    }

}

/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
//双链表的插入操作需要特殊处理
void myLinkedListAddAtHead(MyLinkedList* obj, int val) 
{
    MyLinkedList* temp_head = obj;
    MyLinkedList* save_next = obj->next;
    
    MyLinkedList* new_elem = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    new_elem->data = val;
    new_elem->next = NULL;
    new_elem->prev = NULL;
    //当链表刚被初始化,头结点 next_pointer 直接指向了NULL 需要特殊处理
    if(temp_head->next == NULL)
    {
        temp_head -> next = new_elem;
        new_elem -> prev = temp_head;
        new_elem -> next = save_next;
    }
    //当链表内除头节点外至少含有一个元素
    else
    {
        MyLinkedList* save_prev = obj->next->prev;//就是头结点自己
        temp_head->next = new_elem;
        new_elem -> prev = temp_head;
        new_elem -> next = save_next;
        save_next -> prev = new_elem;
    }
    obj -> data = obj -> data +1;//头结点记录元素个数+1
}

/** Append a node of value val to the last element of the linked list. */
void myLinkedListAddAtTail(MyLinkedList* obj, int val) 
{
    MyLinkedList* temp_head = obj;
    MyLinkedList* new_elem = (MyLinkedList*)malloc(sizeof(MyLinkedList));
    new_elem->data = val;
    new_elem->next = NULL;
    new_elem->prev = NULL;
    
    //先找到tail结点(NULL之前的一个)
    while(temp_head -> next != NULL)
    {
        temp_head = temp_head -> next;
    }
    
    MyLinkedList* save_next = temp_head->next;
    temp_head -> next = new_elem;
    new_elem -> prev = temp_head;
    new_elem -> next = save_next;
    
    obj->data = obj -> data +1;
    
}

/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val)
{
    if(index == obj->data)
    {
        myLinkedListAddAtTail(obj,val);//拓展链表,直接调用尾插法
    }
    else if(index == 0)
    {
        myLinkedListAddAtHead(obj,val);
    }
    else if(index >0 && index < obj->data)
    {
        MyLinkedList* temp_head = obj;
        MyLinkedList* save_next = NULL;
        MyLinkedList* save_prev = NULL;
        MyLinkedList* new_elem = (MyLinkedList*)malloc(sizeof(MyLinkedList));
        new_elem->data = val;
        new_elem->next = NULL;
        new_elem->prev = NULL;

        for(int i=0;i<index;i++)//先找到待插入位置(即给定位置的前一个元素)
        {
            temp_head = temp_head -> next;
        }
        
        save_next = temp_head->next;
        save_prev = temp_head;
        temp_head->next = new_elem;
        new_elem->prev = temp_head;
        new_elem->next = save_next;
        save_next->prev = new_elem;
        obj -> data = obj->data + 1;
    }
}

/** Delete the index-th node in the linked list, if the index is valid. */
//按照元素下标index删除
void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index)
{
    MyLinkedList* temp_head = obj;
    MyLinkedList* save_next = NULL;
    MyLinkedList* free_elem = NULL;
    //需要特殊处理的为删除最后一个元素(因为NULL指针)
    if(index == (obj->data)-1)
    {
        for(int i=0;i<index;i++)
        {
            temp_head = temp_head->next;
        }
        free_elem = temp_head -> next;
        save_next = temp_head -> next -> next;
        free(free_elem);
        temp_head ->next = save_next;
        obj->data = obj->data - 1;
    }
    else if(index < obj->data)
    {
        MyLinkedList* save_prev = NULL;
        for(int i=0;i<index;i++)
        {
            temp_head = temp_head->next;
        }
        free_elem = temp_head -> next;
        save_next = temp_head -> next -> next;
        save_prev = temp_head;
        
        free(free_elem);
        temp_head ->next = save_next;
        save_next -> prev = save_prev;
        obj->data = obj->data - 1;
    }
    
    
    
}

void myLinkedListFree(struct MyLinkedList* obj)
{
    struct MyLinkedList* temp_head = obj;
    struct MyLinkedList* temp_free = NULL;

    while (temp_head->next!=NULL)
    {
        temp_free = temp_head;
        temp_head = temp_head->next;
        free(temp_free);
    }

}

image.png
插入、删除方法实现的特殊处理逻辑
image.png
delete操作特殊处理删去最后的元素,原因同上

评论

暂无评论