数据结构与算法系列（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;i
       
        data)>(m->data)) { s->data^=m->data;//交换 m->data^=(s->data); s->data^=(m->data); } s=s->next; m=m->next; } QuikSort(start,midl); Quik