将线性表的抽象数据类型定义在链接存储结构下用C++的类实现，由于线性表的数据元素类型不确定，所以采用模板机制。
头文件linklist.h
#pragma once
#include <iostream>
// 单链表的节点
template<class T>
struct Node
{
T data;//数据域
Node<T> *next;// 指针域，指向后继节点
};
// 单链表的类实现
template<class T>
class LinkList
{
public:
LinkList();// 无参构造函数，建立只有头节点的空链表
LinkList(T a[],int n);// 有参构造函数，建立有n个元素的单链表
~LinkList();// 析构函数
int Length();// 求单链表的长度
T Get(int i);// 查找第i个元素
int Locate(T x);// 查找值为x的元素
void Insert(int i, T x);// 在第i个元素处插入x
T Delete(int i);// 删除第i个节点
void PrintList();// 遍历各个元素
private:
Node<T>* first;// 单链表的头节点
}; template<class T>
inline LinkList<T>::LinkList()
{
first = new Node<T>; // 生成头节点
first->next = NULL; // 头节点指针域为空
} // 头插法建立单链表
template<class T>
LinkList<T>::LinkList(T a[], int n)
{
first = new Node<T>;
first->next = NULL; // 初始化一个空链表
for (int i = ; i < n; i++)
{
Node<T>* S = new Node<T>;
S->data = a[i]; // 为每个数据元素建立一个节点
S->next = first->next;
first->next = S; // 将节点S插入头节点之后
}
}
// 尾插法建立单链表
template<class T>
LinkList<T>::LinkList(T a[], int n)
{
first = new Node<T>;// 建立头节点
first->next = NULL;
Node<T>* r = first;// 尾指针初始化
for(int i = ; i < n; i++)
{
Node<T>* S = new Node<T>;
S->data = a[i]; // 为每个数据元素建立一个节点
r->next = S;
r = S; // 插入节点S，并将尾指针指向S节点
}
r->next = NULL; // 单链表建立完毕之后，将尾指针置空
} template<class T>
LinkList<T>::~LinkList()
{
while (first != NULL)
{
Node<T>* p = first; // 暂存将被释放节点
first = first->next; // 指向下一个节点
delete p;
}
} template<class T>
int LinkList<T>::Length()
{
int count = ; // 计数
Node<T>* p = first->next; // 将工作指针指向第一个节点
while (p != NULL)
{
count++;
p = p->next;
}
return count;
} template<class T>
T LinkList<T>::Get(int i)
{
int count = ; // 计数
Node<T>* p = first->next; // 将工作指针指向第一个节点
while (p != NULL)
{
count++;
if (count == i)
return p->data;
p = p->next;
}
return -; // 越界
} template<class T>
int LinkList<T>::Locate(T x)
{
int count = ; // 计数
Node<T>* p = first->next; // 将工作指针指向第一个节点
while (p != NULL)
{
count++;
if (p->data == x)
return count;
p = p->next;
}
return ; // 查找失败
} template<class T>
void LinkList<T>::Insert(int i, T x)
{
int count = ; // 计数
Node<T>* p = first; // 将工作指针指向头节点
while (p != NULL)
{
if (count == i - ) // 找第i-1个节点
{
Node<T>* S = new Node<T>;
S->data = x;
S->next = p->next;
p->next = S;
}
p = p->next;
count++;
}
if (p == NULL)
throw "位置越界";
} template<class T>
T LinkList<T>::Delete(int i)
{
int count = ; // 计数
Node<T>* p = first; // 将工作指针指向头节点
while (p != NULL)
{
if (count == i - )
{
Node<T>* q = p->next;// 暂存被删节点
T x = q->data;
p->next = q->next;
delete q;
return x;
}
p = p->next;
count++;
}
return -;
} template<class T>
void LinkList<T>::PrintList()
{
Node<T>* p = first->next; // 将工作指针指向第一个节点
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
}
主函数
#include"linklist.h"
using namespace std; int main()
{
int arry[] = { , , , , , , , , , };
LinkList<int>* linklist = new LinkList<int>(arry, );
cout << linklist->Length() << endl;
cout << linklist->Get() << endl;
cout << linklist->Locate() << endl;
linklist->Insert(, );
linklist->Delete();
linklist->PrintList(); system("pause");
return ;
}
运行结果如下：