数据结构:双向循环链表

发布时间:2024年01月18日

sxxhlb.h

/*===============================================
*   文件名称:sxxhlb.h
*   创 建 者:cxy     
*   创建日期:2024年01月17日
*   描    述:
================================================*/
#ifndef _SXXHLB_H
#define _SXXHLB_H

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

typedef struct list{
    struct list *front;
    struct list *next;
    int data;
}List,*Plist;

int init_list(Plist *L);
int insert_data(Plist p,int data); //头插
int delete_data(Plist p,int data);
int change_data(Plist p,int old_data,int new_data);
Plist select_data(Plist p,int data);
int empty(Plist p);   //1为空
int clear(Plist p);   //清空至初始化时模样
void show_front(Plist p);  //逆序打印
void show_next(Plist p);   //顺序打印
int free_list(Plist *L);  //释放整个链表

#endif

sxxhlb.c

/*===============================================
*   文件名称:sxxhlb.c
*   创 建 者:cxy     
*   创建日期:2024年01月17日
*   描    述:
================================================*/
#include "sxxhlb.h"

int init_list(Plist *L)   //创建头节点
{
    *L = malloc(sizeof(List));
    if(NULL == *L)
    {
        perror("init_malloc");
        return -1;
    }
    (*L)->next = *L;   //前后指针指向自己
    (*L)->front = *L;

    return 0;
}

int insert_data(Plist p,int data)  //头插
{
    if(NULL == p)
    {
        perror("insert err:p");
        return -1;
    }
    Plist q = malloc(sizeof(List));
    if(NULL == q)
    {
        perror("insert err:q");
        return -1;
    }
    q->data = data;

    q->next = p->next;
    p->next->front = q;
    q->front = p;
    p->next = q;

    return 0;
}

//删除节点,指针指向对应节点,连接前一个节点与后一个节点
int delete_data(Plist p,int data)
{
    if(NULL == p)
    {
        perror("delete err:p");
        return -1;
    }
    if(empty(p))   //只有头节点
    {
        perror("delete err:empty");
            return -1;
    }
    Plist q = p->next;   //头节点下一个节点开始
    while(q != p)
    {
        if(q->data == data)
        {
            q->next->front = q->front;
            q->front->next = q->next;
            Plist delete = q;
            q = q->next;      //继续判断下一个
            free(delete);
        }
        else
        {
            q = q->next;
        }
    }

    return 0;
}

int change_data(Plist p,int old_data,int new_data)
{
    if(NULL == p)
    {
        perror("change err:p");
        return -1;
    }
    if(empty(p))
    {
        perror("change err:empty");
        return -1;
    }
    Plist q = p->next;
    while(q != p)
    {
        if(q->data == old_data)
        {
            q->data = new_data;
        }
        q = q->next;
    }

    return 0;
}

Plist select_data(Plist p,int data)
{
    if(NULL == p)
    {
        perror("select err:p");
        return NULL;
    }
    if(empty(p))
    {
        perror("select err:empty");
        return NULL;
    }
    Plist q = p->next;

    while(q != p)
    {
        if(q->data == data)
        {
            return q;
        }
        else
        {
            q = q->next;
        }
    }

    return NULL;
}

int empty(Plist p)
{
    if(NULL == p)
    {
        perror("empty err:p");
        return -1;
    }
    Plist phead = p;
    if(p->next == phead && p->front == phead)
    {
        return 1;
    }
 
    return 0;   //不写会报错
}

int clear(Plist p)
{
    if(NULL == p)
    {
        perror("clear err:p");
        return -1;
    }
    if(empty(p))
    {
        perror("clear err:empty");
        return -1;
    }
#if 0
    Plist q = p->next;
    Plist clear = NULL;
    while(q != p)
    {
        clear = q;
        q = q->next;
        free(clear);
    }
    p->next = p;
    p->front = p;
#else
    Plist q = NULL;
    while(p->next != p)
    {
        q = p->next;
        p->next = q->next;
        q->next->front = p;
        free(q);
    }
#endif

    return 0;
}

void show_front(Plist p) //逆序
{
    if(NULL == p)
    {
        perror("show err:p");
        return;
    }
    if(empty(p))
    {
        perror("show err:empty");
        return;
    }
    Plist q = p->front;
    while(q != p)
    {
        printf("%d ",q->data);
        q = q->front;
    }
    puts("");

    return;
}

void show_next(Plist p) //顺序
{
    if(NULL == p)
    {
        perror("show err:p");
        return;
    }
    if(empty(p))
    {
        perror("show err:empty");
        return;
    }
    Plist q = p->next;
    while(q != p)
    {
        printf("%d ",q->data);
        q = q->next;
    }
    puts("");

    return;
}


int free_list(Plist *L)  //释放整个链表
{
    if(NULL == *L)
    {
        perror("clear err:*L");
        return -1;
    }
#if 1
    if(!empty(*L))
    {
        Plist q = NULL;
        while((*L)->next != (*L))
        {
            q = (*L)->next;
            (*L)->next = q->next;
            q->next->front = (*L);
            free(q);
        }
    }
    free(*L);  //释放空间
    *L = NULL; //改变指针指向
#else
    clear(*L);
    free(*L);
    *L = NULL;
#endif

    return 0;
}

mian.c

/*===============================================
*   文件名称:main.c
*   创 建 者:     
*   创建日期:2024年01月17日
*   描    述:
================================================*/
#include "sxxhlb.h"

int main(int argc, char *argv[])
{ 
    Plist p = NULL;
    int num;

    init_list(&p);
    
    printf("**********empty,1为空**********\n");
    num = empty(p);
    printf("%d\n",num);

    printf("**********insert_data**********\n");
    insert_data(p,22);
    insert_data(p,33);
    insert_data(p,44);
    insert_data(p,55);
    insert_data(p,66);
    printf("**********show_front**********\n");
    show_front(p);
    printf("**********show_next**********\n");
    show_next(p);
    
    printf("**********select_data**********\n");
    Plist q = select_data(p,22);
    printf("%p\n",q);
    
    printf("**********empty,1为空**********\n");
    num = empty(p);
    printf("%d\n",num);

    printf("**********delete_data**********\n");
    delete_data(p,12);
    printf("**********show_front**********\n");
    show_front(p);
    printf("**********show_next**********\n");
    show_next(p);

    printf("**********change_data**********\n");
    change_data(p,44,44444);
    printf("**********show_front**********\n");
    show_front(p);
    printf("**********show_next**********\n");
    show_next(p);

    printf("**********clear**********\n");
    clear(p);
    printf("**********empty,1为空**********\n");
    num = empty(p);
    printf("%d\n",num);

    free_list(&p);

    return 0;
} 

结果

文章来源:https://blog.csdn.net/cxy255256/article/details/135654455
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。