基础数据结构_循环单链表

声明

#ifndef CLIST_H
#define CLIST_H
typedef int ElemType;
typedef struct CNode
{
    ElemType data;
    struct CNode* next;//指针域
}CNode, * PCNode;
//可执行操作
//初始化
void Init_clist(struct CNode* plist);
//头插
bool Push_Front(PCNode plist, int val);
//尾插
bool Push_Back(PCNode plist, int val);
//按位置插
bool Insert_Pos(PCNode plist, int pos, int val);
//头删
bool Pop_Front(PCNode plist);
//尾删
bool Pop_Back(PCNode plist);
//按位置删
bool Del_Pos(PCNode plist, int pos);
//按值删除
bool Del_Val(PCNode plist, int val);
//查找
struct CNode* Search(PCNode plist, int val);
//找值为val的节点前驱
struct CNode* Get_Prev(PCNode plist, int val);
//找值为val的节点后继
struct CNode* Get_Next(PCNode plist, int val);
//获取其有效节点的个数
int Get_Length(PCNode plist);
//清空
void Clear(PCNode plist);
//销毁1
void Destroy1(PCNode plist);
//销毁2
void Destroy2(PCNode plist);
//判空
bool IsEmpty(PCNode plist);
//打印
void Show(PCNode plist);
#endif

实现

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

struct CNode* Buynode()
{
    CNode* newnode = (CNode*)malloc(sizeof(CNode));
    if (NULL == newnode)
    {
        printf("memory error");
        exit(1);
    }
    return newnode;
}
//可执行操作
//初始化
void Init_clist(struct CNode* head)
{
    assert(head != NULL);
    head->next = head;
}
//查到ptr下一个
bool Insert_Next(CNode* ptr, int val)
{
    assert(ptr);
    CNode* pnewnode = Buynode();
    pnewnode->next = ptr->next;
    ptr -> next = pnewnode;
    pnewnode->data = val;
    return true;
}
//头插
bool Push_Front(PCNode head, int val)
{
    assert(head);
    return Insert_Next(head, val);
}
//尾插
bool Push_Back(PCNode head, int val)
{
    assert(head);
    CNode* p = head;
    while (p->next != head)
    {
        p = p->next;
    }
    return Insert_Next(p, val);
}
//按位置插
bool Insert_Pos(PCNode head, int pos, int val)
{
    assert(head);
    if (pos < 0)return false;
    CNode* pnode = head;
    while (pnode->next != head && pos--)
    {
        pnode = pnode->next;
    }
    if (pos != 0)
    {
        return false;
    }
    return Insert_Next(pnode, val);
}
//删除下一个
bool Del_Next(CNode* ptr)
{
    assert(ptr);
    CNode* p = ptr->next;
    ptr->next = p->next;
    free(p);
    return true;
}
//头删
bool Pop_Front(PCNode head)
{
    assert(head);
    if (head == head->next)//只有头结点不行
    {
        return false;
    }
    return Del_Next(head);
}
//尾删
bool Pop_Back(PCNode head)
{
    assert(head);
    CNode* p = head;
    if (head == p->next)//只有头结点不行
    {
        return false;
    }
    while (p->next->next != head)
    {
        p = p->next;
    }
    return Del_Next(p);
}
//按位置删
bool Del_Pos(PCNode head, int pos)
{
    assert(head);
    if (pos < 0)return false;
    CNode* p = head;
    if (NULL == p->next)return false;
    int count = pos - 1;
    while (p->next != head && count--)
    {
        p = p->next;
    }
    if (count != -1)
    {
        return false;
    }
    return Del_Next(p);
}
//按值删除
bool Del_Val(PCNode head, int val)
{
    assert(head);
    CNode* p = head;
    if (NULL == p->next)return false;
    while (p->next != head && val != p->next->data)
    {
        p = p->next;
    }
    if (p->next == head)
    {
        return false;
    }
    return Del_Next(p);
}
//查找
struct CNode* Search(PCNode plist, int val);
//找值为val的节点前驱
struct CNode* Get_Prev(PCNode plist, int val);
//找值为val的节点后继
struct CNode* Get_Next(PCNode plist, int val);
//获取其有效节点的个数
int Get_Length(PCNode head)
{
    assert(head);
    CNode* p = head;
    int count = 0;
    while (p->next != head)
    {
        count++;
    }
    return count;
}
//判空
bool IsEmpty(PCNode head)
{
    assert(head);
    if (head->next == head)return true;
    return false;
}
//清空
void Clear(PCNode head)
{
    assert(head);
    while (!IsEmpty(head))
    {
        Pop_Front(head);
    }
}
//销毁1
void Destroy1(PCNode head)
{
    assert(head);
    Clear(head);
}
//销毁2
void Destroy2(PCNode plist);
//打印
void Show(PCNode head)
{
    assert(head);
    CNode* p = head->next;
    while (p != head)
    {
        printf("%3d ", p->data);
        p = p->next;
    }
    printf("\n");
}
int main()
{
    CNode cn;
    Init_clist(&cn);
    for (int i = 0;i < 10;i++)
    {
        Insert_Pos(&cn, i,i+1);

    }
    Show(&cn);
    Push_Front(&cn, 100);
    Push_Back(&cn, 200);
    Show(&cn);

    Pop_Front(&cn);
    Pop_Back(&cn);
    Show(&cn);

    Del_Val(&cn, 6);
    Show(&cn);
    Del_Pos(&cn, 6);
    Show(&cn);
    Destroy1(&cn);
    Show(&cn);
}