数据结构与算法---线性表

线性表

1.顺序表

需求分析

/*
	创建顺序表

	具体功能：
		初始化顺序表
		销毁顺序表
		获取顺序表元素个数
		输出顺序表中的内容
		自动扩容

		增 --- 插入数据（包含了尾部添加功能）
		删 --- 删除数据（包含了尾部删除功能）
		改 --- 修改数据
		查 --- 查找数据

		尾部追加
		尾部删除
 */

C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>


// 定义顺序表存储的数据类型
typedef int dataType;


// 定义顺序表结构
typedef struct SeqList {
	dataType* arr;	// 用来记录表的地址
	int capacity;	// 用来记录表的容量
	int size;		// 用来记录表中元素的个数
}SeqList;


// 功能声明：
// ----------------------------------------------------
bool initList(SeqList&, int);				// 初始化顺序表
void destroyList(SeqList&);					// 销毁顺序表
int sizeList(SeqList&);						// 获取顺序表元素个数
void printList(SeqList&);					// 输出顺序表中的内容
bool expandList(SeqList&, int);				// 自动扩容
// ----------------------------------------------------
bool insertList(SeqList&, dataType, int);		// 增
bool deleteList(SeqList&, int);					// 删
bool modifyList(SeqList&, dataType, int);		// 改
int findList(SeqList&, dataType);				// 查
// ----------------------------------------------------
bool appendList(SeqList&, dataType);	// 尾部追加数据 --- 增的扩展
bool popList(SeqList&);					// 删除尾部数据 --- 删的扩展
// ----------------------------------------------------



int main()
{
	// 创建顺序表
	SeqList myList;

	// 初始化顺序表
	bool res = initList(myList, 5);		// 指定顺序表的数据空间为5个
	(res == true) ? printf("顺序表初始化成功！\n") : printf("顺序表初始化失败！\n");

	// 获取顺序表元素个数
	int size = sizeList(myList);
	printf("顺序表中元素的个数：%d\n", size);

	// 输出顺序表中的内容
	printList(myList);

	// 插入数据
	insertList(myList, 10, 0);
	insertList(myList, 20, 0);
	insertList(myList, 30, 0);
	insertList(myList, 40, 0);
	printList(myList);

	// 删除数据
	deleteList(myList, 2);			// 删除顺序表中下标为2的元素
	printList(myList);

	// 修改数据
	modifyList(myList, 66, 2);		// 将顺序表中下标为2的元素修改为66
	printList(myList);

	// 查找数据
	int searchTarget = 40;
	int index = findList(myList, searchTarget);
	printf("元素%d的下标：%d\n", searchTarget, index);

	// 尾部追加
	appendList(myList, 50);
	printList(myList);

	// 尾部删除
	popList(myList);
	printList(myList);

	// 销毁顺序表
	destroyList(myList);

	char justPause = getchar();		// 让程序暂停一下
	return 0;
}


// 功能实现：
// ----------------------------------------------------
// 初始化顺序表
bool initList(SeqList& sl, int capacity)
{
	// 开辟空间，形成一个表，并记录表的地址
	sl.arr = (dataType*)malloc(sizeof(dataType) * capacity);
	if (sl.arr == NULL)	return false;	// 开辟空间失败

	// 其他初始化操作
	sl.capacity = capacity;		// 初始化表的容量
	sl.size = 0;				// 初始化表中元素的个数
	return true;
}

// 销毁顺序表
void destroyList(SeqList& sl)
{
	free(sl.arr);		// 释放内存空间
	sl.arr = NULL;
	sl.size = 0;
	sl.capacity = 0;
}

// 获取顺序表元素个数
int sizeList(SeqList& sl)
{
	return sl.size;
}

// 输出顺序表中的内容
void printList(SeqList& sl)
{
	printf("[ ");
	for (int i = 0; i < sl.size; i++)
	{
		printf("%d, ", sl.arr[i]);
	}
	printf("]\n");
}

// 自动扩容
bool expandList(SeqList& sl, int size)
{
	// 开辟一片新内存空间
	dataType* p = (dataType*)malloc(sizeof(dataType) * (sl.capacity + size));
	if (sl.arr == NULL)	return false;		// 扩容失败

	// 开辟成功，将数据迁移到新的空间
	for (int i = 0; i < sl.size; i++)
	{
		p[i] = sl.arr[i];
	}

	// 释放原来的空间
	free(sl.arr);

	// 更新数据
	sl.capacity += size;
	sl.arr = p;
	p = NULL;

	return true;
}

// ----------------------------------------------------

// 插入数据
bool insertList(SeqList& sl, dataType element, int index)
{
	// 判断下标是否合法
	if (index < 0 || index > sl.size)	return false;

	// 判断顺序表是否已经满了，如果满了，进行扩容操作
	if (sl.size == sl.capacity)
	{
		if (expandList(sl, 10) == false)	return false;	// 扩容：10个数据空间
	}

	// 元素迁移
	for (int i = sl.size; i > index; --i)
	{
		sl.arr[i] = sl.arr[i - 1];
	}

	// 在目标位置插入元素
	sl.arr[index] = element;

	// 更新表中元素的个数
	sl.size++;

	return true;
}

// 删除数据
bool deleteList(SeqList& sl, int index)
{
	// 判断表是否为空
	if (sl.size == 0)	return false;

	// 判断插入的下标是否合法
	if (index < 0 || index > sl.size - 1)	return false;

	// 数据覆盖
	for (int i = index; i < sl.size - 1; i++)
	{
		sl.arr[i] = sl.arr[i + 1];
	}

	// 更新数据
	sl.size--;	// 这里实现了逻辑删除，而不是实际删除，因为也没有必要进行实际删除

	return true;
}

// 修改数据
bool modifyList(SeqList& sl, dataType element, int index)
{
	// 判断插入的下标是否合法
	if (index < 0 || index > sl.size - 1)		return false;

	// 修改数据
	sl.arr[index] = element;
	return true;
}

// 查找数据
int findList(SeqList& sl, dataType element)
{
	for (int i = 0; i < sl.size; i++)
	{
		if (sl.arr[i] == element)		return i;
	}
	return -1;		// 查找不到元素，返回-1
}

// ----------------------------------------------------

// 尾部追加
bool appendList(SeqList& sl, dataType element)
{
	return insertList(sl, element, sl.size);
}

// 尾部删除
bool popList(SeqList& sl)
{
	return deleteList(sl, sl.size - 1);
}

C++实现

#include <iostream>


// 定义顺序表类
template<class T>	// 顺序表存储的数据类型为T
class SeqList
{
private:
	// 顺序表的属性:
	T* arr;			// 记录表的地址
	int capacity;	// 记录表的容量
	int size;		// 记录表中元素的个数

public:
	// 顺序表提供的方法（类内声明）
	// ----------------------------------------------------
	SeqList();							// 初始化顺序表
	~SeqList();							// 销毁顺序表
	int sizeList();						// 获取顺序表元素个数
	void printList();					// 输出顺序表中的内容
	bool expandList();					// 自动扩容
	// ----------------------------------------------------
	bool insertList(T, int);		// 增
	bool deleteList(int);			// 删
	bool modifyList(T, int);		// 改
	int findList(T);				// 查
	// ----------------------------------------------------
	bool appendList(T);			// 尾部追加数据 --- 增的扩展
	bool popList();				// 删除尾部数据 --- 删的扩展
	// ----------------------------------------------------
};



int main()
{
	// 创建顺序表 + 初始化顺序表
	SeqList<int> sl;

	// 获取顺序表元素个数
	int size = sl.sizeList();
	printf("顺序表中元素的个数：%d\n", size);

	// 输出顺序表中的内容
	sl.printList();

	// 插入数据
	sl.insertList(10, 0);
	sl.insertList(20, 0);
	sl.insertList(30, 0);
	sl.insertList(40, 0);
	sl.printList();

	// 删除数据
	sl.deleteList(2);		// 删除顺序表中下标为2的元素
	sl.printList();

	// 修改数据
	sl.modifyList(66, 2);	// 将顺序表中下标为2的元素修改为66
	sl.printList();

	// 查找数据
	int searchTarget = 40;
	int index = sl.findList(searchTarget);
	printf("元素%d的下标：%d\n", searchTarget, index);

	// 尾部追加
	sl.appendList(50);
	sl.printList();

	// 尾部删除
	sl.popList();
	sl.printList();

	// 销毁顺序表
	// 不用手动销毁，因为对象被回收时会自动调用析构函数

	system("pause");		// 让程序暂停一下
	return 0;
}


// 顺序表提供的方法（类外实现）
// ----------------------------------------------------
// 初始化顺序表
template<class T>
SeqList<T>::SeqList()
{
	this->arr = new T[capacity];		// 创建表空间
	this->capacity = capacity;			// 记录表的容量
	this->size = 0;						// 记录表中元素的个数
}

// 销毁顺序表
template<class T>
SeqList<T>::~SeqList()
{
	delete this->arr;		// 释放表空间
	this->capacity = 0;		// 容量大小置空
	this->size = 0;			// 元素个数置空
}

// 获取顺序表元素个数
template<class T>
int SeqList<T>::sizeList()
{
	return this->size;
}

// 输出顺序表中的内容
template<class T>
void SeqList<T>::printList()
{
	std::cout << "[ ";
	for (int i = 0; i < this->size; i++)
	{
		std::cout << this->arr[i] << ", ";
	}
	std::cout << "]" << std::endl;
}

// 自动扩容
template<class T>
bool SeqList<T>::expandList()
{
	// 开辟新的内存空间
	T* temp = new T[this->capacity + 10];	// 每次扩容10个空间
	if (temp == nullptr)	return false;

	// 将数据迁移到新的内存空间
	for (int i = 0; i < this->size; i++)
	{
		temp[i] = this->arr[i];
	}

	// 释放原来的空间
	delete this->arr;

	// 更新数据
	this->arr = temp;
	this->capacity += size;
	temp = nullptr;
	return true;
}

// ----------------------------------------------------

// 插入数据
template<class T>
bool SeqList<T>::insertList(T element, int index)
{
	// 判断下标是否合法
	if (index < 0 || index > this->size)	return false;

	// 判断顺序表是否已经满了，如果满了，进行扩容操作
	if (this->size == this->capacity)	expandList();

	// 元素迁移
	for (int i = size; i > index; i--)
	{
		this->arr[i] = this->arr[i - 1];
	}

	// 在目标位置插入元素
	this->arr[index] = element;

	// 更新数据
	this->size++;

	return true;
}

// 删除数据
template<class T>
bool SeqList<T>::deleteList(int index)
{
	// 判断下标是否合法
	if (index < 0 || index > this->size - 1)	return false;

	// 数据覆盖
	for (int i = index; i < this->size - 1; i++)
	{
		this->arr[i] = this->arr[i + 1];
	}

	// 更新数据
	this->size--;

	return true;
}

// 修改数据
template<class T>
bool SeqList<T>::modifyList(T element, int index)
{
	// 判断下标是否合法
	if (index < 0 || index > this->size - 1)	return false;

	// 修改数据
	this->arr[index] = element;

	return true;
}

// 查找数据
template<class T>
int SeqList<T>::findList(T element)
{
	for (int i = 0; i < this->size; i++)
	{
		if (this->arr[i] == element)	return i;
	}
	return -1;		// 查找不到结果，返回-1
}

// ----------------------------------------------------

// 尾部追加
template<class T>
bool SeqList<T>::appendList(T element)
{
	return insertList(element, this->size);
}

// 尾部删除
template<class T>
bool SeqList<T>::popList()
{
	return deleteList(this->size - 1);
}

2.链表

需求分析

/*
	创建链表

	具体功能：
		初始化链表
		销毁链表
		获取链表元素个数
		输出链表中的内容

		插入数据
		删除数据
		修改数据
		查找数据

		尾部追加
		尾部删除
 */

C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>


// 数据类型
typedef int dataType;


// 节点的结构
typedef struct Node
{
	dataType data;		// 用来存放数据
	Node* next;			// 用来存放下一个节点的内存地址
}Node;


// // -------------------------- 功能声明 --------------------------
void init(Node*);
int size(Node*);
void print(Node*);
bool insert(Node*, dataType, int);
bool remove(Node*, int);
bool modify(Node*, dataType, int);
int find(Node*, dataType);
bool append(Node*, dataType);
bool pop(Node*);
void destroy(Node*);

int main()
{
	// 创建链表 (创建一个头节点)
	Node headNode;

	// 初始化链表 (初始化头节点)
	init(&headNode);

	// 获取链表元素个数
	printf("链表元素的个数：%d\n", size(&headNode));

	// 输出链表中的内容
	print(&headNode);

	// 插入数据
	insert(&headNode, 66, 1);
	insert(&headNode, 77, 1);
	insert(&headNode, 88, 1);
	print(&headNode);

	// 删除数据
	remove(&headNode, 1);
	print(&headNode);

	// 修改数据
	modify(&headNode, 99, 0);
	print(&headNode);

	// 查找数据
	int index = find(&headNode, 66);
	(index == -1) ? printf("查找不到此数据！\n") : printf("查到此数据的下标：%d\n", index);

	// 尾部追加
	append(&headNode, 6666);
	print(&headNode);

	// 尾部删除
	pop(&headNode);
	print(&headNode);

	// 销毁链表
	destroy(&headNode);

	char justPause = getchar();		// 让程序暂停
	return 0;
}

// -------------------------- 功能实现 --------------------------
// 初始化链表
void init(Node* node)
{
	node->next = NULL;
}

// 获取链表元素个数
int size(Node* node)
{
	// 默认就有1个元素 (即:头节点)
	int size = 1;

	// node 是一个整体，请把 node->next 也看作是一个整体，如果 node->next 这个整体不为 NULL，说明这个整体对应的空间有数据(元素)！！
	while (node->next)
	{
		size++;
		node = node->next;
	}
	return size;
}

// 输出链表中的内容
void print(Node* node)
{
	printf("(*) -> ");
	while (node->next)
	{
		node = node->next;
		printf("%d -> ", node->data);
	}
	printf("\n");
}

// 插入数据
bool insert(Node* node, dataType element, int index)
{
	// 检查下标是否合法 (检查左边界)
	if (index < 1)	return false;

	// 根据index确定步长，将node更新(移动)对应的次数
	// 更新(移动)结束后，node关联的就是要被插的节点的上一个节点
	while (--index)
	{
		node = node->next;
		if (node == NULL)	return false;
	}

	// 将数据放到新节点中
	Node* temp = (Node*)malloc(sizeof(Node));	// 申请一块内存作为新节点
	if (temp == NULL)	return false;			// 申请内存空间失败
	temp->data = element;	// 在新节点里面存放要插入的数据

	// 完成节点的插入 (下面代码顺序不可替换!!)
	temp->next = node->next;
	node->next = temp;

	return true;
}

// 删除数据
bool remove(Node* node, int index)
{
	// 检查下标是否合法 (检查左边界)
	if (index < 1)	return false;

	// 根据index确定步长，将node更新(移动)对应的次数
	// 更新(移动)结束后，node关联的就是要被删除的节点的上一个节点
	while (--index)
	{
		node = node->next;
		if (node == NULL)	return false;
	}

	// 删除节点
	Node* temp = node->next;			// 先引用一下待会将要被删除的节点，防止丢失内存地址而无法真正删除
	node->next = node->next->next;		// 实现逻辑删除
	free(temp);							// 释放内存空间，实现了真正的删除，并且回收了资源

	return true;
}

// 修改数据
bool modify(Node* node, dataType element, int index)
{
	// 检查下标是否合法 (检查左边界)
	if (index < 1)	return false;

	// 根据index确定步长，将node更新(移动)对应的次数
	// 更新(移动)结束后，node关联的就是要被修改的节点的上一个节点
	while (--index)
	{
		node = node->next;
		if (node == NULL)	return false;
	}

	// 修改数据
	node->next->data = element;

	return true;
}

// 查找数据
int find(Node* node, dataType element)
{
	int index = 0;		// 头节点的下标为0，其他节点的下标可以在此基础上通过累加计算得到
	while (node->next)
	{
		node = node->next;
		index++;
		if (node->data == element)	return index;	// 找到了数据，返回对应的下标号
	}
	return -1;		// 找不到数据，返回-1
}

// 尾部追加
bool append(Node* node, dataType element)
{
	// 一直循环，直到 node->next 整体为NULL为止
	// 循环结束后，此时的 node 关联着最后一个节点
	while (node->next)
	{
		node = node->next;
	}

	Node* temp = (Node*)malloc(sizeof(Node));	// 申请内存空间，制作新节点
	if (temp == NULL)	return false;			// 申请失败

	// 将数据放到到新节点中
	temp->data = element;
	temp->next = NULL;

	// 尾节点指向新节点
	node->next = temp;

	return true;
}

// 尾部删除
bool pop(Node* node)
{
	// 如果这个链表只有头节点，而没有后面的数据节点：
	if (node->next == NULL)	return false;

	// 如果有数据节点：
	// 一直循环，直到 node->next 整体为NULL为止
	// 循环结束后，此时的 node 关联的是最后一个节点，而 prev 则关联着倒数第二个节点
	Node* prev = NULL;
	while (node->next)
	{
		prev = node;		// 先记录旧的node
		node = node->next;	// 再创建新的node
	}

	// 释放最后一个节点的内存
	free(node);

	// 将倒数第二个节点的next指向NULL
	prev->next = NULL;

	return true;
}

// 销毁链表
void destroy(Node* node)
{
	// 释放头节点以外的所有节点的内存空间，堆区的空间
	// 注意：不可手动释放头节点的内存空间，因为它是main主函数的变量，栈区里面的变量
	Node* temp = NULL;
	while (node->next)
	{
		temp = node->next;	// 先备份一下节点的指针
		node->next = node->next->next;
		free(temp);
	}
}

C++实现

#include<iostream>


// 节点
template <class T>
class Node
{
public:
	T data;				// 用来存放数据
	Node<T>* next;		// 用来存放下一个节点的内存地址

	// 构造函数
	Node()
	{
		this->next = nullptr;
	}

	// 析构函数
	~Node()
	{
		this->next = nullptr;
	}
};


// 链表
template<class T = int>		// 默认模板参数为int类型
class Link
{
private:
	Node<T>* head;		// 用来记录头节点指针
	int size;			// 用来记录链表中元素的个数

public:
	// -------------------------- 功能类内声明 --------------------------
	Link();
	~Link();
	int getSize();
	void printLink();
	bool insert(T, int);
	bool remove(int);
	bool modify(T, int);
	int find(T);
	bool append(T);
	bool pop();
};



int main()
{
	// 创建链表 + 初始化链表
	Link<> myLink;

	// 获取链表元素个数
	printf("链表元素的个数：%d\n", myLink.getSize());

	// 输出链表中的内容
	myLink.printLink();

	// 插入数据
	myLink.insert(66, 1);
	myLink.insert(77, 1);
	myLink.insert(88, 1);
	myLink.insert(99, 1);
	myLink.printLink();

	// 删除数据
	myLink.remove(1);
	myLink.printLink();

	// 修改数据
	myLink.modify(100, 2);
	myLink.printLink();

	// 查找数据
	int index = myLink.find(66);
	(index == -1) ? printf("查找不到此数据！\n") : printf("查到此数据的下标：%d\n", index);

	// 尾部追加
	myLink.append(1024);
	myLink.printLink();

	// 尾部删除
	myLink.pop();
	myLink.printLink();

	// 销毁链表
	// 自动会调用析构函数去销毁链表，无需手动操作

	system("pause");	// 让程序暂停
	return 0;
}


// -------------------------- 功能类外实现 --------------------------
// 初始化链表
template<class T>
Link<T>::Link()
{
	this->head = new Node<T>;	// 创建一个头节点，并让 this->head 能够指向这个头节点
	this->size = 1;				// 链表元素个数
}

// 销毁链表
template<class T>
Link<T>::~Link()
{
	// 释放其他节点
	Node<T>* temp = nullptr;
	while (this->head->next)	// 判断头节点的下一个节点是否为空，如果不为空，说明节点里面有数据，需要删除这个节点
	{
		temp = this->head->next;	// 先备份好内存地址，方便待会删除这个地址所指向的节点
		this->head->next = this->head->next->next;	// 将头节点连接"要被删除节点"的下一个节点
		delete temp;	// 删除节点
	}

	// 释放头节点
	delete this->head;
	this->head = nullptr;

	// 链表元素个数置零
	this->size = 0;
}

// 获取链表元素个数
template<class T>
int Link<T>::getSize()
{
	return this->size;
}

// 输出链表中的内容
template<class T>
void Link<T>::printLink()
{
	Node<T>* temp = this->head->next;	// 头节点的下一个节点
	std::cout << "(*) -> ";
	while (temp)	// 如果 temp 不是 nullptr 空指针，则说明当前节点有数据，可以进入循环内部，输出数据
	{
		std::cout << temp->data << " -> ";
		temp = temp->next;
	}
	std::cout << std::endl;
}

// 插入数据
template<class T>
bool Link<T>::insert(T data, int index)
{
	// 检查下标是否合法，可插入的范围是 [1, this->size]
	if (index < 1 || index > this->size)	return false;

	// 获取目标节点的上一个节点
	Node<T>* targetNodePre = this->head;
	for (int i = 0; i < index - 1; i++)
	{
		targetNodePre = targetNodePre->next;
	}

	// 创建新节点，并将数据存放到里面
	Node<T>* newNode = new Node<T>;
	newNode->data = data;

	// 将新节点插入到链表中
	newNode->next = targetNodePre->next;
	targetNodePre->next = newNode;

	// 更新元素个数
	this->size++;

	return true;
}

// 删除数据
template<class T>
bool Link<T>::remove(int index)
{
	// 检查下标是否合法，可删除的范围是 [1, this->size -1]
	if (index < 1 || index > this->size)	return false;

	// 获取目标节点的上一个节点
	Node<T>* targetNodePre = this->head;
	for (int i = 0; i < index - 1; i++)
	{
		targetNodePre = targetNodePre->next;
	}

	// 删除节点
	Node<T>* temp = targetNodePre->next;	// 先引用一下待会将要被删除的节点，防止丢失内存地址而无法真正删除
	targetNodePre->next = targetNodePre->next->next;	// 实现逻辑删除
	delete temp;	// 释放内存空间，实现了真正的删除，并且回收了资源

	// 更新元素个数
	this->size--;

	return true;
}

// 修改数据
template<class T>
bool Link<T>::modify(T data, int index)
{
	// 检查下标是否合法，可修改的范围是 [1, this->size -1]
	if (index < 1 || index > this->size)	return false;

	// 获取目标节点的上一个节点
	Node<T>* targetNodePre = this->head;
	for (int i = 0; i < index - 1; i++)
	{
		targetNodePre = targetNodePre->next;
	}

	// 修改数据
	targetNodePre->next->data = data;

	return true;
}

// 查找数据
template<class T>
int Link<T>::find(T data)
{
	int index = 0;		// 头节点的下标为0，其他节点的下标可以在此基础上通过累加计算得到
	Node<T>* targetNodePre = this->head;
	while (targetNodePre->next)		// 如果不为空指针nullptr，说明里面有数据
	{
		targetNodePre = targetNodePre->next;
		index++;
		if (targetNodePre->data == data)	return index;	// 找到了数据，返回对应的下标号
	}
	return -1;		// 找不到数据，返回-1
}

// 尾部追加
template<class T>
bool Link<T>::append(T data)
{
	return insert(data, this->size);
}

// 尾部删除
template<class T>
bool Link<T>::pop()
{
	return remove(this->size - 1);
}

3.扩展

双向链表

/*
	C++实现双向链表：
	  1.插入数据
	  2.删除数据
	  3.展示数据
*/

#include<iostream>


// 节点
template<class T>
class Node
{
public:
	T data;
	Node* next;
	Node* prev;

	Node()
	{
		this->next = nullptr;
		this->prev = nullptr;
	}

	~Node()
	{
		this->next = nullptr;
		this->prev = nullptr;
	}
};


// 链表
template<class T = int>
class Link
{
private:
	Node<T>* head;
	int size;

public:
	Link()
	{
		this->head = new Node<T>;
		this->size = 1;
	}

	~Link()
	{
		// 释放其他节点
		Node<T>* temp = nullptr;
		while (this->head->next)
		{
			temp = this->head->next;
			this->head->next = this->head->next->next;
			delete temp;
		}

		// 释放头节点
		delete this->head;
		this->head = nullptr;
		this->size = 0;
	}

	bool insert(T data, int index)
	{
		// 下标合法性校验
		if (index < 1 || index > this->size)	return false;

		// 获取目标节点的前驱节点
		Node<T>* targetNodePre = this->head;
		for (int i = 1; i < index; i++)
		{
			targetNodePre = targetNodePre->next;
		}

		// 创建新节点，并装入数据
		Node<T>* newNode = new Node<T>;
		newNode->data = data;

		// 将新节点插入到链表中		[...targetNodePre <===> targetNodePre->next] <--- newNode
		newNode->next = targetNodePre->next;
		newNode->prev = targetNodePre;
		if (targetNodePre->next != nullptr)	targetNodePre->next->prev = newNode;
		targetNodePre->next = newNode;

		// 更新节点个数
		this->size++;

		return true;
	}

	bool remove(int index)
	{
		// 下标合法性校验
		if (index < 1 || index > this->size - 1)	return false;

		// 获取目标节点
		Node<T>* targetNode = this->head;
		for (int i = 1; i <= index; i++)
		{
			targetNode = targetNode->next;
		}

		// 删除操作	[targetNode->prev <===> targetNode <===> targetNode->next]
		if (targetNode->next != nullptr)	targetNode->next->prev = targetNode->prev;
		targetNode->prev->next = targetNode->next;
		delete targetNode;

		// 更新节点个数
		this->size--;

		return true;
	}

	void printLink()
	{
		std::cout << "(*) <==> ";
		Node<T>* temp = this->head;
		while (temp->next)
		{
			temp = temp->next;
			std::cout << temp->data << " <==> ";
		}
		std::cout << std::endl;
	}
};


// 主函数
int main()
{
	// 创建链表并初始化
	Link<int> myLink;
	myLink.printLink();

	// 插入数据
	myLink.insert(10, 1);
	myLink.printLink();

	myLink.insert(20, 2);
	myLink.printLink();

	myLink.insert(30, 3);
	myLink.printLink();

	// 删除数据
	myLink.remove(1);
	myLink.printLink();

	myLink.remove(1);
	myLink.printLink();

	myLink.remove(1);
	myLink.printLink();

	system("pause");
	return 0;
}

循环链表

在这里插入图片描述

特殊线性表

1.栈

通过顺序表实现

// C++

#include<iostream>
#include<string>
using namespace std;


template<class T>
class Stack
{
public:
	T* arr;			// 栈空间
	int capacity;	// 栈的容量
	int top;		// 用于记录栈顶的位置

	Stack()
	{
		this->arr = new T[10];		// 开辟空间
		this->capacity = 10;
		this->top = -1;
	}

	~Stack()
	{
		delete[] this->arr;			// 释放空间
		this->capacity = 0;
		this->top = -1;
	}

	// 入栈
	Stack& push(T data)
	{
		top++;
		this->arr[top] = data;
		return *this;
	}

	// 出栈
	Stack& pop()
	{
		top--;
		return *this;
	}

	// 输出栈里面的内容
	void show()
	{
		string symbol = "";
		for (int i = 0; i <= top; i++)
		{
			symbol += "----";
		}
		cout << "*" << symbol << endl << "| ";
		for (int i = 0; i <= top; i++)
		{
			std::cout << this->arr[i] << "  ";
		}
		cout << endl << "*" << symbol << endl << endl;
	}
};


int main()
{
	Stack<int> s;

	// 入栈
	s.push(10);
	s.push(20);
	s.push(30).show();

	// 出栈
	s.pop().show();
	s.pop().show();
	s.pop().show();

	system("pause");
	return 0;
}

通过链表实现

// C++

#include<iostream>
#include<string>
using namespace std;


// 节点
template<class T>
class Node
{
public:
	T data;
	Node* next;

	Node()
	{
		this->next = nullptr;
	}
};


// 栈（通过链表实现的栈）
template<class T>
class Stack
{
public:
	Node<T>* head;		// 头节点
	int size;			// 用于记录栈中的元素个数

	Stack()
	{
		this->head = new Node<T>;	// 创建头节点
		this->size = 0;
	}

	~Stack()
	{
		// 释放其他节点
		Node<T>* temp = nullptr;
		while (this->head->next)
		{
			temp = this->head->next;
			this->head->next = this->head->next->next;
			delete temp;
		}

		// 释放头节点
		delete this->head;
		this->head = nullptr;
		this->size = 0;
	}

	// 入栈
	Stack& push(T data)
	{
		// 创建新节点，并存放数据
		Node<T>* newNode = new Node<T>;
		newNode->data = data;

		// 插入新节点
		newNode->next = this->head->next;
		this->head->next = newNode;

		// 更新元素个数
		size++;

		return *this;
	}

	// 出栈
	Stack& pop()
	{
		// 删除节点
		Node<T>* temp = nullptr;
		if (this->head->next)
		{
			temp = this->head->next;
			this->head->next = this->head->next->next;
			delete temp;
		}

		// 更新元素个数
		size--;

		return *this;
	}

	// 输出栈里面的内容
	void show()
	{
		string symbol = "";
		for (int i = 0; i < this->size; i++)
		{
			symbol += "----";
		}
		cout << "*" << symbol << endl << "| ";

		if (this->size == 0)
		{
			cout << endl << "*" << symbol << endl << endl;
			return;
		}

		Node<T>** arr = new Node<T>*[this->size];
		int index = 0;

		Node<T>* temp = this->head;
		while (temp->next)
		{
			temp = temp->next;
			arr[index] = temp;
			index++;
		}

		for (int i = this->size - 1; i > -1; i--)
		{
			std::cout << arr[i]->data << "  ";
		}
		cout << endl << "*" << symbol << endl << endl;

		delete[] arr;
	}
};


int main()
{
	Stack<int> s;

	// 入栈
	s.push(10);
	s.push(20);
	s.push(30).show();

	// 出栈
	s.pop().show();
	s.pop().show();
	s.pop().show();

	system("pause");
	return 0;
}

2.队列

通过顺序表实现

在这里插入图片描述

// C++

#include<iostream>
#include<string>
using namespace std;

// 队列所存储数据的类型
typedef int E;


// 队列 (通过顺序表实现循环队列)
class Queue
{
public:
	E* arr;			// 用于记录队列的内存地址
	int capacity;	// 用于记录队列的容量
	int size;		// 用于记录队列中元素的个数
	int front;		// 用于记录队首位置
	int rear;		// 用于记录队尾位置

	Queue()
	{
		this->capacity = 5;
		this->arr = new E[this->capacity];
		this->size = 0;
		this->front = this->rear = 0;
	}

	~Queue()
	{
		delete[] this->arr;
		this->arr = nullptr;
		this->capacity = 0;
		this->size = 0;
		this->front = this->rear = 0;
	}

	// 入队
	Queue& enqueue(E data)
	{
		// 判断队列是否已满
		if (this->size == this->capacity)	return *this;

		// 循环入队
		this->arr[rear] = data;
		this->size++;
		this->rear++;
		this->rear %= this->capacity;		// 循环队列的核心算法

		return *this;
	}

	// 出队
	Queue& dequeue()
	{
		// 判断队列是否为空
		if (size == 0)	return *this;

		// 循环出队
		this->front++;
		this->size--;
		this->front %= this->capacity;		// 循环队列的核心算法

		return *this;
	}

	// 输出
	void show()
	{
		string symbol = "";
		for (int i = 0; i < this->size; i++)
		{
			symbol += "<<<<";
		}
		if (this->size == 0)	symbol = "<<<<";
		cout << symbol << endl;
		for (int i = this->front; i < this->front + this->size; i++)
		{
			cout << this->arr[i % this->capacity] << "  ";
		}
		cout << endl << symbol << endl << endl;
	}
};

int main()
{
	Queue q;	// 创建并初始化队列
	q.show();	// 输出队列里面的内容

	// 入队
	q.enqueue(10).show();
	q.enqueue(20).show();
	q.enqueue(30).show();

	// 出队
	q.dequeue().show();
	q.dequeue().show();
	q.dequeue().show();

	system("pause");
	return 0;
}

通过链表实现

在这里插入图片描述

// C++

#include<iostream>
#include<string>
using namespace std;

// 队列所存储数据的类型
typedef int E;

// 节点
class Node
{
public:
	E data;
	Node* next;

	Node()
	{
		this->next = nullptr;
	}
};

// 队列 (通过顺序表实现循环队列)
class Queue
{
public:
	Node* head;		// 头节点（队首）
	Node* tail;		// 尾节点（队尾）
	int size;		// 用于记录队列中元素的个数

	Queue()
	{
		this->head = new Node;
		this->tail = this->head;
		this->size = 0;
	}

	~Queue()
	{
		// 释放其他节点
		Node* temp = nullptr;
		while (this->head->next)
		{
			temp = this->head->next;
			this->head->next = this->head->next->next;
			delete temp;
		}

		// 释放头节点
		delete this->head;
		this->head = this->tail = nullptr;
		this->size = 0;
	}

	// 入队
	Queue& enqueue(E data)
	{
		// 创建新节点，并存入数据
		Node* newNode = new Node;
		newNode->data = data;
		newNode->next = nullptr;

		// 将新节点插入到队尾
		this->tail->next = newNode;
		this->tail = newNode;

		// 更新数据
		this->size++;

		return *this;
	}

	// 出队
	Queue& dequeue()
	{
		// 回收内存空间
		Node* temp = nullptr;
		if (this->head->next)
		{
			temp = this->head->next;
			this->head->next = this->head->next->next;
			delete temp;
		}

		// 更新数据
		this->size--;

		return *this;
	}

	// 输出
	void show()
	{
		string symbol = "";
		for (int i = 0; i < this->size; i++)
		{
			symbol += "<<<<";
		}
		if (this->size == 0)	symbol = "<<<<";
		cout << symbol << endl;
		Node* temp = this->head;
		while (temp->next)
		{
			temp = temp->next;
			cout << temp->data << "  ";
		}
		cout << endl << symbol << endl << endl;
	}
};

int main()
{
	Queue q;	// 创建并初始化队列
	q.show();	// 输出队列里面的内容

	// 入队
	q.enqueue(10).show();
	q.enqueue(20).show();
	q.enqueue(30).show();

	// 出队
	q.dequeue().show();
	q.dequeue().show();
	q.dequeue().show();

	system("pause");
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/591159.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

(ARM)ORACLE JDK 22 的下载安装及环境变量的配置

(ARM)ORACLE JDK 22 的下载安装及环境变量的配置

目录 获取JDK 安装JDK 配置JAVA环境变量 其他补充&#xff1a;JDK 22的新特征 1. 语法 2. 库 3. 性能 4. 工具 在今年的3月份&#xff0c;ORACLE 更新了的JDK 发行版 JDK 22&#xff0c;作为了一位ORACLE Primavera系列产品的研究者&#xff0c;其实对JDK的迭代完全不感…
阅读更多...
基于.NET WinForms 数据的CURD实现

基于.NET WinForms 数据的CURD实现

开发工具 VS 2022 C#&#xff0c;数据库MS SQL SERVER 2019 1.WinForms界面 2.使用SqlDataApater DataSet DataGridView 读取数据 private void ReadData() {//数据库连接串string strConn "Data Source127.0.0.1;Initial CatalogTEST;Persist Security InfoTrue;Us…
阅读更多...
Vue 组件通信

Vue 组件通信

组件通信 组件与组件之间的数据传递 组件的数据是独立的&#xff0c;无法直接访问其他组件的数据。通过组件通信&#xff0c;可以访问其他组件的数据。 组件关系 父子关系非父子关系 组件通信解决方案 父子关系 父->子 父组件通过props将数据传递给子组件 App.vue …
阅读更多...
模式识别作业：颜色算子的三种阈值分割算法

模式识别作业：颜色算子的三种阈值分割算法

一、引言&#xff1a; 在图像处理中&#xff0c;我们往往需要提取图像的一些关键信息&#xff0c;比如本篇文章的内容——提取颜色&#xff0c;然而当我们需要提取某一种颜色时&#xff0c;无论图像余下的部分如何“丰富多彩”&#xff0c;他们都不再重要&#xff0c;需要被忽…
阅读更多...
IDEA2024版本控制台乱码怎么解决？

IDEA2024版本控制台乱码怎么解决？

在使用最新版本的IDEA时&#xff0c;可能会遇到控制台输出乱码问题&#xff1f; 在网上找了很多办法&#xff0c;修改了IDEA的vmoptions文件也没有用,最后发现原来是要修改这里 Setting>>Build&#xff0c;Execution,Deployment>>Runnr中的VM Options配置&#xf…
阅读更多...
Vue进阶之Vue项目实战（一）

Vue进阶之Vue项目实战（一）

Vue项目实战 项目搭建初始化eslint版本约束版本约束eslint配置 stylelintcspellcz-githusky给拦截举个例子 zx 项目搭建 node版本&#xff1a;20.11.1 pnpm版本&#xff1a;9.0.4 初始化 vue3最新的脚手架 pnpm create vite byelide-demo --template vue-ts pnpm i pnpm dev…
阅读更多...
2024年 Java 面试八股文——Mybatis篇

2024年 Java 面试八股文——Mybatis篇

目录 1. 什么是Mybatis&#xff1f; 2. 说说Mybatis的优缺点 3. Xml映射文件中&#xff0c;都有哪些标签 4. #{}和&{}有什么区别 5. Mybatis是如何进行分页的,分页插件的原理是什么 6. Mybatis是如何将sql执行结果封装为目标对象并返回的&#xff1f; 7. Mybatis是怎…
阅读更多...
【副本向】Lua副本逻辑

【副本向】Lua副本逻辑

副本生命周期 OnCopySceneTick() 子线程每次心跳调用 --副本心跳 function x3323_OnCopySceneTick(elapse)if x3323_g_IsPlayerEnter 0 thenreturn; -- 如果没人进入&#xff0c;则函数直接返回endif x3323_g_GameOver 1 thenif x3323_g_EndTick > 0 thenx3323_CountDown…
阅读更多...
简化Transformer模型，以更少的参数实现更快的训练速度

简化Transformer模型，以更少的参数实现更快的训练速度

在深度学习领域&#xff0c;Transformer模型因其卓越的性能而广受欢迎&#xff0c;但其复杂的架构也带来了训练时间长和参数数量多的挑战。ETH Zurich的研究人员Bobby He和Thomas Hofmann在最新研究中提出了一种简化的Transformer模型&#xff0c;通过移除一些非必要的组件&…
阅读更多...
STM32——GPIO篇

STM32——GPIO篇

技术笔记&#xff01; 1. 什么是GPIO&#xff1f; GPIO是通用输入输出端口&#xff08;General-purpose input/output&#xff09;的英文简写&#xff0c;是所有的微控制器必不可少的外设之一&#xff0c;可以由STM32直接驱动从而实现与外部设备通信、控制以及采集和捕获的功…
阅读更多...
wordpress子比主题美化-为图文列表封面添加动态缩略图特效 多种效果演示

wordpress子比主题美化-为图文列表封面添加动态缩略图特效 多种效果演示

wordpress子比主题-为图文列表文章封面添加动态缩略图特效 给自己子比主题加一个列表文章封面添加动态缩略图 直接复制以下代码&#xff0c;添加到主题自定义CSS代码中即可&#xff0c;下图为效果演示 wordpress子比主题-为图文列表文章封面添加动态缩略图特效 给自己子比主题…
阅读更多...
MySQL①——数据库与表格的创建

MySQL①——数据库与表格的创建

今日任务&#xff1a; 创建一个名为“db_classes”的数据库 创建一行名为“db_hero”的表 将四大名著中的常见人物插入这个英雄表 数据库的创建与删除 create 命令&#xff08;创建&#xff09;&#xff1a; create database 数据库名&#xff1b;#参数默认create database …
阅读更多...
Spring MVC（上）

Spring MVC（上）

initApplicationEventMulticaster为上下文初始化 simpleApplicationEventMulticaster怎么处理广播事件的 refisterListeners注册监听器 finishBeanFactoryInitialization初始化非延迟bean 惰性初始化 dispatcherServlet的初始化 servletConfigPropertyValues创建propertyValues…
阅读更多...
虚拟化技术 安装并配置ESXi服务器系统

虚拟化技术 安装并配置ESXi服务器系统

安装并配置ESXi服务器系统 一、实验目的与要求 1.掌握创建VMware ESXi虚拟机 2.掌握安装VMware ESXi系统 3.掌握配置VMware ESXi系统的管理IP 4.掌握开启VMware ESXi的shell和ssh功能的方法 二、实验内容 1.安装VMware workstation 15或更高版本 2.创建VMware ESXi虚拟…
阅读更多...
软件杯 深度学习的动物识别

软件杯 深度学习的动物识别

文章目录 0 前言1 背景2 算法原理2.1 动物识别方法概况2.2 常用的网络模型2.2.1 B-CNN2.2.2 SSD 3 SSD动物目标检测流程4 实现效果5 部分相关代码5.1 数据预处理5.2 构建卷积神经网络5.3 tensorflow计算图可视化5.4 网络模型训练5.5 对猫狗图像进行2分类 6 最后 0 前言 &#…
阅读更多...
分布式事务—＞ seata

分布式事务—＞ seata

分布式事务之Seata 一、什么是分布式事务&#xff1f; 分布式事务是一种特殊类型的事务&#xff0c;它涉及多个分布式系统中的节点&#xff0c;包括事务的参与者、支持事务的服务器、资源服务器以及事务管理器。 在分布式事务中&#xff0c;一次大型操作通常由多个小操作组成…
阅读更多...
排序算法--直接选择排序

排序算法--直接选择排序

前提&#xff1a; 选择排序&#xff1a;选择排序(Selection sort)是一种比较简单的排序算法。它的算法思想是每一次从待排序的数据元素中选出最小(或最大)的一个元素&#xff0c;存放在序列的起始位置&#xff0c;直到全部待排序的数据元素排完。 话不多说&#xff0c;直接放图…
阅读更多...
ResponseHttp

ResponseHttp

文章目录 HTTP响应详解使用抓包查看响应报文协议内容 Response对象Response继承体系Response设置响应数据功能介绍Response请求重定向概述实现方式重定向特点 请求重定向和请求转发比较路径问题Response响应字符数据步骤实现 Response响应字节数据步骤实现 HTTP响应详解 使用抓…
阅读更多...
Web前端一套全部清晰 ⑥ day4 CSS.1 基础选择器、文字控制属性

Web前端一套全部清晰 ⑥ day4 CSS.1 基础选择器、文字控制属性

后来的我不在抱怨 所有的事与愿违都是我能力或者判断力不足 仅此而已 —— 24.5.1 一、CSS定义 1. 将CSS放在html文件的<style>标签中 层叠样式表(Cascading style Sheets&#xff0c;缩写为 CSS)&#xff0c;是一种 样式表 语言&#xff0c;用来描述 HTML 文档的呈现(美…
阅读更多...
LeetCode 面试经典150题 28.找出字符串中第一个匹配项的下标

LeetCode 面试经典150题 28.找出字符串中第一个匹配项的下标

题目&#xff1a;给你两个字符串 haystack 和 needle &#xff0c;请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;。如果 needle 不是 haystack 的一部分&#xff0c;则返回 -1 。 思路&#xff1a;暴力&#xff08;…
阅读更多...
最新文章

Copyright @ 2022~2023