数据结构 · 线性表 | 单链表

啊我摔倒了..有没有人扶我起来学习....

---

👱个人主页：$《CGod的个人主页》$交个朋友叭~
💒个人社区：$《编程成神技术交流社区》$加入我们，一起高效学习，收割好Offer叭~
🌱刷题链接：$《LeetCode》$快速成长的渠道哦~

---

---

前言

• 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
• 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
  线性表在物理上存储时，通常以数组和链式结构的形式存储
  

---

一、链表

1.1 链表的概念及结构

• 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
  
  

1.2 链表的分类

• 实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
  1. 单向或者双向
     
  2. 带头或者不带头
     
  3. 循环或者非循环
     
     虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
     

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了

1.3 单链表的实现

1. 接口：

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType val;
	struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* phead);
// 单链表尾插
void SListPushBack(SListNode** pphead, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pphead, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pphead);
// 单链表头删
void SListPopFront(SListNode** pphead);
// 单链表查找
SListNode* SListFind(SListNode* phead, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode* pos, SLTDateType x);
// 单链表删除pos位置的值
void SListErase(SListNode* 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

2. 接口的实现：

//申请结点
SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    newnode->val = x;
    newnode->next = NULL;

    return newnode;
}
//打印
void SListPrint(SListNode* phead)
{
    SListNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("NULL\n");
}
//尾插
void SListPushBack(SListNode** pphead, SLTDateType x)
{
    assert(pphead);

    SListNode* newnode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SListNode* tail = *pphead;
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}
//头插
void SListPushFront(SListNode** pphead, SLTDateType x)
{
    assert(pphead);

    SListNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}
//尾删
void SListPopBack(SListNode** pphead)
{
    assert(pphead);
    assert(*pphead);

    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SListNode* tail = *pphead;
        while (tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}
//头删
void SListPopFront(SListNode** pphead)
{
    assert(pphead);
    assert(*pphead);

    SListNode* cur = *pphead;
    *pphead = (*pphead)->next;
    free(cur);
    cur = NULL;
}
//查找
SListNode* SListFind(SListNode* phead, SLTDateType x)
{
    SListNode* cur = phead;
    while (cur->val != x)
    {
        cur = cur->next;
    }
    if (cur->val == x)
        return cur;
    return NULL;
}
//任意位置插入
void SListInsert(SListNode* pos, SLTDateType x)
{
    assert(pos);

    if ((*pphead)->next == NULL)
    {
        SListPushFront(pphead, x);
    }
    else
    {
        SListNode* cur = *pphead;
        SListNode* newnode = BuySListNode(x);
        while (cur->next != pos)
        {
            cur = cur->next;
        }
        cur->next = newnode;
        newnode->next = pos;
    }
}
//任意位置删除
void SListErase(SListNode* pos)
{
    assert(pos);

    if (pos == *pphead)
    {
        SListPopFront(pphead);
    }
    else
    {
        SListNode* cur = *pphead;
        while (cur->next != pos)
        {
            cur = cur->next;
            //走到空了还没找到pos,说明传错了pos
            assert(cur);
        }
        cur->next = pos->next;
        free(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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

---