[数据结构]----链表(无头单向非循环链表的实现)_无头节点单向链表

目录

1. 顺序表的缺陷

2. 链表

2.1 链表的概念

2.2.链表的结构

2.3 链表的分类

3. 无头单向非循环链表

3.1 链表的结构体定义

3.2 动态创建一个链表新结点

3.3 打印链表

3.4 尾插和尾删

3.5 头插和头删

3.6 找到x值的地址

3.7 在pos前面/后面插入一个数

3.8 删除某个位置/删除某个位置的后一个位置

3.9 销毁链表

---

1. 顺序表的缺陷

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。

2. 链表

2.1 链表的概念

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

2.2. 链表的结构

 

 链表结构是有一个Data存储值/数据，有一个结构体指针存放下一个结点的地址

2.3 链表的分类

1.单向链表或双向链表

 2.带头（哨兵位）链表或不带头（哨兵位）链表

 3.循环链表或不循环链表

 每种类型都有两种不同的结构，所以一共能出8种（2*2*2）不同的结构

虽然链表的种类众多，但是我们主要用两种链表

无头单向非循环链表和带头双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势

3. 无头单向非循环链表

 

 注：为什么有的函数传递二级指针

        因为当链表的头结点需要被改变时，需要传递头结点的地址，以此才能改变头结点 

 

3.1 链表的结构体定义

typedef int DataType;
 
typedef struct Slist
{
	DataType data;
	struct Slist* next;
}SL;

3.2 动态创建一个链表新结点

函数声明：

SL* BuyListNode(DataType x);

 在VS中malloc一个内存块时，注意检查一下malloc是否成功，最后返回malloc出来的结点地址

函数定义：  

SL* BuyListNode(DataType x)
{
	SL* newnode = (SL*)malloc(sizeof(SL));
	if (newnode == NULL)
	{
		printf("malloc errno\n");
		exit(-1);
	}
 
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode; 
}

3.3 打印链表

函数声明：

void SlPrint(SL* phead);

注：当while循环中是cur != NULL时，最后cur会指向链表最后一个元素存储的NULL

       当while循环中是cur->next !=NULL时，最后cur会指向链表的最后一个元素

函数定义：  

void SlPrint(SL* ps)
{
	SL* cur = ps;
	//while (cur)
	while (cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
 
	printf("NULL\n");
}

3.4 尾插和尾删

 尾插：

函数声明： 

void SlPushBack(SL** pphead, DataType x);

无头单向非循环链表尾插需要通过遍历才能找到链表的尾，有些麻烦

尾插时，分两种情况：

1.链表中还没有存储数据，此时链表的头结点是NULL
   此时直接将malloc出来的结点给头结点

2.链表中已经有数据，此时链表的头结点不是NULL
    此时需要先找到尾结点，然后再把malloc出来的结点给tail->next 

函数定义：  

void SlPushBack(SL** pphead, DataType x)
{
	assert(pphead);
	SL* newnode = BuyListNode(x);
 
	if (*pphead == NULL)//1
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SL* tail = *pphead;//2
 
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
 
		tail->next = newnode;
	}
}

尾删：

函数声明： 

void SlPopBack(SL** pphead);

首先需要检查传进函数的指针不为空

尾删时，分两种情况：
1.链表中只有一个结点：

  此时直接free掉这个结点，然后再让它为空

2.链表中不只有一个结点：

  此时需要找到尾结点，同时也需要记录尾结点的前一个结点，最后让前一个节点的指向NULL

（原因：若只找到尾结点并释放掉的话，尾结点的前一个结点还指向原来的尾结点地址，如果打印时此时会造成指针的非法访问）

  

函数定义： 

void SlPopBack(SL** pphead)
{
	assert(*pphead);
 
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SL* end = *pphead;
		SL* prve = NULL;
		while (end->next)
		{
			prve = end;
			end = end->next;
		}
 
		free(end);
		end = NULL;
 
		prve->next = NULL;
	}
 
}

3.5 头插和头删

头插：

函数声明： 

void SlPushFront(SL** pphead, DataType x);

 只需要检查一下指针不为NULL，然后将malloc出来的结点直接插入

函数定义：  

void SlPushFront(SL** pphead, DataType x)
{
	assert(pphead);
 
	SL* newnode = BuyListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头删：

函数声明：

void SlPopFront(SL** pphead);

需要检查一下指针不为NULL，记录第二个结点地址，释放第一个结点，将第二个结点地址给头结点

函数定义：  

void SlPopFront(SL** pphead)
{
	assert(*pphead != NULL);
	assert(pphead);
 
	SL* next = (*pphead)->next;
	free(*pphead);
	
	*pphead = next;
 
}

3.6 找到x值的地址

函数声明： 

SL* SlFind(SL* phead, DataType x);

遍历链表，找到返回结点地址，找不到返回NULL 

函数定义：  

SL* SlFind(SL* phead, DataType x)
{
	assert(phead);
 
	while (phead)
	{
		if (phead->data == x)
		{
			return phead;
		}
		else
		{
			phead = phead->next;
		}
	}
	return NULL;
}

3.7 在pos前面/后面插入一个数

在pos前面插入一个数：

函数声明：

void SlInsertBefore(SL** pphead, SL* pos, DataType x);

 1.pos是头结点，此时就是头结点的前插

 2.在其他位置前插一个数，需要记录pos位置的前一个结点的位置

函数定义：  

void SlInsertBefore(SL** pphead, SL* pos, DataType x)
{
	assert(*pphead);
	assert(pos);
 
	if (*pphead == pos)
	{
		SlPushFront(pphead,x);
	}
	else
	{
		SL* prev = *pphead;
		while (prev->next != pos)
		{
			prev = (*pphead)->next;
		}
 
		SL* newnode = BuyListNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

在pos后面插入一个数：

函数声明：

void SlInsertAfter(SL* pos, DataType x);

 只直接改变两个结点的next指针即可

函数定义：  

void SlInsertAfter(SL* pos, DataType x)
{
	SL* newnode = BuyListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

3.8 删除某个位置/删除某个位置的后一个位置

删除某个位置 ：

函数声明：

void SlErase(SL** pphead, SL* pos);

1. pos是头结点时，调用头删函数

2. pos是其他结点，通过遍历找到pos的前一个结点，将pos前一个结点的next指向pos的下一个结点，最后free掉pos

函数定义：  

void SlErase(SL** pphead, SL* pos)
{
	assert(*pphead);
	assert(pos);
	if(*pphead == pos)
	{
		SlPopFront(pphead);
	}
	else
	{
		SL* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
		pos = NULL;
	}

删除某个位置的后一个位置：

函数声明：

void SListEraseAfter(SL* pos);

记录pos下两个结点的地址

将pos下两个结点的地址给pos->next 

函数定义：  

void SListEraseAfter(SL* pos)
{
	assert(pos);
	assert(pos->next);
 
	SL* next = pos->next;
	pos->next = next->next;
 
	free(next);
	next = NULL;
}

3.9 销毁链表

函数声明：

void SlDestory(SL** pphead);

通过遍历链表释放每个结点

函数定义： 

void SlDestory(SL** pphead)
{
	assert(pphead);
 
	SL* cur = *pphead;
	while (cur)
	{
		SL* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}