C语言的双向循环链表

作者: 付凯强 | 来源:发表于2023-01-26 23:33 被阅读0次

C++实现双向循环链表
双向链表&双向循环链表
C语言的双向循环链表
0x05双向循环链表
双向链表
C++语言实现双向链表
C语言实现双向循环链表
链表
线性表--链式存储结构--双向链表
数据结构与算法之数组与链表

SingleLinkedList.h

//
// Created by fukaiqiang on 2023/1/24.
//

#ifndef SINGLELINKEDLIST_SINGLELINKEDLIST_H
#define SINGLELINKEDLIST_SINGLELINKEDLIST_H

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

typedef int SingleListNodeData;
typedef struct SingleListNode {
    int data;
    struct SingleListNode* next;
    struct SingleListNode* prev;
    int isHead;
} SListNode;

SListNode* init();
void pushFront(SListNode* head,SingleListNodeData data);
void pushBack(SListNode* head,SingleListNodeData data);
void delete(SListNode* head,SingleListNodeData data);
void destroySingleList(SListNode* head);
void print(SListNode* head);
SListNode* find(SListNode* head,SingleListNodeData data);
int lenSListNode(SListNode* head);
bool empty(SListNode* head);
SListNode* new(SingleListNodeData data);
SListNode* modify(SListNode* target,SingleListNodeData data);
void insertBefore(SListNode* target,SingleListNodeData data);
void insertAfter(SListNode* target,SingleListNodeData data);
void printReverse(SListNode *head);
#endif //SINGLELINKEDLIST_SINGLELINKEDLIST_H

SingleLinkedList.c

//
// Created by fukaiqiang on 2023/1/24.
//
#include "SingleLinkedList.h"

SListNode *init() {
    SListNode *initNode = malloc(sizeof(SListNode));
    if (initNode == NULL) {
        perror("malloc initNode failed");
        exit(-1);
    }
    initNode->next = initNode;
    initNode->prev = initNode;
    initNode->isHead = 1;
    return initNode;
}

void pushFront(SListNode *head, SingleListNodeData data) {
    if (head == NULL) {
        perror("pushFront head is null.");
        exit(-1);
    }
    SListNode* newSListNode = new(data);
    SListNode* nextSListNode = head->next;

    head->next = newSListNode;
    newSListNode->prev = head;
    newSListNode->next = nextSListNode;
    nextSListNode->prev = newSListNode;
}

void pushBack(SListNode *head, SingleListNodeData data) {
    if (head == NULL) {
        perror("pushBack head is null.");
        exit(-1);
    }
    SListNode *newSListNode = new(data);
    SListNode *tailSListNode = head->prev;

    tailSListNode->next = newSListNode;
    newSListNode->prev = tailSListNode;
    newSListNode->next = head;
    head->prev = newSListNode;
}

void delete(SListNode *head, SingleListNodeData data) {
    if (head == NULL) {
        perror("print head is null.");
        exit(-1);
    }
    while (head->next) {
        head = head->next;
        if (head->data == data) {
            head->prev->next = head->next;
            head->next->prev = head->prev;
            free(head);
            return;
        }
    }
}

void destroySingleList(SListNode *head) {
    if (head == NULL) {
        perror("destroySingleList head is null.");
        exit(-1);
    }
    SListNode* cur = head->next;
    while (cur!=head) {
        SListNode *nextSListNode = cur->next;
        free(cur);
        cur = NULL;
        cur = nextSListNode;
    }
    free(head);
    head = NULL;
}

void print(SListNode *head) {
    if (head == NULL) {
        perror("print head is null.");
        exit(-1);
    }
    printf("SingleLinkedList element: \n");
    SListNode* nextSListNode = head->next;
    while (nextSListNode!=head) {
        printf("%d ", nextSListNode->data);
        nextSListNode = nextSListNode->next;
    }
    printf("\n");
}

void printReverse(SListNode *head) {
    if (head == NULL) {
        perror("print head is null.");
        exit(-1);
    }
    printf("SingleLinkedList reverse element: \n");
    printf("%d ", head->data);
    SListNode* prevSListNode = head->prev;
    while (prevSListNode!=head) {
        if (!prevSListNode->isHead){
            printf("%d ", prevSListNode->data);
        }
        prevSListNode = prevSListNode->prev;
    }
    printf("\n");
}

SListNode *find(SListNode *head, SingleListNodeData data) {
    if (head == NULL) {
        perror("find head is null.");
        exit(-1);
    }
    SListNode* nextSListNode = head->next;
    while (nextSListNode!=head) {
        if (nextSListNode->data == data) {
            return nextSListNode;
        }
        nextSListNode = nextSListNode->next;
    }
    return NULL;
}

SListNode* modify(SListNode* target,SingleListNodeData data) {
    if (target == NULL) {
        perror("modify head is null.");
        exit(-1);
    }
    target->data = data;
    return target;
}

void insertBefore(SListNode* target,SingleListNodeData data){
    if (target == NULL) {
        perror("insertBefore target is null.");
        exit(-1);
    }
    SListNode* prevSListNode = target->prev;
    SListNode* newSListNode = new(data);

    prevSListNode->next = newSListNode;
    newSListNode->prev = prevSListNode;
    newSListNode->next = target;
    target->prev = newSListNode;
}
void insertAfter(SListNode* target,SingleListNodeData data){
    if (target == NULL) {
        perror("insertAfter target is null.");
        exit(-1);
    }
    SListNode* nextSListNode = target->next;
    SListNode* newSListNode = new(data);
    target->next = newSListNode;
    newSListNode->prev = target;
    newSListNode->next = nextSListNode;
    nextSListNode->prev = newSListNode;
}

int lenSListNode(SListNode *head) {
    int size = 0;
    SListNode* nextSListNode = head->next;
    while (nextSListNode!=head) {
        size++;
        nextSListNode = nextSListNode->next;
    }
    return size;
}

bool empty(SListNode *head) {
    return lenSListNode(head) == 0;
}

SListNode *new(SingleListNodeData data) {
    SListNode *newSListNode = malloc(sizeof(SListNode));
    if (newSListNode == NULL) {
        perror("malloc newSListNode failed");
        exit(-1);
    }
    newSListNode->data = data;
    newSListNode->next = NULL;
    newSListNode->isHead = 0;
    return newSListNode;
}

main.c

#include "SingleLinkedList.h"

int main() {
    SListNode *initNode = init();
    for (int i = 10; i < 20; i++) {
        pushBack(initNode, i);
    }
    for (int i = 9; i > 0; i--) {
        pushFront(initNode, i);
    }
    SListNode *printReverseNode = find(initNode, 15);
    print(initNode);
    printReverse(printReverseNode);
    printf("size = %d\n", lenSListNode(initNode));
    delete(initNode,1);
    delete(initNode,2);
    delete(initNode,10);
    delete(initNode,19);
    printf("delete 1 2 10 19\n");
    print(initNode);
    printf("size = %d\n",lenSListNode(initNode));
    printf("empty = %d\n",empty(initNode));
    SListNode* findNode = find(initNode,18);
    if (findNode == NULL) {
        perror("findNode is null.");
        exit(-1);
    }
    printf("findNode data = %d\n",findNode->data);
    SListNode* modifyNode = modify(findNode,20);
    if (modifyNode == NULL) {
        perror("modifyNode is null.");
        exit(-1);
    }
    printf("modifyNode data = %d\n",modifyNode->data);
    printf("after modifyNode list:\n");
    print(initNode);

    insertBefore(modifyNode,19);
    printf("after insertBefore list:\n");
    print(initNode);

    insertAfter(modifyNode,21);
    printf("after insertAfter list:\n");
    print(initNode);

    destroySingleList(initNode);
    return 0;
}

result

/Users/fukaiqiang/CLionProjects/SingleLinkedList/cmake-build-debug/SingleLinkedList
SingleLinkedList element: 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
SingleLinkedList reverse element: 
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 19 18 17 16 
size = 19
delete 1 2 10 19
SingleLinkedList element: 
3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 
size = 15
empty = 0
findNode data = 18
modifyNode data = 20
after modifyNode list:
SingleLinkedList element: 
3 4 5 6 7 8 9 11 12 13 14 15 16 17 20 
after insertBefore list:
SingleLinkedList element: 
3 4 5 6 7 8 9 11 12 13 14 15 16 17 19 20 
after insertAfter list:
SingleLinkedList element: 
3 4 5 6 7 8 9 11 12 13 14 15 16 17 19 20 21 

Process finished with exit code 0