下载文档原格式
《数据结构教程》第一章绪论数据结构教程第一章绪论数据结构是计算机科学中的重要概念之一，它是计算机程序设计的基础。
本教程的第一章将介绍数据结构的基本概念和作用。
一、什么是数据结构？在计算机科学中，数据结构用于存储和组织数据，以便在计算机程序中进行高效的操作。
数据结构可以分为两种基本类型：线性数据结构和非线性数据结构。
1.1 线性数据结构线性数据结构是最简单的数据结构之一，它将数据元素按照线性顺序组织，可以使用一对一的关系连接数据元素。
常见的线性数据结构有数组、链表和栈。
1.2 非线性数据结构非线性数据结构是指数据元素之间存在多对多的关系，不是简单的一对一关系。
常见的非线性数据结构有树和图。
二、数据结构的作用数据结构的设计和选择对于程序的效率和性能具有重要影响。
合理选择数据结构可以提高算法的执行速度，降低计算机资源的占用。
2.1 提高数据的存储效率通过选择适当的数据结构可以减少内存的占用，提高数据的存储效率。
例如，链表数据结构可以动态地分配内存空间，减少内存的浪费。
2.2 提高数据的访问效率不同的数据结构在数据的访问效率上有所差异。
例如，对于需要频繁插入和删除操作的场景，链表数据结构比数组数据结构更加高效。
2.3 优化算法的执行速度数据结构和算法是相辅相成的，通过选择合适的数据结构可以优化算法的执行速度。
例如，在查找操作中使用二叉搜索树可以降低时间复杂度。
三、数据结构的分类根据数据结构的存储方式和操作特性，可以将数据结构分为线性数据结构和非线性数据结构。
3.1 线性数据结构线性数据结构是最常用的数据结构之一，它将数据元素按照线性顺序排列，每个元素有一个直接前驱和直接后继。
常见的线性数据结构有数组、链表和栈。
3.1.1 数组数组是一种最简单的数据结构，它将数据元素存储在连续的内存空间中。
数组的访问速度很快，但是插入和删除操作的效率较低。
3.1.2 链表链表是一种动态数据结构，它通过指针将数据元素链接在一起。
第1章绪论1.1 什么是数据结构数据与数据之间的关系1.2 基本概念和术语1.基本定义(1).数据(Data) ：是客观事物的符号表示。
在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
(2)数据项(Data Item)：一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。
2.举例如字符集合C={‘A’,‘B’,‘C’,…}--C表示字符对象；A ，B等表示数据元素；再如学生集合Students={“Zhangsan”, “Lisi”，…}Zhangsan(ID,name,age,grade,…)……--Students表示学生对象；“Zhangsan”、“Lisi”表示数据元素；Zhangsan的ID、name、age等表示数据项。
3.数据结构的形式定义数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集4.逻辑结构与物理结构(1)数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
(2)数据结构在计算机中的表示（映像）称为数据的物理结构。
数据结构的存储方式1)顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
2)链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。
3)例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的存储结构。
数据结构知识整理（部分）第一章：绪论1．数据：数据是外部信息的载体，他能够被计算机识别、存储和加工处理，是计算机程序加工的原料；2．数据元素：数据元素是数据的基本单位，在计算机中通常被作为一个整体进行考虑和处理；3．一个数据元素可由若干个数据项组成。
数据项是不可分割的、含有独立意义的最小数据单位，数据项有时也称为字段或域；4．数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。
在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关系称为结构；5．4种基本数据结构：集合：只有“同属一个集合”的关系；线性结构：存在着一对一的关系；树形结构：存在着一对多的关系；图状结构：存在着多对多的关系；6．数据结构包括数据的逻辑结构和物理结构。
逻辑结构：从具体问题抽象出来的数学模型，与数据在计算机中的具体储存没有关系。
从逻辑上可以把数据结构分为线性结构和非线性结构，其中集合、树、图形结构属于非线性结构；7．数据的物理结构又叫存储结构，是数据在计算机中的表示和存储，包括数据元素的表示和存储以及数据元素之间关系的表示和存储，存储结构必须依赖于计算机。
数据元素之间的关系在计算机中的表示有两种:顺序映像和非顺序映像。
分别对应两和数据的存储结构：顺序存储结构和链式存储结构；顺序存储结构是指把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中；链式存储结构不要求必须相邻。
链式存储结构中的数据元素叫做结点，在结点中附近设地址域来存储与该结点相邻的结点的地址来实现结点之间逻辑关系；8．在软件设计中，抽象数据类型通常包括定义、表示和实现三部分9．算法：是指在有限的时间范围之内为解决某一问题而采取的方法和步骤的准确完整的描述，他是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算；10算法的特征：有穷性，确定性，可行性，输入，输出；算法+数据结构=程序；11．评价一个算法的主要标准：正确性，可读性，健壮性，运行时间，占用空间；健壮性要求算法要全面细致的考虑所有可能出现的边界情况和异常情况；实际上，算法的时间效率和空间效率经常是一对矛盾，相互抵触，我们要根据实际问题进行处理，有时要牺牲空间换取时间，有时要牺牲时间换取空间。
