[数据结构]单链表C语言的简单实现

你的名字 2022-06-04 01:20 197阅读 0赞

Github:([https://github.com/FlameCharmander/DataStructure][https_github.com_FlameCharmander_DataStructure])  
本来是在和顺序表里放一起写。但是考虑简洁的话，就这样写了。  
直接上链表的代码了。

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElemType;
    typedef int BOOL;
    #define TRUE 1
    #define FALSE 0
    
    typedef struct LinkNode{
        ElemType data;
        struct LinkNode* next;
    }LinkList, Node;
    
    void InitList(LinkList *list);   //初始化链表
    BOOL Insert(LinkList *list, ElemType e, int pos);   //将元素插入
    BOOL Delete(LinkList *list, ElemType e);    //将指定元素删除
    BOOL IsEmtpy(LinkList *list);   //判断链表是否为空
    
    int main()
    {
        LinkList list;
        InitList(&list);
        printf("%d\n", IsEmtpy(&list));
        Insert(&list, 'a', 1);
        Insert(&list, 'b', 2);
        Insert(&list, 'c', 1);
        Delete(&list, 'a');
        Node *p = list.next;
        while (p != NULL) {
            printf("%c ", p->data);
            p = p->next;
        }
        printf("\n%d\n", IsEmtpy(&list));
        Delete(&list, 'b');
        Delete(&list, 'c');
        printf("%d\n", IsEmtpy(&list));
        return 0;
    }
    
    void InitList(LinkList *list){
        list->next = NULL; //设置一个头结点
    }
    
    BOOL Insert(LinkList *list, ElemType e, int pos){
        int i;
        Node* pre = list;
        for (i = 1; i < pos; ++i){
            pre = pre->next;
        }
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = e;
        node->next = pre->next;
        pre->next = node;
        return TRUE;
    }
    
    BOOL Delete(LinkList *list, ElemType e){
        Node* pre = list;
        while (pre->next != NULL) {
            if (pre->next->data == e){
                Node* q = pre->next;    //临时存储
                pre->next = pre->next->next;
                free(q);
                return TRUE;
            } else {
                pre = pre->next;
            }
        }
        return FALSE;
    }
    
    BOOL IsEmtpy(LinkList *list){
        if (list->next == NULL) {
            return TRUE;
        } else {
            return FALSE;
        }
    }

老规矩，要对代码做一个解释了，可以再开窗口对照着看。  
Line 1~2 是导入头文件  
Line 4 Typedef是给用来为复杂的声明定义简单的别名，所以这里我这里设置ElemType char，如果到时链表的元素类型不是char，比如只要int，只需typedef int ElemType。  
Line 5~7 由于C语言没有布尔类型，所以这里用了int代替，1代表True,0代表False  
Line 9~12 这是链表的数据结构，如果不太熟的话，去看看理论部分吧。  
Line 14~17 函数的声明，如果函数写在main函数下面，需要在这里做个定义  
Line 19~38 这里是main函数，就是将所写的操作给测试一下，看有没有出错  
Line 40~42 这里默认链表是有头结点的，这样插入和删除等会方便很多，如果你不知道头结点是什么，我简单说下，头结点就是一个没有值的结点，下面会讲为什么需要投结点。  
Line 44~55 这就是我们的插入操作了。1<=pos<=n。  
Line 46 pre代表是前一个结点的意思。我画了张图，是链表插入了元素a,b之后的图。  
![插入a和b之后的链表][a_b]  
第一个没有值的结点就是头结点了，现在我们要插入c到1的位置，也就是a的前面，那么我们需要a之前的结点（现在这个结点是头结点）才能把c插入到a的前面对吧。  
那你试想下，如果没有头结点的话，那是不是还要判断插入结点是第一个结点还是第一个结点之后。（你们想象下没有头结点的插入就知道了）  
Line 47~49 这个是寻找要插入的位置的前一个结点  
Line 50~51 申请一个新的结点，并把要插入的元素（现在是c）赋值到数据域，我们即将要把它插入到我们想要的位置。  
Line 52~54 看下下面这个图  
![插入c][c]

`node->next = pre->next;`将c的指针域指向到a  
`pre->next = node;`将pre结点（现在是头结点）的指针域指向c  
然后返回真，这就完成了一次插入操作，请注意，我们要插入一个结点，需要的是前一个结点。  
Line 57~70 删除操作  
我们把刚才的插入完C的表重新调整一下。  
![插入C之后的链表][C]  
Line 59 是遍历全部结点  
![删除a][a]  
Line 60 是找到要删除的结点的前一个结点  
Line 61 用指针q指向结点a，看图  
Line 62 比如现在找到了c（a的前一个结点），那我们要把a删除，把c的指针域指向b结点即可  
Line 63 这时结点a就没有了任何存在的意义了,我们需要手动释放它，这里的Line 61~63的顺序是不能换的，耐人寻味。为什么不能先释放呢，因为我们如果先释放了，那我们c结点就找不到a结点的后一个结点b了  
Line 72~78 由于有头结点，所以判断的条件next是否为空。

[https_github.com_FlameCharmander_DataStructure]: https://github.com/FlameCharmander/DataStructure
[a_b]: /images/20220604/14b7c806340c401ba2388e8865a39db4.png
[c]: /images/20220604/ec63a23ec44a4686b70f7e0ef52d41fd.png
[C]: /images/20220604/7f57412f574546b28c8b97da47fd2bca.png
[a]: /images/20220604/11da9d6b5a284ea0b41809245f0cb599.png