c++實作連結清單

之前在學c的時候以c的版本謝了有關連結清單的最基礎的幾個函數，最近在學習C++，是以，，，哈哈就用另一種版本再次呈現給大家；

感覺c++好像寫起來比較簡單一些。因為它有結構體，是以沒有那麼繁瑣；

cpp.h

#pragma once

#include<iostream>

using namespace std;

typedef int DataType;

 struct Node

{

DataType _data;

struct Node * _next;

Node(const DataType &d)

:_data(d)

,_next(NULL)

}

};

 class Slist

 {

friend ostream & operator<<(ostream &os,Slist &s);

 public:

//構造連結清單

Slist()

:_head(NULL)

,_tail(NULL)

~Slist()

if(_head==NULL)

return ;

Node *cur=_head;

while(cur!=NULL)

Node *del=cur;

cur=cur->_next;

delete del;

delete cur;

_head=NULL;

_tail=NULL;

Slist(const Slist &s)

while(cur)

pushback(cur->_data);

void pushback(const DataType &d);

void popback();

void pushfront(const DataType &d);

void popfront();

//尋找連結清單中某個節點

Node *Find(const DataType &d);

void Insert(Node* pos,const DataType &d);

void Reverse();

void sort();

//合并兩個有序單連結清單。。有一點問題

Node* Merge(Slist slist1,Slist slist2);

void Remove(const DataType &d);

void RemoveAll(const DataType &d);

//删除連結清單中倒數第k個節點

void Delk(int k);

//在指定節點後邊插入一個節點

void InsertFrontNode(Node* pos,const DataType &d);

//尋找連結清單的中間節點

Node* FindMidNode();

//求連結清單的長度

int GetlistLength();

//銷毀連結清單

void Destory();

//判斷連結清單是否帶環

Node* Checkcycle();

//擷取環的入口節點

Node* GetcycleEntryNode(Node* meetnode);

 private:

Node *_head;

Node *_tail;

 };

test.c

#include"Slist.h"

#include<assert.h>

//1<<輸出運算符的重載

ostream& operator<<(ostream &os,Slist &s)

if(s._head==NULL)

return os;

Node *cur=s._head;

os<<cur->_data<<"->";

os<<"over"<<endl;

 }

//2頭插法建立單連結清單

 void Slist::pushback(const DataType &d)

 Node * newNode=new Node(d);

_head=newNode;

_tail=_head;

else

_tail->_next=newNode;

_tail=newNode;

 //3尾删除法單連結清單

void  Slist::popback()

//沒有節點

if(_head=NULL)

return;

//有一個節點

if(_head==_tail)

delete _head;

//有好多個節點

while(cur->_next!=_tail)

delete _tail;

_tail=cur;

_tail->_next=NULL;

//3頭插法建立單連結清單

void  Slist::pushfront(const DataType &d)

     Node* newNode=new Node(d);

newNode->_next=_head;

//4頭删

void  Slist::popfront()

//如果連結清單為空則直接傳回

  return;

//否則挨個删除

Node *del=_head;

_head=_head->_next;

//5在單連結清單中查找某個資料的節點

Node*  Slist::Find(const DataType &d)

if(_head==NULL||_head->_next==NULL)

return _head;

if(cur->_data==d)

   return cur;

   cur=cur->_next;

    return NULL;

// 6在目前節點後邊插入某個資料

void  Slist::Insert(Node* pos,const DataType &d)

Node* newNode=new Node(d);

if(pos==_tail)

newNode->_next=pos->_next;

 pos->_next=newNode;

//7翻轉單連結清單

void Slist::Reverse()

Node *th=NULL;

Node *q =NULL;

Node *p=_head;

   return;

while(p)

   q=p;

p=p->_next;

q->_next=th;

th=q;

_head=th;

//8對單連結清單進行排序

 void Slist:: sort()

Node* end=NULL;

Node* cur=_head;

     if(cur==NULL||cur->_next==NULL)

while(cur->_next!=end)

while(cur!=NULL&&cur->_next!=end)

      if(cur->_data>cur->_next->_data)

  {

  DataType tmp=cur->_data;

  cur->_data=cur->_next->_data;

  cur->_next->_data=tmp;

  }

      cur=cur->_next;

    end=cur;

cur=_head;

//9合并兩個有序單連結清單

Node* Merge(Node* _head1,Node* _head2)

  Node *newHead=NULL;

 if(_head1==_head2)

 return _head1;

 if(_head1==NULL&&_head2!=NULL)

   return _head2;

if(_head1!=NULL&&_head2==NULL)

   return _head1;

if(_head1->_data<_head2->_data)

 newHead=_head1;

_head1=_head1->_next;

newHead=_head2;

_head2=_head2->_next;

Node* cur=newHead;

while(_head1&&_head2)

  cur->_next=_head1;

 _head1=_head1->_next;

cur->_next=_head2;

if(_head1)

cur->_next=_head1;

return newHead;

//10删除連結清單中的某個值為d的節點

void  Slist::Remove(const DataType &d)

Node * del=NULL;

Node *prve=NULL;

if(cur==NULL)

{//若連結清單為空則直接傳回

 return;

//若cur不為空 則一直往下走

del=cur;

//若要找的為第一個節點

if(cur=_head)

prve->_next=cur->_next;

break;

prve=cur;

//11删除連結清單中的所有值為d的節點

void  Slist::RemoveAll(const DataType &d)

 Node *cur=_head;

cur=prve->_next;

//12删除連結清單中倒數第k個節點

void Slist::Delk(int k)

assert(k>1);

Node* p1=_head;

Node* p2=_head;

while(--k)

p1=_head->_next;

while(p1->_next)

p1=p1->_next;

p2=p2->_next;

Node* del=p2->_next;

p2->_data=p2->_next->_data;

p2->_next=p2->_next->_next;

//13在目前連結清單前插入一個資料

void Slist::InsertFrontNode(Node* pos,const DataType &d)

Node * newNode=new Node(d);

pos->_next=newNode;

DataType tmp=pos->_data;

pos->_data=pos->_next->_data;

pos->_next->_data=tmp;

//14尋找連結清單的中間節點

Node* Slist:: FindMidNode()

  Node *fast=_head;

  Node *slow=_head;

  if(fast==NULL)

     return NULL;

  if(fast!=NULL&&fast->_next!=NULL)

  fast=fast->_next->_next;

  slow=slow->_next;

    return slow;

//15求連結清單的長度

int  Slist:: GetlistLength()

int count=0;

count++;

   return count;

void Slist::Destory()

 Node* cur=_head;

 Node* del=NULL;

 if(_head=NULL)

 else

 while(cur)

del=NULL;

Node* Slist::Checkcycle()

  Node* fast=_head;

  Node*slow=_head;

  while(fast&&fast->_next)

if(fast==slow)

return slow;

  return NULL;

Node* Slist::GetcycleEntryNode(Node* meetnode)

 Node* entry=_head;

 Node* meet=meetnode;

 while(entry!=meet)

 entry=entry->_next;

 meet=meet->_next;

 return entry;

void test1()

Slist slist1;

slist1.pushback(1);

slist1.pushback(2);

slist1.pushback(3);

slist1.pushback(4);

slist1.Destory();

cout<<slist1<<endl;

    void test2()

slist1.pushfront(1);

slist1.pushfront(2);

slist1.pushfront(4);

slist1.RemoveAll(4);

void test3()

slist1.pushfront(3);

slist1.Reverse();

void test4()

slist1.pushfront(5);

slist1.pushfront(7);

slist1.Delk(2);

cout<<slist1;

void test5()

Node* cur=slist1.Find(1);

slist1.InsertFrontNode(cur,2);

void test6()

slist1.sort();

void test8()

int count=slist1.GetlistLength();

cout<<count;

void test9()

int i=0;

for(i=1;i<8;i++)

slist1.pushfront(i);

Node* end=slist1.Find(8);

Node* cur=slist1.Find(2);

end->_next=cur;

cur=slist1.Checkcycle();

if(cur!=NULL)

cout<<cur;

int main()

test9();

system("pause");

return 0;