欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

双向链表基本操作

程序员文章站 2022-03-15 19:55:56
...

1.DLinklist.h

#pragma once

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

//构建一个结构体,包含链表的数据,前一个指针及后一个指针
typedef char DLinkType;

typedef struct DLinkNode {
    DLinkType data;
    struct DLinkNode* next;
    struct DLinkNode* prev;
} DLinkNode;

void DLinkListInit(DLinkNode** head);//链表的初始化

DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value);//尾插

void DLinkListPopBack(DLinkNode* head);//尾删

void DLinkListPushFront(DLinkNode* head, DLinkType value);//头插

void DLinkListPopFront(DLinkNode* head);//头删

DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find);//查找

/**
* @brief 往指定位置之前插入一个元素
*/
void DLinkListInsert(DLinkNode* pos, DLinkType value);//前插

/**
* @brief 往指定位置之后插入一个元素
*/
void DLinkListInsertAfter(DLinkNode* pos, DLinkType value);//后插

void DLinkListErase(DLinkNode* head,DLinkNode* pos);//删除指定位置的元素


void DLinkListRemove(DLinkNode* head,DLinkType value); //删除指定值的元素


void DLinkListRemoveAll(DLinkNode* head,DLinkType value);//删除所有相同值得元素


size_t DLinkListSize(DLinkNode* head); //链表长度


int DLinkListEmpty(DLinkNode* head);//链表是否为空


void DLinkListDestroy(DLinkNode** head);//销毁链表

2.DLinklist.c

#include "dblinklist.h"

DLinkNode* CreateNode(DLinkType value){
    DLinkNode* new_node = (DLinkNode*)malloc(sizeof(DLinkNode));
    new_node->data = value;
    new_node->next = new_node;
    new_node->prev = new_node;
    return new_node;
}

void DestroyNode(DLinkNode* ptr){
    free(ptr);
}

void DLinkListInit(DLinkNode** head){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* cur = CreateNode('0');
    *head = cur;
}

DLinkNode* DLinkListPushBack(DLinkNode* head, DLinkType value){
    if(head == NULL){
        //非法输入
        return NULL;
    }
    DLinkNode* new_node = CreateNode(value);
    head->prev->next = new_node;
    new_node->prev = head->prev;
    head->prev = new_node;
    new_node->next = head;
    return new_node;
}

void DLinkListPopBack(DLinkNode* head){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_delete = head->prev;
    to_delete->prev->next = head;
    head->prev = to_delete->prev;
    DestroyNode(to_delete);
}

void DLinkListPushFront(DLinkNode* head, DLinkType value){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* new_node = CreateNode(value);
//    head->next = new_node;
//    new_node->prev = head;
//    head->prev = new_node->next;
//    new_node->next = head->prev;
    DLinkNode* new_node_prev = head;
    DLinkNode* new_node_next = head->next;
    new_node->prev = new_node_prev;
    new_node->next = new_node_next;
    new_node_prev->next = new_node;
    new_node_next->prev = new_node;
    return;
}


void DLinkListPopFront(DLinkNode* head){
    if(head ==NULL){
        //非法输入
        return;
    }
    DLinkNode* to_delete = head->next;
    head->next = to_delete->next;
    to_delete->next->prev = head;
    return;
}

DLinkNode* DLinkListFind(DLinkNode* head, DLinkType to_find){
    if(head ==NULL){
        //非法输入
        return NULL;
    }
    DLinkNode* cur = head->next;
    while(cur != head){
        if(cur->data == to_find){
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void DLinkListInsert(DLinkNode* pos, DLinkType value){
    if(pos == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_insert = CreateNode(value);
    to_insert->prev = pos->prev;
    pos->prev->next = to_insert;
    pos->prev = to_insert;
    to_insert->next = pos;
    return;
}

void DLinkListInsertAfter(DLinkNode* pos, DLinkType value){
    if(pos == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_insert = CreateNode(value);
    to_insert->next = pos->next;
    pos->next->prev = to_insert;
    pos->next = to_insert;
    to_insert->prev = pos;
    return;
}
void DLinkListErase(DLinkNode* head,DLinkNode* pos){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* pos_prev = pos->prev;
    DLinkNode* pos_next = pos->next;


    pos_prev->next = pos_next;
    pos_next->prev = pos_prev;


    DestroyNode(pos);
    return;
}


void DLinkListRemove(DLinkNode* head,DLinkType value){
    if(head ==NULL){
        //非法输入
        return;
    }
    DLinkNode* pos = DLinkListFind(head,value);
    if(pos!=NULL){
        DLinkListErase(head,pos);
    }
    return;
}


void DLinkListRemoveAll(DLinkNode* head,DLinkType value){
    if(head == NULL){
        //非法输入
        return;
    }
    while(1){
    DLinkNode* pos = DLinkListFind(head,value);
    if(pos!=NULL){
        DLinkListErase(head,pos);
        }else
            break;
    }
    return;
}


size_t DLinkListSize(DLinkNode* head){
    if(head == NULL){
        //非法输入
        return 0;
    }
    size_t count = 0;
    DLinkNode* cur = head->next;
    while(cur!=head){
        cur = cur->next;
        ++count;
    }
    return count;
}


int DLinkListEmpty(DLinkNode* head){
    if(head->next == head && head->prev == head){
        return 1;
    }
    return 0;
}


void DLinkListDestroy(DLinkNode** head){
    if(head == NULL){
        //非法输入
        return;
    }
    DLinkNode* to_destroy = (*head)->next;
    while(to_destroy!=(*head)){
        DLinkNode* cur = to_destroy;
        (*head)->next = to_destroy->next;
        to_destroy->next->prev = *head;
        DestroyNode(cur);
        to_destroy = to_destroy->next;
    }
    DestroyNode(*head);
    *head = NULL;
    return;
}