分类： C/C++
2011-08-06 22:31:28
/*
* C++单链表实现函数
* Lzy 2011-七夕
*/
#include
using namespace std;
template <class T>
class LinearListLink; //前向声明
template <class T>
class LinkNode //定义模板类链表节点
{
private:
T data; //数据域
LinkNode<T> *next; //指针域
public:
friend class LinearListLink<T>; //声明LinearListLink
};
template <class T>
class LinearListLink
{
protected:
LinkNode<T> *head; //头指针
public:
LinearListLink();
bool IsEmpty() const {return head->next==NULL;} //链表是否为空
int Length() const; //返回链表长度
bool Find(int k, T &x); //寻找链表中第K个元素
int Search(const T &x) const; //按值查找元素的位置
LinkNode<T> * GetNode(int i); //返回第i个结点
bool Insert(int k, const T &x); //在第K个位置插入x
bool Delete(int k, T &x); //删除第K个元素并将它返回至x
void Output() const; //输出
LinkNode<T> * GetHead(){return head;} //获得头结点指针
~LinearListLink(){delete head;};
};
/*
* 链表元素输出
*/
template <class T>
void LinearListLink<T>::Output() const
{
LinkNode<T> *current = head->next; //指向第一个节点
while(current) //指针是否指向链表尾
{
cout<<current->data<<" ";
current = current->next; //指针沿链表移动
}
}
/*
* 功能：删除第K个元素并将它返回至x
*/
template <class T>
bool LinearListLink<T>::Delete(int k, T &x)
{
LinkNode<T> *current = GetNode(k-1); //找到第k个节点前一个节点
if(current)
{
LinkNode<T> *p = current->next;
x = p->data; //弹出数据
current->next = p->next; //数据插入
delete p; //释放空间
return true;
}
return false;
}
/*
* 功能：在第K个位置插入x
*/
template <class T>
bool LinearListLink<T>::Insert(int k, const T &x)
{
LinkNode<T> *current = GetNode(k-1); //找到第k个节点前一个节点
if(current)
{
LinkNode<T> *p = new LinkNode<T>;
p->data = x; //保存数据
p->next = current->next;
current->next = p; //数据插入
return true;
}
return false;
}
/*
* 功能：寻找链表中第i个元素
* 返回第i个节点地址
*/
template <class T>
LinkNode<T> * LinearListLink<T>::GetNode(int i)
{
if(i < 0 || i > Length()) //检查K是否合法
{
cout<<"GetNode: "<<i<<"无效"<<endl;
return NULL;
}
LinkNode<T> *current = head; //指向头节点，头节点标号为0
for(int index = 0; index < i && current; index++)
{
current = current->next; //指针沿链表移动
}
if(current)
{
return current;
}
else
{
cout<<"没有: "<<i<<"数据"<<endl;
return NULL;
}
}
/*
* 功能：寻找链表中第K个元素
* 并将其值送至x
*/
template <class T>
bool LinearListLink<T>::Find(int k, T &x)
{
LinkNode<T> *current = GetNode(k); //指向第k个节点
if(current)
{
x = current->data; //返回第k个位置的节点值
return true;
}
else
return false;
}
/*
* 功能：按值查找元素在链表中的位置
*/
template <class T>
int LinearListLink<T>::Search(const T &x) const
{
if(IsEmpty() == true)
{
cout<<"ListLink is Empty"<<endl;
return 0;
}
LinkNode<T> *current = head->next; //指向第一个节点
int index = 1;
while(current && current->data != x)
{
current = current->next; //指针沿链表移动
index++;
}
if(current)
{
return index;
}
else
{
cout<<"没有: "<<x<<"数据"<<endl;
return false;
}
}
/*
* 功能：计算链表长度
* 出口参数：链表长度
*/
template <class T>
int LinearListLink<T>::Length() const
{
LinkNode<T> *current = head->next; //指向第一个节点
int len = 0;
while(current) //指针是否指向链表尾
{
current = current->next; //指针沿链表移动
len++; //计数加一
}
return len; //返回链表长度
}
/*
* 构造函数初始化链表头
*/
template <class T>
LinearListLink<T>::LinearListLink()
{
head = new LinkNode<T>;
head->next = NULL;
}
/*
* 测试程序
*/
int main(void)
{
LinearListLink<int> L;
L.Length();
for(int i=1; i<20; i++) //插入数据
L.Insert(i,i);
L.Output();
cout<<endl;
cout<<"链表长度"<<L.Length()<<endl;
cout<<"数据为13的位置 "<<L.Search(13)<<endl;
L.Insert(9,20); //在弟9个位置插入20
int i;
L.Find(9,i);
cout<<"第9个位置的数据 "<<i<<endl;
L.Delete(9,i);
cout<<"删除的数据 "<<i<<endl;
return 0;
}
源码：
C++单链表.rar
