無頭不循環單連結清單

1. 連結清單節點的删除與插入；
2. 連結清單節點的查詢；
3. 連結清單的快慢指針用法；
4. 連結清單的逆置(兩種方法)；(暫不考慮遞歸實作)
5. 有序連結清單和合并；

頭檔案"Slist.h"

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DateType;
typedef struct PlistNode
{
	DateType _date;
	struct PlistNode* _next;
} PlistNode;
PlistNode* GetNode(DateType x);
void Print(PlistNode* plist);  //列印函數
void PushBack(PlistNode** pplist, DateType x);  //尾插
void PopBack(PlistNode** pplist);  //尾删
void PushFront(PlistNode** pplist, DateType x);  //頭插
void PopFront(PlistNode** pplist);  //頭删
PlistNode* ListFind(PlistNode* plist, DateType x);  //查找節點
void ListInsertAfter(PlistNode** pos, DateType x);  //在一個連結清單的pos位後插入
void SListEraseAfter(PlistNode** pos);  //删除某個連結清單pos後的一個節點
PlistNode* middleNode(PlistNode** head);  //傳回連結清單的中間節點(快慢指針實作)
PlistNode* reverseList1(PlistNode** head);  //逆轉連結清單(改變指針方向)
PlistNode* reverseList2(PlistNode** head);  //逆轉連結清單(頭插法每一個原連結清單值插入新連結清單)
PlistNode* FindKNode(PlistNode** head, int k);  //傳回該連結清單中倒數第k個結點(含第k個節點)後所有結點(快慢指針實作)
           

源檔案"Slist.c"

#include "Slist.h"
void Print(PlistNode* plist)  //列印函數
{
	PlistNode* cur = plist;
	while (cur != NULL)
	{
		printf("%d\n", cur->_date);
		cur = cur->_next;
	}
	printf("\n");
}
PlistNode* GetNode(DateType x)  //得到一個新的節點，并将要插入得值賦給該節點
{
	PlistNode* NewNode = (PlistNode*)malloc(sizeof(PlistNode));
	NewNode->_date = x;
	NewNode->_next = NULL;
	return NewNode;  //新節點的指針
}
void PushBack(PlistNode** plist, DateType x)  //尾插
{
	PlistNode* NewNode = GetNode(x);
	if (*plist == NULL)
		*plist = NewNode;
	else
	{
		PlistNode* tail = *plist;
		while (tail->_next != NULL)
			tail = tail->_next;
		tail->_next = NewNode;
	}
}
void PopBack(PlistNode** plist)  //尾删
{
	if (*plist == NULL || (*plist)->_next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		PlistNode* cur = *plist;
		PlistNode* prv = NULL;
		while (cur->_next != NULL)
		{
			prv = cur;
			cur = cur->_next;
		}
		free(cur);
		cur = NULL;
		prv->_next = NULL;
	}
}
void PushFront(PlistNode** plist, DateType x)  //頭插
{
	PlistNode* NewNode = GetNode(x);
	if (*plist == NULL)
		*plist = NewNode;
	else
	{
		NewNode->_next = *plist;
		*plist = NewNode;
	}
}
void PopFront(PlistNode** plist)  //頭删
{
	if (*plist == NULL)
		return;
	else if ((*plist)->_next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		PlistNode* cur = (*plist)->_next;
		free(*plist);
		*plist = cur;
	}
}
PlistNode* ListFind(PlistNode* pslist, DateType x)  //查找函數
{
	assert(pslist);
	PlistNode* cur = pslist;
	while (cur != NULL)
	{
		if (x == cur->_date)
			return cur;
		cur = cur->_next;
	}
	return NULL;
}
void ListInsertAfter(PlistNode** pos, DateType x)  //在一個連結清單的pos位後插入
{
	PlistNode* cur = GetNode(x);
	PlistNode* tmp = NULL;
	tmp = (*pos)->_next;
	(*pos)->_next = cur;
	cur->_next = tmp;
}
void SListEraseAfter(PlistNode** pos)  //删除某個連結清單pos後的一個節點
{
	PlistNode* tmp = NULL;
	PlistNode* cur = NULL;
	tmp = (*pos)->_next;
	cur = tmp->_next;
	(*pos)->_next = cur;
	free(tmp);
	tmp = NULL;
}
PlistNode* middleNode(PlistNode** head)  //傳回連結清單的中間節點(快慢指針實作)
{
	PlistNode* fast = *head;
	PlistNode* slow = *head;
	while (fast != NULL && fast->_next != NULL)
	{
		fast = fast->_next->_next;
		slow = slow->_next;
	}
	return slow;
}
PlistNode* reverseList1(PlistNode** head)  //逆轉連結清單(改變指針方向)
{
	if ((*head == NULL) || ((*head)->_next == NULL))
		return *head;
	PlistNode* n1 = (*head);
	PlistNode* n2 = (*head)->_next;
	PlistNode* n3 = n2->_next;
	n1->_next = NULL;
	while (n2 != NULL)
	{
		n2->_next = n1;
		n1 = n2;
		n2 = n3;
		if (n3 != NULL)  //判斷是否逆置完成
			n3 = n3->_next;
	}
	return n1;
}
PlistNode* reverseList2(PlistNode** head)  //逆轉連結清單(頭插法每一個原連結清單值插入新連結清單)
{
	if ((*head) == NULL || (*head)->_next == NULL)
		return (*head);
	PlistNode* cur = *head;
	PlistNode* newhead = GetNode(cur->_date);
	PlistNode* tmp = NULL;
	while (cur->_next != NULL)
	{
		cur = cur->_next;
		tmp = GetNode(cur->_date);
		tmp->_next = newhead;
		newhead = tmp;
	}
	return newhead;
}
PlistNode* FindKNode(PlistNode** head, int k)  //傳回該連結清單中倒數第k個結點(含第k個節點)後所有結點(快慢指針實作)
{
	if ((*head) == NULL)  //排除空指針情況
		return NULL;
	PlistNode* fast = *head;
	PlistNode* slow = *head;
	while (k--)
	{
		if (fast == NULL)  //排除k大于連結清單總長度
			return NULL;
		fast = fast->_next;
	}
	while (fast != NULL)
	{
		fast = fast->_next;
		slow = slow->_next;
	}
	return slow;
}
           

主函數"main.c"

#include "Slist.c"
void text()
{
	PlistNode* head = NULL;
	PlistNode* cur = NULL;
	PlistNode* res1 = NULL;
	PlistNode* res2 = NULL;
	PlistNode* res3 = NULL;
	PushBack(&head, 1);
	PushBack(&head, 2);
	PushBack(&head, 3);
	PushBack(&head, 4);
	PushBack(&head, 5);
	Print(head);
	PopBack(&head);
	Print(head);
	PushFront(&head, 0);
	Print(head);
	cur = ListFind(head, 4);
	Print(cur);
	ListInsertAfter(&cur, 100);
	Print(head);
	SListEraseAfter(&cur);
	Print(head);
	res1 = middleNode(&head);
	printf("%d\n\n", res1->_date);  //輸出資料中間節點
	res1 = reverseList1(&head);
	Print(res1);
	res2 = reverseList2(&res1);  //head已為空，傳head無效
	Print(res2);
	res3 = FindKNode(&res2, 3);
	printf("%d\n\n", res3->_date);  //輸出倒數第k個節點資料
	Print(res3);  //輸出倒數第k個節點後所有節點資料
}
int main()
{
	text();
	system("pause");
	return 0;
}