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

【C语言版】数据结构教程(一)绪论(上)

【内容简介】本文整理数据结构(C语言版)相关内容的复习笔记,供各位朋友借鉴学习。本章内容更偏于记忆和理解,请读者们耐心阅读。

数据结构教程 · 绪论(上)

        本节学习目标

        1.1 基本概念

        1.2 抽象数据类型的表示与实现

本节学习目标

  • 熟悉数据结构相关的一些概念和术语
  • 了解如何书写抽象数据类型的形式定义

1.1 基本概念

下面我们简要介绍一下数据结构相关的一些概念和术语,这在之后的学习过程中都经常会用到。

1、数据(data)是所有能输入到计算机中并被计算机程序处理的符号的总称。例如:声音、图像、字符串等等。

2、数据元素(data system)是数据的基本单位。例如:下面这张“图”中由许多圆圈组成,这些圆圈就可以认为是数据元素。     

3、数据项(data item)是组成数据元素的单位,也是数据的不可分割的最小单位。例如:书籍的目录对于这本书而言是一个数据元素,目录中每一章的信息(章名、页码等)就是一个数据项。

4、数据对象(data object)是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合 N = {0,1,-1,2,-2,···}。

以上是数据的一些详细概念。而我们着重要学习的数据结构(data structure)是相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的关系称为结构(structure)。一般而言,数据元素之间存在以下 4 种基本结构:

  1. 集合:结构中的数据元素之间除了“同属于一个集合”之外,没有其它关系。
  2. 线性结构:结构中的数据元素之间存在一个对一个的关系。
  3. 树形结构:结构中的数据元素之间存在一个对多个的关系。
  4. 图状结构或网状结构:结构中的数据元素之间存在多个对多个的关系。

数据的定义方式并不唯一,除上述之外,还有一种形式定义:数据结构是一个二元组,

Data_Structure = { D,S }

其中:D 是数据元素的有限集,S是D上存在的关系的有限集。这样的说法比较抽象,我们举个例子:

【例1】现在我们需要编写一个公司职工管理系统,那么我们首先需要构思这个系统中的数据结构。假设这个公司有 1 个董事长,1 个总经理和 3 个员工,那么这个公司的职工之间存在的关系是:董事长管理总经理,总经理管理员工。则可以定义如下的数据结构:

Group = ( P,R )

其中:P 包含这个公司的所有职员,

           R = { R1,R2 },

           R1 = { <董事长,总经理> },

           R2 = { <总经理,员工1>,<总经理,员工2>,<总经理,员工3> }。

上述定义仅仅只是一种从对象的角度抽象出来的数学模型。结构定义中的“关系”描述为数据元素之间的逻辑关系,因此又称为数据的逻辑结构

但是,为了在计算机中实现对其的操作,还需要研究在计算机中如何来表示一个数据结构。数据结构在计算机中的表示称为数据的物理结构,又称为存储结构。它包括数据元素的表示以及关系的表示。在计算机中,表示信息的最小单位是二进制数的一位,叫做位(bit)。由若干个位组成的位串表示一个数据元素,通常称为元素结点,例如:用 8 位二进制数表示一个字符。

数据元素之间的关系在计算机中有两种不同的表示方法:顺序映像非顺序映像,并由此得到两种不同的存储结构:顺序存储结构链式存储结构

顺序映像的特点是,借助元素在存储器中的相对位置来表示逻辑关系,例如:假设用 2 个字长的位串表示一个实数,则相邻 4 个字长的位串可以表示一个复数。而对于非顺序映像而言,通常通过指针来指示元素存储地址,从而将数据元素之间的逻辑关系表示出来。如下图所示:

而存储结构可以分别用“一维数组”来描述顺序存储结构,用“指针”描述链式存储结构。

数据类型(data type)是和数据结构密切相关的一个概念。它包括了一个值的集合和定义在这个值集上的一组操作的总称。例如:C语言中的整型变量,其值集为某个区间上的整数,定义在上面的操作为加、减、乘、除和取模等算术运算。根据“值”的不同,数据类型可分为两类:一类是不可分解的原子类型,例如:实数;一类是由若干成分按某种结构组成,可以分解的结构类型,例如:数组。

1.2 抽象数据类型的表示与实现

抽象数据类型(abstract data type,简称 ADT)是指一个数学模型以及定义在该模型上的一组操作。也就是说,只要这个数据类型的逻辑特性不发生变化,就不影响它在外部的使用,类似我们常说的“面向对象的设计”原则。

一个含抽象数据类型的软件模块通常应包含定义、表示和实现 3 个部分。由于抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。按照其值的不同特性,可以分为:原子类型固定聚合类型可变聚合类型。后两者分别代表组成值的成分数量一定或是可变。

与数据结构的形式定义类似,抽象数据类型可用以下三元组表示:( D,S,P )。其中,D 是数据对象,S 是 D 上的关系集,P 是对 D 的基本操作集。具体来书写可以如下:

ADT 抽象数据类型名 {数据对象:<数据对象的定义>数据关系:<数据关系的定义>基本操作:<基本操作的定义>
} ADT 抽象数据类型名

其中,数据对象和数据关系的定义用伪码描述,基本操作的定义格式为:

基本操作名(参数表)初始条件:<初始条件描述>操作结果:<操作结果描述>

基本操作有两种参数:赋值参数只为操作提供输入值;引用参数以 & 打头,除了提供输入值以外,还将返回操作结果。

【例2】一个抽象数据类型三元组的定义:

ADT Triplet {

        数据对象:D = {e1, e2, e3 | e1, e2, e3 属于这个集合}

        数据关系:R1 = {<e1, e2> , <e2, e3>}

        基本操作:

                InitTriplet (&T, v1, v2, v3)

                        操作结果:构造三元组 T,元素 e1, e2, e3 分别被赋以参数 v1, v2,v3的值。

                DestroyTriplet (&T)

                        操作结果:三元组 T 被销毁。

                Get (T, i , &e)

                        初始条件:三元组 T 已存在,i = 1,2,3。

                        操作结果:用 e 返回 T 中第 i 个元素的值。

                ...

} ADT Triplet


继续阅读下一篇(点击跳转):【C语言版】数据结构教程(一)绪论(下)

相关文章:

【C语言版】数据结构教程(一)绪论(上)

【内容简介】本文整理数据结构&#xff08;C语言版&#xff09;相关内容的复习笔记&#xff0c;供各位朋友借鉴学习。本章内容更偏于记忆和理解&#xff0c;请读者们耐心阅读。 数据结构教程 绪论&#xff08;上&#xff09; 本节学习目标 1.1 基本概念 1.2 抽象数据类型的表示…...

酒后为什么总感觉渴?

喝酒后感到口渴&#xff0c;这种感觉其实很常见。这主要是因为酒精对我们的身体有几种影响。首先&#xff0c;酒精能够扩张血管&#xff0c;这会加快血液循环&#xff0c;让肾脏更加活跃&#xff0c;产生更多的尿液。这样一来&#xff0c;我们体内的水分就会通过排尿流失&#…...

Docker安装OwnCloud私有云盘对接ceph

一、安装OwnCloud 我的安装包链接&#xff1a;https://pan.baidu.com/s/1cJO8WEonsw4gGQWgQaYzpw?pwd6bak 提取码&#xff1a;6bak 启动OwnCloud容器&#xff0c;没有镜像会自动下载 docker run -d -p 80:80 -v /home/owncloud:/var/www/html --name owncloud --restartalway…...

创建了Vue项目,需要导入什么插件以及怎么导入

如果你不知道怎么创建Vue项目,建议可以看一看这篇文章 怎么安装Vue的环境和搭建Vue的项目-CSDN博客 1.在idea中打开目标文件 2.系在一个插件Vue.js 3.下载ELement UI 在Terminal中输入 # 切换到项目根目录 cd vueadmin-vue # 或者直接在idea中执行下面命令 # 安装element-u…...

abstract 关键字

在C#中&#xff0c;abstract 关键字是一个非常重要的特性&#xff0c;它用于定义抽象类和抽象成员&#xff08;如方法、属性、索引器、事件或操作符&#xff09;。使用 abstract 关键字的目的主要是为了提供一种机制&#xff0c;让基类能够指定一个或多个必须由派生类实现的方法…...

用Python编写你的网络监控系统详解

概要 在现代网络管理中,实时监控网络流量和状态是保证网络正常运行的关键。使用Python编写网络监控工具可以帮助管理员及时发现和解决网络问题。本文将详细介绍如何使用Python编写网络监控工具,包括基本概念、常用库及其应用场景,并提供相应的示例代码。 网络监控的基本概念…...

操作系统——虚拟内存

一、虚拟内存是什么&#xff1f; 虚拟内存类似一个桥梁&#xff0c;原来程序直接访问物理内存读取数据&#xff0c;现在程序直接访问虚拟内存&#xff0c;由虚拟内存再访问物理内存。 使用虚拟内存的好处&#xff1a; 隔离进程、提高内存使用安全性&#xff1a;每个进程直接…...

Zoom视频会议软件使用

Zoom 是一款广泛使用的视频会议软件,可以用于在线会议、网络研讨会、课堂教学、团队协作等。以下是使用 Zoom 的基本步骤和一些有用的技巧: 安装 Zoom 下载并安装: 访问 Zoom 下载页面。下载适用于你的操作系统(Windows, macOS, Linux, iOS, Android)的客户端。安装完成后…...

MVC软件设计模式及QT的MVC架构

目录 引言 一、MVC思想介绍 1.1 MCV模型概述 1.2 Excel的处理数据 1.3 MVC模式的优势 二、QT中的MVC 1.1 模型&#xff08;Model&#xff09; 1. QAbstractItemModel 2. QStringListModel 3. QStandardItemModel 4. QSqlTableModel 和 QSqlQueryModel 5. QAbstract…...

使用WSL通过SSH连接并运行图形界面程序

使用WSL通过SSH连接并运行图形界面程序 1. 在Windows上安装X服务器2. 配置并启动VcXsrv3. 在WSL Ubuntu中设置DISPLAY变量4. 从WSL Ubuntu连接到远程服务器5. 在远程服务器上设置DISPLAY变量6. 测试X11转发7. 运行您的安装程序注意事项 在Windows Subsystem for Linux (WSL) 上…...

柳湛宇-简历

...

6-1 从全连接层到卷积

我们之前讨论的多层感知机十分适合处理表格数据&#xff0c;其中行对应样本&#xff0c;列对应特征。 对于表格数据&#xff0c;我们寻找的模式可能涉及特征之间的交互&#xff0c;但是我们不能预先假设任何与特征交互相关的先验结构。 此时&#xff0c;多层感知机可能是最好的…...

【Android Studio】项目目录结构

文章目录 常用视图Android视图project视图 gradlebuild.gradleSDK 路径主题入口程序 常用视图 Android视图 project视图 gradle build.gradle SDK 路径 主题 入口程序...

electron-builder打包vue2项目问题合集

一、打包之后不显示elecmentui的图标 1、使用版本 vue ^2.6.14element-ui ^2.15.14vue-cli-plugin-electron-builder 2.1.1 2、解决办法 1&#xff09; 如果是简单的图标可以使用图片代替&#xff08;这种对于elementui组件的图标还是不会显示&#xff09; 2&#xff09;在v…...

5行代码快速Git配置ssh

0 流程步骤 检查本地主机是否已经存在ssh key生成ssh key获取ssh key公钥内容&#xff08;id_rsa.pub&#xff09;复制该内容&#xff0c;到Github账号上添加公钥&#xff0c;进入Settings设置验证是否设置成功 1 代码 # 1.检查本地主机是否已经存在ssh key cd ~/.ssh ls # …...

气相色谱检测常见问题和实战案例分享-测试狗

气相色谱检测常见问题和实战案例分享 气相色谱GC是一种高效、灵敏的分离和分析技术&#xff0c;广泛应用于石油化工、环境保护、食品安全、药物分析等领域&#xff1b;在使用气相色谱进行检测时&#xff0c;可能会遇到一些常见问题&#xff0c;本文将分享一些实战案例&#xff…...

一文学会CUDA编程:深入了解CUDA编程与架构(一)

前言&#xff1a; CUDA&#xff08;Compute Unified Device Architecture&#xff0c;统一计算设备架构&#xff09;是由NVIDIA公司开发的一种并行计算平台和编程模型。CUDA于2006年发布&#xff0c;旨在通过图形处理器&#xff08;GPU&#xff09;解决复杂的计算问题。在早期…...

Jquery判断图片加载失败,显示默认图片

//加载图片 出现404状态时触发 $(img).error(function () { //将加载不到的图片的src属性时&#xff0c;修改成默认图片&#xff0c;注意&#xff1a;默认图片必须保证存在&#xff0c;否则会一直调用此函数&#xff0c;造成死循环。$(this).attr("src", "Imag…...

App 自动化测试调研

App 自动化测试调研 App 自动化测试的价值 App 自动化测试在软件开发过程中扮演着重要的角色&#xff0c;具有以下几个方面的价值&#xff1a; 1.提高测试效率和覆盖率&#xff1a;自动化测试可以执行大量的测试用例&#xff0c;覆盖各种功能和场景&#xff0c;相比手动测试…...

Java 后端已经过时的技术,也是我逝去的青春

最近这段时间收到了一些读者的私信&#xff0c;问我某个技术要不要学&#xff0c;还有一些的同学竟然对 Java 图形化很感兴趣&#xff0c;还想找这方面的工作。 我接触 Java 已近 10多年了&#xff0c;见证了许多 Java 技术变迁&#xff0c;包括&#xff1a; JavaEE 框架&…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...