含头结点的单链表C++实现(包含创建,查找,插入,追加,删除,反转,排序,合并,打印,清空,销毁等基本操作)

温馨提示:下面代码默认链表数据为字符型,本代码仅供参考,希望能对找到本随笔的人有所帮助!

 #include<iostream>
 using namespace std;
 typedef struct Lnode
 {
  char data;
  struct Lnode *next;
 }LN;
 LN *CreateLinkList()
 {
  LN *head,*p,*pre;
  char ch;
  ;
  head=(LN *)malloc(sizeof(LN));
  head->next=NULL;
  pre=head;
  )
  {
   cout<<"输入第"<<i<<"个节点数据:";
   while((ch=cin.get())!='\n')
   {
   cin.get();
   p=(LN *)malloc(sizeof(LN));
   pre->next=p;
   p->next=NULL;
   p->data=ch;
   pre=p;
   i++;
   break;
   }
   if(ch=='\n')
      break;
  }
   pre->next=NULL;
  return head;
 }
 int LinkListLength(LN *head)
 {
  ;
  LN *p;
  p=head->next;
  if(p==NULL)
  {
   ;
  }
  else
  {
  while(p->next)
  {
   p=p->next;
   count++;
  }
  return count;
  }
 }
 void SearchData(int i,LN *head)
 {
  LN *p;
  ;
  p=head->next;
  cout<<"输入要查找的节点:";
  cin>>i;
  )
  {
   p=p->next;
   j++;
  }
   if(!p)
  {
   cout<<"该节点不存在!"<<endl;
  }
  else
  {
  cout<<"该节点数据为:"<<p->data<<endl;
  }
 }

 LN *SearchSpecificData(char ch,LN * head)
 {
  LN *p;
  ;
  p=head->next;
  while(p)
  {
   if(p->data==ch)
   {
    cout<<"该数据是链表中第"<<count<<"个数据!"<<endl;
    return p;
    break;
   }
   else
   {
    p=p->next;
    count++;
   }
  }
  if(p==NULL)
  {
   cout<<"链表中不存在该数据!"<<endl;
   return NULL;
  }
 }
 LN *InsertData(int i,LN *head)
 {
  LN *p,*insert;
  ;
  char ch;
  cout<<"输入要插入的数据:";
  cin>>ch;
  cout<<"输入元素插入的位置:";
  cin>>i;
  )
  {
   cout<<"插入错误!"<<endl;
   return NULL;
  }
  )
  {
   insert=(LN *)malloc(sizeof(LN));
   insert->next=head->next;
   head->next=insert;
   insert->data=ch;
   return head;
  }
  else
  {
  p=head->next;
  )
  {
   p=p->next;
   j++;
  }
  insert=(LN *)malloc(sizeof(LN));
  insert->data=ch;
  insert->next=p->next;
  p->next=insert;
  return head;
  }
 }
 LN *DeleteData(int i,LN *head)
 {
  LN *p,*q;
  ;
  cout<<"输入要删除的节点位置:";
  cin>>i;
  if(i>LinkListLength(head))
  {
   cout<<"该节点不存在,删除失败!"<<endl;
   return NULL;
  }

  else
  {
  q=head;
  while(q&&j<i)
  {
   p=q;
   q=q->next;
   j++;
  }

  p->next=q->next;
  free(q);
  return head;
  }
 }
 LN * AddDataToTail(char ch,LN *head)
 {
  LN *p,*add;
  p=head;
  while(p->next)
  {
   p=p->next;
  }
  add=(LN *)malloc(sizeof(LN));
  add->data=ch;
  p->next=add;
  add->next=NULL;
  return head;
 }
 LN * PrintLinkList(LN *head)
 {
  LN *p;
  p=head->next;
  if(p==NULL)
  {
   cout<<"空链表无法打印!"<<endl;
   return NULL;
  }
  else
  {
  while(p->next)
  {
   cout<<p->data<<"-->";
   p=p->next;
  }
  cout<<p->data<<endl;
  return head;
  }
 }
 LN * FindMin(LN * head)
 {
  LN *p,*minptr;
  char min;
  p=head->next;
  minptr=p;
  min=minptr->data;
  while(p!=NULL)
  {
   if(p->data<min)
   {
    minptr=p;
    min=p->data;
   }
   p=p->next;
  }
  return minptr;
 }
 LN * DeleteSpecificData(char ch,LN * head)
 {
  LN *p,*q;
  ;
  q=head->next;
  p=head;
  while(q&&q->data!=ch)
  {
   p=q;
   q=q->next;
  }
  if(q==NULL)
  {
   cout<<"数据不存在,删除失败!"<<endl;
   return NULL;
  }
  else
  {
  p->next=q->next;
  free(q);
  return head;
  }
 }
 LN * ReverseLinkList(LN * head)
 {
  LN *p,*q,*pr;
  p=head->next;
  q=NULL;
  head->next=NULL;
  while(p)
  {
   pr=p->next;
   p->next=q;
   q=p;
   p=pr;
  }
  head->next=q;
  return head;
 }
 /*
 LN *OrderLinkList(LN *head)//链表排序法1
 {
  LN *ptn,*p,*minptr,*head1;
  ptn=(LN *)malloc(sizeof(LN));
  ptn->next=NULL;
  head1=ptn;
  p=head1;
  while(LinkListLength(head)!=0)
  {
   minptr=FindMin(head);
   ptn=(LN *)malloc(sizeof(LN));
   ptn->data=minptr->data;
   ptn->next=NULL;
   if(LinkListLength(head)==1)
   {
    p->next=ptn;
    DeleteSpecificData(minptr->data,head);
        p=p->next;
    free(head);
    break;
   }
   p->next=ptn;
   DeleteSpecificData(minptr->data,head);
   p=p->next;
  }
  return head1;
 }
 */
 LN * OrderLinkList(LN *head)//链表排序法2(冒泡法排序)
 {
  LN *p,*pr;
  char temp;
  p=head->next;
  while(p->next)
  {
   pr=p->next;
   while(pr)
   {
    if(pr->data<p->data)
    {
     temp=p->data;
     p->data=pr->data;
     pr->data=temp;
    }
    pr=pr->next;
   }
   p=p->next;
  }
  return head;
 }
 LN *Clear(LN * head)//清除重复数据
 {
  LN *q,*p,*ptn;
  q=head->next;
  if(q->next==NULL)//链表只有1个数据则直接返回头结点
  {
   return head;
  }
  else//链表含有2个或以上数据则进行以下操作
  {
  p=q->next;

  while(p)
  {
   if(q->data!=p->data)
   {
    q=q->next;
    q->data=p->data;
   }
   p=p->next;
  }
  ptn=q->next;
  while(ptn)
  {
   p=ptn;
   ptn=ptn->next;
   free(p);
  }
  q->next=NULL;
  return head;
  }
 }
 LN *EmptyLinkList(LN * head)//(清空)释放除头节点外的所有节点,释放后仍可以进行链表的各种操作
 {
  LN *p,*q;
  p=head->next;
  head->next=NULL;
  while(p)
  {
   q=p;
   p=p->next;
   free(q);
  }
  return head;
 }
 void DestroyLinkList(LN *head)//(销毁)链表不再存在,释放了所有节点
 {
  EmptyLinkList(head);
  free(head);
 }

 LN *GetTogether(LN *head,LN *head1)//将一个链表中数据全部追加到另一个链表尾部
 {
  LN *p1;
  p1=head1->next;
  while(p1)
  {
   AddDataToTail(p1->data,head);
   p1=p1->next;
  }
  DestroyLinkList(head1);
  return head;
 }

 int main()
 {
  ;
  int choice;
  char ch;
  LN *head,*head1,*result;
  head=CreateLinkList();
  if(head->next!=NULL)
  {
   cout<<"单链表head创建成功!"<<endl;
  }
  else
  {
   cout<<"创建了空链表head!"<<endl;
  }
  )
  {
      system("pause");
   system("cls");
  cout<<"1.查找指定节点数据"<<endl;
  cout<<"2.查找指定数据"<<endl;
  cout<<"3.查找最小数据"<<endl;
  cout<<"4.插入数据"<<endl;
  cout<<"5.追加数据"<<endl;
  cout<<"6.删除指定节点数据"<<endl;
  cout<<"7.删除指定数据"<<endl;
  cout<<"8.链表反转"<<endl;
  cout<<"9.链表排序(非递减)"<<endl;
  cout<<"10.合并两个链表(非递减)"<<endl;
  cout<<"11.链表长度"<<endl;
  cout<<"12.打印链表"<<endl;
  cout<<"13.清空链表"<<endl;
  cout<<"14.清除重复数据"<<endl;
  cout<<"0.退出程序"<<endl;
  cout<<"请选择操作:";
  cin>>choice;
  switch(choice)
  {
  : SearchData(n,head);break;
  :cout<<"输入待查找数据:";cin>>ch;SearchSpecificData(ch,head);break;
  :result=FindMin(head);cout<<"最小数据:"<<result->data<<endl;break;
  : result=InsertData(n,head);
   if(result)
   {
          cout<<"数据插入成功!"<<endl;
   }break;
  : cout<<"输入要追加的数据:"<<endl;cin>>ch;AddDataToTail(ch,head);cout<<"数据追加成功!"<<endl;break;
  : result=DeleteData(n,head);
   if(result)
   {
    cout<<"数据删除成功!"<<endl;
   }break;
   :cout<<"输入要删除的数据:"<<endl;cin>>ch;result=DeleteSpecificData(ch,head);
   if(result)
   {
    cout<<"该数据删除成功!"<<endl;
   }break;
  :cout<<"反转后链表为:";result=ReverseLinkList(head);PrintLinkList(result);break;
  :cout<<"链表按非递减排列:";result=OrderLinkList(head);PrintLinkList(result);break;
  :cin.get();head1=CreateLinkList();
   if(head1->next!=NULL)
  {
   cout<<"单链表head1创建成功!"<<endl;
  }
  else
  {
   cout<<"创建了空链表head1!"<<endl;
  }
  head=GetTogether(head,head1);
  head=OrderLinkList(head);if(head->next){cout<<"合并后链表为:";}
  PrintLinkList(head);break;
  : cout<<"链表长度为:"<<LinkListLength(head)<<endl;break;
  :if(head->next){cout<<"链表为:";}PrintLinkList(head);break;
  :head=EmptyLinkList(head);cout<<"链表已清空!"<<endl;break;
  :head=Clear(head);cout<<"重复数据已清除!"<<endl;break;
  :DestroyLinkList(head);exit();
  default:cout<<"输入错误!"<<endl;break;
  }
  }
  ;
 }

若有不足欢迎指正;若有疑问鄙人也乐于解答,欢迎留言或QQ加群!

欢迎加入QQ群:735472015,群内有VC,MFC,win32API,批处理,python学习资料干货喔

上一篇:Linux下的文件及文件后缀名


下一篇:Unity3d webplayer获取url参数