认识单链表

-之前我们学过储存数据的一种表——顺序表，那么为什么还有链表呢
首先我们回顾一下顺序表
顺序表是物理地址连续的一段内存空间（数组），我们通过动态内存开辟的，
那么：
顺序表也有自己的一些优点，比如我们之前做过的一些题，可以通过下标来快速完成，因为他的地址是连续的所以只要利用下标的加减就可以实现

既然顺序表有缺点，那么我们就有了链表。（按需求申请空间）

通过插入数据，来理解链表

打印函数

在链表的尾部插入数据

代码：

SLTPushBack(SLTNode* plist, SLTDataType x)
{
	//首先要开辟一个结构体来把要插入的数据的内容写进去，在之前的BuySListNode函数就是干这个事情的
	SLTNode* newnode = BuySListNode(x);
	SLTNode* tail = plist;

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

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

上述的尾插是建立在之前已经头插了几个节点的情况下的

那么当链表还是空的时候，这样的尾插还适用吗

知道了这个问题我们来修改代码：

那么想要修改plist就要传址，

尾插总结图

头插：头插不管什么情况都要挪动plist的，所以也是传址操作，上面已经写到过头插的指针变换了，这里我们直接写代码就行

void TestSList3()
	{
		SLTNode* plist = NULL;
		SLTPushFront(&plist,5);
		SLTPushFront(&plist, 4);
		SLTPushFront(&plist, 3);
		SLTPushFront(&plist, 2);
		SLTPrin(plist);


	}


void SLTPushFront(SLTNode** head, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *head;
	*head = newnode;

}


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

尾删

代码：

//尾删
		SLTPopBack(&plist);
		SLTPrin(plist);

		SLTPopBack(&plist);
		SLTPrin(plist);

		SLTPopBack(&plist);
		SLTPrin(plist);


		SLTPopBack(&plist);
		SLTPrin(plist);

		SLTPopBack(&plist);
		SLTPrin(plist);

	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

头删

代码：

		SLTPopFront(&plist);
		SLTPrin(plist);

		SLTPopFront(&plist);

		SLTPrin(plist);

		SLTPopFront(&plist);

		SLTPrin(plist);

		SLTPopFront(&plist);

		SLTPrin(plist);



void SLTPopFront(SLTNode** head)
{
	assert(*head);

	SLTNode* newnode = (*head)->next;
	free(*head);
	*head = newnode;
}

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

查找链表中的数的指针，并改变这个指针所指节点的数据

代码：

		//查找链表中的一个值的指针，并且改变他
		SLTNode* newnode = SLTFind(plist, 3);
		newnode->data = 20;

		SLTPrin(plist);
SLTNode* SLTFind(SLTNode* head, SLTDataType x)
{
	SLTNode* cur = head;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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

在Pos位置插入节点

代码：

		//在指定数据的指针pos位置前插入一个节点
		SLTNode* pos = SLTFind(plist, 3);//先查找到3所对应的指针pos
		SLTnsert(&plist, pos, 30);
		SLTPrin(plist);
void SLTnsert(SLTNode** head, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *head)
	{
		SLTPushFront(head, x);//头插
	}
	else
	{
		SLTNode* prev = *head;
		while (prev->next != pos)
		{
			prev = prev->next;//找到pos位置之前的那个节点的指针
		}
		SLTNode* newnode= BuySListNode(x);//为要插入的数据创建一个节点
		prev->next = newnode;
		newnode->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

在pos位置之后插入节点

代码:

SLTNode* pos = SLTFind(plist, 3);//先查找到3所对应的指针pos
	/*	SLTnsert(&plist, pos, 30);
		SLTPrin(plist);*/

		SLTnsertAfter(plist, pos, 30);
		SLTPrin(plist);
void SLTnsertAfter(SLTNode* head, SLTNode* pos, SLTDataType x)
{
	assert(head);

	SLTNode* newnode = BuySListNode(x);//为要插入的数据创建一个节点

	newnode->next = pos->next;
	pos->next = newnode;
}

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

删除Pos位置的节点

		SLTErase(&plist, pos);
		pos = NULL;
		SLTPrin(plist);

void SLTErase(SLTNode** head, SLTNode* pos)
{
	assert(pos);
	if (pos == *head)
	{
		SLTPopFront(head);//头删
	}
	else
	{
		SLTNode* per = *head;
		while (per->next!=pos)
		{
			per = per->next;
		}
		per->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

删除pos位置之后的节点

代码：

SLTNode* pos = SLTFind(plist, 3);//先查找到3所对应的指针pos


		SLTEraseAfter(pos);
		SLTPrin(plist);
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos->next);
	assert(pos);
	SLTNode* per = pos->next;
	pos->next = per->next;
	free(per);
	

	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

释放链表