二、C语言实现头结点的单链表

1、头结点单链表（逻辑图）

2、声明 

#pragma once


//结构声明
typedef int DataType;

//结点声明
typedef struct Node
{
	union //采用联合体的形式，开辟结点时二选一
	{
		DataType data;	//普通节点存储数据
		int length;     //头结点存储单链表的长度
	};

	struct Node* next;  //定义指向下一个结点的指针
}Linklist;



//方法声明

//单链表的初始化(头结点的初始化)
bool InitLinkList(Linklist* head);

//求单链表的长度
int LenghtOfLinkList(Linklist* head);

//申请新结点
Linklist* ApplyNewNode(Linklist* node, DataType value);

//插入：按位置插入（头结点与第一个结点之间的位置为0位置,最大位置不超过pos）
bool InsertOfPos(Linklist* head, DataType value, int pos);

//头插法
bool InsertOfHead(Linklist* head, DataType value);
//尾插法
bool InsertOfRear(Linklist* head, DataType value);


//按位置删除
bool DeleteOfPos(Linklist* head, int pos);
//头删法
bool DeleteOfHead(Linklist* head);
//尾删法
bool DeleteOfRear(Linklist* head);

//输出打印
void ShowAllNode(Linklist* head);

//单链表的销毁
bool DestroyList(Linklist* head);

3、方法实现

#include<stdio.h>
#include"headList.h"
#include<stdlib.h>
#include<malloc.h>

//单链表的初始化(头结点的初始化)
bool InitLinkList(Linklist* head)
{
	if (head == NULL) return false;

	head->length = 0;   //头结点开始存储单链表的结点个数为0
	head->next = NULL;  //头结点的next指向空

	return true;
}

//求单链表的长度
int LenghtOfLinkList(Linklist* head)
{
	if (head == NULL) exit(0);//exit(0);调用<stdlib.h>头文件

	return head->length;

}

//申请新结点
Linklist* ApplyNewNode(Linklist *node,DataType value)
{
	Linklist* new_node = (Linklist*)malloc(sizeof(Linklist));
	
	if (new_node == NULL) return NULL;

	new_node->data = value;
	new_node->next = node;

	return new_node;//返回申请成功的地址
}

//插入：按位置插入（头结点与第一个结点之间的位置为0位置,最大位置不超过pos）
bool InsertOfPos(Linklist* head, DataType value, int pos)
{
	if (head == NULL) return false;

	if (pos<0 || pos>LenghtOfLinkList(head)) return false;

	//找到pos位置的直接前驱
	Linklist* p = head;  //让p指向头结点

	while (pos)       //循环遍历找到pos的直接前驱
	{
		p = p->next;
		pos--;
	}

	Linklist* new_node =ApplyNewNode(p->next,value);//申请空间指的是让新结点指向p的直接后继结点（在堆区开辟新结点的空间）
	
	if (new_node == NULL) return NULL;
	p->next = new_node;
	head->length++;

	return true;
}

//头插法
bool InsertOfHead(Linklist* head, DataType value)
{
	if (head == NULL) return false;

	Linklist* new_node = ApplyNewNode(head->next, value);//与上面同理，让新结点的next域指向head的直接后继
	if (new_node == NULL) return false;

	head->next = new_node;   //连接前驱与新结点
	head->length++;          //长度++

	return true;
}


//尾插法
bool InsertOfRear(Linklist* head, DataType value)
{
	return InsertOfPos(head, value, head->length);
}

//按位置删除
bool DeleteOfPos(Linklist* head, int pos)
{
	if (head == NULL || pos<0 || pos>=head->length) return false;

	Linklist* p = head;
	//同理寻找pos位置的直接前驱
	while (pos)
	{
		p = p->next;
		pos--;
	}

	Linklist* q = p->next;//让q指向p的直接后继位置
	//将p->next指向q位置结点的直接后继
	p->next = q->next;

	free(q);
	//防止出现野指针
	head->length--;
	return true;
}


//头删法
bool DeleteOfHead(Linklist*head)
{
	return DeleteOfPos(head, 0);
}

//尾删法
bool DeleteOfRear(Linklist* head)
{
	if (head == NULL) return false;

	Linklist* p = head;
	Linklist* q = head->next;
	while (!q->next == NULL)
	{
		p = p->next;
		q = q->next;
	}
	free(q);
	p->next = NULL;//新尾结点置空
	head->length--;

	return true;
}

//按值删除，含有重复值的情况
bool DeleteOfValue(Linklist*head,DataType value)
{
	if (head == NULL) return false;

	Linklist* p = head;
	Linklist* q = head->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;
}


//输出打印
void ShowAllNode(Linklist* head)
{
	if (head == NULL) exit(0);

	Linklist* p = head->next;

	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

//销毁单链表
bool DestroyList(Linklist* head)
{
	if (head == NULL) exit(0);

	while (!IsEmpty(head))
	{
		DeleteOfHead(head);
	}
	return true;
}

4、主函数测试

#include<stdio.h>
#include"headList.h"

int main()
{
	Linklist list;//在栈区定义一个单链表list
	InitLinkList(&list);

	printf("插入0-9\n");
	for (int i = 0; i < 10; i++)
	{
		InsertOfPos(&list,i,i);
	}
	ShowAllNode(&list);

	printf("头插法\n");
	InsertOfHead(&list,10);
	ShowAllNode(&list);

	printf("尾插法\n");
	InsertOfRear(&list, 66);
	ShowAllNode(&list);
	
	printf("按3位置删除\n");
	DeleteOfPos(&list,3);
	ShowAllNode(&list);

	printf("头删法\n");
	DeleteOfHead(&list);
	ShowAllNode(&list);

	printf("尾删法\n");
	DeleteOfRear(&list);
	ShowAllNode(&list);

	DestroyList(&list);
	

	return 0;
}

5、结束语

There is no development physically or intellectually without effort.

没有努力，就不会有身体上或智能上的成长。

                                                                                                                                                                                                                                                                           ——2021.03.10