考研数据结构之单链表的实现（基于C语言）

系统管理员 2023-09-29 17:36 13阅读 0赞

> 今天带大家来实现一下单链表的初始化，尾插，头插，随机删除

#### 文章目录 ####

*  前言：**什么是单链表，单链表的初始化**
 *  一、单链表是什么？
 *  二、使用步骤
    
     *  1.首先是单链表的初始化
     *  2.单链表的尾插和头插
     *  3.**单链表的删除**
 *  总结

--------------------

## 前言 ##

**什么是单链表？单链表其实也是一块线性结构，并且是链式存储的，但是它相比与顺序表来顺序表就是顺序存储的，就不是很方便，因为他得放在一起，而单链表就是可以不用放在一起，并且只要你的电脑运行的内存够大，就可以一直的动态开辟**

--------------------

`提示：以下是本篇文章正文内容，下面案例可供参考`

## 一、单链表是什么？ ##

在内存中，他是一块连续的地址，我们这里选择一种带头的头结点来为大家讲解

![e41379a0c20547fc96843204bd2af567.png][]

如图所示，单链表的结尾是指向NULL这一点比较重要，需要记住好啦。知道具体的结构之后我们来走入代码吧！

## 二、使用步骤 ##

### 1.首先是单链表的初始化 ###

其实初始化，很简单初始化其实就是把我们的地址赋给NULL，因为我们单链表的结束条件是指针域指向NULL嘛，所以我们在一开始的时候就直接把我们的指针域指向NULL，那我们的初始化是不是就已经完成了呢？对的，没错就是这么一个道理噢！

代码如下（示例）：

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    typedef int datatype;
    struct slistnode
    {
        datatype data;
        struct slistnode* next;
    };
    
    struct slistnode* slist_init()
    {
        struct slistnode* phead = (struct slistnode*)malloc(sizeof(struct slistnode));
        if(phead == NULL)
        {
            printf("malloc fail\n");
            return NULL;
        }
        phead->next = NULL;
        return phead;
    }

### 2.单链表的尾插和头插 ###

1.那么什么是头插和尾插呢？首先我们要插入的话我们的形参是不是必须得有要插入的数据呢？是的，那么是不是还要我们要插入的链表呢？没错

讲一下思路吧，我们既然要选择插入，那么我们是不是应该先malloc一块新的元素，然后在把这块地址放到我们想放到的地方

接下来我们画图来解释

![0e67b96db7364fa78a87dd8f3b93791b.png][]

首先我们先讲头插，你们想我们的结束条件是什么，是不是最后一块地址所存储的东西存储的是NULL这样才算是结束，那么我们此时的NULL哪里去寻找呢？这时候我们可以回忆一下，我们初始化的时候是不是把刚开始的头结点的next放了NULL对吧。好啦这时候我们就可以直接把pnew->next = phead->next;这句话就是把NULL赋给了pnew的next，那么这时候我们是不是已经找到了我们的结束条件了，这时候我们的链表是不是还没有链接起来，因为我们是链式存储的嘛 ，在把他们链接起来就好啦！

bool slist_head(struct slistnode* phead, datatype x)
    {
        struct slistnode* pnew = (struct slistnode*)malloc(sizeof(struct slistnode));
        if (pnew == NULL)
        {
            printf("malloc fail");
            return false;
        }
        pnew->next = NULL;
        pnew->data = x;
        pnew->next = phead->next;
        phead->next = pnew;
        return true;
    }好啦头插写完了，该写尾插啦！  那么什么是尾插，其实就是在尾部插入啦，你觉得难嘛？其实不难的，我们来看看图吧

![91097407dcc0414aa8abb02d278d23c3.png][]

其实单链表的插入就是把新开辟的元素的地址存入到当前链表最后一个位置就行啦是不是很简单呢？我们直接上代码吧！

> bool slist\_tail(struct slistnode\* phead, datatype x)  
> \{  
> struct slistnode\* pnew = (struct slistnode\*)malloc(sizeof(struct slistnode));  
> if (pnew == NULL)  
> \{  
> printf("malloc fail\\n");  
> return NULL;  
> \}  
> pnew->data = x;  
> pnew->next = NULL;  
> struct slistnode\* tail = phead->next;  
> while (tail->next != NULL)  
> \{  
> tail = tail->next;  
> \}  
> tail->next = pnew;  
> pnew = tail;  
> return true;  
> \}

### **3.单链表的删除** ###

**最后我们来讲一下单链表的删除吧！什么是删除呢？其实单链表的删除是非常不方便的，为什么呢？我们来分析一下，首先我们需要找到当前你要删除的数据吧？找到了假设你把这个数据删了，那么前后就链接不到一起了，这样的话就会出现野指针的情况前后找不到了，所以此次的删除的话，我们需要两个指针来执行，一个在前一个在后，后追着前，这样我们是不是就可以解决了找不到前后的问题了呢？**

> **bool slist\_delete(struct slistnode\* phead, datatype x)  
> \{  
> struct slistnode\* tail = phead;  
> struct slistnode\* prev = phead->next;  
> while (prev)  
> \{  
> if (x == prev->data)  
> \{  
> tail->next = prev->next;  
> free(prev);  
> return true;  
> \}  
> tail = prev;  
> prev = prev->next;  
> \}  
> if (prev == NULL)  
> return false;  
> \}**

--------------------

## 总结：一定要自己动手敲一下，不要直接cv了啦，你要记住学习是给自己学的，不是给别人学的！ ##

> \#define \_CRT\_SECURE\_NO\_WARNINGS 1
> 
> \#include<stdio.h>  
> \#include<stdlib.h>  
> \#include<stdbool.h>  
> typedef int datatype;  
> struct slistnode  
> \{  
> datatype data;  
> struct slistnode\* next;  
> \};
> 
> struct slistnode\* slist\_init()  
> \{  
> struct slistnode\* phead = (struct slistnode\*)malloc(sizeof(struct slistnode));  
> if (phead == NULL)  
> \{  
> printf("malloc fail\\n");  
> return NULL;  
> \}  
> phead->next = NULL;  
> return phead;  
> \}  
> bool slist\_head(struct slistnode\* phead, datatype x)  
> \{  
> struct slistnode\* pnew = (struct slistnode\*)malloc(sizeof(struct slistnode));  
> if (pnew == NULL)  
> \{  
> printf("malloc fail");  
> return false;  
> \}  
> pnew->next = NULL;  
> pnew->data = x;  
> pnew->next = phead->next;  
> phead->next = pnew;  
> return true;  
> \}  
> bool slist\_tail(struct slistnode\* phead, datatype x)  
> \{  
> struct slistnode\* pnew = (struct slistnode\*)malloc(sizeof(struct slistnode));  
> if (pnew == NULL)  
> \{  
> printf("malloc fail\\n");  
> return NULL;  
> \}  
> pnew->data = x;  
> pnew->next = NULL;  
> struct slistnode\* tail = phead->next;  
> while (tail->next != NULL)  
> \{  
> tail = tail->next;  
> \}  
> tail->next = pnew;  
> //new = tail;  
> return true;  
> \}  
> bool is\_empty(struct slistnode\* phead)  
> \{  
> if (phead->next == NULL)  
> return true;  
> else  
> return false;  
> \}  
> bool slist\_Print(struct slistnode\* phead)  
> \{  
> if (is\_empty(phead))  
> return false;  
> struct slistnode\* cur = phead->next;  
> while (cur)  
> \{  
> printf("%d ", cur->data);  
> cur = cur->next;  
> \}  
> printf("\\n");  
> return true;  
> \}  
> bool slist\_delete(struct slistnode\* phead, datatype x)  
> \{  
> struct slistnode\* tail = phead;  
> struct slistnode\* prev = phead->next;  
> while (prev)  
> \{  
> if (x == prev->data)  
> \{  
> tail->next = prev->next;  
> free(prev);  
> return true;  
> \}  
> tail = prev;  
> prev = prev->next;  
> \}  
> if (prev == NULL)  
> return false;  
> \}  
> int main()  
> \{  
> struct slistnode\* plist = slist\_init();  
> slist\_head(plist, 1);  
> slist\_head(plist, 2);  
> slist\_head(plist, 3);  
> slist\_head(plist, 4);  
> slist\_Print(plist);  
> slist\_delete(plist, 1);  
> slist\_Print(plist);  
> slist\_delete(plist, 0);  
> slist\_Print(plist);  
> return 0;  
> \}

[e41379a0c20547fc96843204bd2af567.png]: https://img-blog.csdnimg.cn/e41379a0c20547fc96843204bd2af567.png
[0e67b96db7364fa78a87dd8f3b93791b.png]: https://img-blog.csdnimg.cn/0e67b96db7364fa78a87dd8f3b93791b.png
[91097407dcc0414aa8abb02d278d23c3.png]: https://img-blog.csdnimg.cn/91097407dcc0414aa8abb02d278d23c3.png