//單鏈表的類定義linklist3.h
#ifndef linklist3H
#define linklist3H
#define LEN 30
//定義ElemType為int
typedef int ElemType;
//單鏈表中結(jié)點的類型
typedef struct LNode{
  ElemType data;//值域
  LNode *next;  //指針域
}LNode;
class LinkList{
  LNode *head;
 public:
//不帶形參構(gòu)造函數(shù)
  LinkList();
//帶一個形參構(gòu)造函數(shù)
  LinkList(int);
//帶二個形參構(gòu)造函數(shù) ,n是初始化元素個數(shù)，
//mark=0不排序，mark>0升序，mark<0降序
  LinkList(int n,int mark=0);
//復(fù)制構(gòu)造函數(shù)
  LinkList(LinkList& HL);
//析構(gòu)函數(shù)
  ~LinkList();
//清空單鏈表
  void ClearList();
//求單鏈表長度
  int ListSize();
//檢查單鏈表是否為空
  bool ListEmpty();
//返回單鏈表中指定序號的結(jié)點值
  ElemType GetElem(int pos);
//遍歷單鏈表
  void TraverseList(void f(ElemType &));
//從單鏈表中查找元素
  bool FindList(ElemType& item);
//更新單鏈表中的給定元素
  bool UpdateList(const ElemType& item,ElemType e);
//向單鏈表插入元素 , mark=0 插在表首，否則插在表尾
  void InsertList(ElemType item,int mark);
//從單鏈表中刪除元素 , mark為要刪除的第幾個元素
  bool DeleteList(ElemType& item,int mark);
//對單鏈表進行有序排列   mark>0 升序  否則降序
  void pailie(int mark=1);
//單鏈表la 和lb 的元素按值非遞減排列,兩個單鏈表
//合并后的鏈表也是一個有序的
  void MergeList_L(LinkList &la,LinkList &lb);
//對單鏈表進行有序輸出,mark=0不排序，mark>0升序，mark<0降序
  void OrderOutputList(int mark=0);
};
#endif
//linklist3.cpp
#include "linklist3.h"
LinkList::LinkList()//不帶形參構(gòu)造函數(shù)
{head=new LNode;
 head->next=NULL;
}
LinkList:: LinkList(int d1)//帶一個形參構(gòu)造函數(shù)
{head=new LNode;
 head->next = new LNode;
 head->next->data = d1;
 head->next ->next=NULL;
}
//帶二個形參構(gòu)造函數(shù)
LinkList::LinkList(int n,int mark)
{randomize();
 ElemType a[LEN+1];
 for(int i=1;i<=n;i++)
   a[i]=random(150+i);
 for(int i=1;i<n;i++)
 for(int j=1;j<=n-i;j++)
  {int t;
   if( mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1])
    {t=a[j+1];
     a[j+1]=a[j];
     a[j]=t;
    }
  }
 head=new LNode;
 LNode *p=head,*q;
 for(int i=1;i<=n;i++)
  {q= new LNode;
   q->data =a[i];
   p->next =q;
   p=p->next;
  }
 p->next =NULL;
}
LinkList::LinkList(LinkList& HL)//復(fù)制構(gòu)造函數(shù)
{head=new LNode;
 head->next=NULL;
 LNode *p2=HL.head->next  ,*p1=head,*q;
 while( p2)
  {q= new LNode;
   q->data=p2->data ;
   p1->next =q;
   p1=q;
   p2=p2->next ;
  }
 p1->next =NULL;
}
LinkList::~LinkList()//析構(gòu)函數(shù)
{LNode *p=head->next ,*q;
 while(p)
  {q=p->next ;
   free(p);
   p=q;
  }
}
void LinkList::ClearList()//清空單鏈表
{LNode*p=head->next ,*q;
 while(p)
  {q=p->next;
   free(p);
   p=q;
  }
 head->next =NULL;
}
int LinkList::ListSize()//求單鏈表長度
{LNode*p=head->next ;
 int i=0;
 while(p)
  {i++;
   p=p->next ;}
 return i;
}
bool LinkList::ListEmpty()//檢查單鏈表是否為空
{return ListSize()==0;}
//返回單鏈表中指定序號的結(jié)點值
ElemType LinkList::GetElem(int pos)
{LNode*p=head->next ;
 int i=1;
 while(p)
  {if(i++==pos)return p->data ;
   p=p->next ;
  }
 return head->data ;
}
void LinkList::TraverseList(void f(ElemType &))//遍歷單鏈表
{LNode*p=head->next ;
 while(p)
  {f(p->data );
   p=p->next ;}
}
bool LinkList::FindList(ElemType& item)//從單鏈表中查找元素
{LNode*p=head->next ;
 while(p)
  {if(p->data==item)return 1;
   p=p->next ;}
 return 0;
}
//更新單鏈表中的給定元素
bool LinkList::UpdateList(const ElemType &item,ElemType e)
{LNode*p=head->next ;
 int flag=0;
 while(p)
  {if(p->data==item)
    {p->data=e;
     flag=1;}
   p=p->next ;}
 return flag;
}
//向單鏈表插入元素
void LinkList::InsertList(ElemType item,int mark)
{LNode *q= new LNode;
 q->data = item;
 if(mark==0)
  {q->next = head->next ;
   head->next=q;
   return;}
 LNode *p=head;
 while(p->next)
  {p=p->next ;}
 q->next =NULL;
 p->next =q;
}
//從單鏈表中刪除元素
bool LinkList::DeleteList(ElemType& item,int mark)
{if(ListEmpty()||mark<1||mark>ListSize())return 0;
 LNode *p=head,*q;
 for(int i=0;i<mark-1;i++)
   p=p->next;
 item=p->next->data;
 q=p->next->next ;
 free(p->next );
 p->next=q;
 return 1;
}
//對單鏈表進行有序排列mark>0升序,否則降序
void LinkList::pailie(int mark)
{ElemType a[LEN+1];
 LNode *p=head->next;
 int k ;
 for(k=1;p!=NULL;k++,p=p->next )
   a[k]=p->data;
 k--;
 for(int i=1;i<k;i++)
  for(int j=1;j<=k-i;j++)
   {int t;
    if( mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1])
     {t=a[j+1];
      a[j+1]=a[j];
      a[j]=t;}}
 p=head->next;
 for(int j=1;j<=k;j++,p=p->next )
  p->data=a[j];
}
//單鏈表la 和lb 的元素按值非遞減排列,兩個單鏈表
//合并后的鏈表也是一個有序的
void LinkList::MergeList_L(LinkList &la,LinkList &lb)
{LNode *pa=la.head->next ,*pb=lb.head->next ,*p=head;
 while(pa&&pb)
  {LNode *q=new LNode;
   if(pa->data <pb->data )
    {q->data =pa->data;
     pa=pa->next ;
     p->next =q;
     p=q;}
   else
    {q->data =pb->data;
     pb=pb->next ;
     p->next =q;
     p=q;}
  }
 while(pa)
  {LNode *q=new LNode;
   q->data =pa->data;
   pa=pa->next ;
   p->next =q;
   p=q;}
 while(pb)
  {LNode *q=new LNode;
   q->data =pb->data;
   pb=pb->next ;
   p->next =q;
   p=q;}
 p->next =NULL;
}
//對單鏈表進行有序輸出
void LinkList::OrderOutputList(int mark)
{ElemType a[LEN+1];
 LNode *p=head->next;
 int k ;
 for( k=1;p!=NULL;k++,p=p->next )
   a[k]=p->data;
 k--;
 for(int i=1;i<k;i++)
  for(int j=1;j<=k-i;j++)
   {int t;
    if( mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1])
     {t=a[j+1];
      a[j+1]=a[j];
      a[j]=t;}}
 for(int j=1;j<=k;j++)
  cout<<a[j]<<"  ";
}
//linklist3m.cpp
#include<iostream.h>
#include"linklist3.cpp"
void ff(int &a)//用于遍歷的函數(shù)
{cout<<a<<",";}
void main()
{cout<<"linklist3m.cpp運行結(jié)果:\n";
 int init_size,xu;
 cout<<"\n首先請構(gòu)造單鏈表list1";
 cout<<"\n初始化長度(1--30):";
 cin>>init_size;
 cout<<"是否排序:(=0不排序,=1升序,=-1降序):";
 cin>>xu;
 //構(gòu)造單鏈表list1調(diào)用二個形參構(gòu)造函數(shù)
 LinkList list1(init_size,xu);
 cout<<"\n單鏈表list1構(gòu)造成功!"<<"\n它是:";
 list1.TraverseList(ff);
 cout<<"\n它為空嗎?(1:是;0:不是):"<<list1.ListEmpty();
 cout<<"\n長度為:"<<list1.ListSize() ;
 int i;
 cout<<"\n請輸入你想得到第幾個元素的值(1--"<<init_size<<"):";
 cin>>i;
 cout<<"單鏈表list1中第"<<i<<"的值是"<<list1.GetElem(i);
 int it;
 cout<<"\n請輸入你想刪除第幾個元素的值(1--"<<init_size<<"):";
 cin>>i;
 list1.DeleteList(it,i);
 cout<<"\n單鏈表list1刪除第"<<i<<"個元素"<<"\'"<<it<<"\'"<<"后變?yōu)?";
 list1.TraverseList(ff); //對單鏈表list1每個數(shù)進行遍歷.
 int news,olds;
 cout<<"\n請輸入要被修改的元素:"; cin>>olds;
 cout<<"請輸入修改后要變成的元素:"; cin>>news;
 list1.UpdateList(olds,news);
 cout<<"\n修改后單鏈表list1變?yōu)?quot;;
 list1.TraverseList(ff);
 cout<<"\n下面請構(gòu)造單鏈表list2";
 cout<<"\n請輸入單鏈表list2初始化長度(1--30):";
 cin>>init_size;
 cout<<"請選擇是否排序:(=0不排序,=1 升序,=-1 降序):";
 cin>>xu;
 //構(gòu)造單鏈表list2調(diào)用二個形參構(gòu)造函數(shù)
 LinkList list2(init_size,xu);
 cout<<"\n單鏈表list2為:";
 list2.TraverseList(ff);
 LinkList list3;//構(gòu)造單鏈表list3 調(diào)用一個形參構(gòu)造函數(shù)
 list1.pailie(); //對單鏈表進行升序排列
 list2.pailie(); //對單鏈表進行升序排列
 list3.MergeList_L(list1,list2);//聯(lián)合list1和list2
 cout<<"\nlist1和list2聯(lián)合之后為list3:\n";
 list3.TraverseList(ff);
 cout<<"\n這時它為空嗎?(1:是;0:不是):"<<list3.ListEmpty();
 cout<<"\n長度為:"<<list3.ListSize() ;
 list3.ClearList();//清空單鏈表list3
 cout<<"\n清空單鏈表list3\n";
 cout<<"\n按回車鍵結(jié)束...";
 cin.get();cin.get();}
linklist3m.cpp運行結(jié)果:
首先請構(gòu)造單鏈表list1
初始化長度(1--30):10
是否排序:(=0不排序,=1升序,=-1降序):1
單鏈表list1構(gòu)造成功!
它是:8,16,24,42,90,97,109,111,111,125,
它為空嗎?(1:是;0:不是):0
長度為:10
請輸入你想得到第幾個元素的值(1--10):7
單鏈表list1中第7的值是109
請輸入你想刪除第幾個元素的值(1--10):5
單鏈表list1刪除第5個元素'90'后變?yōu)?
8,16,24,42,97,109,111,111,125,
請輸入要被修改的元素:109
請輸入修改后要變成的元素:98
修改后單鏈表list1變?yōu)?,16,24,42,97,98,111,111,125,
下面請構(gòu)造單鏈表list2
請輸入單鏈表list2初始化長度(1--30):7
請選擇是否排序:(=0不排序,=1 升序,=-1 降序):-1
單鏈表list2為:148,121,62,47,26,23,4,
list1和list2聯(lián)合之后為list3:
4,8,16,23,24,26,42,47,62,97,98,111,111,121,125,148,
這時它為空嗎?(1:是;0:不是):0
長度為:16
清空單鏈表list3
按回車鍵結(jié)束...