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

2024-06-02 12:34| 来源: 网络整理| 查看: 265

@TOC

前言

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

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

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

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

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

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

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

一、数组

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

（一）知识点概念说明数组的定义数组是一种由相同类型的元素组成的集合，这些元素在内存中是连续存储的。数组的大小在创建时就确定了，无法在运行时改变。数组的下标数组的下标从零开始，最大值为数组长度减一。可以使用下标来访问数组中的元素，例如arr[0]表示数组中的第一个元素。多维数组数组也可以是多维的，例如二维数组就是由多个一维数组组成的。访问多维数组中的元素需要使用多个下标，例如arr[0][0]表示二维数组中的第一个元素。数组的初始化数组可以在创建时进行初始化，也可以在之后的代码中进行初始化。如果没有初始化，数组中的元素将会是随机值。数组的遍历可以使用for循环来遍历数组中的所有元素。数组的排序可以使用Arrays类提供的sort方法对数组中的元素进行排序。Arrays.sort(arr); 数组的复制可以使用Arrays类提供的copyOf方法复制数组，int[] arr2 = Arrays.copyOf(arr, arr.length); （二）常用操作代码示例

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

1. 声明数组 int arr[5]; //声明一个长度为5的整型数组 2. 初始化数组 int arr[5] = { 1, 2, 3, 4, 5}; //声明一个长度为5的整型数组，并初始化为1,2,3,4,5 3. 访问数组元素 int arr[5] = { 1, 2, 3, 4, 5}; cout 1, 2, 3, 4, 5}; for (int i = 0; i for (int i = 0; i int arr[5] = { 1, 2, 3, 4, 5}; printArray(arr, 5); //将数组作为函数参数传递 return 0; } 二、链表

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

（一）知识点概念说明链表的定义链表是一种线性结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的节点不一定是连续存储的，每个节点可以单独分配内存空间。链表的分类链表可以分为单向链表、双向链表和循环链表三种。单向链表每个节点只有一个指针指向下一个节点，双向链表每个节点有两个指针分别指向前一个节点和下一个节点，循环链表的尾节点指向头节点。链表的操作链表的基本操作包括插入、删除和查找。插入和删除操作需要修改节点的指针，查找操作需要遍历链表。链表的优缺点链表的优点是可以动态地分配内存空间，插入和删除操作效率高，缺点是访问链表中的任意节点需要遍历整个链表，效率较低。链表的应用链表在计算机科学中有广泛的应用，例如实现栈、队列、哈希表等数据结构，还可以用于表示多项式、图等抽象数据类型。（二）常用操作代码示例

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

1. 定义链表节点结构体 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(NULL) { } }; 2. 创建链表 ListNode* head = new ListNode(1); //创建头节点 ListNode* node1 = new ListNode(2); //创建第一个节点 ListNode* node2 = new ListNode(3); //创建第二个节点 head->next = node1; //头节点指向第一个节点 node1->next = node2; //第一个节点指向第二个节点 3. 遍历链表 ListNode* p = head; //从头节点开始遍历 while (p != NULL) { cout p = p->next; //指向下一个节点 } if (p->next != NULL) { ListNode* temp = p->next; //保存要删除的节点 p->next = temp->next; //删除节点 delete temp; //释放内存 } 三、栈

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

（一）知识点概念说明栈的定义栈是一种线性结构，它只允许在一端进行插入和删除操作。栈遵循先进后出的原则，即最后进入的元素最先弹出。栈的基本操作栈的基本操作包括入栈（push）、出栈（pop）、查看栈顶元素（peek）和判断栈是否为空（isEmpty）。栈的实现栈可以使用数组或链表来实现。使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈。栈的应用栈在计算机科学中有广泛的应用，例如实现函数调用、表达式求值、括号匹配、迷宫路径搜索等。栈的复杂度入栈、出栈、查看栈顶元素和判断栈是否为空的时间复杂度均为O(1)。（二）常用操作代码示例

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

1. 头文件引用 #include 2. 声明栈 stack s; //声明一个整型栈 3. 入栈 s.push(1); //将1入栈 s.push(2); //将2入栈 4. 出栈 s.pop(); //将栈顶元素2出栈 5. 访问栈顶元素 cout cout cout } }; 2. 创建二叉树 TreeNode* root = new TreeNode(1); //创建根节点 TreeNode* node1 = new TreeNode(2); //创建左子节点 TreeNode* node2 = new TreeNode(3); //创建右子节点 root->left = node1; //根节点的左子节点为node1 root->right = node2; //根节点的右子节点为node2 3. 遍历二叉树前序遍历 void preorderTraversal(TreeNode* root) { if (root != NULL) { cout inorderTraversal(root->left); //遍历左子树 cout postorderTraversal(root->left); //遍历左子树 postorderTraversal(root->right); //遍历右子树 cout p = p->left; //指向左子节点 } if (p->left != NULL) { TreeNode* temp = p->left; //保存要删除的节点 p->left = temp->left; //删除节点 delete temp; //释放内存 } 六、图

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

（一）知识点概念说明图的定义图是一种非线性结构，它由多个节点和边组成，节点之间可以有多条边连接。图分为有向图和无向图，有向图中每条边都有一个方向，无向图中每条边没有方向。图的基本概念图的基本概念包括节点、边、度、路径、连通性、权重等。图的遍历图的遍历分为深度优先遍历和广度优先遍历。深度优先遍历和树的深度优先遍历类似，广度优先遍历和树的层次遍历类似。图的实现图可以使用邻接矩阵或邻接表来实现。邻接矩阵使用二维数组表示图中节点之间的连接关系，邻接表使用链表表示图中节点之间的连接关系。图的应用图在计算机科学中有广泛的应用，例如实现路由算法、社交网络分析、图像处理等。图的复杂度图的遍历时间复杂度为O(n+m)，其中n为图中节点的个数，m为图中边的个数。（二）常用操作代码示例

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

1. 头文件引用 #include #include 2. 定义图节点结构体 struct GraphNode { int val; vector neighbors; GraphNode(int x) : val(x) { } }; 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); 4. 遍历图广度优先遍历 void bfs(GraphNode* node) { queue q; q.push(node); //将起始节点加入队列 unordered_set visited; //记录已经访问过的节点 visited.insert(node); //将起始节点标记为已访问 while (!q.empty()) { GraphNode* curr = q.front(); //取出队首节点 q.pop(); //将队首节点出队 cout //如果邻居节点未被访问过 visited.insert(neighbor); //将邻居节点标记为已访问 q.push(neighbor); //将邻居节点加入队列 } } } } bfs(node1); //从节点1开始广度优先遍历深度优先遍历 void dfs(GraphNode* node, unordered_set& visited) { visited.insert(node); //将节点标记为已访问 cout //如果邻居节点未被访问过 dfs(neighbor, visited); //递归遍历邻居节点 } } } unordered_set visited; //记录已经访问过的节点 dfs(node1, visited); //从节点1开始深度优先遍历总结

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

【本文地址】

公司简介

联系我们