登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

单链表  

2006-02-23 21:54:42|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

功能描述:此类是简单的实现单链表的操作

作者:秒大刀

完成时间:2005-03-12

头文件    linklist.h

实现文件  linklist.cpp

测试文件  linkmain.cpp


--------------------------------------------------------------------------------

//头文件linklist.h
//单循环链表的声明文件
#ifndef LINKLIST_H
#define LINKLIST_H

template<class ElemType>
class LinkList
{
struct LNode //单链表中结点的类型
{
ElemType data; //值域
LNode* next; //指针域
};
//////////////////////////////////类型定义
typedef typename const ElemType& crElemType;
typedef typename ElemType& rElemType;

typedef typename LinkList* pLinkList;
typedef typename LinkList& rLinkList;
typedef typename const LinkList* cpLinkList;
typedef typename const LinkList& crLinkList;
typedef typename const LinkList cLinkList;
//////////////////////////////////
private:
LNode* head;
public:
LinkList();//构造函数
LinkList(crLinkList HL);//复制构造函数
~LinkList();//析构函数
public:
unsigned Size(); //求单链表长度
void Clear();//清空单链表
bool Empty();//检查单链表是否为空
bool Find(rElemType item);//从单链表中查找元素
void Insert(crElemType item, const int mark);//向单链表插入元素
bool Erase(rElemType item, const int mark);//从单链表中删除元素
bool Set(crElemType item);//更新单链表中的给定元素
ElemType Get(const unsigned pos);//返回单链表中指定序号的结点值
public:
void Traverse();//遍历单链表
void OrderOutput(int mark);//对单链表进行有序输出
};
/////////////////////////
#ifndef LINKLIST_CPP
#include "LinkList.cpp"
#endif //LINKLIST_CPP
/////////////////////////
#endif //LINKLIST_H


--------------------------------------------------------------------------------

//单循环链表的实现文件linklist.cpp

//#include<iomanip.h>
#ifndef LINKLIST_CPP
#define LINKLIST_CPP
#include<cstdlib>
#ifndef LINKLIST_H
#include "linklist.h"
#endif //LINKLIST_H


////////////////////////////////
template <class ElemType>
LinkList<ElemType>::LinkList()
{
head=NULL;
}
//复制构造函数
template<class ElemType>
LinkList<ElemType>::LinkList(crLinkList HL)
{
if(HL.head==NULL)
{
head=NULL;
return;
}
//以下为非空链表的拷贝
head=new LNode;
head->data=HL.head->data;
LNode *p, *q=head;
for(p=HL.head->next; p; p=p->next)
{
q=q->next=new LNode;
q->data=p->data;
}
q->next=NULL;
}

//析构函数
template <class ElemType>
LinkList<ElemType>::~LinkList()
{
Clear();
}
//清空单链表
template <class ElemType>
void LinkList<ElemType>::Clear()
{
LNode *cp, *np;
cp=head;
while(cp!=NULL)
{
np=cp->next;
delete cp;
cp=np;
}
head=NULL;
}
//求单链表长度
template<class ElemType>
unsigned LinkList<ElemType>::Size()
{
LNode* p=head;
unsigned i=0;
while(p!=NULL)
{
i++;
p=p->next;
}
return i;
}

//检查单链表是否为空
template<class ElemType>
bool LinkList<ElemType>::Empty()
{
return (head==NULL);
}

//返回单链表中指定序号的结点值
template<class ElemType>
ElemType LinkList<ElemType>::Get(const unsigned pos)
{
if(pos<1)
{
cerr<<"pos is out range!"<<endl;
cin.get();
exit(1);
}
LNode* p=head;
unsigned i=0;
while(p!=NULL)
{
i++;
if(i==pos)
break;
p=p->next;
}
if(p!=NULL)
return p->data;//正常出口
else
{
cerr<<"pos is out range!"<<endl;
exit(1);
}
}

//遍历单链表
template<class ElemType>
void LinkList<ElemType>::Traverse()
{
LNode* p=head;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

//从单链表中查找元素
template <class ElemType>
bool LinkList<ElemType>::Find(rElemType item)
{
LNode* p=head;
while(p!=NULL)
{
if(p->data==item)
{
item=p->data;
return true;
}
else
p=p->next;
}
return false;
}

//更新单链表中的给定元素
template <class ElemType>
bool LinkList<ElemType>::Set(crElemType item)
{
LNode* p=head;
while(p!=NULL) //查找元素
if(p->data==item)
break;
else
p=p->next;
if(p==NULL)
return false;
else { //更新元素
p->data=item;
return true;
}
}

//向单链表插入元素
template<class ElemType>
void LinkList<ElemType>::Insert(crElemType item, const int mark)
{
//建立一个值为item的新结点
LNode* newptr;
newptr=new LNode;
newptr->data=item;
//向表头插入结点
if(mark>0)
{
newptr->next=head;
head=newptr;
}
//向表尾插入结点
else if(mark<0)
{
if(head==NULL)
{
newptr->next=NULL;
head=newptr;

}
else
{
LNode* p=head;
while(p->next!=NULL)
p=p->next;
p->next=newptr;
newptr->next=NULL;
}
}
//插入到合适位置
else
{
LNode* cp;
LNode* ap;
ap=NULL; cp=head;
while(cp!=NULL)
{
if(item<cp->data)
break;
else
{
ap=cp;
cp=cp->next;
}
}
if(ap==NULL)
{
newptr->next=head;
head=newptr;
}
else
{
newptr->next=cp;
ap->next=newptr;
}
}
}

//从单链表中删除元素
template<class ElemType>
bool LinkList<ElemType>::Erase(rElemType item, const int mark)
{
if(head==NULL)
return false;
//删除表头结点
if(mark>0)
{
LNode* p=head;
item=head->data;
head=head->next;
delete p;
return true;
}
//删除表尾结点
else if(mark<0)
{
LNode *cp=head, *ap=NULL;
while(cp->next!=NULL)
{
ap=cp;
cp=cp->next;
}
if(ap==NULL)
head=NULL;
else
ap->next=cp->next;
item=cp->data;
delete cp;
return true;
}
//删除值为item结点
else
{
LNode *cp=head, *ap=NULL;
while(cp!=NULL)
if(cp->data==item)
break;
else
{
ap=cp;
cp=cp->next;
}
if(cp==NULL)
return false;
else
{
if(ap==NULL)
head=head->next;
else
ap->next=cp->next;
item=cp->data;
delete cp;
return true;
}
}
}

//对单链表进行有序输出
template<class ElemType>
void LinkList<ElemType>::OrderOutput(const int mark)
{
if(head==NULL)
{
cout<<"链表为空!"<<endl;
return;
}
//建立新的单链有序表的表头结点
LinkList x;
x.head=new LNode; //x.head为新建有序表的表头指针
x.head->data=head->data; x.head->next=NULL;
//根据head单链表生成x.head单链有序表
for(LNode* p=head->next; p; p=p->next)
{
LNode* q=new LNode;
q->data=p->data;
LNode *cp=x.head, *ap=NULL;
//为向x单链表插入q结点而顺序查找合适位置
while(cp)
{
if(mark==1)
{
if(q->data<cp->data)
break;
else
{
ap=cp;
cp=cp->next;
}
}
else
{
if(cp->data<q->data)
break;
else
{
ap=cp;
cp=cp->next;
}
}
}
//把q结点插入h有序单链表中
if(ap==NULL)
{
q->next=x.head;
x.head=q;
}
else {
q->next=cp;
ap->next=q;
}
}
//遍历x有序单链表
x.Traverse();
}
#endif //LINKLIST_CPP
 


--------------------------------------------------------------------------------

//单循环链表LinkList类的测试文件linkmain.cpp

//#include<iomanip.h>
#include "linklist.h"
#include<iostream>
using namespace std ;
void main()
{
LinkList<int> a;
int i;
int x;
//依次向单链表a表尾插入5个整数结点
cout<<"从键盘输入5个整数:";
for(i=0; i<5; i++)
{
cin>>x;
a.Insert(x,-1);
}
//依次向单链表a表头插入2个整数结点
cout<<"从键盘输入2个整数";
cin>>x;
a.Insert(x,1);
cin>>x;
a.Insert(x,1);
//按不同次序遍历输出单链表a
a.Traverse();
a.OrderOutput(1);
a.OrderOutput(0);
//从单链表a中查找一个给定的整数
cout<<"从键盘上输入一个待查整数:";
cin>>x;
if(a.Find(x))
cout<<x<<" 查找成功!"<<endl;
else
cout<<"查找失败!"<<endl;
//把单链表a中的所有元素依次有序插入到一个新单链表b中
LinkList<int> b;
int k=a.Size();
for(i=1; i<=k; i++)
b.Insert(a.Get(i),0);
//输出单链表b
b.Traverse();
//从单链表a中分别删除表头、表尾、给定值结点
if(a.Erase(x,1))
cout<<"Delete success!"<<endl;
else
cout<<"Delete fail!"<<endl;
if(a.Erase(x,-1))

cout<<"Delete success!"<<endl;
else
cout<<"Delete fail!"<<endl;

cout<<"从键盘上输入一个待删除的整数:";
cin>>x;

if(a.Erase(x,0))
cout<<"Delete success!"<<endl;
else
cout<<"Delete fail!"<<endl;
//输出单链表a
a.Traverse();
}
//错误的原因:没有做模板的特化;no
//错误原因,应该包含cpp文件而不是h文件

  评论这张
 
阅读(1399)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018