数据结构笔记

绪论

数据元素

1
**数据项构成数据元素的最小单位**，一个数据集元素可以有多个数据项

数据对象

1
【定义】具有相同性质的数据元素的集合，是数据的一个子集【例】所有学生的信息可以作为一个数据对象。

数据类型

1
2
【定义】是一组值的集合和定义在该集合上的操作的总和。
其中有原子类型（不可再分割）、结构类型（多个原子类型值的组合）、抽象数据类型

数据结构

1
2
3
【定义】数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

有相互的关系的数据集合

数据结构三要素

数据的逻辑结构

集合
线性结构
树形结构
图形结构

数据的存储结构

顺序存储

顺序存储结构：把数据元素放到地址连续的存储单元里面，其数据间的逻辑关系和物理关系是一致的。

链式存储

链式存储结构：把数据元素放到任意的存储单元里面，这组存储单元可以是连续的，也可以是不连续的。

索引存储

索引存储结构：在存储数据的同时，还建立附加的索引表，索引表中的每个元素都含有该数据元素在存储器中的地址。

逻辑关系通过指针表示

散列存储(哈希存储)

散列存储结构：根据关键字直接计算出该数据元素的存储地址，即地址= f(关键字)。 比特币的挖矿就是用的散列存储结构。

复杂度

时间复杂度

时间复杂度：一个算法执行所耗费的时间。

常数阶O(1)

这种与问题规模的大小无关（n的多少），执行时间恒定的算法，O（1）时间复杂度，又叫做常数阶复杂度。

1
2
3
int sum = 0, n = 100; /*执行一次*/
sum = (1 + n) * n / 2; /*执行一次*/
printf("%d\n", sum); /*执行一次*/

线性阶O(n)

1
2
3
for (i = 0; i < n; i++) { /*执行n次*/
    printf("%d\n", i); /*执行n次*/
}

对数阶O(log2n)

1
2
3
4
5
int count = 1;
while (count < n) { /*执行log2n次*/
    count = count * 2;
    /*执行log2n次*/
}

由于每次count乘以2之后，就距离n更近了一分。也就是说，有多少个2相乘后大于n，则会退出循环。由2＾x＝n 得到x＝1og2（n）。所以这个循环的时间复杂度

平方阶O(n＾2)

1
2
3
4
5
6
int i, j;
for (i = 0; i < n; i++) { /*执行n次*/
    for (j = 0; j < n; j++) { /*执行n次*/
        printf("%d %d\n", i, j); /*执行n*n次*/
    }
}

推导时间复杂度的方法

当运行时间只有常数时，则用1来代替。
在得到的运行次数函数中，只【保留最高阶】，且【除去最高阶项中相乘的常数】

1
执行次数函数为3n＾2＋2n＋1，则时间复杂度为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
void BubbkeSort(int* a,int n)
{
    assert(a);
    for(size_t end=n;end>0;--end)
    {
        int exchange=0;
        for(size_t i=1;i<end;++i)
        {
            if(a[i-1]>a[i])
            {
                Swap(&a[i-1],&a[i]);
                exchange=1;
            }
        }
        if(exchange==0)
            break;
    }
}

空间复杂度：O(1)
解析：这里其实总共开辟了三个空间，分别为end、exchange、i，
既然是常数个变量，那么空间复杂度就是0（1），空间复杂度算的是申请的额外空间所以跟上面的int＊a和int n没有关系。

O(1)和O(n)的区别

malloc一个数组 int a=(int)malloc(sizeof(int)*numssize);//0(N) 此情况的前提是numsSize必须是个未知的数字，如果是具体数字，那么空间复杂度依旧是0（1）
变长数组 int a［numsSize］；／／numsSize未知，0（N）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
long long* Fibonacci(size_t n)
{
    if(n==0)
        return NULL;
    long long* fibArray = (long long*)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for(int i=2;i<=n;++i)
    {
        fibArray[i] = fibArray[i-1] + fibArray[i-2];
    }
    return fibArray;
}

空间复杂度：O(n)

这里看到了malloc开辟了n＋1个大小为1ong long类型的数组，看到这就不需要再过多计较后续创建了几个变量，因为空间复杂度是估算，所以直接就是O（N）

阶乘递归Fac的空间复杂度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
long long Fac(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N-1)*N;
}

空间复杂度：O(N)

这里看到了递归调用了N次，每次都会开辟一个栈帧，所以空间复杂度就是O（N）

线性表

线性表可以分为数组(顺序表)和链表两种存储结构。

前驱元素: 若A元素在B元素的前面，则称A为B的前驱元素。

后继元素: 若B元素在A元素的后面，则称B为A的后继元素。

特征: 数据元素之间只有一对一的关系

头节点: 第一个有效节点之前的节点第一个数据元素没有前驱

尾节点: 最后一个有效节点之后的节点最后一个数据元素没有后继

顺序表(数组)

顺序表是以数组的形式存储

优点: - 查询速度快，时间复杂度为O(1)

缺点 - 插入和删除速度慢，时间复杂度为O(n) - 表中元素个数需要提前定义

特点: 逻辑地址相邻物理地址也相邻

顺序表基本操作功能实现

线性表的静态定义

1
2
3
4
5
6
#define MAXSIZE 100 // 定义线性表的最大长度
typedef int ElemType; // 定义数据元素的类型
typedef struct {
    ElemType data[MAXSIZE]; // 用静态的“数组”存放数据元素
    int length; // 线性表当前长度
} SqList; // 顺序表的类型定义

线性表的静态初始化

1
2
3
4
5
6
void InitList(SqList &L) {
    for (int i = 0; i < MAXSIZE; i++) {
        L.data[i] = 0; // 将所有数据元素的值设置为默认值
    }
    L.length = 0; // 将线性表的当前长度设置为0
}

线性表的插入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) { // 判断i的范围是否有效
        return false;
    }
    if (L.length >= MAXSIZE) { // 当前存储空间已满，不能插入
        return false;
    }
    for (int j = L.length; j >= i; j--) { // 将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e; // 在位置i处放入e
    L.length++; // 线性表长度增1
    return true;
}

线性表的删除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) { // 判断i的范围是否有效
        return false;
    }
    e = L.data[i - 1]; // 将被删除的元素赋值给e
    for (int j = i; j < L.length; j++) { // 将第i个元素之后的元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--; // 线性表长度减1
    return true;
}

线性表的按索引查找

1
2
3
ElemType GetElem(SqlList L,int i){
    return L.data[i-1];
}

线性表的按值查找

1
2
3
4
5
6
ElemType LocateElem(SqlList L,ElemType e){ 
    for(int i =0;i <L.length;i ++) 
        if(L.data[i]==e)
            return i+1; 
    return 0;
}

动态增长内存

1
2
3
4
5
6
7
8
void IncreaseSize(SqlList &L,int len){
    int *p =L.data;
    L.data =(int *)malloc((L.maxsize+len)*sizeof(int));
    for(int i =0;i <L.length;i ++)
        L.data[i]=p[i];
    L.maxsize=L.maxsize+len;
    free(p);
}

链表

分为单向链表和双向链表

特点: 逻辑地址相邻物理地址不一定相邻

单向链表

1
2
3
每一个结点由一个数据域和一个指针域组成，数据域是用来存储数据，指针域是用来指向下一个结点
头结点的数据域不存储数据
尾结点的指针域是空的。

初始化单链表

1
2
3
4
5
template <typename DataType> LinkList<DataType>::LinkList()
{ 
    first=new Node<DataType>; //生成头节点
    first->next = nullptr;  //头节点指针域置空
}

头插法建立单链表

1
2
s->next=first->next; //将s的指针域指向第一个结点
first->next=s; //将头结点的指针域指向s

尾插法建立单链表

1
2
3
r->next=s; //将尾结点的指针域指向s
r=s; //将尾结点指针指向s
r->next=nullptr; //尾结点指针域置空

判空操作

1
只需要判断first->next是否为空即可

求表长操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int LinkList<DataType>::Length()
{
    Node<DataType> *p=first->next; //p指向第一个结点
    int count=0; //计数器
    while(p!=nullptr) //p不为空
    {
        count++; //计数器加1
        p=p->next; //p指向下一个结点
    }
    return count;
}

按位查找操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
DataType LinkList<DataType>::Get(int i)
{
    Node<DataType> *p=first->next; //p指向第一个结点
    int count=1; //计数器
    while(p!=nullptr&&count<i) //p不为空且计数器小于i
    {
        p=p->next; //p指向下一个结点
        count++; //计数器加1
    }
    if(p==nullptr) //p为空
        throw "位置非法"; //抛出异常
    else
        return p->data; //返回第i个结点的数据域
}

即使知道访问节点的需要，也不能像顺序表那样直接按序号查找，只能从头指针出发顺next域的方向一个一个查找，直到找到第i个结点为止。

按值查找操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int LinkList<DataType>::Locate(DataType x)
{
    Node<DataType> *p=first->next; //p指向第一个结点
    int count=1; //计数器
    while(p!=nullptr&&p->data!=x) //p不为空且p的数据域不等于x
    {
        p=p->next; //p指向下一个结点
        count++; //计数器加1
    }
    if(p==nullptr) //p为空
        return 0; //返回0
    else
        return count; //返回结点序号
}

对单链表中的元素依次进行比较，直到找到值为x的结点，返回元素的序号

插入操作

 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
void LinkList<DataType>::Insert(int i,DataType x)
{
    Node<DataType> *p=first; //p指向头结点
    int count=0; //计数器
    while(p!=nullptr&&count<i-1) //p不为空且计数器小于i-1
    {
        p=p->next; //p指向下一个结点
        count++; //计数器加1
    }
    if(p==nullptr) //p为空
        throw "位置非法"; //抛出异常
    else
    {
        Node<DataType> *s=new Node<DataType>; //生成新结点
        s->data=x; //新结点数据域赋值
        s->next=p->next; //新结点指针域指向p的后继结点
        p->next=s; //p的指针域指向新结点
    }
}

在单链表中插入节点时指针的变化情况
s->next=p->next; //新结点指针域指向p的后继结点
p->next=s; //p的指针域指向新结点

在不带头节点的单链表中插入节点时指针的变化情况
s->next=first; //新结点指针域指向头结点
first=s; //头结点指针域指向新结点
s->next=p->next; //新结点指针域指向p的后继结点
p->next=s; //p的指针域指向新结点

删除操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void LinkList<DataType>::Remove(int i)
{
    Node<DataType> *p=first; //p指向头结点
    int count=0; //计数器
    while(p!=nullptr&&count<i-1) //p不为空且计数器小于i-1
    {
        p=p->next; //p指向下一个结点
        count++; //计数器加1
    }
    if(p==nullptr) //p为空
        throw "位置非法"; //抛出异常
    else
    {
        Node<DataType> *q=p->next; //q指向p的后继结点
        if(q==nullptr) //q为空
            throw "位置非法"; //抛出异常
        else
        {
            p->next=q->next; //p的指针域指向q的后继结点
            delete q; //释放q
        }
    }
}

销毁单链表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void LinkList<DataType>::Destroy()
{
    Node<DataType> *p=first; //p指向头结点
    while(p!=nullptr) //p不为空
    {
        Node<DataType> *q=p->next; //q指向p的后继结点
        delete p; //释放p
        p=q; //p指向q
    }
    first=nullptr; //头指针置空
}

双链表

每个节点在存储数据元素的同时，还存储了其前驱元素和后记元素所在的地址信息


prior	data	next

插入操作

1
2
3
4
5
在节点p后面插入节点s，需要修改4个指针
s->prior=p; //s的前驱指针指向p
s->next=p->next; //s的后继指针指向p的后继结点
p->next->prior=s; //p的后继结点的前驱指针指向s
p->next=s; //p的后继指针指向s

删除操作

1
2
(p->prior)->next=p->next; //p的前驱结点的后继指针指向p的后继结点
(p->next)->prior=p->prior; //p的后继结点的前驱指针指向p的前驱结点

循环链表的实现

循环链表是一种头尾相接的链表，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环

1
2
3
4
s = new Node;
s->data =x;
s->next = p-> next;
p->next=s;

普通	循环
开始节点：first->next	rear->next->next
终端节点：O(n)	rear

栈

限定仅在一端进行插入和删除操作的线性表

栈顶: 允许插入和删除的一端栈底: 不允许插入和删除的一端

栈的操作特性

插入操作: 入栈，进栈，压栈，push 删除操作: 出栈，退栈，弹栈，pop

操作特性：先进后出，后进先出

例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？

c b a
b c a

栈只是对插入和删除操作的位置进行了限制并没有限定插入和删除操作进行的时间

栈的抽象数据类型定义

顺序栈

顺序栈的存储结构定义

顺序栈的类定义

顺序栈的实现——入栈

顺序栈的实现——出栈

顺序栈的实现——判空

栈链

栈链: 栈的链式存储结构，即链栈

栈链的存储结构定义

栈链的实现——入栈

栈链的实现——出栈

队列

队列: 只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队尾元素队头元素

队列的操作特性

队列的操作特性: 先进先出，后进后出

队列的抽象数据类型定义

顺序队列

循环队列

链队列

循环队列与链队列比较

时间性能：都需要O(1)时间

空间性能：循环队列需要预先分配空间，所以有存储元素个数和空间浪费的问题，链队列不需要

串

串的基本概念

串: 由零个或多个字符组成的有限序列

空串: 零个字符组成的串，长度为0

子串: 串中任意个连续的字符组成的子序列

子串与子序列的区别: 子串是串的一个部分，子序列是串的一个子集

串的抽象数据类型定义

串的存储结构

用一个变量来表示串的实际长度
用数组的0号单元存放串的长度，从1号单元开始存放串值
在串尾存储一个不会在串中出现的特殊字符作为串的终结符，表示串的结尾

BF算法

暴力匹配算法(Brute Force)，也叫朴素匹配算法

BF算法实例

def brute_force(text, pattern): n = len(text) m = len(pattern)

for i in range(n - m + 1):
    j = 0
    while j < m and text[i + j] == pattern[j]:
        j += 1

    if j == m:
        return i

return -1

text = “Hello, world!” pattern = “world”

result = brute_force(text, pattern) if result != -1: print(f"Pattern found at index {result}") else: print(“Pattern not found”)

BF伪代码实现

def brute_force(text, pattern): n = len(text) m = len(pattern)

for i in range(n - m + 1):
    j = 0
    while j < m and text[i + j] == pattern[j]:
        j += 1

    if j == m:
        return i

return -1

text = “Hello, world!” pattern = “world”

result = brute_force(text, pattern) if result != -1: print(f"Pattern found at index {result}") else: print(“Pattern not found”) # BF算法伪代码

函数 brute_force(文本, 模式):
    n = 文本的长度
    m = 模式的长度

    对于 i 从 0 到 n - m + 1:
        j = 0
        当 j < m 且 文本[i + j] 等于 模式[j] 时:
            j += 1

        如果 j 等于 m:
            返回 i

    返回 -1

文本 = "Hello, world!"
模式 = "world"

结果 = brute_force(文本, 模式)
如果 结果 不等于 -1:
    打印 "在索引 " + 结果 + " 处找到模式"
否则:
    打印 "未找到模式"

平均比较次数：(n-m)/2 O(n+m)

最坏情况：(n+m)/2 O(n*m)

KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

KMP算法的核心思想是：当子串与目标字符串不匹配时，其实你已经知道了前面已经匹配成功那一部分的字符（包括子串与目标字符串）。以阮一峰的文章为例，当空格与D不匹配时，你其实知道前面六个字符是“ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把“搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

详解KMP算法[https://www.cnblogs.com/dusf/p/kmp.html]

数组

二维数组的内存结构

数组没有插入和删除操作，所以不用预留空间，适合顺序存储

特殊矩阵的压缩存储

特殊矩阵的压缩要求：保证随机存取的功能，即在O(1)时间内找到任意一个元素

压缩存储对称矩阵

只存下三角部分元素

压缩存储三角矩阵

上（下）三角部分的元素 相同的常数只存储一个

对角矩阵

稀疏矩阵的压缩存储

稀疏矩阵: 矩阵中有很多元素，并且分布没有规律，但是大部分元素都是0

三元组表

十字链表

广义表

广义表又称列表，是一种线性存储结构

可存储不可再分的元素也能存储可在分元素

举例

A = (): A表示一个广义表，只不过表是空的 B = (e): 广义表B中职业一个原子e C =(a,(b,c,d)):广义表C中有两个元素，原子a和子表(b,c,d)

树

度数

结点拥有的子树数目称为结点的度

二叉树

满二叉树和完全二叉树是两种不同的二叉树结构。

满二叉树是一种特殊的二叉树，其中每个非叶子节点都有两个子节点，且所有叶子节点都在同一层上。换句话说，满二叉树的每一层都是满的。

完全二叉树是一种二叉树，其中除了最后一层外，其他层的节点都是满的，并且最后一层的节点都尽可能地靠左排列。换句话说，完全二叉树是在满二叉树的基础上，去掉了最后一层的一些节点。

二叉树的性质

二叉树存储

顺序存储

链式存储

二叉树的遍历

先序遍历

(1) 先访问根节点

(2) 再访问左子树

(3) 最后访问右子树

先序遍历的结果为 ABCDEFG

 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
#include <iostream>

// TreeNode 表示二叉树的节点
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// preorderTraversal 执行二叉树的先序遍历
void preorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        // 先访问根节点
        std::cout << root->value << " ";
        // 递归遍历左子树
        preorderTraversal(root->left);
        // 递归遍历右子树
        preorderTraversal(root->right);
    }
}

int main() {
    // 创建一个简单的二叉树
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 进行先序遍历
    std::cout << "先序遍历结果: ";
    preorderTraversal(root);

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

//输出 1 2 4 5 3 

中序遍历

先访问左子树
再访问根节点
最后访问右子树

 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
#include <iostream>

// TreeNode 表示二叉树的节点
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// inorderTraversal 执行二叉树的中序遍历
void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        // 递归遍历左子树
        inorderTraversal(root->left);
        // 访问根节点
        std::cout << root->value << " ";
        // 递归遍历右子树
        inorderTraversal(root->right);
    }
}

int main() {
    // 创建一个简单的二叉树
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 进行中序遍历
    std::cout << "中序遍历结果: ";
    inorderTraversal(root);

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

//结果 4 2 5 1 3

后序遍历

先访问左子树
再访问右子树
最后访问根节点

 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
#include <iostream>

// TreeNode 表示二叉树的节点
struct TreeNode {
    int value;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

// postorderTraversal 执行二叉树的后序遍历
void postorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        // 递归遍历左子树
        postorderTraversal(root->left);
        // 递归遍历右子树
        postorderTraversal(root->right);
        // 访问根节点
        std::cout << root->value << " ";
    }
}

int main() {
    // 创建一个简单的二叉树
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    // 进行后序遍历
    std::cout << "后序遍历结果: ";
    postorderTraversal(root);

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

//结果 4 5 2 3 1

二叉排序树(二叉搜索树)

特点

若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值
左、右子树也分别为二叉排序树
中序遍历的序列是递增的序列

中序序列为： 47 58 62 73 88 99

代码题

求二叉树所有节点个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int size = 0;
void TreeSize(BTNode* root)
{
    if(root == NULL)
    {
        return;
    }
    else
    {
        ++size;
    }
    TreeSize(root->left);
    TreeSize(root->right);
}

求二叉树叶子节点个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int TreeLeafSize(BTNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    if(root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

求二叉树的高度

1
2
3
4
5
6
7
/*递归走到树的最底层，再通过比较左右子树的高度，取较高一颗+1，一直累加到树根*/
int Height(Tree& t){
    if(t == NULL){
        return 0;
    }
    return Height(t->left) > Height(t->right) ? Height(t->left) + 1 : Height(t->right) + 1;
}

输出二叉树中所有叶子节点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
void PrintLeaves(BinTree BT)
{
    if(BT)
    {
        if(!BT->Left && !BT->Right)
        {
            printf("%d ", BT->Data);
        }
        PrintLeaves(BT->Left);
        PrintLeaves(BT->Right);
    }
}

绪论#

数据元素#

数据对象#

数据类型#

数据结构#

数据的存储结构#

顺序存储#

链式存储#

索引存储#

散列存储(哈希存储)#

复杂度#

时间复杂度#

常数阶O(1)#

线性阶O(n)#

对数阶O(log2n)#

平方阶O(n＾2)#

推导时间复杂度的方法#

常见的时间复杂度#

空间复杂度#

O(1)和O(n)的区别#

阶乘递归Fac的空间复杂度#

线性表#

顺序表(数组)#

顺序表基本操作功能实现#

线性表的静态定义#

线性表的静态初始化#

线性表的插入#

线性表的删除#

线性表的按索引查找#

线性表的按值查找#

动态增长内存#

链表#

单向链表#

初始化单链表#

头插法建立单链表#

尾插法建立单链表#

判空操作#

求表长操作#

按位查找操作#

按值查找操作#

插入操作#

删除操作#

销毁单链表#

双链表#

插入操作#

删除操作#

循环链表的实现#

栈#

栈的操作特性#

栈的抽象数据类型定义#

顺序栈#

顺序栈的存储结构定义#

顺序栈的类定义#

顺序栈的实现——入栈#

顺序栈的实现——出栈#

顺序栈的实现——判空#

栈链#

栈链的存储结构定义#

栈链的实现——入栈#

栈链的实现——出栈#

队列#

队列的操作特性#

队列的抽象数据类型定义#

顺序队列#

循环队列#

链队列#

循环队列与链队列比较#

串#

串的基本概念#

串的抽象数据类型定义#

串的存储结构#

BF算法#

BF算法实例#

BF伪代码实现#

KMP算法#

数组#

特殊矩阵的压缩存储#

压缩存储对称矩阵#

压缩存储三角矩阵#

对角矩阵#

绪论

数据元素

数据对象

数据类型

数据结构

数据的存储结构

顺序存储

链式存储

索引存储

散列存储(哈希存储)

复杂度

时间复杂度

常数阶O(1)

线性阶O(n)

对数阶O(log2n)

平方阶O(n＾2)

推导时间复杂度的方法

常见的时间复杂度

空间复杂度

O(1)和O(n)的区别

阶乘递归Fac的空间复杂度

线性表

顺序表(数组)

顺序表基本操作功能实现

线性表的静态定义

线性表的静态初始化

线性表的插入

线性表的删除

线性表的按索引查找

线性表的按值查找

动态增长内存

链表

单向链表

初始化单链表

头插法建立单链表

尾插法建立单链表

判空操作

求表长操作

按位查找操作

按值查找操作

插入操作

删除操作

销毁单链表

双链表

插入操作

删除操作

循环链表的实现

栈

栈的操作特性

栈的抽象数据类型定义

顺序栈

顺序栈的存储结构定义

顺序栈的类定义

顺序栈的实现——入栈

顺序栈的实现——出栈

顺序栈的实现——判空

栈链

栈链的存储结构定义

栈链的实现——入栈

栈链的实现——出栈

队列

队列的操作特性

队列的抽象数据类型定义

顺序队列

循环队列

链队列

循环队列与链队列比较

串

串的基本概念

串的抽象数据类型定义

串的存储结构

BF算法

BF算法实例

BF伪代码实现

KMP算法

数组

特殊矩阵的压缩存储

压缩存储对称矩阵

压缩存储三角矩阵

对角矩阵