数据结构之线性表（3）

数据结构之线性表（3）

上文我们了解了线性表的静动态存储的相关操作，此篇我们对线性表中链表的相关操作探讨。
在进行链表的相关操作时，我们先来理解单链表是什么？

1.链表的概念及结构

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

//单链表的结点定义
struct SeqListNode
{
	datatype data;
	struct SLNode * next;
};
typedef struct SeqListNode SLNode;

单链表的基本操作：

1.头插

//头插
void SLNpushfront(SLNode** pphead,datatype x)
{
	//1.不存在其他结点
	if (*pphead == NULL)
	{
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		newnode->data = x;
		newnode->next = NULL;
		*pphead = newnode;
	}
	else
	{
		//2.存在其他结点
		SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));
		tmp->data = x;
		tmp->next = *pphead;
		*pphead = tmp;
	}
}

2.尾插

//尾插
void SLNpushback(SLNode** pphead, datatype x)
{
	//1.不存在其他结点
	if (*pphead == NULL)
	{
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		newnode->data = x;
		newnode->next = NULL;
		*pphead = newnode;
	}
	else
	{
		//2.存在其他结点
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		tail->next = newnode;
		newnode->data = x;
		newnode->next = NULL;
	}
}

3.头删

//头删
void SLNpopfront(SLNode** pphead)
{
	//1.链表中0个结点，无法删除
	if (*pphead == NULL)
	{
		printf("链表中没有结点，无法删除\n");
		exit(-1);
	}
	//2.链表中只有一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		(*pphead) = NULL;
	}
	//3.链表中有一个以上结点
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	(*pphead) = NULL;
	*pphead = tmp;
}

4.尾删

//尾删
void SLNpopback(SLNode** pphead)
{
	//1.链表中0个结点
	if (*pphead ==NULL)
	{
		printf("链表中没有结点，无法删除\n");
		exit(-1);
	}
	//2.链表中只有一个结点,就类似于只有一个结点的头删
	if ((*pphead)->next ==NULL)
	{
		free(*pphead);
		(*pphead) = NULL;
	}
	//3.链表中有一个以上结点
	SLNode* prev = NULL;
	SLNode* tail = (*pphead);
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
	prev->next = NULL;
}

5.打印

//打印
void SLNprintf(SLNode* pphead)
{
	while (pphead)
	{
		printf("%d ", pphead->data);
		pphead = pphead->next;
	}
}

6.查找

//查找
SLNode* SLNfind(SLNode* phead, datatype x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

7.指定位置插入

//指定位置插入
void SLNinsert(SLNode** pphead, SLNode* pos, datatype x)
{
	if (pos == *pphead)
	{
		SLNpushfront(pphead, x);//若pos==*pphead，就等同于头插
	}
	else
	{
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		newnode->data = x;
		newnode->next = NULL;
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}

7.指定位置删除

void SLNdeleate(SLNode** pphead, SLNode* pos)
{
	if (pos == *pphead)
	{
		SLNpopfront(pphead);//若pos==*pphead，就等同于头删
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

完整代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
//单链表结点的定义
struct SeqListNode
{
	datatype data;
	struct SLNode* next;
};
typedef struct SeqListNode SLNode;
//头插
void SLNpushfront(SLNode** pphead,datatype x)
{
	//1.不存在其他结点
	if (*pphead == NULL)
	{
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		newnode->data = x;
		newnode->next = NULL;
		*pphead = newnode;
	}
	else
	{
		//2.存在其他结点
		SLNode* tmp = (SLNode*)malloc(sizeof(SLNode));
		tmp->data = x;
		tmp->next = *pphead;
		*pphead = tmp;
	}
}
//尾插
void SLNpushback(SLNode** pphead, datatype x)
{
	//1.不存在其他结点
	if (*pphead == NULL)
	{
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		newnode->data = x;
		newnode->next = NULL;
		*pphead = newnode;
	}
	else
	{
		//2.存在其他结点
		SLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		tail->next = newnode;
		newnode->data = x;
		newnode->next = NULL;
	}
}
//头删
void SLNpopfront(SLNode** pphead)
{
	//1.0个结点，无法删除
	if (*pphead == NULL)
	{
		printf("链表中没有结点，无法删除\n");
		exit(-1);
	}
	//2.链表中只有一个结点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		(*pphead) = NULL;
	}
	//3.链表中有一个以上结点
	SLNode* tmp = (*pphead)->next;
	free(*pphead);
	(*pphead) = NULL;
	*pphead = tmp;
}
//尾删
void SLNpopback(SLNode** pphead)
{
	//1.链表中0个结点
	if (*pphead ==NULL)
	{
		printf("链表中没有结点，无法删除\n");
		exit(-1);
	}
	//2.链表中只有一个结点,就类似于只有一个结点的头删
	if ((*pphead)->next ==NULL)
	{
		free(*pphead);
		(*pphead) = NULL;
	}
	//3.链表中有一个以上结点
	SLNode* prev = NULL;
	SLNode* tail = (*pphead);
	while (tail->next != NULL)
	{
		prev = tail;
		tail = tail->next;
	}
	free(tail);
	tail = NULL;
	prev->next = NULL;
}
//打印
void SLNprintf(SLNode* pphead)
{
	while (pphead)
	{
		printf("%d ", pphead->data);
		pphead = pphead->next;
	}
}
//指定位置插入
void SLNinsert(SLNode** pphead, SLNode* pos, datatype x)
{
	if (pos == *pphead)
	{
		SLNpushfront(pphead, x);
	}
	else
	{
		SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
		newnode->data = x;
		newnode->next = NULL;
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
}
//指定位置删除
void SLNdeleate(SLNode** pphead, SLNode* pos)
{
	if (pos == *pphead)
	{
		SLNpopfront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}
//查找
SLNode* SLNfind(SLNode* phead, datatype x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
int main()
{
	SLNode* plist = NULL;
	SLNpushfront(&plist, 1);
	SLNpushfront(&plist, 2);
	SLNpushfront(&plist, 3);
	SLNpushback(&plist, 4);
	SLNpushback(&plist, 5);
	SLNpushback(&plist, 6);
	SLNpushback(&plist, 7);
	SLNpopfront(&plist);
	SLNpopback(&plist);
	SLNprintf(plist);
	return 0;
}

以上就是单链表中最简单的一种结构的相关操作啦，谢谢大家支持。