这是基于链表的线性表：
#ifndef LINKED_LIST
#define LINKED_LIST
#include<iostream.h>
#include<stdlib.h>
#include<assert.h>
//////////////////////////////////////////////////////////
//链表结点结构LinkNode的定义
//////////////////////////////////////////////////////////
template <class T>
struct LinkNode
{
//数据域
T data;
//指针域
LinkNode<T>* link;
//本结点的访问次数
int fre;
//结点构造函数,只用指针初始化
LinkNode(LinkNode<T>* ptr=NULL)
{
//用参数初始化
link=ptr;
};
//结点构造函数,用数据和指针初始化
LinkNode(const T& item,LinkNode<T>* ptr=NULL)
{
//初始化数据
data=item;
//初始化指针
link=ptr;
//访问次数
fre=0;
};
};
//////////////////////////////////////////LinkNode结构结束
//////////////////////////////////////////////////////////
//链表类List的定义
//////////////////////////////////////////////////////////
template<class T>
class List//:public LinearList<T>
{
protected:
LinkNode<T>* first;
public:
//构造函数
List()
{
//初始化头指针，并自动调用
//结点的构造函数
first=new LinkNode<T>;
};
//构造函数
List(const T& x)
{
//动态分配一个带参数的结点
first=new LinkNode<T>(x);
};
//复制构造函数
List(List<T>& L);
//析构函数
~List()
{
//即释放链表所占用的所有内存
//链表游标
LinkNode<T>* ptr=first;
//指向要删除的结点
LinkNode<T>* del;
while(ptr!=NULL)
{
del=ptr;
ptr=ptr->link;
delete del;
}
//cout<<"链表的内存已经完全释放!"<<endl;
};
LinkNode<T>* getHead()const
{
return first;
};
//将链表置空
void makeEmpty();
//得到链表的长度
int Length()const;
//得到链表的尾部的结点
LinkNode<T>* getRear(LinkNode<T>*);
//设置附加头结点的地址
void setHead(LinkNode<T>* p)
{first=p;};
//搜索含数据元素x的结点，返回接指针
LinkNode<T>* Search(T x);
//用递归的方法搜索具有值x的结点指针
LinkNode<T>* search(LinkNode<T>*,T x);
//定位函数
LinkNode<T>* Locate(int i);
//获取指定位置上的数据
T* getData(int i);
//用x来修改第i个元素上的值
void setData(int i,T& x);
//在第i个元素后插入元素x
bool Insert(int i,T& x);
//删除第i个元素，并通过x返回被删除的值
bool Remove(int i,T& x);
//判断链表是否为空
bool IsEmpty()const
{
if(first->link==NULL)
return true;
else
return false;
};
//判断链表是否为满
bool IsFull()const
{
//链表的长度不受限制
return false;
};
//链表元素的输出
void output();
//从头部插入元素建立链表
void inputFront(T);
//从尾部插入元素建立链表
void inputRear(T);
//重载赋值运算符
LinkNode<T>& operator=(LinkNode<T>& L);
//把链表中的所有指针逆转
void reverseList();
//把已经地址的结点挂入当前链表的尾部
void hangRear(LinkNode<T>* ptr);
//字符数据的分离
void charSelect(List<T>&,List<T>&,List<T>&);
//删除介于[min,max]区间上的元素
void removeList(T,T);
//取得已经指针指向的结点的序号
int getNo(LinkNode<T>*);
//依次显示每个结点的访问次数
void displayFre();
//按照访问的次数fre对链表中的结点排序(从大到小)
void SortFre();
//通过堆栈来逆转链表的所有结点
void revList();
};
////////////////////////////////////////List链表类声明结束
//////////////////////////////////////////////////////////
//List()复制构造函数
//////////////////////////////////////////////////////////
template<class T>
List<T>::List(List<T>& L)
{
//用于存放要复制的值
T value;
//指向新结点
LinkNode<T>* newNode;
//新建一个附加头结点
first=new LinkNode<T>(0);
if(first==NULL)
{
cerr<<"内存分配失败!"<<endl;
exit(1);
};
//复制每个元素的内容，得到被复制链表的附加头结点地址
LinkNode<T>* srcptr=L.getHead();
//源链表
LinkNode<T>* destptr=first;
//目的链表
//逐个结点复制
while(srcptr!=NULL)
{
//从附加头结点后的那个结点开始
//取出源链表的数据，放入value
value=srcptr->data;
//创建一个新结点，用value初始化，并以游标指向它
newNode=new LinkNode<T>(value);
//把新结点挂到目的结点的尾部
destptr->link=newNode;
//目的链表指针往后推进一格
destptr=newNode;
//源链表指针往后推进一格
srcptr=srcptr->link;
};
destptr->link=NULL;
};
/////////////////////////////////////////复制构造函数结束
/////////////////////////////////////////////////////////
//将链表置空的makeEmpty()函数
/////////////////////////////////////////////////////////
template<class T>
void List<T>::makeEmpty()
{
//一个结点指针
LinkNode<T>* q;
//当链表不为空时，删去所有数据结点
while(first->link!=NULL)
{
//获得第一个数据结点地址
q=first->link;
//摘下第一个数据结点
first->link=q->link;
//删除摘下的结点
delete q;
};
};
//////////////////////////////////////makeEmpty()函数结束
/////////////////////////////////////////////////////////
//计算链表的长度Length()函数
/////////////////////////////////////////////////////////
template<class T>
int List<T>::Length()const
{
//链表游标，指向第一个数据结点
LinkNode<T>* ptr=first->link;
//计数器
int count=0;
//扫描链表所有结点
while(ptr!=NULL)
{
count++;
//指针向后推一格
ptr=ptr->link;
}
return count;
};
/////////////////////////////////////////Length()函数结束
/////////////////////////////////////////////////////////
//getRear()函数 得到链表的尾指针
/////////////////////////////////////////////////////////
template<class T>
LinkNode<T>* List<T>::getRear(LinkNode<T>* ptr)
{
if(ptr==NULL)
//如果链表为空
return NULL;
else
//递归结束条件
if(ptr->link==NULL)
return ptr;
else
//递归的过程
return getRear(ptr->link);
};
////////////////////////////////////////getRear()函数结束
/////////////////////////////////////////////////////////
//Search()函数
/////////////////////////////////////////////////////////
template<class T>
LinkNode<T>* List<T>::Search(T x)
{
//定义一个链表游标
LinkNode<T>* ptr=first->link;
while(ptr!=NULL)
{
//匹配
if(ptr->data==x)
break;
else
//游标向后推进一格
ptr=ptr->link;
};
//返回指针，如果没找到ptr自动为空
return ptr;
};
///////////////////Search()函数结束
/////////////////////////////////////////////////////////
//search()函数 以递归的方法
//搜索具有值x的结点指针
/////////////////////////////////////////////////////////
template<class T>
LinkNode<T>* List<T>::search(LinkNode<T>* f,T x)
{
if(f==NULL)
{
//如果链表为空
cout<<"链表为空!"<<endl;
return NULL;
}
else if(f->link==NULL)
{
//没有找到停止递归
cout<<"没有找到!"<<endl;
return NULL;
}
else if(f->data==x)
return f;
else
{
return search(f->link,x);
};
};
/////////////////////////////////////////search()函数结束
/////////////////////////////////////////////////////////
//Locate()函数
/////////////////////////////////////////////////////////
template<class T>
LinkNode<T>* List<T>::Locate(int i)
{
//定义一个链表游标
LinkNode<T>* ptr=first;
//如果i<0或者超出链表长度，则返回NULL
//用this指针指代当前对象
//i=0表示指向附加头结点
if(i<0||i>this->Length())
return NULL;
for(int x=1;x<=i;x++)
{
//游标向后推进一格
ptr=ptr->link;
}
//访问次数加一
ptr->fre++;
//把访问次数多的结点望头结点的位置调整
return ptr;
};
/////////////////////////////////////////Locate()函数结束
/////////////////////////////////////////////////////////
//getData()函数
/////////////////////////////////////////////////////////
template<class T>
T* List<T>::getData(int i)
{
//i越界的情形，第0个结点不含数据，不含在内
if(i<=0||i>Length())
return NULL;
//不越界
LinkNode<T>* ptr=Locate(i);
if(ptr==NULL)
return NULL;
else
//返回数据域的地址
return &ptr->data;
};
////////////////////////////////////////getData()函数结束
/////////////////////////////////////////////////////////
//setData()函数
/////////////////////////////////////////////////////////
template<class T>
void List<T>::setData(int i,T& x)
{
//第0个结点数据不能修改，所以不含在内
if(i<=0||i>Length())
return;
//指向要修改的结点
LinkNode<T>* current=Locate(i);
if(current==NULL)
return;
else
current->data=x;
};
////////////////////////////////////////////setData()函数
/////////////////////////////////////////////////////////
//Insert()函数
/////////////////////////////////////////////////////////
template<class T>
bool List<T>::Insert(int i,T& x)
{
//将新元素x插入在第i个元素之后
//指向要插入元素前一个结点的指针
LinkNode<T>* current=Locate(i);
//定位不成功
if(current==NULL)
return false;
//为新数据创建一个新结点
LinkNode<T>* newNode=new LinkNode<T>(x);
if(newNode==NULL)
{
cerr<<"内存分配失败!"<<endl;
exit(1);
}
//以下执行插入操作
newNode->link=current->link;
current->link=newNode;
//插入成功
return true;
};
/////////////////////////////////////////Insert()函数结束
/////////////////////////////////////////////////////////
//Remove()函数
/////////////////////////////////////////////////////////
template<class T>
bool List<T>::Remove(int i,T& x)
{
//越界处理
if(i<=0||i>Length())
return false;
//得到一个要删除结点的前一个结点的指针
LinkNode<T>* current=Locate(i-1);
//删除失败
if(current==NULL||current->link==NULL)
return false;
//del用于指向被摘下的结点
LinkNode<T>* del=current->link;
current->link=del->link;
x=del->data;
delete del;
//删除成功
return true;
};
/////////////////////////////////////////Remove()函数结束
/////////////////////////////////////////////////////////
//output()函数
/////////////////////////////////////////////////////////
template<class T>
void List<T>::output()
{
//定义游标
LinkNode<T>* current=first->link;
if(current==NULL)
{
cout<<"链表为空!"<<endl;
return;
}
else
{
while(current!=NULL)
{
//依次显示每个结点数据域的内容
cout<<current->data<<" ";
current=current->link;
}
}
};
/////////////////////////////////////////output()函数结束
/////////////////////////////////////////////////////////
//重载赋值运算符
/////////////////////////////////////////////////////////
template<class T>
LinkNode<T>& List<T>::operator =(LinkNode<T>& L)
{
//把对象参数L复制到当前对象中去
T value;
//得到源串首地址和新建目的串指针
LinkNode<T>* srcptr=L.getHead();
LinkNode<T>* destptr=first=new LinkNode<T>;
//逐个结点复制
while(srcptr!=NULL)
{
//得到原串结点的数据
value=src->link->data;
//新建一个结点，并value初始化
destptr->link=new LinkNode<T>(value);
//目的串和源串指针分别向后推进一格
srcptr=srcptr->link;
destptr=destptr->link;
};
destptr->link=NULL;
//返回当前对象的引用
return *this;
};
/////////////////////////////////////////////////重载结束
/////////////////////////////////////////////////////////
//inputFront()函数
/////////////////////////////////////////////////////////
template<class T>
void List<T>::inputFront(T endTag)
{
//endTag为结束符号
//新结点的指针
LinkNode<T>* newNode;
//要插入的值
T val;
//新建一个附加头结点
//first->link默认为NULL
//其实在链表结点的构造函数已经分配过了
//以下代码如果加上则只能新建链表而不能追加元素
/*first=new LinkNode<T>;
if(first==NULL)
{
cerr<<"内存分配出错!"<<endl;
exit(1);
};*/
//输入值
cout<<"请输入链表的的数据内容:"<<endl;
cin>>val;
while(val!=endTag)
{
//创建新结点
newNode=new LinkNode<T>(val);
if(newNode==NULL)
{
cerr<<"内存分配出错!"<<endl;
exit(1);
};
//把新结点插入到链表的头部
newNode->link=first->link;
first->link=newNode;
//输入下一个结点的数据值
cin>>val;
};
};
//////////////////////////////////////////input()函数结束
/////////////////////////////////////////////////////////
//inputRear()函数
/////////////////////////////////////////////////////////
template<class T>
void List<T>::inputRear(T endTag)
{
//新结点的指针
LinkNode<T>* newNode;
//指向链表尾部的指针
LinkNode<T>* last;
//要插入的值
T val;
//新建一个附加头结点
//以下代码如果加上则只能新建链表而不能追加元素
/*first=new
LinkNode<T>;
if(first==NULL)
{
cerr<<"内存分配出错!"<<endl;
exit(1);
};*/
cout<<"请输入链表的数据内容:"<<endl;
cin>>val;
//让last指向链表的最后一个结点
last=first;
while(last->link!=NULL)
{
//指针向后推进一格
last=last->link;
};
while(val!=endTag)
{
//新建一个结点，让newNode指向它
//用val值进行初始化
newNode=new LinkNode<T>(val);
if(newNode==NULL)
{
cerr<<"内存分配出错!"<<endl;
exit(1);
};
//把新建的结点插入到链表的尾部
last->link=newNode;
last=newNode;
//输入下个结点的数据
cin>>val;
};
//把最后一个结点的指针置为空
last->link=NULL;
};
//////////////////////////////////////inputRear()函数结束
/////////////////////////////////////////////////////////
//reverseList()函数
//逆转单链表
/////////////////////////////////////////////////////////
template<class T>
void List<T>::reverseList()
{
if(first==NULL)
{
cout<<"链表为空!"<<endl;
exit(1);
};
if(first->link==NULL)
{
cout<<"链表中只有一个元素!";
exit(1);
}
LinkNode<T>* pre;
LinkNode<T>* p;
LinkNode<T>* next;
pre=first;
p=first->link;
next=first->link;
while(p!=NULL)
{
//指向断点后的第二个结点
next=next->link;
//让断点后的第一个结点的指针域指向
//断点前的最后一个结点
p->link=pre;
//pre向后推进一格
pre=p;
//p和next指向断点后的第一个结点
p=next;
}
//把逆转后的尾结点(即原来的头结点)
//的指针域设为NULL
first->link=NULL;
//显示逆转后的的链表的所有元素
//因为本链表在逆转前是含有附加头结点的、
//所以反向遍历的时候可以不用遍历附加头结点
while(pre->link!=NULL)
{
cout<<pre->data<<" ";
pre=pre->link;
}
cout<<endl;
}
////////////////////////////////////reverseList()函数结束
/////////////////////////////////////////////////////////
//hangRear()函数
//把已知地址的结点挂入当前结点
/////////////////////////////////////////////////////////
template<class T>
void List<T>::hangRear(LinkNode<T>* ptr)
{
LinkNode<T>* rear=getHead();
//首先找到当前链表的尾指针
while(rear->link!=NULL)
{
//指针向后推进
rear=rear->link;
};
//把结点挂入rear指针
rear->link=ptr;
};
///////////////////////////////////////hangRear()函数结束
/////////////////////////////////////////////////////////
//getNo()函数
得到已知的指针所
//向的结点在当前链表中的序列号
/////////////////////////////////////////////////////////
template<class T>
int List<T>::getNo(LinkNode<T>* ptr)
{
//游标指针
LinkNode<T>* p=getHead();
//计数器
int count=0;
while(p->link!=NULL && p!=ptr)
{
count++;
p=p->link;
}
return count;
};
//////////////////////////////////////////getNo()函数结束
/////////////////////////////////////////////////////////
//displayFre()公有成员函数
显示所有结点的访问次数
/////////////////////////////////////////////////////////
template<class T>
void List<T>::displayFre()
{
if(IsEmpty())
cout<<"链表为空!"<<endl;
else
{
LinkNode<T>* ptr=first->link;
//游标指针
int i=1;
//结点序号
while(ptr!=NULL)
{
cout<<i<<" frequency:"<<ptr->fre<<endl;
ptr=ptr->link;
i++;
}
}
}
/////////////////////////////////////displayFre()函数结束
/////////////////////////////////////////////////////////
//SortFre()公有成员函数
对结点按Fre从大到小排序
/////////////////////////////////////////////////////////
template<class T>
void List<T>::SortFre()
{
//开辟一个指针数组存放每个结点的指针
LinkNode<T>** Point=new LinkNode<T>*[Length()];
//断言内存分配成功
assert(Point);
//把结点的地址依次放入Point中去
LinkNode<T>* ptr=first->link;
//游标指针
int i=0;
//序号计数器
while(ptr!=NULL)
{
Point[i]=ptr;
i++;
ptr=ptr->link;
}
//对Point数组里的指针按照fre降序排列
int j,k;
LinkNode<T>* tempt;
for(i=0;i<Length()-1;i++)
{
k=i;
for(j=i+1;j<Length();j++)
if(Point[j]->fre>Point[k]->fre)
k=j;
if(i!=k)
{
tempt=Point[i];
Point[i]=Point[k];
Point[k]=tempt;
}
}
//把指针重新连接
int Len=Length();
first->link=Point[0];
for(i=1;i<Len-1;i++)
{
Point[i-1]->link=Point[i];
}
Point[Len-1]=NULL;
};
////////////////////////////////////////SortFre()函数结束
#endif
2008-09-25 15:52
