线性表之单链表
一、头文件: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;
}
本文永久更新链接地址:http://www.linuxidc.com/Linux/2017-04/142465.htm