C语言实现无头单链表详解

2024-04-02 19:04:59 512人浏览泡泡鱼

摘要

目录链表的结构体描述(节点)再定义一个结构体(链表) 断言处理 & 判空处理创建链表创建节点头插法打印链表尾插法指定位置插入头删法尾删法&n

链表的结构体描述(节点)

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>       
typedef int DataType;
//节点
typedef struct node        
{
	DataType data;
	struct Node* next;
}NODE,*LPNODE;

再定义一个结构体(链表)

通过记录头节点和尾节点的方式去描述链表

typedef struct list 
{
	LPNODE frontNode;        //头节点
	LPNODE backNode;         //尾节点
	int curSize;	         //当前节点个数
}LIST,*LPLIST;

断言处理 & 判空处理

如果 list 为空，会引发中断(申请内存可能失败)

防御性编程，如果申请内存失败，操作无效，NULL 里面没有 frontNode，backNode，curSize，存在安全隐患C6011：取消对 NULL 指针"list"的引用

如果申请内存失败，assert()直接让程序直接中断，并且告诉你程序断在哪一行

#include<assert>    //断言处理宏
   #define assert(expression) (void)(  \
            (!!(expression)) ||        \
(_wassert(_CRT_WIDE(#expression), _CRT_WIDE(__FILE__), (unsigned)(__LINE__)), 0) \
        )
 
LPLIST  createList() 
{
	LPLIST list = (LPLIST)malloc(sizeof(LIST)); 
    list = NULL;                        //list为空 引发中断
	assert(list);		           
    //if(list == NULL)
    //return NULL;                      //可以替换
	list->frontNode = NULL;                     
	list->backNode = NULL;
	list->curSize = 0;                         
	return list;
}
 
//abort() has been called line 25

创建链表

描述链表最初的状态

LPLIST  createList() 
{
	LPLIST list = (LPLIST)malloc(sizeof(LIST)); //用结构体变量去描述 做动态内存申请
	assert(list);		                   
	list->frontNode = NULL;                     //链表刚开始是空的 头尾节点指向空
	list->backNode = NULL;
	list->curSize = 0;                          //当前元素个数为0
	return list;
}

创建节点

LPNODE createNode(int data) 
{
	LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
	assert(newNode);
    //初始化数据
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}

头插法

插入一个节点，节点插在原表头前面，表头会改变，在1(表头)前面插入666(数据)

把新节点的 next 指针指向原来的表头

把原来表头指针从原来的位置挪到新节点的位置

//插入的链表 插入的数据
void push_front(LPLIST list,int data) 
{
	LPNODE newNode = createNode(data);    //创建新节点
	newNode->next = list->frontNode;
	list->frontNode = newNode;
	//护头也要护尾
	if (list->curSize == 0)               //只有一个节点 链表为空尾节点也是指向新节点
		list->backNode = newNode;         //把尾节点置为新节点
	list->curSize++;
}
//测试代码
	LPLIST list = createList();
	push_front(list, 1);
	push_front(list, 2);                  //2 1
	printList(list);

打印链表

从第1个节点开始打印

void printList(LPLIST list) 
{
	LPNODE pmove = list->frontNode;
	while (pmove != NULL)             //不为空打印数据
	{
		printf("%d\t", pmove->data);   
		pmove = pmove->next;
	}
	printf("\n");
}

尾插法

不需要找尾巴，因为记录了尾巴的位置

//插入的链表 插入的数据
void push_back(LPLIST list, int data) 
{
	LPNODE newNode = createNode(data);     //创建新节点
	if (list->curSize == 0) 
	{
		list->frontNode = newNode;         //只有1个节点的情况 表头也是指向新节点
		//list->backNode = newNode;        //表尾指向新节点
	}	
	else 
	{
		list->backNode->next = newNode;    //把原来链表的尾节点的next指针置为新节点
		//list->backNode = newNode;        //原来的表尾挪到新节点的位置
	}
	list->backNode = newNode;              //相同代码
	list->curSize++;
}
//测试代码
    push_back(list, 666);
	push_back(list, 999);                  //2 1 666 999
	printList(list);

指定位置插入

根据指定数据做插入，插在指定位置(数据)前面，不需要考虑表尾(尾插)

分改变表头、不改变表头两种情况：指定数据，数据可能插在表头前面(头节点的数据==指定数据)

前驱节点的 next 指针指向新节点，新节点的 next 指针指向当前节点

void push_appoin(LPLIST list, int posData, int data) 
{
	if (list == NULL || list->curSize == 0)  //为空无法做插入
	{
		printf("无法插入链表为空!\n");
		return;
	}
    //其他情况可以插入
	if (list->frontNode->data == posData)    //头节点的数据==指定数据 
	{
		push_front(list, data);              //会改变表头 用头插法插入
		return;
	}
    //正常插入的情况
	LPNODE preNode = list->frontNode;        //定义一个前驱节点指向第1个节点
	LPNODE curNode = list->frontNode->next;  //定义一个当前节点指向第1个节点的下一个节点
    //当前节点!=NULL && 当前节点的数据!=指定数据
	while (curNode != NULL && curNode->data != posData) //并排往下走
	{
		preNode = curNode;                   //前1个节点走到当前节点的位置
		curNode = preNode->next;             //当前节点走到原来位置的下一个
	}
    //分析查找结果做插入
	if (curNode == NULL)                     //没找到无法做插入
	{
		printf("没有找到指定位置，无法插入！\n");
	}
	else 
	{
		LPNODE newNode = createNode(data);   //创建新节点 
		preNode->next = newNode;             //连接
		newNode->next = curNode;             
		list->curSize++;
	}
}
//测试代码
    push_appoin(list, 666, 888);
	printList(list);                         //2 1 888 666 999

头删法

只有一个节点的情况：表尾也要改变(表尾指向了一段删除的内存)，表尾也要置为空

void pop_front(LPLIST list)
{
	if (list == NULL || list->curSize == 0)     //判空处理
	{
		printf("链表为空，无法删除!\n");
		return;
	}
	LPNODE nextNode = list->frontNode->next;    //头节点的下一个--->第2个节点
	free(list->frontNode);                      //直接删除表头
	list->frontNode = nextNode;                 //把原来的表头节点置为下一个节点
	if (list->curSize == 1)                     //只有1个节点的情况
	{
		list->backNode = NULL;                  //表尾也要置为空
	}
	list->curSize--;
}
//测试代码
    pop_front(list);
	pop_front(list);
	pop_front(list);
	pop_front(list);
	printList(list);                             //999

尾删法

要找到表尾的上一个节点

//要删除的链表
void pop_back(LPLIST list) 
{
	if (list == NULL || list->curSize == 0)
	{
		printf("链表为空，无法删除!\n");
		return;
	}
    //从第1个节点开始找 做移动
	LPNODE preNode = list->frontNode;    //头节点
	LPNODE backNode = list->frontNode;   //头节点的下一个
	while (backNode->next != NULL) 
	{
		preNode = backNode;              //并排往下走
		backNode = preNode->next;
	}
	free(backNode);
	if (list->curSize == 1)              //只有一个节点的情况
	{
		backNode = NULL;                 //释放后置空
		list->frontNode = NULL;          //表头也要置为空
		list->backNode = NULL;           //表尾置为空
		list->curSize--;
	}
	else 
	{
		backNode = NULL;
		preNode->next = NULL;
		list->backNode = preNode;    
		list->curSize--;
	}
}
//测试代码
    pop_back(list);
	printList(list);

指定位置删除

void pop_appoin(LPLIST list,int posData) 
{
	if (list == NULL || list->curSize == 0)
	{
		printf("链表为空，无法删除!\n");
		return;
	}
	if (list->frontNode->data == posData) //头节点的数据==指定数据 
	{
		pop_front(list);                  //头删法
		return;
	}
	if (list->backNode->data == posData) //尾节点的数据==指定数据
	{
		pop_back(list);                  //尾删法
		return;
	}
    //中间的某个情况
	LPNODE preNode = list->frontNode;    //原来的头部
	LPNODE curNode = list->frontNode->next;
	while (curNode != NULL && curNode->data != posData) 
	{
		preNode = curNode;               //并排往下走
		curNode = preNode->next;
	}
	if (curNode == NULL) 
	{
		printf("未找到指定位置，无法删除!\n");
	}
	else 
	{
		preNode->next = curNode->next;   //先连后断
		free(curNode);
		curNode = NULL;
		list->curSize--;
	}
}
//测试代码
    pop_appoin(list, 2);
	pop_appoin(list, 999);
	pop_appoin(list, 888);               //2 1 888 666 999
	printList(list);                     //1 666

查找链表

//要查找的链表 要查找的数据
LPNODE searchlist(LPLIST list, int posData)
{
	if (list == NULL)                              //list为空 返回NULL无法做删除
		return NULL;
	LPNODE pmove = list->frontNode;                //定义一个移动的节点
	while (pmove != NULL && pmove->data != posData) 
	{
		pmove = pmove->next;                       //数据!=指定数据一直往下走
	}
	return pmove;                                  //退出循环直接返回
}

删除所有指定相同的元素

void pop_all(LPLIST list, int posData) 
{
	while (searchlist(list, posData) != NULL)   //!=NULL说明里面有指定数据
	{
		pop_appoin(list, posData);              //持续做删除
	}
}
//测试代码   
	LPLIST test = createList();
	push_back(test, 1);
	push_back(test, 1);
	push_back(test, 1);
	push_back(test, 2);
	pop_all(test, 1);
	printList(test);                            //2