數據結構與算法系列（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!"<運行截圖
