当前位置:   article > 正文

C语言简单的数据结构:单链表_c语言单链表

c语言单链表


我们在使用顺序表的时候我们发现了一些问题:
1.涉及到中间插入和头插时会进行数据的移动,导致效率较低
2.增容的空间会进行数据的拷贝
3.每次申请的空间不一定被使用,导致空间浪费
以上都说明顺序表不是很完美的,那有什么解决方法呢?
没错那就是:链表

1. 单链表的概念及结构

概念:链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构,数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。
所以链表也是线性表的一种(物理结构上不一定时线性的,逻辑结构是连续的)

在这里插入图片描述
这就是链表的结构,它是由存储的数据和指向下一个节点的指针组成的
那么链表的定义就可以写出来了:
在这里插入图片描述

2. 单链表的实现

2.1单链表的定义、创建和打印

2.11单链表的定义

首先是文件的创建和之前的一样:SList.h头文件,SList.c、test.c源文件
然后就是定义结构体了,这里用到的方法和顺序表的方法一样
在这里插入图片描述

2.12单链表的创建

接下来我们进行节点的创建,这里创建了四个节点
在这里插入图片描述

那我们如何让他们互相找到呢,这就是前面说的:放指向下一个节点的指针
在这里插入图片描述

这样就构成了一个链表

2.13单链表的打印

打印函数的函数的声明:
在这里插入图片描述

在这里插入图片描述

这里多创建一个指针防止对原来指针进行改变
在这里插入图片描述
我们在这里创建了一个pcur来接受传进来的传进来的地址接收,然后当pcur指向的不为NULL指针时,将数值打印出来,然后让pcur 指向下一个节点的地址,这就是链表的遍历

测试:
在这里插入图片描述

2.2单链表的头插和尾插

在这里插入图片描述

函数的声明(但这里有问题下文会改正)
既然要加数据就要先把数据放入节点中:
在这里插入图片描述
简单的空间开辟,将数值放入即可

2.21尾插

在这里插入图片描述
将我们最后的节点指向NULL改成限一个节点的地址,然后让下一个节点指向NULL即可
在这里插入图片描述

但是这个代码中有问题:
原链表如果是空链表,那么while语句就对NULL指针解引用,就会出现问题
解决方法:直接将新开辟的节点给phead即可
在这里插入图片描述
但还是有问题
在这里插入图片描述
这里并没有改变,我们进行调试:
在这里插入图片描述
发现形参变了而实参没有变化,就要传地址,而不是传值
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这样就改完了
测试:
在这里插入图片描述

在这里插入图片描述
这样就正确了,在优化一下:
在这里插入图片描述

2.22头插

在这里插入图片描述
和尾插一样但是申请的节点要指向之前的链表头,然后成为链表头
在这里插入图片描述
这里如果phead是NULL也可以,直接会替换NULL
测试:
在这里插入图片描述

2.3单链表的头删和尾删

在这里插入图片描述
函数声明

2.31尾删

在这里插入图片描述
将指针到5位置的数据删除掉,好要将第四个节点指向NULL
在这里插入图片描述
用快慢指针进行更改即可
但这个代码还有问题:
在这里插入图片描述
这种情况就不用找尾部节点
在这里插入图片描述
测试:
在这里插入图片描述
此时在进行尾删就会报错
在这里插入图片描述

2.31头删

在这里插入图片描述
创建新指针接收,让后进行释放后再将保存的指针重新赋值即可
测试:
在这里插入图片描述

2.4单链表的查找

声明:
在这里插入图片描述

在这里插入图片描述

链表进行遍历,找不到就返回NULL,一个循环加判断就可以了
测试:
在这里插入图片描述

2.5单链表指定位置的插入和删除

2.51指定位置前插入数据

在这里插入图片描述
在这里插入图片描述

这里因为有pos就一定有数值所以pphead不能为NULL
在这里插入图片描述
这是pos在中间时可以使用,进行遍历然后让prev,newnode,pos相连接就可以了
在这里插入图片描述

代码在头部就行不通,因为在前面无法找到pos,在最后面时可以行的
在这里插入图片描述

这里加个判断进行头插的调用即可
测试:
在这里插入图片描述

2.52指定位置后插入数据

在这里插入图片描述
为什么没有头节点?
因为之后插入直接在pos进行操作即可不用对pos前的数据
在这里插入图片描述
这里连接的方法有两种:
1.是先蓝(尾部连接)再红(头部连接)
2.先红(头部连接)后蓝(尾部连接)
这里分析一下:
在这里插入图片描述

这里第二种pos的指针next已经先改变了,无法再给newnode
在这里插入图片描述
关系明了了,代码不难的
测试:
在这里插入图片描述

2.53删除pos节点

在这里插入图片描述
在这里插入图片描述
这里又涉及到找pos前的数据了,所以有pphead
在这里插入图片描述
这里先找pos将其的指向下个地址给prev,然后释放pos
但这里又有pos在首位的时候会查不到,和之前的解决方法一样
在这里插入图片描述

测试:
在这里插入图片描述

2.54删除pos之后节点

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
这里如果pos后没有节点就不可以删除,要用assert对pos->next进行断言
测试:
在这里插入图片描述
在这里插入图片描述

2.6单链表的销毁

在这里插入图片描述

在这里插入图片描述
要一个一个的释放掉,就要用指针保存下一个节点的地址
在这里插入图片描述
测试:
在这里插入图片描述

本文代码:

SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
//定义节点的结构
typedef struct SListNode
{
	SLTDataType data;
	struct SLintNode* next;
}SLTNode;

void SLTPrint(SLTNode* phead);//打印链表

SLTNode* SLTBuyNode(SLTDataType x);//新节点存放数据
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//指定位置前插入数据
void SLTInstertAfter(SLTNode* pos, SLTDataType x); //指定位置后插入数据

void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos节点
void SLTEraseAfter(SLTNode* pos);//删除pos之后节点

void SListDesTroy(SLTNode** pphead);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SLTPrint(SLTNode* phead)
{
	//打印链表
	SLTNode* pcur = phead;
	while (pcur)//pcur!=NULL
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL");
	printf("\n");
}

SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);//新节点的创建
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* ptail = *pphead;
		//找尾(patil的下一个节点为NULL)
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead && *pphead);//链表和地址都不为NULL
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = *pphead;
		SLTNode* ptail = *pphead;
		while (ptail->next)
		{
			prev = ptail;
			ptail = ptail->next;
		}
		free(ptail);
		ptail = NULL;
		prev->next = NULL;
	}
}

void SLTPopFront(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* pcur = phead;
	while (pcur)
	{
		if (pcur->data == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && *pphead);
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	if (pos == *pphead)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		newnode->next = pos;
		prev->next = newnode;
	}
}

void SLTInstertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && *pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos && pos->next);
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;
}

void SListDesTroy(SLTNode** pphead)
{
	assert(pphead && *pphead);
	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SListTest01()
{
	//定义节点
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	//将节点连接起来
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	SLTNode* plist = node1;

	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest02()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	//SLTPushFront(&plist, 5);
	//SLTPushFront(&plist, 7);
	//SLTPushFront(&plist, 8);
	//SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SLTPopBack(&plist);
	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest03()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTNode* find = SLTFind(plist, 1);
	SLTInstertAfter(find, 11);
	SLTPrint(plist);
	SLTNode* find1 = SLTFind(plist, 4);
	SLTInstertAfter(find1, 11);
	SLTPrint(plist);
	SListDesTroy(&plist);
}

void SListTest04()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SListDesTroy(&plist);
	SLTPrint(plist);
}

int main()
{
	/*SListTest01();*/
	/*SListTest03();*/
	SListTest04();
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88

以上就是本文的全部内容了,希望对大家有所帮助,大家加油!!!

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号