c++ 实现基本数据结构代码

数据结构是计算机科学的一个重要的分支，主要研究如何有效地存储和组织数据以便于快速访问和操作。

常见的数据结构有：

• 数组：是一种线性的数据结构，可以通过索引来访问数组中的元素。
• 链表：是一种非线性的数据结构，由节点组成，每个节点存储数据并与其他节点相连。
• 栈：是一种特殊的数据结构，只允许在顶部插入和删除元素。
• 队列：是一种特殊的数据结构，只允许在队尾插入元素，在队头删除元素。
• 树：是一种非线性的数据结构，以根节点为核心，通过父节点和子节点的关系构成。
• 图：是一种非线性的数据结构，由节点和边构成，可以表示一组具有特定关系的数据。

#include <iostream>

#include <stack>

#include <vector>

using namespace std;


//数组：实际上是静态的列表，以连续的内存地址存储元素
void arr()
{
	int arr[5] = {1, 2, 3, 4, 5};
	
	for (int i=0; i < 5; ++i)
		{
			cout << arr[i] <<endl;
		}
 	return;
}


//链表：是一种动态的列表，每个元素都是一个节点，包含数据和指向下一个节点的指针
struct ListNode {
	int data;
	ListNode *next;
};


void list()
{
	ListNode *head = new ListNode;
	head->data = 1;
	head->next = new ListNode;
	head->next->data = 2;
	head->next->next = new ListNode;
	head->next->next->data = 3;
	head->next->next->next = nullptr;

	ListNode *node = head;
	while(nullptr != node)
	{
		cout << node->data << endl;
		node = node->next;
	}
	
	return;
}

//栈：是一种后进先出（LIFO）的数据结构，通常使用数组或链表实现

void Stack()
{
	stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);

	while(!s.empty())
	{
		//top()是取栈顶元素，不会删除里面的元素，返回栈顶的引用
		//pop()是删除栈顶元素
		cout << s.top() <<endl;
		s.pop();
	}

	return;
}

//队列 是一种先进先出（FIFO）的数据结构，通常使用数组或链实现

//设置队列最大成员数
const int MAX_SIZE = 100;

class Queue {
	private:
		int data[MAX_SIZE];
		int front, rear;

	public:
		Queue() 
		{
			data[MAX_SIZE] = {0};
			front = 0;
			rear = -1;
		}

		bool isEmpty() 
		{
			return -1 == rear;
		}

		bool isFull() 
		{
			return MAX_SIZE-1 == rear;
		}

		void enqueue(int value) 
		{
			if (isFull()) 
			{
				cout << "Queue is full" << endl;
				//循环队列可以做
				return;
			}

			rear++;
			data[rear] = value;
		}

		void dequeue() 
		{
			if (isEmpty()) 
			{
				cout << "Queue is empty" << endl;
				return;
			}
			front++;
			// 可以做个循环队列
			// if (MAX_SIZE == front)
			// {
			// 	front = 0;
			// }
		}

		int getFront() 
		{
			if (isEmpty()) 
			{
				cout << "Queue is empty" << endl;
				return -1;
			}

			return data[front];
		}
};

void queue()
{
	Queue q;

	int queueSize = 5;
	for (int i = 1; i < queueSize; i++)
	{
		q.enqueue(i);
	}

	for (int i = 1; i < queueSize; i++)
	{
		cout << q.getFront() << endl;
		q.dequeue();
	}

	return;
}

//简单的二叉树 实现了一个二叉搜索树的基本功能，可以插入节点，遍历节点，并输出以中序遍历的形式

struct Node {
	int data;
	Node *left, *right;
};

class Tree {
	public:
		Node *root;
		Tree() {root = nullptr;}

		Node* createNode(int data)
		{
			Node *newNode = new Node;
			newNode->data = data;
			newNode->left = newNode->right = nullptr;
			return newNode;
		}

		void insertNode(Node *&node, int data)
		{
			if (!node)
			{
				node = createNode(data);
				//创建的第一个节点是根节点
				if (!root) 
				{
					root = node;
				}
			}
			//代码可优化
			else if (data < node->data)
			{
				insertNode(node->left, data);
			}
			else
			{
				insertNode(node->right, data);
			}
		}

		//顺序遍历
		void inOrderTraversal(Node *node)
		{
			if (node)
			{
				inOrderTraversal(node->left);
				cout << node->data << " ";
				inOrderTraversal(node->right);
			}
		}
};

void tree()
{
	Tree tree;
	tree.insertNode(tree.root, 50);
	tree.insertNode(tree.root, 30);
	tree.insertNode(tree.root, 20);
	tree.insertNode(tree.root, 40);
	tree.insertNode(tree.root, 70);
	tree.insertNode(tree.root, 60);
	tree.insertNode(tree.root, 80);

	cout << "In-Order Traversal: ";
	tree.inOrderTraversal(tree.root);
	cout << endl;

	return;
}

//图 
class Graph{
	int V; //顶点数
	vector<int> *adj; //领接表

	public:
		Graph(int V)
		{
			this->V = V;
			adj = new vector<int>[V];
		}

		~Graph()
		{
			V = 0;
			delete[] adj;
			adj = nullptr;
		}

		//向图中添加一条边
		void addEdge(int v, int w)
		{
			adj[v].push_back(w);
		}

		//打印图中所有的边
		void printGraph()
		{
			for (int i = 0; i < V; i++)
			{
				cout << "顶点" << i << "的领接点：";
				for (int j = 0; j < adj[i].size(); j++)
				{
					cout << adj[i][j] << " ";
				}
				cout << endl;
			}
		}
};

void graph()
{
	Graph g(5); //创建图
	g.addEdge(0, 1); //添加边
	g.addEdge(0, 4);
	g.addEdge(1, 2);
	g.addEdge(1, 3);
	g.addEdge(1, 4);
	g.addEdge(2, 3);
	g.addEdge(3, 4);

	g.printGraph(); // 打印图中所有的边

	return;
}

//数据结构基本打印

int main()
{
	cout << "array" << endl;
	arr();
	
	cout << "list" << endl;
	list();

	cout << "stack" << endl;
	Stack();

	cout << "queue" << endl;
	queue();

	cout << "tree" << endl;
	tree();

	cout << "graph" << endl;
	graph();

	return 0;
}