C语言深入讲解链表的使用

目录

• 一、链表的概念
• 二、链表的分类
• 1. 单向或者双向链表
• 2. 带头或者不带头(是否有自带哨兵位头结点)
• 3. 循环或者非循环链表
• 4. 无头单向非循环链表和带头双向循环链表
• 3、链表的实现(代码和注释)
• 4、链表oj题(小试牛刀)
• 总结

现实生活中的火车就像一个完整的链表，现在我们来深入理解一下链表这个数据结构。

一、链表的概念

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

注：

1、从上图中可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。

2、从现实中的结点一般是通过malloc函数申请的，所以其内存分配是在堆区。

3、从堆上申请的空间，是按照一定的策略来分配的，则一个节点的大小为8个字节。

二、链表的分类

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

1. 单向或者双向链表

2. 带头或者不带头(是否有自带哨兵位头结点)

第二个链表的d1指向了我们的哨兵位头结点。

3. 循环或者非循环链表

4. 无头单向非循环链表和带头双向循环链表

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

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

3、链表的实现(代码和注释)

无头+单向+非循环链表增删查改实现

头文件：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//要求存储的数据从0开始，依次存储
//静态的顺序表
//问题：开小了，不够用，开大了，存在浪费。
//struct SeqList
//{
//	int a[N];
//	int size;//记录存储了多少个数据。
//};
typedef int SLDateType;//宏定义我们的 SLDateType是int类型的
//动态的顺序表
typedef struct SeqList
{
	SLDateType* a;
	int size;	//存储数据个数
	int capacity;//存储空间大小
}SL, SeqList;
void SeqListPrint(SeqList* psl);//链表的打印
void SeqListInit(SeqList* psl);//链表的初始化
void SeqListDestroy(SeqList* psl);//链表的销毁
void SeqListCheckCapacity(SeqList* psl);//检查内存空间是否足够
//时间复杂度是o(1)
void SeqListPushBack(SeqList* psl, SLDateType x);//链表的尾插
void SeqListPopBack(SeqList* psl);//链表的尾删
//时间复杂度是o(n)
void SeqListPushFront(SeqList* psl, SLDateType x);//链表的头插
void SeqListPopFront(SeqList* psl);//链表的头删
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x);
// 删除pos位置的数据
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDateType x);

链表的函数实现部分的代码：

#include"SeqList.h"
#include<assert.h>
void SeqListPrint(SeqList* psl)//结构体指针传参
{
	for (int i = 0; i < psl->size; ++i)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}
void SeqListInit(SeqList* psl)
{
	assert(psl);//断言psl不为空
	psl->a = NULL;//a就相当于是链表的头
	psl->size = 0;
	psl->capacity = 0;
}
void SeqListDestroy(SeqList* psl)//链表的删除
{
	assert(psl);
	free(psl->a);//free掉链表中a这个节点的位置
	psl->a = NULL;//将a指向空
	psl->capacity = psl->size = 0;//将链表的内存大小置为0
}
void SeqListCheckCapacity(SeqList* psl)//检查链表的内存，如果不够就增容。
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		//capacity == 0,所以要先特判一下capacity 的值
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//初始节点数为4，如果内存现在为0就扩大一倍
		SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//申请空间
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;//原来的空间变为新空间
		}
	}
}
void SeqListPushBack(SeqList* psl, SLDateType x)
{
	//如果满了，要扩容
	if (psl->size == psl->capacity)
	{
		//capacity == 0,所以要先特判一下capacity 的值
		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			psl->a = tmp;
			psl->capacity = newCapacity;
		}
	}
	psl->a[psl->size] = x;
	psl->size++;
}
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	if (psl->size > 0)
	{
		psl->size--;//尾删就size--就好了
	}
}
void SeqListPushFront(SeqList* psl, SLDateType x)
{
	assert(psl);
	SeqListCheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)//所有的数据往后挪1位
	{
		psl->a[end + 1] = psl->a[end];
		--end;
	}
	psl->a[0] = x;//两种操作是等价的
	psl->size++;
	//SeqListInsert(psl, 0, x);在头部插入。
}
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	if (psl->size > 0)
	{
		int begin = 1;
		while (psl->size > begin)
		{
			psl->a[begin - 1] = psl->a[begin];
			++begin;
		}
		--psl->size;
	}
}
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
	// 暴力检查
	assert(psl);
	// 温和检查
	if (pos > psl->size)
	{
		printf("pos 越界：%d\n", pos);
		return;
		//exit(-1);
	}
	// 暴力检查
	//assert(pos <= psl->size);
	SeqListCheckCapacity(psl);
	//int end = psl->size - 1;
	//while (end >= (int)pos)
	//{
	//	psl->a[end + 1] = psl->a[end];
	//	--end;
	//}
	size_t end = psl->size;
	while (end > pos)
	{
		psl->a[end] = psl->a[end - 1];
		--end;
	}
	psl->a[pos] = x;
	psl->size++;
}

4、链表oj题(小试牛刀)

1、leetcode203移除链表元素力扣

包含三种情况

画个图分析：

思路：情况一和情况二都可以用prev和cur指针遍历数组的两个元素， if cur指针不等于6，prev指针和cur指针都往前走，如果cur = 6，prev跳到cur的下一个位置

如果是第三种情况，则需先找到head != val的位置，再重复进行如上操作。

代码示例：

struct ListNode* removeElements(struct ListNode* head, int val)
{
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        if(cur->val != val)//当cur这个位置的值不等于val时往下走
        {
            prev = cur;//prev跳到cur位置
             cur = cur->next;//cur指针继续往下走
        }
        else
        {
            struct ListNode* next = cur->next;//定义一个新的指针
            if(prev == NULL)//头删，head为空的状态
            {
                free(cur);
                head = next;//继续往后面走
                cur = next;
            }
            else
            {
                free(cur);//free掉cur这个节点
                prev->next = next;//跳过了cur这个点
                cur = next;//cur继续往后走
            }
        }
    }
    return head;
}

2、leetcode206反转链表力扣

思路1：反转指针方向

思路二：用三个指针， n1, n2, n3 分别存放NULL, head, head->next;

代码示例：

struct ListNode* reverseList(struct ListNode* head)
{
    if(head == NULL) return NULL;
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;//n3的地址是n2的下一位
    while(n2)
    {
        n2->next = n1;//n2 的下一位指向 n1;起到掉头的作用
        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
    }
    return n1;
}

方法2：头插法

殊途同归。newhead 相当于之前的n1, cur = n2, next = n3;
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //头插
        cur->next = NewHead;//代表链表的指向方向。
        NewHead = cur;//接着把地址传过来(更新)
        cur = next;//（更新）
    }
    return NewHead;
}

3、leetcode 876链表的中间结点力扣

思路：快慢指针法

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;//刚开始slow和fast指针都指向头
    while(fast && fast->next) //想的是结束的条件，写的是继续的条件
    {
        slow = slow->next;
        fast = fast->next->next;//fast 每次走两步
    }
    return slow;
}

总结

这里我带大家从链表的概念，链表的分类，链表的简单实现以及3题oj题四个方面带大家认识链表

到此这篇关于C语言深入讲解链表的使用的文章就介绍到这了,更多相关C语言链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！