【数据结构与算法】数据结构知识点总结_数据结构与算法知识点总结

---

前言

数据结构是计算机科学中的一个重要主题，它涉及到如何组织和存储数据，以便于在计算机程序中进行访问和操作。以下是一些常见的数据结构及其用途：

1. 数组：数组是一种简单的数据结构，它可以存储一系列相同类型的数据。数组的主要优点是可以快速访问任何一个元素。数组的缺点是大小固定，一旦分配了内存空间，就无法改变。

2. 链表：链表是一种动态数据结构，可以在运行时添加或删除元素。链表的主要优点是可以动态地分配内存空间，但是访问链表中的任何一个元素需要遍历整个链表，所以访问速度较慢。

3. 栈：栈是一种后进先出（LIFO）的数据结构。它通常用于存储临时数据，例如函数调用时的局部变量。栈的主要优点是可以快速访问最后一个元素，但是不能随机访问栈中的其他元素。

4. 队列：队列是一种先进先出（FIFO）的数据结构。它通常用于实现缓冲区或消息队列。队列的主要优点是可以快速访问最后一个元素和第一个元素，但是不能随机访问队列中的其他元素。

5. 树：树是一种层次结构，它可以用于表示有父子关系的数据。树的主要优点是可以快速查找和插入元素，但是删除元素比较麻烦。

6. 图：图是一种非常灵活的数据结构，可以用于表示复杂的关系。图的主要优点是可以表示各种类型的关系，但是访问和操作图比较复杂。

---

一、数组

数组是数据结构中最基本的一种数据类型，它可以存储一组相同类型的数据，并通过下标来访问其中的元素。以下是一些关于数组的知识点总结：

（一）知识点

（二）常用操作代码示例

以下是C++中数组的基本操作示例：

1. 声明数组

int arr[5]; //声明一个长度为5的整型数组
1

2. 初始化数组

int arr[5] = {1, 2, 3, 4, 5}; //声明一个长度为5的整型数组，并初始化为1,2,3,4,5
1

3. 访问数组元素

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0] << endl; //输出数组第一个元素，即1
1
2

4. 修改数组元素

int arr[5] = {1, 2, 3, 4, 5};
arr[0] = 0; //将数组第一个元素修改为0
1
2

5. 遍历数组

int arr[5] = {1, 2, 3, 4, 5};
for (int i = 0; i < 5; i++) {
    cout << arr[i] << " "; //输出数组所有元素
}
1
2
3
4

6. 数组作为函数参数

void printArray(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        cout << arr[i] << " "; //输出数组所有元素
    }
}

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    printArray(arr, 5); //将数组作为函数参数传递
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11

二、链表

链表是数据结构中一种常用的线性结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。以下是一些关于链表的知识点总结：

（一）知识点

（二）常用操作代码示例

以下是C++中链表的基本操作示例：

1. 定义链表节点结构体

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
1
2
3
4
5

2. 创建链表

ListNode* head = new ListNode(1); //创建头节点
ListNode* node1 = new ListNode(2); //创建第一个节点
ListNode* node2 = new ListNode(3); //创建第二个节点
head->next = node1; //头节点指向第一个节点
node1->next = node2; //第一个节点指向第二个节点
1
2
3
4
5

3. 遍历链表

ListNode* p = head; //从头节点开始遍历
while (p != NULL) {
    cout << p->val << " "; //输出节点值
    p = p->next; //指向下一个节点
}
1
2
3
4
5

4. 插入节点

ListNode* newNode = new ListNode(4); //创建新节点
ListNode* p = head; //从头节点开始遍历
while (p->next != NULL) {
    p = p->next; //指向下一个节点
}
p->next = newNode; //将新节点插入到链表末尾
1
2
3
4
5
6

5. 删除节点

ListNode* p = head; //从头节点开始遍历
while (p->next != NULL && p->next->val != 3) {
    p = p->next; //指向下一个节点
}
if (p->next != NULL) {
    ListNode* temp = p->next; //保存要删除的节点
    p->next = temp->next; //删除节点
    delete temp; //释放内存
}
1
2
3
4
5
6
7
8
9

三、栈

栈是数据结构中一种常用的线性结构，它遵循先进后出的原则，即最后进入的元素最先弹出。以下是一些关于栈的知识点总结：

（一）知识点

（二）常用操作代码示例

以下是C++中栈的基本操作示例：

1. 头文件引用

#include <stack>
1

2. 声明栈

stack<int> s; //声明一个整型栈
1

3. 入栈

s.push(1); //将1入栈
s.push(2); //将2入栈
1
2

4. 出栈

s.pop(); //将栈顶元素2出栈
1

5. 访问栈顶元素

cout << s.top() << endl; //输出栈顶元素1
1

6. 判断栈是否为空

if (s.empty()) {
    cout << "栈为空" << endl;
} else {
    cout << "栈不为空" << endl;
}
1
2
3
4
5

四、队列

队列是数据结构中一种常用的线性结构，它遵循先进先出的原则，即最先进入的元素最先弹出。以下是一些关于队列的知识点总结：

（一）知识点

（二）常用操作代码示例

以下是C++中队列的基本操作示例：

1. 头文件引用

#include <queue>
1

2. 声明队列

queue<int> q; //声明一个整型队列
1

3. 入队

q.push(1); //将1入队
q.push(2); //将2入队
1
2

4. 出队

q.pop(); //将队首元素1出队
1

5. 访问队首元素

cout << q.front() << endl; //输出队首元素2
1

6. 访问队尾元素

cout << q.back() << endl; //输出队尾元素2
1

7. 判断队列是否为空

if (q.empty()) {
    cout << "队列为空" << endl;
} else {
    cout << "队列不为空" << endl;
}
1
2
3
4
5

五、树

树是数据结构中一种非线性结构，它由多个节点和边组成，节点之间有父子关系。以下是一些关于树的知识点总结：

（一）知识点

（二）常用操作代码示例

以下是C++中二叉树的基本操作示例：

1. 定义二叉树节点结构体

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1
2
3
4
5
6

2. 创建二叉树

TreeNode* root = new TreeNode(1); //创建根节点
TreeNode* node1 = new TreeNode(2); //创建左子节点
TreeNode* node2 = new TreeNode(3); //创建右子节点
root->left = node1; //根节点的左子节点为node1
root->right = node2; //根节点的右子节点为node2
1
2
3
4
5

3. 遍历二叉树

• 前序遍历

void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        cout << root->val << " "; //输出节点值
        preorderTraversal(root->left); //遍历左子树
        preorderTraversal(root->right); //遍历右子树
    }
}
1
2
3
4
5
6
7

preorderTraversal(root); //从根节点开始前序遍历

• 中序遍历

void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left); //遍历左子树
        cout << root->val << " "; //输出节点值
        inorderTraversal(root->right); //遍历右子树
    }
}
inorderTraversal(root); //从根节点开始中序遍历
1
2
3
4
5
6
7
8

• 后序遍历

void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left); //遍历左子树
        postorderTraversal(root->right); //遍历右子树
        cout << root->val << " "; //输出节点值
    }
}
postorderTraversal(root); //从根节点开始后序遍历
1
2
3
4
5
6
7
8

4. 插入节点

TreeNode* newNode = new TreeNode(4); //创建新节点
TreeNode* p = root; //从根节点开始遍历
while (p->left != NULL) {
    p = p->left; //指向左子节点
}
p->left = newNode; //将新节点插入到最左侧
1
2
3
4
5
6

5. 删除节点

TreeNode* p = root; //从根节点开始遍历
while (p->left != NULL && p->left->val != 2) {
    p = p->left; //指向左子节点
}
if (p->left != NULL) {
    TreeNode* temp = p->left; //保存要删除的节点
    p->left = temp->left; //删除节点
    delete temp; //释放内存
}
1
2
3
4
5
6
7
8
9

六、图

图是数据结构中一种非线性结构，它由多个节点和边组成，节点之间可以有多条边连接。以下是一些关于图的知识点总结：

（一）知识点

（二）常用操作代码示例

以下是C++中图的基本操作示例：

1. 头文件引用

#include <vector>
#include <queue>
1
2

2. 定义图节点结构体

struct GraphNode {
    int val;
    vector<GraphNode*> neighbors;
    GraphNode(int x) : val(x) {}
};
1
2
3
4
5

3. 创建图

GraphNode* node1 = new GraphNode(1);
GraphNode* node2 = new GraphNode(2);
GraphNode* node3 = new GraphNode(3);
node1->neighbors.push_back(node2);
node1->neighbors.push_back(node3);
node2->neighbors.push_back(node1);
node2->neighbors.push_back(node3);
node3->neighbors.push_back(node1);
node3->neighbors.push_back(node2);
1
2
3
4
5
6
7
8
9

4. 遍历图

• 广度优先遍历

void bfs(GraphNode* node) {
    queue<GraphNode*> q;
    q.push(node); //将起始节点加入队列
    unordered_set<GraphNode*> visited; //记录已经访问过的节点
    visited.insert(node); //将起始节点标记为已访问
    while (!q.empty()) {
        GraphNode* curr = q.front(); //取出队首节点
        q.pop(); //将队首节点出队
        cout << curr->val << " "; //输出节点值
        for (auto neighbor : curr->neighbors) {
            if (visited.find(neighbor) == visited.end()) { //如果邻居节点未被访问过
                visited.insert(neighbor); //将邻居节点标记为已访问
                q.push(neighbor); //将邻居节点加入队列
            }
        }
    }
}
bfs(node1); //从节点1开始广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 深度优先遍历

void dfs(GraphNode* node, unordered_set<GraphNode*>& visited) {
    visited.insert(node); //将节点标记为已访问
    cout << node->val << " "; //输出节点值
    for (auto neighbor : node->neighbors) {
        if (visited.find(neighbor) == visited.end()) { //如果邻居节点未被访问过
            dfs(neighbor, visited); //递归遍历邻居节点
        }
    }
}
unordered_set<GraphNode*> visited; //记录已经访问过的节点
dfs(node1, visited); //从节点1开始深度优先遍历
1
2
3
4
5
6
7
8
9
10
11

---

总结

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。