个人中心
gpt4 book ai didi

一文弄懂C语言如何实现单链表

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 29 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章一文弄懂C语言如何实现单链表由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

1、单链表与顺序表的区别：

1、顺序表：

1、内存中地址连续 。

2、长度可以实时变化 。

3、不支持随机查找 。

4、适用于访问大量元素的，而少量需要增添/删除的元素的程序 。

5、中间插入或者删除比较方便，内存命中率较高 。

2、链表

1、内存中地址不连续（逻辑上连续，物理上不连续） 。

2、长度可以实时变化（避免浪费空间） 。

3、不支持随机查找，查找的时间复杂度为o(1).

4、适用于访问大量元素的，对访问元素无要求的程序 。

5、中间插入或者删除比较方便，效率高 。

2、关于链表中的一些函数接口的作用及实现

1、创建接口，开辟空间 。

2、尾插尾删 。

3、头插头删 。

4、查找并修改 。

5、中插中删 。

ps：我看了许多的单链表文章，在插删的接口实现上大多数是往前进行插删，这里写的则是往后进行插删 。

1、头文件里的结构体和函数声明等等

?
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
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
 
typedef int SListDataType;
//节点
typedef struct SListNode
{
     SListDataType data;
     struct SListNode* next;
}SListNode;
 
//struct SList
//{
//  SListNode* head;
//  SListNode* tail;
//};
 
//尾插尾删
void SListPushBack(SListNode** pphead, SListDataType x);
void SListPopBack(SListNode** pphead);
 
//头插头删
void SListPushFront(SListNode**  pphead, SListDataType x);
void SListPopFront(SListNode** pphaed);
 
void SListPrint(SListNode* phead);
//查找并修改
SListNode* SListFind(SListNode* phead, SListDataType x);
//中插中删
void SListInserAfter(SListNode**pphead,SListNode* pos, SListDataType x);
void SListEraseAfter(SListNode* pos);
 
//从头到尾打印链表
void PrintTailToHead(SListNode* pList);

2、创建接口空间

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//开辟的下一个空间
SListNode* BuySListNode(SListDataType x)
{
     SListNode* newNode = (SListNode*) malloc ( sizeof (SListNode));
     if (newNode == NULL)
     {
         printf ( "申请结点失败\n" );
         exit (-1);
     }
     newNode->data = x;
     newNode->next = NULL;
     return newNode;
 
}

3.尾插尾删

?
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
//尾插
void SListPushBack(SListNode** pphead, SListDataType x)
{
     SListNode* newNode = BuySListNode(x); //我们指向头指针的那个结点是**pphead，*pphead就是头指针的地址
     //如果头指针的地址为空，我们就把新开辟的这个空间指针（已经传入值）再赋给头指针，也就是下面的这个if循环
     if (*pphead == NULL)
     {
         *pphead = newNode;
     }
     else
     {
         //找尾巴，判断尾巴是不是空地址,这个函数实现的是尾插，我们找到尾巴后，如果尾巴是空地址，我们将插入的newNode赋给尾巴，此时
         //实现了尾插，在下面的代码中，我们首先把头指针当成尾巴，从头指针开始依次往后找，如果下一个不是空指针，我们就令
         //tail=tail->next,此时指向下一个结点，进入循环继续判断，当找到后，我们再令尾巴=newNode,在上面我们也判断了头指针为空的情况
         SListNode* tail = *pphead;
         while (tail->next!= NULL)
         {
             tail = tail -> next;
         }
         tail->next = newNode;
     }
}
void SListPopBack(SListNode** pphead)
{
     //1、空
     //2、一个结点
     //3、一个以上
     if (*pphead == NULL)
     {
         return ;
     }
     else if ((*pphead)->next == NULL)
     {
         free (*pphead);
         *pphead = NULL;
     }
     else
     {
         SListNode* prev = NULL;
         SListNode* tail = *pphead;
         while (tail->next != NULL)
         {
             prev = tail;
             tail = tail->next;
 
         }
         free (tail);
         //tail = NULL;//这个无所谓，因为我们释放后，出了这个作用域，tail和prev都被销毁，没人能拿到，所以不会被再找到
         prev->next = NULL;  
     }
}

4、头插头删

?
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
//头插头删
void SListPushFront(SListNode** pphead, SListDataType x)
{
     SListNode* newnode = BuySListNode(x);
     newnode->next = *pphead;
     *pphead = newnode;
}
void SListPopFront(SListNode** pphead)
{
     //1、空
     //2、一个结点+3、一个以上
    
     if (*pphead == NULL)
     {
         return ;
     }
     //(*phead)->next:*和>都是解引用，同一优先级，我们需要给*pphead带括号，(*pphead)->next才是下一个结点
    
     else {
         //我们头删也会遇到情况，我们删除第一个的话，第一个里面还存有第二个结点的地址，我们必须在删除前，保存第二个结点的地址
         SListNode* next = (*pphead)->next;
         free (*pphead); //通过调试我们发现：free前后，*pphead的地址不变，但是*pphead里的值被置为随机值，free不仅仅把这块空间还给操作系统
           //而且还把这块空间存的值和地址都置为随机值
         *pphead = next;
     }
 
}

 5、单链表查找

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//单链表查找
SListNode* SListFind(SListNode* phead, SListDataType x)
{
     SListNode* cur = phead;
     while (cur)
     {
         if (cur->data == x)
         {
             return cur;
         }
         cur = cur->next;
     }
     return NULL;
}

6、中间插入（在pos后面进行插入）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void SListInserAfter(SListNode** pphead,SListNode* pos, SListDataType x)
{
     assert (pos && pphead);
     if (*pphead == pos)
     {
         SListPushFront(pphead, x);
     }
     else
     {
         SListNode* newnode = BuySListNode(x);
         SListNode* tmp = *pphead;
         while (tmp->next != pos)
         {
             tmp = tmp->next;
         }
         tmp->next = pos;
         pos->next = newnode;
 
     }
    
}

 7、中间删除（在pos后面进行删除）

?
1
2
3
4
5
6
7
8
9
10
11
12
13
void SListEraseAfter(SListNode* pos)
{
     //删除pos后面的
     assert (pos);
     if (pos->next)
     {
         //pos->next=pos->next->next//不推荐
         SListNode* next = pos->next;
         SListNode* nextnext = next->next;
         pos->next = nextnext;
         free (next);
     }
}

8、单独打印链表和从头到尾打印链表

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void SListPrint(SListNode* phead)
{
     SListNode* cur = phead;
     while (cur != NULL)
     {
         printf ( "%d->" , cur->data);
         cur = cur->next;
     }
     printf ( "NULL\n" );
}
 
 
 
void PrintTailToHead(SListNode* pList)
{
     if (pList == NULL)
     {
         return ;
     }
     PrintTailToHead(pList->next);
     printf ( "%d->" ,pList->data);
}

9、test.c

?
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
#include"SList.h"
 
TestSList1()
{
 
     SListNode* pList = NULL; //这个结构体指针指向开辟的空间,头指针指向链表的开头
     SListPushBack(&pList, 1);
     SListPushBack(&pList, 2);
     SListPushBack(&pList, 3);
     SListPushBack(&pList, 4);
     SListPrint(pList);
 
     SListPopBack(&pList);
     SListPopBack(&pList);
     SListPopBack(&pList);
     SListPopBack(&pList);
     SListPopBack(&pList);
     SListPrint(pList);
 
     SListPushFront(&pList, 1);
     SListPushFront(&pList, 2);
     SListPushFront(&pList, 6);
     SListPushFront(&pList, 4);
     SListPushFront(&pList, 5);
     SListPrint(pList);
     SListPopFront(&pList);
     SListPopFront(&pList);
     SListPopFront(&pList);
     SListPopFront(&pList);
     SListPopFront(&pList);
     SListPopFront(&pList);
     SListPrint(pList);
 
 
}
 
TestSList2()
{
     SListNode* pos1;
     SListNode* pList = NULL; //这个结构体指针指向开辟的空间,头指针指向链表的开头
     SListPushBack(&pList, 1);
     SListPushBack(&pList, 2);
     SListPushBack(&pList, 3);
     SListPushBack(&pList, 4);
     SListPrint(pList);
     SListNode* pos = SListFind(pList, 3);
     if (pos)
     {
         pos->data = 30; //这里将cur-data改为pos->data,然后再将pos-data原来的值改为30
     }
     SListPrint(pList);
     pos1 = SListFind(pList, 30); //我们先去找到这个pos1的位置，然后再去插入
     SListInserAfter(&pList,pos1,50); //函数传参要对应起来，我们用指针传用指针接收，不能在pos1位置直接写个数字
     SListPrint(pList);
     SListEraseAfter(pos1); //pList指向第一个结点，pList->next指向第二个结点，那么我们删除的是目标节点后面
     SListPrint(pList);
     //PrintTailToHead(&pList);
}
int main()
{
     TestSList1();
     TestSList2();
     return 0;
    
 
}

总结

到此这篇关于C语言如何实现单链表的文章就介绍到这了,更多相关C语言实现单链表内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://blog.csdn.net/weixin_59551524/article/details/120115991 。

最后此篇关于一文弄懂C语言如何实现单链表的文章就讲到这里了,如果你想了解更多关于一文弄懂C语言如何实现单链表的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

29 4 0
文章推荐： C/C++中多重继承详解及其作用介绍
文章推荐： phpStudy vscode 搭建debug调试的教程详解
文章推荐： jQuery+PHP实现图片上传并提交功能
文章推荐： C++哈希应用的位图和布隆过滤器
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com