C++数据结构之单链表
node.h
#ifndef __NODE_H__
#define __NODE_H__
// 结点类模板
template <class ElemType>
struct Node
{
// 数据成员:
ElemType data; // 数据成分
Node<ElemType>* next; // 指针成分
// 构造函数模板:
Node(); // 无参数的构造函数模板
Node(const ElemType& e, Node<ElemType>* link = NULL); // 已知数据元素值和指针建立结点
};
// 结点类模板的实现部分
template<class ElemType>
Node<ElemType>::Node()
// 操作结果：构造指针成分为空的结点
{
next = NULL;
}
template<class ElemType>
Node<ElemType>::Node(const ElemType& e, Node<ElemType>* link)
// 操作结果：构造一个数据成分为e和指针成分为link的结点
{
data = e;
next = link;
}
#endif
lk_list.h
#ifndef __LK_LIST_H__
#define __LK_LIST_H__
#include "node.h" // 结点类模板
// 线性链表类模板
template <class ElemType>
class LinkList
{
protected:
// 数据成员:
Node<ElemType>* head; // 头结点指针
mutable int curPosition; // 当前位置的序号
mutable Node<ElemType>* curPtr; // 指向当前位置的指针
int count; // 元素个数
// 辅助函数模板:
Node<ElemType>* GetElemPtr(int position) const; // 返回指向第position个结点的指针
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
LinkList(); // 无参数的构造函数模板
virtual ~LinkList(); // 析构函数模板
int Length() const; // 求线性表长度
bool Empty() const; // 判断线性表是否为空
void Clear(); // 将线性表清空
void Traverse(void (*visit)(const ElemType&)) const; // 遍历线性表
bool GetElem(int position, ElemType& e) const; // 求指定位置的元素
bool SetElem(int position, const ElemType& e); // 设置指定位置的元素值
bool Delete(int position, ElemType& e); // 删除元素
bool Delete(int position); // 删除元素
bool Insert(int position, const ElemType& e); // 插入元素
LinkList(const LinkList<ElemType>& source); // 复制构造函数模板
LinkList<ElemType>& operator =(const LinkList<ElemType>& source); // 重载赋值运算符
};
// 链表类模板的实现部分
template<class ElemType>
Node<ElemType>* LinkList<ElemType>::GetElemPtr(int position) const
// 操作结果：返回指向第position个结点的指针
{
if (curPosition > position)
{ // 当前位置在所查找位置之后,只能从表头开始操作
curPosition = 0;
curPtr = head;
}
for (; curPosition < position; curPosition++)
curPtr = curPtr->next; // 查找位置position
return curPtr;
}
template <class ElemType>
LinkList<ElemType>::LinkList()
// 操作结果：构造一个空链表
{
head = new Node<ElemType>; // 构造头结点
curPtr = head; curPosition = 0; // 初始化当前位置
count = 0; // 初始化元素个数
}
template <class ElemType>
LinkList<ElemType>::~LinkList()
// 操作结果：销毁线性表
{
Clear(); // 清空线性表
delete head; // 释放头结点所指空间
}
template <class ElemType>
int LinkList<ElemType>::Length() const
// 操作结果：返回线性表元素个数
{
return count;
}
template <class ElemType>
bool LinkList<ElemType>::Empty() const
// 操作结果：如线性表为空，则返回true，否则返回false
{
return head->next == NULL;
}
template <class ElemType>
void LinkList<ElemType>::Clear()
// 操作结果：清空线性表
{
while (!Empty())
{ // 表性表非空，则删除第1个元素
Delete(1); // 删除第1个元素
}
}
template <class ElemType>
void LinkList<ElemType>::Traverse(void (*visit)(const ElemType&)) const
// 操作结果：依次对线性表的每个元素调用函数(*visit)
{
for (Node<ElemType>* temPtr = head->next; temPtr != NULL; temPtr = temPtr->next)
{ // 用temPtr依次指向每个元素
(*visit)(temPtr->data); // 对线性表的每个元素调用函数(*visit)
}
}
template <class ElemType>
bool LinkList<ElemType>::GetElem(int position, ElemType& e) const
// 操作结果：当线性表存在第position个元素时，用e返回其值，返回true,
// 否则返回false
{
if (position < 1 || position > Length())
{ // position范围错
return false; // 元素不存在
}
else
{ // position合法
Node<ElemType>* temPtr = GetElemPtr(position); // 取出指向第position个结点的指针
e = temPtr->data; // 用e返回第position个元素的值
return true; // 元素存在
}
}
template <class ElemType>
bool LinkList<ElemType>::SetElem(int position, const ElemType& e)
// 操作结果：将线性表的第position个位置的元素赋值为e,
// position的取值范围为1≤position≤Length(),
// position合法时返回true,否则返回false
{
if (position < 1 || position > Length())
{ // position范围错
return false; // 范围错
}
else
{ // position合法
Node<ElemType>* temPtr = GetElemPtr(position); // 取出指向第position个结点的指针
temPtr->data = e; // 设置第position个元素的值
return true; // 设置元素成功
}
}
template <class ElemType>
bool LinkList<ElemType>::Delete(int position, ElemType& e)
// 操作结果：删除线性表的第position个元素, 并用e返回其值,
// position的取值范围为1≤position≤Length(),
// position合法时返回true,否则返回false
{
if (position < 1 || position > Length())
{ // position范围错
return false; // 范围错
}
else
{ // position合法
Node<ElemType>* temPtr = GetElemPtr(position - 1); // 取出指向第position-1个结点的指针
Node<ElemType>* nextPtr = temPtr->next; // nextPtr为temPtr的后继
temPtr->next = nextPtr->next; // 删除结点
e = nextPtr->data; // 用e返回被删结点元素值
if (position == Length())
{ // 删除尾结点,当前结点变为头结点
curPosition = 0; // 设置当前位置的序号
curPtr = head; // 设置指向当前位置的指针
}
else
{ // 删除非尾结点,当前结点变为第position个结点
curPosition = position; // 设置当前位置的序号
curPtr = temPtr->next; // 设置指向当前位置的指针
}
count--; // 删除成功后元素个数减1
delete nextPtr; // 释放被删结点
return true; // 删除成功
}
}
template <class ElemType>
bool LinkList<ElemType>::Delete(int position)
// 操作结果：删除线性表的第position个元素, 并用e返回其值,
// position的取值范围为1≤position≤Length(),
// position合法时返回true,否则返回false
{
if (position < 1 || position > Length())
{ // position范围错
return false; // 范围错
}
else
{ // position合法
Node<ElemType>* temPtr = GetElemPtr(position - 1); // 取出指向第position-1个结点的指针
Node<ElemType>* nextPtr = temPtr->next; // nextPtr为temPtr的后继
temPtr->next = nextPtr->next; // 删除结点
if (position == Length())
{ // 删除尾结点,当前结点变为头结点
curPosition = 0; // 设置当前位置的序号
curPtr = head; // 设置指向当前位置的指针
}
else
{ // 删除非尾结点,当前结点变为第position个结点
curPosition = position; // 设置当前位置的序号
curPtr = temPtr->next; // 设置指向当前位置的指针
}
count--; // 删除成功后元素个数减1
delete nextPtr; // 释放被删结点
return true; // 删除成功
}
}
template <class ElemType>
bool LinkList<ElemType>::Insert(int position, const ElemType& e)
// 操作结果：在线性表的第position个元素前插入元素e
// position的取值范围为1≤position≤Length()+1
// position合法时返回true, 否则返回false
{
if (position < 1 || position > Length() + 1)
{ // position范围错
return false; // 范围错
}
else
{ // position合法
Node<ElemType>* temPtr = GetElemPtr(position - 1); // 取出指向第position-1个结点的指针
Node<ElemType>* newPtr = new Node<ElemType>(e, temPtr->next); // 生成新结点
temPtr->next = newPtr; // 将temPtr插入到链表中
curPosition = position; // 设置当前位置的序号
curPtr = newPtr; // 设置指向当前位置的指针
count++; // 插入成功后元素个数加1
return true; // 删除成功
}
}
template <class ElemType>
LinkList<ElemType>::LinkList(const LinkList<ElemType>& source)
// 操作结果：由线性表source构造新线性表——复制构造函数模板
{
int sourceLength = source.Length(); // source的长度
ElemType temElem; // 临时元素
// 初始化一个空线性表
head = new Node<ElemType>; // 构造头结点
curPtr = head; curPosition = 0; // 初始化当前位置
count = 0; // 初始化元素个数
for (int temPos = 1; temPos <= sourceLength; temPos++)
{ // 复制数据元素
source.GetElem(temPos, temElem); // 取出第temPos个元素
Insert(Length() + 1, temElem); // 将temElem插入到当前线性表
}
}
template <class ElemType>
LinkList<ElemType>& LinkList<ElemType>::operator =(const LinkList<ElemType>& source)
// 操作结果：将线性表source赋值给当前线性表——重载赋值运算符
{
if (&source != this)
{
int sourceLength = source.Length(); // source的长度
ElemType temElem; // 临时元素
Clear(); // 清空当前线性表
for (int temPos = 1; temPos <= sourceLength; temPos++)
{ // 复制数据元素
source.GetElem(temPos, temElem); // 取出第temPos个元素
Insert(Length() + 1, temElem); // 将temElem插入到当前线性表
}
}
return *this;
}
#endif测试程序
#include <iostream> // 编译预处理命令
using namespace std; // 使用命名空间std
#include "lk_list.h" // 线性链表类
template <class ElemType>
void Show(const ElemType& e)
// 操作结果: 显示数据元素
{
cout << e << " ";
}
int main()
{
char select = '0';
LinkList<double> la, lb;
double e;
int position;
while (select != '7')
{
cout << endl << "1. 生成线性表.";
cout << endl << "2. 显示线性表.";
cout << endl << "3. 检索元素.";
cout << endl << "4. 设置元素值.";
cout << endl << "5. 删除元素.";
cout << endl << "6. 插入元素.";
cout << endl << "7. 退出";
cout << endl << "选择功能(1~7):";
cin >> select;
switch (select)
{
case '1':
cout << endl << "输入e(e = 0时退出):";
cin >> e;
while (e != 0)
{
la.Insert(la.Length() + 1, e);
cin >> e;
}
break;
case '2':
lb = la;
lb.Traverse(Show<double>);
break;
case '3':
cout << endl << "输入元素位置:";
cin >> position;
if (!la.GetElem(position, e))
cout << "元素不存储." << endl;
else
cout << "元素:" << e << endl;
break;
case '4':
cout << endl << "输入位置:";
cin >> position;
cout << endl << "输入元素值:";
cin >> e;
if (!la.SetElem(position, e))
cout << "位置范围错." << endl;
else
cout << "设置成功." << endl;
break;
case '5':
cout << endl << "输入位置:";
cin >> position;
if (!la.Delete(position, e) && !la.Delete(position))
cout << "位置范围错." << endl;
else
cout << "被删除元素值:" << e << endl;
break;
case '6':
cout << endl << "输入位置:";
cin >> position;
cout << endl << "输入元素值:";
cin >> e;
if (!la.Insert(position, e))
cout << "位置范围错." << endl;
else
cout << "成功:" << e << endl;
break;
}
}
return 0; // 返回值0, 返回操作系统
}
例程均来自清华大学出版社 《数据结构与算法》（C++版）作者：唐宁九 游洪跃。