带头结点单链表、不带头结点单链表（头指针单链表）

article/2025/11/9 6:43:06

1、头结点和头指针的区别

1.1区别：
头指针表明了链表的结点，可以唯一确定一个单链表。
头指针指向链表的第一个结点，其记录第一个存储数据的结点的地址。
头结点是点链表的第一个结点，若单链表有头结点，则头指针指向头结点；若单链表没有头结点，则指针指向第一个结点。
一个单链表可有没有头结点，但不能没有头指针。
头结点的数据域可以不存储任何数据。

1.2记录链表的类型不同：
头指针是一个4字节的指针，记录第一个存储数据的结点的地址。
头结点是一个结构体变量，使用这个变量的next域来记录第一个存储数据的结点的地址，头结点的data域可以使用联合体的方式记录链表的长度。

1.3各个操作方法的定义不同
如果是头指针实现，则方法中国接受这个链表的类型必须是二级指针。
头指针实现使用一级指针就OK。
在这里插入图片描述

2、头结点单链表

链表和顺序表的区别：
（1）链表在逻辑存储上是连续的，在物理存储上是不连续的。
（2）单链表属于链表中的一种，每一个存储数据的节点除了存储数据本身之外，还要存储其直接后继结点的地址。
在这里插入图片描述
例：32位系统存储10个整形（int 4个字节）数据：
顺序表存储 ：总共需要堆区空间：40个字节
单链表存储： 总共需要堆区空间：80个字节

单链表的实现

头结点：
在这里插入图片描述
头指针——在实现代码中会使用二级指针
在这里插入图片描述
方法的声明：

#include<stdio.h>
typedef int DataType;typedef struct Node
{//数据类型union//结合体、联合体{DataType data;//存储元素int length;//存储元素个数};//结点指针类型struct Node *next; 
}LinkList;//初始化
void InitLinkList(LinkList *head);//销毁
void DestroyLinkList(LinkList *head);//按位置插入插入
bool InsertPos(LinkList *head,DataType value,int pos);//头插
bool InsertFront(LinkList *head,DataType value);//尾插
bool InsertRear(LinkList *head,DataType value);//按位置删除
bool DeletePos(LinkList *head,int pos);//头删
bool DeleteFront(LinkList *head);//尾删
bool DeleteRear(LinkList *head);//按值删除
bool DeleteValue(LinkList *head,DataType value);//判空
bool IsEmpty(LinkList *head);//求长度
int GetLength(LinkList *head);//输出
bool PrintLinkList(LinkList *head);

方法的实现：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include"head.h"static LinkList *ApplyNode(DataType value,LinkList *point )
{LinkList *new_node=(LinkList *)malloc(sizeof(LinkList));if(new_node==NULL) return NULL;new_node->data=value;new_node->next=point;return new_node;
}void InitLinkList(LinkList *head)
{if(head==NULL) exit(0);head->length=0;head->next=NULL;
}int GetLength(LinkList *head)
{if(head==NULL) exit(0);return head->length;
}bool InsertPos(LinkList *head,DataType value,int pos)
{if(head==NULL) exit(0);if(pos<0||pos>GetLength(head)) return false;LinkList *p=head;while(pos){p=p->next;pos--;}LinkList *new_node=ApplyNode(value,p->next);//生成新的结点if(new_node==NULL) return false;p->next=new_node;head->length++;return true;}bool InsertFront(LinkList *head,DataType value)
{if(head==NULL) exit(0);LinkList *new_node=ApplyNode(value,head->next);if(new_node==NULL) return false;head->next=new_node;head->length++;return true;
}bool InsertRear(LinkList *head,DataType value)
{if(head==NULL) exit(0);return InsertPos(head,value,GetLength(head));
}bool DeletePos(LinkList *head,int pos)
{if(head==NULL) exit(0);if(pos<0||pos>=head->length) return false;LinkList *p=head;while(pos){p=p->next;pos--;}LinkList *q=p->next;p->next=q->next;free(q);head->length--;return true;
}bool DeleteFront(LinkList *head)
{if(head==NULL) exit(0);return DeletePos(head,0);
}bool DeleteRear(LinkList *head)
{if(head==NULL) exit(0);return DeletePos(head,GetLength(head)-1);
}bool DeleteValue(LinkList *head,DataType value)
{if(head==NULL) exit(0);LinkList *p=head;LinkList *q=p->next;while(q!=NULL){if(q->data==value){p->next=q->next;free(q);q=p->next;head->length--;}else{p=q;q=q->next;}}return true;
}bool IsEmpty(LinkList *head)
{ if(head==NULL) exit(0);return head->length==0;
}bool PointLinkList(LinkList *head)
{if (head == NULL) exit(0);LinkList *p = head->next;while (p != NULL){printf("%d  ", p->data);p = p->next;}printf("\n");
}
void DestroyLinkList(LinkList *head)
{if(head=NULL) exit(0);while(IsEmpty(head)!=NULL){DeleteFront(head);}
}//找到第K个结点
LinkList *FindK(LinkList *head, int k)  //  0< k <= length
{if (head == NULL)  return NULL;if (k <= 0 || k > head->length)  return NULL;int pos = head->length - k + 1;LinkList *p = head;while (pos){p = p->next;pos--;}return p;
}//  不能直接获得length的情况
LinkList *FindOfK2(LinkList *head, int k)
{if (head == NULL)  return NULL;if (k <= 0)  return NULL;LinkList *p = head;while (k && p != NULL){p = p->next;k--;}if (p == NULL)  return NULL;LinkList *q = head;while (p != NULL){p = p->next;q = q->next;}return q;
}//O(1)删除非尾结点p
bool DeletePos1(LinkList *head,int pos)
{if(head==NULL) return false;if(pos<0||pos>=head->length) return false;LinkList *p=head;while(pos){p=p->next;pos--;}LinkList *q=p->next;p->next=q->next;free(q);head->length--;return true;}//将单链表逆置  -- 结点逆置
void Reverse(LinkList *head)
{if(head==NULL) return;LinkList *p=NULL;LinkList *q=head->next;LinkList *s=q->next;while(q!=NULL){q->next=p;p=q;q=s;if(s!=NULL) s=s->next;}head->next=p;
}
//判断两个结点是否相交，返回相交的第一个结点
LinkList *IsIntersect(LinkList *head1,LinkList *head2)
{if(head1==NULL||head2==NULL) return false;LinkList *p=head1;LinkList *q=head2;if(head1->length>head2->length){for(int i=0;i<head1->length-head2->length;i++){p=p->next;}}else{for(int i=0;i<head2->length-head1->length;i++){q=q->next;}}while(p!=q){p=p->next;q=q->next;}return p;
}LinkList *IsIntersect2(LinkList *head1, LinkList *head2)
{if (head1 == NULL || head2 == NULL)  return NULL;LinkList *p = head1;LinkList *q = head2;while (p != q){if (p != NULL) p = p->next;else  p = head2;if (q != NULL) q = q->next;else q = head1;
// 		p = p != NULL ? p->next : head2;
// 		q = q != NULL ? q->next : head1;}return p;
}
//判断单链表是否有环，如果有，返回入环的第一个结点
LinkList *IsLoop(LinkList *head)
{if(head==NULL) return NULL;LinkList *fast=head;LinkList *slow=head;while(fast!=NULL&&fast->next!=NULL){fast=fast->next->next;slow=slow->next;if(fast==slow) break;}LinkList *p=fast;LinkList *q=slow;while(q!=p){p=p->next;q=q->next;}return p;
}int main()
{LinkList list;InitLinkList(&list);InsertFront(&list,1);InsertPos(&list,2,1);InsertRear (&list,3);InsertRear (&list,4);InsertRear (&list,5);DeletePos(&list,1);printf("单链表长度为:%d\n",GetLength(&list));printf("第一次输出：");PointLinkList(&list);DeleteValue(&list,4);InsertPos(&list,2,1);printf("第二次输出：");PointLinkList(&list);return 0;
}

3、头指针单链表

在这里插入图片描述
方法的声明：

#include<stdio.h>
typedef  int  DataType;typedef struct Node
{DataType    data;    //   记录本结点存储的数据struct Node  *next;  //   记录下一个结点的地址
}LinkList;// 初始化
void  InitLinkList(LinkList **phead);
//  插入
bool InsertLinkList(LinkList **phead, DataType value, int pos);bool InsertLinkListHead(LinkList **phead, DataType value);bool InsertLinkListRear(LinkList **phead, DataType value);//  删除
bool DeleteLinkList(LinkList **phead, int pos);bool DeleteLinkListHead(LinkList **phead);bool DeleteLinkListRear(LinkList **phead);//  长度
int GetLength(LinkList **phead);
//  判空
bool  Empty(LinkList **phead);
//  销毁
void  DestroyLinkList(LinkList **phead);//  显示
void  ShowLinkList(LinkList **phead);

方法的实现：

#include "head.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>static LinkList *ApplyNewNode(DataType value, LinkList *next)
{LinkList *new_node = (LinkList *)malloc(sizeof(LinkList));if (new_node == NULL)  exit(0);new_node->data = value;new_node->next = next;return new_node;
}void  InitLinkList(LinkList **phead)  //  phead中存储的值就是main方法中的phead变量的地址
{if (phead == NULL)  exit(0);*phead = NULL;
}int GetLength(LinkList **phead)
{if (phead == NULL)  exit(0);int length = 0;LinkList *p = *phead;while (p != NULL){length++;p = p->next;}return length;
}bool InsertLinkList(LinkList **phead, DataType value, int pos)
{if (phead == NULL)  exit(0);if (pos < 0 || pos > GetLength(phead))  return false;//  在头指针的后面插入新结点，头插法必须特殊处理： 因为只有在这需要修改头指针的值if (pos == 0)  return InsertLinkListHead(phead, value);//  头插LinkList *p = *phead;while (pos > 1){p = p->next;pos--;}//  while循环结束后，就需要在p所指向的结点的后面插入新结点/* LinkList *new_node = ApplyNewNode(value, p->next); p->next = new_node;*/p->next = ApplyNewNode(value, p->next);return true;
}bool InsertLinkListHead(LinkList **phead, DataType value)
{if (phead == NULL)  exit(0);*phead = ApplyNewNode(value, *phead);return true;
}bool InsertLinkListRear(LinkList **phead, DataType value)
{if (phead == NULL)  exit(0);//  链表本身是空的，尾插相当于头插if (Empty(phead))  return InsertLinkListHead(phead, value);LinkList *p = *phead;while (p->next != NULL)  p = p->next;  //  while循环结束后，p就是最后一个结点p->next = ApplyNewNode(value, NULL);return true;
}bool  Empty(LinkList **phead)
{if (phead == NULL)  exit(0);if (*phead == NULL)  return true;return false;
}bool DeleteLinkList(LinkList **phead, int pos)
{if (phead == NULL)  exit(0);if (pos < 0 || pos >= GetLength(phead))  return false;if (pos == 0)  return DeleteLinkListHead(phead);LinkList *p = *phead;  //  p指向的是第一个数据结点while (pos > 1){p = p->next;pos--;}//  while循环结束后，要删除的结点时p->nextLinkList *q = p->next;p->next = q->next;free(q);return true;
}bool DeleteLinkListHead(LinkList **phead)
{if (phead == NULL)  exit(0);if (Empty(phead))  return false;LinkList *p = *phead;*phead = p->next;free(p);return true;
}bool DeleteLinkListRear(LinkList **phead)
{if (phead == NULL)  exit(0);if (Empty(phead))  return false;LinkList *front = NULL;LinkList *p = *phead;while (p->next != NULL){front = p;p = p->next;}if (front == NULL)  return DeleteLinkListHead(phead);front->next = NULL;free(p);return true;
}void  DestroyLinkList(LinkList **phead)
{if (phead == NULL)  exit(0);while (!Empty(phead)){DeleteLinkListHead(phead);}
}void  ShowLinkList(LinkList **phead)
{if (phead == NULL)  exit(0);LinkList *p = *phead;while (p != NULL){printf("%d  ", p->data);p = p->next;}printf("\n");
}int main()
{LinkList *list;InitLinkList(&list);InsertLinkListHead(&list,6);InsertLinkListHead(&list,5);InsertLinkListHead(&list,4);InsertLinkListHead(&list,3);InsertLinkListHead(&list,2);InsertLinkListHead(&list,1);DeleteLinkList (&list,5);printf("第一次输出：");ShowLinkList(&list);InsertLinkList(&list,6,5);InsertLinkListRear(&list,7);DeleteLinkListHead(&list);DeleteLinkListRear(&list);printf("第一次输出：");ShowLinkList(&list);return 0;
}

头指针单链表操作时的转化

因为头结点实现的单链表相比于头指针实现的单链表，操作时特殊情况少一些。在实现一些有指针的单链表的操作时，可以虚拟构建出一个头结点。

bool Funaction(LinkList **phead)
{//虚拟出来的头结点LinkList *head=(LinkList *)malloc(sizeof(LinkList));head->next =*phead;LinkList *p=head;//p指向头结点LinkList *q=p->next;while(q->next!=NULL){p=q;q=q->next;}p->next=q->next ;free(q);*phead=head->next;free(head);
}

http://chatgpt.dhexx.cn/article/bRQV5OW8.shtml

相关文章

不带头结点的单链表------C语言实现

不带头结点的单链表------C语言实现

1 /****************************************************/ 3 File name&#xff1a;no_head_link.c4 Author&#xff1a;SimonKly Version:0.1 Date: 2017.5.205 Description&#xff1a;不带头节点的单链表6 Funcion List: 7 ***************************************…
阅读更多...
单链表的头结点的作用

单链表的头结点的作用

问题&#xff1a;在单链表中使用“头结点”&#xff0c;这个哑结点始终是链表的第一个元素&#xff0c;这个技巧的利与弊&#xff1f; 链表中第一个结点的存储位置叫做头指针&#xff0c;那么整个链表的存取就必须从头指针开始进行了。之后的每一个结点&#xff0c;其实就是上…
阅读更多...
【数据结构】单链表之带头结点的单链表

【数据结构】单链表之带头结点的单链表

一、单链表相关知识点介绍&#xff1a; 1. 结点&#xff1a;结点就是单链表中研究的数据元素&#xff0c;结点中存储数据的部分称为数据域&#xff0c;存储直接后继地址的部分称为指针域。 2. 头结点&#xff1a;引入头结点的目的是&#xff0c;将链表首元结点的插入和删除操作…
阅读更多...
【链表】带头节点和不带头节点单链表的区别

【链表】带头节点和不带头节点单链表的区别

目录 &#x1f354;当链表的结点只包含一个指针域时&#xff0c;叫做单链表 &#x1f354;不论带不带头节点&#xff0c;所有的链表都要有个头指针&#xff01; &#x1f35f;带头结点的链表的头指针指向的是头结点&#xff0c;头结点的指针域指向首元结点 &#x1f35f;不带…
阅读更多...
带头结点的单链表的操作（C语言）

带头结点的单链表的操作（C语言）

初始化 先了解头结点 头结点是一个特殊的结点&#xff0c;它的数据域不存储信息&#xff0c;通常情况下&#xff0c;头指针指向的结点为头结点&#xff0c;由于头结点不存储信息&#xff0c;所以不是数据结构中的实际结点&#xff0c;第一个实际结点其实是head->next指示的…
阅读更多...
单链表（不带头结点）

单链表（不带头结点）

单链表不带头结点结构体设计&#xff1a; //不带头结点的结构体设计&#xff1a; typedef int ELEM_TYPE;//有效数据节点结构体设计 typedef struct Node {ELEM_TYPE data;//数据域 &#xff08;1.头结点&#xff1a;不保存任何数据 2.有效数据节点&#xff1a;保存有效值…
阅读更多...
数据结构之不带头结点的单链表

数据结构之不带头结点的单链表

我们都知道不管是单链表、双向链表还是循环链表&#xff0c;都带有头结点&#xff0c;这个头结点相当于一个起始的位置。我们在设计带头结点的单链表的时候&#xff0c;我们会在主函数中设计一个头结点&#xff0c;并把它的指针域置为空&#xff0c;这样我们就可以进行增删查改…
阅读更多...
数据结构--带头结点的单链表

数据结构--带头结点的单链表

单链表分为&#xff1a;带头结点和不带头结点&#xff0c;不带头结点的单链表需要用到二级指针&#xff0c;容易出错。 1、结构体设计 typedef int ELEM_TYPE; //有效数据节点结构体设计&#xff08;头结点借用&#xff09; typedef struct Node {ELEM_TYPE data;//数据域 &…
阅读更多...
带头结点的单链表的总结

带头结点的单链表的总结

线性表的链式存储是用若干地址分散的存储单元存储数据元素&#xff0c;逻辑上相邻的数据元素在物理位置上不一定相邻。 带头结点的单链表是指&#xff0c;在单链表的第一个结点之前增加一个特殊的结点&#xff0c;称为头结点。 头结点的作用&#xff1a;使所有链表&#xff08;…
阅读更多...
单链表的创建（带头结点和不带头结点）

单链表的创建（带头结点和不带头结点）

伪代码&#xff1a; 创建结点 创建头结点(单独定义一个结构体来保存单链表的首地址和尾地址还有链表的长度) 创建带头结点的单链表 注意&#xff1a;创建头结点中的首尾指针都要指空&#xff0c;长度等于0&#xff1b; 从终端接收数据 创建结点保存数据&#xff1a; 创建的节点…
阅读更多...
单链表———带头结点跟不带头结点的区别

单链表———带头结点跟不带头结点的区别

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、单链表&#xff1a;带头结点跟不带头结点二、使用步骤总结 前言 数据结构中单链表的创建 带头结点跟不带头结点的区别 一、单链表&#xff1a;带头结点跟…
阅读更多...
【数据结构】带头结点的单链表

【数据结构】带头结点的单链表

文章目录 一、单链表的概念二、结构体声明&#xff1a;三、函数1.购买节点2.释放节点3.单链表的初始化4.判空函数5.获取单链表有效值个数6.按数据查询&#xff08;返回含有此数据节点的前驱&#xff09;7.按数据查询&#xff08;返回含有当前数据的节点&#xff09;8.按pos位置…
阅读更多...
【考研】分清带头结点和不带头结点的单链表

【考研】分清带头结点和不带头结点的单链表

CSDN话题挑战赛第2期 参赛话题&#xff1a;学习笔记 前言 为分清带结点与不带头结点的单链表操作&#xff0c;本文以图文和表格形式描述了两者之间的区别。考研中&#xff0c;数据结构的单链表操作是重要考点&#xff0c;其中&#xff0c;比较常考带头结点的链表操作。 所以&…
阅读更多...
【带头结点的单链表】

【带头结点的单链表】

带头结点的单链表 前言一、带头结点的单链表结构体设计1. 带头结点的单链表2. 结构体声明 二、函数实现1. 初始化2. 申请新节点3. 头插4. 尾插5. 按位置插入6. 头删7. 尾删8. 销毁 总结 前言 单链表的概念&#xff1a; 单链表是一种链式存取的数据结构&#xff0c;用一组地址…
阅读更多...
带头结点单链表 (详解)

带头结点单链表 (详解)

单链表结构体 结构体后的*List是一个指向结构体的指针类型&#xff0c;我们通过它来定义该类型的指针。 如&#xff1a;List p ;  则这个p就是指向LinkedList结构体的一个指针&#xff0c;也就是单链表的头指针。&#xff08;所以说头指针是必然存在的&#xff0c;但单链表不…
阅读更多...
数据结构-带头节点的单链表（C语言）超详细讲解

数据结构-带头节点的单链表（C语言）超详细讲解

前面我们学到线性表的顺序存储结构&#xff08;顺序表&#xff09;&#xff0c;发现它有着明显的缺点&#xff1a;插入和删除元素时需要频繁的移动元素&#xff0c;运算效率低。必须按事先估计的最大元素个数申请连续的存储空间。存储空间估计大了&#xff0c;造成浪费空间&…
阅读更多...
Windows配置端口转发绕过samba 445端口限制共享linux磁盘

Windows配置端口转发绕过samba 445端口限制共享linux磁盘

概述 Samba是在Linux和UNIX系统上实现SMB协议的一个免费软件。SMB&#xff08;Server Messages Block&#xff0c;信息服务块&#xff09;是一种在局域网上共享文件和打印机的一种通信协议&#xff0c;它为局域网内的不同计算机之间提供文件及打印机等资源的共享服务。SMB协议…
阅读更多...
Linux安装samba服务

Linux安装samba服务

个人推荐: &#x1f4e2;&#x1f4e2;&#x1f4e2; 前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下 "通俗易懂&#xff0c;风趣幽默"&#xff0c;感觉非常有意思,忍不住分享一下给大家。点击跳转到教程。 一&#xff1a;使用到的Linux指令 1:检查是否…
阅读更多...
samba服务

samba服务

目录 一&#xff1a;samba概述 1.1samba简介 1.2samba的监听端口 1.3samba的进程 1.4samba安全级别 二&#xff1a;samba服务的特点 三&#xff1a;samba的主要作用 四&#xff1a;常见文件服务器软件的对比 五&#xff1a;samba配置文件 5.1samba主配置文件 5.2常用…
阅读更多...
Samba配置详解

Samba配置详解

一、简介 Samba是一个能让Linux系统应用Microsoft网络通讯协议的软件&#xff0c;而SMB是Server Message Block的缩写&#xff0c;即为服务器消息块 &#xff0c;SMB主要是作为Microsoft的网络通讯协议&#xff0c;后来Samba将SMB通信协议应用到了Linux系统上&#xff0c;就形成…
阅读更多...
推荐文章

Copyright @ 2022~2023