1.4 数据结构基础知识

掌握一些基础的数据结构与算法的知识，对理解本书有重要帮助。

数据结构（data structure）是指数据对象及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。数据结构的内容可归纳为3个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，这就是一个数据结构。

数据的逻辑结构

数据元素之间的逻辑关系。数据的逻辑结构通常有下列4类：

集合：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。

线性结构：其中的数据元素之间存在一对一的关系。

树型结构：其中的数据元素之间存在一对多的关系。

图状结构（或称网状结构）：其中的数据元素之间存在多对多的关系。

数据的存储结构

数据元素及它们之间的相互关系在计算机存储器内的表示（又称映像），也称为数据的物理结构。

数据的存储结构可采用以下4种基本的存储方法得到：

● 顺序存储方法。

● 链接存储方法。

● 索引存储方法。

● 散列存储方法。

1.4.1 线性表

线性表是具有相同数据类型的n(n≥0)个数据元素的有限序列。

顺序表

采用顺序存储结构的线性表称之为顺序表。

顺序表L的第i个元素的存储位置和第1个元素的存储位置的关系为：

                  LOC(ai)=LOC(a1)+(i-1)＊m

其中LOC(a1)是线性表的第1个数据元素的存储位置，通常称为线性表的起始位置或基地址。

顺序表的存储结构

          typedef int datatype;     /＊定义表元素类型＊/
          #define maxsize 1024   /＊线性表的最大长度＊/
          typedef struct
          {    datatype elem[maxsize];/＊存放表结点的数组＊/
          int length;                    /＊表长＊/
          }sequenlist;

顺序表的插入、删除操作

在顺序表第i个元素前插入结点，则需要把i到n的所有元素向后移动一位，最后把新元素插入到第i个位置。需要注意的是，在进行移动的时候，必须是从n到i依次向后移动，如果从i到n依次向后移动，则最后i+1到n+1位置的所有元素都是一样的值，即原来第i元素的值。

删除第i个元素时，需要将i+1到n元素依次向前移动。移动顺序与插入相反，是从前向后进行，即从i到n依次向前移动一个位置。

链表

以链式结构存储的线性表称之为链表。

链表包括：单链表，双向链表，循环链表。

单链表的存储结构

          typedef struct LNode
              {  int   data；
                Struct LNode ＊next;
              }LinkList;
          LinkList ＊L, ＊head;

单链表的插入、删除操作

要在单链表中第i个元素前插入结点，或者删除第i个结点，都只需要修改第i-1个结点的next指针。所以进行插入删除的主要工作就是找到第i-1个结点，这需要从头结点开始。

当需要在第1个元素前插入元素，或者删除第1个元素时，对于不带头结点的单链表，则需要修改头指针。这就是带头结点和不带头结点的单链表在进行运算时的主要区别。不带头结点的单链表在进行插入删除运算时，在程序的开始总是要判断是不是在表头进行操作。带头结点的单链表则不需要此操作。

线性表顺序存储与链式存储的比较

从时间的角度考虑，在按位置查找数据，或在查找元素的前趋和后继等方面，顺序存储有着较大的优势。在插入数据、删除数据时，链式存储就有较大的优势，这是由于在链表中只要修改指针即可做到；而在顺序表中进行插入和删除，平均要移动表中将近一半的数据元素。

从空间的角度考虑，顺序表的存储空间是静态分配的，在程序执行之前必须规定其存储规模。而动态链表的存储空间是动态分配的，只要内存空间有空闲，就不会产生溢出。

1.4.2 栈和队列

栈

限定只能在表的一端进行插入和删除运算的线性表。允许插入和删除运算的一端称为栈顶，不允许插入和删除运算的一端称为栈底。访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。

存储方式：顺序栈或链栈。

队列

只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。允许插入的一端称为队尾、允许删除的一端称为队头。队列遵循先进先出（FIFO）的原则。

存储方式：顺序队列（循环队列），链队列。

队列在顺序存储下会发生溢出。队空时再进行出队的操作称为“下溢”；而在队满时再进行入队的操作称为“上溢”。解决假溢出的方法是将顺序队列假想为一个首尾相接的圆环，称之为循环队列。

循环队列并不真的是一个循环的存储空间，它本身是一个顺序空间，只不过把它假想成一个首尾相连的空间。当指针走到最后一个元素后，再往后移动就强制指向第1个元素。由于不知道何时到了最后一个元素，一般只要是指针向后移动，都强制进行求余运算。

1.4.3 树

树（tree）是n（n≥0）个结点的有限集T，当n=0时，称为空树；当n＞0时，满足以下条件：

（1）有且仅有一个结点被称为树根（root）结点。

（2）当n＞1时，除根结点以外的其余n-1个结点可以划分成m(m＞0)个互不相交的有限集T1,T2,…，Tm，其中每一个集合本身又是一棵树，称为根的子树（subtree）。

结点的度（degree）：结点拥有的子树的数目。

树的度：树中最大的结点的度数即为树的度。

结点的层次（level）：从根结点算起，根为第1层，它的子结点为第2层……若某结点在第l层，则其子结点就在第l+1层。

树的高度（depth）：树中结点的最大层次数。

1.4.4 查找

给定一个关键字值K，在含有n个结点的表中找出关键字等于给定值K的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。

散列表（Hash Table）是一种重要的查找表。

散列的基本思想是：以结点的关键字K为自变量，通过一个确定的函数（即映射）关系h，计算出对应的函数值h(K)，然后把这个值解释为结点的存储地址，将结点存入h(K)所指的存储位置上。在查找时，根据要查找的关键字用同一函数h计算出地址，再到相应的单元里去取要找的结点。

用散列方法存储的线性表称为散列表（Hash Table），也称哈希表或杂凑表。上述的函数h称为散列函数，h(K)称为散列地址。

两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突。发生冲突的两个关键字称为该散列函数的同义词（Synonym）。

通常情况下，由于关键字的个数大于散列表的长度，因此无论怎样设计h，也不可能完全避免冲突。我们只能做到，在设计h时尽可能使冲突最少，同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到散列表中。

散列表与其他查找表的区别：

● 线性表查找、二分查找、分块查找、二叉排序树、B-树等查找方法其共同特点是：记录在存储结构中的相对位置是随机的，所以在查找时都要通过一系列的关键字比较才能确定待查记录在存储结构中的位置；也就是说，这类查找是以关键字的比较为基础的。

● 散列表则不同，它是通过散列函数将记录的关键字为自变量映射成记录的存储地址，散列表的生成就是把记录逐一存放到以相应函数值为地址的存储单元中。在散列表中查找时，只需用散列函数计算得到待查记录的存储地址，即可得到所查信息，必要时通过冲突处理方法处理冲突。冲突越小，效率越高。

1.4.5 排序

排序：是根据记录关键字的递增或递减关系将一组记录的次序重新排列。

排序方法的稳定性

在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称该排序方法是稳定的；否则，若具有相同关键字的记录之间的相对次序发生变化，则称该排序方法是不稳定的。

排序方法的分类。

按是否涉及数据的内、外存交换分类：外排序、内排序。

按策略划分内部排序方法：插入排序、选择排序、交换排序、归并排序和基数排序等。

排序算法性能评价

表1-2为各种排序方法的比较。判断一个算法性能的好坏，主要有两个标准。

（1）执行算法所需的时间。

（2）执行算法所需的辅助空间。

选取排序方法时需要考虑的因素有：

● 待排序的记录数目。

● 记录本身信息量的大小。

● 关键字的结构及其分布情况。

● 对排序稳定性的要求。

● 语言工具的条件、辅助空间的大小。