[C语言实现]数据结构——单链表详解(1)_typedef struct slistnode { sltdatetype data; struc

---

目录

什么是链表？

为什么需要链表？

链表的实现：

链表的结构体实现

链表的头插/尾插

链表的头删/尾删

链表的打印

---

哟呼！大家好吖，今天这篇博客给大家带来的是小吃鲷鱼烧——不循环单链表的部分详解，剩余详解我们会放到下一篇博客捏！

什么是链表？

链表是一种物理存储单元上非连续、非顺序的存储结构，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。——百度百科。

为什么需要链表？

顺序表在物理结构和逻辑结构上都是一片连续的存储空间，每一次的连续空间开辟都会造成内存中有闲散的内存碎片没有利用起来，并且有些情况下需要大量的连续存储空间，内存不一定能分出这一部分空间来存储数据。

其次，对于顺序表来说，我们的查找操作是非常简便的，而插入和删除操作是非常复杂的，如果在第一个结点进行插入会把之后所有的元素都往后移动一位，非常繁琐。因此，链表应运而生，顾名思义，可以把一个个空间连起来，形成一片逻辑上连续的空间来存储数据，并且插入和删除操作非常简便，当然有优势也会有劣势，链表的查找操作就不是那么方便了。

链表的实现：

我们分为test.c Slist.h与Slist.c来实现链表，把函数放进Slist.c中实现，声明放入Slist.h中。

---

链表的结构体实现

链表，要找到下一个元素就需要把存储空间一分为二，一部分存储当前结点的元素，另一部分存储下一结点的地址。所以我们选择用结构体来实现。

//Slist.h
 
typedef int SLTDataType;
//利用typdef类型重定义来定义链表的数据类型以及结构体的简写。
//便于以后链表数据类型的更换以及结构体类型声明。
typedef struct SListNode{
    SLTDataType data;
    struct SListNode* next;
}SLTNode;

链表的头插/尾插：

用户在test.c中创建一个结构体的头指针head，并赋值为NULL，意为空链表，当用户需要头插和尾插时，传入空链表的头指针和插入的数据即可。

尾插：

我们接下来思考怎么尾插，我们拿到头指针后，找到最后一个位置，再新建一个结点，结点的data域里放入插入数据的值，然后把结点的next域置为NULL，把头指针指向新的结点上就行。

void SLTNodePushBack(SLTNode *phead, SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if(newnode == NULL)
    {
        printf("malloc fail;\n");
        exit(-1);//内存开辟失败，退出程序
    }
    newnode->data = x;
    newnode->next = NULL;
    //因为链表最后一个元素的next为NULL
    //所以通过NULL来找到最后结点
    while(phead -> next != NULL)
    {
        phead = phead->next;
    }
    //插入结点
    phead -> next = newnode;
}

我们来看看是否所有情况都能插入成功，很显然，我们循环里用的phead->next != NULL 会对phead进行解引用访问，但是用户传的可能是空链表啊，对NULL进行解引用不就错误访问了吗？所以我们还得修改一下这段代码！

void SLTNodePushBack(SLTNode *phead, SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if(newnode == NULL)
    {
        printf("malloc fail;\n");
        exit(-1);//内存开辟失败，退出程序
    }
    newnode->data = x;
    newnode->next = NULL;
    if(phead == NULL)
    {
        phead = newnode;//直接插入
        return;
    }
    //因为链表最后一个元素的next为NULL
    //所以通过NULL来找到最后结点
    while(phead -> next != NULL)
    {
        phead = phead->next;
    }
    //插入结点
    phead -> next = newnode;
}

我们再来思考一下，这样真的能插入成功吗？？我们传入的是一个结构体指针，我们要通过指针改变结构体内容，需要解引用操作，可我们上述代码中直接插入时phead = newnode 改变的是形参 而不是实参，并没有对phead进行解引用操作。 所以我们要改变phead时，我们需要使用二级指针，因此我们传入的也不是结构体指针，而是结构体指针的地址。

代码改变如下：

void SLTNodePushBack(SLTNode **pphead, SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if(newnode == NULL)
    {
        printf("malloc fail;\n");
        exit(-1);//内存开辟失败，退出程序
    }
    newnode->data = x;
    newnode->next = NULL;
    if(*pphead == NULL)
    {
        *pphead = newnode;//直接插入
        return;
    }
    //因为链表最后一个元素的next为NULL
    //所以通过NULL来找到最后结点
    SLTNode* cur = *pphead;
    while(cur -> next != NULL)
    {
        cur = cur->next;
    }
    //插入结点
    cur -> next = newnode;
}

头插：

我们接下来开始实现头插，头插相比尾插就非常简单了，我们直接让新结点的next域指向现在的第一个结点，然后让 *pphead指向新结点就好了。

我们发现不论是头插还是尾插，都需要创建新的结点，所以我们不妨先把创建一个新结点做成一个函数。

SLTNode* BuyNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if(newnode == NULL)
    {
        printf("malloc fail;\n");
        exit(-1);
    }
    newnode -> data = x;
    newnode -> next = NULL;
    return newnode;
}
 
void SLTNodePushFront(SLTNode **pphead, SLTDataType x)
{
    SLTNode* newnode = BuyNode(x);
    newnode -> next = *pphead;
    *pphead = newnode;
}

链表的头删/尾删

我们把链表的头插和尾插实现之后，就可以着手实现链表的头删和尾删了。

头删：

因为我们有一个指向第一个结点的指针，所以我们只需要把第一个结点free掉，并让这个指针指向下一个结点就行了，但是能找到下一结点地址的也只有上一结点，所以我们需要新建一个指针变量。

void SLTNodePopFront(SLTNode **pphead)
{
    if(*pphead == NULL)
    {
        printf("链表为空，无法进行删除操作！\n");
        return;
    }
    SLTNode* prev = *pphead;
    *pphead = *pphead -> next;
    free(prev);   
}

尾删：

我们先遍历链表找到倒数第二个结点，然后把最后一个结点free，倒数第二个结点的next变成NULL就行，但是注意，如果只有一个元素的时候，那么找倒数第二个结点就会造成错误访问，所以我们要单独把这一种情况拎出来。

void SLTNodePopBack(SLTNode **pphead)
{
    if(*pphead == NULL)
    {
        printf("链表为空，删除失败！\n");
        return;
    }
    SLTNode* prev = NULL;//指向倒数第二个结点
    SLTNode* cur = *pphead;//指向尾结点
    while(cur -> next)
    {
        prev = cur;
        cur = cur->next;
    }
    if(prev == NULL)//代表是只有一个结点
    {
        *pphead = NULL;
        free(*pphead);
        return;
    }
    free(cur);
    prev -> next = NULL;
}

链表的打印：

void PrintSLT(SLTNode* phead)
{
    while(phead)
    {
        printf("%d->", phead->data);
        phead = phead->next;
    }
    printf("NULL\n");
}

还剩下链表的插入和删除的内容，我会在下一篇博客详细解释。