详细解析单链表带头节点的结构体定义,普通单链表与有序单链表的创建等操作(含创建步骤与码源)

本文涉及的产品
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
简介: 详细解析单链表带头节点的结构体定义,普通单链表与有序单链表的创建等操作(含创建步骤与码源)

目录


单链表回顾

带头结点的单链表

带头节点的意义

什么是头节点

头节点与数据节点定义

创建带头节点的单链表的步骤与详细代码

创建有序带头节点单链表的步骤与码源


正文


带头结点的单链表


带头节点的意义


很多时候我们可能经常需要知道一个链表有多少个结点,或者求一个链表的最后一个结点...

       => 我们都要通过第一个结点的指针,遍历整个链表。


而一个头节点就能很好的帮我们解决这个问题,而且只需要知道单链表的第一个结点的指针,first  对单链表的基本操作 “增删改查”就可以完成了


例如:

find_x
p = h;
while(p)
{
  if(p->data == x)
  {
      break;
  }
  p = p->next;
}
find_last
p = h;
while(p)
{
    if(p->next == NULL)
  {
    reak;
  }
  p = p->next;
}


什么是头节点


头结点是用来管理链表的结点,这个结点一般包括常用的管理链表的数据对象:

   eq: 指向链表的第一个结点指针 ,指向链表最后一个结点的指针...

 

   什么是数据结点?

       原来用来保存数据的结点 就称为数据结点

     

   头结点是唯一一个标识一个链表存在与否的标志。

 

   带头结点的单链表:

       一个链表可以没有数据结点,但是必须要有头结点。

     

       没有数据结点,表示“空链表”

       没有头结点,表明这个链表不存在


头节点与数据节点定义


提示:简单描述算法知识点相关题目题意

//数据结点:
typedef int ElemType;
typedef struct node
{
  ElemType data;//数据域
  struct node *next;//指针域
}Node;
//头结点:不保存数据 只有两个指针 加一个结点数目
typedef struct linkedlist
{
  Node *first;//指向链表中的第一个数据结点
  Node *last;//指向链表中的最后一个数据结点
  ElemType NodeNum;//结点的数目
  //...//根据具体需求 增加其它的成员变量
}List;


创建带头节点的单链表的步骤与详细代码


根据用户的输入数据 创建一个单链表

   step1:创建一个头结点

   step2:每获得一个数据就创建一个数据结点

   step3:把获得的数据 写入到数据结点中

   step4:把数据结点加入到链表中去。

List *create_list()
{
    ElemType d;//用来保存获取的数据
    Node *pnew = NULL;//指向新创建的数据结点
    //step1:创建一个头结点
    List *list = malloc(sizeof(*list));
    list->first = NULL;
    list->last = NULL;
    list->NodeNum = 0;
    //step2 :每获得一个数据就创建一个数据结点
    while(1)
    {
        scanf("%d",&d);
        if(d == 0)
        {
            break;
        }
        pnew = malloc(sizeof(*pnew));
    //step3:把获得的数据 写入到数据结点中
        pnew->data = d;
        pnew->next = NULL;
    //step4:把数据结点加入到链表中去。
        if(list->first == NULL)//从无都有
        {
            list->first = pnew;
            list->last = pnew;
        }
        else//从少到多
        {
            //尾插
            #if 1
            list->last->next = pnew;
            list->last = pnew;
            #endif
            //头插
            #if 0
            pnew->next = list->first;
            list->first = pnew;
            #endif
        }
        list->NodeNum++;
    }
    return list;
}


创建有序带头节点单链表的步骤与码源


创建一条带头结点的有序列表  升序

       step1:创建一个头结点

       step2:每获得一个数据就创建一个数据结点

       step3:把获得的数据 写入到数据结点中

       step4:把数据结点加入到链表中去。

               从无到有

               从少到多 --》找到第一个比pnew大的数据

                   1.第一个就比pnew大 pnew头插

                   2.找一了遍 没有找

/*
    create_sort_list:创建一条带头结点的有序单链表
    返回值:
        创建好的单链表的头结点
*/
List *create_sort_list()
{
    ElemType d;//用来保存获取的数据
    Node *pnew= NULL;//指向新创建的数据结点
    //step1:创建一个头结点
    List *list = malloc(sizeof(*list));
    list->first = NULL;
    list->last = NULL;
    list->NodeNum = 0;
    while(1)
    {
        //step2:每获得一个数据就创建一个数据结点
        scanf("%d",&d);
        if(d == 0)
        {
            break;
        }
        pnew = malloc(sizeof(*pnew));
        //step3:把获得的数据 写入到数据结点中
        pnew->data = d;
        pnew->next = NULL;
        //step4:把数据结点加入到链表中去。
        if(list->first == NULL)//从无到有
        {
            list->first = pnew;
            list->last = pnew;
        }
        else//从少到多
        {
            Node *p = list->first;//遍历指针 要找到第一个比pnew大的值
            Node *pre = NULL;//指向p前面的那个结点
            while(p)
            {
                if(p->data > pnew->data)//找到了
                {
                    break;
                }
                pre = p;
                p = p->next;
            }
            if(p != NULL)
            {
                if(p == list->first)//头插 第一个数就比我的Pnew大
                {
                    pnew->next = list->first;
                    list->first = pnew;
                }
                else
                {
                    pre->next = pnew;
                    pnew->next = p;
                }
            }
            else//p为null pnew最大
            {
                //pre->next = pnew;
                list->last->next = pnew;
                list->last = pnew;
            }
        }
        list->NodeNum++;
    }
    return list;//返回头结点 代表整个链表
}
相关文章
|
28天前
|
存储 Java
深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。
【10月更文挑战第16天】本文深入探讨了Java集合框架中的HashSet和TreeSet,解析了两者在元素存储上的无序与有序特性。HashSet基于哈希表实现,添加元素时根据哈希值分布,遍历时顺序不可预测;而TreeSet利用红黑树结构,按自然顺序或自定义顺序存储元素,确保遍历时有序输出。文章还提供了示例代码,帮助读者更好地理解这两种集合类型的使用场景和内部机制。
38 3
|
1月前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码,包括创建链表、插入、删除和打印等基本操作。
22 1
|
1月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
17 0
LeetCode第二十四题(两两交换链表中的节点)
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
40 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
1月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
46 0
|
1月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
2月前
|
存储 C语言
C语言程序设计核心详解 第九章 结构体与链表概要详解
本文档详细介绍了C语言中的结构体与链表。首先,讲解了结构体的定义、初始化及使用方法,并演示了如何通过不同方式定义结构体变量。接着,介绍了指向结构体的指针及其应用,包括结构体变量和结构体数组的指针操作。随后,概述了链表的概念与定义,解释了链表的基本操作如动态分配、插入和删除。最后,简述了共用体类型及其变量定义与引用方法。通过本文档,读者可以全面了解结构体与链表的基础知识及实际应用技巧。
|
3月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
2月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。

推荐镜像

更多