线性表之单链表C++实现

　　　　线性表之单链表

一、头文件：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;}

//实现单链表按位查找，返回指定位置的元素template<class DataType>DataType LinkedList<DataType>::GetElement(int index){ 　　//定义工作指针 　　Node<DataType> *p = first->next; 　　//定义计数器，初始值是1 　　int count = 1; 　　//查找序号所对应的位置 　　while (p != NULL&&count < index) 　　{ 　　　　//工作指针后移 　　　　p = p->next; 　　　　//计数器加1 　　　　count++; 　　} 　　//如果找到单链表的末尾，还找不到指定的位置，则抛出异常 　　if (p == NULL) 　　{ 　　　　throw "查找的位置有误"; 　　} 　　else 　　{ 　　　　//当找到合适的位置时，返回该位置上的元素 　　　　return p->data; 　　}

}

//实现获取单链表的长度template<class DataType>int LinkedList<DataType>::GetLength(){ 　　//定义计数器，用来计算单链表的长度 　　int count = 0; 　　//定义工作指针 　　Node<DataType> *p = first->next; 　　while (p != NULL) 　　{ 　　　　p = p->next; 　　　　count++; 　　} 　　return count;

}

//实现单链表的按序号输出元素template<class DataType>void LinkedList<DataType>::PrintLinkedList(){ 　　//声明工作指针 　　Node<DataType> *p; 　　//初始化工作指针 　　p = first->next; 　　while(p != NULL) 　　{ 　　　　cout << p->data << " "; 　　　　//工作指针向后移动 　　　　p = p->next; 　　} 　　cout << endl;}

//实现单链表的删除template<class DataType>DataType LinkedList<DataType>::Delete(int index){ 　　Node<DataType> *p = first->next; 　　int count = 0; 　　//查找第 index-1 位置结点 　　while (p != NULL&&count < index - 1) 　　{ 　　　　p = p->next; 　　　　count++; 　　} 　　//如果能找到 　　if (p == NULL || p->next == NULL) 　　{ 　　　　throw "删除的位置有误"; 　　} 　　else 　　{ 　　　　Node<DataType> *q = p->next; 　　　　DataType x = q->data; 　　　　p->next = q->next; 　　　　delete q; 　　　　return x; 　　}}

 二、测试线性表之单链表的源文件：TestLinkedList.cpp

#include<iostream>#include "LinkedList.h"using namespace std;void show(){ 　　cout << "---------------------------------------" << endl;}int main(){ 　　int array[] = { 1, 3, 5, 2, 7, 6, 9, 8, 10, 4}; 　　//声明单链表 　　LinkedList<int> linkedList = LinkedList<int>(10,array); 　　cout << "输出单链表：" << endl; 　　linkedList.PrintLinkedList(); 　　show(); 　　cout << "单链表的长度:" << linkedList.GetLength() << endl; 　　cout << "单链表中第5个元素是：" << linkedList.GetElement(5) << endl; 　　cout << "单链表中元素5的位置是：" << linkedList.GetLocal(5) << endl; 　　show(); 　　cout << "在单链表的第5个位置上插入元素22" << endl; 　　linkedList.Insert(5, 22); 　　cout << "输出单链表：" << endl; 　　linkedList.PrintLinkedList(); 　　cout << "单链表的长度:" << linkedList.GetLength() << endl; 　　show(); 　　cout << "删除第5位置的元素" << endl; 　　linkedList.Delete(5); 　　cout << "输出单链表：" << endl; 　　linkedList.PrintLinkedList(); 　　cout << "单链表的长度:" << linkedList.GetLength() << endl; 　　show(); 　　return 0;}