精华内容
下载资源
问答
  • 抽象数据结构三个组成部分
    千次阅读
    2021-08-30 17:23:21

    数据结构的基本概念

    一、基本概念与术语

    1.数据

    数据是信息的载体,是计算机程序加工的原料。

    2.数据元素

    数据元素是数据的基本单位,通常作为一个整体进行考虑,一个数据元素由若干数据项组成。

    3.数据对象

    数据对象是具有相同性质的数据元素的集合。

    4.数据结构

    数据结构是相互间存在一种或多种特定关系的数据元素的集合。

    5.各代表范围

    数据 > 数据结构 = 数据对象 > 数据元素 > 数据项

    数据结构与数据对象都由数据元素组成,区别在于数据结构注重数据元素间的关系,数据对象注重数据元素中是否有相同性质。

    6.数据类型

    原子类型

    其值不可再分的数据类型,如:int、double、bool等基本类型。

    结构类型

    其值可再分的的数据类型,如C语言中的struct结构体,Java中的实体类、视图类等。

    抽象数据类型*

    抽象数据结构(Abstract Data Type,ADT)是计算机科学中具有类似行为的特定类别的数据结构的数学模型;或者具有类似语义的一种或多种程序设计语言的数据类型。

    其定义了一个抽象的数据组织及其相关操作,可以用一个ADT定义一个完整的数据结构。

    二、数据结构三要素

    数据结构的三要素为:数据的逻辑结构、数据的存储结构(物理结构)、数据的运算

    按逻辑结构划分,数据结构可划分为:集合结构、线性结构、树形结构、图状结构

    按物理结构划分,数据结构可划分为:顺序存储、链式存储、索引存储、散列存储

    数据的运算其定义上是针对逻辑结构的,实现上是针对物理结构的

    更多相关内容
  • 三个抽象数据类型抽象数据类型(ADT)一、列表 ADT1. 实现列表ADT的两种数据结构:数组(array-based)和链表(linked list)2. 链表的结构3. 操作:二、栈 ADT1. 插入和删除都在同一个地方(在top),First In ...


    对之前学的一些知识点做个总结,比较简略。记录一些容易忘记的点。

    抽象数据类型(ADT)

    数据结构的基本概念和术语可参考:数据结构基本概念定义(挺详细的)

    • 数据类型:是指一组性质相同的值的集合以及定义在此集合上一些操作的总称(data+operation)
    • 数据类型 = 原子类型 + 结构类型
      – 原子类型,如 int,float,字符串, 是不可分割的基本类型
      – 结构类型, 数据结构+操作,可以分割
    • 抽象数据类型(ADT):一个数据模型以及定义在该模型上的一组操作

    一、列表 ADT

    1. 实现列表ADT的两种数据结构:数组(array-based)和链表(linked list)

    时间复杂度(效率)

    OperationArrayLinked list
    Insert×✔ O(n)
    Remove×✔ O(n)
    Find一样 O(n)一样 O(n)
    FindKth✔ O(1)× O(n)

    空间复杂度: Linked list需要记录所有node的地址,所以数组所需要的space更少

    linked list更适合实现链表的操作。因为数组的长度是不能改的。

    2. 链表的结构
    typedef struct node{
    	double data;
    	struct node* next;
    }Node;
    
    3. 操作

    bool IsEmpty(Node* head)

    • 判断head是否为null

    Node* InsertNode(Node** phead, int index, double x)

    • 在最前面insert:创建值为x的node,next指向head,head指向next
    • 在其他位置insert:找到index位置上的node,保存这个node的next,…

    int FindNode(Node* head, double x)

    • 返回x都一次出现的地方:遍历所有直到找到为止

    Int DeleteNode(Node** phead, double x)

    • 删除最前面的;删除中间或者后面的
    • 删除后释放空间(free)

    void DisplayList(Node* head)

    • 遍历完然后一个个print

    void DestroyList(Node* heas)

    • deletes all the nodes in the list
    • frees the memory allocated to the nodes

    二、栈 ADT

    是一种特殊的List ADT

    1. 插入和删除都在同一个地方(在top),First In Last Out
    2. 栈的应用
    • Expression evaluation (prefix,infix,postfix)
    • 回溯,返回上一级(搜索,查找路径等)
    • 内存管理(memory management)
    3. 实现栈ADT的两种数据结构:数组(array-based)和链表(linked list)
    OperationArrayLinked list
    PushO(1)O(1)
    PopO(1)O(1)
    TopO(1)O(1)

    更适合用数组来实现,因为数组是个物理结构,可以直接找到。或者用反向的链表,rear的指针指向最后一个node。

    4. 栈的结构
    typedef struct stack{
    	double* values;
    	int top;
    	int maxTop;
    }Stack;
    
    5. 操作

    假设 maxTop = size - 1

    Bool CreateStack(Stack *stack, int size)

    • 创建一个新的stack

    bool IsEmpty(Stack* stack);

    • Top为-1

    bool IsFull(stack* stack);

    • Top = maxTop

    bool Top(Stack* stack, double* x);

    • 返回stack.values[stack.top]

    bool Push(Stack* stack, double x);

    • 看看有没有满
    • 没满的话加到stack.values[stack.top+1]

    bool Pop(Stack* stack, double* x);

    • 看看空不空
    • 不空的话删除stack.values[stack.top],top -= 1

    void DisplayStack(Stack* stack);

    • 遍历stack中的values

    void DestroyStack(Stack* stack);

    • free values
    • free stack

    三、队列 ADT

    是一种特殊的List ADT

    1. 在最后面(rear)插入,在最前面(front)删除都在同一个地方(在top),First In First Out
    2. 队列的应用
    • 打印
    • 网页爬取
    • 系统缓冲区(system buffer)
    3. 队列的结构
    typedef struct queue{
    	double* values;
    	int front;
    	int rear;
    	int counter; // 队列里一共有几个元素
    }Stack;
    
    4. A circular array

    首尾相连的array,有一个固定的长度。

    5. 操作

    bool CreateQueue(Queue *queue, int size);

    • size,定义的数组长度

    bool IsEmpty(Queue* queue);

    • front和rear重合,counter == 0

    bool IsFull(Queue* queue);

    • front和rear重合,counter == maxSize

    bool Enqueue(Queue* queue, double x);

    • 看看队列满不满
    • 在rear插入,(rear的位置+1)% size

    bool Dequeue(Queue* queue, double* x);

    • 看看队列空不空
    • 在front删除,(front的位置+1)% size

    void DisplayQueue(Queue* queue);

    • 从头(front)开始遍历,到size再到1

    void DestroyQueue(Queue** pqueue);

    • free(values)
    • free(queue)

    四. 优先级队列(priority queue)

    1. 基本思想
    • enqueue:insert后进行堆排序(上小下大) O(logn)
    • dequeue:最前面是min O(logn)
    展开全文
  • 数据结构的基本概念及其要素

    千次阅读 2021-04-16 19:31:03
    一、数据结构的基本概念 (一)、数据 ...()、数据对象、数据结构 数据对象:是具有相同性质的数据元素的集合,是数据的一子集。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。 同一

    一、数据结构的基本概念

    在这里插入图片描述

    (一)、数据

    • 数据:数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

    (二)、数据元素、数据项

    • 数据元素:是数据的基本单位,通常作为一个整体进行考虑和处理。
    • 一个个数据元素可由若干个数据项组成,数据项是构成数据元素的不可分割的最小单位。

    (三)、数据对象、数据结构

    • 数据对象:是具有相同性质的数据元素的集合,是数据的一个子集。
    • 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
    • 同一个数据对象里的数据元素,可以组成不同的数据结构。
    • 不同的数据元素,可以组成相同的数据结构。

    二、数据结构的三要素

    在这里插入图片描述

    (一)、逻辑结构

    在这里插入图片描述

    (二)、数据的运算

    • 数据的运算:针对于某种逻辑结构,结合实际要求,定义基本运算。

    1. 逻辑结构:

    • 线性结构:
      ①、查找第i个数据元素。
      ②、在第i个位置插入新的数据元素。
      ③、删除第i个位置的数据元素

    (三)、物理结构(存储结构)

    在这里插入图片描述

    1. 顺序结构

    在这里插入图片描述

    2. 链式结构

    在这里插入图片描述

    3. 索引结构

    在这里插入图片描述

    4. 散列结构

    在这里插入图片描述

    1. 若采用顺序存储,则各个数据元素在物理上必须是连续的;若采用非顺序存储,则各个数据元素在物理上可以是离散的
    2. 数据的存储结构影响存储空间分配的方便程度
    3. 数据的存储结构影响对数据运算的速度
    • 运算的定义针对逻辑结构的,指出运算的功能;
    • 运算的实现针对存储结构的,指出运算的具体操作步骤。

    三、数据类型、抽象数据类型

    • 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
      ①、原子类型。其值不可再分的数据类型。
      ②、结构类型。其值可以再分解为若干成分(分量)的数据类型。

      在这里插入图片描述
    • 抽象数据类型(Abstract Data Type,ADT)是抽象数据组织及与之相关的操作。
      在这里插入图片描述
    展开全文
  • 数据结构要素4.1 逻辑结构4.1.1 集合4.1.2 线性结构4.1.2 树形结构4.1.4 图结构4.2 数据的物理结构(存储结构)4.2.1 顺序存储4.2.2 链式存储4.2.3 索引存储4.2.4 散列存储4.2.5 顺序存储总结4.3 数据的运算5....

    离线笔记下载:
    https://download.csdn.net/download/qq_38454176/12347554

    1. 知识框架

    在这里插入图片描述

    2. 什么是数据

    数据:
    数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
    数据(data)是事实或观察的结果,是对客观事物的逻辑归纳,是用于表示客观事物的未经加工的原始素材。
    数据可以是连续的值,比如声音、图像,称为模拟数据。也可以是离散的,如符号、文字,称为数字数据。
    在计算机系统中,数据以二进制信息单元0,1的形式表示。

    3. 数据结构基本概念

    3.1 数据元素、数据项

    数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成,数据项是构成数据元素的不可分割的最小单位
    在这里插入图片描述

    3.2 数据结构、数据对象

    结构——各个元素之间的关系
    数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
    数据对象是具有相同性质的数据元素的集合,是数据的一个子集。

    实例:
    数据结构:某个特定门店的排队顾客信息和它
    们之间的关系
    数据对象:全国所有门店的排队顾客信息
    在这里插入图片描述

    4.数据结构的三要素

    在这里插入图片描述

    4.1 逻辑结构

    4.1.1 集合

    集合:各个元素同属一个集合,别无其他关系
    在这里插入图片描述

    4.1.2 线性结构

    线性结构:数据元素之间是一对一的关系。除了第一个元素,所有元素都有唯一前驱;除了最后一个元素,所有元素都有唯一后继。
    在这里插入图片描述

    4.1.2 树形结构

    树形结构:数据元素之间是一对多的关系
    在这里插入图片描述

    4.1.4 图结构

    图结构:数据元素之间是多对多的关系

    在这里插入图片描述

    4.2 数据的物理结构(存储结构)

    4.2.1 顺序存储

    顺序存储: 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现

    在这里插入图片描述

    4.2.2 链式存储

    链式存储: 逻辑上相邻的元素在物理位置上可以不相邻,借助指示元素存储地址的指针来表示元素之间的逻辑关系。
    在这里插入图片描述

    4.2.3 索引存储

    索引存储:在存储元素信息的同时,还建立附加的索引表。索引表中的每项称为索引项,索引项的一般形式是(关键字:地址)

    在这里插入图片描述

    4.2.4 散列存储

    散列存储。根据元素的关键字直接计算出该元素的存储地址,又称哈希(Hash)存储。具体后面介绍

    4.2.5 顺序存储总结

    绪论部分只需要理解三点:

    1. 若采用顺序存储,则各个数据元素在物理上必须是连续的;若采用非顺序存储,则各个数据元素在物理上可以是离散的
    2. 数据的存储结构影响存储空间分配的方便程度
    3. 数据的存储结构影响对数据运算的速度

    4.3 数据的运算

    数据的运算——施加在数据上的运算包括运算的定义和实现。
    运算的定义针对逻辑结构的,指出运算的功能;运算的实现针对存储结构的,指出运算的具体操作步骤。

    逻辑结构——线性结构(队列)
    结合现实需求定义队列这种逻辑结构的运算:
    ①队头元素出队;
    ②新元素入队;
    ③输出队列长度

    5. 数据类型、抽象数据类型

    5.1.1 数据类型

    数据类型是一个值的集合和定义在此集合上的一组操作的总称。
    1)原子类型。其值不可再分的数据类型。
    如:

    • bool 类型:值的范围:true、false可进⾏操作:与、或、⾮…
    • int类型:值的范围:-2147483648 ~ 2147483647,可进⾏操作:加、减、乘、除、模运算…

    2)结构类型。其值可以再分解为若干成分(分量)的数据类型。
    如:

    struct Customer{
    int num; //号数:定义一个具体的结构类型,表示排队顾客信息。根据具体业务需求来确定值的范围,可进行的操作
    int people; //人数:值的范围:`num(1~9999)、people(1~12)`,可进行操作:如“拼桌”运算,把人数相加合并
    …… //其他必要的信息
    };
    

    5.2 抽象数据类型(Abstract Data Type,ADT)

    抽象数据类型(Abstract Data Type,ADT)是抽象数据组织及与之相关的操作;ADT 用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关

    6. 本节重点

    在这里插入图片描述

    • 数据结构这门课着重关注的是数据元素之间的关系,和对这些数据元素的操作,而不关心具体的数据项内容

    离线笔记下载:
    https://download.csdn.net/download/qq_38454176/12347554

    展开全文
  • 抽象数据类型(ADT)

    千次阅读 2017-09-12 21:10:48
    说到抽象数据类型,那么就得先提到数据类型数据类型指的是一值的集合以及定义在这集合上的一组操作为什么要有不同的数据类型呢 当我们计算1+1的时候,只需要很小的存储空间,但是当我们去计算10000+100000的时候...
  • 人们在使用计算机解决客观世界中存在的具体问题时,通常过程如下:首先通过对客观世界的认知形成印象和概念从而得到了信息,在此基础上... 数据结构主要与在上述过程中从建立概念模型到实现模型转化并为后续程序设...
  • 常见抽象数据类型

    千次阅读 2019-03-27 15:48:25
    一、栈 结构:栈顶、栈底 特点:后进先出。从栈顶压入栈,从栈顶压出栈 二、队列 1、队列 ...、树 1、二叉树 2、AVL树 3、伸展树 4、(2,4)树 5、红黑树 四、图 五、映射 1、哈希表 2、跳跃表 ...
  • 数据结构——数据结构大结构

    千次阅读 2019-09-02 22:53:14
    数据结构三个层次:逻辑结构(抽象层)、物理结构(结构层)、运算结构(实现层)。 1.1 数据结构的逻辑结构 逻辑结构指人对数据之间关系的理解和看法,逻辑结构和计算机无关。 逻辑结构: 1、 集合结构 ...
  • 数据结构与算法必知基础知识

    千次阅读 多人点赞 2021-01-06 22:58:12
    数据结构与算法是程序员内功体现的重要标准之一,且数据结构也应用在各个方面,业界更有程序=数据结构+算法这等式存在。各个中间件开发者,架构师他们都在努力的优化中间件、项目结构以及算法提高运行效率和降低...
  • 计算机组成原理 这门学科告诉你什么是计算机。 首先,我们可以把计算机分解成最原始的部件——晶体管。晶体管是一种半导体材料,其最重要的作用就是半导:可以通过电流的变化,实现电路的切换。比...
  • 2023考研王道计算机408数据结构+操作系统+计算机组成原理+计算机网络网盘链接: https://pan.baidu.com/s/1AuJdzuM9IO3yqhcDz4xBtg?pwd=asxt 提取码:asxt408不难,但是上130很难!六月,是408的季节~我觉得408跟...
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。
  • 从今天开始,我将正式开启一新的打卡专题——【数据结构·水滴计划】,没错!这是今年上半年的一整个系列计划!本专题目的是通过百天刷题计划,通过题目和知识点串联的方式,刷够1000道题!完成对数据结构相关知识...
  • 什么是抽象数据类型?

    千次阅读 2021-04-29 23:15:13
    什么是抽象数据类型?前言1.数据类型和数据构造2.抽象数据类型的概念3.抽象数据类型的描述 前言 抽象数据类型(Abstract Data Type,ADT)是计算机领域中被广泛接受的一种思想和方法,也是一种用于设计和实现程序...
  • 用计算机解决实际问题时,步骤:首先分析实际问题,从中抽象出一适当的数学模型,然后设计一解决此数学模型的算法,最后编程,调试,测试。 寻求数据模型的实质是分析问题,从中提取出计算机处理的对象,并找出...
  • 学算法先学数据结构?是否是无稽之谈?

    万次阅读 多人点赞 2022-03-02 08:30:55
    对应的文章如下: (第4讲) 组合数 (第30讲) 概率问题 7、零基础如何学习数据结构   学习数据结构之前,选择一款相对来说心仪的教程是必不可少的,我这里准备了一用动画来解释数据结构的教程,在我这也有,就是:...
  • 1.3数据抽象级别

    千次阅读 2018-01-18 13:55:10
    一、数据抽象的级别1、概念数据模型2、逻辑数据模型3、外部数据模型4、内部数据模型表达用户需求观点的数据全局逻辑结构的模型,称之为概念模型;表达计算机实现观点的DB全局逻辑结构的模型,称之为逻辑模型;表达...
  • 数据结构-链表篇

    千次阅读 2021-09-07 22:54:59
    数据结构-链表篇
  • 数据结构基础 1、数据结构的研究内容 2、基本概念和术语 3、算法和算法分析
  • 什么是数据结构

    千次阅读 2019-06-19 20:25:39
    什么是数据结构数据结构是什么? 数据结构是计算机存储、组织数据的方式...数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。也就是说,数组结构指的是数据集合及...
  • 分门别类介绍数据结构的基本概念,查漏补缺必看文章。
  • 数据结构抽象数据类型(ADT)简介

    千次阅读 2010-10-28 20:39:00
    1. 数据(Data) 数据是信息的载体。它能够被计算机识别、存储和加工处理,是计算机程序加工的"原料"。 随着计算机应用领域的扩大,数据的范畴包括:整数、实数、字符串、图像和声音... 数据结构(Da
  • 其实树结构是平日里我们常见的一种数据结构,例如家族族谱、公司管理层级结构图等,这样的数据结构的存在一定有一定的道理。因此,在计算机领域中,树结构也是会被广泛用到的,例如数据库系统中就有用到。那么本文就...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • 云南专升本-数据结构知识总结和常考例题(一)

    千次阅读 多人点赞 2021-11-15 16:08:34
    文章目录数据结构一、数据结构的基本概念抽象数据类型算法二、线性表顺序表链表、栈和队列栈(stack)队列(Queue) 一、数据结构的基本概念 数据是对客观事物的符号表示。 数据元素是数据的 基本 单位。 数据...
  • 数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为计算机专业的专业基础课程,是计算机考研的必考科目之一,如果打算报考计算机专业的研究生,你...
  • 数据结构知识点总结

    万次阅读 多人点赞 2020-05-09 09:23:23
    一,数据结构的一般概念 数据:所有能被输入到计算机并被处理的符号的集合 数据元素:数据的基本单位 数据项:构成数据的不可分割的最小单位,一数据元素有若干数据项组成。 ......
  • 数据结构复习题(绪论)

    千次阅读 多人点赞 2021-05-31 23:24:41
    选择题数据结构复习(复习题)绪论二级目录级目录 绪论 线性结构中数据元素的位置之间存在( )的关系 A.一对多 B.一对一 C.多对多 D.每一元素都有一直接前驱和一直接后继 数据结构中,与所使用的计算机...
  • 数据结构与算法—前导

    千次阅读 2019-07-25 23:53:34
    数据结构与算法是程序员内功体现的重要标准之一,而数据结构的也应用在各个方面,更有程序=数据结构+算法这被人认证的等式存在。并且数据结构与算法的应用无处不在,各个中间件开发者,架构师。他们都在努力的优化...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 197,937
精华内容 79,174
关键字:

抽象数据结构三个组成部分

数据结构 订阅