数据结构——不带头结点的单链表的基本操作

数据结构——不带头节点的单链表的基本操作

结构体的创建：

typedef struct SListNode
{
	ElemType data;
	struct SListNode *next;
}SListNode;

typedef SListNode* SList;

单链表的基本操作：

初始化：

void SListInit(SList *phead)//初始化
{
	assert(phead != NULL); //因为phead是外部实参的地址,所以地址是一定存在的,不可能为空
	                       //如果为NULL的话一定是出错误了,所以用assert断言来提示
	
	*phead = NULL;         //在变量声明的时候，如果没有确切的地址可以赋值，
						   //为指针变量赋一个 NULL 值是一个良好的编程习惯。
	                       //赋为 NULL 值的指针被称为空指针
}

void SListPushBack(SList *phead, ElemType x)//尾插法
{
	assert(phead);
	SList s = (SList)malloc(sizeof(SListNode));
	assert(s!= NULL);
	s->data = x;
	s->next = NULL;
	SList p = *phead;
	//连接
	if (p == NULL)
	{
		*phead = s;
	}
	else
	{
		while (p->next != NULL)
		{
			p = p->next;
		}
		p->next = s;
	}
}

void SListPushFront(SList *phead, ElemType x)    //头插法
{
	assert(phead!=NULL);
	SList s = (SList)malloc(sizeof(SListNode));
	s->data = x;
	s->next = NULL;
	//连接
	s->next = *phead;     //当无节点时也不会影响，因为初始化中*phead=NULL；
	*phead = s;
}

void SListPopBack(SList *phead)    //尾部删除 分为三种情况：0个，1个，多个节点
{
	assert(phead != NULL);
	SList p = *phead;
	SList prev = NULL;
	if (*phead == NULL)    //0个节点
	{
		printf("链表为空，无节点可删！");
		return;
	}

	else if ((*phead)->next == NULL)    //1个节点
	{
		free(*phead);
		*phead = NULL;
		printf("删除成功！");
		return;
	}

	else{
		while(p->next != NULL)    //多个节点
		{
			prev = p;
			p = p->next;
		}
		
		free(p);
		prev->next = NULL;
		printf("删除成功！");
	}	
}

头部删除

{
void SListPopFront(SList *phead)//头部删除
{
	assert(phead != NULL);
	SList p = *phead;
	if (*phead == NULL)    //0个节点
	{
		printf("链表为空，无节点可删！");
		return;
	}
	else
	{
		*phead = p->next;
		free(p);
	}

}

显示

void SListShow(SList phead)//显示
{
	//assert(phead != NULL);
	SListNode *p = phead;
	while (p != NULL)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("Over.\n");
}

size_t SListLength(SList phead)//单链表长度
{
	//assert(phead != NULL);
	size_t size = 0;
	SListNode *p = phead;
	while (p != NULL)
	{
		size++;
		p = p->next;
	}
	return size;
}

SListNode* SListFind(SList phead, ElemType key)//按值寻找
{
	SListNode *p = phead;
	while (p != NULL && p->data != key)
		p = p->next;
	return p;
}

void SListEraseByVal(SList *phead, ElemType key)//按值删除;
{
	assert(phead != NULL);
	SList p = SListFind(*phead, key);
	if (p == NULL)
	{
		printf("不存在该值！");
		return;
	}

	SList prev = *phead;
	if (prev == p)   //
	{
		free(p);
		*phead = NULL;
	}
	else
	{
		while (prev->next != p)
			prev = prev->next;
		prev->next = p->next;
		free(p);
	}
}

void SListInsertByVal(SList *phead, ElemType key)//按值插入
{
	assert(phead != NULL);
	SList p = *phead;
	SList prev = NULL;
	if (*phead == NULL)
	{
		SListPushFront(phead, key);
	}
	else
	{
		while (key > p->data)
		{
			prev = p;
			p = p->next;
		}
		SList s = (SList)malloc(sizeof(SListNode));
		s->data = key;
		s->next = prev->next;
		prev->next = s;
		printf("添加成功！");
	}
}

void Sort(SList *phead) //按值排序2
{
	assert(phead != NULL);
	if (SListLength(*phead) <= 1)
	{
		printf("该链表长度为%d,无需排序!", SListLength(*phead));
		return;
	}
	else
	{
		SList p = *phead;
		SList q = p->next;
		p->next = NULL;
		while (q != NULL)
		{
			SList tmp = *phead;           //在while循环中定义保证每次tmp指向头结点
			p = q;
			q = q->next;
			if ((p->data > (*phead)->data)) //与头进行比较决定插入位置前后
			{
				while (tmp->next != NULL && (p->data) > (tmp->next)->data)  //后插，找出插入位置的前驱，保证有序
				{ //注意：先判断tmp是否为空，否则比较时候会出错
					tmp = tmp->next;
				}
				p->next = tmp->next;
				tmp->next = p;
			}
			else                          //前插
			{
				p->next = *phead;
				*phead = p;
			}
			tmp = *phead;
		}
	}
}

void SListSort(SList *phead)//按值排序
{
	assert(phead != NULL);
	if (SListLength(*phead) <= 1)
	{
		printf("该链表长度为%d,无需排序!", SListLength(*phead));
		return;
	}
	else
	{
		SList tmp = *phead;
		SList prev = NULL;
		SList p = *phead;
		SList q = p->next;
		p->next = NULL;
		while (q != NULL)
		{
			p = q;
			q = q->next;
			while (tmp != NULL&&p->data > tmp->data)
			{
				prev = tmp;
				tmp = tmp->next;
			}	
			if (prev == NULL)//while循环中p->data > tmp->data未执行，即需要在tmp前插入
			{
				p->next = *phead;
				*phead = p;
			}
			else
			{
				p->next = prev->next;
				prev->next = p;
			}
			tmp = *phead;
			prev = NULL;
		}
	}

	

	
}

ElemType SListFront(SList phead)//头元素
{
	assert(phead != NULL);
	return phead->data;
}

ElemType SListBack(SList phead)//尾元素
{
	assert(phead != NULL);
	SListNode *p = phead;
	while (p->next != NULL)
		p = p->next;
	return p->data;
}

void SListEraseAll(SList *phead, ElemType key) //按值删除所有值
{
	assert(phead != NULL); 
	int num = 0;
	SList p = SListFind(*phead, key);//定位到key第一次出现的位置
	if (p == NULL)
	{
		printf("该链表不存在该值！删除失败！");
		return;
	}
	for (; p != NULL; p = p->next)
	{
		if (p->data == key)
			num++;
	}
	for (int i = 0; i < num; i++)
	{
		SList p = SListFind(*phead, key);
		SList prev = *phead;
		if (prev == p)   
		{
			*phead = p->next;
			free(p);
		}
		else
		{
			while (prev->next != p)
				prev = prev->next;
			prev->next = p->next;
			free(p);
		}
	}
	printf("删除成功！");
}

void SListClear(SList *phead) //清空链表
{
	assert(phead != NULL);
	SListNode *p = NULL;
	while (*phead != NULL)
	{
		p = *phead;
		*phead = p->next;
		free(p);
	}
}

void SListDestroy(SList *phead) //摧毁链表
{
	SListClear(phead);
}

void SListReverse(SList *phead) //链表转置
{
	assert(phead != NULL);
	SListNode *p = *phead;
	SListNode *q = p->next;

	p->next = NULL;
	while (q != NULL)
	{
		p = q;
		q = q->next;
		p->next = *phead;
		*phead = p;
	}
}