单向链表 c语言实现

发布时间:2020-07-14 10:57:39 作者:onecan2009
来源:网络 阅读:10125
  1. 定义(引用百度百科)
    单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
  2. 场景

在实际生产中,有可能在软件启动后,对一些数据进行多态扩容,比如,网卡收发包的时候,从协议栈上产生一个需求的包,需要暂时排队,等网卡把数据发送出去后,在在队列里处理,所以这种利用堆中分散的内存,以结点为单位的数据结果是有一定的意义的。

  1. C语言实现,聊作记录

链表的数据的数据结构

typedef struct node
{
        int data;                                           //数据域
        struct node *next;                          //指针域
}NODE_t;

链表的创建

    NODE_t *CreatNodeList()
{
    NODE_t *head = NULL;

    head = (NODE_t *)malloc(sizeof(NODE_t));
    if(!head)
        exit(-1);
    head->next = NULL;

    return head;
}

链表的插入,头插入,有个头节点,方便遍历,处理

int InsertNode(NODE_t *head,int data)
{
    NODE_t *cur = NULL;

    if(!head)
        exit(-1);

    cur = (NODE_t *)malloc(sizeof(NODE_t));
    if(!cur)
        exit(-1);

    cur->data = data;
    //cur 插入到 head 和 head->next 之间
    cur->next = head->next;
    head->next = cur;

    return 0;
}

结点的查找

NODE_t *findNode(NODE_t *head,int data)
{
    head = head->next;
    while(head)
    {
        if(head->data == data)
        {
            break;
        }
        head = head->next;
    }
    if(head == NULL)
    {
        printf("sorry,%d is not in the list\n",data);
    }

    return head;
}

结点的删除

    int DeleteNodeOfList(NODE_t *head,NODE_t *pfind)
{
    // 首先找到这个需要删除指针的前一个节点的指针
    // 因为pfind 的合法性在外面判断,此处不再判断
    while(head->next != pfind)
    {
        head = head->next;
    }

    head->next = pfind->next;
    free(pfind);
    pfind = NULL;

    return 0;
}

这里的删除,假设结点数目很多,则会造成一个问题,单链表只能一个方向,则需要找到需要删除的节点的前驱指针,则需要从头开始遍历,比较浪费资源,所以,这个地方存在优化空间,就是,一旦拥有需要删除的节点,则可以这么操作

优化版本如下:

// 优化点: 不必每次都遍历所有的节点,找到前驱节点
// 将这个需要删除的节点的后驱节点的数据域拷贝过来,然后删除这个后驱节点
int DeleteNodeOfList_Better(NODE_t *head,NODE_t *pfind)
{
    NODE_t *p = pfind->next;

    //最后一个节点,它其后没有后驱节点,所以需要从头遍历,找到它的前置节点
    if(pfind->next == NULL)
    {
        while(head->next != pfind)
        {
            head = head->next;
        }

        head->next = pfind->next;
        free(pfind);
        pfind = NULL;
    }
    else //对于除最后一个节点的外的其他位置节点,则使用覆盖后删除后置节点的方式实现删除
    {

        pfind->data = pfind->next->data;
        pfind->next = pfind->next->next;

        free(p);
        p = NULL;
    }

    return 0;
}

一旦找到结点的指针操作只是针对数据域的一个操作,比较便捷
结点的修改

int UpdateNode(NODE_t *head,int olddata,int newdata)
{
    NODE_t *p = findNode(head,olddata);
    if(p)
    {
        p->data = newdata;
    }

    return 0;
}

遍历打印显示

void showList(NODE_t *head)
{
    head = head->next;
    while(head)
    {
        printf("%d ==> ",head->data);
        head = head->next;
    }
    printf("end..\n");
}

链表的排序

int sortList(NODE_t *head)
{
    int i = 0,j = 0;
    int listlen = 0;
    int tmpData = 0;
    NODE_t *p = NULL;

    // 使用冒泡排序,不动指针域,比较数据域,使用临时变量,将有大小之别的节点的数据域交换
    // 得到链表长度,方便冒泡
    listlen = ListNodeLen(head);

    // 指到首节点
    p = head->next;
    for(i = 0;i < listlen-1;i++)
    {
        // 每一轮从头开始
        p = head->next;
        for(j = 0;j<listlen - i-1;j++)
        {
            // 将小值排在前面
            if(p->data > p->next->data)
            {
                tmpData = p->data;
                p->data = p->next->data;
                p->next->data = tmpData;
            }
            p = p->next;
        }
    }

    return 0;
}

这里只是demo,链表的数据域很小,所以这种排序方式可以,但是当数据域的很大时,直接使用这种排序,涉及到大量的搬运内存,将会导致很大的资源消耗,所以这个地方是存在优化的空间的,比如直接改变需要交换结点的指向关系
代码如下

int sortList_better(NODE_t *head)
{
    // 当数据域很大的时候,搬远数据很耗费资源,但是指针就4个字节,
    // 所以改变指针域的相互指向,就可解决问题
    // 思路如下:
    // 还是使用冒泡比较,当需要交换时,将两个节点的指针域指向关系互换

    int i = 0,j = 0;
    int listlen = 0;
    NODE_t *p = NULL;
    NODE_t *q = NULL;
    NODE_t *tmp = NULL;
    listlen = ListNodeLen(head);

    for(i = 0;i <listlen -1;i++)
    {
        tmp = head;
        p = head->next;
        q = p->next;                    // q 永远指向p结点的下一个结点
        for(j = 0;j <listlen-i-1;j++)
        {
            if(p->data > q->data)
            {
                //                NODE_t *tmp = prePointerOfNode(head,p);
//                现在有三个结点,prep p    q 他们分别代表的含义是

//                p 为当前结点
//                prep为p结点的前驱结点
//                q 为p结点的后续结点

//                现在需要将p 和 q的顺序做对调,只需要改变其指向关系即可
//                1. 将prep 的下一个结点指向到q
//                2. 将p结点后续结点指向q的后续结点
//                3. 在第二步里已经在q的后续结点的已经找到,所以这个时候将q的后续结点指向p,
//                这样子,就将p和q的顺序对调过了
                tmp->next = q;
                p->next = q->next;
                q->next = p;

//                因为p和q的顺序已经对调过了,为保证顺序,将p和q的顺序做一次对调,
//                确保q是p的下一个结点
                /*
                    注意p和q都是临时变量,所以,这个地方并非对结点的对调,只是临时指针的对调,就是将q对于结点的指针放到p这个临时变量里
                    ,原来p对应的结点指针放到q这个临时变量中
                */
                NODE_t *t = NULL;
                t = p;
                p = q;
                q = t;
            }
//            向下走一个
            tmp = tmp->next;
            p = p->next;
            q = p->next;
        }
    }

    return 0;
}

链表的逆序

void ReverseList(NODE_t *head)
{
    //将头指针和其他链表割裂,这样子就是一个空链表 和一个无头的链表
    // 然后将另一个链表的每个结点拆出来,然后使用头插法插入到空链中,这样子最后就实现了链表的逆向排序

    NODE_t *HeadNextNode = head->next;
    head->next = NULL; //分割链表,分成一个空链和一个链表

    // 将第二个链表的每一个结点分别插入到空链的头部
    for(HeadNextNode;HeadNextNode !=NULL;HeadNextNode = HeadNextNode->next)
    {
        InsertNode(head,HeadNextNode->data);
    }
}

这个思路很好,不易出错,如果贸然的从指向关系上入手,很容易把自己绕晕

链表的销毁

void DestoryNodeList(NODE_t *head)
{
    NODE_t *p = NULL;

    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
}
推荐阅读:
  1. C语言之字符单向链表
  2. C语言反转单向链表的代码

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

单链表 c基本 操作

上一篇:Java工作的方向是什么

下一篇:中小型企业网络构建之路由的简单配置

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》