c語言 雙向鏈表的基礎操作

c語言 雙向鏈表的基礎操作

//頭文件
#pragma once
 
typedef int DataType;
 
typedef struct LinkList
{
    DataType _data;
    struct LinkList* _next;
    struct LinkList* _prev;
}LinkList,*pLinkList;
 
void InitList(pLinkList pNode);
pLinkList _BuyNode(pLinkList& pNode,DataType x);
void PrintList(pLinkList pHead);
void PushBack(pLinkList& pHead,DataType x);
void PopBack(pLinkList& pHead);
void PushFront(pLinkList& pHead,DataType x);
void PopFront(pLinkList& pHead);
pLinkList Find(pLinkList pHead, DataType x);
void Insert(pLinkList pos,DataType x);
void Erase(pLinkList& pHead, pLinkList pos);
void Reverse(pLinkList& pHead);
void DestroyList(pLinkList& pHead);
 
//函數文件
#include<stdio.h>
#include<assert.h>
#include"LinkList.h"
#include<malloc.h>
 
//初始化
void InitList(pLinkList pNode)
{
    assert(pNode);
    if (pNode->_next == NULL)
    {
        pNode->_prev = NULL;
    }
}
//創建節點
pLinkList _BuyNode(pLinkList& pNode, DataType x)
{
    pNode = (pLinkList)malloc(sizeof(LinkList));
    pNode->_data = x;
    pNode->_next = NULL;
    pNode->_prev = NULL;
    return pNode;
}
//遍歷輸出鏈表數據域
void PrintList(pLinkList pHead)
{
    pLinkList head = pHead;
    if(pHead == NULL)
    {
        printf("鏈表為空!\n");
        return;
    }
    while (head)
    {
        printf("%d ",head->_data);
        head = head->_next;
    }
    printf("\n");
}
//尾插
void PushBack(pLinkList& pHead, DataType x)
{
    pLinkList head = pHead;
    if (head == NULL)
    {
        _BuyNode(pHead, x);
        return;
    }
    while (head->_next)
    {
        head = head->_next;
    }
    head->_next = _BuyNode(head->_next,x);
    head->_next->_prev = head;
}
//尾刪
void PopBack(pLinkList& pHead)
{
    pLinkList head = pHead;
    pLinkList tmp = NULL;
    if (pHead == NULL)
    {
        printf("鏈表已空！\n");
        return;
    }
    if (head->_next == NULL)
    {
        free(head);
        pHead = NULL;
        return;
    }
    while (head->_next)
    {
        head = head->_next;
    }
    tmp = head->_prev;
    tmp->_next = NULL;
    free(head);
}
//頭插
void PushFront(pLinkList& pHead, DataType x)
{
    pLinkList head = pHead;
    pLinkList tmp = pHead;
    if (pHead == NULL)
    {
        _BuyNode(pHead, x);
        return;
    }
    pHead=_BuyNode(head->_prev, x);
    pHead->_next = tmp;
}
//頭刪
void PopFront(pLinkList& pHead)
{
    pLinkList tmp = pHead;
    if (pHead == NULL)
    {
        printf("鏈表已空！\n");
        return;
    }
    pHead = pHead->_next;
    if (pHead)
    {
        pHead->_prev = NULL;
    }
    free(tmp);
}
//查找
pLinkList Find(pLinkList pHead, DataType x)
{
    pLinkList head = pHead;
    assert(pHead);
    while (head)
    {
        if (head->_data == x)
            return head;
        head = head->_next;
    }
    return NULL;
}
//中插_之後
void Insert(pLinkList pos, DataType x)
{
    pLinkList tmp = pos->_next;
     
    assert(pos);
    _BuyNode(pos->_next, x);
    pos->_next->_prev = pos;
    pos->_next->_next = tmp;
}
//中刪
void Erase(pLinkList& pHead, pLinkList pos)
{
    pLinkList tmp = pos;
    assert(pos);
    if (pos->_next == NULL)
    {
        pos->_prev->_next = NULL;
        free(tmp);
        return;
    }
    if (pos==pHead)
    {
        pHead = pHead->_next;
        pHead->_prev = NULL;
        free(pos);
        return;
    }
    tmp->_prev->_next = tmp->_next;
    tmp->_next->_prev = tmp->_prev;
    free(pos);
}
//逆置
void Reverse(pLinkList& pHead)
{
    pLinkList head = pHead;
    pLinkList tmp = pHead;
    if (pHead == NULL&&pHead->_next == NULL)
        return;
    while (head)
    {
        tmp = head->_next;
        head->_next = head->_prev;
        head->_prev = tmp;
        if (head->_prev == NULL)
            pHead = head;
        head = tmp;  
    }
}
//銷毀
void DestroyList(pLinkList& pHead)
{
    while (pHead)
    {
        PopFront(pHead);
    }
}
 
//測試用例  主函數
 
#include"LinkList.h"
#include<stdio.h>
 
void test1()
{
    pLinkList pHead=NULL;
    //PushBack(pHead, 1);
    //PushBack(pHead, 2);
    //PushBack(pHead, 3);
 //   PushBack(pHead, 4);
    //PushBack(pHead, 5);
    //PrintList(pHead);
    //PopBack(pHead);
    //PopBack(pHead);
    //PopBack(pHead);
    //PopBack(pHead);
    //PopBack(pHead);
    //PopBack(pHead);
    PushFront(pHead, 1);
    PushFront(pHead, 2);
    PushFront(pHead, 3);
    PushFront(pHead, 4);
    PushFront(pHead, 5);
    PrintList(pHead);
    //PopFront(pHead);
    //PopFront(pHead);
    //PopFront(pHead);
    //PopFront(pHead);
    //PopFront(pHead);
    //PopFront(pHead);
    //printf("%d\n",Find(pHead, 6));
    Insert(Find(pHead, 1), 6);
    Erase(pHead,Find(pHead,2));
    PrintList(pHead);
 
    Reverse(pHead);
    PrintList(pHead);
    DestroyList(pHead);
    PrintList(pHead);
}
 
int main()
{
    test1();
    return 0;
}