线性表之单链表
一、头文件：LinkedList.h
//单链表是用一组任意的存储单元存放线性表的元素，这组单元可以是连续的也可以是不连续的，甚至可以是零散分布在内存中的任意位置。
//单链表头文件
#include<iostream>
using namespace std;
//定义单链表结点-结构体类型
template<class DataType>
struct Node
{
//数据域，存放该结点的数据
DataType data;
//指针域，指向下一个结点
Node<DataType> *next;
};
template<class DataType>
class LinkedList{
public:
//单链表无参构造器
LinkedList();
//单链表有参构造器
LinkedList(DataType array[], int n);
LinkedList(int n, DataType array[]);
//单链表析构函数
~LinkedList();
//获取单链表的长度
int GetLength();
//查找单链表指定元素的序号
int GetLocal(DataType x);
//获取单链表指序号的元素
DataType GetElement(int index);
//单链表中在指定位置插入指定的元素
void Insert(int index, DataType x);
//在单链表中删除指定位置的元素
DataType Delete(int index);
//按序号输出单链表中的元素
void PrintLinkedList();
private :
//声明单链表的头指针
Node<DataType> *first;
};
//实现单链表的无参构造函数
template<class DataType>
LinkedList<DataType>::LinkedList()
{
first = new Node<DataType>;
first->next = NULL;
}
//头插法建立单链表
template<class DataType>
LinkedList<DataType>::LinkedList(int n,DataType array[])
{
//初始化一个空链表
first = new Node<DataType>;
first->next = NULL;
for (int i = 0; i < n; i++)
{
//为每一个数组元素都申请新结点
Node<DataType> *s = new Node<DataType>;
//数组元素赋值给结点数据域
s->data = array[i];
//将结点插入到头结点之前
s->next = first->next;
first->next = s;
}
}
//尾插法建立单链表
template<class DataType>
LinkedList<DataType>::LinkedList(DataType array[], int n)
{
//生成头结点
first = new Node<DataType>;
//定义尾结点
Node<DataType> *r = first;
for (int i = 0; i < n; i++)
{
//为每一个数组元素申请一个结点
Node<DataType> *s = new Node<DataType>;
//把数组元素赋值给结点的数据域
s->data = array[i];
//将每一个结点追加到终端结点之后
r->next = s;
r = s;
}
//尾结点尾NULL
r->next = NULL;
}
//实现单链表的析构函数
template<class DataType>
LinkedList<DataType>::~LinkedList()
{
//声明工作指针
Node<DataType> *q;
while (first != NULL)
{
//暂存被释放的结点
q = first;
//让头指针指向要释放结点的下一个结点
first = first->next;
delete q;
}
}
//实现单链表插入:在指定的位置插入指定的元素
template<class DataType>
void LinkedList<DataType>::Insert(int index, DataType x)
{
//定义工作指针
Node<DataType> *p = first->next;
//定义计数器，初始值为0
int count = 0;
while (p != NULL &&count < index - 1)
{
//工作指针后移
p = p->next;
count ++;
}
//找到 index-1 的位置
if (p == NULL)
{
throw "插入的位置有误";
}
else
{
//申请一个新结点
Node<DataType> *s;
s= new Node<DataType>;
//其数据域为 x
s->data = x;
//在新结点的指针域存放工作指针p的指针域
s->next = p->next;
//将结点s插入到p结点之后
p->next = s;
}
}
//实现单链表的按值查找，返回指定元素在单链表中的序号（如不存在，则返回0）
template<class DataType>
int LinkedList<DataType>::GetLocal(DataType x)
{
//定义工作指针
Node<DataType> *p = first->next;
//定义计数器，初始值是1
int count = 1;
//查找序号所对应的位置
while (p != NULL)
{
if (p->data == x)
{
return count;
}
//工作指针后移
p = p->next;
//计数器加1
count++;
}
//如果找不到该元素，则返回0
return 0;
}