这是一个小测试
#include<bits/stdc++.h> using namespace std;
数据结构 本页面是由enum ice Lee所创建，主要是数据结构的复习所用，本页面将包含链表， 栈，队列，图，树，堆这几类数据结构，每类数据结构仅包含定义（数组版，链表版），增删查改（如果支持），遍历方式。
<strong>链表</strong>
补充：线性表（封装过的数组，地址元素都是对应的逻辑上相邻）
代码如下：
#include
#include
#define ElemType int
#define Static int
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100
typedef struct node {
ElemType *elem;
ElemType size;
struct node *next;
}*ListNode,Node;
Static Init_ListNode(ListNode &L){
L = (ListNode)malloc(sizeof(Node));
printf("address: %p\n",L);
L->elem = (ElemType*)malloc(sizeof(ElemType)*(MAXSIZE));
L->size=0;
L->next=nullptr;
return OK;
}
Static Destroy_ListNode(ListNode &L){
free(L);
return OK;
}
Static Delete_Node(ListNode &L,ElemType index){
if(index<0&&index>L->size){
printf("ERROR INDEX\n");
return ERROR;
}
else{
for(int i=index;isize;i++){
L->elem[i-1] = L->elem[i];
}
L->size--;
}
return OK;
}
Static Insert_ListNode(ListNode &L,ElemType index,ElemType e){
if(index<0&&index>L->size){
printf("Index Error\n");
return ERROR;
}
if(L->size == MAXSIZE){
printf("Stack Overflow\n");
return ERROR;
}
for(int i=L->size;i>=index;i--){
L->elem[i]=L->elem[i-1];
}
L->elem[index-1] = e;
L->size++;
return OK;
}
Static Clear_ListNode(ListNode &L){
for(int i=0;i<MAXSIZE;i++) L->elem[i] = 0;
L->size=0;
return OK;
}
Static Get_Elem(ListNode &L,ElemType index){
if(L->size==0){
printf("NULL ELEMENT\n");
return ERROR;
}
if(index<0||index>L->size){
printf("ERROR INDEX\n");
return ERROR;
}
return L->elem[index-1];
}
Static Add_Element(ListNode &L,int index,ElemType e){
if(index<0||index>MAXSIZE){
printf("Error index\n");
return ERROR;
}
}
ListNode L;
int main(){
Init_ListNode(L);
for(int i=0;i<MAXSIZE;i++) L->elem[i] = i;
for(int i=0;i<MAXSIZE;i++) printf("L->elem[%d]: %d\n",i,L->elem[i]);
int Cnt = Get_Elem(L,10);
printf("Cnt: %d\n",Cnt);
Clear_ListNode(L);
for(int i=0;i<MAXSIZE;i++){ printf("Cleared: L->elem[%d]: %d\n",i,L->elem[i]);
}
Destroy_ListNode(L);
printf("hello world!\n");
return 0;
}
栈：用于表达式求值，回文串判断，函数传参等等 特点：后进先出，只在一端操作 区分：线性栈、链表栈
线性栈代码如下:
#include<bits/stdc++.h>
using namespace std;
#define MAXSIZE 100
#define Elem int
typedef struct Stack {
int top; //栈顶指针
int *stack;//指向栈数组的指针
}Stack;
void Init_Stack(Stack* S){
S->top = -1; //top是从-1开始的，所以判断是否为空应是s->top == -1；数组第0位不要
S->stack = new int[MAXSIZE]; //分配了MAXSIZE空间的int类型的数组
}
int Is_Full(Stack S){ //判断是否为满
if(S.top == MAXSIZE-1){
return 1;
}
return 0;
}
int Is_Empty(Stack S){
if(S.top == -1){
return 1;
}
return 0;
}
void Push(Stack* S,Elem e){
if(Is_Full(*S)){
cout<<"Stack is full!"<<endl;
return ;
}
S->stack[++S->top] = e; //S->top前自增,因为S->top开始时是-1,-1+1=0才是开始存储的位置
}
void Pop(Stack* S,Elem *e){
if(Is_Empty(*S)){
cout<<"Stack is empty!"<<endl;
}
*e = S->stack[S->top--];//后自减，因为S->top是有数字的,取完这个数字后就自动减少一位,可以少写一行
}
void Print_Stack(Stack S){//不是栈的基本操作，这个只是为了看看栈的内容
cout<<"栈内容如下："<<endl;
cout<<"------"<<endl;
for(int i=S.top-1;i>=0;i--){
cout<<i<<" --> "<<S.stack[i]<<endl;
}
cout<<"------"<<endl;
}
void Clear_Stack(Stack* S){
S->top=-1;//直接令S->top是-1就行
}
void Destroy_Stack(Stack *S){
delete S->stack; //释放空间
return ;
}
int main(){
Stack S;
Init_Stack(&S);//初始化
int tmp;
for(int i=1;i<=10;i++){
Push(&S,i*10); //压栈
}
Print_Stack(S);//看栈内容
Clear_Stack(&S);//清空栈
Push(&S,114);
Push(&S,514);
Push(&S,8585);
Push(&S,312);
Print_Stack(S);//看栈内容
Push(&S,99);//压栈
Print_Stack(S);//看栈内容
Pop(&S,&tmp);//弹出来到tmp
cout<<"tmp:"<<tmp<<endl;//看看tmp的内容
Destroy_Stack(&S);//销毁栈
return 0;
}
链栈代码如下：
#include<iostream>
using namespace std;
template<typename T> //用到了模板
struct SNode{
T data;
struct SNode *next;
};
template<typename T>
class Stack{
private:
SNode<T> *top; //栈顶指针，指向栈顶节点
int len;//栈的长度，用于判断栈是否为空
public:
Stack(){//空参构造
this->top = NULL;
this->len = 0;
}
~Stack(){//析构函数，主要是用于释放内存
SNode<T>* tmp;
tmp = this->top;
while(tmp){
this->top = this->top->next;
delete tmp;
tmp = this->top;
}
this->len = 0;
}
bool Is_Empty(){
if(this->len == 0) return true;
return false;
}
void Push(T val){
SNode<T>* p = new SNode<T>;
p->data = val;
p->next = top;
top = p;
this->len ++;
}
void Pop(T &val){
if(Is_Empty()){
cout<<"Stack is Empty!"<<endl;
return;
}
SNode<T>*p = this->top;
this->top = this->top->next;
val = p->data;
delete p;
this->len --;
}
};
int main(int args,char* argv[]){
Stack<int>s;
cout<<"入栈10"<<endl;
s.Push(10);
cout<<"出栈值到tmp"<<endl;
int tmp;
s.Pop(tmp);
cout<<"tmp:"<<tmp<<endl;
cout<<"栈空检查"<<endl;
s.Pop(tmp);
return 0;
}
1. 队列的概念
队列（Queue）是一种 ** 先进先出（FIFO, First In First Out）** 的数据结构。
新元素从队尾（rear）加入。
旧元素从队头（front）删除。
2. 基本结构
队列可以用数组或链表实现：
数组实现：固定大小，可能出现假溢出。
链表实现：大小动态变化，无假溢出问题。
3. 基本操作
常见操作有：
入队（Enqueue）：在队尾添加元素。
出队（Dequeue）：从队头删除元素。
取队头元素（Front）：返回队头元素，不删除。
判空（IsEmpty）：判断队列是否为空。
判满（IsFull）：数组队列需要判断是否已满。
4. 特点总结
特点 说明
先进先出 第一个进入队列的元素第一个离开。
顺序存取 元素按插入顺序被访问。
限制插入删除位置 插入只能在队尾，删除只能在队头。
不支持随机访问 不能直接访问中间元素。
常用场景 任务排队、广度优先搜索（BFS）、缓冲区等。
5. 常见队列类型
普通队列：基础的 FIFO 队列。
循环队列：解决数组队列假溢出问题。
双端队列（Deque）：两端都可以插入和删除。
优先级队列：按优先级出队，不一定遵循 FIFO。
6. 应用场景
任务调度：操作系统的任务排队执行。
消息队列：系统间异步通信。
BFS 遍历：树或图的广度优先搜索。
缓冲区：键盘输入、打印机输出等。
线性循环队列：
#include<bits/stdc++.h>
using namespace std;
#define MAXQSIZE 100
#define Status int
#define OK 0
#define ERROR 1
#define OVERFOLOW -1
typedef struct Dnode{
int front;
int rear;
int *base;
}Queue;
Status InitDequeue(Queue &Q){
Q.base = new Status[MAXQSIZE];//空间分配
if(!Q.base) exit(OVERFLOW);//分配失败时
Q.rear=Q.front=0;//初始化
return OK;
}
Status GetLength(Queue &Q){
return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE); //获取队列长度 公式：(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE
}
Status IsFull(Queue &Q){
return ((Q.rear+1)%MAXQSIZE == Q.front)?1:0; //判满：公式：(Q.rear+1)%MAXQSIZE == Q.front
}
Status IsEmpty(Queue &Q){
return ((Q.rear == Q.front)?1:0); //判空：公式：Q.rear == Q.front
}
Status EnQueue(Queue& Q,Status e){ //入队
if(IsFull(Q)) exit(OVERFLOW);
Q.base[Q.rear] = e; //赋值
Q.rear = (Q.rear+1)%MAXQSIZE; //Q.rear往下一位
return OK;
}
Status Dequeue(Queue& Q,Status &e){ //出队
if(IsEmpty(Q)){exit(OVERFLOW);}
e = Q.base[Q.front];//赋值
Q.front = (Q.front+1)%MAXQSIZE; //Q.front往下一位
return OK;
}
Status Print_Queue(Queue& Q){ //遍历队列(不是队列的基本函数，只是为了看看里面有什么)
cout<<"队列遍历:"<<endl;
cout<<"-------"<<endl;
int tmp_ptr = Q.front;//把队头指针临时存起来，用的是队头指针遍历
while(!IsEmpty(Q)){
cout<<Q.base[Q.front]<<" ";
Q.front = (Q.front+1)%MAXQSIZE;
}
Q.front = tmp_ptr;//还原回去
cout<<endl;
cout<<"-------"<<endl;
return OK;
}
Status QueueClear(Queue& Q){//清空队列,眼不见即为空
Q.front = Q.rear = 0;
return OK;
}
Status DestroyQueue(Queue &Q){ //销毁队列
delete Q.base; //释放空间
return OK;
}
int n,tmp;
int main(int args,char* argv[]){
Queue q;
InitDequeue(q);
cout<<"请输入入队元素数量(<100):";
cin>>n;
for(int i=1;i<=n;i++) {
cout<<"入队:";
cin>>tmp;
EnQueue(q,tmp);
}
Print_Queue(q);
cout<<"出队tmp"<<endl;
Dequeue(q,tmp);
cout<<"the val dequeued:"<<tmp<<endl;
Print_Queue(q);
cout<<"队列清空"<<endl;
QueueClear(q);
Print_Queue(q);
cout<<"队列销毁"<<endl;
DestroyQueue(q);
return 0;
}
普通链队：
#include<bits/stdc++.h>
using namespace std;
typedef struct Qnode{
int data;
struct Qnode *next;
}Qnode,*LinkQueue;
class Queue{
public:
Queue(){ //这个链队是带头节点（一个没有存储意义的辅助节点）的
Q = new Qnode;
Q->next = NULL;
this->front = Q;
this->rear = Q;
};
Queue(int val){
Q = new Qnode;
LinkQueue p = new Qnode;
p->next = NULL;
this->front = Q;
this->rear = Q;
this->front->next = p;
this->rear = p;
};
~Queue(){
LinkQueue p;
while(Q){
p = Q->next;
delete Q;
Q = p;
}
};
int Push(int val){
LinkQueue p = new Qnode;
if(!p){exit(-1);};
p->data = val;
p->next = this->rear->next;
this->rear->next = p;
this->rear = p;
return 0;
};
bool Empty(){
if(this->front->next == NULL) {
return true;
}
return false;
}
int Pop(int &val){
if(Empty()){
cout<<"empty!"<<endl;return 1;
};
LinkQueue p = this->front->next; //因为带头节点才这样
this->front->next = p->next;
val = p->data;
if(p == this->rear){
this->rear = this->front;
}
delete p;
return 0;
}
int GetLength(){
int cnt=0;
LinkQueue p = this->front->next; //因为头节点的原因
while(p){
cnt++;
p = p->next;
}
return cnt;
}
int Travalor(){ //遍历队列
cout<<"遍历队列:"<<endl;
cout<<"-------"<<endl;
LinkQueue p = this->front->next;
while(p){
((p->next != NULL)?cout<<p->data<<" ":cout<<p->data<<endl);
p = p->next;
}
cout<<"-------"<<endl;
return 0;
}
private:
LinkQueue Q;
LinkQueue front,rear;
};
int main(int args,char* argv[]){
Queue q;
cout<<"入队"<<endl;
q.Push(1);
cout<<"入队1"<<endl;
q.Push(1);
cout<<"入队1"<<endl;
q.Push(4);
cout<<"入队4"<<endl;
q.Travalor();
int tmp;
cout<<"出队"<<endl;
q.Pop(tmp);
cout<<"Queue front :"<<tmp<<endl;
q.Pop(tmp);
cout<<"Queue front :"<<tmp<<endl;
q.Pop(tmp);
cout<<"Queue front :"<<tmp<<endl;
q.Pop(tmp);
q.Travalor();
return 0;
}
1. 树的概念
树是一种非线性的数据结构，由若干节点（Node）和连接节点的边（Edge）组成。
有一个特殊的根节点（Root），没有父节点。
除根节点外，每个节点有且仅有一个父节点。
节点可以有多个子节点。
没有子节点的节点称为叶子节点（Leaf）。
2. 基本结构
树的结构可以用递归定义：
单个节点是一棵树。
一棵树的根节点可以有若干子树，每个子树也是一棵树。
3. 基本术语
术语 说明
根节点 树的最顶层节点，没有父节点。
父节点 一个节点的直接上层节点。
子节点 一个节点的直接下层节点。
叶子节点 没有子节点的节点。
路径 从一个节点到另一个节点经过的边序列。
深度 从根节点到该节点的路径长度。
高度 从该节点到最远叶子节点的路径长度。
层 根节点在第 1 层，子节点在第 2 层，依此类推。
度 一个节点的子节点个数。
4. 树的特点
特点 说明
非线性结构 节点之间是一对多的关系，不同于线性结构（如数组、链表）。
递归定义 树的子树仍然是树。
无环 任意两个节点之间有且仅有一条路径。
分层结构 节点按层次组织，便于表示层次关系（如文件系统、组织结构）。
多种遍历方式 前序、中序、后序、层序遍历。
5. 常见树类型
普通树：子节点个数不限。
二叉树：每个节点最多有两个子节点（左子树和右子树）。
满二叉树：所有层的节点都满。
完全二叉树：除最后一层外，其他层节点都满，且最后一层节点靠左排列。
二叉搜索树（BST）：左子树节点值小于根节点，右子树节点值大于根节点。
平衡二叉树（AVL 树、红黑树）：左右子树高度差不超过 1，用于提高查找效率。
多叉树：如 B 树、B+ 树，用于数据库索引。
6. 基本操作
常见操作有：
插入节点：根据树的类型（如 BST）插入到合适位置。
删除节点：删除指定节点并调整树结构。
查找节点：根据值查找节点。
遍历：
前序遍历：根节点 → 左子树 → 右子树。
中序遍历：左子树 → 根节点 → 右子树。
后序遍历：左子树 → 右子树 → 根节点。
层序遍历：从上到下、从左到右按层访问。
求树的高度：递归计算左右子树高度的最大值加 1。
计算节点总数：递归统计左右子树节点数加 1。
7. 应用场景
文件系统：目录和文件的层次结构。
数据库索引：B 树、B+ 树用于快速查询。
编译器语法分析：抽象语法树（AST）。
机器学习：决策树用于分类和回归。
组织结构：公司部门、家族族谱等层次关系。
数的顺序存储数组版：
#include<bits/stdc++.h>
using namespace std;
const int N = 1025;
int arr[N] = {0};//数的构建序列
int in[N] = {0}; //输入序列
// 中序遍历创建二叉树（数组版）
/*
原理：
任意的树，从1开始，对于节点i（有左右节点及其双亲节点的话）
左子节点：2*i
右子节点：2*i+1
双亲节点 floor(i/2) 向下取整
创建方法：前序、中序、后序创建
*/
void create_tree(int arr[], int in[], int index, int size) {
// 如果当前索引越界，直接返回
if (index > size) return;
// 递归创建左子树
create_tree(arr, in, 2 * index, size);
// 存储当前节点值
arr[index] = in[index];
// 递归创建右子树
create_tree(arr, in, 2 * index + 1, size);
}
void prior_travel(int arr[],int index){//前序遍历
if(arr[index]!=0){
cout<<index<<":"<<arr[index]<<endl;
if(arr[index*2]!=0) prior_travel(arr,index*2);
if(arr[index*2+1]!=0) prior_travel(arr,index*2+1);
}
}
void mid_travel(int arr[],int index){//中序遍历
if(arr[index]!=0){
if(arr[index*2]!=0) mid_travel(arr,index*2);
cout<<index<<":"<<arr[index]<<endl;
if(arr[index*2+1]!=0) mid_travel(arr,index*2+1);
}
}
void post_travel(int arr[],int index){//后续遍历
if(arr[index]!=0){
if(arr[index*2]!=0) post_travel(arr,index*2);
if(arr[index*2+1]!=0) post_travel(arr,index*2+1);
cout<<index<<":"<<arr[index]<<endl;
}
}
int main(int args,char* argv[]){
int in[] = {0, 1, 2, 5, 3, 4, 0, 6, 0, 0, 0, 0};
/*
1
/ \
2 5
/ \ \
3 4 6
*/
int size=7;
create_tree(arr,in,1,size);//使用中序创建且当0是表示空
cout<<"输出每个节点的详细信息"<<endl;
for(int i=1;i<=size;i++){
cout<<"index:"<<i<<" val(node):"<<arr[i]<<" left:"<<i*2<<":"<<arr[i*2]<<" right:"<<i*2+1<<":"<<arr[i*2+1]<<endl;
}
cout<<"-------"<<endl;
prior_travel(arr,1);
cout<<"-------"<<endl;
mid_travel(arr,1);
cout<<"-------"<<endl;
post_travel(arr,1);
cout<<"--------------"<<endl;
return 0;
}
数的链式存储：
#include <bits/stdc++.h>
using namespace std;
typedef struct node {
int data;
struct node* left;
struct node* right;
} Node, *ListNode;
ListNode T;
// 初始化树
void Initial_tree(ListNode* T) {
if (!(*T)) {
(*T) = new Node;
(*T)->data = -1; // 空树标志
(*T)->left = nullptr;
(*T)->right = nullptr;
} else {
cout << "该树已被初始化" << endl;
}
}
// 判断是否为叶子节点
bool IsLeaf(ListNode T) {
if (!T->left && !T->right) return true;
else return false;
}
// 销毁树
void Destroy_Tree(ListNode T) {
if (T) {
Destroy_Tree(T->left);
Destroy_Tree(T->right);
delete T;
}
}
// 插入节点（二叉搜索树规则）
void Insert(ListNode* T, int val) {
if (!(*T)) { // 空树
*T = new Node;
(*T)->data = val;
(*T)->left = nullptr;
(*T)->right = nullptr;
} else if (val < (*T)->data) {
Insert(&((*T)->left), val);
} else {
Insert(&((*T)->right), val);
}
}
// 查找节点
bool Find(ListNode T, int val) {
if (!T) return false;
if (T->data == val) return true;
else if (val < T->data) return Find(T->left, val);
else return Find(T->right, val);
}
// 前序遍历
void PreOrder(ListNode T) {
if (T) {
cout << T->data << " ";
PreOrder(T->left);
PreOrder(T->right);
}
}
// 中序遍历
void InOrder(ListNode T) {
if (T) {
InOrder(T->left);
cout << T->data << " ";
InOrder(T->right);
}
}
// 后序遍历
void PostOrder(ListNode T) {
if (T) {
PostOrder(T->left);
PostOrder(T->right);
cout << T->data << " ";
}
}
// 层序遍历
void LevelOrder(ListNode T) {
if (!T) return;
queue<ListNode> q;
q.push(T);
while (!q.empty()) {
ListNode cur = q.front();
q.pop();
cout << cur->data << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
// 获取树的高度
int Height(ListNode T) {
if (!T) return 0;
return max(Height(T->left), Height(T->right)) + 1;
}
// 节点总数
int CountNodes(ListNode T) {
if (!T) return 0;
return CountNodes(T->left) + CountNodes(T->right) + 1;
}
// 叶子节点数
int CountLeaves(ListNode T) {
if (!T) return 0;
if (IsLeaf(T)) return 1;
return CountLeaves(T->left) + CountLeaves(T->right);
}
int main() {
T = nullptr; // 初始化为空树
// 插入节点
Insert(&T, 5);
Insert(&T, 3);
Insert(&T, 7);
Insert(&T, 2);
Insert(&T, 4);
Insert(&T, 6);
Insert(&T, 8);
cout << "前序遍历: ";
PreOrder(T);
cout << "\n中序遍历: ";
InOrder(T);
cout << "\n后序遍历: ";
PostOrder(T);
cout << "\n层序遍历: ";
LevelOrder(T);
cout << "\n树的高度: " << Height(T);
cout << "\n节点总数: " << CountNodes(T);
cout << "\n叶子节点数: " << CountLeaves(T);
cout << "\n查找值 6: " << (Find(T, 6) ? "存在" : "不存在");
cout << "\n查找值 9: " << (Find(T, 9) ? "存在" : "不存在");
Destroy_Tree(T);
return 0;
}
