数据结构与算法系列（1）-单链表类的实现（C++)

通过定义一个C++类封装单链表这种数据结构,

封装的方法有：

1.通过输入创建单链表；

2.获取单链表的数据元素个数；

3.打印输出单链表中各个元素；

4.搜索某个元素在单链表中的位置；

5.在某个位置之后插入一个结点；

6.在某个位置删除一个节点；

7.单链表逆置；

8.单链表是否存在回环的判定；

9.单链表的升序排序；

10.两个单链表的升序合并；

11.两个单链表的降序合并。

注：单链表的排序采用的是快速排序的方法。

下面是C++写的程序代码，附运行截图。

#include <iostream>
#include <malloc.h>
#include <math.h>

using namespace std;

typedef struct node //结点类型
{
	int data;//数据域
	node* next;//指针域
}node;

class LinkList//单链表类的定义
{

public:
	LinkList(int N=0)//但参数构造函数，生成含N个元素的链表（不包括头结点）
	{
		CreateList(N);
		len=GetLength();
	}
	node* head;//头结点指针
	int len;//元素个数
public:
	void CreateList(int n);//根据输入创建单链表
	int GetLength();//获取单链表的长度（元素个数）
	void PrintList();//打印单链表的各个元素
	int  SearchNode(int data);//查找某个元素在单链表中的位置，不过不存在，返回0。
	bool InsertNode(int pos,int data);//在pos位置后插入值为data的节点
	bool DeleteNode(int pos);//删除pos位置后的第一个元素,删除成功返回true.
	void Reverse();//将单链表逆置
	bool IsLoop();//判断单链表中是否存在会换，存在返回真，不存在返回false
	void SelfASOrder();//将链表中元素升序排列
	void ASCMerge(LinkList& L);//与另一个链表升序合并
	void DESCMerge(LinkList& L);//与L链表降序合并

private:
	void QuikSort(node* start,node* end);
	
};

void LinkList::CreateList(int n)//根据输入创建单链表
{
	head = new node;
	head->data=0;
	head->next=NULL;
	node *p,*q;
	int temp;
	q=head;
	while(n--)
	{
		cin>>temp;
		p=new node;
		p->data=temp;
		p->next=NULL;
		q->next=p;
		q=p;
		p=NULL;
		
	}
	q=NULL;
	delete q;
	
}

void LinkList::PrintList()//打印单链表的每一个元素
{
	len=GetLength();
	int l=len;
	
	node* p=head->next;
	while(l--)
	{
		cout<<p->data<<"  ";
		p=p->next;
	}
	p=NULL;
	delete p;
	cout<<endl;
}

int LinkList::GetLength()//获取单链表的长度
{
	int l=0;
	node* p=head;
	while((p->next)!=NULL)
	{
		l++;
		p=p->next;
	}
	return l;
}

int LinkList::SearchNode(int data)//查找某个元素在单链表中的位置，如果不存在这个元素，返回0
{
	int locate=0;
	node *p=head->next;
	while(len--)
	{
		if(p->data==data)
		{  locate=10-len;
			break;
		}
		p=p->next;
	}
	return locate;
}

bool LinkList::InsertNode(int pos,int data)//插入节点
{
	len=GetLength();
	if(pos>len)//插入位置超出范围
		return false;
	
	node* p=head->next;
	if(0==pos)
	{ 
		p=head;
		node* q = new node;
		q->data=data;
		q->next=p->next;
		p->next=q;
		p=NULL;
		q=NULL;
		delete p;
		delete q;
		len++;
		return true;
	}
	else
	{

	
	pos=pos-1;
	while(pos--)
	{
		p=p->next;
	}
	node* q = new node;
	q->data=data;
	q->next=p->next;
	p->next=q;
	p=NULL;
	q=NULL;
	delete p;
	delete q;
	len++;
	return true;
	}
}

bool LinkList::DeleteNode(int pos)
{
	len=GetLength();
	if(pos>=len)
		return false;
	node* p=head;
	pos=pos-1;
	while(pos--)
	{
		p=p->next;
	}
	node* q=p->next;
	p->next=p->next->next;
	delete q;
	q=NULL;
	len++;
	return true;


}

void LinkList::Reverse()
{
	node *p,*q,*r;
	if(head->next==NULL)
	{
		return;
	}
	p=head->next;
	q=p->next;
	p->next=NULL;
	while(q!=NULL)
	{
		r=q->next;
		q->next=p;
		p=q;
		q=r;
	}
	head->next=p;
}

bool LinkList::IsLoop()
{
	node *p=head->next;
	node* q=head->next->next;
	while((q!=NULL)&&(p!=q))
	{
		p=p->next;
		q=q->next->next;

	}
	if(p==q)
		return true;
	else
		return false;
}

void LinkList::SelfASOrder()//升序排列，采用快速排序的方法
{
	node* start,*end;
	int len=GetLength();
	start=head->next;
	end=start;
	while((end->next)!=NULL)
		end=end->next;
	QuikSort(start,end);

	

}

void LinkList::QuikSort(node* start,node*end)
{
	
	if(start==end)
		return;
	int Len=0;
	node* st=start;
	node* en=end;
	while(st!=en)
	{
		st=st->next;
		Len++;
	}
	double x=Len/2.0;
	double xL=floor(x);
	double xU=ceil(x);
	double HalfLen=x;
	int L=xL;
	int U=xU;
	node* mid=start;
	node* midl=start;

	while(U--)
	{
		mid=mid->next;
	}

	while(L--)
	{
		midl=midl->next;
	}
	node* s=start;
	node* m=mid;
	int flag=0;
	for(int i=0;i<xL+1;++i)
	{
		flag=midl-start+1;
		if((s->data)>(m->data))
		{
			s->data^=m->data;//交换
			m->data^=(s->data);
			s->data^=(m->data);
		}
		s=s->next;
		m=m->next;

	}
	QuikSort(start,midl);
	QuikSort(mid,end);
}

void LinkList::ASCMerge(LinkList& L)
{
	this->SelfASOrder();
	L.SelfASOrder();
	node* q=(L.head)->next;
	node* p=head->next;
	int position=0;
	while((p!=NULL)&&(q!=NULL))
	{
		if(q->data<p->data)
		{
			InsertNode(position,q->data);
			q=q->next;
			position++;
		}
		else
		{
			p=p->next;
			position++;
		}
	}
	position=GetLength();
	while(q!=NULL)
	{
		InsertNode(position,q->data);
		q=q->next;
		position++;
	}

}

void LinkList::DESCMerge(LinkList& L)
{
	ASCMerge(L);
	Reverse();
}

int main()
{
	LinkList L(10);
	cout<<"Input the L1 List:"<<endl;
	LinkList L1(15);
	L.PrintList();

	cout<<endl<<"Input the data to search:"<<endl;
	int DataSearch=0;
	cin>>DataSearch;
	cout<<L.SearchNode(DataSearch)<<endl;


	cout<<"Input the data to insert:"<<endl;
	int DataInsert=0;
	cin>>DataInsert;
	cout<<"Input the position to insert:"<<endl;
	int PosInsert=0;
	cin>>PosInsert;
	if(L.InsertNode(PosInsert,DataInsert))
	{
	cout<<"Insert successfully! The new list is:";
	L.PrintList();

	}
	else
	cout<<"Insert Failed!"<<endl;

	cout<<"Input the position to delete:"<<endl;
	int PosDel=0;
	cin>>PosDel;
	if(L.DeleteNode(PosDel))
	{
	cout<<"Delete successfully! The new list is:";
	L.PrintList();
	}
	else
	{
	cout<<"Delete Failed!"<<endl;
	}

	L.Reverse();
	cout<<"The new list after reversed is:";
	L.PrintList();

	/*if(L.IsLoop())
		cout<<"There is a Loop in the List"<<endl;
	else
		cout<<"There is No Loop in the List"<<endl;
*/
	L.SelfASOrder();
	cout<<"List after ASCSorted:";
	L.PrintList();

	LinkList L2;
	L2=L;
	L2.ASCMerge(L1);
	cout<<"L and L1 ASCMerge is:"<<endl;
	L2.PrintList();

	LinkList L3;
	L3=L;
	L3.DESCMerge(L1);
	cout<<"L and L1 DESCMerge is:"<<endl;
	L3.PrintList();
	
	return 0;
}