数据结构中的逻辑结构以及物理结构

数据结构中的名词解释

数据结构中的名词解释

数据结构：数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

数据：数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图象等，都称为数据。 结点：结点也叫数据元素，它是组成数据的基本单位。

逻辑结构：结点和结点之间的逻辑关系称为数据的逻辑结构。

存储结构：数据在计算机中的存储表示称为数据的存储结构。

数据处理：数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。

数据类型：数据类型是指程序设计语言中各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。本章主要介绍了如下一些基本概念：

线性表：一个线性表是n≥0个数据元素a0，a1，a2，…，an-1的有限序列。线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。

线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元——结点（可以是不连续的`）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。

循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结 循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。

- 1 - 逻辑结构与物理结构的关系

逻辑结构与物理结构的关系

逻辑结构和物理结构都是软件开发的基本概念，在软件工程中都有着重要的作用，它们之间有着相互的关系。

首先，逻辑结构是指应用程序中的逻辑组织形式。它代表了为实现和完成目标而采用的不同方法及其实现的运行时流程。逻辑结构的基本元素包括：算法、数据结构、控制结构、模块等。

而物理结构指的是应用程序对计算机硬件所采取的实际的组织形式，也就是把应用程序以某种形式分割成不同的文件存放在计算机硬件上，如存放在磁盘或磁带等存储设备中。这些文件包括源程序文件、头文件、程序文件、库文件、可执行文件等。

因此，可以说，物理结构是逻辑结构的一种实现形式，它实现了逻辑结构，给出了逻辑结构的具体实现方式。反之亦然，逻辑结构正是物理结构的抽象表示，它把物理结构的复杂细节抽象化，变为一种更容易理解的形式。

因此，可以说，物理结构和逻辑结构之间是相互依赖且相互影响的关系，二者是软件工程中不可分割的部分。在软件工程中，需要在物理结构与逻辑结构之间建立联系，以更好地实现软件的功能。

逻辑结构与物理结构的区别和联系

逻辑结构与物理结构是数据结构中的两个基本概念，它们描述了数据元素之间的不同组织和存储方式。

一、逻辑结构

逻辑结构是指数据元素之间的逻辑关系和操作方式。在逻辑结构中，数据元素被视为不可分割的整体，它们之间的关系是通过元素之间的语义关系来描述的。逻辑结构通常分为以下几种类型：

1. 线性结构：数据元素按照一对一的关系进行排列，每个元素有且只有一个前驱和一个后继。线性结构通常用数组或链表来实现。

2. 树形结构：数据元素之间存在一对多的关系，每个元素可以有多于一个的子元素。树形结构通常用于表示层次关系，如文件系统、XML文档等。

3. 图形结构：数据元素之间存在多对多的关系，每个元素可以与多个元素相关联。图形结构通常用于表示网络、社交关系等。

在逻辑结构中，操作通常是对整个元素进行的，如读取、修改、删除等。逻辑结构的主要目的是为了方便程序员理解和操作数据元素之间的关系。

二、物理结构 物理结构是指数据元素在计算机内存中的存储方式。在物理结构中，数据元素被视为可独立存储的数据项，它们之间的关系是通过指针或链接来描述的。物理结构通常分为以下几种类型：

1. 顺序存储结构：数据元素按照逻辑顺序依次存储在一片连续的物理空间中，每个元素占用固定大小的空间。顺序存储结构通常用数组来实现。

2. 链式存储结构：数据元素之间通过指针相互链接，每个元素包含数据域和指针域。链式存储结构可以实现动态存储和修改，但需要额外的空间来存储指针。

3. 索引存储结构：数据元素按照一定的顺序存储在一片连续的物理空间中，同时建立一个索引表来指示每个元素的位置。索引存储结构可以提高查找效率，但需要额外的空间来存储索引表。

4. 散列存储结构：数据元素按照一定的散列函数映射到一块连续的物理空间中，每个元素占用固定大小的空间。散列存储结构可以实现快速查找和插入，但需要解决冲突问题。

在物理结构中，操作通常是对单个元素进行的，如读取、修改、删除等。物理结构的主要目的是为了提高计算机内存的使用效率和方便程序员进行数据的存储和访问。

数据结构

第一章

1、 数据是描述客观事物的数和字符的集合

2、 数据项：是具有独立含义的数据最小单位，也称为字段或域

3、 数据对象：指性质相同的数据元数的集合，是数据的一个子集

4、 数据结构：指所有数据元素以及数据元素之间的关系

5、 数据的逻辑结构：由数据元素之间的逻辑关系构成

6、 数据的存储结构：数据元素及其关系在计算机存储器中的存储表示，称为物理结构

逻辑结构的表达方式：

1、 图表表示：采用表格或图形直接描述数据的逻辑关系。

2、 二元组表示：通用的数据逻辑结构表示方式：R={r},r={<010,021>,<021,027>,<027,029>}

逻辑结构的类型：

1、 集合：指数据元素之间除了“同属于一个集合”的关系以外别无其他关系。 2、 线性结构：一对一关系，只有一个前驱和一个后继元素。

3、 树形结构：多对多关系，除了开始元素以外，都只有一个前驱和多个后继元素。

什么是算法：是问题求解步骤的描述，是指令的有限序列。

1、 有穷性：执行有穷步后结束

2、 确定性：不能有二义性

3、 可行性：算法可以通过有限次的操作完成其功能，能够被重复地执行

4、 有输入：一个算法有0个或多个输入

5、 有输出：一个算法有一个或多个输出

算法设计的目标：正确性(算法能正确执行)、可使用性(方便地使用)、可读性(算法易于理解)、健壮性(有好的容错性，不会异常中断或死机)、高效率与低存储量需求(算法的执行时间和存储空间)

算法时间性分析方法：事后统计法(缺点:必须执行、存在很多因素掩盖算法本质)、事前估算法(仅考虑算法本身的效率高低、只依赖于问题的规模)

第二章 线性表：具有相同特性的数据元素的一个有限序列

有序表：指线性表中的所有元素按递增或剃减方式有序排列

顺序表：线性表的顺序存储结构简称为顺序表(下标从0开始)，从逻辑上相邻的元素对应的物理存储位置也相邻，当进行插入或删除的操作时要平均移动半个表的元素，相当费时。