数据结构备考笔记

2025-05-12

学习

6.1k words

阅读次

——Smiling

0 前言

本笔记写于2025年年中，为应对程序设计与数据结构-2的期末考试而写。主要针对的是在各类复习资料以及历年上交各班的期末考试试卷中出现的有关各类数据结构的易错点和考点，以供复习之用。

1 Notes

记录一下在考卷中遇到的自己不熟的内容：

struct edgeNode{//存储边的结点类
    int end;//终点
    edgeNode *next;
    edgeNode(int e, edgeNode *n= NULL) { 
        end = e, next = n;
    }
}
struct verNode {//存储顶点的结点类
    TypeOfVer ver, //顶点值
    edgeNode *head; //对应的单链表的头指针
    verNode(edgeNode *h=NULL){ 
        head = h;
    }
}

class adjListGraph{
private:
    verNode* verList; //图中结点组成的动态数组
    int Vers, Edges; //图中结点数及边数
public:
    void allVetexes(TypeOfVer v) const;
};
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

   这个邻接表模板各个老师都经常用，特别是程序题作为base给出，需要熟悉。

   verNode存的是ver：顶点值，以及一个edgeNode指针head，表示第一个他指出的边，然后就可以通过这个head不断next找到所有的他指出来的边。每个边的end是边指向的点。

2. ST表->习题课的数据结构都复习了吗

3. 各种排序：基数排序、**快排**、...

4. AVL树的平衡调整

5. 外排序，置换选择，磁带排序

6. 树状数组

7. LZW压缩与解码

8. B树、B+树性质，插入删除操作

9. queue（队列）的pop不返回值，所以要先用front获取再pop，stack也是（好像）。弄清楚每种数据结构能做的有什么事

10. n阶B树：根节点存至少一个，其他节点存至少 $\lceil n/2 \rceil - 1$ 个数据，至多 $n - 1$  个，节点的分叉数量为数据个数+1，叶子和非叶子都可以存数据

    n阶B树：根节点存至少一个，其他节点存至少 $\lceil n/2 \rceil$ 个数据，至多 $n$  个，节点的分叉数量为数据个数，只有叶子存数据，非叶子只存索引

11. 构造函数不能是虚函数，但析构函数可以是虚函数，而且最好是虚函数。如果派生类新增加的数据成员中含有指针，指向动态申请的内存，那么派生类必须定义析构函数释放这部分空间。但如果派生类的对象是通过基类的指针操作的，则delete基类指针指向的对象就会造成内存泄漏

12. 二叉树查找的时候如果要返回一个指针，则需要用&.

    ```c++
    class node{
        Key data;
    }
    Key* find(node *root,Key a){
        return &(root->data);
    }

单调队列求滑动窗口，单调栈求左右最大最小数。具体的代码实现需要掌握
访问者模式（虽然是拓展，但是有空可以稍微我看一下）代码见附录。
表达式。中缀后缀
大作业的实现：hashmap，linked_hashmap，LRU，deque，Cow_trie，ESet，B+树
c++20，把27 28 ppt学一遍
哈希表中的各种方式。迟删除，指向函数的指针，该函数将关键字转换为整型数等内容
再过一遍ppt中的所有代码中的有注释的部分，考试很可能直接拿源代码搬上来问
各种小算法的伪代码，例如mst的Kruskal和Prim
操作系统内部，函数调用用栈来实现
优先队列与普通队列（先进先出）的最大区别在于：每个元素都有一个优先级，队列的输出顺序由元素的优先级决定，而非进入队列的先后顺序。用堆实现
拓扑排序，要么用BFS每次找汇点（出度为0）输出删除，要么用DFS的post倒序排序

2 Questions

可通过同时使用按高度并和路径压缩提高并查集的性能：为什么错了？（23John-15)
哈希函数确定查找成功所需的平均元素比较次数和查找不成功所需的平均元素比较次数，为什么查找不成功要+1？在空的时候不是直接返回false吗？(23John-二.4)
树的高度到底是怎么定义的？eg.24John-8
Fortune要考吗（224john-二6）
LRU-k算法没看明白（2024john-二9）
2024John-二12看不懂

int DelRepeat(){
    std::map<elemType , int> mp;
    for(int i = 0 ; i < currentLength ; i++){
        mp[data[i]]++;
        if(mp[data[i]] >= 2){
            
        }
    }
}

3 附录

访问者模式

# include <cstdio>
# include <algorithm>
# include <cmath>
# include <cstring>
# include <iostream>
# include <queue>
# include <vector>

using namespace std;

#include <iostream>
#include <memory>
using namespace std;

// 前置声明访问者接口
class ExprVisitor;

// 表达式基类：定义accept接口
class Expr {
public:
    virtual void accept(ExprVisitor& visitor) = 0;
    virtual ~Expr() = default;
};

// 访问者接口：声明对每种表达式类型的操作
class ExprVisitor {
public:
    virtual void visitLit(class Lit& lit) = 0;
    virtual void visitAdd(class Add& add) = 0;
    virtual void visitSub(class Sub& sub) = 0;  // 新增类型时在此扩展接口
};

// 具体表达式类：Lit（常量）
class Lit : public Expr {
private:
    int value;
public:
    Lit(int v) : value(v) {}
    void accept(ExprVisitor& visitor) override { visitor.visitLit(*this); }
    int getValue() const { return value; }
};

// 具体表达式类：Add（加法）
class Add : public Expr {
private:
    shared_ptr<Expr> left, right;
public:
    Add(shared_ptr<Expr> l, shared_ptr<Expr> r) : left(l), right(r) {}
    void accept(ExprVisitor& visitor) override { visitor.visitAdd(*this); }
    shared_ptr<Expr> getLeft() const { return left; }
    shared_ptr<Expr> getRight() const { return right; }
};

// 具体表达式类：Sub（减法，新增类型）
class Sub : public Expr {
private:
    shared_ptr<Expr> left, right;
public:
    Sub(shared_ptr<Expr> l, shared_ptr<Expr> r) : left(l), right(r) {}
    void accept(ExprVisitor& visitor) override { visitor.visitSub(*this); }
    shared_ptr<Expr> getLeft() const { return left; }
    shared_ptr<Expr> getRight() const { return right; }
};

// 求值操作访问者（新增操作无需改表达式类）
class EvalVisitor : public ExprVisitor {
public:
    int result;
    void visitLit(Lit& lit) override { result = lit.getValue(); }
    void visitAdd(Add& add) override {
        add.getLeft()->accept(*this);
        int leftVal = result;
        add.getRight()->accept(*this);
        result = leftVal + result;
    }
    void visitSub(Sub& sub) override {
        sub.getLeft()->accept(*this);
        int leftVal = result;
        sub.getRight()->accept(*this);
        result = leftVal - result;
    }
};

// 打印操作访问者（新增操作无需改表达式类）
class PrintVisitor : public ExprVisitor {
public:
    void visitLit(Lit& lit) override { cout << lit.getValue(); }
    void visitAdd(Add& add) override {
        cout << "(";
        add.getLeft()->accept(*this);
        cout << "+";
        add.getRight()->accept(*this);
        cout << ")";
    }
    void visitSub(Sub& sub) override {
        cout << "(";
        sub.getLeft()->accept(*this);
        cout << "-";
        sub.getRight()->accept(*this);
        cout << ")";
    }
};

// 示例用法
int main() {
    // 构建表达式：(5 - (3 + 2))
    auto expr = make_shared<Sub>(
        make_shared<Lit>(5),
        make_shared<Add>(make_shared<Lit>(3), make_shared<Lit>(2))
    );

    // 求值操作
    EvalVisitor evaluator;
    expr->accept(evaluator);
    cout << "Value: " << evaluator.result << endl;  // 输出 Value: 0

    // 打印操作
    PrintVisitor printer;
    expr->accept(printer);  // 输出 (5-(3+2))
    return 0;
}

2024-2-12

12. 1) 假设我们正在编写一个有关几何的程序，其中需要用到点和向量。从数学角度看，两者都是实数的三元组，但是从编程角度看，我们往往要对两者做不同的处理，因此我们希望把它们区分成两个类。但是，两者在代码上有很多重复的地方，比如都有三个坐标，都能进行线性插值（但是点和向量之间不能），等等。前者可以用继承处理，但是后者由于是二元运算并且要返回自己的类型，相对不好处理。有一个技巧可以处理这一种情况。我们这样定义基类： 
template <class Self> 
class Tuple3 { 
public: 
  float x, y, z; 
  // 构造函数略 
  Self Lerp(float p, Self c) { 
    return {p*x + (1-p)*c.x, p*y + (1-p)*c.y, p*z + (1-p)*c.z}; 
  } 
}; 
我们希望达成下面的效果： 
int main() { 
  Point3 p(0., 0., 0.); 
  Point3 q(1., 1., 1.); 
  Vector3 v(1., 1., 1.); 
  // 正确 
  Point3 r = p.Lerp(0.3, q); 
  // 编译时报错 
  // Point3 e = p.Lerp(0.7, v); 
} 
请写出子类 Point3 和 Vector3 如何定义。（ 4 ） 
    
2) 在上面的定义中，三个分量都是单精度浮点数。有时，我们使用整数即可，因此我们希望分量的类型也是模板参数。当两个有相同模板类但分量类型不同的点或者向量运算时，得到的结果是精度比较高的那一类。请写出新的基类，以及如何继承。（ 3 ） 
  提示：模板参数可以本身是一个模板。 
  提示：函数的返回值可以这么写：auto f(...) -> T { ... } 
        这样，在类型 T 中，可以引用参数的类型。 
  提示：我们可以用 T{} 得到类型 T 的默认值，即使 T 是一个标量。 
  提示：我们可以用 decltype(...) 得到一个表达式的类型。

Categories

Tags

Archives

Recent Posts

数据结构备考笔记

0 前言

1 Notes

2 Questions

3 附录