Data organization -- singly linked list of the linear table

前言

In a blog post I wrote about the data structure of the linear table the first representation structure----顺序表,While this is introduced in the second linear structure----Singly linked list in the list！

1.链表

In a blog post on the linear table I mentioned on the logic is a kind of linear structure,So the list also have this nature,As shown is a graphical representation of the list.

The above is a linked list node,The node usually has two parts,Part of the user needs to real-time data,The other part is the address of the next node.So the link between these nodes to construct can form the list,In the last node in the linked list,该节点的next是指向NULL的,这一点很重要！

The following such as sequential table,Implementation of the data to add and delete operations such as！

2.相关功能接口

实现链表,The first thing we need to create a structure to create a node;

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

data是实时数据,The other part is the next node address

2.1Node creation and destruction

1️⃣The creation of the node

SListNode* BuyNewNode(SListData x)
{
    
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
    
		printf("%s", strerror(errno));
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

分析:When creating nodes of node application space,将dataPassed to the newly created node in thedata,The new node points to address values forNULL;And create nodes will need to return,Therefore function types, that is, the custom of structure type,Means that the data returned is a pointer to struct！

2️⃣结点的销毁

void DestorySListNode(SListNode** pphead)
{
    
	SListNode* cur = *pphead;
	while (cur != NULL)
	{
    
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

分析：Which nodes are dynamic memory similarly also there is a dynamic memory recovery,当cur不等于NULL时,To release and makecur指向下一个结点,To the whole list can release the memory,The adversary pointer to buyNULL.

2.2头插与头删

2.2.1头插

void PushSListFront(SListNode** pphead, SListData x)
{
    
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

分析：Head of the logic is simple,Is the head pointer is passed to the content of thenewnode的中的next,再将newnodeAddress to assign a value to the head pointer to complete his head！

In the above code about the secondary pointer function argument why be？

When I have been mentioned in the introduction of head pointer,The head pointer is stored in the first node address,When I was in for his head,Need to change the head pointer the value in the,Also is constantly update change pointer address;Transmit the function and consistent with general parameters,If pass simply value,Is not the function of internal change reflected in the function of external,Therefore in this needs to be addressed;When the head function called,I need to pass a parameter is the address of the head pointer,指针的地址,Then I need to use pointer to pointer to receive,Is using the secondary pointer to receive function can be internal changes reflect to the outside of the function to,This also is the reason why secondary pointer function parameters,At the back of the interface function of the principle of parameter passing the secondary pointer is in line with the above,Down not to explain！

2.2.2头删

void PopSListNodeFront(SListNode** pphead)
{
    
	assert(pphead);
	assert(*pphead!=NULL);
	SListNode* temp = *pphead;
	*pphead = (*pphead)->next;
	free(temp);
	temp = NULL;
}

分析：Delete the first need to make sure that is linked list is empty,Therefore assert that;*pphead就是plist的内容,pphead即是plist的地址;Let the head pointer to a pointer points to the piece of spacenext指向的空间;Is pointing to the second node.

2.3尾插和尾删

2.3.1尾插

void PushSListBack(SListNode** pphead, SListData x)
{
    
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	//空时
	if (*pphead == NULL)
	{
    
		newnode->next = *pphead;//无意义的
		*pphead = newnode;
	}
	else
	{
    
		SListNode* temp = *pphead;
		while (temp->next != NULL)
		{
    
			temp = temp->next;
		}
		temp->next = newnode;
	}
}

分析：首先,如果链表为空时,The tail plug is equivalent to the first plug,在此不进行赘述.The list is empty,I need to find the last node at this time,让该节点的nextPoint to the new space of the node is inserted into the success！

2.3.2尾删

void PopSListNodeBack(SListNode** pphead)
{
    
	assert(pphead);
	assert(*pphead != NULL);
	SListNode* tail = *pphead;
	SListNode* prev = NULL;
	while (tail->next != NULL)
	{
    
		prev = tail;
		tail = tail->next;
	}
	prev->next = NULL;
	free(tail);
}

分析：Tail delete relatively trouble,Need to find the last node before a node,For the previous nodenext置为NULL,Then on the last node memory can be released,所以prevBefore the last node of a node,对prev->next置为NULL,然后释放tail即可！

2.4查找

SListNode* FindNode(SListNode* phead, SListData x)
{
    
	assert(phead);
	SListNode* cur = phead;
	while (cur != NULL)
	{
    
		if (cur->data == x)
		{
    
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

The type of the function is the pointer to structure,Namely when find successful return to find node,So is that of the type and function！

2.5插入

2.5.1在pos之前插入

The realization of the insert function is inseparable from the lookup function,因此在实际应用中,Call to insert function should be called insertion function.

void InsertPosBefore(SListNode** pphead, SListData x, SListNode* pos)
{
    
	assert(pphead);
	assert(pos);
	if (*pphead == NULL)
	{
    
		PushSListFront(pphead, x);
	}
	else
	{
    
		SListNode* prev = *pphead;
		//prev时pos的前一个
		while (prev->next != pos)
		{
    
			prev = prev->next;

			//Have been looking for back,When can't find continue to back,当pos不在链表中时,此时prev为NULL
			//为NULLWhen an assertion that
			assert(prev);
		}

		SListNode* newnode = BuyNewNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

当prev的next与pos相等时,As the means to findpos的前一个结点,And then create a new node,使pos的前一个结点prev的next指向新结点,让新结点的next指向posInsert can be realized!

2.5.2在pos之后插入

void InsertPosAfter(SListNode* pos, SListData x)
{
    
	assert(pos);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

分析：在pos之后插入,就直接传递pos即可,将pos->next赋给newnode->next,Would mean a new node is inserted into thepos与posAfter a node between;然后在使pos的next指向newnode即可;这个顺序是不能颠倒的,Otherwise it is point to yourself a case！

2.6删除

2.6.1删除pos的位置

void DelSListNode(SListNode** pphead, SListNode* pos)
{
    
	assert(pos);
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur->next != pos)
	{
    
		cur = cur->next;
		assert(cur);//Find the end also can't find the word error
	}
	cur->next = pos->next;
	free(pos);
}

Delete directly findpos的前一个结点,Through the previous nodenext锁定pos,然后将posThe address of the next one toposBefore an address,如cur->next = pos->next;,最后对pos进行释放即可！

2.6.2删除pos之后的位置

void DelPosAfter(SListNode* pos)
{
    
	assert(pos);
	if (pos->next == NULL)
	{
    
		return;
	}
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

这个函数比较简单,将pos之后的元素的next赋给pos的next即可！

3.完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<errno.h>
#include<stdlib.h>

typedef int SListData;
typedef struct SListNode
{
    
	SListData data;
	struct SListData* next;
}SListNode;
//创造新结点
SListNode* BuyNewNode(SListData x);
//头插
void PushSListFront(SListNode** pphead, SListData x);
//尾插
void PushSListBack(SListNode** pphead, SListData x);
//头删
void PopSListNodeFront(SListNode** pphead);
//尾删
void PopSListNodeBack(SListNode** pphead);
//查找
SListNode* FindNode(SListNode* phead, SListData x);
//在pos之前插入
void InsertPosBefore(SListNode** pphead, SListData x, SListNode* pos);
//在pos之后插入
void InsertPosAfter(SListNode* pos, SListData x);
//打印
void PrintSList(SListNode* phead);
//删除
void DelSListNode(SListNode** pphead, SListNode* pos);
//删除pos之后的结点
void DelPosAfter(SListNode* pos);
//销毁
void DestorySListNode(SListNode** pphead);


//创造新结点
SListNode* BuyNewNode(SListData x)
{
    
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
    
		printf("%s", strerror(errno));
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//头插
void PushSListFront(SListNode** pphead, SListData x)
{
    
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}
//尾插
void PushSListBack(SListNode** pphead, SListData x)
{
    
	assert(pphead);
	SListNode* newnode = BuyNewNode(x);
	//空时
	if (*pphead == NULL)
	{
    
		newnode->next = *pphead;//无意义的
		*pphead = newnode;
	}
	else
	{
    
		SListNode* temp = *pphead;
		while (temp->next != NULL)
		{
    
			temp = temp->next;
		}
		temp->next = newnode;
	}
}

//头删
void PopSListNodeFront(SListNode** pphead)
{
    
	assert(pphead);
	assert(*pphead!=NULL);
	SListNode* temp = *pphead;
	*pphead = (*pphead)->next;
	free(temp);
	temp = NULL;
}

//尾删
void PopSListNodeBack(SListNode** pphead)
{
    
	assert(pphead);
	assert(*pphead != NULL);
	SListNode* tail = *pphead;
	SListNode* prev = NULL;
	while (tail->next != NULL)
	{
    
		prev = tail;
		tail = tail->next;
	}
	prev->next = NULL;
	free(tail);
}

//查找
SListNode* FindNode(SListNode* phead, SListData x)
{
    
	assert(phead);
	SListNode* cur = phead;
	while (cur != NULL)
	{
    
		if (cur->data == x)
		{
    
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//在pos之前插入
void InsertPosBefore(SListNode** pphead, SListData x, SListNode* pos)
{
    
	assert(pphead);
	assert(pos);
	if (*pphead == NULL)
	{
    
		PushSListFront(pphead, x);
	}
	else
	{
    
		SListNode* prev = *pphead;
		//prev时pos的前一个
		while (prev->next != pos)
		{
    
			prev = prev->next;

			//Have been looking for back,When can't find continue to back,当pos不在链表中时,此时prev为NULL
			//为NULLWhen an assertion that
			assert(prev);
		}

		SListNode* newnode = BuyNewNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
//在pos之后插入
void InsertPosAfter(SListNode* pos, SListData x)
{
    
	assert(pos);
	SListNode* newnode = BuyNewNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
//打印
void PrintSList(SListNode* phead)
{
    
	SListNode* cur = phead;
	while (cur!= NULL)
	{
    
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//删除
void DelSListNode(SListNode** pphead, SListNode* pos)
{
    
	assert(pos);
	assert(pphead);
	SListNode* cur = *pphead;
	while (cur->next != pos)
	{
    
		cur = cur->next;
		assert(cur);//Find the end also can't find the word error
	}
	cur->next = pos->next;
	free(pos);
}
//删除pos之后的结点
void DelPosAfter(SListNode* pos)
{
    
	assert(pos);
	if (pos->next == NULL)
	{
    
		return;
	}
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}
//销毁
void DestorySListNode(SListNode** pphead)
{
    
	SListNode* cur = *pphead;
	while (cur != NULL)
	{
    
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
//测试函数
void test1()
{
    
	SListNode* plist = NULL;
	PushSListFront(&plist, 1);
	PushSListFront(&plist, 2);
	PushSListFront(&plist, 3);
	PushSListFront(&plist, 4);
	PrintSList(plist);

	PushSListBack(&plist, 10);
	PushSListBack(&plist, 20);
	PushSListBack(&plist, 30);
	PrintSList(plist);

	/*PopSListNodeFront(&plist); PrintSList(plist); PopSListNodeBack(&plist); PrintSList(plist);*/

	SListNode*pos=FindNode(plist,10);
	if (pos)
	{
    
		InsertPosBefore(&plist, 66, pos);
		InsertPosAfter(pos, 88);
	}
	PrintSList(plist);

	SListNode* pos1 = FindNode(plist, 88);
	DelSListNode(&plist, pos1);
	SListNode* pos2 = FindNode(plist, 10);
	DelSListNode(&plist, pos2);
	PrintSList(plist);

	SListNode* pos3 = FindNode(plist, 1);
	DelPosAfter(pos3);
	PrintSList(plist);

	DestorySListNode(&plist);
}
int main()
{
    
	test1();
}

Ending

Singly linked list in the list is updated completed,The secondary pointer travels and perhaps more troublesome、难以理解,Combined with the ordinary function pass and we can solve this problem very well;其次,There is a way to the parameter is a function of the secondary pointer is designed as the return type structure pointer to a function,但是,This function USES the very inconvenient,So this article is not to write;

好了,就这样吧‍*️