双向带头循环链表的接口函数实现

学习内容：

1.双向链表的节点形式以及函数声明

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

typedef int DataType;
typedef struct ListNode
{
    int val;
    struct ListNode* next;
    struct ListNode* prev;
}LTNode;

void LTNInit(LTNode** phead);//初始化
void LNTDestroy(LTNode* phead);//销毁链表
void LTNPrint(LTNode* phead);//打印链表
void LTNPushBack(LTNode* phead, DataType x);//尾插
void LTNPushFront(LTNode* phead, DataType x);//头插
void LTNPopBack(LTNode* phead);//尾删
void LTNPopFront(LTNode* phead);//头删
LTNode* LTNFInd(LTNode* phead, DataType x);//查找
void LTNInsert(LTNode* pos, DataType x);//指定位置之前插入
void LTNInsertAfter(LTNode* pos, DataType x);//指定位置之后插入
void LTNERase(LTNode* pos);//指定位置删除
 

2.创建节点

代码如下：

LTNode* LTNBuyNode(DataType x)
{
    LTNode* node = (LTNode*)malloc(sizeof(LTNode));
    assert(node);
    node->val = x;
    node->next = node->prev = node;
    return node;
}

3.初始化链表

void LTNInit(LTNode** phead)//初始化,创建头结点
{
    *phead = LTNBuyNode(0);
}

4.打印链表

代码如下：

void LTNPrint(LTNode* phead)//打印链表
{
    assert(phead);
    LTNode* pcur = phead->next;
    while (pcur != phead)
    {
        printf("%d->", pcur->val);
        pcur = pcur->next;
    }
    printf("NULL");
    putchar('\n');
}

5.尾插

void LTNPushBack(LTNode* phead, DataType x)//尾插
{
    LTNode* newnode = LTNBuyNode(x);

    LTNode* tail = phead->prev;

    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
    tail->next = newnode;
}

6.头插

void LTNPushFront(LTNode* phead, DataType x)//头插
{
    assert(phead);
    LTNode* newnode = LTNBuyNode(x);
    newnode->next = phead->next;
    newnode->prev = phead;
    phead->next->prev = newnode;
    phead->next = newnode;
}

7.尾删

void LTNPopBack(LTNode* phead)//尾删
{
    assert(phead && phead->next != phead);
    LTNode* del = phead->prev;
    del->prev->next = phead;
    phead->prev = del->prev;
    free(del);
    del = NULL;
}

8.头删

void LTNPopFront(LTNode* phead)//头删
{
    assert(phead && phead->next != phead);
    LTNode* del = phead->next;
    del->next->prev = phead;
    phead->next = del->next;
    free(del);
    del = NULL;
}

9.查找

LTNode* LTNFInd(LTNode* phead, DataType x)//查找
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->val == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

10.指定位置之后插入

void LTNInsertAfter(LTNode* pos, DataType x)//指定位置之后插入
{
    assert(pos);
    LTNode* newnode = LTNBuyNode(x);
    newnode->prev = pos;
    newnode->next = pos->next;
    pos->next->prev = newnode;
    pos->next = newnode;
}
 

11.指定位置之前插入

void LTNInsert(LTNode* pos, DataType x)//指定位置之前插入
{
    assert(pos);
    LTNode* newnode = LTNBuyNode(x);
    newnode->prev = pos->prev;
    newnode->next = pos;
    pos->prev->next = newnode;
    pos->prev = newnode;
}

12.指定位置的删除

void LTNERase(LTNode* pos)//指定位置删除
{
    assert(pos);
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;

    free(pos);
    pos = NULL;
}

13.销毁

void LNTDestroy(LTNode* phead)//销毁链表
{
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
    phead = NULL;
}