线性表之单链表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;}