[数据结构与算法][数据结构----单链表]

单链表

增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

1.单向、双向

2.带头、不带头（有没有头结点，不存放数据）

3.循环、非循环

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，另外这种结构在笔试面试中出现很多。下图为单向不带头非循环链表

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带
来很多优势，实现反而简单了。下图为带头双向循环链表

本文实现的是不带头单向非循环链表。

链表结点

typedef int LinkListDataType;//结点所包含的数据的数据类型，方便更换其他数据类型导致很多代码的修改
typedef struct LinkListNode {
	LinkListDataType data;//数据
	struct LinkListNode* next;//指向下一个节点的指针
}LinkListNode;

开辟新结点

//开辟新结点
LinkListNode* BuyLinkListNode(LinkListDataType val) {
	LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
	if (newNode == NULL) {
		printf("malloc failed\n");
		exit(-1);
	}
    //初始化新结点，将数据域中的数据置为val,指针域先置为空，待到使用的地方再赋值
	newNode->data = val;
	newNode->next = NULL;
	return newNode;
}

打印链表

//打印
void LinkListPrint(LinkListNode* phead) {
	//不用做指针合法性的检查，因为头指针也有空的情况，当单链表中没有元素的时候，phead就等于NULL
	LinkListNode* cur = phead;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

尾插

尾插分为两种情况

1. 链表中一个元素也没有

2. 链表中有元素

   ? 有元素的时候需要先找到尾结点，不然怎么插入呢

//尾插
void LinkListPushBack(LinkListNode** pphead, LinkListDataType val) {
	assert(pphead != NULL);
	LinkListNode* newNode = BuyLinkListNode(val);
	//如果链表中没有结点
	if (*pphead == NULL) {
		*pphead = newNode;
	}
	//如果链表中有结点，需要先找到尾
	//这种情况已经包含只有一个结点的情况，故不需要单独讨论
	else {
		LinkListNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

尾插的测试

void test01() {
	LinkListNode* pList = NULL;
	LinkListPrint(pList);
	LinkListPushBack(&pList, 1);
	LinkListPushBack(&pList, 2);
	LinkListPushBack(&pList, 3);
	LinkListPushBack(&pList, 4);
	LinkListPrint(pList);
}

尾删

尾删分为三种情况

1. 链表中一个元素也没有

   ? 直接返回

2. 链表中只有一个元素

   ? 释放结点，将结点置空

3. 链表中有一个以上元素

   ? 不仅需要找到尾结点，还需要找到尾结点的前一个结点，删除尾结点后，需要将它的前一个结点（删除尾结点后，这个结点就是现在的尾结点了）的指针域next置空

//尾删
void LinkListPopBack(LinkListNode** pphead) {
	assert(pphead);//pphead为pList的地址，如果为空，那就不合理了，必须要检查
	//为什么这里需要传入二级指针，是因为如果我删除的就是头结点，传入一级指针并不会改变外部实参
	//一个结点也没有
	if (*pphead == NULL) {
		return;
	}
	//只有一个结点
	else if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	//一个以上结点
	//不仅需要找到尾结点，还需要找到尾结点的前一个结点，删除尾结点后
	//需要将它的前一个结点的指针域next置空
	else {
		LinkListNode* prev = NULL;//当前结点的前一个结点
		LinkListNode* cur = *pphead;//当前结点
        //找到尾
		while (cur->next != NULL) {
			prev = cur;
			cur = cur->next;
		}
        //此时cur为尾结点，prev为尾结点的前一个结点，删除尾结点cur后，需要将prev的指针域置空
		free(cur);
		cur = NULL;//可不置空，出了作用域谁也找不到它
		prev->next = NULL;//将新的尾结点的指针域next置空
	}
}

尾删的测试

void test02() {
	LinkListNode* pList = NULL;
	LinkListPrint(pList);
	LinkListPushBack(&pList, 1);
	LinkListPushBack(&pList, 2);
	LinkListPushBack(&pList, 3);
	LinkListPushBack(&pList, 4);
	LinkListPrint(pList);

	LinkListPopBack(&pList);
	LinkListPopBack(&pList);
	LinkListPrint(pList);

	LinkListPopBack(&pList);
	LinkListPopBack(&pList);
	LinkListPrint(pList);
}

判空

判定当前链表中有无元素，没有元素的话返回真（1），有元素说明非空，返回假（0）。

//判空
int LinkListEmpty(LinkListNode* phead) {
	return phead == NULL;
}

判空的测试

void test02() {
	LinkListNode* pList = NULL;
	int ret = LinkListEmpty(pList);
	if (ret) {
		printf("链表为空\n");
	}
	else {
		printf("链表不为空\n");
	}
	
	LinkListPushBack(&pList, 1);
	ret = LinkListEmpty(pList);
	if (ret) {
		printf("链表为空\n");
	}
	else {
		printf("链表不为空\n");
	}
}

头插

头插不需要判断链表为空，只有一个元素及一个元素以上，因为以下代码包含上述三种情况。

//头插
void LinkListPushFront(LinkListNode** pphead, LinkListDataType val) {
	assert(pphead != NULL);
	LinkListNode* newNode = BuyLinkListNode(val);
	newNode->next = *pphead;
	*pphead = newNode;
}

头插的测试

void test02() {
	LinkListNode* pList = NULL;
	LinkListPushFront(&pList, 10);
	LinkListPushFront(&pList, 20);
	LinkListPushFront(&pList, 30);
	LinkListPushFront(&pList, 40);
	LinkListPrint(pList);
}

头删

头删分为两种情况

1. 链表为空

   ? 直接返回

2. 链表含有一个及以上的元素，操作相同

//头删
void LinkListPopFront(LinkListNode** pphead) {
	assert(pphead != NULL);
	//如果链表为空
	if (*pphead == NULL) {
		return;
	}
	//如果链表不为空
	//一个结点和多个结点的情况都可实现
	LinkListNode* delNode = *pphead;
	*pphead = delNode->next;
	free(delNode);
	delNode = NULL;//可不置空，出了作用域也找不到它了。
}

头删的测试

void test02() {
	LinkListNode* pList = NULL;
	LinkListPushFront(&pList, 10);
	LinkListPushFront(&pList, 20);
	LinkListPushFront(&pList, 30);
	LinkListPushFront(&pList, 40);
	LinkListPrint(pList);

	LinkListPopFront(&pList);
	LinkListPopFront(&pList);
	LinkListPrint(pList);
	LinkListPopFront(&pList);
	LinkListPopFront(&pList);
	LinkListPopFront(&pList);
	LinkListPrint(pList);
}

查找

//查找
LinkListNode* LinkListFind(LinkListNode* pphead, LinkListDataType val) {
	LinkListNode* cur = pphead;
	while (cur != NULL) {
		if (cur->data == val) {
			return cur;
		}
		cur = cur->next;
	}
	//程序执行到这儿说明并没有找到val
	return NULL;
}

任意位置之后插入

//任意位置之后插入
void LinkListInsertAfter(LinkListNode* pos, LinkListDataType val) {
	assert(pos != NULL);
	LinkListNode* newNode = BuyLinkListNode(val);
	newNode->next = pos->next;
	pos->next = newNode;
}

任意位置之前插入

在pos位置之前插入，需要找到pos位置之前的结点，不然插入新结点后怎么确保新结点的连接。

//任意位置之前插入
void LinkListInsertBefore(LinkListNode** pphead, LinkListNode* pos, LinkListDataType val) {
	assert(pphead);
	LinkListNode* newNode = BuyLinkListNode(val);
	LinkListNode* posPrev = *pphead;
	while (posPrev->next != pos) {
		posPrev = posPrev->next;
	}
	posPrev->next = newNode;
	newNode->next = pos;
}

任意位置之后删除

//任意位置之后删除
void LinkListEraseAfter(LinkListNode* pos) {
	//合法性检查，即要检查pos位置之后有结点才能删除吧
	assert(pos != NULL && pos->next != NULL);
	LinkListNode* delNode = pos->next;
	pos->next = delNode->next;
	free(delNode);
	delNode = NULL;//可不置空
}

结点个数

//结点个数
int LinkListSize(LinkListNode* phead) {
	int count = 0;
	LinkListNode* cur = phead;
	while (cur != NULL) {
		++count;
		cur = cur->next;
	}
	return count;
}

查找，任意位置之后插入、删除，任意位置之前删除，结点个数的测试

void test02() {
	LinkListNode* pList = NULL;
	LinkListPushFront(&pList, 5);
	LinkListPushFront(&pList, 15);
	LinkListPushFront(&pList, 25);
	LinkListPushFront(&pList, 35);
	LinkListPrint(pList);

	//查找函数也可以实现修改操作
	//如查找15，找到则将15修改为100
	LinkListNode* pos = LinkListFind(pList, 15);
	if (pos != NULL) {
		pos->data = 100;
	}
	LinkListPrint(pList);

	int size = LinkListSize(pList);
	printf("当前链表结点有%d个\n", size);

	//在100之后插入200,在100之前插入50
	LinkListNode* pos2 = LinkListFind(pList, 100);
	if (pos2 != NULL) {
		LinkListInsertAfter(pos2, 200);
		LinkListInsertBefore(&pList, pos2, 50);
	}
	LinkListPrint(pList);

	//删除100之后的200
	LinkListEraseAfter(pos2);
	LinkListPrint(pList);
}

链表的销毁

销毁后需要将头指针置空，防止出现野指针。

//销毁单链表
void LinkListDestroy(LinkListNode** pphead) {
	assert(pphead);
	while (*pphead != NULL) {
		LinkListNode* delNode = *pphead;
		*pphead = delNode->next;
		free(delNode);
	}
	*pphead = NULL;//将头指针置空，防止出现野指针
}

完整代码实现

LinkList.h

#pragma once	//防止头文件重复包含
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int LinkListDataType;//结点所包含的数据的数据类型，方便更换其他数据类型导致很多代码的修改
typedef struct LinkListNode {
	LinkListDataType data;//数据
	struct LinkListNode* next;//指向下一个节点的指针
}LinkListNode;

//开辟新结点
LinkListNode* BuyLinkListNode(LinkListDataType val);

//尾插
void LinkListPushBack(LinkListNode** pphead, LinkListDataType val);

//打印
void LinkListPrint(LinkListNode* phead);

//尾删
void LinkListPopBack(LinkListNode** pphead);

//判空
int LinkListEmpty(LinkListNode* phead);

//头插
void LinkListPushFront(LinkListNode** pphead, LinkListDataType val);

//头删
void LinkListPopFront(LinkListNode** pphead);

//查找
LinkListNode* LinkListFind(LinkListNode* pphead, LinkListDataType val);

//任意位置之后插入
void LinkListInsertAfter(LinkListNode* pos, LinkListDataType val);

//任意位置之前插入
void LinkListInsertBefore(LinkListNode** pphead, LinkListNode* pos, LinkListDataType val);

//任意位置之后删除
void LinkListEraseAfter(LinkListNode* pos);

//结点个数
int LinkListSize(LinkListNode* phead);

//销毁单链表
void LinkListDestroy(LinkListNode** pphead);

LinkList.c

#include "LinkList.h"

//开辟新结点
LinkListNode* BuyLinkListNode(LinkListDataType val) {
	LinkListNode* newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
	if (newNode == NULL) {
		printf("malloc failed\n");
		exit(-1);
	}
	newNode->data = val;
	newNode->next = NULL;
	return newNode;
}

//尾插
void LinkListPushBack(LinkListNode** pphead, LinkListDataType val) {
	assert(pphead != NULL);
	LinkListNode* newNode = BuyLinkListNode(val);
	//如果链表中没有结点
	if (*pphead == NULL) {
		*pphead = newNode;
	}
	//如果链表中有结点，需要先找到尾
	//这种情况已经包含只有一个结点的情况，故不需要单独讨论
	else {
		LinkListNode* tail = *pphead;
		while (tail->next != NULL) {
			tail = tail->next;
		}
		tail->next = newNode;
	}
}

//打印
void LinkListPrint(LinkListNode* phead) {
	//不用做指针合法性的检查，因为头指针也有空的情况，当单链表中没有元素的时候，phead就等于NULL
	LinkListNode* cur = phead;
	while (cur != NULL) {
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

//尾删
void LinkListPopBack(LinkListNode** pphead) {
	assert(pphead);//pphead为pList的地址，如果为空，那就不合理了，必须要检查
	//为什么这里需要传入二级指针，是因为如果我删除的就是头结点，传入一级指针并不会改变外部实参
	//一个结点也没有
	if (*pphead == NULL) {
		return;
	}
	//只有一个结点
	else if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	//一个以上结点
	//不仅需要找到尾结点，还需要找到尾结点的前一个结点，删除尾结点后
	//需要将它的前一个结点的指针域next置空
	else {
		LinkListNode* prev = NULL;
		LinkListNode* cur = *pphead;
		while (cur->next != NULL) {
			prev = cur;
			cur = cur->next;
		}
		free(cur);
		cur = NULL;//可不置空，出了作用域谁也找不到它
		prev->next = NULL;//将新的尾结点的指针域next置空
	}
}

//判空
int LinkListEmpty(LinkListNode* phead) {
	return phead == NULL;
}

//头插
void LinkListPushFront(LinkListNode** pphead, LinkListDataType val) {
	assert(pphead != NULL);
	LinkListNode* newNode = BuyLinkListNode(val);
	newNode->next = *pphead;
	*pphead = newNode;
}

//头删
void LinkListPopFront(LinkListNode** pphead) {
	assert(pphead != NULL);
	//如果链表为空
	if (*pphead == NULL) {
		return;
	}
	//如果链表不为空
	//一个结点和多个结点的情况都可实现
	LinkListNode* delNode = *pphead;
	*pphead = delNode->next;
	free(delNode);
	delNode = NULL;//可不置空，出了作用域也找不到它了。
}

//查找
LinkListNode* LinkListFind(LinkListNode* pphead, LinkListDataType val) {
	LinkListNode* cur = pphead;
	while (cur != NULL) {
		if (cur->data == val) {
			return cur;
		}
		cur = cur->next;
	}
	//程序执行到这儿说明并没有找到val
	return NULL;
}

//任意位置之后插入
void LinkListInsertAfter(LinkListNode* pos, LinkListDataType val) {
	assert(pos != NULL);
	LinkListNode* newNode = BuyLinkListNode(val);
	newNode->next = pos->next;
	pos->next = newNode;
}

//任意位置之前插入
void LinkListInsertBefore(LinkListNode** pphead, LinkListNode* pos, LinkListDataType val) {
	assert(pphead);
	LinkListNode* newNode = BuyLinkListNode(val);
	LinkListNode* posPrev = *pphead;
	while (posPrev->next != pos) {
		posPrev = posPrev->next;
	}
	posPrev->next = newNode;
	newNode->next = pos;
}

//任意位置之后删除
void LinkListEraseAfter(LinkListNode* pos) {
	assert(pos != NULL && pos->next != NULL);
	LinkListNode* delNode = pos->next;
	pos->next = delNode->next;
	free(delNode);
	delNode = NULL;//可不置空
}

//结点个数
int LinkListSize(LinkListNode* phead) {
	int count = 0;
	LinkListNode* cur = phead;
	while (cur != NULL) {
		++count;
		cur = cur->next;
	}
	return count;
}

//销毁单链表
void LinkListDestroy(LinkListNode** pphead) {
	assert(pphead);
	while (*pphead != NULL) {
		LinkListNode* delNode = *pphead;
		*pphead = delNode->next;
		free(delNode);
	}
	*pphead = NULL;//将头指针置空，防止出现野指针
}

testLinkList.c

#include "LinkList.h"


void test01() {
	LinkListNode* pList = NULL;
	LinkListPrint(pList);
	LinkListPushBack(&pList, 1);
	LinkListPushBack(&pList, 2);
	LinkListPushBack(&pList, 3);
	LinkListPushBack(&pList, 4);
	LinkListPrint(pList);

	LinkListPopBack(&pList);
	LinkListPopBack(&pList);
	LinkListPrint(pList);

	LinkListPopBack(&pList);
	LinkListPopBack(&pList);
	LinkListPrint(pList);

	int ret = LinkListEmpty(pList);
	if (ret) {
		printf("链表为空\n");
	}
	else {
		printf("链表不为空\n");
	}

	LinkListPushFront(&pList, 10);
	LinkListPushFront(&pList, 20);
	LinkListPushFront(&pList, 30);
	LinkListPushFront(&pList, 40);
	LinkListPrint(pList);

	LinkListPopFront(&pList);
	LinkListPopFront(&pList);
	LinkListPrint(pList);
	LinkListPopFront(&pList);
	LinkListPopFront(&pList);
	LinkListPopFront(&pList);
	LinkListPrint(pList);


	LinkListPushFront(&pList, 5);
	LinkListPushFront(&pList, 15);
	LinkListPushFront(&pList, 25);
	LinkListPushFront(&pList, 35);
	LinkListPrint(pList);

	//查找函数也可以实现修改操作
	//如查找15，找到则将15修改为100
	LinkListNode* pos = LinkListFind(pList, 15);
	if (pos != NULL) {
		pos->data = 100;
	}
	LinkListPrint(pList);

	int size = LinkListSize(pList);
	printf("当前链表结点有%d个\n", size);

	//在100之后插入200,在100之前插入50
	LinkListNode* pos2 = LinkListFind(pList, 100);
	if (pos2 != NULL) {
		LinkListInsertAfter(pos2, 200);
		LinkListInsertBefore(&pList, pos2, 50);
	}
	LinkListPrint(pList);

	//删除100之后的200
	LinkListEraseAfter(pos2);
	LinkListPrint(pList);
	LinkListDestroy(&pList);
}

int main() {
	test01();
	system("pause");
	return 0;
}

本来下午就写好了，因为typora文件上传到CSDN时图片导入出错，百度一下，需要通过gitte，将图片上传到gitte，但是gitte每小时只能上传20个文件，因为一下重复操作，让我等了好久没有解决，后来又搜了下，通过linux将图片上传到gitte，改天得空可以写一下操作，加油，老铁们。