單鏈表的增刪查 逆置 倒數(shù)第k個節(jié)點等問題

    對于單鏈表而言，它沒有雙鏈表那么復雜，它只有頭節(jié)點，尾節(jié)點，節(jié)點數(shù)據(jù)，后繼指針。在下面本人實現(xiàn)了 單鏈表的 增   刪   插  查  改。
    
#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include<stdlib.h>
typedef int Datatype;
typedef struct SListNode
{
	Datatype data;
	struct SListNode*next;
}SListNode;
void PushBack(SListNode*&pHead, Datatype x);
void PopBack(SListNode *&pHead);
void PrintSlist(SListNode *&PHead);
void PushFrot(SListNode*&pHead,Datatype x);
void PopFront(SListNode*&pHead);
SListNode *Find(SListNode*pHead, Datatype x);
//void Insert(SListNode*pHead, Datatype pos, Datatype x);
void Insert(SListNode*pHead,  Datatype x);
void Erase(SListNode*&pHead,SListNode *pos );
void InsertNoNode(SListNode *pos, Datatype x);


SListNode* _BuyNode(Datatype x)
{
	SListNode *temp = (SListNode*)malloc(sizeof(SListNode));
	temp->data = x;
	temp->next = NULL;
	return temp;
}
void PushBack(SListNode*&pHead, Datatype x)
{
	//1 空   2  不為空
	if (pHead == NULL)
	{
		pHead = _BuyNode(x);
	}
	else
	{
		SListNode *tail = pHead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = _BuyNode(x);
	}
}
void PopBack(SListNode *&pHead)
{
	//1空  2 一個節(jié)點  3 多個節(jié)點  
	if(pHead == NULL)
	{
		return;
	}
	else if (pHead->next == NULL)
	{
		free(pHead);
		pHead = NULL;
	}
	else{
		SListNode *tail = pHead;
		SListNode *tem = NULL;
		while (tail->next != NULL)
		{
			tem = tail;
			tail = tail->next;
		}
		free(tail);
		tem->next = NULL; 
	}
}
void PrintSlist(SListNode *&PHead)  //打印鏈表
{
	SListNode*cur = PHead;
	while (cur!=NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
void PushFrot(SListNode*&pHead, Datatype x)   //頭插
{
	if (pHead == NULL)
	{
		pHead = _BuyNode(x);
	}
	else
	{
		SListNode *tmp = _BuyNode(x);
		tmp->next = pHead;
		pHead = tmp;
	}
}
void PopFront(SListNode*&pHead)    //單鏈表頭刪
{
	//1 空
	//2 一個結(jié)點
	//3 一個以上的節(jié)點
	if (pHead == NULL)
	{
		return;
	}
	else if(pHead->next == NULL)
	{
		free(pHead);
		pHead = NULL;
	}
	else
	{
		SListNode *tmp = pHead;
		pHead = pHead->next;
		free(tmp);
	}
	
}

SListNode *Find(SListNode*pHead, Datatype x)    //查找節(jié)點
{
	//assert(pHead);
	SListNode *tail = NULL;//當前指針
	Datatype tmp ;   //保存節(jié)點數(shù)據(jù)
    if (pHead->data == x)
	{
		return pHead;
	}
	else
	{
		tail=pHead->next;
		while (tail!= NULL)
		{
			tmp = tail->data;
			if (tmp == x)  //把節(jié)點數(shù)據(jù)與要查找的數(shù)比較
			{
				return tail; //返回所要查找結(jié)點的地址
			}
			else
			{
				tail =tail->next;
			}
		}	
		printf("沒有查到該數(shù)據(jù)！\n");
	}
}

void Insert(SListNode*pos, Datatype x)  ////在指定節(jié)點  插入數(shù)據(jù)
{
	assert(pos);
	SListNode *tmp = _BuyNode(x);
	tmp->next = pos->next;
	pos->next = tmp;
}

	

void Erase(SListNode *&pHead,SListNode *pos) //刪除指定位置的節(jié)點
{
	assert(pos);
	assert(pHead);
	if (pHead == pos)
	{
		pHead = pHead->next;
		free(pos);
		return;
	}
	SListNode *prv = pHead;
	while (prv)
	{
		if (prv->next == pos)
		{
			prv->next = pos->next;
			free(pos);
			break;
		}
		prv = prv->next;
	}
	
	
}

//刪除一個無頭單鏈表
void DelNoNode(SListNode *pos)
{
	assert(pos);
	assert(pos->next);
	SListNode *del = pos->next;
	SListNode *next = del->next;
	pos->data = del->data;
	pos->next = next;
	free(del);
}
//在無頭單鏈表的一個非頭節(jié)點前插入一個節(jié)點
void InsertNoNode(SListNode *pos, Datatype x)
{
	assert(pos);
	//assert(pos->next);
//1 種方法	//Datatype temp = 0;
	//SListNode *behind = pos;
	//SListNode*prv =_BuyNode(x);
	//SListNode *next = behind->next;
	//pos->next = prv;
	//prv->next = next;
	//temp = pos->data;
	//pos->data = prv->data;
	//prv->data = temp;
//2 種方法
	SListNode*prv = _BuyNode(pos->data);
	prv->next = pos->next;
	pos->next = prv;
	pos->data = x;
}
//查找中間節(jié)點
SListNode *FindmidNode(SListNode *phead)
{
	SListNode *fast = phead;
	SListNode *slow = phead;
	while (fast&&fast->next)
	{
		fast = fast->next->next;
        slow = slow->next;	
	}
	return slow;
}

    //找倒數(shù)第k個節(jié)點
SListNode *FindkNode(SListNode *phead, int k)
{
	SListNode *fast = phead;
	SListNode *slow = phead;
    /*for (int i = 1; i<=k-1; i++)
		{
		 	fast = fast->next;
		}
	while (fast->next)
	{
		
		slow = slow->next;
		fast = fast->next;
	}*/
	while (fast&&k--)
	{
		
		fast= fast->next;
		if (fast == NULL)
			return NULL;
	}
	while (fast)
	{
		slow = slow->next;
		fast = fast->next;
	}
	return slow;
}
//從尾到頭打印鏈表
void PrintTailToHead(SListNode*phead)
{
	if (phead)
	{
		PrintTailToHead(phead->next);
		printf("%d ", phead->data);
	}
}
//
SListNode *Reverse(SListNode *phead)//單鏈表的逆置
{
	SListNode *cur = phead;
	SListNode *newhead = NULL;
	while (cur)
	{
		SListNode*tmp =cur;
		cur = cur->next;
		tmp->next =newhead;
		newhead = tmp;
	}
	return newhead;
}
void test1()
{
	SListNode*list = NULL;
	PushBack(list, 1);
	PushBack(list, 3);
	PushBack(list, 2);
	PushBack(list, 4);
	PushBack(list, 6);
	PrintSlist(list);
}
void test2()
{
	SListNode*list = NULL;
	PushBack(list, 1);
	PushBack(list, 2);
	PushBack(list, 3);
	PushBack(list, 4);
	PushBack(list, 5);
	PushBack(list, 6);
	PushBack(list, 7);
	PrintSlist(list);
	//Find(list, 4);
	//Insert(list,7, 8);
	SListNode *pos = Find(list, 1);
	Erase(list,pos );
	PrintSlist(list);
}
void test3()
{
	SListNode*list = NULL;
	PushBack(list, 1);
	PushBack(list, 2);
	PushBack(list, 3);
	PushBack(list, 4);
	PushBack(list, 5);
	PushBack(list, 6);
	PushBack(list, 7);
	PrintSlist(list);
	SListNode *pos = Find(list ,7);
	Insert(pos, 2);
	PrintSlist(list);
}
void test4()
{
	SListNode*list = NULL;
	PushBack(list, 1);
	PushBack(list, 2);
	PushBack(list, 3);
	PushBack(list, 4);
	PushBack(list, 5);
	PushBack(list, 6);
	PushBack(list, 7);
	PrintSlist(list);
	/*SListNode *pos = list;
	DelNoNode(pos);*/
	SListNode *pos = Find(list,1);
	InsertNoNode(pos, 9);
	PrintSlist(list);
}
void test5()
{
	SListNode *list = NULL;
	PushBack(list, 1);
	PushBack(list, 8);
	PushBack(list, 2);
	PushBack(list, 3);
	PushBack(list, 4);
	PushBack(list, 5);
	PrintSlist(list);
	//SListNode*pos = FindmidNode(list);
	SListNode*pos =FindkNode(list, 5);
	printf("%d\n", pos->data);
	//PrintSlist(list);
}
void test6()
{
	SListNode*list = NULL;
	PushBack(list, 1);
	PushBack(list, 3);
	PushBack(list, 2);
	PushBack(list, 4);
	PushBack(list, 6);
	// 
	SListNode*pos=Reverse(list);
	PrintTailToHead(pos);
}
int main()
{
	//test1();
	test6();
	system("pause");
	return 0;
}

   以上如果發(fā)現(xiàn)有錯的地方或者還有其他建議，希望提出寶貴意見。謝謝?。?！