[数据结构]——单链表超详细总结_正向构造单链表需要满足市民条件

目录：

链表是个优秀的结构，没有容量概念，可以在任意位置增加删除数据，这个博客，我准备花大量篇幅去总结链表（特别是单链表），同时也总结一下顺序表（顺序表和我们以前写的通讯录动态版类似，一般采用数组存储的方法，在数组上完成数据的增删查改）

一、线性表的概念

线性表的定义：由n个数据元素组成具有相同特性的有限序列。
常见的线性表：顺序表、链表、栈、队列、字符串等等。
线性表的概念：线性表在逻辑上是线性结构，也就是说它是一条直线，它的物理结构并不一定是连续的，线性表在物理上存储时，通常以数组和链表的形式存储。

二、顺序表

顺序表的定义：
顺序表是一段物理地址连续的存储单元，是一种用来依次存储数据的线性结构。

1.静态顺序表：使用定常数组存储元素

#define N 7//方便改变数组大小
typedef int SLDatatype;
typedef struct SLD
{
SLDatatype arr[N];//定长数组
size_t size;//有效数据的个数
}SeqList;//顺序表
1
2
3
4
5
6
7

2.动态顺序表：使用动态开辟的数组存储元素（空间不够就可以扩容）

typedef int SLDatatype;
typedef struct SLD
{
SLDatatype* p;//指向动态开辟的数组
size_t size;//有效数据的个数
size_t capicity;//表示容量空间的大小
}SeqList;//顺序表
1
2
3
4
5
6
7

三、链表

3.1 链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意:
链式结构在逻辑上是连续的，但是在物理上不一定连续。
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

3.2 链表的分类

链表的结构非常多，结合起来有8种：
1、单向或者双向

2、带头或者不带头

3、循环或者不循环

实际中常用的两种结构是：

1. 无头单向非循环链表 ：
   结构简单，一般不会单独存数据。其他数据的子结构，如哈希桶、图的领接表等等。
2. 带头双向循环链表：
   结构最复杂，一般可以单独存数据。实际中使用的链表数据结构，都是带头双向循环链表。

3.3 无头+单向+非循环链表的实现

头文件里的函数声明

// slist.h
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos);
// 单链表的销毁
void SListDestroy(SListNode** pplist);
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

下面将是各个函数的实现

// slist.c
#include "SList.h"
//动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
//在堆上开辟一个存放指针的变量，并给它初始化
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	node->data = x;
	node->next = NULL;
	return node;//返回指针
}
//单链表打印
void SListPrint(SListNode* plist)
{
//定义一个指针，指针指向头指针
	SListNode* cur = plist;
	//遍历指针，不是空就循环
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	//cur指向空
	printf("NULL\n");
}
//单链表尾插一个数据
void SListPushBack(SListNode** pplist, SLTDateType x)
{
//开辟一个新结点
	SListNode* newnode = BuySListNode(x);
	//如果头指针指向的是空就让它指向这个新结点
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else//如果头指针指向的不是空
	{
	//创建一个尾指针
		SListNode* tail = *pplist;
		//尾指针不在尾部，遍历单链表，让尾指针指向链表的最后结点
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
//把开辟的新结点尾插到尾指针结点的下一个结点
		tail->next = newnode;
	}
}
//单链表尾删
void SListPopBack(SListNode** pplist)
{
//定义两个指针
	SListNode* prev = NULL;//当前位置的指针
	SListNode* tail = *pplist;//尾结点的指针
	// 1.空、只有一个节点
	// 2.两个及以上的节点
	if (tail == NULL || tail->next == NULL)
	{
//给空间释放
		free(tail);
		*pplist = NULL;
	}
	else
	{
	//遍历链表，找到尾指针
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}

		free(tail);
		tail = NULL;
//让最后一个结点指向空
		prev->next = NULL;
	}
}

//单链表头插法
void SListPushFront(SListNode** pplist, SLTDateType x)
{
//这个指针是空就报错
	assert(pplist);
	// 1.空
	// 2.非空
	SListNode* newnode = BuySListNode(x);
	if (*pplist == NULL)//pplist指针指向的是空
	{
		*pplist = newnode;
	}
	else
	{
	//在*pplist指针指向的那个结点前面头插一个结点
		newnode->next = *pplist;
		//*pplist指针重新指向头结点
		*pplist = newnode;
	}
}
//单链表头删
void SListPopFront(SListNode** pplist)
{
	// 1.空
	// 2.一个
	// 3.两个及以上
	SListNode* first = *pplist;//定义一个头指针，它为空就返回，
	if (first == NULL)
	{
		return;
	}
	else if (first->next == NULL)//只有一个结点，就释放空间，然后置空
	{
		free(first);
		*pplist = NULL;
	}
	else
	{
	//两个以上结点
		SListNode* next = first->next;//把头指针的下一个结点位置存起来
		free(first);//释放头指针
		*pplist = next;//让首指针重新指向头指针
	}
}
 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
			return cur;

		cur = cur->next;
	}

	return NULL;
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)//用单链表查找，找到值x的位置，返回的指针给pos
{
	assert(pos);
	SListNode* next = pos->next;//next指针存放pos之后的节点
	SListNode* newnode = BuySListNode(x);//开辟一个新结点
	pos->next = newnode;//在pos后面插入新开辟的结点
	newnode->next = next;//让新结点连接上next指向的那个结点
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)//用单链表查找，找到值x的位置，返回的指针给pos
{
	assert(pos);
	// pos next nextnext
	SListNode* next = pos->next;

	if (next != NULL)
	{
		SListNode* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}
// 单链表的销毁
void SListDestroy(SListNode** pplist)
{
    
    SListNode* cur = *pplist;
    while (cur)
    {
        *pplist = cur->next;
        free(cur);
        cur = *pplist;
    }
}
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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171

3.4 带头+双向+循环链表的实现

头文件里的函数声明

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
//创建新结点
 ListNode* ListNodes(LTDataType x);
//双向链表初始化
 ListNode* ListInit();
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* phead);
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* phead);
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* phead);
//求链表有多少数据
int listsize(ListNode* phead);
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* 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

函数的定义实现

// 创建新节点
ListNode* ListNodes(LTDataType x)
{
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    head->data = x;
    head->next = NULL;
    head->prev = NULL;
    return head;
}
//链表初始化
ListNode* ListInit()
{
    ListNode* phead = ListNodes(-1);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
// 双向链表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
    assert(phead);
    ListNode* newnode = ListNodes(x);//创建一个新节点
    ListNode* tail = phead->prev;
    newnode->data = x;
    //双向链表尾插
    tail->next = newnode;
    newnode->next = phead;
    newnode->prev = tail;
    phead->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* phead)
{
    assert(phead);
    assert(phead->next != NULL);
    ListNode* tail = phead->prev;
    ListNode* tailPrev = tail->prev;
    free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}
// 双向链表头插
void ListPushFront(ListNode* phead, LTDataType x)
{
    ListNode* next = phead->next;
    ListNode* newnode = ListNodes(x);
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = next;
    next->prev = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* phead)
{
    assert(phead);
    assert(phead->next != NULL);
    ListNode* node = phead->next;
    phead->next = node->next;
    node->next->prev = phead;
    free(node);
}
//求链表有多少数据
int listsize(ListNode* phead)
{
    int  size = 0;
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        size++;
        cur = cur->next;
    }
    return size;
}
// 双向链表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
    ListNode* newnode = ListNodes(x);
    ListNode* prevnode = pos->prev;
    prevnode->next = newnode;
    newnode->prev = prevnode;
    newnode->next = pos;
    pos->prev = newnode;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* nodeprev = pos->prev;
    ListNode* nodenext = pos->next;
    free(pos);
    nodeprev->next = nodenext;
    nodenext->prev = nodeprev;
}
// 双向链表打印
void ListPrint(ListNode* phead)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d<=>", cur->data);
        cur = cur->next;
    }
}
// 双向链表销毁
void ListDestory(ListNode* phead)
{
    //断言指针指针不为NULL
    assert(phead);
    ListNode* cur = phead;//定义一个指针
    //断开循环链表
    phead->prev->next = NULL;

    while (cur)
    {
        ListNode* Next = cur->next;
        free(cur);
        cur = Next;
    }
}
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

四、顺序表和链表的区别和联系

补充： 高速缓存利用率
先要对存储器的层次结构有一定了解
如图：

数据是存在内存中的，CPU要访问数据，它不会去内存直接访问数据。看数据在不在缓存，在缓存，数据就命中（cpu访问数据时，数据恰好在缓存里），不在缓存，访问不命中（cpu访问数据，不会把4个字节加载到缓存，它会把一长段的数据加载到缓存）

注意：CPU访问数据第一次不命中，第二次一定命中