概要

        本文包括利用c++编写的单链表的类模板以及其可视化界面。

整体架构流程

1. 在“linkList.h”头文件中定义一个LinkList类模板，在类模板中声明构造函数、析构函数和要实现的成员函数，并在其后给出所有函数的定义；

2. 在“链表.h”头文件中给出main函数中需要的函数（即设计可视化界面需要的函数）的声明；

3. 在“链表.cpp”文件中给出main函数中需要的函数（即设计可视化界面需要的函数）的定义；

4. 在“test.cpp”文件中完成可视化界面的设计。

技术名词解释

• 单链表

        单链表是一种常见的数据结构，用于存储和组织数据。它由一个个节点组成，每个节点包含两部分：数据域和指针域。

        数据域存储节点中实际的数据，可以是任意类型的数据，例如整数、字符、对象等。指针域则用于指向下一个节点的地址，将多个节点按顺序连接起来形成链表。

        单链表的特点包括：

1. 链式存储：单链表使用指针链接节点，而不需要连续的内存空间。这使得单链表能够灵活地插入和删除节点，不受固定大小的限制。
2. 动态大小：单链表的大小可以根据需要动态增长或缩小，不像数组需要预先指定大小并占用连续的内存空间。
3. 随机访问困难：由于节点之间通过指针链接，要访问链表中某个特定位置的元素，需要从头节点开始遍历直到目标位置。因此，单链表的访问时间复杂度为O(n)，其中n是链表的长度。
4. 插入和删除效率高：相对于数组，单链表在插入和删除元素时具有较高的效率，只需修改节点的指针即可完成操作，时间复杂度为O(1)。

        单链表适用于以下情况：

1. 需要频繁的插入和删除操作而不关注随机访问效率，例如实现队列、栈等数据结构。
2. 数据集合不需要连续的内存空间，大小不确定或会动态变化。
3. 不需要快速的查找操作。

        总之，单链表是一种灵活且常用的数据结构，它通过节点间的链接存储和组织数据，并提供了高效的插入、删除操作。

• c++类模板

        c++类模板是一种通用的编程工具，用于创建可以适应多种数据类型的类或函数。类模板允许在定义类时使用参数化类型，这样可以根据不同的类型生成具体的类。

        类模板使用 <template> 关键字定义，并在尖括号内指定一个或多个模板参数。模板参数可以是类型、常量或其他模板，用于在类的定义中表示占位符。

实现代码

linkList.h文件：

#pragma once
#include<iostream>
using namespace std;

//链表结点
template<class T>
struct Node {
	T data;
	Node* next;
};

//链表类模板
template<class T>
class LinkList {
private:
	Node<T>* head;
public:
	LinkList();             //构造函数，创建空链表
	~LinkList();			//析构函数，删除表空间
	void CreateList(int n); //创建具有n个元素的线性链表
	void Insert(int i, T e);//在表中第i个位置插入元素
	T Delete(int i);        //删除表中第i个元素
	T GetElem(int i);       //按位查找，获取第i个元素的值
	int Locate(T e);        //在链表中查找为e的元素
	int Empty();			//测表空
	int Length();			//测表长
	void Clear();			//清空表
	void ListDisplay();		//遍历输出表中元素
};

template<class T>
LinkList<T>::LinkList() {
	//构造函数，创建空链表
	head = new Node<T>;
	head->next = NULL;
}

template<class T>
LinkList<T>::~LinkList() {
	//析构函数，删除表空间
	while (head) {
		Node<T>* p = head;
		head = head->next;
		delete p;
	}
	head = NULL;
}

template<class T>
void LinkList<T>::CreateList(int n) { 
	//创建具有n个元素的线性链表
	//尾插法
	Node<T>* p, * s;
	p = head;
	for (int i = 0; i < n; i++) {
		s = new Node<T>;
		cout << "请输入第" << (i + 1) << "个位置的元素值：" << endl;
		cin >> s->data;
		s->next = p->next;
		p->next = s;
		p = s;
	}
}

template<class T>
void LinkList<T>::Insert(int i, T e) {
	//在表中第i个位置插入元素
	Node<T>* p = head;
	int j = 0;
	while (p && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p || j > i - 1)
		throw "插入位置异常！";
	else {
		Node<T>* s = new Node<T>;
		s->data = e;
		s->next = p->next;
		p->next = s;
	}
}

template<class T>
T LinkList<T>::Delete(int i) { 
	//删除表中第i个元素
	T x;
	Node<T>* p, * q;
	p = head;
	int j = 0;
	while (p->next && j < i - 1) {
		p = p->next;
		j++;
	}
	if (!p->next || j > i - 1)
		throw "删除位置异常！";
	else {
		q = p->next;
		p->next = q->next;
		x = q->data;
		delete q;
		return x;
	}
}

template<class T>
T LinkList<T>::GetElem(int i) {
	//按位查找，获取第i个元素的值
	Node<T>* p;
	p = head->next;
	int j = 1;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	if (!p || j > i)
		throw "查找位置异常！";
	else 
		return p->data;
}

template<class T>
int LinkList<T>::Locate(T e){
	//在链表中查找为e的元素
	Node<T>* p;
	p = head->next;
	int i = 1;
	while (p && p->data != e) {
		p = p->next;
		i++;
	}
	if (p)
		return i;
	else
		return 0;
}

template<class T>
int LinkList<T>::Empty() {
	//测表空
	if (!head->next)
		return 1;
	return 0;
}

template<class T>
int LinkList<T>::Length() {
	//测表长
	Node<T>* p;
	p = head;
	int n = 0;
	while (p->next) {
		p = p->next;
		n++;
	}
	return n;
}

template<class T>
void LinkList<T>::Clear() {
	//清空表
	Node<T>* p, * q;
	p = head->next;
	while (p) {
		q = p->next;
		delete p;
		p = q;
	}
	head->next = NULL;
}

template<class T>
void LinkList<T>::ListDisplay() {
	//遍历输出表中元素
	Node<T>* p;
	p = head->next;
	int n = 1;
	if (!p)
		throw "表中没有元素";
	while (p) {
		cout << "表中第" << n << "个元素为：" << p->data << endl;
		p = p->next;
		n++;
	}
}

链表.h文件：

#pragma once
#include"linkList.h"
#include<conio.h>
template<typename T>
void menu();        //菜单
template<typename T>
void createList(LinkList<T>* list);  //建表
template<typename T>
void add(LinkList<T>* list);		    //增加元素
template<typename T>
void dele(LinkList<T>* list);	    //删除元素
template<typename T>
void get(LinkList<T>* list);			//按位查找
template<typename T>
void locate(LinkList<T>* list);		//按值查找
template<typename T>
void empty(LinkList<T>* list);		//测表空
template<typename T>
void length(LinkList<T>* list);		//测表长
template<typename T>
void clear(LinkList<T>* list);		//清空
template<typename T>
void print(LinkList<T>* list);		//打印表

链表.cpp文件：

#include"链表.h"

template<typename T>
void menu()        //菜单
{
	cout << "************************" << endl;
	cout << "*****  1.建表      *****" << endl;
	cout << "*****  2.增加元素  *****" << endl;
	cout << "*****  3.删除元素  *****" << endl;
	cout << "*****  4.按位查找  *****" << endl;
	cout << "*****  5.按值查找  *****" << endl;
	cout << "*****  6.测表空    *****" << endl;
	cout << "*****  7.表长      *****" << endl;
	cout << "*****  8.清空      *****" << endl;
	cout << "*****  9.打印表    *****" << endl;
	cout << "*****  0.退出      *****" << endl;
	cout << "************************" << endl;
}

template<typename T>
void createList(LinkList<T>* list)  //建表
{
	system("cls");
	cout << "*****  1.建表      *****" << endl;
	cout << "您需要创建几个元素？" << endl;
	int n;
	cin >> n;
	list->CreateList(n);
	cout << "创建成功！" << endl;
}

template<typename T>
void add(LinkList<T>* list)		    //增加元素
{
	system("cls");
	cout << "*****  2.增加元素  *****" << endl;
	int i;
	T e;
	cout << "您想把元素添加在第几位？" << endl;
	cin >> i;
	cout << "您想添加的元素是？" << endl;
	cin >> e;
	list->Insert(i, e);
	cout << "添加成功！" << endl;
}

template<typename T>
void dele(LinkList<T>* list)	    //删除元素
{
	system("cls");
	cout << "*****  3.删除元素  *****" << endl;
	int i;
	cout << "您想删除第几位元素？" << endl;
	cin >> i;
	T e = list->Delete(i);
	cout << "已成功删除第" << i << "位元素：" << e << endl;
}

template<typename T>
void get(LinkList<T>* list)			//按位查找
{
	system("cls");
	cout << "*****  4.按位查找  *****" << endl;
	int i;
	cout << "您要查找哪一位？" << endl;
	cin >> i;
	T e = list->GetElem(i);
	cout << "表中第" << i << "位元素为：" << e << endl;
}

template<typename T>
void locate(LinkList<T>* list)		//按值查找
{
	system("cls");
	cout << "*****  5.按值查找  *****" << endl;
	T e;
	cout << "您想在表中查找哪个元素？" << endl;
	cin >> e;
	int i = list->Locate(e);
	if (i) {
		cout << "元素" << e << "在表中第" << i << "位" << endl;
	}
	else {
		cout << "未找到该元素" << endl;
	}
}

template<typename T>
void empty(LinkList<T>* list)		//测表空
{
	system("cls");
	cout << "*****  6.测表空    *****" << endl;
	if (list->Empty())
		cout << "表空" << endl;
	else
		cout << "表非空" << endl;
}

template<typename T>
void length(LinkList<T>* list)		//测表长
{
	system("cls");
	cout << "*****  7.表长      *****" << endl;
	cout << "表长为：" << list->Length() << endl;
}

template<typename T>
void clear(LinkList<T>* list)		//清空
{
	system("cls");
	cout << "*****  8.清空      *****" << endl;
	cout << "是否确认清空?按“1”确认，其他键取消操作" << endl;
	char c = _getch();
	if (c == '1') {
		list->Clear();
		cout << "已清空" << endl;
	}
	else {
		cout << "取消操作成功" << endl;
	}
}

template<typename T>
void print(LinkList<T>* list)		//打印表
{
	system("cls");
	cout << "*****  9.打印表    *****" << endl;
	list->ListDisplay();
}

test.cpp文件：

#include"链表.h"
#include"链表.cpp"


int main() {

	//生成对象
	LinkList<char> list;

	while (true) {

		system("cls");

		//菜单
		menu<int>();

		//用户选择
		char choice;
		choice = _getch();
		
		//系统接收
		try {
			switch (choice) {
			case '1':
				createList(&list);
				break;

			case '2':
				add(&list);
				break;

			case '3':
				dele(&list);
				break;

			case '4':
				get(&list);
				break;

			case '5':
				locate(&list);
				break;

			case '6':
				empty(&list);
				break;

			case '7':
				length(&list);
				break;

			case '8':
				clear(&list);
				break;

			case '9':
				print(&list);
				break;

			case '0':
				system("cls");
				cout << "再见！" << endl;
				system("pause");
				return 0;
				break;
			default:
				continue;
			}
		}
		catch (const char* s) {
			cout << s << endl;
		}

		system("pause");

	}

	system("pause");
	return 0;

}

作者留言

        本文代码使用的IDE工具为Visual Studio 2019。作者是个菜鸟，欢迎各位大佬留言指错。