带头结点的单链表 与顺序表相同，链表也是一种线性表。与顺序表不同的是，链表的物理存储结构是用一组地址任意的存储单元存储数据。它不像顺序表那样需要占据一段地址连续
与顺序表相同，链表也是一种线性表。与顺序表不同的是，链表的物理存储结构是用一组地址任意的存储单元存储数据。它不像顺序表那样需要占据一段地址连续存储空间，而是将存储单元分散在内存的任意地址上。
在链表结构中，每个数据元素都存放在链表中的一个结点（node）上，而每个结点之间通过指针将其连接起来，这样就形成了一条如“链”的结构。
在C程序中，链表中的每个结点都可以用结构体来表示。在链表的每个结点中都必须有一个存放指针（地址）的域，也叫做指针域，指针域用来保存后继结点的地址，这样就将每个结点连接在一起，形成一条链。
一个链表中通常有一个表头，表头的用来保存第一个结点的地址。一个链表的最后一个结点的指针域要置空（NULL），因为它没有后继结点。
单链表的特点：
-
除“第一个”数据元素外，其余数据元素有且仅有一个 前驱元素 prev，
-
除“最后一个”数据元素外，其余数据元素有且仅有一个 后继元素 next
-
单链表的每个结点只有一个指针域
结点：每一个结点都包含两个部分：数据域和指针域。数据域用于存放数据元素，指针域用于存放后继结点的地址。
头指针：无论链表是否为空，头指针均不为空，头指针是链表的必要元素，头指针指向表头结点
头结点：放在第一个元素结点之前，其数据域一般无意义（当然也可以用来存放链表的长度等）
首元结点：第一个元素的结点，它是表头结点之后的第一个结点。
带头结点的单链表在后期的维护中更方便，头结点与其他结点一样拥有
数据域和指针域，头结点的数据域可以不存储任何信息，但也可以存储如链表长度等附加信息。 头结点的指针域用于保存首元结点的地址。带头结点的单链表的相关代码如下。
带头结点的单链表操作
单链表元素结点
单链表的结点（LNode）通常使用结构体表示。
typedef struct node
{
//结点数据域
int data;
//结点指针域
struct node *next;
}LNode;
单链表头结点
单链表的头结点（HNode）也使用结构体表示，头结点的指针域保存首元结点的地址，所以其指针域的类型需要与元素结点类型相同。
typedef struct head
{
//记录链表长度
int len;
LNode *next;
}HNode;
创建带头结点的单链表
创建一个带头结点的单链表，并返回一个指向单链表头结点的头指针。头指针用来标识单链表，保存单链表的入口地址。
/***************************************************************
函数功能: 创建带头结点的单链表
入口参数: 无
返回值: head（单链表头指针）
****************************************************************/
HNode *create_linked_list(void)
{
//创建一个头指针
HNode*head = NULL;
//创建一个头结点，并将头指针指向头结点
head = (HNode*)malloc(sizeof(HNode));
head->len = 0;
head->next = NULL;
return head;
}
打印单链表
打印单链表的所有元素。
/***************************************************************
函数功能: 打印带头结点的单链表
入口参数: head（单链表头指针)）
返回值: 无
****************************************************************/
void print_linked_list(HNode*head)
{
LNode *list = NULL;
list = head->next;
while(list)
{
printf("%d ", list->data);
list = list->next;
}
printf("\n");
}
例如：
单链表：1 2 3 4 5 6 7 8 9
输出：1 2 3 4 5 6 7 8 9
尾插法
在单链表最后一个结点之后插入一个新结点，并将新插入的结点的指针域置NULL，单链表最后一个结点没有后继节点。
/***************************************************************
函数功能: 在单链表最后一个结点之后插入一个结点
入口参数:
参数1：head（单链表头指针)
参数2：x(需要保存的元素数据)
返回值: head（单链表头指针）
****************************************************************/
HNode *add_linked_list_last(HNode *head,int x)
{
LNode *last_node = NULL;
last_node = head->next;
//判断是否为最后一个结点
while(last_node->next)
{
last_node=last_node->next;
}
//申请开辟一个结点空间
LNode *new_node = (LNode*)malloc(sizeof(LNode));
new_node->data = x;
new_node->next=NULL;
//将结点插入最后
last_node->next = new_node;
last_node = new_node;
head->len++;//链表长度加1
return head;
}
例如：
单链表：1 2 3 4 5 6 7 8 9
插入10后：1 2 3 4 5 6 7 8 9 10
头插法
在单链表首元结点之前插入一个新结点，并将头结点的指针指向新结点。
/***************************************************************
函数功能: 在单链表首元结点之前插入一个结点
入口参数:
参数1：head（单链表头指针)
参数2：x(需要保存的元素数据)
返回值: head（单链表头指针）
****************************************************************/
HNode *add_linked_list_first(HNode *head,int x)
{
LNode *new_node = NULL;
//申请开辟一个结点空间
new_node = (LNode*)malloc(sizeof(LNode));
new_node->data = x;//保存需要插入的元素
new_node->next = NULL;
//将新结点插入到第一个结点之前
new_node->next = head->next;
head->next = new_node;
head->len++;
return head;
}
例如：
单链表：2 4 7 8 9 1
插入11后：11 2 4 7 8 9 1
删除单链表中第N个结点
删除单链表中的第N个结点，需要将第N-1个结点的后继指针指向第N+1个结点，然后将第N个结点的后继指针置NULL，然后再释放第N个结点的空间。
/***************************************************************
函数功能: 删除单链表中的第N个结点
入口参数:
参数1：head（单链表头指针)
参数2：n（第N个结点）
返回值: head（单链表头指针）
****************************************************************/
HNode *delete_theN_node(HNode *head,int n)
{
//判断n是否大于链表长度
if (n > head->len || n < 1)
{
printf("该结点不存在！\n");
return 0;
}
LNode *now_node = NULL;
LNode *prev_node = NULL;
now_node = head->next;
//删除第一个结点
if (1 == n)
{
head->next = now_node->next;
now_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
}
//删除最后一个结点
else if(head->len == n)
{
while(--n)
{
prev_node = now_node;
now_node = now_node->next;
}
prev_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
}
//删除中间某个结点
else
{
while(--n)
{
prev_node = now_node;
now_node = now_node->next;
}
prev_node->next = now_node->next;
now_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
}
return head;
}
例如：
单链表：2 4 7 8 9 1
删除第2个结点后： 2 7 8 9 1
删除单链表中元素为X的结点
前提：单链表中不包含重复元素。
/***************************************************************
函数功能: 删除单链表中元素为X的结点（单链表中不包含重复元素）
入口参数:
参数1：head（单链表头指针)
参数2：x(删除的元素数据)
返回值: head（单链表头指针）
****************************************************************/
HNode *delete_num(HNode *head,int x)
{
LNode *now_node = NULL;
LNode *prev_node = NULL;
now_node = head->next;
//判断X是不是第一个结点的元素
if(x == now_node->data){
head->next = now_node->next;
now_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
return head;
}
//判断中间
while(now_node->next)
{
if(x == now_node->data){
prev_node->next = now_node->next;
now_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
return head;
}
else{
prev_node = now_node;
now_node = now_node->next;
}
}
//判断最后一个结点的元素是否为X
if(x == now_node->data){
prev_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
}
else{
printf("链表中无%d这个元素\n",x);
return 0;
}
return head;
}
例如：
单链表：2 4 7 8 9 1
删除元素9后：2 4 7 8 1
删除单链表中连续重复的元素只保留一个
/***************************************************************
函数功能: 删除单链表中的重复元素
入口参数: head（单链表头指针)
返回值: head（单链表头指针）
****************************************************************/
HNode *delete_repetitive_num(HNode*head)
{
LNode *now_node = NULL;
LNode *prev_node = NULL;
now_node = head->next;
while(now_node->next){
prev_node = now_node;
now_node = now_node->next;
//判断相邻两个元素是否相等
if(prev_node->data == now_node->data){
prev_node->next = now_node->next;
now_node->next = NULL;
free(now_node);
now_node = prev_node;
}
}
return head;
}
例如：
单链表：1 1 2 2 3 3 3 5 5
删除后：1 2 3 5
销毁单链表
销毁除头结点之外的结点。
/***************************************************************
函数功能: 销毁除头结点之外的结点
入口参数: head（单链表头指针)）
返回值: head（单链表头指针）
****************************************************************/
HNode *destroy_linked_list(HNode *head)
{
LNode *now_node = NULL;
//从第一个元素结点开始销毁
while(head->next){
now_node = head->next;
if(now_node->next == NULL){
head->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
break;
}
head->next = now_node->next;
now_node->next = NULL;
free(now_node);
now_node = NULL;
head->len--;
}
return head;
}
单链表逆置
说明：此逆置不改变结点原来的位置，只交换两个结点存储的数据。
/***************************************************************
函数功能: 逆置单链表（交换元素数据）
入口参数: head（单链表头指针)
返回值: head（单链表头指针）
****************************************************************/
HNode *reverse_linked_list(HNode *head)
{
int n = head->len;
int temp;
int i,j;
printf("链表长度：%d\n",n);
LNode *first_node = NULL;
LNode *temp1_node = NULL;
LNode *temp2_node = NULL;
first_node = head->next;
temp1_node = first_node;
//如果链表元素个数为奇数则(n-1)%2,反之n%2
if(n%2 == 0||(n-1)%2==0)
{
//不管是奇数个元素还是偶数个元素，都只需要交换n/2次
//奇数个元素其最中间那一个元素不需要交换
for(i=0;i<n/2;i++)
{
temp2_node = first_node;
for(j=0;j<n-i-1;j++)
{
temp2_node = temp2_node->next;
}
temp = temp1_node->data;
temp1_node->data = temp2_node->data;
temp2_node->data = temp;
//指向第一个结点的指针往后移动一个
temp1_node = temp1_node->next;
}
}
return head;
}
例如：
单链表：3 2 4 5 10 8 1
逆置后：1 8 10 5 4 2 3
将两个链表归并为一个有序链表
/***************************************************************
函数功能: 将两个链表归并为一个有序链表
入口参数:
参数1：head1（单链表头指针)
参数2：head2（单链表头指针）
返回值: head3（单链表头指针）
****************************************************************/
HNode *combine_linked_list(HNode*head1,HNode*head2)
{
HNode *head3 = NULL;
LNode *now_node = NULL;
LNode *next_node = NULL;
int flag = 0;
int temp;
int n;
now_node = head1->next;
//找head1的最后一个结点
while(now_node->next){
now_node = now_node->next;
}
//连接head1和head2
now_node->next = head2->next;
//合并
head3 = head1;
head3->len = (head1->len) + (head2->len);
n = head3->len;
//冒泡排序
for(int i=0;i<n-1;i++)
{
now_node = head3->next;
next_node = now_node;
for(int j=0;j<n-1-i;j++)
{
next_node = next_node->next;
if(now_node->data > next_node->data)
{
temp = now_node->data;
now_node->data = next_node->data;
next_node->data = temp;
flag = 1;
}
now_node = now_node->next;
}
if(flag == 0){
break;
}
}
return head3;
}
例如：
单链表1：5 4 3 2 1
单链表2：9 6 8 7
归并后：1 2 3 4 5 6 7 8 9
更新第N个结点的数据
/***************************************************************
函数功能: 修改第N个结点的数据
入口参数:
参数1：head（单链表头指针)
参数2：n（第N个结点）
参数3：更新的数据
返回值: head3（单链表头指针）
****************************************************************/
HNode *change_theN_node(HNode *head,int n,int x)
{
//判断n是否大于链表长度
if (n > head->len || n < 1)
{
printf("该结点不存在！\n");
return 0;
}
LNode *now_node = NULL;
now_node = head->next;
while(--n)
{
now_node = now_node->next;
}
now_node->data = x;
return head;
}
例如：
单链表：5 4 3 2 1
更新第2个结点数据为12：5 12 3 2 1
查找值为X的元素
/***************************************************************
函数功能: 查找值为X的元素
入口参数:
参数1：head（单链表头指针)
参数2：x（查找的值）
返回值: 0 表示不存在，1表示存在
****************************************************************/
int find_data_linked_list(HNode *head,int x)
{
LNode *now_node = NULL;
now_node = head->next;
while(now_node){
if(now_node->data == x){
return 1;
}
now_node = now_node->next;
}
return 0;
}
主函数参考
int main(int argc, char const *argv[])
{
int num;
int n;
//创建一个头指针用于标识链表
HNode *phead = NULL;
//创建一个带头结点的单链表
phead = create_linked_list();
LNode*new_node = NULL;
LNode*last_node = NULL;
printf("请向单链表输入数据：");
do{
scanf("%d",&num);
new_node = (LNode*)malloc(sizeof(LNode));
new_node->data = num;
new_node->next = NULL;
if (phead->next == NULL)
{
phead->next = new_node;
last_node = new_node;
phead->len++;
}
else
{
last_node->next = new_node;
last_node = new_node;
phead->len++;
}
}while(getchar() != '\n');
//打印链表所有元素
printf("链表长度：%d\n",phead->len);
printf("链表所有元素：");
print_linked_list(phead);
//尾插法
//头插法
//删除第N个结点
//查找数据
return 0;
}
注意：该文章仅供学习交流不得转载商用。