欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

循环链表c语言实现 circlelinklist.h 和 circlelinklist.c

程序员文章站 2022-05-24 17:49:50
circlelinklist.h 文件 #ifndef _circle_link_list_h_ #define _circle_link_list_h_ #include #inclu...

circlelinklist.h 文件

#ifndef _circle_link_list_h_
#define _circle_link_list_h_
#include 
#include 
#include 
//循环链表
//链表操作精髓在于操作关系节点,引入辅助指针pcurrent,pnext.从表头开始遍历各关系节点。
//链表就是一个一个的表通过关系节点连接的


//利用小节点定义一个链表头,其他的业务节点有业务自己定义后连接到表头上

//实现上层调用和底层分离,不让调用用户知道数据结构
typedef void list;
typedef void listnode;

#ifndef bool
#define bool int
#define true 1
#define false 0
#endif

//定义小节点是有联系的 ,小节点的链表
typedef struct _tag_circlelinklistconnectednode
{
    struct _tag_circlelinklistconnectednode* next;
}circlelinklistconnectednode;

//定义链表
typedef struct _tag_circlelinklist{
    circlelinklistconnectednode head;  //小节点
    circlelinklistconnectednode* slider; //游标 
    int length; //小节点的个数就相当于业务节点的个数
}circlelinklist;


list* circlelinklist_create();
bool circlelinklist_destory(list* list);
bool circlelinklist_clear(list* list);
int circlelinklist_getlength(list* list);
bool circlelinklist_insertonenode(list* list , listnode* listnode, int pos);
listnode* circlelinklist_getonenode(list* list, int pos);
listnode* circlelinklist_deleteonenode(list* list,int pos);
bool circlelinklist_deleteallnode(list* list);
listnode* circlelinklist_deleteonenodebynodepointer(list* list,listnode* listnode);
listnode* circlelinklist_resetslider(list* list);
listnode* circlelinklist_getcurrentslider(list* list);
listnode* circlelinklist_slidermovetonext(list* list);
#endif

circlelinklist.c 文件

#include 
#include 
#include 
#include "circlelinklist.h"
//链表操作精髓在于操作关系节点,引入辅助指针pcurrent,pnext.从表头开始遍历各关系节点。
//链表就是一个一个的表通过关系节点连接的
list* circlelinklist_create()
{
   list* ret = null;
   circlelinklist* temp_circlelist = null;
   temp_circlelist = (circlelinklist*)malloc(sizeof(circlelinklist));
   if (temp_circlelist == null)
   {
       return null;
   }
   temp_circlelist->head.next =null;
   temp_circlelist->length = 0;
   temp_circlelist->slider = null;
   ret = (circlelinklist*)temp_circlelist;
   return ret;
}

bool circlelinklist_destory(list* list)
{
    circlelinklist* temp_circlelist = null;
    if (list == null)
    {
        return false;
    }
    temp_circlelist = (circlelinklist*)list;
    free(temp_circlelist);
    temp_circlelist = null;
    return true;
}

bool circlelinklist_clear(list* list)
{
    circlelinklist* temp_circlelist = null;
    if (list == null)
    {
        return false;
    }
    temp_circlelist = (circlelinklist*)list;
    //长度清零,头部指向空,游标指向空
    temp_circlelist->length = 0;
    temp_circlelist->head.next = null;
    temp_circlelist->slider = null;
    return true;
}

int circlelinklist_getlength(list* list)
{
    int ret = 0;
    circlelinklist* temp_circlelist = null;
    if (list == null)
    {
        return -1;
    }
    temp_circlelist = (circlelinklist*)list;
    ret = temp_circlelist->length;
    return ret;
}

bool circlelinklist_insertonenode(list* list , listnode* listnode, int pos)
{
    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node = null;
    circlelinklistconnectednode* pcurrent = null;
    int i = 0;
    circlelinklistconnectednode* lastnode = null;
    if (list == null || listnode == null || pos < 0)
    {
        return false;
    }
    temp_circlelist = (circlelinklist*)list;
    temp_circlelistconnected_node = (circlelinklistconnectednode*)listnode;
    //链表的首地址与小节点的地址相同
    pcurrent = (circlelinklistconnectednode*)temp_circlelist;
    //pcurrent =(circlelistnode*) &(temp_circlelist->head);
    //辅助指针从头部跳到(pos-1) 处;头部、0、1、2、。。
    for (i = 0; (i < pos && pcurrent->next != null); i ++)
    {
        pcurrent = pcurrent->next;
    }
    //插入节点
    temp_circlelistconnected_node->next = pcurrent->next;
    pcurrent->next = temp_circlelistconnected_node;
    //第一次插入节点,游标指向插入的第一个节点 即 0 位置
    if (temp_circlelist->length == 0)
    {
        temp_circlelist->slider = temp_circlelistconnected_node;
    }
    //长度加1
    temp_circlelist->length++;
    //辅助指针没有调,头插法,插到0位置
    if (pcurrent == (circlelinklistconnectednode*)temp_circlelist)
    {
        //得到最后一个节点
        lastnode = (circlelinklistconnectednode*)circlelinklist_getonenode((list*)temp_circlelist,temp_circlelist->length - 1);
        //最后一个节点的next域指向当前插入
        lastnode->next = pcurrent->next;
        //lastnode->next = temp_circlelist_node;
    }
    return true;
}

listnode* circlelinklist_getonenode(list* list, int pos)
{

    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node = null;
    circlelinklistconnectednode* pcurrent = null;
    int i = 0;
    listnode* ret = null;
    if (list == null || pos < 0)
    {
        return null;
    }
    temp_circlelist = (circlelinklist*)list;
    //不要判断长度了,循环的嘛
    if (temp_circlelist->length <= 0 )
    {
        return null;
    }
    //链表的首地址与小节点的地址相同
    pcurrent = (circlelinklistconnectednode*)temp_circlelist;
    //pcurrent =(circlelistnode*) &(temp_circlelist->head);
    //辅助指针从头部跳到(pos-1) 处;头部、0、1、2、。。
    for (i = 0; (i < pos && pcurrent->next != null); i ++)
    {
        pcurrent = pcurrent->next;
    }
    temp_circlelistconnected_node = (circlelinklistconnectednode*)(pcurrent->next);
    ret = (listnode*)temp_circlelistconnected_node;
    return ret;
}

listnode* circlelinklist_deleteonenode(list* list,int pos)
{
    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node_delete = null;
    circlelinklistconnectednode* pcurrent = null;
    circlelinklistconnectednode* lastnode = null;
    int i = 0;
    listnode* ret = null;
    if (list == null || pos < 0) 
    {
        return null;
    }
    temp_circlelist = (circlelinklist*)list;
    //链表的首地址与小节点的地址相同
    pcurrent = (circlelinklistconnectednode*)temp_circlelist;
    //pcurrent =(circlelistnode*) &(temp_circlelist->head);
    if (temp_circlelist->length <= 0 || pos >= temp_circlelist->length)
    {
        return null;
    }
    //辅助指针从头部跳到(pos-1) 处;头部、0、1、2、。。
    for (i = 0; (i < pos && pcurrent->next != null); i ++)
    {
        pcurrent = pcurrent->next;
    }
    temp_circlelistconnected_node_delete = pcurrent->next;
    pcurrent->next = temp_circlelistconnected_node_delete->next;
    //pcurrent->next = pcurrent->next->next;
    //如果从0位置删除
    if (pcurrent == (circlelinklistconnectednode*)temp_circlelist)
    {
        //得到最后一个节点
        lastnode = (circlelinklistconnectednode*)circlelinklist_getonenode((list*)temp_circlelist,temp_circlelist->length - 1);
        //最后一个节点的next域指向当前插入
        if (lastnode != null)
        {
            lastnode->next = pcurrent->next;
            //lastnode->next = temp_circlelist_node_delete->next;
            //lastnode->next = temp_circlelist->head.next;
        }

    }
    //长度减1
    temp_circlelist->length--;
    //如果删除的是游标指向的位置则游标下移
    if (temp_circlelist->slider == temp_circlelistconnected_node_delete)
    {
        temp_circlelist->slider = temp_circlelistconnected_node_delete->next;
    }
    //长度为0就清空
    if (temp_circlelist->length == 0)
    {
        temp_circlelist->head.next = null;
        temp_circlelist->slider = null;
    }

    ret = (listnode*)temp_circlelistconnected_node_delete;
    return ret;
}

bool circlelinklist_deleteallnode(list* list)
{
    circlelinklist* temp_circlelist = null;
    if (list == null)
    {
        return false;
    }
    temp_circlelist = (circlelinklist*)list;
    while (temp_circlelist->length > 0 )
    {
        circlelinklist_deleteonenode((list*)temp_circlelist,0);
    }
    return true;
}

listnode* circlelinklist_deleteonenodebynodepointer(list* list,listnode* listnode)
{
    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node_delete = null;
    circlelinklistconnectednode* pcurrent = null;
    circlelinklistconnectednode* retnode = null;
    int i = 0;
    listnode* ret = null;
    if (list == null || listnode == null)
    {
        return null;
    }
    temp_circlelist = (circlelinklist*)list;
    temp_circlelistconnected_node_delete = (circlelinklistconnectednode*)listnode;
    pcurrent = (circlelinklistconnectednode*)temp_circlelist;
    for (i = 0; i < temp_circlelist->length; i ++)
    {
        pcurrent = pcurrent->next;
        if (pcurrent == temp_circlelistconnected_node_delete)
        { 
            retnode = pcurrent;
            break;
        }
    }
    if (retnode == null)
    {
        return null;
    }
    circlelinklist_deleteonenode((list*)temp_circlelist,i);
    ret =(listnode*)retnode;
    return ret;
}

//重置游标
listnode* circlelinklist_resetslider(list* list)
{
    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node = null;
    listnode* ret = null;
    if (list == null)
    {
        return null;
    }
    temp_circlelist = (circlelinklist*)list;
    temp_circlelist->slider = temp_circlelist->head.next;

    temp_circlelistconnected_node = temp_circlelist->slider;
    ret = (listnode* )temp_circlelistconnected_node;
    return ret;
}
//返回当前游标,
listnode* circlelinklist_getcurrentslider(list* list)
{
    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node = null;
    listnode* ret = null;
    if (list == null)
    {
        return null;
    }
    temp_circlelist = (circlelinklist*)list;

    temp_circlelistconnected_node = temp_circlelist->slider;
    ret = (listnode* )temp_circlelistconnected_node;
    return ret;
}
//游标下移,并返回游标下移之前的节点
listnode* circlelinklist_slidermovetonext(list* list)
{
    circlelinklist* temp_circlelist = null;
    circlelinklistconnectednode* temp_circlelistconnected_node = null;
    listnode* ret = null;
    if (list == null)
    {
        return null;
    }
    temp_circlelist = (circlelinklist*)list;
    if (temp_circlelist->slider == null)
    {
        return null;
    }
    //得到当前游标指向的节点
    temp_circlelistconnected_node = temp_circlelist->slider;
    //游标下移,指向下一个节点
    temp_circlelist->slider = temp_circlelistconnected_node->next;
    //返回当初得到的节点
    ret = (listnode*)temp_circlelistconnected_node;
    return ret;

}


/***********************以下为测试代码************************/

/*
typedef struct _tag_teacher
{

    circlelinklistconnectednode node;
    int age ;
    char name[];
}teacher;

void main()
{
    list* list = null;
    teacher t1,t2,t3,t4,t5;
    int kk = 0;
    teacher* teacher = null;
    t1.age = 21;t2.age = 22;t3.age = 23;t4.age = 24;t5.age = 25;
    list = circlelinklist_create();
    if (list == null)
    {
        printf("创建list失败");
    }
    //尾插法
    circlelinklist_insertonenode(list,(listnode*)&t1,circlelinklist_getlength(list));
    circlelinklist_insertonenode(list,(listnode*)&t2,circlelinklist_getlength(list));
    circlelinklist_insertonenode(list,(listnode*)&t3,circlelinklist_getlength(list));
    circlelinklist_insertonenode(list,(listnode*)&t4,circlelinklist_getlength(list));
    circlelinklist_insertonenode(list,(listnode*)&t5,circlelinklist_getlength(list));

    //打印2边,能输出2遍,没有越界,证明是循环链表
    for (kk = 0; kk < 2*circlelinklist_getlength(list); kk ++)
    {
         teacher = (teacher* )circlelinklist_getonenode(list,kk);
         printf("老师%d的年龄是%d",kk,teacher->age);
         printf("\n");
    }
    circlelinklist_deleteonenodebynodepointer(list,(listnode*)&t5);

    printf("链表长度%d \n",circlelinklist_getlength(list));
    for (kk = 0; kk < 2*circlelinklist_getlength(list); kk ++)
    {
        teacher = (teacher* )circlelinklist_getonenode(list,kk);
        printf("老师%d的年龄是%d",kk,teacher->age);
        printf("\n");
    }
    printf("链表长度%d \n",circlelinklist_getlength(list));
    circlelinklist_deleteallnode(list);
    printf("链表长度%d \n",circlelinklist_getlength(list));
    circlelinklist_destory(list);
    system("pause");
}
*/

可能会调用其它头文件或源文件,如果调用,请翻看我的其它博客,对其头文件或源文件的实现。
good luck !