深入浅出数据结构笔记

本文最后更新于：1 个月前

导读

b站上带有咖喱味英语的数据结构课程（由于是在大一下纯英学习记录的，所以在大二学校开启这门课的时候就没有仔细听，后期复习时又在本文增加一些概念）

概念：Data Structures is a way to store and organize data

数字和逻辑模型数学数学Mathematical/logical models( 抽象数据类型Abstract Data Types,简称ADP)

谈论实现(Implementation)

ADTS:Arrays,Linked List,stack,Queue,Tree,Graph…

通常设计一个“好”的算法应考虑达到以下目标:
(1) 正确性。算法应能够正确地求解问题
(2) 可读性。算法能具有良好的可读性，以帮助人们理解
(3) 健壮性。输入非法数据时，算法能适当地做出反应或进行处理，而不会
产生莫名其妙的输出结果。
(4) 高效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算
法执行过程中所需的最大存储空间

算法效率

算法效率的度量是通过时间复杂度和空间复杂度来描述的。一个语句的频度指该语句在算法中被重复执行的次数算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。

image-20231227212301699

抽象数据类型(ADTS)

顺序表

顺序表：在逻辑位置相邻的两个元素子物理位置也相邻，随机存储，存储密度高，插入和删除需要大量移动元素

image-20231228174936762

先用array定义抽象数据类型

首先定义一个基本的给定元素数量、给定数据类型的静态列表

1
2
3
int A[10];
A[i]=2;
print A[i];

然后再试着定义一个动态列表，特点是列表为空其大小为零，并且可以在列表中插入或者修改元素

-empty list has -insert -remove -count -Read/modity element at a position

-Bpecity data-type

1
2
3
4
5
6
7
8
9
int [MAX SIZE]
int end=-1;//每次插入数组都会改变，指向空数组
insert(2)0:2
insert(4);0:2 1:4
insert(6);0:2 1:4 2:6
insert(7);0:2 1:4 2:6 3:7
isnert(9);0:2 1:4 2:6 3:7 4:9
insert(5,2);0:2 1:4 2:5 3:6 4:7 5:9
remove(0);0:4 1:5 2:6 3:7 4:9

当数组已满，将创建一个新的更大(两倍)的数组，并复制上一个数组的所有元素到新的数组，然后释放上一个数组占用的内存，所以发现用数组试着创建一个动态列表就内存利用率和消耗量而言，不是最有效的，还存在一些限制。为了更好理解链表，我们需要了解这些限制

linked list逻辑理解

1
2
3
4
5
struct Node
{                         //example:6,5,4,2,3
    int data;//4bytes
    Node next;//bytes
}

linked list可以实现list的限制，并且不会占用多余的空间

array VS Linked List

比较方面

1.cost of accesing an element(成本)

2.Memory requirements(内存需求)

3.cost of iserting anelement(插入元素的成本，时间复杂度)

4.easy of use

Array

1
2
3
4
5
6
7
1:constant time O(1)
2：Fixed size(memory may not be available as oe large blocus)
3：
(1)at beginning O(N)
(2)at end o(1)
(3)a ith o(n)
4:y

Linked List

1
2
3
4
5
6
7
8
1:average case O(n)
2:No usused memory  extra memory for pointer variables
(memory may be available as multiple small blocus)
3：
(1)at begining O(1)
(2)at end O(n)  要先全部遍历一遍，所以花费时间和链表元素成正比
(3)at ith O(n)
4:n

链表

单链表

在c/c++中实现

逻辑视图如下

节点是一个数据类型，他有两个域，一个用来储存数据，一个用来存储指针，在c中我们将这种数据类型定义为结构体

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Node
{
    int data；
    Node* link;//next
}
Node* A;//第一件事，声明一个指向头节点的指针，一个将存储头节点地址的变量
A=NULL;//最初没有元素，使指针不指向具体节点，因此列表为空
Node* temp=(Node*)malloc(sizeof(Node));//创建一个节点.c++建议用new：Node* temp=new Node();
(*temp).data=2;//temp->data=2;
(*temp).link=NULL;//此时第一个节点的link指向NULL
A=temp;//temp是用来暂时存储节点地址的，一旦链接调整完成，temp可以用作其他目的
//继续
temp=new Node();//相当于在列表末尾插入
temp->data=4;
temp->link=Null;
/*
遍历列表代码逻辑
Node *temp=A;A永远不会被改变，存储头节点的地址值从不应该被修改
while(temp1->link!=Null){
temp1=temp1->link;到达下一个节点，，到达末尾
}
*/

头部插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<stdlib.h>
#include<stdio.h>
struct Node{
    int data;
    struct Node* next;//在c++中只用写Node* next
};
struct Node* head;//global variable,can be accessed anywhere
void Insert(int x){
    Node* temp=(Node*)malloc(sizeof(struct Node));
    temp->data=x;
    temp->next=head;
    head=temp;
}
void Print(){
    struct 	Node* temp=head;
        printf("List is: ");
    while(temp!=NULL){
        printf(" %d",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
int main(){
    head=NULL;//empty list;
    printf("How many numbers?\n");
    int n,i,x;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        printf("Enter the number \n");
        scanf("%d",&x);
        Insert(x);
        Print();
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
struct Node{
    int data;
    struct Node* next;
};
Node* Insert(Node* head,int x){//(Node** head,int x)
    struct Node* temp=(Node*)malloc(sizeof(struct Node));
    temp->data=x;
    temp->next=NULL;
    if(head!=NULL)temp->next=head;//if(*head!=NULL)temp->next=*head
    head=temp;
    return head;
}
void Print(Node* head){
	printf("List is: ");
	while(head!=NULL){
        printf(" %d",head->data);
        head=head->next;
    }
    printf("\n");
}
int main(){
    Node* head=NULL;//empty list;
    printf("How many numbers?\n");
    int n,i,x;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        printf("Enter the number \n");
        scanf("%d",&x);
        head=Insert(head,x);
        Print(head);//两个头节点是不一样的
    }
    
}

任意位置插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdlib.h>
#include<stdio.h>
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;//globl
void Insert(int data,int n){
    Node* temp1=new Node();//Node* temp=(Node*)malloc(sizeof(struct Node));
    temp1->data=data;
    temp1->next= NULL;
    if(n==1){
        temp1->next=head;
        head=temp1;//head将变得不在任何位置都能直接访问
        return;//所以函数调用，需要返回一些值来指示更新后的head
    }
    Node* temp2 =head;
    for(int i=0;i<n-2;i++){//转到第n-1节点，头节点不参加循环 
        temp2=temp2->next;
    }
    temp1->next=temp2->next;
    temp2->next=temp1;
  
}
void Print(){
    Node* temp=head;
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
int main(){
    head=NULL;//empty list
    Insert(2,1);//2
    Insert(3,2);//2,3
    Insert(4,1);//4,2,3
    Insert(5,2);//4,5,2,3
    Print();
}

任意一个位置删除节点

删除节点是有两个重点：

1.修复链接，是节点不再成为链表的一部分(Fix the links)

2.释放空间，把节点占据的空间从内存中释放(Free the space)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdlib.h>
#include<stdio.h>
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;//global
void Insert(int data){//insert an integer at end of list
    Node* temp=(Node*)malloc(sizeof(struct Node));
    temp->data=data;
    temp->next=head;
    head=temp;
}
void Print(){//print all
    struct 	Node* temp=head;
        printf("List is: ");
    while(temp!=NULL){
        printf(" %d",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
void Delete(int n){//delete node at position n
    struct Node* temp1=head;
    if(n==1){
        head=temp1->next;
        free(temp1);
        return;
    }
    int i;
    for(i=0;i<n-2;i++){
        temp1=temp1->next;
    }//(n-1)th node
    struct Node* temp2=temp1->next;//nth node
    temp1->next=temp2->next;//(n+1)th node
    free(temp2);//delete
}
int main(){
    head =NULL;//empty
    Insert(2);
    Insert(4);
    Insert(5);
    Insert(6);//list: 2,3,5,6
    Print();
    int n;
    char a;
    for (int i=0;i<4;i++){
    printf("Enter a position \n");
    scanf("%d",&n);
    Delete(n);
    }
}

反转列表(迭代)

递归和迭代都是重复计算的一种方式，但是实现方式有所不同。递归是一种重复递推与回归过程的结构，而迭代则是一种重复循环与更新状态的结构。

递归是指在函数定义中使用函数自身的方法，通过在循环中调用自身来实现重复计算。而迭代则是通过某段代码实现循环，利用变量的原值推算出变量的一个新值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node* next;
};
struct Node* head;//global
void Print(Node* head){//print all
   while(head!=NULL){
   	printf("%d ",head->data);
	   head=head->next; 
   }
   printf("\n");
}
Node* Insert(Node* head,int data){
    Node *temp=(struct Node*)malloc(sizeof(struct Node));
    temp->data=data;
    temp->next=NULL;
    if(head==NULL){
    	head=temp;
	}
	else{
		Node* temp1=head;
		while(temp1->next!=NULL){
			temp1=temp1->next;	
		}
		temp1->next=temp;
	}
	return head;
}
struct Node* Reverse(struct Node* head){
    struct Node* current,*prev,*next;
    current=head;
    prev=NULL;
    while(current!=NULL){
        next=current->next;
        current->next=prev;//*(current).next
        prev=current;//重新设置遍历列表
        current=next;
    }
    head=prev;
    return head;
}
int main(){
    struct Node* head=NULL;
    head=Insert(head,2);
    head=Insert(head,4);
    head=Insert(head,6);
    head=Insert(head,8);
    Print(head);
    head=Reverse(head);
    Print(head);    
}

打印列表(递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<stdio.h>
#include<stdlib.h>

struct Node{
    int data;
    struct Node* next;
};
void Print(struct Node* p){
    if(p==NULL) {
        printf("\n");
        return;
    }//递归结束
    printf("%d ",p->data);
    Print(p->next);
}
void ReversePrint(struct Node* p){
    if(p==NULL){
        return;
    }
    ReversePrint(p->next);//一次次调用自身函数，从最里层到最外层依次输出，相当于反转
    printf("%d ",p->data);
}
Node* Insert(Node* head,int data){
    Node *temp=(struct Node*)malloc(sizeof(struct Node));
    temp->data=data;
    temp->next=NULL;
    if(head==NULL){
    	head=temp;
	}
	else{
		Node* temp1=head;
		while(temp1->next!=NULL){
			temp1=temp1->next;	
		}
		temp1->next=temp;
	}
	return head;
}
int main(){
    struct Node*  head=NULL;
    head=Insert(head,2);
    head=Insert(head,4);
    head=Insert(head,6);
    head=Insert(head,5);
    Print(head);
	ReversePrint(head); 
}

反转列表(递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;
void Reverse(struct Node* p){
    if(p->next==NULL)
    {//exit condition
        head=p;
        return;
    }
    Reverse(p->next);
    struct Node* q=p->next;//p->nexct->next=p
    q->next=p;
    p->next=NULL;
}

int main(){
    struct Node* head=NULL;
    Insert(1,2);
    Insert(1,4);
    Insert(1,5);
    Insert(1,6);
    Reverse(head);
    Print(head);
}

双向链表(Doubly Linked List)

单链表结构体

1
2
3
4
struct Node{
    int data;
    struct Node* next;
};

双链表结构体

1
2
3
4
5
struct Node{
    int data;
    struct Node* next;
    struct Node* prev;//指向上一个节点
}

双链表的优点：

如果有指向任何节点的指针，可以反向查询(Reverse look-up)

实现

Insert At Head(x)写一个在头部插入的函数，取一个整型作为参数

Insert At Tail(x)在末尾插入

Print()打印函数,从头到尾遍历

ReversePrint()反向打印函数，反向遍历，验证是否正确创建了每个节点的反向链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include<stdlib.h>
struct Node{
   int data;
    struct Node* next;
    struct Node* prev;
};
struct Node* head;//global variable -pointer to head node
struct Node*  GetNewNode(int x){//局部变量存在栈区，我们无法控制其生命周期
    //local variable
    //will be cleared from memeory when function call will finish
    struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->data=x;
    newNode->prev=NULL;
    newNode->next=NULL;
    return newNode;
}
void InsertAtHead(int x){
    struct Node* newNode =GetNewNode(x);
    if(head==NULL){
        head=newNode;
        return;//返回或退出
    }
    head->prev=newNode;
    newNode->next=head;
    head=newNode;
}
void Print(){
    struct Node* temp=head;
    printf("Forward ");
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
void ReversePrint(){
    struct Node* temp=head;
    if(temp==NULL)return;
    while(temp->next!=NULL){//gonig to last node
        temp=temp->next;
    }
    printf("Reverse: ");
    while(temp!=NULL){
        printf("%d ",temp->data);
        temp=temp->prev;
    }
    printf("\n");
}
int main(){
    head =NULL;
    InsertAtHead(2);Print();ReversePrint();
    InsertAtHead(4);Print();ReversePrint();
    InsertAtHead(6);Print();ReversePrint();
}

栈(stack)

当把栈作为一种抽象数据类型来讨论，我们只讨论特性和操作(feratures/operations)，而不讨论具体实现(imprementeation)。

Stack ADT

A list with the restriction that insertion and deletion can be pertormed only from one end ,called the top.

LIFO(Last-In-First-Out)

operations

1.Push//插入 2.pop//弹出 3.Top//返回栈顶元素 4.IsEmpty//判断栈是否为空,空返回true

时间复杂度为O(1)

Applications(应用场景)

1.Function calls/Recursion(执行函数)

2.undo in an editor(编辑器中撤回)

3.Balanced Parentheses(编译器平衡括号)

实现

arrays

linked lists

基于数组实现栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<stdio.h>
#define MAX_SIZE 101
int [MAX_SIZE];
int top=-1;
void Push(int x){
     if(top==MAX_SIZE-1){//处理溢出情况
         printf("Error,stack overflow\n");
         return;
     }
    A[++top]=x;//top++; A[top]=x;
}
void pop(){
    if(top==-1){
        printf("Error:No element to pop\n");
        return;
    }
    top--;
}
void top(){
    return A[top];
}
void Print(){
    int i;
    printf("Stack: ");
    for(i=0;i<top;i++){
        printf("%d",A[i]);
    }
    printf("\n")
}
int main(){
    Push(2);Print();
    Push(5);Print();
    Push(10);Print();
    Pop();Print();
    Push(12);Print();
}

基于链表实现栈

链表作为栈来使用，我们有两种选择

Insert/delete

-at end of list(tail) 因为要从头到尾遍历，所以时间复杂度为O(n)，不是常数时间

-at beginning of list (head) 时间复杂度为O(1),所以我们考虑实现这种插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#include<stdlib.h>
struct Node {
    int data;
    struct Node* link;
}; 
struct Node* top=NULL;
void Push(int x){
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node*));
    temp->data=x;
    temp->link=top;
    top=temp;
}
void Pop(){
    struct Node *temp;
    if (top== NULL){
        return;
    }
    temp=top;
    top=top->link;
    free(temp);
}
void Print(){
    struct Node *temp;
    temp=top;
    printf("Stack: ");
   while(temp!=NULL){
       printf("%d ",temp->data);
       temp=temp->link;
   }
    printf("\n");
}
int main(){
    Push(8);Print();
    Push(4);Print();
    Push(6);Print();
    Pop();Print();
    Pop();Print();
}

栈功能

1.Using stack to reverse

PROBLEM1 :Reverse a string

栈的特点是后入先出，所以向栈中压入一些元素，所有元素都在栈上，依次出栈，最后一个出栈的对应的是第一个入栈的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
class Stack //可以是基于数组或量链表实现的栈
{
    private:
    char A[101];
    int top;
    public:
    void Push(int x);//使用相关库函数去实现栈
    void Pop();
    int Top();
    bool IsEmpty();
};
int main(){
    char C[51];
    printf("Enter a string: ")
        gets(C);
    Reverse(C,strlen(C));
    printf("Output: %s",C);
}

我们来用c++标准库的方式来实现字符串反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//string reversal using stack
#include<bits/stdc++.h>
#include<stack> //stack from standard template libraty (stl)
using namespace std ;
void Reverse(char *C,int n){
    stack<char>S;//C++中的标准模板库（STL）组件，定义了一个名为S的栈（stack），其中S存储char类型的元素
    for(int i=0;i<n;i++){//loop for push 这种情况下时间复杂度为O(n)
        S.push(C[i]);
    }
    for(int i=0;i<n;i++){//loop for pop 这种情况下时间复杂度为O(n)
        C[i]=S.top();//overwrite the character at index i
        S.pop(); //perform  pop
    }
}
int main(){
    char C[51];
    printf("Enter a string: "); 
        gets(C);
    Reverse(C,strlen(C));
    printf("Output: %s",C);
}

PROBLEM2:Reverse a Linker List

Iterative Solution 迭代: Time-O(n) Space-O(1)

Recursive Solution(Implicit Stack) 递归: Time-O(n) Space-O(n)

隐式地使用了栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
   
struct Node{
    int  data;
    Node* next;
}
void Reverse(){
    if(head==NULL) return;
    stack<struct Node*>S;
    while(temp！=NULL){
        S.push(temp);
        temp=temp->next;
    }
    temp=S.top();head=temp;
    while(!S.empty()){
        temp->next=S.top();
        S.pop();
        temp=temp->next;
    }
    temp->next=NULL;
}

2.Check for balanced parentheses

parentheses:()or{}or[]

Expression:当表达式或字符串包含大小写字符，操作符，各种括号

EXPRESSION BALANCED

(A+B) YES

{(A+B)+(C+D)} YES

{(x+y)*(z) NO

[2*3]+(A)] NO

{a+z) NO

Solution:

scanf from left to right .if opening symbol,add it to a list;if closeing symbols, remove last opening symbol in list.should end witn an empty list.

伪代码逻辑思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Check Balanced Parebthesis(exp){
    n<-length(exp)
    Create a stack:-S
        for i<-0 to n-1
        {
            if exp[i] is '('or'{'or'['
                push(exp[i])
            else if exp[i]is ')'or'}'or']'
            {
                if (S is empty)||
                {
                    top dose not pair with exp[i],
                    return flase
                }
                else pop()
            }
        }
    return S is empty? true or false
}//扫描结束栈为空

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*
  使用堆栈检查表达式中平衡括号的 C++ 程序。
  给定一个由开始和结束字符组成的字符串表达式
  括号 - ()，大括号 - {} 和方括号 - []，我们需要
  检查符号是否平衡。
*/
#include<iostream>
#include<stack>
#include<string>
using namespace std;
// Function to check whether two characters are opening 检查两个字符是否打开的函数
// and closing of same type. 和相同类型的关闭
bool ArePair(char opening,char closing)
{
	if(opening == '(' && closing == ')') return true;
	else if(opening == '{' && closing == '}') return true;
	else if(opening == '[' && closing == ']') return true;
	return false;
}
bool AreParanthesesBalanced(string exp)
{
	stack<char>  S;
	for(int i =0;i<exp.length();i++)
	{
		if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
			S.push(exp[i]);
		else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
		{
			if(S.empty() || !ArePair(S.top(),exp[i]))
				return false;
			else
				S.pop();
		}
	}
	return S.empty() ? true:false;
}

int main()
{
	/*Code to test the function AreParanthesesBalanced*/
	string expression;
	cout<<"Enter an expression:  "; // input expression from STDIN/Console来自 STDIN/Console 的输入表达式
	cin>>expression;
	if(AreParanthesesBalanced(expression))
		cout<<"Balanced\n";
	else
		cout<<"Not Balanced\n";
}

Infix, Postfix, Prefix

中缀，前缀，后缀

基本概念

就是对对算术和逻辑表达式的求值

​ Infix 中缀表达式

1
2
3
2+3                         
A-B                   <operand><operator><operand>操作数 操作符 操作数
(P*2)

Order of operation (优先级)

  1. Parenthese () {} []
  2. Exponents (right to left) 2^ 3 ^2=2 ^9=512
  3. Multiplication and division(left to right)
  4. Addition and Subtraction(left to right)

​ Prefix 前缀表达式

+2 3

+A B

+a(*bc)

​ Postfix 后缀表达式

Index Prefix Postfix

2+3 +2 3 2 3 +

p-q -p q p q-

a+bc +a( * bc) abc +

求值

**(Evaluation of Prefix and Postfix expressions)**前缀和后缀

后缀求值伪代码逻辑思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
EvaluatePostfix(exp){
     creat a stack S;
    fori<-0to lenth(exp)-1
    {  if(exp[i]is operand)
            push(exp[i])
         else if(exp[i] is operator)
         {
             op2<-pop()
             op2<-pop()
                 res<-Perform(exp[i],op1,op2)//运算操作函数
                 Push(res)
         }
    }
    return top of stack 
}

源码

Infix to Postfix

第一种逻辑

1
Infix   A+(B*C) -> A+(BC*) -> A(BC*)+ -> ABC*+  Postfix

c++源码

第二种逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Infix ToPostfix(exp)
{
  Create a stack S
  res<- expty string
  for i<-0 to lenth(exp)-1
  {
     if exp[i]is operand
     res<- res +exp[i]
     else if exp[i] is operator{
     while (s.expty()&& HasHigherPrec(s.top(),exp[i]))
     {
     res<-res+S.top()
     S.pop()
     }
     S.Push(exp[i])
     }
  }
  while(!S.expty())
  {
  res<-res+s.top()
  S.pop()
  }
  return res
}

c++源码

队列(queues)

Queue -First-In-First-Out

Stack -Last-In-First-Out

Queue ADP

A list or collection with the restriction that insertion can be performed at one end (队尾) and deletion can be performed at other end (队头)

Operations (O(1))

  1. EnQueue(x) or Push(x) -在队尾插入
  2. DeQueue( ) or Pop( ) -在队头删除
  3. Front( ) or Peek( ) -查看队头元素
  4. IsEmpty( ) -判断是否为空

上图右边是队列的结构

Applications

  1. Printer queue 打印机队列
  2. Process scheduling 进程调度
  3. simulating wait 模拟等待

实现

使用数组实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<iostream>
using namespace std; 
#define MAX_SIZE 101  //maximum size of the array that will store Queue. 

// Creating a class named Queue.
class Queue
{
private:
	int A[MAX_SIZE];
	int front, rear; 
public:
	// Constructor - set front and rear as -1. 
	// We are assuming that for an empty Queue, both front and rear will be -1.
	Queue()
	{
		front = -1; 
		rear = -1;
	}

	// To check wheter Queue is empty or not
	bool IsEmpty()
	{
		return (front == -1 && rear == -1); 
	}

	// To check whether Queue is full or not
	bool IsFull()
	{
		return (rear+1)%MAX_SIZE == front ? true : false;
	}

	// Inserts an element in queue at rear end
	void Enqueue(int x)
	{
		cout<<"Enqueuing "<<x<<" \n";
		if(IsFull())
		{
			cout<<"Error: Queue is Full\n";
			return;
		}
		if (IsEmpty())
		{ 
			front = rear = 0; 
		}
		else
		{
		    rear = (rear+1)%MAX_SIZE;
		}
		A[rear] = x;
	}

	// Removes an element in Queue from front end. 
	void Dequeue()
	{
		cout<<"Dequeuing \n";
		if(IsEmpty())
		{
			cout<<"Error: Queue is Empty\n";
			return;
		}
		else if(front == rear ) 
		{
			rear = front = -1;
		}
		else
		{
			front = (front+1)%MAX_SIZE;
		}
	}
	// Returns element at front of queue. 
	int Front()
	{
		if(front == -1)
		{
			cout<<"Error: cannot return front from empty queue\n";
			return -1; 
		}
		return A[front];
	}
	/* 
	   Printing the elements in queue from front to rear. 
	   This function is only to test the code. 
	   This is not a standard function for Queue implementation. 
	*/
	void Print()
	{
		// Finding number of elements in queue  
		int count = (rear+MAX_SIZE-front)%MAX_SIZE + 1;
		cout<<"Queue       : ";
		for(int i = 0; i <count; i++)
		{
			int index = (front+i) % MAX_SIZE; // Index of element while travesing circularly from front
			cout<<A[index]<<" ";
		}
		cout<<"\n\n";
	}
};
int main()
{
	/*Driver Code to test the implementation
	  Printing the elements in Queue after each Enqueue or Dequeue 
	*/
   Queue Q; // creating an instance of Queue. 
   Q.Enqueue(2);  Q.Print();  
   Q.Enqueue(4);  Q.Print();  
   Q.Enqueue(6);  Q.Print();
   Q.Dequeue();	  Q.Print();
   Q.Enqueue(8);  Q.Print();
}

使用链表实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<stdio.h>
#include<stdlib.h>
struct Node {
	int data;
	struct Node* next;
};
// Two glboal variables to store address of front and rear nodes. 
struct Node* front = NULL;
struct Node* rear = NULL;

// To Enqueue an integer
void Enqueue(int x) {
	struct Node* temp = 
		(struct Node*)malloc(sizeof(struct Node));
	temp->data =x; 
	temp->next = NULL;
	if(front == NULL && rear == NULL){
		front = rear = temp;
		return;
	}
	rear->next = temp;
	rear = temp;
}

// To Dequeue an integer.
void Dequeue() {
	struct Node* temp = front;
	if(front == NULL) {
		printf("Queue is Empty\n");
		return;
	}
	if(front == rear) {
		front = rear = NULL;
	}
	else {
		front = front->next;
	}
	free(temp);
}

int Front() {
	if(front == NULL) {
		printf("Queue is empty\n");
		return;
	}
	return front->data;
}

void Print() {
	struct Node* temp = front;
	while(temp != NULL) {
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

int main(){
	/* Drive code to test the implementation. */
	// Printing elements in Queue after each Enqueue or Dequeue 
	Enqueue(2); Print(); 
	Enqueue(4); Print();
	Enqueue(6); Print();
	Dequeue();  Print();
	Enqueue(8); Print();
}

树(tree)

数是经常被用来表示层次数据的一种非线性数据结构，树这种数据结构可以被定义为：链接在一起的被称为节点的实体的集合.

root

children

Parent

sibling (have sane parent)

leaf (has no chlidren)

if we can go from A to B(These links are not bidirectional.)

A is ancestor of B ;B is descendent of A.

sub-trees (子树)

Depth and Height

depth of x = NO. of edges in path from root to x

height of x= NO. of edges in longest path from x to a leaf.(height of tree is height of root node)

Binary Tree(二叉树)

a tree in which each node can have at most 2 children

image-20230723222406866

(偷张图…)

Applications

1） Storing naturally hierachical data（存储天然具备层级结构的数据）

eg: file system(磁盘驱动器上的文件系统)

2）organzie data for quick search ,insertion,deletion(组织数据)

eg: Binary Search tees (二叉搜索树)

3）Trie树 -> 存储dictionary

4） Network Eouting algorithm(网络路由算法)

二叉树(binary tree)

each node can have most 2 children

Strict/Proper binary tree

each node can have either 2 or 0 children

Complete Binary tree

all levels except possibly the last are completely filled and all nodes are as left as possible

最后一层除外每层都要被填满且左对齐

max number of nodes at level i= 2^i

Perfect Binary tree

每层都被填满

Maximum no of nodes in a tree with heighe h =2^0 +2^1 +2^2 + 2^3……..+2^h= 2^(h+1)-1

n=number of nodes

h=log2(n+1)-1

Balanced binary tree

difference between height of let and right subtree for every node is not more than K(mostly 1)

Height of an empty tree =-1

Height of tree with 1 node=0

二叉搜索树

Binary Search Tree(Balanced)时间成本

Search(x) O(logn)

Insert(x) O(logn)

Remove(x) O(logn)

二进制搜索树是一种二叉树，其中每一个节点，所有的左子树上的节点值都比该节点的值要小，所有右子树上的节点值都比该节点的值要大，子叶的值比root的值小即可

c/c++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
using namespace std;
struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};
BstNode* GetNewNode(int data){
    BstNode* newNode=new BstNode();
    newNode->data=data;
    newNode->left=newNode->right=NULL;
    return newNode;
}
BstNode* Insert(BstNode* root ,int data){
    if(root==NULL){
        root=GetNewNode(data);
        return root;
    }
    else if(data<=root->data){//递归
        root->left=Insert(root->left,data);
    }
    else{
        root->right=Insert(root->right,data);
    }
    return root;
}
bool Search(BstNode* root,int data){
    if(root==NULL) return false;
    else if(root->data==data) return true;
    else if(data<=root->data)return Search(root->left,data);
    else return Search(root->right,data);
}
int main(){
    BstNode* root=NULL;//creating an empty tree
    root=Insert(root,15);
    root=Insert(root,10);
    root=Insert(root,20);
    root=Insert(root,25);
    root=Insert(root,8);
    root=Insert(root,12);
    int number;
    while(1){

    cout<<"Enter number be searched\n";
    cin>>number;
    if(Search(root,number)==true) cout<<"Found\n";
    else cout<<"Not Found\n";
    }
}

1
2
3
4
5
6
7
8
9
10
11
Enter number be searched
15
Found
Enter number be searched
20
Found
Enter number be searched
18
Not Found
Enter number be searched

下面穿插一个基础知识点

系统会分配一个程序或者应用的内存，在典型架构中，会被分为四个段。代码段(code(text))是用来存放程序指令(指令是编译好的机器语言)；一个段(Static/Global)用于存放全局变量(在所有函数外部声明的变量被称为全局变量，可以被任何函数访问);下一个段是栈段，基本是是一个暂存空间(用来执行函数，暂存所有的局部变量，所有在函数内部声明的变量存活于栈上)；最后一个段是堆段，也被称为自由的存储空间(动态内存，根据我们的需要增加或减小)，其他段的大小都是固定的，也就在编译时决定，但是堆可以在运行时增长。

在上边的程序中，我们需要想象出栈段和堆段的交互过程

查找最小值和最大值

左子树大，右子树小

使用迭代的方式实现Findmin函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};
int FindeMin(BstNode* root){
    if(root==NULL){
        cout<<"Error: Tree is empty\n";
        return -1;
    }
    BstNode* current =root;
    while(current->left!=NULL){
        current=current->left;
    }
    return current->data;
}

使用递归的方式实现Findmin函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct BstNode{
    int data;
    BstNode* left;
    BstNode* right;
};
int FindMin(BstNode* root){
    if(root==NULL){
        cout<<"Error: Tree is empty\n";
        return -1;
    }
    BstNode* current =root;
    while(current->left!=NULL){
        return current->data;
    }
    return FindMin(current->left);
}

二叉树的高度和深度

二叉树的遍历-广度优先vs深度优先

树并不是一个线性的数据结构，树的遍历被称为访问树的每个结点的过程，按照某种顺序每个节点仅被访问一次，访问的意思是读取或者修改节点中的数据

Binary Tree Tracersal

Breadth-first(广度优先)

一层一层访问

Depth-first(深度优先)

访问一个孩子的同时访问那个路径上的完整子树，一般有LDR,DLR,LRD三种方式L(左子树)D(data)R(右子树)

image-20230723222448598

具体实现

Preorder(DLR)

F,D,B,A,C,E,J,G,I,H,K

Inorder(LDR)

A,B,C,D,E,F,G,H,I,J,K

Postorder(LRD)

A.C.B.E.D.H.I.G.K.J,F

C++实现层次遍历

基本上属于广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/* Binary tree - Level Order Traversal */
#include<iostream>
#include<queue>
using namespace std;

struct Node {
	char data;
	Node *left;
	Node *right;
};

// Function to print Nodes in a binary tree in Level order
void LevelOrder(Node *root) {
	if(root == NULL) return;
	queue<Node*> Q;
	Q.push(root);  
	//while there is at least one discovered node
	while(!Q.empty()) {
		Node* current = Q.front();
		Q.pop(); // removing the element at front
		cout<<current->data<<" ";
		if(current->left != NULL) Q.push(current->left);
		if(current->right != NULL) Q.push(current->right);
	}
}
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data) root->left = Insert(root->left,data);
	else root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    M
			   / \
			  B   Q
			 / \   \
			A   C   Z
    */
	Node* root = NULL;
	root = Insert(root,'M'); root = Insert(root,'B');
	root = Insert(root,'Q'); root = Insert(root,'Z'); 
	root = Insert(root,'A'); root = Insert(root,'C');
	//Print Nodes in Level Order. 
	LevelOrder(root);
}

层次遍历的时间复杂度O(n)

c++实现深度遍历

前序中序后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/* Binary Tree Traversal - Preorder, Inorder, Postorder */
#include<iostream>
using namespace std;
 
struct Node {
	char data;
	struct Node *left;
	struct Node *right;
};

//Function to visit nodes in Preorder
void Preorder(struct Node *root) {
	// base condition for recursion
	// if tree/sub-tree is empty, return and exit
	if(root == NULL) return;

	printf("%c ",root->data); // Print data
	Preorder(root->left);     // Visit left subtree
	Preorder(root->right);    // Visit right subtree
}

//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;

	Inorder(root->left);       //Visit left subtree
	printf("%c ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}

//Function to visit nodes in Postorder
void Postorder(Node *root) {
	if(root == NULL) return;

	Postorder(root->left);    // Visit left subtree
	Postorder(root->right);   // Visit right subtree
	printf("%c ",root->data); // Print data
}

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else 
		root->right = Insert(root->right,data);
	return root;
}
 
int main() {
	/*Code To Test the logic
	  Creating an example tree
	                    M
			   / \
			  B   Q
			 / \   \
			A   C   Z
    */
	Node* root = NULL;
	root = Insert(root,'M'); root = Insert(root,'B');
	root = Insert(root,'Q'); root = Insert(root,'Z'); 
	root = Insert(root,'A'); root = Insert(root,'C');
	//Print Nodes in Preorder. 
	cout<<"Preorder: ";
	Preorder(root);
	cout<<"\n";
	//Print Nodes in Inorder
	cout<<"Inorder: ";
	Inorder(root);
	cout<<"\n";
	//Print Nodes in Postorder
	cout<<"Postorder: ";
	Postorder(root);
	cout<<"\n";
}

判断是否为二叉搜索树

二叉搜索树定义是每个节点的左子树上的节点都比它小或等于，右子树都比它大

第一种通过遍历的方式判断，花费成本较高O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct Node{
    int data;
    Node *left;
    Node *right;
};
bool IsSubtreeLesser(Node* root, int value)
{
    if(root == NULL) return true;
    if(root->data<=value
      &&IsSubtreeLesser(root->left,value)
      &&IsSubtreeLesser(root->right,value))
        return true;
    else
        return false;
}
bool IsSubtreeGreater(Node* root, int value)    
{
    if(root == NULL) return true;
    if(root->data>value
      &&IsSubtreeGreater(root->left,value)
      &&IsSubtreeGreater(root->right,value))
        return true;
    else
        return false;
}
bool IsBinarySearchTree(Node* root)
{
    if(root == NULL) return true;
    if(IsSubtreeLesser5(root->left,root->data)
       && IsSubtreeGreater((root->left,root->data)
       && IsBinarySearchTree(root->left)
       && IsBinarySearchTree(root->right))  
       return true;
     else
       return false;
}

第二种方法，不需要比较一个节点的数据和他子树的所有节点 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool IsBstUtil(Node* root,int minValue,int maxValue)
{
    if(root == NULL) return true;
    if(root->data<minValue&&root->data>maxValue
      &&IsBstUtil(root->left,minValue,root->data)
      &&IsBstUtil(root->right,root-<data,maxValue)))  
       return true;
     else
       return false;
}
bool IsBinarySearchTree(Node* root)
{
    return IsBstutil(root,INT_MIN,INT_MAX);
}

二叉搜索树删除一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/* Deleting a node from Binary search tree */
#include<iostream>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};
//Function to find minimum in a tree. 
Node* FindMin(Node* root)
{
	while(root->left != NULL) root = root->left;
	return root;
}

// Function to search a delete a value from tree.
struct Node* Delete(struct Node *root, int data) {
	if(root == NULL) return root; 
	else if(data < root->data) root->left = Delete(root->left,data);
	else if (data > root->data) root->right = Delete(root->right,data);
	// Wohoo... I found you, Get ready to be deleted	
	else {
		// Case 1:  No child
		if(root->left == NULL && root->right == NULL) { 
			delete root;
			root = NULL;
		}
		//Case 2: One child 
		else if(root->left == NULL) {
			struct Node *temp = root;
			root = root->right;
			delete temp;
		}
		else if(root->right == NULL) {
			struct Node *temp = root;
			root = root->left;
			delete temp;
		}
		// case 3: 2 children
		else { 
			struct Node *temp = FindMin(root->right);
			root->data = temp->data;
			root->right = Delete(root->right,temp->data);
		}
	}
	return root;
}
 
//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;
 
	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}
 
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else 
		root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	            5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); root = Insert(root,10);
	root = Insert(root,3); root = Insert(root,4); 
	root = Insert(root,1); root = Insert(root,11);

	// Deleting node with value 5, change this value to test other cases
	root = Delete(root,5);

	//Print Nodes in Inorder
	cout<<"Inorder: ";
	Inorder(root);
	cout<<"\n";
}

二叉搜索树的中序后继节点

给定一个二叉树的节点，找到在二叉搜索树的中序遍历中紧跟着这个给定节点的下一个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/* C++ program to find Inorder successor in a BST */
#include<iostream>
using namespace std;
struct Node {
	int data;
	struct Node *left;
	struct Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
	if(root == NULL) return NULL;
	else if(root->data == data) return root;
	else if(root->data < data) return Find(root->right,data);
	else return Find(root->left,data);
}

//Function to find Node with minimum value in a BST
struct Node* FindMin(struct Node* root) {
	if(root == NULL) return NULL;
	while(root->left != NULL)
		root = root->left;
	return root;
}

//Function to find Inorder Successor in a BST
struct Node* Getsuccessor(struct Node* root,int data) {
	// Search the Node - O(h)
	struct Node* current = Find(root,data);
	if(current == NULL) return NULL;
	if(current->right != NULL) {  //Case 1: Node has right subtree
		return FindMin(current->right); // O(h)
	}
	else {   //Case 2: No right subtree  - O(h)
		struct Node* successor = NULL;
		struct Node* ancestor = root;
		while(ancestor != current) {
			if(current->data < ancestor->data) {
				successor = ancestor; // so far this is the deepest node for which current node is in left
				ancestor = ancestor->left;
			}
			else
				ancestor = ancestor->right;
		}
		return successor;
	}
}
 
//Function to visit nodes in Inorder
void Inorder(Node *root) {
	if(root == NULL) return;
 
	Inorder(root->left);       //Visit left subtree
	printf("%d ",root->data);  //Print data
	Inorder(root->right);      // Visit right subtree
}
 
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data)
		root->left = Insert(root->left,data);
	else 
		root->right = Insert(root->right,data);
	return root;
}
 
int main() {
	/*Code To Test the logic
	  Creating an example tree
	            5
			   / \
			  3   10
			 / \   \
			1   4   11
    */
	Node* root = NULL;
	root = Insert(root,5); root = Insert(root,10);
	root = Insert(root,3); root = Insert(root,4); 
	root = Insert(root,1); root = Insert(root,11);

	//Print Nodes in Inorder
	cout<<"Inorder Traversal: ";
	Inorder(root);
	cout<<"\n";

	// Find Inorder successor of some node. 
	struct Node* successor = Getsuccessor(root,1);
	if(successor == NULL) cout<<"No successor Found\n";
	else
    cout<<"Successor is "<<successor->data<<"\n";
}

图(graphs)

介绍

概念：

没有节点之间链接的功能

图是一个有序对，有顶集与边集组成，G=(V,E)是我们用来定义图的一个正确数学符号。

如上图，一共有8的节点和10条边。我们先要给这些节点起名字，将他们分位{v1,v2,,,,,v8}一共8个元素，这就是这个图的顶点集，而如何定义这个图的边集呢？

首先我们确定一条边是由两个端点连接而成，边集可以是有向（()）和无向的（{}），这里我们将其定义为无向的，E

c/c++学习笔记
#数据结构
深入浅出数据结构笔记
http://example.com/2023/05/05/深入浅出数据结构/
作者
fan fan
发布于
2023年5月5日
许可协议