打开APP
未登录
开通VIP,畅享免费电子书等14项超值服
开通VIP
首页
好书
留言交流
下载APP
联系客服
C 模版编程——单链表的实现
Fredanf
>《数据结构与算法》
2012.12.01
关注
C++模版编程——单链表的实现
分类:
C++基础
2012-06-04 17:42
257人阅读
评论
(0)
收藏
举报
代码的注释还是很清晰的,就不说废话了。
直接上代码:
[cpp]
view plain
copy
?
#pragma once
#include <assert.h>
#include <iostream>
using
std::cout;
using
std::endl;
//单链表模板类
template
<
class
T>
class
CList
{
public
:
//类方法接口
enum
{begin=0,end=-1};
typedef
struct
_LIST
{
_LIST* pNext;
//指向下一个元素
T data;
//数据域
}LIST,*PLIST;
explicit
CList(
const
T s[],
const
int
n);
explicit
CList();
CList<T>& operator=(
const
CList<T>& l);
//默认赋值操作符
bool
operator==(
const
CList<T>& l);
//重载等于操作符
friend
bool
operator==(
const
LIST& l1,
const
LIST& l2)
{
if
((l1.data==l2.data))
return
true
;
return
false
;
}
virtual
~ CList();
//打印链表元素
void
Show()
const
;
//获取元素数目
void
GetLength()
const
;
//获取第index 个元素
T GetAt(
const
int
& index)
const
;
T operator[](
int
index)
const
;
//在第index个元素前插入元素t,插入末尾时约定index=-1
void
Insert(
const
T& t,
const
int
& index=end);
//默认情况下,在链表末尾插入
void
Insert(
const
T s[],
const
int
count,
const
int
& index=end);
//在第index个元素前插入count个元素
//删除索引为index 的元素
void
Delete(
const
int
& index);
//删除从index开始的n个元素,当n大于index开始的元素数目之和时,删除后面所有的
void
Delete(
const
int
& index,
const
int
& n);
//删除索引为index1和index2之间的所有元素
void
DeleteBetween(
const
int
& index1,
const
int
& index2);
//index1和index2之间大小不用限定
//删除链表中所有元素
void
DeleteAll();
//获取链表所有元素,存在数组中
void
GetData(T s[])
const
;
//获取链表中最大元素
T GetMaxData()
const
;
//获取链表中最小元素
T GetMinData()
const
;
//对链表进行排序
void
SortList();
//链表逆置
void
InverseList();
//链表是否为空
bool
IsEmpty()
const
;
//替换索引为index处的元素值
void
Replace(
const
T& t,
const
int
& index);
//用数组s[]中的count个元素替换index开始的count个节点的值
void
Replace(
const
T s[],
const
int
& index,
const
int
& count);
//从pos开始查找,默认从第一个位置,按先后顺序查找元素值,返回索引值,没有找到返回-1,找到即停止
int
Find(
const
T& t,
const
int
pos=begin);
//从末尾开始查找,没找到返回-1
int
FindLastOf(
const
T& t,
const
int
pos=end);
//获取两个变量中大的一个
inline
int
GetMax(
const
int
& a,
const
int
& b)
const
;
//获取两个变量中小的那个
inline
int
GetMin(
const
int
& a,
const
int
& b)
const
;
protected
:
void
Release();
//释放所有内存空间
//释放index开始的所有内存空间
void
Release(
const
int
& index);
//释放index1到index2之间元素的内存空间
void
Release(
const
int
& index1,
const
int
& index2);
//创建一个链表链接S[]内所有元素,返回首地址
LIST* CreateList(
const
T s[],
const
int
& count)
const
{
assert(count>0);
PLIST p1=
new
LIST;
//第一个节点
p1->data=s[0];
PLIST temp=p1;
for
(
int
i=1;i<count-1;++i)
{
PLIST p=
new
LIST;
p->data=s[i];
temp->pNext=p;
temp=p;
}
PLIST tail=
new
LIST;
tail->data=s[count-1];
temp->pNext=tail;
tail->pNext=NULL;
return
p1;
}
//返回第index(从0开始索引)个元素的地址,默认值-1,返回头指针地址
LIST* GetAddr(
const
int
& index=-1)
{
assert(index>=-1&&index<m_iLength);
if
(index==-1)
return
pHeader;
PLIST p=pHeader->pNext;
for
(
int
i=0;i<index;++i)
p=p->pNext;
return
p;
}
//交换元素值
inline
void
Swap(LIST* p1,LIST* p2)
const
;
//快速排序算法
int
Partition(
int
low,
int
high);
void
QSort(
int
low,
int
high);
void
QuickSort();
private
:
//类属性
PLIST pHeader;
//指向数据域缓冲区首地址,data存放链表长度
int
m_iLength;
//元素数目
};
//实现类方法
template
<
class
T>
CList<T>::CList():pHeader(NULL),m_iLength(0)
{
pHeader=
new
LIST;
pHeader->pNext=NULL;
pHeader->data=(T)0;
}
template
<
class
T>
CList<T>::CList(
const
T s[],
const
int
n):pHeader(NULL),m_iLength(n)
{
assert(n>=0);
pHeader=
new
LIST;
pHeader->data=(T)0;
pHeader->pNext=CreateList(s,n);
}
template
<
class
T>
void
CList<T>::Release()
{
PLIST p=pHeader;
while
(p)
{
PLIST temp=p->pNext;
delete
p;
p=temp;
}
pHeader=NULL;
m_iLength=0;
}
template
<
class
T>
CList<T>::~CList()
{
Release();
}
template
<
class
T>
void
CList<T>::Show()
const
{
PLIST p=pHeader->pNext;
for
(
int
i=0;i<m_iLength-1;++i)
{
cout<<p->data<<
"--->"
;
p=p->pNext;
}
cout<<p->data<<endl;
cout<<endl;
}
template
<
class
T>
void
CList<T>::GetLength()
const
{
return
m_iLength;
}
template
<
class
T>
T CList<T>::GetAt(
const
int
& index)
const
{
assert(index>=0&&index<m_iLength);
PLIST p=pHeader->pNext;
for
(
int
i=0;i<index;++i)
p=p->pNext;
return
p->data;
}
template
<
class
T>
T CList<T>::operator [](
int
index)
const
{
return
GetAt(index);
}
template
<
class
T>
CList<T>& CList<T>::operator =(
const
CList<T> &l)
{
if
(*
this
==l)
return
*
this
;
Release();
pHeader=
new
LIST;
pHeader->data=(T)0;
m_iLength=l.m_iLength;
PLIST lp=pHeader;
for
(
int
i=0;i<m_iLength-1;++i)
{
PLIST p=
new
LIST;
p->data=l[i];
lp->pNext=p;
lp=p;
}
PLIST tail=
new
LIST;
tail->data=l[m_iLength-1];
tail->pNext=NULL;
lp->pNext=tail;
return
*
this
;
}
template
<
class
T>
bool
CList<T>::operator ==(
const
CList<T> &l)
{
if
(pHeader==l.pHeader)
return
true
;
return
false
;
}
template
<
class
T>
void
CList<T>::Insert(
const
T &t,
const
int
& index = -1)
{
assert(index>=-1&&index<m_iLength);
//确保插入位置有效
LIST* p=
new
LIST;
p->data=t;
if
(index==-1)
// 末尾插入
{
GetAddr(m_iLength-1)->pNext=p;
p->pNext=NULL;
}
else
{
PLIST pl=NULL;
if
(index==0)
pl=GetAddr();
else
pl=GetAddr(index-1);
p->pNext=pl->pNext;
pl->pNext=p;
}
m_iLength++;
}
template
<
class
T>
void
CList<T>::Insert(
const
T s[],
const
int
count,
const
int
& index = -1)
{
assert(count>1);
assert(index>=-1&&index<m_iLength);
PLIST p=CreateList(s,count);
if
(index==-1)
//末尾插入
GetAddr(m_iLength-1)->pNext=p;
else
{
PLIST p1=NULL;
if
(index==0)
//头结点后插入
p1=GetAddr();
else
p1=GetAddr(index-1);
PLIST tail=p->pNext;
while
(
true
)
//循环获取插入短链的尾指针
{
if
(tail->pNext==NULL)
break
;
tail=tail->pNext;
}
tail->pNext=p1->pNext;
p1->pNext=p;
}
m_iLength+=count;
}
template
<
class
T>
void
CList<T>::Delete(
const
int
& index)
{
assert(index>=0&&index<m_iLength);
PLIST p=NULL;
if
(index==0)
//删除第一个节点
{
p=pHeader->pNext;
pHeader->pNext=p->pNext;
delete
p;
p=NULL;
}
else
if
(index==m_iLength-1)
//删除最后一个节点
{
p=GetAddr(m_iLength-2);
PLIST temp=p->pNext;
p->pNext=NULL;
delete
temp;
temp=NULL;
}
else
//其他情况
{
p=GetAddr(index-1);
PLIST temp=p->pNext;
p->pNext=temp->pNext;
delete
temp;
temp=NULL;
}
m_iLength--;
}
template
<
class
T>
void
CList<T>::GetData(T s[])
const
{
PLIST p=pHeader->pNext;
int
i=0;
while
(p)
{
s[i]=p->data;
p=p->pNext;
++i;
}
}
template
<
class
T>
void
CList<T>::DeleteAll()
{
Release();
pHeader=
new
LIST;
pHeader->data=(T)0;
pHeader->pNext=NULL;
}
template
<
class
T>
void
CList<T>::Delete(
const
int
&index,
const
int
&n)
{
assert(index>=0&&index<m_iLength);
assert(n>0);
if
(m_iLength-index<n)
//删除index开始的所有元素
Release(index);
else
//删除index开始的n个元素
Release(index,n+index-1);
}
template
<
class
T>
void
CList<T>::DeleteBetween(
const
int
& index1,
const
int
& index2)
{
assert(index1>=0&&index1<m_iLength);
assert(index2>=0&&index2<m_iLength);
Release(index1,index2);
}
template
<
class
T>
void
CList<T>::Release(
const
int
&index)
{
PLIST p=GetAddr(index-1);
PLIST temp=p->pNext;
//保存下一个节点
p->pNext=NULL;
while
(temp)
{
PLIST lp=temp->pNext;
delete
temp;
temp=lp;
}
m_iLength=index;
}
template
<
class
T>
void
CList<T>::Release(
const
int
&index1,
const
int
&index2)
{
if
(index1==index2)
//不释放
return
;
int
max=GetMax(index1,index2);
int
min=GetMin(index1,index2);
if
(max==m_iLength-1)
{
Release(min);
return
;
}
PLIST p1=GetAddr(min-1);
PLIST p2=p1->pNext;
//保存需要删除内存首地址
PLIST p3=GetAddr(max+1);
p1->pNext=p3;
//连接
while
(p2!=p3)
{
PLIST temp=p2->pNext;
//保存下一个节点的地址
delete
p2;
p2=temp;
}
m_iLength-=(max-min+1);
}
template
<
class
T>
T CList<T>::GetMaxData()
const
{
assert(m_iLength>0);
T max=GetAt(0);
for
(
int
i=1;i<m_iLength;++i)
{
T temp=GetAt(i);
if
(temp>max)
max=temp;
}
return
max;
}
template
<
class
T>
T CList<T>::GetMinData()
const
{
assert(m_iLength>0);
T min=GetAt(0);
for
(
int
i=1;i<m_iLength;++i)
{
T temp=GetAt(i);
if
(temp<min)
min=temp;
}
return
min;
}
template
<
class
T>
void
CList<T>::SortList()
{
if
(m_iLength<2)
return
;
QuickSort();
}
template
<
class
T>
inline
void
CList<T>::Swap(LIST* p1,LIST* p2)
const
{
T temp=p1->data;
p1->data=p2->data;
p2->data=temp;
}
template
<
class
T>
void
CList<T>::InverseList()
{
if
(m_iLength<2)
return
;
int
low=0,high=m_iLength-1;
while
(low<high)
{
Swap(GetAddr(low),GetAddr(high));
low++;
high--;
}
}
template
<
class
T>
int
CList<T>::Partition(
int
low,
int
high)
{
T key=GetAddr(low)->data;
while
(low<high)
{
while
(low<high&&GetAddr(high)->data>=key)
--high;
GetAddr(low)->data=GetAddr(high)->data;
while
(low<high&&GetAddr(low)->data<=key)
++low;
GetAddr(high)->data=GetAddr(low)->data;
}
GetAddr(low)->data=key;
return
low;
}
template
<
class
T>
void
CList<T>::QSort(
int
low,
int
high)
{
if
(low<high)
{
int
ret=Partition(low,high);
QSort(low,ret-1);
QSort(ret+1,high);
}
}
template
<
class
T>
void
CList<T>::QuickSort()
{
QSort(0,m_iLength-1);
}
template
<
class
T>
bool
CList<T>::IsEmpty()
const
{
if
(m_iLength)
return
false
;
return
true
;
}
template
<
class
T>
void
CList<T>::Replace(
const
T &t,
const
int
&index)
{
assert(index>=0&&index<m_iLength);
GetAddr(index)->data=t;
}
template
<
class
T>
void
CList<T>::Replace(
const
T s[],
const
int
&index,
const
int
&count)
{
assert(index>=0&&index<m_iLength);
assert(count>=0);
if
(count==0)
return
;
if
(m_iLength-index>count)
//替换count个元素
{
for
(
int
i=0;i<count;++i)
GetAddr(index+i)->data=s[i];
}
else
//替换m_iLength-index个
{
for
(
int
i=0;i<m_iLength-index;++i)
GetAddr(index+i)->data=s[i];
}
}
template
<
class
T>
inline
int
CList<T>::GetMax(
const
int
& a,
const
int
& b)
const
{
if
(a>b)
return
a;
return
b;
}
template
<
class
T>
inline
int
CList<T>::GetMin(
const
int
& a,
const
int
& b)
const
{
if
(a<b)
return
a;
return
b;
}
template
<
class
T>
int
CList<T>::Find(
const
T &t,
const
int
pos)
{
assert(pos>=0&&pos<m_iLength);
int
index=pos;
PLIST p=GetAddr(pos);
while
(
true
)
{
if
(p->data==t)
return
index;
if
(p->pNext==NULL)
return
-1;
p=p->pNext;
++index;
}
}
template
<
class
T>
int
CList<T>::FindLastOf(
const
T &t,
const
int
pos)
{
assert(pos>=-1&&pos<m_iLength);
PLIST p=NULL;
int
index=pos;
if
(pos==end)
{
p=GetAddr(m_iLength-1);
index=m_iLength-1;
}
else
p=GetAddr(pos);
while
(
true
)
{
if
(p->data==t)
return
index;
if
(index==0)
return
-1;
--index;
p=GetAddr(index);
}
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报
。
打开APP,阅读全文并永久保存
查看更多类似文章
猜你喜欢
类似文章
【热】
打开小程序,算一算2024你的财运
QT信号机制(
一步一步写算法(之单向链表)
C list 类学习笔记
C5
笔试试题
第二十九讲 正确的List(数组)
更多类似文章 >>
生活服务
热点新闻
留言交流
回顶部
联系我们
分享
收藏
点击这里,查看已保存的文章
导长图
关注
一键复制
下载文章
绑定账号成功
后续可登录账号畅享VIP特权!
如果VIP功能使用有故障,
可点击这里联系客服!
联系客服
微信登录中...
请勿关闭此页面
先别划走!
送你5元优惠券,购买VIP限时立减!
5
元
优惠券
优惠券还有
10:00
过期
马上使用
×