下载文档原格式
数据结构基本概念和术语1. 嘿，你知道数据结构不？这可是个超酷的东西呢！就像盖房子得有个好的框架一样，数据结构就是数据在计算机里存放和组织的框架。
比如说，你有一堆玩具，你可以把它们随便扔在盒子里，这就好比是没有规划的数据存放，找起来可费劲了。
可要是你按照大小或者类型把玩具分类放在不同的小格子里，这就像是一种简单的数据结构，找起来就容易多了。
2. 数据结构里有个概念叫数组，这就像是一列小火车，每个车厢都能装东西，而且车厢是按顺序编号的。
我跟我朋友讲这个的时候，他还不信呢。
我就说，你看，假如你要存你们班同学的成绩，用数组就很方便，第1个车厢放第1个同学的成绩，第2个车厢放第2个同学的成绩，以此类推。
这多整齐啊，就像士兵排着队一样。
3. 链表这个数据结构可有点意思了。
想象一下，你和你的小伙伴们手拉手连成一串，这就是链表啦。
每个小伙伴就像链表中的一个节点。
我之前给我弟弟解释这个，他一脸懵。
我就说，你看你那些小卡片，如果在每张卡片上写个数字，然后把卡片按顺序用绳子串起来，这就类似链表了。
想要找其中一张卡片，就得顺着绳子一个一个找过去。
4. 栈这个概念，你可以把它想象成一个弹夹。
先进去的子弹最后才能打出来，这就是栈的特性，后进先出。
我在和同学讨论这个的时候，他说这很奇怪啊。
我就跟他说，你看食堂里叠放的餐盘，最后放上去的餐盘是不是最先被拿走啊，这就和栈是一个道理，是不是很神奇呢？5. 队列又不一样喽。
它就像排队买冰淇淋的队伍，先来的人先买到，先入先出。
我跟我表弟说这个的时候，他说这很简单嘛。
我就说，对啊，就像你们学校排队做早操，第一个站好的同学第一个出去，这就是队列在生活中的体现呀。
6. 树这个数据结构可复杂又有趣啦。
它就像一棵大树，有树干，有树枝，还有树叶。
根节点就是树干，树枝就是子节点。
我和我同事解释的时候，他觉得很难理解。
我就说，你看你们家的族谱，最上面的老祖宗就是根节点，下面的子孙后代就是各个子节点，一层一层的，这就是树结构呀。
什么是数据结构数据结构是计算机科学中的基础概念之一，它是指组织和存储数据的方式，以及数据之间的关系和操作。
在计算机程序设计中，数据结构是指特定数据的组织形式，这些数据可以是数字、字符、实体对象等。
数据结构的选择对于程序的效率和功能具有重要影响。
一、数据结构的基本概念数据结构主要包括以下几个基本概念：1. 数据元素：数据元素是构成数据的最小单位，可以是单个的基本数据类型，也可以是多个基本数据类型组合而成的复合数据类型。
2. 数据项：数据元素中的一个个数据项是可以进行操作的最小单位，也可以理解为一个字段或属性。
3. 数据对象：数据对象是指具有相同性质的数据元素的集合，是数据集合的抽象。
4. 数据结构：数据结构是指数据元素之间的关系以及支持的操作，可以是线性的、非线性的、顺序的、层次的等不同的组织方式。
5. 数据类型：数据类型是一种特定的数据结构，用于描述数据的存储格式和支持的操作。
常见的数据类型包括整型、浮点型、字符型等。
6. 数据存储：数据存储是指数据在计算机中的具体储存形式，可以是内存中的数组、链表，也可以是硬盘中的文件等。
二、常见的数据结构1. 数组：数组是把具有相同类型的数据元素按照一定顺序排列并以连续的内存空间表示的数据结构，通过下标可以快速定位元素。
2. 链表：链表是由若干个结点组成，每个结点包含数据元素和指向下一个结点的指针，它的特点是空间不连续，插入、删除操作较灵活。
3. 栈：栈是一种先进后出的数据结构，只允许在栈顶进行插入和删除操作，类似于弹夹。
4. 队列：队列是一种先进先出的数据结构，只允许在队尾插入元素，在队头删除元素，类似于排队。
5. 树：树是由若干个结点组成的层次结构，每个结点可以有多个子结点，用于表示具有层次关系的数据。
6. 图：图是由若干个结点和边组成，结点表示数据元素，边表示结点之间的关系，用于表示具有复杂关系的数据。
三、数据结构的应用数据结构在计算机领域有广泛的应用，常见的应用包括：1. 数据库管理系统：数据库中的数据需要通过适当的数据结构进行组织和管理，如B+树、散列表等。
数据结构简介了解数据结构的基本概念和分类数据结构简介：了解数据结构的基本概念和分类在计算机科学中，数据结构是指数据元素之间的关系，以及在计算机中存储、组织和操作数据的方法。
数据结构的选择直接影响到算法的实现效率，因此深入了解数据结构的基本概念和分类是非常重要的。
一、数据结构的基本概念数据结构中的基本概念包括以下几个方面：1. 数据元素：数据结构中的基本单位，是数据的最小单位。
2. 关系：数据元素之间的相互关联，包括线性关系、树形关系、图形关系等。
3. 空间和时间的效率：衡量数据结构优劣的重要指标，包括内存空间的利用率和运行时间的复杂度。
4. 操作：对数据结构进行的操作，包括插入、删除、修改、查询等。
5. 抽象数据类型（Abstract Data Type, ADT）：将数据类型与操作定义在一起形成的数据抽象模型，是一种逻辑结构。
二、数据结构的分类根据数据元素之间的关系，数据结构可以分为以下几种类型：1. 线性结构：数据元素之间存在一对一的关系，包括线性表、栈、队列等。
- 线性表：是最基本的数据结构之一，包括顺序表和链表两种形式。
- 栈：一种特殊的线性表，具有“先进后出”（Last In First Out, LIFO）的特点。
- 队列：一种特殊的线性表，具有“先进先出”（First In First Out, FIFO）的特点。
2. 树形结构：数据元素之间存在一对多的关系，包括二叉树、堆、哈夫曼树等。
- 二叉树：每个节点最多只有两个子节点，分为二叉搜索树、平衡二叉树等。
- 堆：一种特殊的二叉树，常用于实现优先队列。
- 哈夫曼树：一种用于数据压缩的树形结构，通过编码来减少数据存储空间。
3. 图形结构：数据元素之间存在多对多的关系，包括有向图、无向图等。
- 有向图：图中的边具有方向性，表示元素之间的有序关系。
- 无向图：图中的边没有方向性，表示元素之间的无序关系。
4. 散列结构：通过散列函数将元素映射到存储地址，实现快速的数据访问。
什么是数据结构数据结构是计算机科学中非常重要的一个领域，它研究如何有效地存储、组织和管理数据，以便于计算机能够快速、高效地处理这些数据。
数据结构是算法的基础，也是软件开发中不可或缺的一部分。
本文将从两个方面来探讨数据结构的概念和应用。
第一点：数据结构的基本概念数据结构可以分为两大类：线性结构和非线性结构。
线性结构是指数据元素之间存在一对一的关系，例如数组、链表、栈和队列等。
非线性结构是指数据元素之间存在一对多或多对多的关系，例如树、图和哈希表等。
1.线性结构线性结构是最基本的数据结构，它的特点是数据元素之间存在一对一的关系。
线性结构主要包括以下几种：（1）数组：数组是一种线性表，它是一组有序的数据元素的集合。
数组的元素个数是固定的，可以通过索引来访问任何一个元素。
数组的特点是随机访问，插入和删除操作需要移动大量元素，因此效率较低。
（2）链表：链表是一种由节点组成的数据结构，每个节点包含数据域和指针域。
链表的特点是插入和删除操作只需要改变指针的指向，因此效率较高，但随机访问比较困难。
（3）栈：栈是一种后进先出（Last In First Out，LIFO）的数据结构。
栈可以通过压栈（push）和出栈（pop）操作来管理数据元素。
栈的特点是只能在表的一端进行操作，适用于函数调用、表达式求值等场景。
（4）队列：队列是一种先进先出（First In First Out，FIFO）的数据结构。
队列可以通过入队（enqueue）和出队（dequeue）操作来管理数据元素。
队列的特点是数据元素按照进入顺序排列，适用于任务调度、缓冲处理等场景。
2.非线性结构非线性结构的数据元素之间存在一对多或多对多的关系，它的特点是可以存在层次关系和分支结构。
非线性结构主要包括以下几种：（1）树：树是一种层次化的数据结构，它由节点组成，每个节点包含数据域和指针域。
树的特点是存在父子关系，适用于表示具有层次关系的数据，如文件系统、组织结构等。
数据结构的基本概念
数据结构是计算机科学中用于组织和管理数据的方式。
它涉及将数据元素组织成特定的方式，以便能够有效地存储、检索和操作数据。
数据结构有很多种类，其中一些常见的包括数组、链表、栈、队列、树和图。
每种数据结构都有其特定的特点和应用场景。
数组是一种线性数据结构，它将相同类型的数据元素存储在连续的内存位置上，并使用索引来访问和操作数据。
链表也是一种线性数据结构，它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。
链表的优点是可以动态地添加或删除节点，但访问元素时需要遍历链表。
栈是一种后进先出（LIFO）的数据结构，只能在一端进行插入和删除操作。
常见的应用场景包括函数调用、表达式求值和浏览器的历史记录。
队列是一种先进先出（FIFO）的数据结构，允许在一端插入元素，在另一端删除元素。
队列常用于实现任务调度、消息传递和缓冲区管理等场景。
树是一种非线性的数据结构，它由节点和边组成，每个节点可以有零个或多个子节点。
树的应用包括文件系统、数据库索引和组织结构图。
图是由节点和边组成的一种非线性数据结构，节点之间的边可以是有向的或无向的。
图的应用包括社交网络、路由算法和地图导航。
了解不同的数据结构以及它们的特点和应用场景，可以帮助开发者选择合适的数据结构来解决问题，并提高程序的效率和性能。
《数据结构》说课稿引言概述：数据结构是计算机科学的基础，它研究数据的组织、存储和管理方式，是计算机程序设计的重要组成部分。
本文将从四个方面介绍数据结构的基本概念、常见数据结构类型、数据结构的应用以及学习数据结构的重要性。
一、基本概念1.1 数据结构的定义：数据结构是指一组数据元素及其之间的关系，是数据的逻辑结构和物理结构的抽象。
1.2 数据结构的分类：数据结构可以分为线性结构、非线性结构和文件结构三类，每类又可以细分为多种具体类型。
1.3 数据结构的基本操作：数据结构的基本操作包括插入、删除、查找和修改等，这些操作是对数据进行增删改查的基础。
二、常见数据结构类型2.1 数组：数组是一种线性结构，它由相同类型的数据元素组成，通过下标访问元素，具有随机访问的特点。
2.2 链表：链表是一种非线性结构，它由节点组成，每个节点包含数据和指向下一个节点的指针，可以实现灵活的插入和删除操作。
2.3 栈和队列：栈和队列是两种特殊的线性结构，栈具有先入后出的特点，而队列具有先入先出的特点，它们在算法中有广泛的应用。
2.4 树和图：树和图是两种常见的非线性结构，树是一种层次结构，图是由节点和边组成的网络结构，它们在数据库、网络等领域有重要的应用。
三、数据结构的应用3.1 数据库管理系统：数据库管理系统是基于数据结构的软件，它通过合理的数据结构来存储和管理大量的数据，提供高效的数据访问和操作功能。
3.2 图像处理：图像处理涉及大量的像素数据，通过合适的数据结构可以高效地存储和处理图像，实现图像的压缩、滤波、特征提取等操作。
3.3 算法设计：算法是解决问题的步骤和方法，合适的数据结构可以提高算法的效率和性能，常见的排序、查找和图算法都离不开数据结构的支持。
四、学习数据结构的重要性4.1 提高编程能力：学习数据结构可以培养抽象思维和逻辑思维能力，提高编程的效率和质量。
4.2 解决实际问题：数据结构是解决实际问题的基础，通过合适的数据结构可以更好地组织和管理数据，实现高效的数据处理和分析。
数据结构必考知识点总结在准备考试时，了解数据结构的基本概念和相关算法是非常重要的。
以下是一些数据结构的必考知识点总结：1. 基本概念数据结构的基本概念是非常重要的，包括数据、数据元素、数据项、数据对象、数据类型、抽象数据类型等的概念。
了解这些概念有助于更好地理解数据结构的本质和作用。
2. 线性表线性表是数据结构中最基本的一种，它包括顺序表和链表两种实现方式。
顺序表是将数据元素存放在一块连续的存储空间内，而链表是将数据元素存放在若干个节点中，每个节点包含数据和指向下一个节点的指针。
了解线性表的概念和基本操作是非常重要的。
3. 栈和队列栈和队列是两种特殊的线性表，它们分别具有后进先出和先进先出的特性。
栈和队列的实现方式有多种，包括数组和链表。
掌握栈和队列的基本操作和应用是数据结构的基本内容之一。
4. 树结构树是一种非线性的数据结构，它包括二叉树、多路树、二叉搜索树等多种形式。
了解树的基本定义和遍历算法是必考的知识点。
5. 图结构图是一种非线性的数据结构，它包括有向图和无向图两种形式。
了解图的基本概念和相关算法是非常重要的，包括图的存储方式、遍历算法、最短路径算法等。
6. 排序算法排序是一个非常重要的算法问题，掌握各种排序算法的原理和实现方式是必不可少的。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
7. 查找算法查找是另一个重要的算法问题，包括顺序查找、二分查找、哈希查找、树查找等。
了解各种查找算法的原理和实现方式是必考的知识点之一。
8. 算法复杂度分析算法的时间复杂度和空间复杂度是评价算法性能的重要指标，掌握复杂度分析的方法和技巧是非常重要的。
9. 抽象数据类型ADT是数据结构的一种概念模型，它包括数据的定义和基本操作的描述。
了解ADT的概念和实现方式是非常重要的。
10. 动态存储管理动态存储管理是数据结构中一个重要的问题，包括内存分配、内存释放、内存回收等。
了解动态存储管理的基本原理和实现方式是必考的知识点之一。
第1章绪论1.1 数据结构的基本概念数据元是数据的基本单位，一个数据元素可由若干个数据项完成，数据项是构成数据元素的不可分割的最小单位。
例如，学生记录就是一个数据元素，它由学号、姓名、性别等数据项组成。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
数据类型是一个值的集合和定义在此集合上一组操作的总称。
•原子类型：其值不可再分的数据类型•结构类型：其值可以再分解为若干成分（分量）的数据类型•抽象数据类型：抽象数据组织和与之相关的操作抽象数据类型（ADT）是指一个数学模型以及定义在该模型上的一组操作。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
通常用（数据对象、数据关系、基本操作集）这样的三元组来表示。
#关键词：数据，数据元素，数据对象，数据类型，数据结构数据结构的三要素：1.逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据，独立于计算机。
分为线性结构和非线性结构，线性表、栈、队列属于线性结构，树、图、集合属于非线性结构。
2.存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构，包括数据元素的表示和关系的表示，依赖于计算机语言，分为顺序存储（随机存取）、链式存储（无碎片）、索引存储（检索速度快）、散列存储（检索、增加、删除快）。
3.数据的运算：包括运算的定义和实现。
运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。
1.2 算法和算法评价算法是对特定问题求解步骤的一种描述，有五个特性：有穷性、确定性、可行性、输入、输出。
一个算法有零个或多个的输入，有一个或多个的输出。
时间复杂度是指该语句在算法中被重复执行的次数，不仅依赖于问题的规模n，也取决于待输入数据的性质。
一般指最坏情况下的时间复杂度。
空间复杂度定义为该算法所耗费的存储空间。
算法原地工作是指算法所需辅助空间是常量，即O(1)。
第2章线性表2.1 线性表的定义和基本操作线性表是具有相同数据类型的n个数据元素的有限序列。
数据结构知识点总结一、数据结构基础概念数据结构是指数据元素之间的关系，以及对数据元素进行操作的方法的总称。
数据结构是计算机科学中非常基础的概念，它为计算机程序的设计和实现提供了基础架构。
数据结构的研究内容包括数据的逻辑结构、数据的存储结构以及对数据进行操作的算法。
1.1 数据结构的分类数据结构可以根据数据的逻辑关系和数据的物理存储方式进行分类，常见的数据结构分类包括线性结构、树形结构、图结构等。
1.2 数据结构的基本概念（1）数据元素：数据结构中的基本单位，可以是原子类型或者复合类型。
（2）数据项：数据元素中的一个组成部分，通常是基本类型。
（3）数据结构的逻辑结构：指数据元素之间的逻辑关系，包括线性结构、树形结构、图结构等。
（4）数据结构的存储结构：指数据元素在计算机内存中的存储方式，包括顺序存储结构和链式存储结构等。
1.3 数据结构的特点数据结构具有以下几个特点：（1）抽象性：数据结构是对现实世界中的数据进行抽象和模型化的结果。
（2）实用性：数据结构是在解决实际问题中得出的经验总结，是具有广泛应用价值的。
（3）形式化：数据结构具有精确的数学定义和描述，可以进行分析和证明。
（4）计算性：数据结构是为了使计算机程序更加高效而存在的。
二、线性结构线性结构是数据元素之间存在一对一的关系，是一种最简单的数据结构。
常见的线性结构包括数组、链表、栈和队列等。
2.1 线性表线性表是数据元素之间存在一对一的关系的数据结构，可以采用顺序存储结构或者链式存储结构实现。
（1）顺序存储结构：线性表采用数组的方式进行存储，数据元素在内存中连续存储。
（2）链式存储结构：线性表采用链表的方式进行存储，数据元素在内存中非连续存储，通过指针将它们进行连接。
2.2 栈栈是一种特殊的线性表，只允许在一端进行插入和删除操作，这一端称为栈顶。
栈的操作遵循后进先出（LIFO）的原则。
2.3 队列队列也是一种特殊的线性表，允许在一端进行插入操作，另一端进行删除操作，这两端分别称为队尾和队首。
第五章数据结构基础概念本章我们将介绍有关数据结构的基础知识，要求大家熟悉数据结构中常用的名词、术语，掌握基本概念，分清逻辑结构和存储结构的性质；了解线性表的逻辑结构特性及其在计算机中的表示。
掌握线性表的顺序存储结构及其插入和删除操作的基本思想；掌握栈和队列的特点，能根据实际问题正确地选用它们，掌握栈满、栈空、队满、队空的判别方法；熟悉树型结构的描述方法，了解图的术语和概念。
5.1数据结构基本概念1、数据结构是怎样产生的？我们知道计算机已经不仅仅是用于科学计算了，早期的计算机确实主要用于数值处理，用于科学计算，随着计算机技术的飞速发展，计算机的应用范围不断扩大，已不再局限于单纯的数值计算，更多地应用于控制、管理及数据处理等非数值计算的处理工作。
非数值型的问题在我们日常生活中是非常多的，也需要我们使用计算机来处理这些非数值问题。
例如：在城市交通运输中，从A点到B点有很多条道路，每条道路的长度不同，拥挤程度不同，我们要选择一条最快的线路到达目的地，该如何选择？再比如：图书馆有成千上万的图书资料，我们该如何进行管理才能使我们可以快速查找到需要的资料。
北京市有上千万的人口，我们应该怎样保存这些人口的资料信息，才能使我们可以快速查找到所需要查找的人。
象这样的问题都是典型的非数值问题。
要用计算机处理这些非数值问题，就为我们提出了一个课题：如何在计算机内部描述这些非数值问题，采用什么样的算法可以快速、有效地完成问题的求解。
随着计算机技术的发展，于是就产生了数据结构。
进一步，对于不同的处理对象，要想设计出高质量的程序，就必须研究，如何组织数据和处理数据，根据问题的要求及数据元素之间的特性，确定相应的存储结构和算法，这些都是数据结构研究的内容。
我们可以通过下面的例子来认识数据结构。
电话是我们通讯联络必不可少的工具。
如何用计算机来实现自动查询电话号码呢？要求对于给定的任意姓名，如果该人有电话号码，则迅速给出电话号码，否则，给出查找不到该人电话号码的信息。
对于这样的问题，我们可以按照客户向电信局申请电话号码的先后次序建立电话号码表，存储到计算机中。
在这种情况下，由于电话号码表是没有任何规律的，查找时只能从第一个号码开始逐一进行，这样的逐一按顺序进行查找效率非常低。
为了提高查询的效率，我们可以根据每个用户姓名的第一个拼音字母，按照26个英文字母的顺序进行排列，这样根据姓名的第一个字母就可以迅速地进行查找，从而极大地减少了查找所需的时间。
进一步，我们可以按照用户的中文姓名的汉语拼音顺序进行排序，这样就可以进一步提高查询效率了。
在上述例子中，我们感兴趣的是如何提高查找效率。
为了解决这个问题，就必须了解待处理对象之间的关系，以及如何存储和表示这些数据。
在电话号码查询的例子中，每一个电话号码就是一个要处理的数据对象，我们也称为数据元素，在数据结构中为了抽象地表示不同的数据元素，为了研究对于具有相同性质的数据元素的共同特点和操作，我们将数据元素又称为数据结点，简称为结点。
电话号码经过处理，按照拼音排好了顺序，每个电话号码之间的先后次序就是数据元素之间的关系。
数据结构就是研究这类非数值处理的程序设计问题。
2、数据结构研究什么内容？数据结构一般包含三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。
●数据的逻辑结构是指数据元素之间的逻辑关系，与数据的在计算机内部是如何存储无关，数据的逻辑结构独立于计算机。
例如在城市交通中，两个地点之间就存在一种逻辑关系，两个地点之间的逻辑关系分为三种：第一种是：两个地点之间有公共汽车可以直达；第二种是：两个地点之间没有公共汽车可以直达，但可以通过中途换乘其他公共汽车而到达；第三种逻辑关系就是：两个地点之间没有公共汽车可以达到。
又如在电话号码本中，电话号码如何进行分类，按照什么顺序进行排列等都是数据之间的逻辑关系。
●数据的存储结构是指数据元素在计算机存储设备中的存储方式，可以用顺序存储方式，也可以用链式存储方式。
例如在城市交通的例子中，我们就要研究如何在计算机中表示1个地点，任何在计算机中表示两个地点之间存在一条公共汽车线路，该线路有多长等。
又如对于电话号码资料信息在计算机中如何保存，如何表示资料的分类，如何表示排好顺序的电话号码之间的先后次序关系。
●数据的运算主要包括：插入、删除、检索和排序等与问题相关的处理。
例如在城市交通问题中，我们就要设计求两点之间最短线路的算法，要能够判断从城市的任一点出发乘坐公共汽车是否可以达到城市的任何地方。
在电话号码问题中，我们就要设计如何插入一个新的电话号码信息，如何删除一个作废的电话号码信息，如何对电话号码进行快速整理排序，如何高效快速查找资料等算法。
为了进一步研究数据的逻辑结构，我们可以将数据的逻辑结构分为线性结构和非线性结构两大类。
线性结构包括：线性表、栈和队列等。
其主要特征为各个数据之间有明确的、唯一的“先后”顺序。
在现实生活中具有线性结构的实例非常多，例如我们在日常生活中的排队购物，队列中的每个人都有一个明确先后次序关系。
非线性结构包括树和图型结构。
树型结构的主要特征是结点之间存在着一种层次的关系，每一个结点对应着下一层的多个结点，也就是说，数据元素之间的关系是“一对多”的关系。
例如：我们一所学校下面有好几个系，每个系下面有好多班，每个班下面有好多学生。
我们说：学校—系—班—学生，每一层之间都是一个一对多的关系，这就是一个典型的树型结构。
而在图型结构中，任何两个结点之间都可能存在着联系，数据元素之间存在着多对多的关系。
典型的图型结构就是城市交通。
如果城市中有单行线路，则从城市中的一个地点A 出发，可以到达N个不同的地方，从城市的M个不同的地方出发又可以到达地点A。
城市交通就是一个典型的“多对多”的图型结构。
数据结构通常具有下列一些基本操作：1、插入：在数据结构的指定位置上添加一个新结点。
2、删除：删去数据结构中指定位置的结点。
3、更新：修改数据结构中某个结点的值。
4、查找：在数据结构中寻找满足指定条件的结点及其位置。
5、排序：按照指定的顺序，使结点重新排列。
5.2线性结构的基本概念线性结构是最常用且最简单的数据结构，它包括线性表、栈和队列等。
5.2.1线性表日常生活中大量存在着这样的表格，例如一份学生名单表，一张仓库设备清单等，我们把一个人、一台设备都抽象地看成是一个数据元素，这些数据元素之间除了在表中的排列次序即先后次序不同外，没有其它的联系，这一类的表属于线性表。
这里我们使用“结点”的概念来描述线性表。
结点就是对数据的一种抽象。
例如在学生名单中，我们可以认为一个学生数据就是一个结点，如果一长学生名单有1000人组成，我们就可以抽象地认为，学生名单这样的线性表就是由1000个结点组成的。
再比如，在一张仓库设备清单中有800台设备，我们就可以抽象地认为，仓库设备清单就是一张线性表，表中有800个结点。
在这样的抽象的意义上，我们就不再关心，我们是处理学生数据还是处理设备数据，我们可以认为我们处理的数据就是“结点”。
这样可以使得我们数据结构研究的算法具有通用性和一般性。
那么，从数据结构的角度出发，线性表是n（n≥0）个数据元素组成的有限序列，记为：（a1，a2……a n）当n=0时，线性表为空表。
在线性表中，除了第一个和最后一个数据元素外，每一个数据元素都有一个直接前趋结点和一个直接后继结点。
所谓直接前驱结点就是排列在它的前一个的那一个结点，直接后继结点就是排列在它后面的下一个结点。
线性表中的数据元素在不同的场合代表不同的含义，例如，在学生名单表及仓库设备清单表中不难看出，同一线性表具有相同的数据类型，学生和设备分别是两个表中的数据元素，各自代表不同的含义。
以管理仓库设备清单为例：工厂有时会根据需要，从仓库调出一台设备，或者新购进一批设备以备工程使用，对设备清单表而言，就是要进行删除或添加操作，这就转化为对线性表的运算。
在线性表中的基本运算包括：1、求表长；2、在线性表的指定位置插入一个数据元素；3、删除线性表中指定位置的数据元素；4、取线性表中指定位置的数据元素。
为了实现这些基本操作，我们先来研究一下，线性表是如何存储在计算机中的。
1、线性表的存储结构线性表可以用不同的方式存储在计算机中，其中最简单也是最常见的是用一组地址连续的存储空间，依次存放线性表中的每一个数据元素，称为线性表的顺序存储结构，用这种方法存储的线性表称为顺序表。
在高级语言中，可以用一维数组来实现。
线性表还可以采用链式方式进行存储。
每一个数据结点独立保存在内存的一片连续区域之中，结点之间通过“链”相互连接，这样就可以通过链来表示数据之间的先后次序关系了。
链式方式可以采用C语言中的结构来实现。
2、线性表的插入和删除操作大家知道，在商场排队购物时，如果有一个人插入到队伍中，他后面的人们就不得不后退一步，以保持正常的队形。
在线性表中插入一个数据元素，就与这一情况类似。
那么，怎样让计算机来实现呢？首先应指明插入位置，假如在第i个元素之前插入一个新的数据元素a，为了保持线性表的连续性，就需要腾空第i个位置用于存放新插入的元素。
为了实现这一操作，就必须从第i个元素开始到最后一个元素为止，把数据元素依次向后移动一个位置。
移动从最后一个位置的数据元素开始，依次向后移动，使长度为n的线性表（s1,s2……s i-1,s i…s n）变成长度为n+1的线性表（s1,s2…,s i-1,a,s i,…,s n）。
这一过程用计算机来实现就是算法处理的基本思想。
如图5.1所示：(a) 插入前n = 7(b) 插入后n = 8图5.1 线性表的插入过程（在第4个位置前插入100）对于删除操作，如果要删除第i个数据元素，由于线性表中的元素必须连续排列，故删除第i个元素以后要使它后面的所有元素向前移动一个位置，使长度为n的线性表（s1,…,s i-1,s i,s i+1,…s n）变成长度为n-1的线性表（s1,…,s i-1,s i+1,…s n）。
请看图5.2，在线性表中删除17。
(a) 删除前n = 8(b) 删除后n = 7图5.2 线性表的删除过程（删除第6个位置的元素17）5.2.2 栈栈的概念是从日常生活中货物在货栈内的存取过程抽象出来的，最后入栈的货物最先被取出来，例如从图书馆的书架中取书放到桌子上，第一次取出的放在最底层，第二次被取出的书放在第一本书的上面，依次叠放，最后被取出来的放在最上面，当我们在这一摞中取书时，最后放入的被最先取出，符合先入后出，后进先出的原则，因此，栈也称作后进先出表。
从逻辑上说，栈就是一种特殊的线性表，栈是一种受限的线性表，它限定在表的一端进行插入和删除操作。
表中允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。
