C语言实现双向循环链表

头文件linklist.h

#ifndef LINKLIST_H
#define LINKLIST_H

// 为一个链表结点分配空间，返回指向结点的指针
#define NEW_NODE ((Node *)malloc(sizeof(Node)))

typedef int elem;

typedef struct node_s
{
   
    elem val;
    struct node_s *pre;
    struct node_s *next;
} Node;

typedef Node *Linklist;

/**
 * 根据传入的数组创建具有头结点的链表
 * 创建成功返回链表的头指针
 * 创建失败返回NULL
 */
Linklist create(elem array[], int arraySize);

/**
 * 头插法插入结点
 * 若成功，返回新结点的地址；若失败，返回NULL
 */
Node *headInsert(Linklist head, elem value);

/**
 * 尾插法插入结点
 * 若成功，返回新结点的地址；若失败，返回NULL
 */
Node *tailInsert(Linklist head, elem value);

/**
 * 删除下标为index的结点
 * 如果成功删除返回0，如果下标index越界，返回-1
 */
int deleteNode(Linklist head, int index);

/**
 * 删除所有值为key的结点
 * 返回删除的结点的数目
 */
int deleteKey(Linklist head, elem key);

/**
 * 将下标为index的结点的值设为value
 * 如果设置成功，返回0；如果下标越界，返回-1
 */
int setValue(Linklist head, int index, elem value);

/**
 * 查找第i个结点
 * 返回指向第i个结点的指针
 * 如果下标越界，返回NULL
 */
Node *find(Linklist head, int index);

/**
 * 查找所有值为key的节点
 * 返回找到的key结点的个数
 * 如果发生错误，返回-1
 * 并将参数nodes设置为指向Node*类型的数组的指针，这个数组存储所有指向值为key的结点的指针
 */
int findAllKey(Linklist head, elem key, Node ***nodes);

#endif // LINKLIST_H

源文件linklist.c

#include <stdlib.h>

#include "linklist.h"

Linklist create(elem array[], int arraySize)
{
   
    Linklist head, current;

    if (arraySize < 0)
    {
   
        return NULL;
    }
    current = head = NEW_NODE;
    for (int i = 0; i < arraySize; i++)
    {
   
        current->next = NEW_NODE;
        current->next->pre = current;
        current = current->next;
        current->val = array[i];
    }
    current->next = head;
    head->pre = current;
    return head;
}

Node *headInsert(Linklist head, elem value)
{
   
    Node *newNode = NEW_NODE;

    if (newNode == NULL)
    {
   
        return NULL;
    }
    newNode->val = value;
    newNode->next = head->next;
    newNode->next->pre = newNode;
    newNode->pre = head;
    head->next = newNode;
    return newNode;
}

Node *tailInsert(Linklist head, elem value)
{
   
    Node *newNode = NEW_NODE;

    if (newNode == NULL)
    {
   
        return NULL;
    }
    newNode->val = value;
    newNode->next = head;
    newNode->pre = head->pre;
    head->pre = newNode;
    newNode->pre->next = newNode;
    return newNode;
}

int deleteNode(Linklist head, int index)
{
   
    Node *target = find(head, index);
    if (target == NULL)
    {
   
        return -1;
    }
    target->pre->next = target->next;
    target->next->pre = target->pre;
    free(target);
    return 0;
}

int deleteKey(Linklist head, elem key)
{
   
    int count = 0;

    for (Node *current = head->next; current != head;)
    {
   
        if (current->val == key)
        {
   
            Node *target = current;

            current = current->next;
            target->pre->next = target->next;
            target->next->pre = target->pre;
            free(target);
            count++;
        }
        else
        {
   
            current = current->next;
        }
    }
    return count;
}

int setValue(Linklist head, int index, elem value)
{
   
    Node *target = find(head, index);
    if (target == NULL)
    {
   
        return -1;
    }
    target->val = value;
    return 0;
}

Node *find(Linklist head, int index)
{
   
    Node *current = head;

    if (index < 0)
    {
   
        return NULL;
    }
    for (int i = 0; i <= index; i++)
    {
   
        if (current->next == head)
        {
   
            return NULL;
        }
        current = current->next;
    }
    return current;
}

int findAllKey(Linklist head, elem key, Node ***nodes)
{
   
    int count = 0, size = 10;
    Node **tempNodes;

    *nodes = (Node **)malloc(sizeof(Node *) * 10);
    for (Node *current = head->next; current != head; current = current->next)
    {
   
        if (current->val == key)
        {
   
            (*nodes)[count] = current;
            count++;
            if (count == size)
            {
   
                size += 10;
                tempNodes = (Node **)realloc(*nodes, sizeof(Node *) * size);
                if (tempNodes == NULL)
                {
   
                    free(*nodes);
                    *nodes = NULL;
                    return -1;
                }
                *nodes = tempNodes;
            }
        }
    }
    if (count == 0)
    {
   
        free(*nodes);
        *nodes = NULL;
        return 0;
    }
    tempNodes = (Node **)realloc(*nodes, sizeof(Node *) * count);
    if (tempNodes == NULL)
    {
   
        free(*nodes);
        *nodes = NULL;
        return -1;
    }
    *nodes = tempNodes;
    return count;
}