C语言的数据结构和编程

全部展开

数据结构

数据结构是计算机存储和组织数据的方式. 数据结构是指相互具有一个或多个特定关系的数据元素的集合. 在正常情况下，精心选择的数据结构可以带来更高的操作或存储效率. 数据结构通常与有效的检索算法和索引技术有关. 在计算机科学界，没有标准的数据结构定义. 个体根据各自的理解有不同的表达方法: Sartaj Sahni在他的《数据结构，算法和应用程序》一书中指出: “数据结构是数据对象，以及对象中存在的实例和构成实例数据之间的各种连接这些连接可以通过定义相关功能来给出. “他定义数据对象为”数据对象是实例或值的集合. ” Clifford A. Shaffer在“数据结构和算法分析”中的定义是: “数据结构是ADT（抽象数据类型）的物理实现. ” Lobert L. Kruse在“数据结构和编程”一书中，数据结构的设计过程分为抽象层，数据结构层和实现层. 其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构和操作，而数据结构层和实现层则讨论数据结构的表示形式以及计算机和存储中的存储细节. 实施操作.

重要

通常认为，数据结构是根据某些逻辑连接由数据元素组成的. 数据元素之间的逻辑关系的描述称为数据的逻辑结构. 数据必须存储在计算机中，数据的存储结构是数据结构及其在计算机中的表示形式. 此外，必须同时讨论数据结构. 对此类数据执行的操作是有意义的. 在设计许多类型的程序时，数据结构的选择是基本的设计考虑因素. 许多大型系统的构建经验表明，系统实现的难度和系统构建的质量在很大程度上取决于是否选择了最佳数据结构. 在许多情况下，确定数据结构后，即可轻松获得算法. 有时情况会逆转，我们会根据特定算法选择要适应的数据结构. 无论哪种情况，选择正确的数据结构都是非常重要的. 选择数据结构后，将相应地确定算法，系统构建的关键因素是数据而不是算法. 这种见解导致了许多软件设计方法和编程语言的出现. 面向对象的编程语言就是其中一种.

研究内容在计算机科学中，数据结构是一门学科，它研究计算机的操作对象（数据元素）及其在非数值计算的编程问题中的关系和操作，并确保在进行这些操作后，产生的新结构是仍然是原始结构类型.

“数据结构”于1968年作为一门独立课程在国外建立. 1968年，美国的Don O. Knut教授率先提出了数据结构的初始系统. 他的第一卷“计算机编程技巧”“基本算法”是第一个系统地解释数据的逻辑结构和存储结构及其操作的书. “数据结构”是计算机科学领域的综合性基础课程. 数据结构是数学，计算机硬件和计算机软件之间的核心课程. 此数据结构课程的内容不仅是通用编程（尤其是非数字编程）的基础，而且是设计和实现编译器，操作系统，系统和其他系统程序的重要基础.

计算机是一门研究计算机的信息表示和处理的科学. 这里涉及两个问题: 信息的表示和信息的处理.

信息的表示和组织与处理信息的过程的效率直接相关. 随着计算机的普及，信息量的增加和信息范围的扩大，许多系统程序和应用程序都具有和复杂的结构. 因此，为了编写“好的”程序，必须分析要处理的对象的特性以及对象之间的关系. 这是数据结构过程中要研究的问题. 众所周知，计算机程序处理信息. 在大多数情况下，此信息不是没有组织的数据结构与程序设计 c语言描述，并且信息（数据）通常具有重要的结构关系，这是数据结构的内容. 数据的结构直接影响算法的选择和效率. 当计算机解决特定问题时数据结构与程序设计 c语言描述，通常需要执行以下步骤: 首先，必须从特定问题中抽象出适当的数学模型，然后设计用于解决该数学模型的算法（算法），最后是程序进行编译，测试，调整，直到获得最终答案. 寻找数学模型的实质是分析问题，从中提取操作对象，找出这些操作对象中包含的关系，然后用数学语言对其进行描述. 计算机算法与数据结构密切相关. 算法都取决于特定的数据结构. 数据结构直接关系到算法的选择和效率. 该计算由计算机完成，这需要设计相应的插入，删除和修改算法. 换句话说，数据结构还需要为每种结构类型定义的各种操作提供算法. 数据是客观事物的象征性表示. 在计算机科学中，它是指可以输入到计算机并由计算机程序处理的所有符号.

数据元素是数据的基本单位，通常在计算机程序中被视为一个整体. 数据元素由几个数据项组成. 数据项是不可分割的最小数据单位. 数据元素有两种类型: 一种是不可分割的原子数据元素，例如: 整数“ 5”，字符“ N”等. 另一个是由多个付款组成的数据元素，其中每个付款称为一个数据项. 例如，描述的数据元素可以由以下6个数据项组成. 出生日期可以由“年”，“月”和“日”这三个数据项组成，则“出生日期”称为组合项，其他不可分割的数据项是原子项.

关键字是指可以标识一个或多个数据元素的数据项. 如果可以发挥独特作用，则称为“主要”关键字，否则称为“辅助”关键字.

数据对象是性质相同的数据元素的集合，并且是数据的子集. 数据对象可以是受限制的或不受限制的.

数据处理是指对数据进行搜索，插入，删除，合并，排序，统计和简单计算的过程. 在早期，计算机主要用于科学和工程计算. 1980年代后，计算机主要用于数据处理. 根据有关统计，现在用于数据处理的计算机时间比例已超过80％. 随着时间的流逝以及计算机应用程序的进一步普及，用于数据处理的计算机时间所占的比例将进一步增加.

分类

数据结构是指同一数据元素类中数据元素之间的关系. 数据结构是逻辑结构，存储结构（物理结构）和数据操作. 数据的逻辑结构是对数据之间关系的描述，有时逻辑结构简称为数据结构. 逻辑结构正式定义为（K，R）（或（D，S）），其中K是数据元素的有限集合，R是K上的关系的有限集合.

数据元素之间的关系称为结构. 有四种基本结构: 集合，线性结构，树形结构和图形结构（网格结构）. 树结构和图结构都称为非线性结构. 集合结构中的数据元素没有其他关系，只是它们属于同一类型. 线性结构中的元素之间存在的关系，树形结构中的元素之间存在一对多的关系，而图结构中的元素之间存在多对多的关系. 图结构中每个节点的前节点和后节点的数量可以为任意数量.

计算机中数据结构的表示形式（图像）称为数据的物理（存储）结构. 它包括数据元素的表示形式和关系的表示形式. 有两种不同的表达数据元素之间关系的方式: 顺序映射和非顺序映射，并从中获得两种不同的存储结构: 顺序存储结构和链式存储结构. 顺序存储方法: 将逻辑上相邻的节点存储在物理位置上彼此相邻的存储单元中. 节点之间的逻辑关系由存储单元的邻接关系反映. 结构体. 顺序存储结构是一种基本的存储表示方法，通常通过编程语言中的数组来实现. 链接存储方法: 不需要逻辑上相邻的节点在物理位置上相邻. 节点之间的逻辑关系由一个附加的指针字段表示. 所得的存储表示形式称为链式存储结构，通常通过编程语言中的指针类型来实现. 索引存储方法: 除了建立存储节点信息之外，还建立了一个附加的索引表来标识节点地址. 散列存储方法: 根据节点的关键字直接计算节点的存储地址.

在数据结构中，逻辑上（逻辑结构: 数据元素之间的逻辑关系）可以将数据结构分为线性结构和非线性结构. 线性结构的顺序存储结构是随机访问存储结构，线性表的链式存储结构是顺序访问存储结构. 如果线性表由链式存储表示，则所有节点之间的存储单元地址可以是连续的或不连续的. 逻辑结构与数据元素本身包含的形式，内容，相对位置和节点数无关.

数据结构和算法

算法的设计取决于数据（逻辑）结构，算法的实现取决于所使用的存储结构. 数据的存储结构实质上是其在计算机内存中的逻辑结构的实现. 为了充分反映数据的逻辑结构，他在存储器中的图像包括两个方面，以及数据元素之间的信息和关系. 不同的数据结构具有其相应的操作. 数据操作是在数据的逻辑结构上定义的操作算法，例如检索，插入，删除和更新排序.

数据的操作是数据结构的重要方面. 任何有关数据结构的讨论都离不开关于数据结构及其实现算法的讨论.

数据结构的形式定义为: 数据结构是一个二进制组:

数据结构=（D，S）

其中: D是数据元素的有限集合，S是D上关系的有限集合.

数据结构不同于数据类型和数据对象. 它不仅描述了数据类型的数据对象，而且还描​​述了数据对象的元素之间的关系.

数据类型是值的集合以及在此值集上定义的一组操作. 数据类型可以分为两类: 原子类型和结构类型. 一方面，在编程语言中，每个数据都属于某种数据类型. 该类型明确或隐含地规定了数据值范围，存储方法和允许的操作. 可以认为数据类型是在程序设计中已经实现的数据结构. 另一方面，在程序设计过程中，当需要引入新的数据结构时，总是借助编程语言提供的数据类型来描述数据的存储结构.

计算机中最小的数据单位是二进制数的一位，称为bit. 我们使用由多个位组合而成的位串来表示数据元素，通常将该位串称为元素或节点. 当数据元素由几个数据项组成时，对应于每个数据项的位串中的子位串称为数据字段. 元素或节点可以视为计算机中数据元素的映像. 一个软件系统框架应该建立在数据之上，而不是建立在操作之上. 具有抽象数据类型的软件模块应包含三个部分: 定义，表示形式和实现. 对于每个数据结构，必须有一组与其紧密相关的操作. 如果操作的类型和次数不同，则即使逻辑结构相同，数据结构也可以发挥不同的作用.

不同的数据结构具有不同的操作集，但是以下操作是必不可少的: 1.结构的生成； 2.破坏结构； 3.搜索满足结构中指定条件的数据元素； 4.在结构中插入新数据元素； 5，删除结构中现有的数据元素； 6，遍历.

抽象数据类型: 数学模型和在模型上定义的一组操作. 抽象数据类型实际上是数据结构的定义. 因为它定义了数据的逻辑结构，并且在此结构上定义了一组算法. 抽象数据类型可以由以下三元组表示: （D，S，P）. D是数据对象，S是在D上设置的关系，P是在D上设置的基本操作. ADT的定义是: ADT抽象数据类型名称{数据对象: （数据元素集合）数据关系: （数据关系二元组）基本操作: （操作函数列表）} ADT抽象数据类型名称；

抽象数据类型具有两个重要特征: 数据抽象

在描述由ADT程序处理的实体时，重点是实体的基本特征，可执行的功能以及与外部用户的接口（即外界如何使用它）. 数据封装将实体的外部特征与其内部实现细节分开，并向外部用户隐藏其内部实现细节.

数据是信息的载体，可以由计算机识别，存储和处理. 它是计算机程序处理的原材料，而应用程序则处理各种数据. 在计算机科学中，所谓的数据是计算机处理的对象. 它可以是数字数据或非数字数据. 数值数据是整数，实数或复数，主要用于工程计算，科学计算和业务处理. 非数字数据包括字符，文本，图形，图像和语音. 数据元素（Data Element）是数据的基本单位. 在不同条件下，数据元素也可以称为元素，节点，顶点，记录等. 例如，检索系统中表中的记录称为数据元素.

有时，数据元素可以由几个数据项（Data Item）组成，例如，学生状态管理系统中表的每个数据元素都是学生记录. 它包括学生的学生ID，姓名，性别，出生地，出生日期，成绩和其他数据项. 这些数据项可以分为两种类型: 一种称为基本项，例如学生的性别，出生地等. 这些数据项是在数据处理过程中无法再划分的最小单位；另一个被称为综合项目，例如学生成绩. 它可以进一步分为较小的项目，例如数学，物理和化学. 通常，在解决实际应用问题时，每个学生记录都作为基本单元进行访问和处理.

数据对象（数据对象）或数据元素类（数据元素类）是具有相同性质的数据元素的集合. 在一个特定的问题中，所有数据元素都具有相同的属性（元素值不一定相等）并且属于同一数据对象（数据元素类）. 数据元素是数据元素类的实例. 例如，在运输咨询系统的运输网络中，所有顶点都是数据元素类，并且顶点A和B分别代表一个城市，并且是数据元素类中的两个实例，并且数据元素值都是A B.数据结构是指彼此具有一个或多个关系的数据元素的集合. 不管有什么问题，数据元素之间都不会隔离，它们之间存在一个或另一个关系. 这些数据元素之间的关系称为结构. 根据数据元素之间关系的不同特征，通常有以下四个基本结构:

⑴集合结构. 这种结构的数据元素之间的关系是“属于同一集合”.

⑵线性结构. 这种结构的数据元素之间存在的关系.

⑶树形结构. 这种结构的数据元素之间存在一对多的关系.

⑷图形结构. 这种结构的数据元素之间也存在多对多关系，也称为网格结构. 从上面介绍的数据结构的概念可以知道，数据结构具有两个元素. 一个是数据元素的集合，另一个是关系的集合. 形式上，数据结构通常可以用两个元组表示.

数据结构的形式定义为: 数据结构是一个二进制组

Data_Structure =（D，R）

其中D是数据元素的有限集合，R是D上的关系的有限集合. 线性结构的特征是，数据元素之间存性关系，并且数据元素“按以下顺序排列”一”. 线性表中数据元素的类型相同，或者线性表是由相同类型的数据元素组成的线性结构. 实际问题中有许多线性表的示例. 例如，表是线性​​表: 表中数据元素的类型是学生类型；字符串也是线性表: 表中数据元素的类型是字符类型等等.

线性表是最简单，最基本，最常用的线性结构. 线性表是具有相同数据类型的n（n> = 0）个数据元素的有限阶数

列，通常写为:

（a1，a2，... ai-1，ai，ai + 1，... an）

其中n是表的长度，n = 0称为空表. 它有两种存储方法: 顺序存储和链式存储. 它的主要基本操作是插入，删除和检索.

常用数据结构数组（Array）在程序设计中，为了简化处理，将具有相同类型的几个变量按顺序组织起来. 这些顺序排列的相似数据元素的集合称为数组. 在C语言中，数组是构造的数据类型. 一个数组可以分解为多个数组元素. 这些数组元素可以是基本数据类型或构造类型. 因此，根据数组元素的不同类型，可以将数组分为数字数组，字符数组，指针数组，结构数组等各种类别.

堆栈是一种特殊的线性表，只能在一端插入和删除. 它按照后进先出的原则存储数据. 第一个输入的数据被压入堆栈的底部. 最后的数据在堆栈的顶部. 当需要读取数据时，将从堆栈顶部弹出数据（首先读取最后一个数据）.

队列（队列）一种特殊的线性表，仅允许在表的前面进行删除操作，并在表的后面进行插入. 执行插入操作的末端称为队列的尾部，执行删除操作的末端称为队列的首部. 当队列中没有元素时，称为空队列.

链表（链表）是物理存储单元上的非连续，非顺序的存储结构. 数据元素的逻辑顺序由链接列表中的指针链接顺序实现. 链表由一系列节点（链表中的每个元素称为节点）组成，可以在运行时动态生成. 每个节点包括两部分: 一个是存储数据元素的数据字段，另一个是存储下一个节点地址的指针字段.

树（树）是包含n（n> 0）个节点的有限集K，并且在K中定义了一个关系N，N满足以下条件: （1）只有一个节点k0，他没有前驱体到关系N，并将K0称为树的根节点. 称为根（root）. （2）除K0以外，k中的每个节点对于关系N的e79fa5e98193e78988e69d8331333262363035具有一个且只有一个前体.

（3）K中的每个节点都可以有m个后继关系N（m> = 0）.

图（图）图由节点的有限集合V和边的集合E组成. 其中，为了将其与树结构区分开，在图结构中，节点通常称为顶点，而边是顶点的有序对. 如果两个顶点之间有一条边，则表示两个顶点是相邻关系.

堆（Heap）在计算机科学中，堆是一种特殊的树形数据结构，每个节点都有一个值. 通常，堆的数据结构是二进制堆. 堆的特征是根节点的值最小（或最大），并且根节点的两个子树也是堆.

哈希表（哈希）如果结构中有键等于K的记录，则该记录必须位于f（K）的存储位置. 结果，无需比较就可以直接获得搜索到的记录. 将该函数称为哈希函数，根据此思想创建的表就是哈希表.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-185679-1.html