初阶数据结构学习记录——셋 单链表(1)

目录

SList.h

SList.c

test.c

1、尾插

2、尾删

3、头部操作

4、test.c

---

从顺序表中可以看出，实现增删等功能需要一个个挪动，并不简洁，比较繁琐。扩容时，需要整个进行扩容，如果是异地扩容，有一定代价，且可能存在一定空间浪费。

针对这些问题的优化方案就是按需事情释放和不挪动数据。想使用再开辟一个，而要读取这些空间时，遍历并不行，用指针可快速访问，因此也就出现了链表。在链表中，每一块空间就是一个节点。具体以代码呈现。

struct SListNode
{
    int data;
    struct SListNode* next;
}

结构体里放一个指针，用来指向下一个节点.为了清楚地看到链表的结构。我先放上一小段代码。

SList.h

#pragma once
#include 
#include 
#include 
 
typedef int SLTDataType;
 
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
 
SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);
 
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);

SList.c

#include "SList.h"
 
SLTNode* BuySLTNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;//这里返回一个指针的地址，自然要用一个指针来接收。
}
 
SLTNode* CreateSList(int n)
{
    SLTNode* phead = NULL, * ptail = NULL;
    for (int i = 0; i < n; ++i)
    {
        SLTNode* newnode = BuySLTNode(i + 10);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
    }
    return phead;//其实phead也是局部变量，也被销毁了，但是在这之前已经传回去了。函数外负责接收的指针就能拿到整个链表的头位置地址，操作者也就可以使用这个链表了。
}
 
void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur != NULL)
    {
        //printf("[%d|%p]->", cur->data, cur->next);
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

 

test.c

#include "SList.h"
 
void TestSList1()
{
        /*SLTNode* n1 = BuySLTNode(1);//为什么要用指针而不是SLTNode sl？因为整个链表每个节点我们需要保存好内容，如果第二种办法，开辟在栈区，那么出了函数数据就没有了，而创建指针，使用malloc，就会存储在堆区，自然也就符合要求了
        SLTNode* n2 = BuySLTNode(2);
        SLTNode* n3 = BuySLTNode(3);
        SLTNode* n4 = BuySLTNode(4);
        n1->next = n2;
        n2->next = n3;
        n3->next = n4;
        n4->next = NULL;*/
    SLTNode* plist = CreateSList(10);
    SLTPrint(plist);
}
 
int main()
{
    TestSList1();
    return 0;
}

链表有很多种，不过比较核心的就是无头单向非循环链表和带头双向循环链表。这篇文章写无头单向非循环链表。但本篇所写的代码一定是挫的，因为本篇主要在于理解单链表，之后再升级。

刚才上头所写其实就是一个单链表。我们继续写它的插删等功能

1、尾插

事实上，单的尾部动作比较麻烦。尾插我们需要先找到尾，可是我们只有头，所以就需要一点点移过去，但是这样写是错误的

SLTNode* newnode = BuySLTNode(x);
SLTNode* tail = phead;
while (tail != NULL)
{
    tail = tail->next;
}
tail = newnode;

为什么错误？tail->next是NULL的时候，tail被赋值为NULL，然后退出循环，把newnode给了tail，但是那个next并没有连接上newnode。这只是tail自己在改变。当退出整个函数时，tail这个局部变量就没了，newnode也没了，尾插并没有实现。

while (tail->next != NULL)
{
    tail = tail->next;
}
tail->next = newnode;

所以我们需要控制好next和tail才能完成基本的单链表。现在在test.c做个测试

void TestSList2()
{
    SLTNode* plist = CreateSList(5);
    SLTPushBack(&plist, 100);
    SLTPushBack(&plist, 200);
    SLTPushBack(&plist, 300);
    SLTPrint(plist);
}
 
int main()
{
    TestSList2();
    return 0;
}

输出结果很正确，是我们所想的。不过还有一个问题，如果头是个NULL呢？是NULL仍然可以继续运行，这不耽误什么，我们对尾插函数做一下改动即可

void SLTPushBack(SLTNode* phead, SLTDataType x)
{
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = phead;
    if (phead == NULL)
    {
        phead = newnode;
    }
    else
    {
        //找尾
        while (tail->next != NULL)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

好，即使这样，phead = NULL开始执行后，打印出来的结果却是NULL。我插入的值呢？这个问题可能容易被忽略掉，plist是个指针，尾插的时候传过去的是plist，这个问题就和要交换两个数值，传过去的数值一样，要想改变plist这个指针的内容，就需要对指针的地址进行操作。所以phead应该是二级指针。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySLTNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        //找尾
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

2、尾删

void SLTPopBack(SLTNode** phead)
{
    SLTNode* tail = *phead;
    while (tail->next)
    {
        tail = tail->next;
    }
    free(tail);
    tail = NULL;
}

一段错误的代码。tail一直往后走，走到最后一个时，tail出循环，然后free，再出函数。tai是一个局部变量，出了函数就消失了，但是还在函数内时就已经释放最后指向的空间了。假设插入100,200,300。300所在的空间被释放了，看似已经删除，但是200的next并没有变成NULL，而是还指向第三块空间，这时候它就变成野指针了，因为没有我们没有写改变第二个next的代码。解决方案有两个，一个是双指针走，这样就能有另一个指针指向第二个。或者，while判断里tail->next->next，对后后个进行判断，tail停下来的时候就能停在第二个了。下面是第一个写法.

void SLTPopBack(SLTNode** phead)
{
    SLTNode* tail = *phead;
    SLTNode* prev = NULL;
    while (tail->next)
    {
        prev = tail;
        tail = tail->next;
    }
    free(tail);
    prev->next = NULL;
    tail = NULL;

一次次删除后，又出现了问题，删到还剩最后一个时，这个函数貌似没法正常完成，需要单独处理这个情况，所以

void SLTPopBack(SLTNode** pphead)
{
    assert(*pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        SLTNode* prev = NULL;
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

现在这个尾删没啥问题了。但是呢，总还有失误的地方。如果没记清自己插入了多少数据，删干净后又来了一次，编译器可就难受了。为了应对这个情况，我们断言一下即可assert(*pphead)，不过尾插就不需要了。

第二个写法：

void SLTPopBack(SLTNode** pphead)
{
    assert(*pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
 
		free(tail->next);
		tail->next = NULL;
    }
}

3、头部操作

链表的头部操作很简单。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;//即使为空，也不需要单独处理
    *pphead = newnode;//pphead指向新的头；
}
 
void SLTPopFront(SLTNode** pphead)
{
    assert(*pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;//只剩一个时也不需要单独处理
}

头插和头删功能很简单。这也是链表的优势所在，链表的尾部操作其实比较繁琐。

4、test.c

void TestSList3()
{
    SLTNode* plist = NULL;
    SLTPushBack(&plist, 100);
    SLTPushBack(&plist, 200);
    SLTPushBack(&plist, 300);
    SLTPrint(plist);
 
    SLTPopBack(&plist);
    SLTPrint(plist);
 
    SLTPopBack(&plist);
    SLTPrint(plist);
 
    SLTPopBack(&plist);
    SLTPrint(plist);
 
    //SLTPopBack(&plist);
    //SLTPrint(plist);
}
 
void TestSList4()
{
    SLTNode* plist = NULL;
    SLTPushFront(&plist, 100);
    SLTPushFront(&plist, 200);
    SLTPushFront(&plist, 300);
    SLTPushFront(&plist, 400);
 
    SLTPrint(plist);
 
    SLTPopFront(&plist);
    SLTPrint(plist);
    SLTPopFront(&plist);
    SLTPrint(plist);
    SLTPopFront(&plist);
    SLTPrint(plist);
    SLTPopFront(&plist);
    SLTPrint(plist);
}
 
int main()
{
    TestSList4();
    return 0;
}

关于pos位置的操作下一篇再写。

结束。