当前位置: 首页 > news >正文

考研必备~总结严蔚敏教授《数据结构》课程的重要知识点及考点

作者主页:知孤云出岫

总结严蔚敏教授《数据结构》课程的重要知识点及考点,并罗列重要的实操代码如下:
在这里插入图片描述

1. 基本概念

1.1 数据结构的定义
  • 数据:数据是信息的符号表示,可以是数值、字符、图像等。
  • 数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
1.2 抽象数据类型 (ADT)
  • 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。

2. 线性表

2.1 顺序表
  • 定义:顺序表是用一段地址连续的存储单元依次存储线性表的数据元素。
  • 操作:插入、删除、查找等。

关键代码:

typedef struct {ElemType *data;int length;
} SqList;void InitList(SqList *L) {L->data = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));L->length = 0;
}
2.2 链表
  • 定义:链表是通过链式存储结构存储线性表的数据元素。
  • 类型:单链表、双链表、循环链表。

关键代码:

typedef struct Node {ElemType data;struct Node *next;
} Node, *LinkList;void InitList(LinkList *L) {*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL;
}

3. 栈和队列

3.1 栈
  • 定义:栈是一种后进先出(LIFO)的线性表。
  • 操作:进栈、出栈、取栈顶元素等。

关键代码:

#define MAXSIZE 100
typedef struct {ElemType data[MAXSIZE];int top;
} SqStack;void InitStack(SqStack *S) {S->top = -1;
}
3.2 队列
  • 定义:队列是一种先进先出(FIFO)的线性表。
  • 类型:顺序队列、链式队列、循环队列。

关键代码:

#define MAXSIZE 100
typedef struct {ElemType data[MAXSIZE];int front;int rear;
} SqQueue;void InitQueue(SqQueue *Q) {Q->front = 0;Q->rear = 0;
}

4. 树和二叉树

4.1 树的基本概念
  • 定义:树是n(n>=0)个结点的有限集。
  • 类型:二叉树、平衡二叉树、完全二叉树等。
4.2 二叉树
  • 遍历:前序遍历、中序遍历、后序遍历、层序遍历。

关键代码:

typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;void PreOrderTraverse(BiTree T) {if(T != NULL) {printf("%c", T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}

5. 图

5.1 图的基本概念
  • 定义:图是由顶点的有穷非空集合和顶点之间边的集合组成。
  • 表示:邻接矩阵、邻接表等。
5.2 图的遍历
  • 深度优先搜索 (DFS)
  • 广度优先搜索 (BFS)

关键代码:

#define MAXVEX 100
typedef struct {char vexs[MAXVEX];int arc[MAXVEX][MAXVEX];int numVertexes, numEdges;
} MGraph;void DFS(MGraph G, int i) {visited[i] = TRUE;printf("%c ", G.vexs[i]);for(int j = 0; j < G.numVertexes; j++) {if(G.arc[i][j] == 1 && !visited[j])DFS(G, j);}
}

6. 查找和排序

6.1 查找
  • 顺序查找:适用于线性表。
  • 二分查找:适用于有序数组。

关键代码:

int BinarySearch(int *a, int n, int key) {int low = 0, high = n - 1;while(low <= high) {int mid = (low + high) / 2;if(a[mid] == key) return mid;else if(a[mid] > key) high = mid - 1;else low = mid + 1;}return -1;
}
6.2 排序
  • 交换排序:冒泡排序、快速排序。
  • 选择排序:简单选择排序、堆排序。
  • 插入排序:直接插入排序、希尔排序。
  • 归并排序:两路归并排序。

关键代码:

void QuickSort(int *a, int low, int high) {if(low < high) {int pivot = Partition(a, low, high);QuickSort(a, low, pivot-1);QuickSort(a, pivot+1, high);}
}int Partition(int *a, int low, int high) {int pivot = a[low];while(low < high) {while(low < high && a[high] >= pivot) high--;a[low] = a[high];while(low < high && a[low] <= pivot) low++;a[high] = a[low];}a[low] = pivot;return low;
}

7. 重点考点

  • 各种数据结构的定义和特点。
  • 各种数据结构的基本操作及其实现。
  • 树和图的遍历算法。
  • 常见的排序和查找算法及其时间复杂度分析。
  • 通过实际代码理解和掌握数据结构的实现和应用。

这些内容涵盖了《数据结构》课程的重要知识点及其考点,并通过关键代码片段帮助理解和实操。

相关文章:

考研必备~总结严蔚敏教授《数据结构》课程的重要知识点及考点

作者主页&#xff1a;知孤云出岫 目录 1. 基本概念1.1 数据结构的定义1.2 抽象数据类型 (ADT) 2. 线性表2.1 顺序表2.2 链表 3. 栈和队列3.1 栈3.2 队列 4. 树和二叉树4.1 树的基本概念4.2 二叉树 5. 图5.1 图的基本概念5.2 图的遍历 6. 查找和排序6.1 查找6.2 排序 7. 重点考…...

【数据分享】国家级旅游休闲街区数据(Excel/Shp格式/免费获取)

之前我们分享过从我国文化和旅游部官网整理的2018-2023年我国50个重点旅游城市星级饭店季度经营状况数据&#xff08;可查看之前的文章获悉详情&#xff09;&#xff01;文化和旅游部官网上也分享有很多与旅游相关的常用数据&#xff0c;我们基于官网发布的名单文件整理得到全国…...

Linux开发:进程间通过Unix Domain Socket传递数据

进程间传递数据的方式有很多种,Linux还提供一种特殊的Socket用于在多进程间传递数据,就是Unix Domain Socket(UDS)。 虽然通过普通的Socket也能做到在多进程间传递数据,不过这样需要通过协议栈层的打包与拆包,未免有些浪费效率,通过UDS,数据仅仅通过一个特殊的sock文件…...

Redis基础教程(九):redis有序集合

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; &#x1f49d;&#x1f49…...

Servlet与Servlet容器

什么是Servlet? Servlet是Java EE&#xff08;现称Jakarta EE&#xff09;中的一个组件&#xff0c;通常用于创建动态Web内容。Servlet是运行在Web服务器上的Java程序&#xff0c;它处理客户端的请求并生成响应。Servlet的核心功能是处理HTTP请求和响应。下面是一个servlet例…...

腾讯centos mysql安装

腾讯centos mysql安装 腾讯云提供了一系列的云计算服务&#xff0c;包括操作系统、数据库、服务器等。在腾讯云上安装CentOS操作系统和MySQL数据库可以按照以下步骤进行&#xff1a; 登录腾讯云控制台&#xff08;登录 - 腾讯云&#xff09;。在控制台页面上方的搜索框中输入…...

c_各个unsigned int 和 int的取值范围

bool, uint8_t, uint16_t, uint32_t, uint64_t, int8_t, int16_t, int32_t, int64_t 取值范围分别是什么&#xff1f; 定义形式&#xff1a; typedef unsigned char uint8_t; typedef unsigned short uint16_t; typedef unsigned int uint32_t; typedef unsigned long uint64_…...

C#/WPF 自制截图工具

在日常使用电脑办公时&#xff0c;我们经常遇到需要截图然后保存图片&#xff0c;我们往往需要借助安装截图工具才能实现&#xff0c;现在我们通过C#自制截图工具&#xff0c;也能够轻松进行截图。 我们可以通过C#调用WindousAPI来实现截图&#xff0c;实例代码如下&#xff1a…...

以腾讯为例,手把手教你搭建产品帮助中心

一个精心设计的产品帮助中心对于提高用户满意度和体验至关重要。腾讯&#xff0c;作为全球领先的互联网企业&#xff0c;通过其多样化的产品线&#xff08;包括微信、QQ、腾讯游戏、腾讯视频等&#xff09;吸引了亿万用户。下面将以腾讯为例&#xff0c;向您展示如何搭建一个高…...

计算机网络概述--自我学习用

计算网络体系概述 相关问题 计算机网络为什么要分层&#xff1f;计算机网络是怎么分层的&#xff1f;三种计算机网络模型的关系是什么&#xff1f;每一层分别包含哪些协议&#xff1f;计算机网络中&#xff0c;数据如何在各层中传播&#xff1f;数据在网络各层中的存在形式是…...

超级好用的java http请求工具

kong-http 基于okhttp封装的轻量级http客户端 使用方式 Maven <dependency><groupId>io.github.kongweiguang</groupId><artifactId>kong-http</artifactId><version>0.1</version> </dependency>Gradle implementation …...

在原有的iconfont.css文件中加入新的字体图标

前言&#xff1a;在阿里图标库中&#xff0c;如果你没有这个字体图标的线上项目&#xff0c;那么你怎么在本地项目中的原始图标文件中添加新的图标呢&#xff1f; 背景&#xff1a;现有一个vue项目&#xff0c;下面是这个前端项目的字体图标文件。现在需要新开发功能页&#x…...

使用 ESP32-WROOM + DHT11 做个无屏温湿度计

最近梅雨天&#xff0c;有个房间湿度很大&#xff0c;而我需要远程查看温湿度&#xff0c;所以无所谓有没有显示屏&#xff0c;某宝上的温湿度计都是带屏的&#xff0c;如果连WIFI查看温湿度操作也比较麻烦&#xff0c;还需要换电池&#xff0c;实在不能满足我的需求&#xff0…...

如何使用 SwiftUI 构建 visionOS 应用

文章目录 前言WindowsVolumes沉浸式空间结论 前言 Apple Vision Pro 即将推出&#xff0c;现在是看看 SwiftUI API 的完美时机&#xff0c;这使我们能够将我们的应用程序适应 visionOS 提供的沉浸式世界。苹果表示&#xff0c;构建应用程序的最佳方式是使用 Swift 和 SwiftUI。…...

InspireFace-商用级的跨平台开源人脸分析SDK

InspireFace-商用级的跨平台开源人脸分析SDK InspireFaceSDK是由insightface开发的⼀款⼈脸识别软件开发⼯具包&#xff08;SDK&#xff09;。它提供了⼀系列功能&#xff0c;可以满⾜各种应⽤场景下的⼈脸识别需求&#xff0c;包括但不限于闸机、⼈脸⻔禁、⼈脸验证等。 该S…...

华为HCIP Datacom H12-821 卷24

1.单选题 企业大楼有大量员工通常都在上班时在大厅开始接入到公司的WLAN网络,随着每位员工走到各自的工位过程中,每个人的移动端叶通过漫游的方式漫游到各自的网络覆盖区域。为了尽量保证每个终端的IP地址是固定的,建议的做法是? A、配置VLAN Pool并配置顺序算法 B、…...

TikTok马来西亚直播网络怎么配置?

TikTok是一款全球流行的社交媒体应用&#xff0c;在东南亚地区拥有大量用户。在马来西亚这个多元化的国家&#xff0c;配置高效稳定的直播网络对TikTok的运营至关重要。 配置马来西亚直播网络的必要性 广泛的地理覆盖&#xff1a;马来西亚包括大片陆地和众多岛屿&#xff0c;网…...

基于若依的文件上传、下载

基于若依实现文件上传、下载 文章目录 基于若依实现文件上传、下载1、前端实现-文件上传1.1 通用上传分析1.2 修改实现上传接口 2、后端实现-文件上传3、后端实现-文件下载4、前端实现-文件下载 官网其实也写了&#xff0c;但是我是自己改造封装了一下&#xff0c;再次迈向全栈…...

论文回顾 | CVPR 2021 | How to Calibrate Your Event Camera | 基于图像重建的事件相机校准新方法

论文速览 | CVPR 2021 | How to Calibrate Your Event Camera | 基于图像重建的事件相机校准新方法 1 引言 在计算机视觉和机器人领域,相机校准一直是一个基础而又重要的问题。传统的相机校准方法主要依赖于从已知校准图案中提取角点,然后通过优化算法求解相机的内参和外参。这…...

高级java每日一道面试题-2024年7月1日

题目&#xff1a;请解释 Java 中的内存泄漏&#xff0c;并说明如何检测和避免内存泄漏。 答案&#xff1a; 内存泄漏指的是程序中不再使用的对象&#xff0c;由于某些原因没有被垃圾回收器回收&#xff0c;仍然占据着内存空间&#xff0c;导致可用内存逐渐减少&#xff0c;最…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...