C++链表的建立，排序，删除

描述：使用随机数建立链表节点，节点的结构很简单，就是一个整形数（随机数）和一个指针，有三个函数，第一个函数建立链表，第二个函数对链表进行排序，第三个函数将链表中所有有重复数字的节点删除，只留只出现过一次的节点。

输入：链表的节点数

输出：

1.建立的链表

2.排序后的链表

3.删除后的链表

#include<iostream>
#include<stdlib.h>
#include<time.h>
#define random(x) (rand()%x)
using namespace std;
struct numst//定义结构体变量
{
	int num;
	numst *next;
};
numst *head=NULL;//定义头指针，并置空
numst *creat()//定义函数。用来创建范围为0～9的链表，由用户设定链表节点个数
{
	numst *p=NULL;
	numst *q=NULL;//定义两个结构体指针变量，用来作为循环迭代中间量
	int sum;
	cout<<"input the sum of nodes:";
	cin>>sum;//由用户输入节点个数
	while(sum)//while循环num次，产生num个链表节点
	{
		p=new numst;
		p->num=random(10);//将产生的随机数赋给新产生的结构体中的变量
		if(head==NULL)//如果头指针为空，则把第一个节点设为头节点
			head=p;
		else
			q->next=p;//否则将p指向q的下一个节点
		q=p;//另q保持为最末尾的节点
		sum--;
	}
	if(head!=NULL)
		q->next=NULL;//将最后一个节点的指针指向空
	numst *begin=head;
	while(begin!=NULL)
	{
		cout<<begin->num<<" ";
		begin=begin->next;
	}//输出生成的链表
	cout<<endl;
	return(head);//函数返回头指针

}
numst *seq(numst *head)//定义函数将随机数链表进行排序
{
	int sum=0,mid;//定义节点总数num,和冒泡法排序的中间量mid
	numst *temp=head;//定义节点数统计指针
	numst * m=head;
	numst * n;//定义冒泡法指针
	while(temp!=NULL)
	{
		sum++;
		temp=temp->next;
	}//统计节点数
	for(int i=0;i<sum;i++)
	{
		n=m->next;//总是保持n指向m的下一个节点
		for(int j=i+1;j<sum;j++)
		{
			if(m->num>n->num)
			{
				mid=m->num;
				m->num=n->num;
				n->num=mid;
			}
			n=n->next;//让m和m以后的所有节点比较

		}
		m=m->next;//m指向下一个节点
	}

		numst *begin=head;
	while(begin!=NULL)
	{
		cout<<begin->num<<" ";
		begin=begin->next;
	}
	cout<<endl;//输出排序后的指针

	return (head);
}
 numst *deletes(numst *head)//定义函数将所有的有数字重复的节点删除
{
	numst *a=head;//定义外层循环的指针a,b是连续的两个指针b在a的后面，每次循环，
	numst *b=a->next;//b就和a比较，如果相同，则将值赋给mark,进行内层循环的删除工作；
	numst *start=head;//定义内层循环的指针，former总是指向start的前一个节点；
	numst *former=NULL;
	int mark;//标记相等的节点的值
	while(b!=NULL)//外层循环，此处不能设为b->next!=NULL,因为会导致最后两个相等的节点不能删除，
	{				//因为最后一个节点的指针指向NULL，所以导致最后这个节点的循环被跳过
		
		if(b->num==a->num)
		{
			mark=a->num;
			while(start!=NULL)
			{
				if((start==head)&&(start->num==mark))//情况一：要删除的是头节点
				{
					if(start->next==NULL)
					{
						cout<<"all deleted"<<endl;
						return(NULL);//如果所有的节点都被删除，则返回NULL；
					}
					head=start->next;//head指向头节点的下一个
					delete start;//删除头节点
					a=head;//由于头节点被删除所以有可能外层循环的a,b指向的节点已被删除，
					b=a->next;//所以重新将a指向头节点
					start=head;//对比的起始点也重置为头节点
				}
				else if(start->num==mark)//第二种情况：不是头节点
				{
					former->next=start->next;
					delete start;//如果符合情况，则删除本节点
					start=former->next;//将start重新指向former的下一个节点
					b=former;//更新b，将外层循环的b设为former，说明外层循环从former开始，以免b的指向丢失
				}
				else//第三种情况：节点不等于mark，则向前推进
				{
					former=start;
					start=start->next;
				}
				
			}
			start=head;//为了测试下一个mark，必须将对比的起始点在此重置为头节点
		}
		else
		{
		a=b;
		b=b->next;//如果不是头节点，继续向后推进，寻找相同节点
		}
	}
	numst *begin=head;
	while(begin!=NULL)
	{
		cout<<begin->num<<" ";
		begin=begin->next;
	}
	cout<<endl;//输出删除后的链表
}
int main()
{
	srand((int)time(0));//设置随机数种子
	deletes(seq(creat()));//调用函数
	return 0;
}