无头单向非循环链表(详解)

链表的种类的简单介绍

链表的种类有很多
1.分有头链表和无头链表
2.分循环链表和非循环链表
3.分单向链表和双向链表

这里的话，我就讲解2种类型的链表，第一种是无头单向非循环链表，第二种是有头双向循环链表
这里讲解第一种，第二种将会在下一篇博客中讲解

链表的定义

如图所示，链表分为指针域和数据域，
指针域一般命名为next指向下一个指针，起连接的作用，使数据连续，
数据域如果a1, a2所示，用来存放链表中这个节点的数据
无头链表的话，代表这第一个节点，也就是头结点，存放的数据是有效的
如果是有头节点的话，数据域存放的数据是无效的，是一个垃圾值。

typedef的运用

typedef 实际上也就是重定义
可以用来重定义结构或者数据的类型
用typedef的话，修改起来比较方便，根据我的理解跟宏定义的作用相似

typedef int SqListType;

struct SqListNode
{
	SqListType  date;
	struct SqListNode* next;
};

typedef struct SqListNode SqList;
1
2
3
4
5
6
7
8
9
10

如果所示，这里用结构体来定义链表
SqListType代表着这是int类型
SqList代表着 这是 struct SqListNode类型

使用typedef 的作用就是方便命名，便于修改

节点的创建

节点的创建，首先的话，也就是考察C语言的动态内存管理，用malloc函数或者用realloc函数
当然，
1.我们这里使用malloc函数来开辟空间
2.开辟完之后，给这个节点的数据域赋值，
3.给指针域初始化，
4.然后返回这个节点

SqList* creatNode(SqListType date)
{
    SqList* node = (SqList*)malloc(sizeof(SqListType));

    node->date = date;
    node->next = NULL;

    return node;
}
1
2
3
4
5
6
7
8
9

当然，这里函数的参数，加一个const，效果应该会更好些，因为这创建节点所传的数据本来就是个常数。

遍历

链表的遍历的话，同样挺简单的，因为通过观察可以知道
链表的最后一个节点，也就是尾节点
他的指针域没有指向下一个节点
说明，尾结点的指针域为NULL，也就是尾结点的next为空

void printDate(SqList* phead)
{ 
    SqList* cur = phead;

    while (cur)
    {
        printf("%d ", cur->date);
        cur = cur->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

这里的话
遍历肯定是用循环
如果不是尾结点的话，就打印这个节点的数据域
然后该节点等于下一个节点（也就是节点的移动，移动到下一个节点）
如果cur = tail(尾结点)->next的时候
当前节点运动到，尾结点的下一个节点，结束循环

头插

头插的话，也就是，在链表的头部前面在插入一个节点
同样不难，也就三步
不过这里要分2种情况
第一种，如果该链表是空链表的话，就直接让当前的头结点 = 新节点
第二种，如果该链表不是空链表
1.创建新节点(直接调用之前写的创建新节点的函数就行)
2.然后新节点成为头节点
3.新节点的指针域指向原来的头结点

void front_back(SqList** pphead, SqListType date)
{
    SqList* new = creatNode(date);
    if (NULL == *pphead)
    {
        *pphead = new;
    }
    else
    {
        //连节点
        SqList* head = *pphead;
        *pphead = new;
        new->next = head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

当然这里使用了二级指针，如果是值的改变，使用二级指针
因为形参不影响实参
如果不涉及到值的改变，用一级指针
当然，如果你要用二级指针也可以

尾插

尾插的话，跟头插类似
也就比头插多了一个步骤，因为链表的头结点是已知的，不需要我们找
但是链表的尾结点是未知的，所以，
1.找到链表的尾结点
2.创建新节点
3.链表的尾结点指向新节点

当然，注意这里也要判断下，链表是否为空

void push_back(SqList** pphead, SqListType date)
{
    SqList* newNode = creatNode(date);

    if (NULL == *pphead)
    {
        *pphead = newNode;
    }
    else
    {
        SqList* tail = *pphead;
        while (NULL != tail->next)
        {
            tail = tail->next;
        }
        tail->next = newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

头删

头删的话，也就是删除链表的第一个节点
然后链表头结点的下一个节点，成为该链表新的头节点
当然，也要判断链表是否为空
如果，链表为空的话，就直接退出这个函数

当然链表的删除，就直接用free函数，释放这个节点的内存就行

具体代码如下：

void pop_front(SqList** pphead)
{
    if (NULL == *pphead)
    {
        printf("空链表");
        return;
    }
    else
    {
        SqList* Next = (* pphead)->next;
        free(*pphead);
        *pphead = Next;
    }

> 这里是引用

    /*SLTNode* next = (*pphead)->next;
    free(*pphead);

    *pphead = next;*/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

当然，这里需要注意的是，如果你先删除了头节点，那么你头节点的下一个节点的位置就找不到，
所以，你必须先要记录头节点下一个节点的位置，在进行删除

尾删

尾删的话，跟头删差不多
找到尾结点的位置，和尾结点的上一个节点的位置
删除尾结点
尾结点的上一个节点成为新的尾结点
同样要注意：
1.链表是否为空的情况
2.尾结点的指针域要置空
(虽然说，你用free函数删除，但是要避免这个不为空，是野指针的情况)

查找节点位置

查找的话，也挺简单的
就挨个遍历，这个链表
如果这个节点的数据域等于你要查找的数据，那么就返回这个节点的位置
如果说找不到的话，就返回空

SqList* findDate(SqList* phead, SqListType date)
{
    SqList* p = phead;

    while (date != p->date)
    {
        p = p->next;
    }

    return p;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

任意位置插入

任意位置插入的话，这里我是结合前面的查找函数使用
通过给出的数据，通过查找函数，返回这个节点的位置
根据这个位置，在这个位置之后插入新的节点

插入的思想，跟头插类似
1.新节点的下一个节点指向原来位置节点的下一个节点
2.原来位置的节点指向下一个新节点

当然同样要考虑链表是否为空的情况

// pos前面插入date
void insert(SqList** pphead, SqList* pos, SqListType date)
{
    if (NULL == *pphead)
    {
        *pphead = creatNode(date);
        (*pphead)->next = NULL;
    }
    else
    {
        SqList* new = creatNode(date);
        SqList* pre = *pphead;

        while (pos != pre->next)
        {
            pre = pre->next;
        }

        pre->next = new;
        new->next = pos;
    }
   
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

任意位置删除

任意位置删除的思想，其实跟那个尾删差不多
当然也要考虑，链表是否为空的情况

用查找函数，找到要删除节点的位置
1.要知道要删除节点，前一个节点的位置，后一个节点的位置已知
2,要删除节点的前一个节点指向删除节点的后一个节点

void pop_back(SqList** pphead)
{
    if (NULL == *pphead) // 没有节点
    {
        printf("空链表");
        return;
    }
    else if(NULL !=(*pphead)->next) //只有一个节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SqList* tail = *pphead;
        SqList* pre = NULL;
        //找到尾结点和尾结点的前一个节点 
        while( NULL != tail->next)
        {
            pre = tail;
            tail = tail->next;
        }

        free(tail);
        pre->next = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

当然，这里要注意，链表只有一个节点的情况
就直接，删除头结点，也就是头删

好了，无头单向非循环链表的讲解就到这里，下一篇博客，讲解有头单向循环链表。