程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 數據結構與算法系列(1)-單鏈表類的實現(C++)

數據結構與算法系列(1)-單鏈表類的實現(C++)

編輯:C++入門知識

數據結構與算法系列(1)-單鏈表類的實現(C++)


通過定義一個C++類封裝單鏈表這種數據結構,

封裝的方法有:

1.通過輸入創建單鏈表;

2.獲取單鏈表的數據元素個數;

3.打印輸出單鏈表中各個元素;

4.搜索某個元素在單鏈表中的位置;

5.在某個位置之後插入一個結點;

6.在某個位置刪除一個節點;

7.單鏈表逆置;

8.單鏈表是否存在回環的判定;

9.單鏈表的升序排序;

10.兩個單鏈表的升序合並;

11.兩個單鏈表的降序合並。

注:單鏈表的排序采用的是快速排序的方法。

下面是C++寫的程序代碼,附運行截圖。

 

#include 
#include 
#include 

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<data<<"  ";
		p=p->next;
	}
	p=NULL;
	delete p;
	cout<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;idata)>(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->datadata)
		{
			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:"<>DataSearch;
	cout<>DataInsert;
	cout<<"Input the position to insert:"<>PosInsert;
	if(L.InsertNode(PosInsert,DataInsert))
	{
	cout<<"Insert successfully! The new list is:";
	L.PrintList();

	}
	else
	cout<<"Insert Failed!"<>PosDel;
	if(L.DeleteNode(PosDel))
	{
	cout<<"Delete successfully! The new list is:";
	L.PrintList();
	}
	else
	{
	cout<<"Delete Failed!"<運行截圖

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved