linklist3.txt

C++描述的数据结构内容,在C++builder的环境中运行,这是第二部分

//单链表的类定义linklist3.h
#ifndef linklist3H
#define linklist3H
#define LEN 30
//定义ElemType为int
typedef int ElemType;
//单链表中结点的类型
typedef struct LNode{
  ElemType data;//值域
  LNode *next;  //指针域
}LNode;
class LinkList{
  LNode *head;
 public:
//不带形参构造函数
  LinkList();
//带一个形参构造函数
  LinkList(int);
//带二个形参构造函数 ,n是初始化元素个数，
//mark=0不排序，mark>0升序，mark<0降序
  LinkList(int n,int mark=0);
//复制构造函数
  LinkList(LinkList& HL);
//析构函数
  ~LinkList();
//清空单链表
  void ClearList();
//求单链表长度
  int ListSize();
//检查单链表是否为空
  bool ListEmpty();
//返回单链表中指定序号的结点值
  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()//不带形参构造函数
{head=new LNode;
 head->next=NULL;
}
LinkList:: LinkList(int d1)//带一个形参构造函数
{head=new LNode;
 head->next = new LNode;
 head->next->data = d1;
 head->next ->next=NULL;
}
//带二个形参构造函数
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)//复制构造函数
{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()//析构函数
{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;}
//返回单链表中指定序号的结点值
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)//用于遍历的函数
{cout<<a<<",";}
void main()
{cout<<"linklist3m.cpp运行结果:\n";
 int init_size,xu;
 cout<<"\n首先请构造单链表list1";
 cout<<"\n初始化长度(1--30):";
 cin>>init_size;
 cout<<"是否排序:(=0不排序,=1升序,=-1降序):";
 cin>>xu;
 //构造单链表list1调用二个形参构造函数
 LinkList list1(init_size,xu);
 cout<<"\n单链表list1构造成功!"<<"\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<<"\'"<<"后变为:";
 list1.TraverseList(ff); //对单链表list1每个数进行遍历.
 int news,olds;
 cout<<"\n请输入要被修改的元素:"; cin>>olds;
 cout<<"请输入修改后要变成的元素:"; cin>>news;
 list1.UpdateList(olds,news);
 cout<<"\n修改后单链表list1变为";
 list1.TraverseList(ff);
 cout<<"\n下面请构造单链表list2";
 cout<<"\n请输入单链表list2初始化长度(1--30):";
 cin>>init_size;
 cout<<"请选择是否排序:(=0不排序,=1 升序,=-1 降序):";
 cin>>xu;
 //构造单链表list2调用二个形参构造函数
 LinkList list2(init_size,xu);
 cout<<"\n单链表list2为:";
 list2.TraverseList(ff);
 LinkList list3;//构造单链表list3 调用一个形参构造函数
 list1.pailie(); //对单链表进行升序排列
 list2.pailie(); //对单链表进行升序排列
 list3.MergeList_L(list1,list2);//联合list1和list2
 cout<<"\nlist1和list2联合之后为list3:\n";
 list3.TraverseList(ff);
 cout<<"\n这时它为空吗?(1:是;0:不是):"<<list3.ListEmpty();
 cout<<"\n长度为:"<<list3.ListSize() ;
 list3.ClearList();//清空单链表list3
 cout<<"\n清空单链表list3\n";
 cout<<"\n按回车键结束...";
 cin.get();cin.get();}
linklist3m.cpp运行结果:
首先请构造单链表list1
初始化长度(1--30):10
是否排序:(=0不排序,=1升序,=-1降序):1
单链表list1构造成功!
它是: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'后变为:
8,16,24,42,97,109,111,111,125,
请输入要被修改的元素:109
请输入修改后要变成的元素:98
修改后单链表list1变为8,16,24,42,97,98,111,111,125,
下面请构造单链表list2
请输入单链表list2初始化长度(1--30):7
请选择是否排序:(=0不排序,=1 升序,=-1 降序):-1
单链表list2为:148,121,62,47,26,23,4,
list1和list2联合之后为list3:
4,8,16,23,24,26,42,47,62,97,98,111,111,121,125,148,
这时它为空吗?(1:是;0:不是):0
长度为:16
清空单链表list3
按回车键结束...