您现在的位置是:首页 >技术教程 >单链表——“数据结构与算法”网站首页技术教程
单链表——“数据结构与算法”
各位CSDN的uu们你们好呀,今天,小雅兰的内容终于是我们心心念念的单链表啦,这一块呢,是一个很重要的部分,也是一个对目前的我来说,比较困难的部分,下面,就让我们进入单链表的世界吧
之前小雅兰写过顺序表的内容:
顺序表(更新版)——“数据结构与算法”_认真学习的小雅兰.的博客-CSDN博客
顺序表存在一些问题:
- 中间/头部的插入删除,时间复杂度为O(N)
- 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
思考:如何解决以上问题呢?下面给出了链表的结构来看看。
链表
链表的概念及结构
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
现实中 数据结构中
结构体里面的数据类型:
typedef int SLTDataType;
定义一个结构体,结构体内部嵌套了一个结构体的指针:
这个就是单链表
typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
单链表的打印:
//单链表的打印 void SLTPrint(SLTNode* phead) { //可以不需要断言 //因为:空链表也是可以打印的 SLTNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL "); }
意思是:首先,定义一个结构体的指针,该指针指向1,然后,对于cur,cur->data表示的是此结构体中的整型数据,cur->next表示的是2的地址,把cur->next赋值给cur,就是把这几块不连续的空间链接起来
表示:phead存的是第一个结点的地址,cur也存的是第一个节点的地址,就是把phead赋值给cur
头插
//头插 void SLPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址 //assert(*pphead); //不能断言,链表为空,也需要能插入 SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL; newnode->next = *pphead; *pphead = newnode; }
测试一下头插的功能:
void TestSList1()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
}
int main()
{
TestSList1();
return 0;
}
在写这段代码的过程中,很容易犯错误,可能会有很多人这样写代码:
//头插
void SLPushFront(SLTNode* phead, SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
newnode->next = phead;
phead = newnode;
}
void TestSList1()
{
SLTNode* plist = NULL;
SLPushFront(plist, 1);
SLPushFront(plist, 2);
SLPushFront(plist, 3);
SLPushFront(plist, 4);
SLPushFront(plist, 5);
SLTPrint(plist);
}
int main()
{
TestSList1();
return 0;
}
这是一个十分经典的错误:
传值调用了!!!
实参是形参的一份临时拷贝,对形参的修改并不会影响实参,所以phead的改变并不会影响plist
举一个简单的例子:Swap
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } int main() { int a = 10; int b = 20; Swap(&a, &b); printf("%d %d ", a, b); return 0; }
毫无疑问,这样写确实是正确的。
有的人在这边可能就会想:是不是只要用了指针就可以了呢?
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } int main() { int* px = 10; int* py = 20; Swap(px, py); printf("%d %d ", px, py); return 0; }
这样写,那是绝对不行的,接下来,来看看正确的写法:
void Swap(int** p1, int** p2) { int* tmp = *p1; *p1 = *p2; *p2 = tmp; } int main() { int* px = 10; int* py = 20; Swap(&px, &py); printf("%d %d ", px, py); return 0; }
我们会发现,在后续很多函数中,都需要用到创建结点这样一个功能,所以,可以把此功能封装成一个函数
//创建结点 void BuyLTNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->data = x; newnode->next = NULL;//就相当于初始化一下 }
尾插
从指向1的地址变为指向2的地址
循环所做的事
//尾插 void SLPushBack(SLTNode** pphead, SLTDataType x) { assert(pphead); SLTNode* newnode = BuyLTNode(x); //1.空链表 //2.非空链表 if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next;//tail->next本质是解引用,用tail的值找到指向的那个内存块,在内存块里面找到tail } tail->next = newnode; } }
测试一下尾插的功能:
void TestSList2()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
SLPushBack(&plist, 6);
SLPushBack(&plist, 7);
SLPushBack(&plist, 8);
SLPushBack(&plist, 9);
SLPushBack(&plist, 10);
SLTPrint(plist);
}
int main()
{
TestSList2();
return 0;
}
下面,来更好地解释一下为什么这边需要用到二级指针:
void func1(int* p)
{
*p = 10;
}
void func2(int** pp)
{
*pp = (int*)malloc(sizeof(int) * 10);
}
void func3(SLTNode* pnode)
{
pnode->next = NULL;
}
void func4(SLTNode** ppnode)
{
*ppnode = NULL;
}
int main()
{
//要改变int,就要传int的地址
int a = 0;
func1(&a);
//要改变int*,就要传int*的地址
int* ptr = NULL;
func2(&ptr);
//要改变结构体,就要传结构体的地址
SLTNode node;
func3(&node);
//要改变结构体的指针,传结构体的指针的地址
SLTNode* pnode;
func4(&pnode);
return 0;
}
尾删
一个典型的错误的写法:野指针问题
解决方式:
找到尾结点以及它的前一个结点
//尾删 void SLPopBack(SLTNode** pphead) { assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址 assert(*pphead); SLTNode* prev = NULL;//前一个结点 SLTNode* tail = *pphead; //找尾 while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); prev->next = NULL; }
还可以找倒数第二个
//尾删 //找倒数第二个 void SLPopBack(SLTNode** pphead) { //没有结点(空链表) //一个结点 //多个结点 assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址 assert(*pphead);//暴力的检查 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* tail = *pphead; //找尾 while (tail->next->next != NULL) { tail = tail->next; } free(tail->next); tail->next = NULL; } }
测试一下尾删的功能:
void TestSList3()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
SLPushBack(&plist, 6);
SLPushBack(&plist, 7);
SLPushBack(&plist, 8);
SLPushBack(&plist, 9);
SLPushBack(&plist, 10);
SLTPrint(plist);
SLPopBack(&plist);
SLPopBack(&plist);
SLTPrint(plist);
}
头删
头删和尾删都有三种情况:
- 没有结点(也就是空链表)
- 有一个结点
- 有多个结点
//头删 void SLPopFront(SLTNode** pphead) { //没有结点(空链表) assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址 assert(*pphead);//暴力的检查 //链表为空,不能头删 //一个结点 //多个结点 if ((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { SLTNode* del = *pphead;//不能直接free掉 //如果直接free的话,就找不到下一个结点的地址啦 *pphead = del->next; free(del); } }
测试一下头删的功能:
void TestSList4()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
SLPushBack(&plist, 6);
SLPushBack(&plist, 7);
SLPushBack(&plist, 8);
SLPushBack(&plist, 9);
SLPushBack(&plist, 10);
SLTPrint(plist);
SLPopBack(&plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLPopFront(&plist);
SLTPrint(plist);
}
单链表查找
//头插、尾插、头删、尾删都要修改链表,所以要传二级指针 //单链表查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { //不用assert,因为空链表也是可以查找的 SLTNode* cur = phead; while (cur != NULL) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
测试一下单链表查找的功能:
void TestSList4()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
SLPushBack(&plist, 6);
SLPushBack(&plist, 7);
SLPushBack(&plist, 8);
SLPushBack(&plist, 9);
SLPushBack(&plist, 10);
SLTPrint(plist);
SLPopBack(&plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLPopFront(&plist);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 2);
pos->data = 30;
SLTPrint(plist);
}
任意位置数据的插入(pos之前插入)
//在pos的位置之前插入 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { assert(pphead); assert(pos); assert(*pphead); if (*pphead == pos) { SLPushFront(pphead, x); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SLTNode* newnode = BuyLTNode(x); prev->next = newnode; newnode->next = pos; } }
后插
//在pos的位置之后插入 void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newnode = BuyLTNode(x); newnode->next = pos->next; pos->next = newnode; }
测试一下前插和后插的功能:
void TestSList5()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
SLPushBack(&plist, 6);
SLPushBack(&plist, 7);
SLPushBack(&plist, 8);
SLPushBack(&plist, 9);
SLPushBack(&plist, 10);
SLTPrint(plist);
SLPopBack(&plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLPopFront(&plist);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
if (pos != NULL)
{
SLTInsert(&plist, pos, 20);
}
SLTPrint(plist);
pos = SLTFind(plist, 2);
if (pos != NULL)
{
SLTInsertAfter(pos, 30);
}
SLTPrint(plist);
}
删除pos位置的值
//删除pos位置的值 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead); assert(pos); assert(*pphead); if (pos == *pphead) { SLPopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
后删
//删除pos位置之后的值 void SLTEraseAfter(SLTNode* pos) { assert(pos); assert(pos->next); SLTNode* next = pos->next; pos->next = next->next; free(next); }
void TestSList5()
{
SLTNode* plist = NULL;
SLPushFront(&plist, 1);
SLPushFront(&plist, 2);
SLPushFront(&plist, 3);
SLPushFront(&plist, 4);
SLPushFront(&plist, 5);
SLTPrint(plist);
SLPushBack(&plist, 6);
SLPushBack(&plist, 7);
SLPushBack(&plist, 8);
SLPushBack(&plist, 9);
SLPushBack(&plist, 10);
SLTPrint(plist);
SLPopBack(&plist);
SLPopBack(&plist);
SLTPrint(plist);
SLPopFront(&plist);
SLPopFront(&plist);
SLTPrint(plist);
SLTNode* pos = SLTFind(plist, 3);
if (pos != NULL)
{
SLTInsert(&plist, pos, 20);
}
SLTPrint(plist);
pos = SLTFind(plist, 2);
if (pos != NULL)
{
SLTInsertAfter(pos, 30);
}
SLTPrint(plist);
pos = SLTFind(plist, 7);
if (pos != NULL)
{
SLTErase(&plist,pos);
}
SLTPrint(plist);
}
源代码如下:
SList.h的内容:
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//单链表的打印
void SLTPrint(SLTNode* phead);
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x);
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x);
//头删
void SLPopFront(SLTNode** pphead);
//尾删
void SLPopBack(SLTNode** pphead);
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在pos的位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x);
//在pos的位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos位置之前的值
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos);
SList.c的内容:
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//单链表的打印
void SLTPrint(SLTNode* phead)
{
//可以不需要断言
//因为:空链表也是可以打印的
SLTNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL
");
}
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
//assert(*pphead);
//不能断言,链表为空,也需要能插入
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;
newnode->next = *pphead;
*pphead = newnode;
}
//创建结点
SLTNode* BuyLTNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
return;
}
newnode->data = x;
newnode->next = NULL;//就相当于初始化一下
return newnode;
}
//尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
//assert(*pphead);
//不能断言,链表为空,也需要能插入
SLTNode* newnode = BuyLTNode(x);
//1.空链表
//2.非空链表
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;//tail->next本质是解引用,用tail的值找到指向的那个内存块,在内存块里面找到tail
}
tail->next = newnode;
}
}
尾删
// 找倒数第一个
//void SLPopBack(SLTNode** pphead)
//{
// assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
// assert(*pphead);
// SLTNode* prev = NULL;//前一个结点
// SLTNode* tail = *pphead;
// //找尾
// while (tail->next != NULL)
// {
// prev = tail;
// tail = tail->next;
// }
// free(tail);
// prev->next = NULL;
//}
//尾删
//找倒数第二个
void SLPopBack(SLTNode** pphead)
{
//没有结点(空链表)
//一个结点
//多个结点
assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
assert(*pphead);//暴力的检查
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* tail = *pphead;
//找尾
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
//头删
void SLPopFront(SLTNode** pphead)
{
//没有结点(空链表)
assert(pphead);//链表为空,pphead也不能为空,因为它是头指针plist的地址
assert(*pphead);//暴力的检查
//链表为空,不能头删
//一个结点
//多个结点
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* del = *pphead;//不能直接free掉
//如果直接free的话,就找不到下一个结点的地址啦
*pphead = del->next;
free(del);
}
}
//头插、尾插、头删、尾删都要修改链表,所以要传二级指针
//单链表查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
//不用assert,因为空链表也是可以查找的
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos的位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (*pphead == pos)
{
SLPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SLTNode* newnode = BuyLTNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
//在pos的位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuyLTNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
//删除pos位置的值
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
if (pos == *pphead)
{
SLPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
}
}
//删除pos位置之后的值
void SLTEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);
SLTNode* next = pos->next;
pos->next = next->next;
free(next);
}
好啦,小雅兰今天的单链表的内容就到这里啦,内容还是非常多的,也比较难,小雅兰会继续加油学习的,冲冲冲!!!