投稿
  1. 首页
  2. C

初见链表（C语言）

电脑常见问题 • 2022-9-23 • C • 阅读 37

初见链表（C语言）,第1张

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录
  • 前言
  • 一、简介
  • 二、算法及相应代码
  • 总结

前言

链表是一种物理存储结构上非连续，非顺序的存储结构，通过链表节点中存储的指针单元可以完成节点单元间的链接。

一、链表简介

逻辑结构：链表是线性的，即首元素没有直接前驱，尾元素没有直接后继，其余元素有且只有一个前驱和后继。

存储结构：以链式结构进行存储(元素间是非连续的)。

优点：

1.链表的内存是动态分配的，内存大小不固定，方便对它拓展，提高了内存利用率，减少浪费。

2.对链表中元素的插入和删除更方便，通过指针的指向就可以进行 *** 作。

缺点：

1.相比较数组查找的效率较低，总是需要从头节点开始遍历链表查找数据。

2.结构比数组复杂一些

二、算法及相应代码

链表的基础 *** 作有增删改查等

1.链表的定义

代码如下：

typedef int linklist_data_t;//数据类型重命名
typedef struct linklist //定义一个结构体，分为数据域和指针域
{
    int data;
    struct linklist *next;//保存了下一个节点的地址
}linkl_node,* linkl_pnode;
2.创建链表头节点

代码如下：

linkl_pnode linkl_creat()
{
    linkl_pnode H=(linkl_pnode)malloc(sizeof(linkl_node));//在堆区开辟空间
    if(NULL == H)
    {
        printf("内存分配失败\n");
        return NULL;
    }
    H->next = NULL;//末尾节点的指针域为NULL
    return H;    
}
3.链表的遍历，判空，长度 
//长度(有效数据节点个数)
int linkl_len(linkl_pnode H)
{
    int count=0;
    while(H->next)
    {
        H=H->next;
        count++;
    }
    return count;
}
//判空
int linkl_empty(linkl_pnode H)
{
    if(H->next==NULL)
        return 0;
    else
        return -1;
}
//遍历输出
int linkl_traverse(linkl_pnode H)
{
    if(0==linkl_empty(H))
    {
        printf("Err:链表为空\n");
        return -1;
    }
    while(H->next)
    {
        H=H->next;
        printf("data=%d\n",H->data);
    }
    return 0;
}
3.增加链表节点 
//插入新节点
/*pos值这里为节点下标，人为的认为链表的第一个数据节点下标为0。
头节点并不是有效数据节点，它指向的下一个节点为第一个有效数据节点
*/
int linkl_inser(linkl_pnode H,int pos,linklist_data_t data)
{
    linkl_pnode new= linkl_creat();//给新的节点在堆区分配空间
    if(pos<0 || pos>linkl_len(H))
    {
        printf("pos值非法\n");
        return -1;
    }
    while(pos--) //H走到下标为pos的前一个节点
        H=H->next;
    new->data=data;
    new->next=H->next;//新节点指向插入位置的下一个节点
    H->next=new;//插入位置的前一个节点指向新节点
}
4.删除节点 
//按照下标删除
int linkl_delete(linkl_pnode H,int pos)
{
    linkl_pnode p;
    if(0==linkl_empty(H))
    {
        printf("链表为空\n");
        return -1;
    }
    if(pos<0 || pos>=linkl_len(H))
    {
        printf("Err:位置值非法\n");
        return -2;
    }
    while(pos--)
        H=H->next;
    p=H->next;//保存要删除的元素
    H->next=p->next;//得到删除元素下一个元素的位置
    free(p);//释放删除节点的空间
    p=NULL;//指向NULL，避免野指针
    return 0;
}
//按照值删除
int linkl_delete_data(linkl_pnode H,linklist_data_t data)
{
    if(0==linkl_empty(H))
    {
        printf("链表为空\n");
        return -1;
    }
    int pos=-1;
    linkl_pnode L=H;//保存头节点
    //记录数据对应的节点下标
    while(L->data!=data && L->next)
    {
        pos++;
        L=L->next;
    }
    if((pos==linkl_len(H)-1) && L->data!=data)
    {
        printf("Err:There is no such data\n");
        return -2;
    }
    while(pos--)
        H=H->next;
    L=H->next;
    H->next=L->next;
    free(L);
    L=NULL;
    return 0;
}
5.改变节点数据 
//按照下标改变内容
int linkl_change_pos(linkl_pnode H,int pos,linklist_data_t data)
{
    if(0==linkl_empty(H))
    {
        printf("链表为空\n");
        return -1;
    }
    if(pos<0 || pos>=linkl_len(H))
    {
        printf("Err:位置值非法\n");
        return -2;
    }
    while(pos--)
        H=H->next;
    H->next->data=data;
    return 0;
}
//按照值改变
int linkl_change(linkl_pnode H,linklist_data_t old_data,linklist_data_t new_data)
{
    if(0==linkl_empty(H))
    {
        printf("链表为空\n");
        return -1;
    }
    int flag=0;
    while(H->next)
    {
        if(H->data==old_data)
        {
            H->data=new_data;
            return 0;
        }
        H=H->next;
    }
    if(flag==0)
    {
        printf("Err:没有要修改的值\n");
        return -2;
    }
}
6.查询节点数据 
//按值查询 链表中可能会有多个节点存储有满足要查询的值，所以返回一个数组
linkl_pnode *linkl_search(linkl_pnode H,linklist_data_t data,linkl_pnode *pos)
{
    if(0==linkl_empty(H))
    {
        printf("Err:链表为空\n");
        *pos=(linkl_pnode)(-1);
        return pos;
    }
    linkl_pnode L=H;
    int poss=-1,i=0,j=0;
    int pos1[100];//保存下标
    while(L->next)
    {
        poss++;
        L=L->next;
        if(L->data==data)
        {
            pos1[i]=poss;
            i++;
        }
    }
    if(0==i)//判断节点中是否有要查询的数据
    {
        printf("Err:There is no such data\n");
        *pos=(linkl_pnode)(-2);
        return pos;
    }
    pos1[i]=-2;//作为结束位，这里存放的数据已经不是合法的节点下标值了
    for(i=0;pos1[i]>=0;i++)
    {
        L=H;
        while(pos1[i]--)
        {
            L=L->next;
        }
        pos[j++]=L->next;//将满足数值的节点地址给到数组中去
    }
    pos[j]=NULL;
    return pos;
}
//按下标查询
linklist_data_t linkl_search_pos(linkl_pnode H,int pos)
{
    if(0==linkl_empty(H))
    {
        printf("Err:链表为空\n");
        return -1;
    }
    if(pos<0 || pos>=linkl_len(H))
    {
        printf("Err:位置值非法\n");
        return -2;
    }
    while(pos--)
        H=H->next;
    return H->next->data;
}
7.链表的清空与销毁 
//清空 除头节点外的节点全部删除
int linkl_clean(linkl_pnode H)
{
    if(0==linkl_empty(H))
    {
        printf("Err:链表为空\n");
        return -1;
    }
    while(linkl_empty(H))//不断删除下标为0的节点，直到头节点中next指向NULL
    {
        linkl_delete(H,0);
    }
    return 0;
}
//销毁：链表的所有节点全部删除
int linkl_destroy(linkl_pnode *H)//要改变头节点H，便需要传递H的地址。
{
    if(0==linkl_empty(*H))
    {
        free(*H);
        *H=NULL;
    }
    else
    {
        linkl_clean(*H);
        free(*H); 
        *H=NULL;
    }
    return 0;
}
8.链表的排序 
//排序 
int linkl_sort(linkl_pnode H)
{
    if(0==linkl_empty(H))
    {
        printf("Err:链表为空\n");
        return -1;
    }
    int len=linkl_len(H);
    linkl_pnode p,q;
    int temp=0;
    for(p=H->next;p!=NULL;p=p->next)//可以和下面的选择排序对应理解
    {
        for(q=p->next;q!=NULL;q=q->next)
        {
            if(p->data>q->data)
            {
                temp=p->data;
                p->data=q->data;
                q->data=temp;
            }
        }
    }
    return 0;
   /* 选择排序
    int i,j,t=0;
    for(i=0;ia[j])
            {
                t=a[i];
                a[i]=a[j];
                a[j]=t;
            }
        }
    }
    */
}
9.链表的逆序

逆序有多种方法，这里介绍两种较为简单的方法

//逆序通过头插法实现
/*创建一个新的头节点，遍历原链表，得到的节点不断在新头节点位置做头插*/
linkl_pnode linkl_reversed_odd(linkl_pnode H)
{
    if(0 == linkl_empty(H))
    {
        printf("Err:链表为空\n");
        return (linkl_pnode)(-1);
    }
    linkl_pnode L=linkl_creat();
    while(H->next)
    {
        linkl_inser(L,0,H->next->data);
        H=H->next;
    }
    return L;
}

//逆序（双指针得到）
linkl_pnode linkl_reversed_odd1(linkl_pnode H)
{
    if(0 == linkl_empty(H))
    {
        printf("Err:链表为空\n");
        return (linkl_pnode)(-1);
    }
    linkl_pnode q=NULL;//保存前一个节点
    linkl_pnode var=H;//保存当前节点
    linkl_pnode p;  //保存后一个节点
    while(var)
    {
        p=var->next;
        var->next=q;//指向前一个节点
        q=var;      //后移
        var=p;
    }
    return q;
}
总结

以上的内容都是对单链表的基础 *** 作，链表还有循环和双链表等种类等待你的了解

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/2990586.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
电脑常见问题 电脑常见问题 一级用户组
0 0
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表（0条）

保存