1. 逻辑结构
逻辑结构描述数据元素与数据元素之间的关联方式，简称为关系，表示的是事物本身的内在联系。逻辑结构又可以分为：线性结构和非线性结构两大类。
线性结构的特点表现为，线性结构中数据元素之间的正逆关系都是“一对一”的。 线性结构又可再分为：线性表、堆栈、队列等。
非线性结构的特点表现为：数据元素不一定存在确定的前后次序，甚至是无序的，数据元素之间存在从属或互为从属的关系或离散关系。
非线性结构又可再分为树形结构、图状或网状结构、纯集合结构。 在树型结构中，数据元素之间存在着“一对多”的关系。 在图或网状结构中，数据元素之间存在着“多对多”的关系。 在纯集合结构中，数据元素具有“同属于一个集合”的关系。 2. 存储结构 存储结构，是逻辑结构的数据元素在计算机的物理存储空间上地映象，映象不仅包含数据元素本身，而且包含着数据元素之间的关联方式，即关系的映象。
映象表现为两种方式：顺序映象和非顺序映象。 1) 顺序映象
顺序映象是指数据元素在一块连续地物理存储空间上存储，物理存储空间只用于存放数据元素本身，数据元素之间的关联以两个数据元素存储的相邻关系来表示或通过某个函数来表示。或者说，利用数据元素在存储空间上的相对位置来表示数据元素之间的逻辑关系。
如一组成绩信息，每个数据由姓名和成绩两个数据项构成： ｛｛彭亮，97｝，｛王明，95｝，｛李智，90｝，｛刘丹，88｝，｛肖象，78｝｝ 数据元素是按成绩从高至低的顺序排列，即按成绩从高至低关联，在物理存储空间上的存储映象如图1.2.2所示，
彭亮，97 王明，95 李智，90 刘丹，88 肖象，78
图1.2.2 成绩信息的顺序映象
再如,有一个下三角矩阵：
1 2 3 4 5
1 0 0 0 0 0
2 A 0 0 0 0 3 B C 0 0 0 4 D E F 0 0
5 G H I J 0
在物理存储空间上存放为如图1.2.3所示，数据元素存储的空间是连续地，每个数据元素以相邻方式存储，数组元素按行优先法则存储。如要查找第i行，第j列（1 F（i,j）=((i-1)*(i-2))/2+j A B C D E F G H I J 顺序映象的最大优点就是空间的利用率最高，但一旦要在中间插入数据元素或删除中间图1.2.3 下三角矩阵的顺序映象 数据元素，就必须移动大量数据元素，这种运算在计算机中是相当耗时的。 2) 非顺序映象 非顺序映象是指数据元素在物理存储空间上非连续地存储，物理存储空间不仅存放数据元素本身，而且为实现数据元素之间的关联，在每个数据元素存储的相邻空间中存储该数据元素关联的另一个或多个数据元素的起始地址。也可以说数据元素之间的关系是由附加“链接或指针”来表示。 非顺序映象存储结构中，数据元素的逻辑结构一般在物理空间上不是以物理空间的相邻来表现，而是在每个数据元素本身所占用空间的相邻空间中，存放该数据元素所关联的另一个或多个数据元素的位置，通常将这个空间称为链地址空间。最后一个数据元素的链地址空间指向空地址。可以看出数据元素在物理存储上是离散的，且物理顺序不一定与逻辑顺序保持一致。 成绩信息的物理映象如图1.2.4 第一个数据元素地址 刘丹，88 彭亮，97 李智，90 王明，95 肖象，78 空 图1.2.4 成绩信息的非顺序映象 D B A B C D E F 图1.2.5 二分枝的树逻辑结构 树的起点地址 空 空 空 A C F E 空 图1.2.6 树的存储结构 3. 数据域和链接域 1) 数据域 数据域是物理存储空间中存储数据元素中数据值的空间，如成绩数据问题中，存储姓名和成绩两个数据项，所占用的空间大小（字节数）依实际应用的数据元素中包含的信息量的大小而定。 2) 链接域 链接域又称指针域，是非顺序存储映象时表示数据元素之间关系的地址存储空间，是额外的空间付出。在顺序存储映象结构中，链接域是不存在的，数据元素之间关系是以物理存储的邻接方式隐含表示的。 线性表及其存储结构 1.3.1线性表的基本概念 线性表是有限元素（e1, ...,ei,...,en）的有序序列的集合。其中n是有穷自然数，ei是表中的元素，每个元素具有相同的特性，表中元素占用空间大小相同（记为：size），n是表的长度。当n=0时，表为空；当n>0时，e1是第一个元素（前件），en 是最后一个元素（后件）。 数据元素通常称为结构或记录类型。而包含多个结构或记录的线性表也可以称为文件。 线性表是一种线性结构。 特征： 1) 有且只有一个根结点e0，它无前件； 2) 有且只有一个终端结点en，它无后件； 3) 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 1.3.2 线性表顺序存储结构 在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。 线性表的顺序存储结构具有以下两个基本特点： ①线性表中所有元素所占的存储空间是连续的； ②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的。 在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间<字节数)相等，线性表中查找某一个元素是很方便的。 元素ei的地址则可以立即由下面公式求出。 location(ei)=location(e1)+（i-1）×size n ? 1 i ? e1 ? ei ? en 图2.2.1 线性表顺序存储 线性表中第k个数据元素之后插入元素x运算 它是指在线性表的元素ek+1和元素ek之间插入一个新的元素x。即要在元素ek+1的地方插入一个元素。 插入过程：首先需要将元素ek+1及以后的所有元素都要向后移动一个元素的位置，移动以后，空出ek元素的存储空间才能存入新的元素x。需要注意，实现元素的插入是有前提条件的，就是要求在线性表的元素en的后面还有空闲的存储单元可以使用，否则插入是无法进行的。插入后线性表的长度加1。 线性表中删除第k个数据元素运算 一般说来，删除运算是指需要删除线性表中的第K个数据元素。删除的办法是将ek后所有元素ek+1，?，en依次向前移动一个元素的位置，然后修改线性表的长度（减1）。 在顺序存储线性表的删除运算中，不用专门进行存储空间的释放，事实上，移动数据元素的同时，被删除元素的空间同时已被释放了，释放到线性表数据元素尾端，即线性表中删除前最后一个数据元素的空间。 线性表顺序存储方式下，由于相邻元素之间是紧邻的，而无可利用的“空闲”空间。因此，进行元素的插入或删除运算时，有着大量元素的移动，移动元素的多少取决于插入或删除元素的位置，而这种大量元素的移动是十分费时的，所以有着频繁的插入或删除运算的线性表，是不适合采用顺序存储方式的。 ①在线性表的指定位置处加入一个新的元素(即线性表的插入)； ②在线性表中删除指定的元素(即线性表的删除)： ⑧在线性表中查找某个(或某些)特定的元素(即线性表的查找)； ④对线性表中的元素进行整序(即线性表的排序)； ⑤按要求将一个线性表分解成多个线性表(即线性表的分解)； ⑥按要求将多个线性表合并成一个线性表(即线性表的合并)； ⑦复制一个线性表(即线性表的复制)： ⑧逆转一个线性表(即线性表的逆转)等。 1.4 1.4.1栈及其基本运算 1. 堆栈的定义 堆栈（也简称栈）是一个线性表，其数据元素只能从这个有序集合的同一端插入或删除，这一端称为堆栈的栈顶（top），而另一端称为堆栈的栈底（bottom）。 故也称栈为后进先出表或先进后出表，简称LIFO（Last in first out）或FILO（First in last out）表。 进栈 出栈 top D C B bottom A 图3.1.1 堆栈 2. 堆栈顺序存储 堆栈顺序存储方式，是将堆栈中的数据元素连续顺序地存放于存储器相邻的单元,来保 证堆栈数据元素逻辑上的有序性。 假设堆栈中每个数据元素占用size字节空间，top指向堆栈中进栈元素的栈顶元素，即栈顶元素的地址，MaxSize表示堆栈可以存储元素的最大空间。一般约定下标为1的元素空间就是栈底，这样就不再另设一变量再来记录栈底指针bottom。 3. 堆栈顺序存储运算 1) 判断堆栈是否为空 所谓堆栈为空，是指堆栈中没有一个数据元素，即栈顶指针top指向数据空间的第一个位置的前面。如堆栈不空，top总是指向栈顶元素。 2) 判断堆栈是否为满 所谓堆栈为满，是指堆栈的所有数据空间已经全部用完，即栈顶指针top指向数据空间的最大下标位置。如堆栈不满，top总是指向栈顶元素（top的值小于MaxSize）。 3) 进栈（又称压入）运算 进栈运算是将一新元素x存储到当前top所指的空间的“上”一个位置，即top+1的的元素空间中。进栈时，首先要判断堆栈中是否存在元素存放的空间，即先判断栈是否满，不满时，x可以进栈，否则出错（上溢）。x进栈前，top指针要先做相应地移动。 4) 出栈（又称弹出）运算 出栈运算是将栈顶元素取出，且将栈顶指针top向“下”移动一个位置，即取出top所指的元素，然后，top的值减1。出栈时，首先要判断堆栈中是否存在元素可取，即先判断栈是否空，不空时，可以出栈，否则出错（下溢）。出栈后，top指针要做相应地移动。 5) 返回栈顶元素的值 返回堆栈栈顶元素的值，是指将top所指的堆栈元素的值取出，但是top指针不移动，当然，能够取得栈顶值的前提是栈中有元素存在（先判断栈是否空）。 这个算法与出栈算法有所不同，两个算法都可以取得栈顶指针所指的元素值，但此算法取值后不会移动top指针，即栈中元素的个数不发生改变。 1.4.2 队列及其基本运算 1. 队列的定义 队列是一个线性表，其数据元素只能从这个线性表的一端插入，而从另一端删除，删除端称为队列的队头（front），插入端称为队列的队尾（rear）。 取数据时（删除），又称出队，总是从队列中front所指的位置取走数据。插入数据时，又称进队，总是在队列中rear所指的位置后面添加。取走数据与放入时的顺序恰好相同，故也称队列为先进先出表，简称FIFO（First in first out）表。 2. 循环队列及其运算 1. 循环队列由来 0 1 2 3 4 MaxSize-1 X A B C D ? front↑ rear↑ 图3.7.1 队列出队前 0 A front↑ 1 B 2 C 3 D 4 rear↑ 图3.7.2 队列出队后（元素前移） ? MaxSize-1