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

时间：2024-05-04 13:10:01

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;
}

相关文章