首页 > 其他分享 >双向链表_C语言

双向链表_C语言

时间:2023-05-12 23:13:33浏览次数:46  
标签:node cur C语言 链表 llist 双向 next data ptr

2023年5月12日22:35:37

1. 数据结构

普通节点:数据域 *data,指针域 *prev、*next

头结点:size + 普通节点

其中:头结点data为NULL,size是指定data空间大小,data数据类型未定,也就是说头结点不同于普通节点

image-20230512224341995

本文想要实现的额外功能:data数据无论是多大,无论是什么类型,都能直接存放进去

代码实现:

struct llist_node_st {
    void *data;
    struct llist_node_st *prev;
    struct llist_node_st *next;
};
 
typedef struct {
    int size;
    struct llist_node_st head;
} LLIST;

2. 插入

链表插入操作的思路是:

  1. 给newnode和newnode的data动态分配空间(data数据类型未知,因此也需要动态分配空间)
  2. 用循环给newnode的data和指针赋值

链表插入方式分为首部插入、尾部插入。new是待插入节点,cur是当前节点。

image-20230512224446867

代码实现

int llist_insert(LLIST *ptr, const void *data, int mode) {
    struct llist_node_st *newnode;
 
//给newnode和对应的data分配空间。原因是保证传入data的任何数据都能接收,所以动态分配
    newnode = malloc(sizeof(*newnode));
    if (newnode == NULL)
        return -1;
 
    newnode->data = malloc(ptr->size);
    if (newnode == NULL)
        return -2;
 
//给newnode的data和指针赋值
    memcpy(newnode->data, data, ptr->size);
 
    if (mode == LLIST_FORWARD) {
        newnode->prev = &ptr->head;
        newnode->next = ptr->head.next;
        newnode->prev->next = newnode;
        newnode->next->prev = newnode;
    } else if (mode == LLIST_BACKWARD) {
        newnode->prev = ptr->head.prev;
        newnode->next = &ptr->head;
    newnode->prev->next = newnode;
        newnode->next->prev = newnode;
    } else {
        return -3;
    }
}

3. 销毁

销毁整个链表:

  1. 将cur节点单独保存为del,cur指向下一个
  2. free(cur.data)
  3. free(cur)

free两次,是因为前期malloc两次

代码实现:

void llist_destroy(LLIST *ptr) {
 
    struct llist_node_st *cur, *next;
 
    for (cur = ptr->head.next; cur != &ptr->head; cur = next) {
        next = cur->next;//cur 是要删除的节点,所以单独提取出来
        free(cur->data);
        free(cur);
    }
    free(ptr);
}

4. 遍历链表

具体的data中具体类型无法得知,所以要通过回调函数,等待用户传参,才能实现遍历的具体内容。

typedef void llist_op(const void *);
 
struct llist_node_st {
    void * data;
    struct llist_node_st *prev;
    struct llist_node_st *next;
};
 
typedef struct {
    int size;
    struct llist_node_st head;
} LLIST;
 
 
//遍历链表,op作用于cur->data
void llist_travel(LLIST *ptr, llist_op *op) {
    struct llist_node_st *cur;
 
    for (cur=ptr->head->next;cur!=&(ptr->head); cur=cur->head){
         op(cur->data);
    }
}
 
//回调函数提供op信息,打印每个cur->data中的id、name、math、chinese
static void print_s(const void *record) {//record指代cur->data
    const struct score_st *r = record;
    printf("%d %s %d %d\n", r->id, r->name, r->math, r->chinese);
}
 
 
int main(){
    //用户提供的data信息
    struct score_st {
        int id;
        char name[NAMESIZE];
        int math;
        int chinese;
    };
 
    LLIST *handler;
    handler = llist_create(sizeof(tmp));
    llist_travel(handler, print_s);
    return 0;
}

5. 查找

查找特定节点的数据域,是要根据传入参数查找。传入的key为学生id时,用循环只要node的data的id与key差值为0,说明找到了中断并返回即可。

typedef int llist_cmp(const void *, const void *);

static int id_cmp(const void *key, const void *record) {
    const int *k = key;//key是用户传入参数,是要查找的节点的data的id
    const struct score_st *r = record;//record是节点的data
    return (*k - r->id);
}//返回差值

static struct llist_node_st *find_(LLIST *ptr, const void *key, llist_cmp *cmp) {
    struct llist_node_st *cur;

    for (cur = ptr->head.next; cur != &ptr->head; cur = cur->next) {
        if (cmp(key, cur->data) == 0)
            break;
    }
    return cur;
}//(2)找到并返回key相同的节点,cmp差值为0说明找到

void *llist_find(LLIST *ptr, const void *key, llist_cmp *cmp) {
    return find_(ptr, key, cmp)->data;
}//(1)找到并返回key相同的节点的data
int main{
    
    LLIST *handler;
    int id = 3;
    struct score_st tmp;
    struct score_st * data;
    data = llist_find(handler, &id, id_cmp);//(0)
    llist_destroy(handler);
    return 0;
}

6. 删除/获取

先找到特定元素,即按照比较参数返回0的元素,将被删节点保存到node,断开指针指向,free之前动态分配的空间

//删除指定节点
int llist_delete(LLIST *ptr, const void *key, llist_cmp *cmp) {
    struct llist_node_st *node;
    node = find_(ptr, key, cmp);
    if (node == &ptr->head)
        return -1;

    node->prev->next = node->next;
    node->next->prev = node->prev;
    free(node->data);
    free(node);
    return 0;
}

//获取并删除
int llist_fetch(LLIST *ptr, const void *key, llist_cmp *cmp, void *data) {
    struct llist_node_st *node;
    node = find_(ptr, key, cmp);
    if (node == &ptr->head)
        return -1;

    node->prev->next = node->next;
    node->next->prev = node->prev;

    if (data != NULL)
        //extern void *memcpy(void *dest, void *src, unsigned int count);
        memcpy(data, node->data, ptr->size);
    free(node->data);
    free(node);
    return 0;
}

static struct llist_node_st *find_(LLIST *ptr, const void *key, llist_cmp *cmp) {
    struct llist_node_st *cur;

    for (cur = ptr->head.next; cur != &ptr->head; cur = cur->next) {
        if (cmp(key, cur->data) == 0)
            break;
    }
    return cur;//如果找不到,会返回头结点的地址
}

static int name_cmp(const void *key, const void *record) {
    const char *k = key;
    const struct score_st *r = record;//r是节点的data
    return strcmp(k, r->name);
}

int main() {    
    LLIST *handler;
	char *n = "std_5";
    int ret=llist_delete(handler, n, name_cmp);
   	return 0;
}

7. 全部代码

2023-05-12-双向链表-llist.c
2023-05-12-双向链表-llist.c
2023-05-12-双向链表-main.c

标签:node,cur,C语言,链表,llist,双向,next,data,ptr
From: https://www.cnblogs.com/Kaelthas/p/17396503.html

相关文章

  • C语言--字符操作库函数1
    strtok 字符串分割char*strtok(char*str,constchar*sep);strerror返回错误码,所对应的错误信息char*strerror(errno)errno--errno.h 是一个全局错误码的变量当C语言的库函数在执行过程中,发生了错误,就会把对应错误吗复制到errno中。字符分类函数引用<ctyoe.h>intret=iscntrl......
  • c语言环境配置
    1.先从百度搜索Windows下MinGW-w64的安装2.在从链接https://pan.baidu.com/s/1aMyeF4iUl0Bfn-P8ILGliQ3.在此电脑属性打开高级系统设置4.打开环境变量,再编辑用户变量中的Pith  5.新建浏览自己文件mingw64中的bin文件 一直确定退出 6.Win加R键输入cmd,输入gcc-v后有......
  • 代码随想录算法训练营第三天|203.移除链表元素 、707.设计链表 、206.反转链表
    一.链表基础1.最后一个节点的指针域指向null(空指针的意思)。2.链表在内存中不是连续分布的。3.链表的长度可以是不固定的,并且可以动态增删,适合数据量不固定,频繁增删,较少查询的场景。1#链表节点的定义2classListNode:3def__init__(self,val,next=None):4......
  • 打卡 c语言趣味编程 最佳存款问题
    假设银行一年整存零取的月息为0.63%。现在某人手中有一笔钱,他打算在今后的5年中的每年年底取出1000元,到第5年时刚好取完,请算出他存钱时应存入多少。思路:计算储蓄金额的数学公式为:储蓄金额=每年取出金额×(1+月息)^(存款年限×12)定义每年取出金额和存款年......
  • 通过C语言玩扫雷
    直接进入主题:先思考后敲代码!!首先,我将扫雷分为两个棋盘,一个放雷,另一个为玩家猜测盘。这就有同学问了,设置一个棋盘不就完了,这样不就搞复杂了吗?先简短的回答这位同学的问题:因为我的考虑是这样的,我用‘1’代表有雷,‘0’代表没有雷,如果放在一个盘中,出现多个1的时候,无法确定这是雷还是......
  • C语言程序设计(第四版)谭浩强版 课后答案 第四章
    4、#include<stdio.h>intmain(){inta,b,c;scanf("%d%d%d",&a,&b,&c);if(a>b){if(a>c){printf("maxnumis:%d\n",a);}......
  • 单片机ADC,十大C语言滤波算法
    一、限幅滤波法1、方法:根据经验判断两次采样允许的最大偏差值(设为A) 每次检测到新值时判断: a.如果本次值与上次值之差<=A,则本次值有效b.如果本次值与上次值之差>A,则本次值无效,放弃本次值,用上次值代替本次值2、优点:能有效克服因偶然因素引起的脉冲干扰3、缺点......
  • 四种语言刷算法之排序链表
    力扣148. 排序链表1、C/***Definitionforsingly-linkedlist.*structListNode{*intval;*structListNode*next;*};*/structListNode*sortList(structListNode*head){intn=0;structListNode*newHead=(structListNode*)m......
  • C语言之环形队列
    . 一、环形队列的优势环形队列是一种特殊的队列,它可以解决普通队列在使用时空间利用不充分的问题。在环形队列中,当队列满时,队列的尾指针指向队列的起始位置,而不是指向队列的最后一个元素。这样可以在不浪费空间的情况下存储更多的元素。      下面我们来详细讲解一下环形......
  • 移除链表元素
     /** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ......