单链表的实现

1、开辟内存

/************开辟内存**************/
SLTNode* BuyListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if(newnode == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2、初始化链表

/************初始化链表**************/
void SListInit(SLTNode** pphead)
{
	*pphead = NULL;//传头指针的地址，通过解引用改变头指针。 
}

3、打印链表

/************打印链表**************/
void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;//不能直接用phead（头指针）访问数据，改变phead的值会导致数据丢失。 
	while(cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	} 
	
	printf("NULL\n");
}

4、尾插

/**************尾插 ***************/
void SListPushBack(SLTNode** pphead,SLTDataType x)
{
	assert(pphead); 
	//申请新节点 
	SLTNode* newnode = BuyListNode(x);
	
	//头指针为空不找尾 
	if(*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{	
		SLTNode* tail = *pphead;
		//找到尾，尾节点标志，next为空 
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		//串联节点 
		tail->next = newnode;
	}
}

5、尾删 

/***************尾删****************/
void SListPopBack(SLTNode** pphead)
{
	//空链表 
	if(*pphead == NULL)
	{
		return;
	} //assert(*pphead != NULL);
	
	
	//1个节点 
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
		
	}
	//2个及以上节点 
	else
	{
		SLTNode* tail = *pphead;
	
		/* 
		两个方法均适用于大于一个的链表 
		方法一：借助一个变量
		SLTNode* prev = NULL;
		
		//while(tail->next),0(NULL)假，1真 
		while(tail->next != NULL)
		{
			prev = tail;//保存前一个指针 
			tail = tail->next;
		} 
		free(tail);
		prev->next = NULL; 
		*/
		
		//方法二：判断tail->next->next为空 
		while(tail->next->next != NULL)
		{ 
			tail = tail->next;
		} 
		free(tail->next);
		tail->next = NULL;	
	}
} 

6、头插

/**************头插 ***************/
void SListPushFront(SLTNode** pphead,SLTDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	
	/*
	if(*pphead == NULL)
	{
		newnode->next = NULL;
		*pphead = newnode;	
	}
	else
	{
		newnode->next = *pphead;
		*pphead =newnode;	
	}
	*/
	
	newnode->next = *pphead;//对于空链表同样适用，因为空链表的头指针就是NULL。 
	*pphead =newnode;		
}

7、头删

/**************头删****************/
void SListPopFront(SLTNode** pphead)
{
	//空链表 
	if(*pphead == NULL)
	{
		return;
	}
	//assert(*pphead != NULL); 
	
	//1个及以上节点 
	else
	{
		SLTNode* next = (*pphead)->next;//先储存下一个节点的地址，否则free之后会丢失 
		free(*pphead);
		*pphead = next;
	}
}

8、查找

/**************查找数据***************/
SLTNode* SListFind(SLTNode* phead,SLTDataType x)
{
	SLTNode* cur = phead;
	while(cur)
	{
		if(cur->data == x)
		{
			return cur;//找到 
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;//未找到 
} 

9、特定位置插入

/**************在pos位置之前(单链表不太适合)插入数据***************/
void SListInsertBefore(SLTNode** pphead,SLTNode* pos,SLTDataType x)
{
	SLTNode* newnode = BuyListNode(x);
	if(*pphead != pos)
	{
		SLTNode* pre = *pphead;//保存pos的前一个位置 
		
		/*
		找pos的前一个位置 
		SLTNode* cur = *pphead;
		while(cur->data != (*pos)->data)
		{
			pre = cur;
			cur =cur->next;
		}
		*/
		while(pre->next != pos)
		{
			pre = pre->next;
		}
	
		pre->next = newnode;
		newnode->next = pos;
	}
	else//头插 
	{
		newnode->next = pos; 
		*pphead = newnode;
			
	}	
}



/**************在pos位置之后插入数据 ***************/
void SListInsertAfter(SLTNode* pos,SLTDataType x) 
{
	assert(pos); 
	SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;//注意先后顺序 
	pos->next = newnode;
}

10、特定位置删除

/**************在pos位置删除数据***************/
void SListErase(SLTNode** pphead,SLTNode* pos)
{
	assert(pphead);//地址不可能为空,错误的一种表示，方便调试 
	assert(pos); 
	if(*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		SLTNode* pre = *pphead;//保存pos的前一个位置
		while(pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
	}
	
}



/**************删除pos位置之后数据***************/
void SListEraseAfter(SLTNode* pos)
{
	assert(pos->next != NULL);//断言 
	
	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next); 
}

11、销毁链表

/**************毁灭链表***************/
void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	
	
	while(cur != NULL)
	{
		SLTNode* next = cur->next;//保存后一个地址 
		free(cur);
		cur = next;
	}
	
	*pphead = NULL;
 
}