【C语言学习】单链表的创建、增删、交换、排序

相对于数组，链表可以动态地更改大小，但它也无法像数字那样根据角标进行索引，几乎所有操作都要从头节点开始遍历。若头节点频繁改变，则会使其他操作变得更加棘手。

所以干脆不让头节点存放有效数据，不参与其他操作，来保证每个链表的头指针固定不变，也可以用头节点储存链表长度。

#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
	int data;
	struct node* next;
}NODE;

NODE* CreatNode()//创建链表头
{
	NODE* headnode = (NODE*)malloc(sizeof(NODE));
	headnode->next = NULL;
	return headnode;
}

void AddendNode(NODE* head,int data)//在尾部添加节点
{
	if (head==NULL)
	{
		printf("No such node.\n");
		exit(0);
	}
	NODE* p = (NODE*)malloc(sizeof(NODE)),*pmove=head;
	int i = 1;
	while (pmove->next!=NULL)
	{
		pmove = pmove->next;
		i++;
	}
	pmove->next = p;
	p->data = data;
	p->next = NULL;
	head->data = i;
}

void AddheadNode(NODE* head, int data)//在头部添加节点
{
	if (head == NULL)
	{
		printf("No such node.\n");
		exit(0);
	}
	NODE* p = (NODE*)malloc(sizeof(NODE)), * pmove = head;
	p->next = head->next;
	p->data = data;
	head->next = p;
	int i = 1;
	while (pmove->next != NULL)
	{
		i++;
		pmove = pmove->next;
	}
	head->data = i;
}

void DisplayNode(NODE* head)//打印链表
{
	NODE* pmove = head->next;
	int i = 1;
	while (pmove != NULL)
	{
		printf("%d  %d\n", i, pmove->data);
		pmove = pmove->next;
	}
}

NODE* FindprNoode(NODE* head, NODE* p)//找出节点p的前一个节点
{
	NODE* pmove = head;
	while (pmove!=NULL)
	{
		if (pmove->next==p)
		{
			return pmove;
		}
		pmove = pmove->next;
	}
	return NULL;
}

void SwapNode(NODE* head, NODE* a, NODE* b)//交换a、b两个节点，需要找前驱函数
{
	NODE* apr = FindprNoode(head, a);
	NODE* bpr = FindprNoode(head, b);
	NODE* temp = NULL;
	if (a==b)
	{
		return;
	}
	if (a->next==b)
	{
		temp = b->next;
		apr->next = b;
		b->next = a;
		a->next = temp;
	}
	else if (b->next==a)
	{
		temp = a->next;
		bpr->next = a;
		a->next = b;
		b->next = temp;
	}
	else
	{
		temp = b->next;
		apr->next = b;
		b->next = a->next;
		bpr->next = a;
		a->next = temp;
	}
}

void SortNode(NODE* head)//对链表进行排序，需要交换函数
{
	NODE* t = NULL, * m = NULL,*temp=NULL;
	for (t = head->next; t != NULL; t = t->next)
	{
		temp = t;
		for (m = t->next; m != NULL; m = m->next)
		{
			if (m->data>temp->data)
			{
				temp = m;
			}
		}
		if (temp->data != t->data)
		{
			SwapNode(head, t, temp);
			t = temp;
		}
	}
}

void DeletoneNode(NODE* head, int data)//删除所有数据为data的节点
{
	NODE* pmove = head->next, * temp = NULL, * pr = head;
	if (pmove == NULL)
	{
		printf("Blank Node!\n");
		return;
	}
	else
	{
		while (pmove != NULL)
		{
			if (pmove->data != data)
			{
				pr = pmove;
				pmove = pmove->next;
			}
			else
			{
				temp = pmove;
				pr->next = pmove->next;
				pmove = pmove->next;
				free(temp);
			}
		}
	}
}

void DeleteAll(NODE* head)//释放链表
{
	NODE* pr = NULL, * p = head;
	while (p != NULL)
	{
		pr = p;
		p = p->next;
		free(pr);
	}
}

int main()
{
	char c;
	int data;
	NODE* testNode = CreatNode();
	printf("Create?");
	scanf("%c", &c);
	getchar();
	while (c=='Y'||c=='y')
	{
		printf("data=");
		scanf("%d", &data);
		getchar();
		AddendNode(testNode, data);
		printf("Continue?");
		scanf("%c", &c);
		getchar();
	}

	SortNode(testNode);
	DisplayNode(testNode);
	DeleteAll(testNode);
	return 0;
}