之前在学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;