数据结构：单链表的实现(C语言)

个人主页 ： 水月梦镜花
个人专栏 ： 《C语言》 《数据结构》

文章目录

前言

本博客将要实现的无头单向不循环链表。

一、单链表实现思路和图解

1.节点的定义(SListNode)

我们将节点定义为如下结构：

其成员变量有data，next。

将int重命名为STLDataType，方便我们以后修改数据域的内容。

//无头单向不循环链表typedefint SLTDataType;typedefstructSListNode{
    SLTDataType data;structSListNode* next;}SListNode;

2.申请一个节点(BuySListNode)

动态申明一个空间，来放置数据。如下：

将data的内容置成形参x，next置NULL。

//申请一个节点
SListNode*BuySListNode(SLTDataType x){
    SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));if(newnode ==NULL){perror("malloc");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;

    retur

3.单链表打印(SListPrint)

循环遍历链表，直到尾节点。创建一个结构体指针变量cur，循环cur = cur->next，并打印cur->data的内容，直到cur == NULL。

//单链表打印voidSListPrint(SListNode* plist){
    SListNode* cur = plist;while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}

4.单链表尾插(SListPushBack)

• 如果链表不为NULL(链表中有元素)，要先遍历链表找到尾节点，在让尾节点指向新节点，完成尾插。
• 如果链表为NULL(链表中没有元素)，此时应该直接让新节点等于头结点，完成尾插。(本链表是无哨兵位的)
• 如果传入的头结点无效，直接判错。

当链表为NULL，我们就要修改头结点本身的内容，所以我们需要头结点的指针，而本文中头结点本身就是结构体指针，所以尾插函数参数我们需要二级指针。

//单链表尾插voidSListPushBack(SListNode** pplist, SLTDataType x){assert(pplist);

    SListNode* newnode =BuySListNode(x);if(*pplist !=NULL){
        SListNode* cur =*pplist;while(cur->next !=NULL){
            cur = cur->next;}
        cur->next = newnode;}else{*pplist = newnode;}}

5.单链表的头插(SListPushFront)

对于头插而言，链表是否有元素并不重要，我们只需要让新节点的指向头结点，并将头结点等于新节点。

因为头插链表，一定会改变头结点的内容，所以我们头插函数的形参也是二级指针。

//单链表的头插voidSListPushFront(SListNode** pplist, SLTDataType x){assert(pplist);

    SListNode* newnode =BuySListNode(x);
    
    newnode->next =*pplist;*pplist = newnode;}

6.单链表的尾删(SListPopBack)

• 如果链表元素有两个及两以上，我们需要两个指针变量prev，next来找尾节点，循环prev = cur，cur = cur->next，使next指向尾节点，prev指向尾节点的前一个，free尾节点，prev指向的节点指向NULL。
• 如果链表元素只有一个，直接free头结点，使头结点置NULL。
• 如果链表没有元素，直接判错。

当链表元素只有一个时，此时尾删链表，要修改头结点的内容，尾删函数的形参需要二级指针。

//单链表的尾删voidSListPopBack(SListNode** pplist){assert(pplist);//链表为NULLassert(*pplist);if((*pplist)->next ==NULL){free(*pplist);*pplist =NULL;}else{
        SListNode* cur =*pplist;
        SListNode* prev =NULL;while(cur->next !=NULL){
            prev = cur;
            cur = cur->next;}
        prev->next =NULL;free(cur);}}

7.单链表头删(SListPopFront)

我们需要一个结构体指针变量next，来保存头结点的下一个节点，然后free头结点，使头结点 = 指针变量next。

• 如果链表没有元素，直接判错。

//单链表头删voidSListPopFront(SListNode** pplist){assert(pplist);assert(*pplist);

    SListNode* next =(*pplist)->next;free(*pplist);*pplist = next;}

8.单链表的查找(SListFind)

我们需要一个结构体指针变量cur，来遍历链表比较cur->data == x，如果相等，放回此时cur的内容(该节点的地址)。如果遍历完链表，并没有相等元素，放回NULL。

//单链表的查找
SListNode*SListFind(SListNode* plist, SLTDataType x){
    SListNode* cur = plist;while(cur !=NULL){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}

9.单链表在pos位置之后插入x(SListInsertAfter)

我们让newnode指向pos下一个的节点，pos指向newnode。

• 如果我们先让pos指向newnode，newnode在指向pos的下一个节点，就会造成newnode指向自己，导致链表成环。
• 该函数不会影响头结点的内容，所以函数的形参不用二级指针。

//单链表在pos位置之后插入xvoidSListInsertAfter(SListNode* pos, SLTDataType x){assert(pos);

    SListNode* newnode =BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;}

10.单链表删除在pos位置之后的值(SListEraseAfter)

我们需要一个结构体指针变量next，记录pos下一个节点的地址，然后是pos指向next的下一个节点，接着free(next)。

• 如果链表只有一个元素，我们不能调用该函数，否则会导致NULL指针的解引用。
• 该函数不会改变头结点的内容，所以形参我们不用二级指针。

//单链表删除在pos位置之后的值voidSListEraseAfter(SListNode* pos){assert(pos && pos->next);

    SListNode* next = pos->next;
    pos->next = next->next;free(next);}

11.单链表的销毁(SListDestroy)

我们需要两个结构体指针prev，cur。先让prev = cur ，cur再指向下一个节点，free(prev)，重复上述操作，直到cur指向NULL。

需要我们在函数调用完后，自己对头结点置NULL。

//单链表的销毁voidSListDestroy(SListNode* plist){assert(plist);

    SListNode* cur = plist;while(cur !=NULL){
        SListNode* prev = cur;
        cur = cur->next;free(prev);}}

二、代码实现

//slist.h  文件#pragmaonce#define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>#include<stdlib.h>#include<assert.h>//无头单向不循环链表typedefint SLTDataType;typedefstructSListNode{
    SLTDataType data;structSListNode* next;}SListNode;//申请一个节点
SListNode*BuySListNode(SLTDataType x);//单链表打印voidSListPrint(SListNode* plist);//单链表尾插voidSListPushBack(SListNode** pplist, SLTDataType x);//单链表的头插voidSListPushFront(SListNode** pplist, SLTDataType x);//单链表的尾删voidSListPopBack(SListNode** pplist);//单链表头删voidSListPopFront(SListNode** pplist);//单链表的查找
SListNode*SListFind(SListNode* plist, SLTDataType x);//单链表在pos位置之后插入xvoidSListInsertAfter(SListNode* pos, SLTDataType x);//单链表删除在pos位置之后的值voidSListEraseAfter(SListNode* pos);//单链表的销毁voidSListDestroy(SListNode* plist);

//slist.c    文件#include"slist.h"//申请一个节点
SListNode*BuySListNode(SLTDataType x){
    SListNode* newnode =(SListNode*)malloc(sizeof(SListNode));if(newnode ==NULL){perror("malloc");exit(-1);}
    newnode->data = x;
    newnode->next =NULL;return newnode;}//单链表打印voidSListPrint(SListNode* plist){
    SListNode* cur = plist;while(cur !=NULL){printf("%d->", cur->data);
        cur = cur->next;}printf("NULL\n");}//单链表尾插voidSListPushBack(SListNode** pplist, SLTDataType x){assert(pplist);

    SListNode* newnode =BuySListNode(x);if(*pplist !=NULL){
        SListNode* cur =*pplist;while(cur->next !=NULL){
            cur = cur->next;}
        cur->next = newnode;}else{*pplist = newnode;}}//单链表的头插voidSListPushFront(SListNode** pplist, SLTDataType x){assert(pplist);

    SListNode* newnode =BuySListNode(x);
    
    newnode->next =*pplist;*pplist = newnode;}//单链表的尾删voidSListPopBack(SListNode** pplist){assert(pplist);//链表为NULLassert(*pplist);if((*pplist)->next ==NULL){free(*pplist);*pplist =NULL;}else{
        SListNode* cur =*pplist;
        SListNode* prev =NULL;while(cur->next !=NULL){
            prev = cur;
            cur = cur->next;}
        prev->next =NULL;free(cur);}}//单链表头删voidSListPopFront(SListNode** pplist){assert(pplist);assert(*pplist);

    SListNode* next =(*pplist)->next;free(*pplist);*pplist = next;}//单链表的查找
SListNode*SListFind(SListNode* plist, SLTDataType x){
    SListNode* cur = plist;while(cur !=NULL){if(cur->data == x){return cur;}
        cur = cur->next;}returnNULL;}//单链表在pos位置之后插入xvoidSListInsertAfter(SListNode* pos, SLTDataType x){assert(pos);

    SListNode* newnode =BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;}//单链表删除在pos位置之后的值voidSListEraseAfter(SListNode* pos){assert(pos && pos->next);

    SListNode* next = pos->next;
    pos->next = next->next;free(next);}//单链表的销毁voidSListDestroy(SListNode* plist){assert(plist);

    SListNode* cur = plist;while(cur !=NULL){
        SListNode* prev = cur;
        cur = cur->next;free(prev);}}

总结

以上就是我对于无头单向不循环链表的实现！！！