数据结构知识的遗忘

发表于 | 分类于

今天对链表，堆栈，队列，二叉树东西进行了总结：

链表

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/*结构*/
typedef struct node
{
    int data;
    struct node *next;
}node ,*link;
/*创建，逆序创建*/
link creath()
{
    node *l;
    l=(node *)malloc(sizeof(node));
    l->next=NULL;
    int x;
    while(~scanf("%d",&x))
    {
        node *p;
        p=(node *)malloc(sizeof(node));
        p->data=x;
        p->next=l->next;
        l->next=p;
    }
    return l;
}
/*创建，顺序创建*/
link creatt()
{
    node *l,*r;
    l=(node *)malloc(sizeof(node));
    l->next=NULL;
    r=l;
    int x;
    while(~scanf("%d",&x))
    {
        node *p;
        p=(node *)malloc(sizeof(node));
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
    }
    r->next=NULL;
    return l;
}
/*删除*/
link linkdelete(link l,int x)
{
    link p,pre;
    p=l->next;
    while(p->data!=x)
    {
        pre=p;
        p=p->next;
    }
    pre->next=p->next;
    free(p);
    return l;
}
``` 
### 堆栈：
``` bash
/*结构*/
typedef struct
{
    int *base;
    int *top;
    int stacksize;
}sqstack;
/*创建一个空栈*/
int init(sqstack &s)
{
    s.base=(int *)malloc(15*sizeof(int));
    s.top=s.base;
    s.stacksize=15;
    return 1;
}
/*销毁栈*/
int destroy(sqstack &s)
{
    s.top=NULL;
    s.stacksize=0;
    free(s.base);
    return 1;
}
/*清空栈*/
int empy(sqstack s)
{
    if(s.top==s.base)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
/*求栈的长度*/
int stacklength(sqstack s)
{
    if(s.top==s.base)
    {
        return 0;
    }
    else
    {
        return(s.top-s.base);
    }
}
/*求栈顶元素*/
int gettop(sqstack s,int &e)
{
    if(s.top==s.base)
    {
        return 0;
    }
    else
    {
        e=*(s.top-1);
    }
    return e;
}
/*栈顶插入元素*/
int push(sqstack s,int &e)
{
    *s.top=e;
    s.top++;
    return 1;
}

堆栈，队列相关c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*堆栈*/
stack s;
s.push(x) //入栈
s.pop()   //出栈
s.top()   //取栈顶
s.empty()  //判断是否为空；
s.size()   //判断堆栈的长度；
/*队列*/
queue q;
q.push(x)  //入队
q.pop()    //出队
q.front()  //队首元素
q.back()   //队尾元素
q.empty()  //判断队是否为空

二叉树

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 <iostream>
using namespace std;
typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}*bitree,node;
void create(bitree &t)
{
    char ch;
    cin>>ch;
    if(ch=='#') t=NULL;
    else
    {
        t=new node;
        t->data=ch;
        create(t->lchild);
        create(t->rchild);
    }
}
void inorder(bitree t)
{
    if(t)
    {
        inorder(t->lchild);
        cout<<t->data;
        inorder(t->rchild);
    }
}
/*树的深度*/
int depth(bitree t)
{
    if(t==NULL)
    {
        return 0;
    }
    else
    {
        int m=depth(t->lchild);
        int n=depth(t->rchild);
        if(m>n)
            return m+1;
        else
            return n+1;
    }
}
/*节点个数*/
int nodecount(bitree t)
{
    if(t==NULL)
        return 0;
    else
        return nodecount(t->lchild)+nodecount(t->rchild)+1;
}

二叉树通过两种遍历的方式（其中中序遍历一定已知），得知另一种遍历的方式

1
2
3
已知先序遍历与中序遍历解题思路：
*******中序遍历里一个字母的两边是左右子树*********
*******后续遍历的特点是给一棵树的根是最后访问的******
Fork me on GitHub