大话数据结构小记

由于在找工作前需要恶补『内功心法』，选择研读这本《大话数据结构》，以下为这本书的读书笔记以及自己代码的实现。

作者语录

谈创新精神

有很多复杂的恩义都是可以有简单办法去处理的，在于你肯不肯动脑筋，在于你有没有创新。

谈转换思维

充分利用现有的资源，正向思维，逆向思维、整合思维可以创造更大的价值。

谈深入思考

所谓优势，只不过是比别人多深入思考一点而已。

谈栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。

反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。

谈枯燥的计算

人脑是用来创造而不是做复杂枯燥的计算的。

作者的话

如果，我是说真的如果，你是一个对编程无比爱好的人，你学数据结构的目的既不是为了工作为了钱，也不是为了学位和考试，而只是为了更好的去感受编程之美。啊~你应该得到我的欣赏，我想我非常愿意与你成为朋友————因为我自己也没有做到如此纯粹地去学习和应用它。

数据结构绪论

名词解释

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

意义所在

为编写出一个”好”的程序，必须分析待处理对象的特性以及各处理对象的关系。这也就是数据结构的意义所在。

针对内存

数据是数据元素的集合，那么根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中。存储器主要是针对内存而言的，像硬盘、软盘、光盘等外部存储器的数据组织通常用文件结构来描述。

重点和难点

数据的存储结构应正确反应数据元素之间的逻辑关系，这才是最为关键的，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

逻辑结构

• 集合结构
• 线性结构
• 树形结构
• 图形结构

存储形式

• 顺序存储结构(比如数组)
• 链式存储结构(时常变化)

算法

名词解释

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

当然通俗点说，算法就是 描述解决问题的方法 。

和数据结构的关系

算法和数据结构的关系是相互依赖不可分割的。

算法的特性

算法具有五个基本特性：

• 输入
• 输出
• 有穷性
• 确定性
• 可行性

有穷性：

算法在执行有线的步骤后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。

确定性：

算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果。算法的每个步骤被精确定义而无歧义。

可行性：

算法的每一步都必须是可行的，也就是说，每一步都能通过执行有限次数完成。可行性意味着算法可以转换为程序上机运行，并得到正确的结果。

好算法的特征

算法不是唯一的，一个问题可以有很多种算法。但是有好坏之分。

正确性

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题的需求、能够得到问题的正确答案。

可读性

算法设计的另一目的是为了便于阅读、理解和交流。

健壮性

当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。

时间效率高和存储量低

顾名思义，时间效率指的是算法的执行时间，存储量即算法程序运行时所占用的内存或外部硬盘存储空间。

算法的时间复杂度

一般情况下，我们考虑的都是算法”最差情况”下的时间复杂度。具体计算都在书中，重在理解和应用。

常见的时间复杂度所消耗的时间大小排列为：

O(1)< O(log n) < O(n) < O(nlog n) < O(n*n) < O(n*n*n) < O(2的n次方) < O(n!) < O(n的n次方)

线性表(List)

名词解释

零个或多个数据元素的有限序列。

通俗解释:

具有像线一样性质的表。

抽象数据类型

ADT 线性表(List)

Data
线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素；除了最后的一个元素a-n外，没一个元素有且只有一个直接后继元素。
数据元素之间的关系是一对一的关系。

Operation

• InitList(*L): 初始化操作，建立一个空的线性表L
• ListEmpty(L): 若线性表为空，返回true，否则返回false
• ClearList(*L): 将线性表清空
• GetElem(L,i,*e): 将线性表L中的第i个位置元素返回给e
• LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
• ListInsert(*L,i,e): 在线性表L中的第i个位置插入新元素e。
• ListDelete(L,i,e): 删除线性表L中第i个位置元素，并用e返回其值。
• ListLength(L): 返回线性表L的元素个数。

endADT

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中设计的关于线性表的更复杂操作，完全可以用这些基本操作的组何来实习i安。

顺序存储结构

简介

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

利用数序存储结构的线性表为随机存储结构，随机存取的性能为O(1)。

代码实现部分

线性表(SqList)

可以用一元数组来实现。

#define MAXSIZE 20;//存储空间初始分配量
typedef int ElemType;//ElemType类型根据实际情况而定，这里假设为int
typedef struct
{
  ElemType data[MAXSIZE];//数组存储数据元素，最大值为MAXSIZE
  int length;//线性表当前长度
}SqList;

我们可以看出来描述顺序存储结构需要三个属性：

1. 存储空间的起始位置：数组data,它的存储位置就是存储空间的存储位置。
2. 线性表的自大存储容量：数组长度MaxSize。
3. 线性表的当前长度：length。

获得值(GetElem)

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码，如OK等
初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
操作结果：用e返回L中第i个数据元素的值
*/
Status GetElem(SqList L,int i, ElemType *e)
{
  if(L.length == 0 || i < 1 || i > L.length)
  {
    return Error;
  }
  *e = L.data[i - 1];
  return OK;
}

主意这里返回值类型Status是一个整型，返回OK代表1，ERROR代表0。

插入(ListInsert)

插入算法的思路：

• 如果插入位置不合理，抛出异常；
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量；
• 从最后一个元素开始向前便利到第i个位置，分别将它们都向后易懂一个位置；
• 将要插入元素填入位置i处；
• 表长+1

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度+1
Status ListInsert(SqList *L, int i, ElemType e)
{
  int k;
  if (L->length == MAXSIZE)//数序线性表已填满
    {return ERROR;}
  if (i < 1 || i > (L->length + 1))//当i不在范围内
    {return ERROR;}
  if (i <= L->length)//若插入数据位置不再表尾
  {
    for (k = L->(length - 1); k >= i - 1; k--)//将插入位置后数据元素向后移动一位
    {
      L->data[k+1] = L->data[k];
    }
  }
  L->data[i - 1] = e;//将新元素插入
  L->length++;
  return OK;
}

删除(ListDelete)

删除算法的思路：

• 如果删除位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
• 表长-1。

//初始条件：顺序线性表L已存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度-1
Status ListDelete(SqList *L, int i, ElemType *e)
{
  int k;
  if (L->length == 0)
  {return ERROR;}
  if (i < 1 || i > L->length)//删除位置不正确
  {return ERROR}
  if (i < 1 || i > L->length)//删除位置不正确
  {return ERROR}
  *e = L->data[i - 1];
  if (i < L->length)//如果删除的不是最后位置
    {
      for(k = i; k < length;k++)//将删除位置后记元素位置前移
      {
        k->data[k - 1] = L->data[k];
      }
    }
    L->length--;
    return OK;
}

线性表顺序存储结构的优缺点

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)；而插入或删除时，时间复杂度都是O(n)。

这就说明，它比较适合元素个数不太变化，而更多是存取数据的应用。当然，它的优缺点还不只这些。

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的”碎片“

链式存储结构

出现的原因

线性表的顺序存储结构最大的缺点是插入和删除时需要移动大量元素，这显然就需要耗费时间，链式存储结构是为了解决这个问题而出现的。

定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

而因此，以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

为了表示每个数据元素ai与其直接后继数据元素a(i+1)之间的逻辑关系，堆数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(node)。

单链表

n个结点(ai的存储映像)链结成一个链表，即为线性表(a1,a2…a(n))的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针与将线性表的数据元素按其逻辑次序链接在一起。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针，那么整个链表的存取位置就必须是从头指针开始进行了。
至于最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为”空(NULL)”。

有时，为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点称为头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有个这特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

代码实现

单链表实现

单链表中，我们在C语言中可用结构指针来描述

//线性表的单链表存储结构
typedef struct Node
{
  ElemType data;
  struct Node *next;
}Node;
typedef struct Node *LinkeList;//定义LinkList

从这个结构体定义中，我们也就知道，结点由存放数据元素的数据域和**存放后继结点地址的指针域组成。p->data指一个数据元素，而p->next的值则是一个指针。

读取实现

在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的，但在单链表中就相对麻烦一些。

获得链表第i个数据的算法思路：

1. 声明一个结点p指向链表第1个结点，初始化j从1开始；
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j++；
3. 若到链表末尾p为空，则说明第i个元素不存在；
4. 否则查找成功，返回结点p的数据。

Status GetElem(LinkList L, int i, ElemType *e)
{
  int j;
  LinkeList p;//声明一个结点
  p = L->next;//让p指向链表L的第一个结点
  j = 1;
  while (p && j < i)//p不为空或者计数器j还没有等于i时，循环继续
  {
    p = p->next;//让p指向下一个结点
    j++;
  }
  if (!p)
  {return ERROR;}//第i个元素不存在
  *e = p->data;//取第i个元素的数据
  return OK;
}

由此可见查找操作的时间复杂度为O(n)

插入实现

单链表第i个数据插入结点的算法思路：

1. 声明一个结点p指向链表第一个结点，初始化j从1开始；
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j++;
3. 若到链表末尾p为空，则说明第i个元素不存在；
4. 否则查找成功，在系统中生成一个空结点s；
5. 将数据元素e赋值给s->data;
6. 单链表的插入标准语句s->next = p->next; p->next = s;
7. 返回成功

//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(LinkList *L, int i, ElemType e)
{
  int j;
  LinkList p,s;
  p = *L;
  j = 1;
  while (p && j < i) //寻找第i个结点
  {
    p = p->next;
    j++;
  }
  if (!p)
  {return ERROR;}//第i个元素不存在
  s = (LinkList)malloc(sizeof(Node));//生成新结点 C标准函数
  s->data = e;
  s->next = p->next;//将p的后继结点赋值给s的后继
  p->next = s;//将s赋值给p的后继
  return OK;
}

在这段代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找到了一小块空地，准备用来存放e数据s结点。

删除实现

单链表第i个数据删除结点的算法思路：

1. 声明一结点p指向链表第1个结点，初始化j从1开始；
2. 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
3. 若到链表末尾p为空，则说明第i个元素不存在；
4. 否则查找成功，将欲删除的结点p->next赋值给q；
5. 单链表的删除标准语句p->next = q->next;
6. 将q结点中的数据赋值给e，作为返回；
7. 释放q的结点；
8. 返回成功。

//初始条件：顺序线性表L已经存在，1<=i<=ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status LsitDelete(LinkList *L, int i, ElemType *e)
{
  int j;
  LinkList p,q;
  p = *L;
  j = 1;
  while (p->next && j < i)//遍历寻找第i个元素
  {
    p = p->next:
    j++;
  }
  if (!(p->next))
  {return ERROR;}//第i个元素不存在
  q = p->next;
  p -> next = q->next;//将q的后继赋值给p的后继
  *e = q->data;//将q结点中的数据给e，这一步看情况可省略
  free(q);//让系统回收次结点，释放内存
  return OK;
}

在这段代码里，我们又用到了另一个C语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。

插入删除小结

分析一下刚才所展示的单链表插入和删除算法，我们发现，它们其实都是由两部分组成：

• 遍历查找第i个元素；
• 插入和删除元素。

从整个算法来说，我们很容易推导出：它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。

但如果，我们希望从第i个位置，插入10个元素，对比线性表的顺序存储结构，单链表数据结构优势就体现出来了。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越明显。

单链表的整表创建

回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就是不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即使生成。

所以创建单链表的过程就是一个动态生成链表的过程。即从”空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

单链表整表创建的算法思路：

1. 声明一结点和计数器变量；
2. 初始化一空链表L；
3. 让L的头结点的指针指向NULL，即建立一个带头结点的单链表；
4. 循环： 生成一新结点赋值给p； 随机生成一数字赋值给p的数据域p->data; * 将p插入到头结点与前一新结点之间。

//随机产生n个元素的值，建立带表头结点的单链线性表L(头插法)
void CreateListHead(LinkList *L, int n)
{
  LinkList p;
  int i;
  srand(time(0));//初始化随机数种子
  *L = (LinkList)malloc(sizeof(Node));
  (*L)->next = NULL;//先建立一个带头结点的单链表
  for(i = 0; i < n; i++)
  {
    p = (LinkList)malloc(sizeof(node));//生成新结点
    p->data = rand()%100 + 1;//随机生成100以内的数字
    p->next = (*L)->next;
    (*L)->next = p;//插入到表头
  }
}

这段代码里，我们用的是插队的方法，就是始终让新结点位于第一的位置。我们也可以把这种算法简称为头插法。

可事实上，我们还可以不这样干，为什么不把新结点都放在最后呢，这才是排队时的正常思维，所谓的先来后独傲。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。

//随机产生n个元素的值，建立带表头结点的单链线性表L(尾插法)
void CreateListTail(LinkList *L, int n)
{
  LinkList p,r;
  int i;
  scrand(time(0));//初始化随机数
  *L = (LinkList)malloc(sizeof(Node));//为整个线性表
  r = *L;
  for (i = 0; i < n; i++)
  {
    p = (Node *)malloc(sizeof(Node));//生成新结点
    p->data = rand()%100 + 1;//随机生成新结点
    r->next = p;//将表尾终端结点的指针指向新结点
    r = p;
  }
  r->next = NULL;//表示当前链表结束
}

单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下：

1. 声明一结点p和q；
2. 将第一个结点赋值给p;
3. 循环： 将下一结点赋值给q; 释放p; * 将q赋值给p。

//初始条件：顺序线性表L已存在
//操作结果：将L重置为空表
Status ClearList(LinkList *L)
{
  LinkList p,q;
  p = (*L)->next; //p指向第一个结点
  while(p)
  {
    q = p->next;
    free(p);
    p = q;
  }
  (*L)->next = NULL;//头结点指针域为空
  return OK;
}

在这段代码里，常见的错误就是有同学会觉得q变量没有存在的必要。在循环体内直接写free(P);p = p->next;即可。可这样会带来什么问题呢？

要知道p是一个结点，它除了有数据域，还有指针域。你在做free(p);时，其实是对它整个结点进行删除和内存释放的工作。p = q;这句相当于起了一个承上启下的作用。这点需要好好理解。

单链表结构和顺序存储结构对比

存储分配方式：

• 顺序存储结构用一段连续的存储单元一次存储线性表的数据元素
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素

时间性能：

• 查找
  • 顺序存储结构O(1)
  • 单链表O(n)
• 插入和删除
  • 顺序存储结构需要平均移动表长一般的元素，时间为O(n)
  • 单链表在找出某位置的指针后，插入和删除时间仅为O(1)

空间性能：

• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

小结

通过上面的对比，我们可以得出一些经验性的结论：

• 若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。
• 若需要频繁插入和删除时，宜采用单链表结构。
• 当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。

我们需要根据实际情况，来综合平衡采用更能满足和达到需求和性能的数据结构。

静态链表

前言

其实C语言真是好东西，它具有的指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便(当然高级语言从某种角度也简介实现了堆指针的某些作用)。

但对于一些上古时期的语言，如Basic、Fortran等早期的编程语言，由于没有指针，链表结构按照我们的讲法，它就没法实现了。

所以就有人想出来用数组来代替指针，来描述单链表。

话外音：(禁不住感叹道)这是一个多么天才的设想~！

概念解析

首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据，而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。

我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫游标实现法。

代码实现

线性表的静态链表存储结构

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲时间可以便于插入时不至于溢出。

//线性表的静态链表存储结构
#defined MAXSIZE 1000 //建设链表的最大长度是1000
typedef struct
{
  ElemType data;
  int cur; //游标(cursor),为0时表示没有指向
}Component，StaticLinkList[MAXSIZE];

备用链表

另外我们堆数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未实用的数组元素称为备用链表。

而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；数组的最后一个元素的cur则存放第一个有数值的元素的下表，相当于单链表中的头结点作用。

//将一维数组space中各分量链成一备用链表
//space[0].cur为头指针，"0"表示空指针
Status InitList(StaticLinkList space)
{
  int i;
  for (i = 0; i < MAXSIZE - 1; i++)
  {
    space[i].cur = i + 1;
  }
  space[MAXSIZE - 1].cur = 0;//目前静态链表为空，最后一个元素的cur值为0
  return OK;
}

插入

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。

在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做到插入和删除的操作。

为了辩明数组中哪些分量未被使用，解决的办法是将所有未被使用果的以及已被删除的分量用游标连成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的结点。

//若备用链表非空，则返回分配的结点下表，否则返回0
int Malloc_SLL(StaticLinkList space)
{
  int i = space[0].cur;//当前数组u第一个元素cur存的值，就是要返回的第一个备用空间的下标
  if(space[0].cur)
  {
    space[0].cur = space[i].cur;//由于要拿出一个分量来使用了，所以我们就得把它的下一个分量拿来当备用。
  }
  return i;
}

插入操作如下：

//在L中第i个严肃之前插入新的数据元素e
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
  int j, k, l;
  k = MAXSIZE - 1;//主意k首先是最后一个元素的下标
  if (i < 1 || i > ListLength(L) + 1)
  {return ERROR;}
  j = Malloc_SLL(L);//获得空间分量的下标
  if(j)
  {
    L[j].data = e; //将数据赋值给此分量的data
    for(l = 1; l <= i - 1; l++)//找到第i个元素之前的位置
    {
      k = L[k].cur;
    }
    L[j].cur = L[k].cur;//把第i个元素之前的cur赋值给新元素的cur
    L[k].cur = j; //把新元素的下标号赋值给第i个元素之前元素的下标
    return OK;
  }
  return ERROR;
}

就这样，我们实现了在数组中不移动元素也可以插入数据的操作。

删除

和前面一样，删除元素时，原来是需要释放结点的函数free()。现在我们也得自己实现它：

//将下表为k的空闲结点回收到备用链表
void FREE_SSL(StaticLinkList space, int k)
{
  space[k].cur = space[0].cur;//把第一个元素cur值赋给要删除的分量cur
  space[0].cur = k;//把要删除的分量下表赋值给第一个元素的cur
}

下面就是删除实现

//删除在L中第i个数据元素e
Status ListDelete(StaticLinkList L, int i)
{
  int j,k;
  if(i < 1 || i > ListLength(L))
  {return ERROR;}
  k = MAXSIZE - 1;
  for (j = 1; j <= i - 1; j++)
  {
    k = L[k].cur;
  }
  j = L[k].cur;
  L[k].cur = L[i].cur;
  FREE_SSL(L,j);
  retrun OK;
}

ListLenght实现

//初始条件：静态链表L已存在。 操作结果：返回L中数据元素的个数
int ListLength(StaticLinkList L)
{
  int j = 0;
  int i = L[MAXSIZE - 1].cur;
  while(i)
  {
    i = L[i].cur;
    j++;
  }
  return j;
}

另外一些操作和线性表的基本操作相同，实现上也不复杂，我们在课堂上就不讲解了。

静态链表优缺点

优点：

• 在插入和删除操作时，只需要修改游标(cursor)，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点：

• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了顺序存储结构随机存取的特性

小结

总的来说，静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管大家不一定会用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。

循环链表

前言

对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了想后链的操作，这样，当中某一结点就无法找到它的前驱结点了，即：不能选择回倒。

由此诞生了循环列表。

概念

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linked list)。

循环链表解决了一个很麻烦的问题：如何从当中一个结点出发，访问到链表的全部结点。

为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。

和单链表的主要差异

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否唯恐，现在则是p->next不等于头结点，则循环未结束。

改造尾指针

在单链表中，我们有了头结点时，可以用O(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要O(n)时间，因为我们需要将单链表全部扫描一遍。

有没有可能用O(1)的时间由链表指针访问到最后一个结点呢？当然可以。

不过我们需要改造一下这个循环链表，不用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。

如： 终端结点用为指针rear指示，则查找终端结点是O(1)，而开始结点，其实就是rear->next->next，其时间复杂度也为O(1)

举个例子

举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。如要合并尾指针分别为rearA和rearB的两个循环链表。只需要如下的操作即可：

p = rearA->next;//保存A表的头结点
rearA->next = rearB->next->next;//将本是指向B表的第一个结点(不是头结点)赋值给rearA->next
rearB->next = p;//将原A表的头结点赋值给rearB->next
free(p);//释放p

双向链表

前言

我们在单链表中，有了next指针，这就使得我们要查找下一结点的时间复杂度为O(1)。可是如果我们要查找的是上一个结点的话，那最坏的时间复杂度就是O(n)了，因为我们每次都要从头即使遍历查找。

为了克服单向性这一缺点，我们的老科学家们，设计出了双向链表。

概念

双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

代码实现

//线性表的双向链表存储结构
typedef struct DulNode
{
  ElemType data;
  struct DulNode *prior; //直接前驱指针
  struct DulNode *next; //直接后继指针
}DulNode, *DuLinkList;

尽然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

其他操作

双向链表是单链表中扩展出来的结构，所以它的很多操作是和单链表相同的，比如求长度的ListLength，查找元素的GetElem，获得元素位置的LocateElem等，这些操作都只要涉及一个方向的指针即可，另一指针多了也不能提供什么帮助。

就像人生一样，想享乐就得先努力，欲收获就得付出代价。双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。

插入操作时，其实并不复杂，不过顺序很重要。

举个例子

我们现在假设存储元素e的结点为s，要实现将结点s插入到结点p和p->next之间需要下面几步

s->prior = p; //把p赋值给s的前驱结点
s->next = p->next; //把p->next赋值给s的后继结点
s->next->prior = s; //把s赋值给p->next的前驱结
p -> next = s; //把s赋值给p的后继结点

小结

双向链表相对于单链表来说，要更复杂一些，毕竟它多了prior指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多一些的。

不过由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。

总结回顾

这一章我们主要讲的是线性表。

先谈了它的定义，线性表是零个或者多个具有相同类型的数据元素的有限序列。然后谈了线性表的抽象数据类型，如它的一些基本操作。

之后我们就线性表的两大结构做了讲述，先讲的是比较容易的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。通常我们都是用数组来实现这一结构。

后来是我们的重点，由顺序存储结构的插入和删除操作不方便，引出了链式存储结构。它具有不受固定的存储空间限制，可以比较快捷的插入和删除操作的特点。然后我们分别就链式存储结构的不同形式，如单链表、循环链表和双向链表做了讲解，另外我们还讲了若不使用指针如何处理链表结构的静态链表方法。

总的来说，线性表的这两种结构其实是后面其他数据结构的基础。把它们学明白，对后面的学习有着至关重要的作用。

栈和队列

前言

栈是限定仅在表尾进行插入和删除操作的线性表。

队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

栈

概念解释

栈(stack)是限定仅在表尾进行插入和删除操作的线性表。

我们把允许插入和删除的一端称为栈顶(top)，另一端称
为栈底(bottom)，不含任何数据元素的栈称为空栈。

首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

栈又称为后进先出(Last In First Out)的线性表，简称LIFO结构。

栈的插入操作，叫做进栈，也称压栈、入栈。栈的删除操作，叫做出栈，也有的叫作弹栈。

栈的抽象数据类型

ADT 栈(stack)

• Data 同线性表。元素具有**相同的类型，相邻元素具有前驱和后继关系。
• Operation
  • InitStack(*S): 初始化操作，建立一个空栈S。
  • DestoryStack(*S): 若栈存在，则销毁它。
  • ClearStack(*S): 将栈清空
  • StackEmpty(*S): 若栈为空，返回true，否则返回false。
  • GetTop(S,*e): 若栈存在且非空，用e返回S的栈顶元素。
  • Push(*S,e): 若栈存在，插入新元素e到栈S中并成为栈顶元素。
  • Pop(S,e): 删除栈S中栈顶元素，并用e返回其值。
  • StackLength(S): 返回栈S的元素个数
• endADT

由于栈本身就是一个线性表，那么上一章我们讨论了线性表的顺序存储和链式存储，对于栈来说，也同样是适用的。

栈的顺序存储结构

栈的顺序结构定义

当栈存在一个元素时，top等于0(因为数组是从0开始的)，因此通常把空栈的判定条件定为top等于-1

//栈的结构定义
typedef int SElemType; //SElemType类型根据实际情况而定，这里假设为int
typedef struct
{
  SElemType data[MAXSIZE];
  int top; //用于栈顶指针
}SqStack;

进栈操作

对于进栈操作push，如下

//插入元素e为新的栈顶元素
Status Push(SqStack *S, SElemType e)
{
  if(S->top == MAXSIZE - 1)//栈满
  {return ERROR;}
  S->top++;//栈顶指针增加1
  S->data[s->top] = e;//将新插入元素赋值给栈顶空间
  return OK;
}

出栈操作

出栈操作pop，如下

//出栈操作pop
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
Status Pop(SqStack *S, SElemType *e)
{
  if (S->top == -1)
  {return ERROR;}
  *e = S->data[S->top];//将要删除的栈顶元素赋值给e
  S->(top --); //栈顶指针-1
  return OK;
}

进栈和出栈没有涉及到任何循环语句，因此时间复杂度均是(1)。

两栈共享空间

栈顺序存储的问题

其实栈的顺序存储还是很方便的，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题。

不过它有一个很大的缺陷，就是必须事先确定数序存储空间大小，万一不够用了，就需要编程手段来拓展数组的容量，非常麻烦。对于一个栈，我们也只能尽量考虑周全，设计出合适大小的数组来处理，但对于两个相同类型的栈，我们却可以做到最大限度地利用其事先开辟的存储空间来进行操作。

解决方案

如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。我们完全可以用一个数组来存储两个栈，只不过需要点小技巧。

关键思路是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。

从这里也就可以分析出来，栈1为空时，就是top1等于-1时；而当top2等于n时，即栈2为空时，那什么时候栈满呢？

想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。但更多的情况，两个栈见面之时，也就是两个指针之间相差1时，即top1 + 1 == top2为栈满。

结构代码

两栈共享空间的结构如下：

//两栈共享空间结构
typedef struct
{
  SElemType data[MAXSIZE];
  int top1; //栈1 栈顶指针
  int top2; //栈2 栈顶指针
}SqDoubleStack;

Push方法

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下：

//插入元素e为新的栈顶元素
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
  if (S->(top1 + 1) == S->top2) //栈已满，不能再push新元素了
  {return ERROR};
  if (stackNumber == 1) //栈1有元素进栈
  {
    S->data[++S->top1] = e; //若是栈1则先top1+1后给数组元素赋值
  }
  else if(stackNumber == 2) //栈2有元素进栈
  {
    S->data[--S->top2] = e; //若是栈2则先top2-1后给数组元素赋值
  }
  return OK;
}

因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担心溢出问题的。

pop方法

对于两栈共享空间的pop方法，参数就只是判断栈1和栈2的参数stackNumber，如下

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber)
{
  if (stackNumber == )
  {
    if (S->top1 == -1)
    {return ERROR;} //说明栈1已经是空栈，溢出
    *e = S->data[S->(top1--)]; //将栈1的栈顶元素出站
  }
  else if (stackNumber == 2)
  {
    if (S->top2 == MAXSIZE)
    {return ERROR;} //说明栈2已经是空栈，溢出
    *e = S->data[S->(top2++)]; //将栈2的栈顶元素出栈
  }
  return OK;
}

适用场合

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。这样使用两栈共享空间存储方法才有比较大的意义。

栈的链式存储结构

前言

栈的链式存储结构，简称为链栈。

想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？

由于单链表有头指针，而栈顶指针也是必须的，那干嘛不让它俩合二为一呢？所以比较好的办法是把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

结构

对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。(这个时候应该叫做『内核恐慌』把：）)

但对于空栈来说，链表原定义式头指针指向空，那么链栈的空其实就是top=NULL的时候

typedef struct StackNode
{
  SElemType data;
  struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack
{
  LinkStackPtr top;
  int count;
}LinkStack;

链栈的操作绝大部分都和单链表类似，只是在插入和删除上，特殊一些。

进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，代码如下

//插入元素e为新的栈顶元素
Status Push(LInkStack *S, SElemType e)
{
  LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
  s->data = e;
  s->next = s->top;//把当前的栈顶元素赋值给新结点的直接后继。
  s->top = s; //将新的结点s赋值给栈顶指针
  S->count++;
  return OK;
}

出栈操作

至于链栈的出栈pop操作，也是很简单的三句操作。

假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
Status Pop(LinkStack *S, SElemType *e)
{
  LinkStackPtr p;
  if (StackEmpty(*S))
  {return ERROR;}
  *e = S->top->data;
  p = S->top; //将栈顶结点赋值给p
  S->top = S->top->next; //使得栈顶指针下移一位，指向后一结点
  free(P); //释放结点p
  S->count--;
  return OK;
}

小结链栈push&pop

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

对比一下顺序栈和链栈，它们在时间复杂度上是一样的，均为O(1)。

对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定为方便。

而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。

所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，有时很小，有时又非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

栈的作用(重要)

有的同学可能会觉得，用数组或链表直接实现功能不就行了吗？干嘛要引入栈这样的数据结构呢？

其实这和我们明明有两只脚可以走了，干嘛还要乘汽车、火车、飞机一样。理论上，陆地上的任何地方，你都是可以靠双脚走到的，可那需要多少时间和精力呢？我们更关注的是到达而不是如何去的过程。

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要去分散精力去考虑数组的下表增减等细节问题，反而掩盖了问题的本质。

所以现在的许多高级语言，比如Python、Swift等都有堆栈结构的封装，你可以不用关注它的实现细节，就可以直接使用Stack的push和pop方法，非常方便。

栈的应用–递归(recursion)

举个例子

栈的很重要的应用就是在程序设计语言中实现了递归。

举个例子–斐波那契数列

F(n) =

• 0, 当 n = 0
• 1, 当 n = 1
• F(n-1) + F(n-2), 当n>1

//斐波那契数列的递归函数
int Fbi(int i)
{
  if (i < 2)
  {
    return i == 0 ? 0 : 1;
  }
  return Fbi(i - 1) + Fbi(i - 2); //这里Fbi就是函数自己，它在自己调用自己
}
int main()
{
  int i;
  for (int i = 0; i < 40; i++) {
    printf("%d\t", Fbi(i));
  }
  return 0;
}

概念解释

我们把一个直接调用自己或通过一系列的调用语句简介地调用自己的函数，称作递归函数。

当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

递归和栈

前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。

这种存储某些数据，并在后面又以存储的逆序恢复这些数据，以提供之后使用的需求，显然很符合栈这样的数据结构，因此，编译器使用栈实现递归就没什么好惊讶的了。

简单的说，就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

当然，对于现在的高级语言，这样的递归问题是不需要用户来管理这个栈的，一切由系统代劳了。：）

栈的应用–四则运算表达式求值

括号难题

如果让你用C语言或其他高级语言(Python除外)实现堆数学表达式的求值，你打算如何做？

这里面的困难就在于乘除在加减的后面，却要先运算，而加入了括号后，就变得更加复杂。不知道该如何处理。

但仔细观察后发现，括号都是成对出现的，有做括号就一定会有右括号，对于多重括号，最终也是完全嵌套匹配的。这用栈结构正好合适。

只要碰到左括号，就将次左括号进栈，不管表达式有多少重括号，反正遇到左括号就进栈，而后面出现右括号时，就让栈顶的左括号出栈，期间让数字运算。

这样，最终有括号的表达式从左到右巡查一遍，栈应该是由空到有元素，最终再因全部匹配成功后成为空栈的结果。

四则运算难题

但对于四则运算，括号也只是当中的一部分，先乘除后加减使得问题依然复杂，如何有效地处理它们呢？我们伟大的科学家想到了好办法。

这就是–逆波兰(Reverse Polish Notation, RPN)表示。即一种不需要括号的后缀表示法。

逆波兰(后缀表示法)

举个例子

对于 9 + (3 - 1) * 3 + 10 / 2，

用后缀表示法应该为 9 3 1 - 3 * + 10 2 / +

叫后缀的原因在于所有的符号都是在要运算数字的后面出现。显然，这里没有了括号，对于从来没有接触过后缀表达式的同学来将，这样的表述是很难受的。不过你不喜欢，我们聪明的计算机可是很喜欢。

计算规则

规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号就将处于栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式，即”9 + (3 - 1) * 3 + 10 / 2”叫做中缀表达式。因为所有的运算符号都在两个数字中间，现在我们的问题就是中缀到后缀的转化。

中缀表达式”9 + (3 - 1) 3 + 10 / 2”转化为后缀表达式”9 3 1 - 3 + 10 2 / +”。

规则：从左到右遍历中缀表达式的每个数字和符号

• 若是数字就输出，即成为后缀表达式的一部分；
• 若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(乘除优于加减)，则栈顶元素依次出栈并输出，并将当前符号进栈。

一直到最终输出后缀表达式为止。

简单的说，就是遇到数字就单纯的输出，遇到符号则要进入堆栈来考虑。

小结

我们可以看出，要想让计算机具有处理我们通常的标准(中缀)表达式的能力，最重要的就是两步：

1. 将中缀表达式转化为后缀表达式(栈用来进出运算的符号)
2. 将后缀表达式进行运算得出结果(栈用来进出运算的数字)。

整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

队列

名词解释

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

假设队列是q = (a1, a2, … , a(n))，那么a1就是队头元素，而a(n)是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时就列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

抽象数据类型

同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。

ADT 队列(Queue)

• Data
  • 同线性表。**元素具有相同的类型，相邻元素具有前驱和后继关系。
• Operation
  • InitQueue(*Q): 初始化操作，建立一个空队列Q。
  • DestroyQueue(*Q): 若队列Q存在，则销毁它。
  • ClearQueue(*Q): 将队列清空。
  • QueueEmpty(Q): 若队列为空，返回true，否则返回false。
  • GetHead(Q, *e): 若队列Q存在且为空，返回true,否则返回false。
  • EnQueue(*Q, e): 若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
  • DeQueue(Q, e): 删除队列Q中对头元素，并用e返回其值。
  • QueueLength(Q): 返回队列Q的元素个数

endADT

循环队列(顺序存储结构)

线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。

队列的顺序存储

前言

入队列(插入)操作很简单，就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)。

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的对头，也就是下标为0的位置不为空，此时时间复杂度为O(n)。

这里的实现和线性表的顺序存储结构完全相同，不再解释。

出队列的问题

可我们再想想，为什么出队列一定要全部移动呢？如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队列的性能就会大大增加。也就是说，**队头不需要一定在下标为0的位置。

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

循环队列定义

我们把队列的这种头尾相接的顺序存储结构称为循环队列。

队列满的条件是(rear + 1) % QueueSize == front

通用的计算队列长度公式为：(rear - front + QueueSize) % QueueSize

实现

顺序存储

循环队列的顺序存储结构代码如下：

typedef int OElemType; //OElemType类型根据实际情况而定，这里假设为int
//循环队列的顺序存储结构
typedef struct
{
  QElemType data[MAXSIZE];
  int front; //头指针
  int rear; //尾指针，若队列不为空，指向队列尾元素的下一个位置
}SqQueue;

初始化

循环队列的初始化代码如下

//初始化一个空队列
Status InitQueue(SqQueue *Q)
{
  Q->front = 0;
  Q->rear = 0;
  return OK;
}

求队列长度

循环队列求队列长度代码如下

//返回Q的元素个数，也就是队列的当前长度
int QueueLength(SqQueue Q)
{
  return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

入队列操作

循环队列的入队列操作代码如下：

//若队列未满，则插入元素e为Q新的队尾元素
Status EnQueue(SqQueue *Q, QElemType e)
{
  if ((Q->rear + 1) % MAXSIZE == Q->front) //判断队列是否满
  {return ERROR;}
  Q->data[Q->rear] = e; //将元素e赋值给队尾
  Q->rear = (Q->rear + 1) % MAXSIZE; //rear指针向后移一位置，若到最后则转向数组头部
  return OK;
}

出队列操作

循环队列的出队列操作代码如下：

// 若队列不空，则删除Q中队头元素，用e返回其值
Status DeQueue(SqQueue *Q, QElemType *e)
{
  if (Q->front == Q->rear) //队列空的判断
  {return ERROR;}
  *e = Q->data[Q->front]; //将队头元素赋值给e
  Q->front = (Q->(front + 1)) % MAXSIZE;//front指针向后移动一位，若到最后则转向数组头部
  return OK;
}

小结

从这一段讲解，大家应该发现，单是顺序存储，若不是循环队列，算法的时间性能是不高的。

但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。

队列的链式存储结构

简介

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。

实现

链队列结构

链队列的结构为：

//链队列的结构为：
typedef int QElemType; //QElemType类型视情况而定，这里假设为int
typedef struct QNode //结点结构
{
  QElemType data;
  struct QNode *next;
}QNode, *QueuePtr;

typedef struct //队列的链表结构
{
  QueuePtr front, rear; //队头、队尾指针
}LinkQueue;

入队操作

入队操作时，其实就是在链表尾部插入结点

//插入元素e为Q的新的队尾元素
Status EnQueue(LinkQueue *Q, QElemType e)
{
  QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
  if (!s) //存储分配失败
  {exit (OVERFLOW);}
  s->data = e;
  s->next = NULL;
  Q->rear->next = s; //把拥有元素e新结点赋值给原队尾结点的后缀
  Q->rear = s; //把当前的s设置为队尾结点
  return OK;
}

出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需要将rear指向头结点。

//若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
Status DeQueue(LinkQueue *Q, QElemType *e)
{
  QueuePtr p;
  if (Q->front == Q->rear)
  {return ERROR;}
  p = Q->front->next; //将欲删除的队头结点暂时存给p
  *e = p->data; //将欲删除的队头结点的值赋值给e
  Q->front->next = p->next;将原队头结点后继p->next赋值给头结点后继
  if (Q->rear == p) //若队头是队尾，则删除后将rear指向头结点
  {
    Q->rear = Q->front;
  }
  free(p);
  return OK;
}

循环队列和链队列比较

对于循环队列与链队列的比较，可以从两方面来考虑。
从时间上其实它们的基本操作都是常数时间，即都为O(1)，不过：

• 循环队列是事先申请好空间，使用期间不释放。
• 而对于链队列，每次申请和释放结点也会存在一些时间开销。

如果入队出队频繁，则两者还是有细微差异。

对于空间上来说

• 循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。
• 连队咧不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。

所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

小结

栈和队列都是特殊的线性表，只不过对插入和删除操作做了限制。

• 栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
• 队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。但它们也有各自的技巧来解决这个问题。

• 对于栈来说，如果是两个相同类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。
• 对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗。使得本来插入和删除是O(n)的时间复杂度变成了O(1)。

它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同。

串

前言

串(string)是由0个或多个字符组成的有限序列，由名叫字符串(有没有觉得一听到字符串就熟悉多了)。

0个字符的串称为空串(null string)，它的长度为0。

空格串：

是只包含空格的串。主意它和空串的区别，空格串是有内容有长度的，而且可以不止一个空格。

子串和主串：

串中任意个数的连续字符组成的子序列称为该串的子串，相应的，包含子串的串称为主串。
子串在主串中的位置就是子串的第一个字符在主串中的序号。

如”Ray”、”June”可以认为是”RayJune”的子串。

串的比较

串的比较是通过串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。(如，utf-8、ASCII、GBK编码)

串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符集，即串中的元素都是字符。

因此，对于串的基本操作与线性表还是有很大差别的。

• 线性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素
• 但串中更多的是查找子串位置、得到指定子串位置、替换子串等操作

ADT 串(string)

• Data
  • 串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
• Operation
  • StrAssign(T, *chars): 生成一个其值等于字符串常量chars的串T。
  • StrCopy(T, S): 串S存在，由串S赋值得串T。
  • ClearString(S): 串S存在，将串清空。
  • StringEmpty(S): 若串S为空，返回true,否则返回false。
  • StrLength(S): 返回串S的元素个数，即串的长度。
  • StrCompare(S, T): 若S>T, 返回值>0，若S=T，返回0，若S<T，返回值<0.
  • Concat(T, S1, S2): 用T返回由S1和S2连接而成的新串。
  • SubString(Sub, S, pos, len): 串S存在，1<=pos<=StrLength(S),且0<=len<=StrLength(S) - pos + 1，用Sub返回串S的第pos个字符起长度为len的子串。
  • Index(S, T, pos): 串T和S存在，T是非空串，1<=pos<=StrLength(S)。若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，佛祖额返回0.
  • Replace(S, T, V): 串S、T和V存在，T是非空串。用V替换主串S中出现的所有与T相等的不重叠的子串。
  • StrInsert(S, pos, T): 串S和T存在，1<=pos<=StrLength(S) - len + 1。从串S中删除第pos个字符起长度为len的子串。

endADT

串的实现

对于不同的高级语言，对字符串的基本操作会有不同的定义方法，如Python、Javascritp的就非常简单。

不过还好，不同语言除了方法名称外，操作实质都是相类似的。

我们来看一个操作index的实现代码

//T为非空串。若主串S中第pos个字符之后存在与T相等的子串
//则返回第一个这样的子串在S中的位置，否则返回0
int Index(String S, String T, int pos)
{
  int n, m, i;
  String sub;
  if (pos > 0)
  {
    n = StrLength(S); //得到主串S的长度
    m = StrLength(T); //得到子串T的长度
    i = pos;
    while (i <= n - m + 1)
    {
      SubString(sub, S, i, m); //取主串第i个位置，长度与T相等的子串给sub
      if (StrCompare(sub, T) != 0)//如果两串不相等
      {
        i++;
      }
      else //如果两串相等
      {
        return i; //则返回i值
      }
    }
  }
  return 0; //若无子串与T相等，返回0
}

当中用到了StrLength、SubString、StrCompare等基本操作来实现。

串的存储结构

与线性表相同

串的存储结构与线性表相同，分为两种。

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符系列的。

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书中也会定义存储在数组的最后一个下标位置。

但也有些编程语言不想这么赶，觉得存个数字占个空间麻烦。它规定在串值后面加一个不计入串长度的结束标记字符，比如”\0”来表示串值的终结。
这个时候，你要想知道此时的串长度，就需要遍历计算一下才知道了，其实这还是需要占用一个空间，还是挺麻烦的。

出现了问题

刚才说的串的顺序存储方式其实是有问题的，因为字符串的操作，比如两串字符串的连接、新串的插入以及字符串的替换，都有可能使得串序列的长度超过了数组的长度。

于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。

比如在计算机中存在一个自由存储区，叫做”堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理。

串的链式存储结构

串的链式存储结构与线性表是相似的，但由于串结构的特殊性，结构中的每个元素数据是一个字符，如果简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。

因此，一个结点可以存放一个字符，也可以**考虑存放多个字符，最后一个结点若是未被占满时，可以用”#”或其他非串值字符补全。

当然，这里一个结点存多少个字符才合适就变得很重要，这会直接影响者串处理的效率，需要根据实际情况做出选择。

但串的链式存储结构除了在连接串与串操作时有一定方便之外，总的来说不如顺序存储灵活，性能也不如顺序存储结构好。

朴素的模式匹配算法

比如我们在一篇Blog中去找”RayJune”，这就相当于一个大字符串中的定位问题。这种子串的定位操作通常称作串的模式匹配，应该算是串中最重要的操作之一。

简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头作”RayJune”这7个长度的小循环，直到匹配成功或全部遍历完成为止。

前面我们已经用串的其他操作实现了index模式匹配的算法。现在考虑不用串的其他操作，而是只用基本的数组来实现同样的算法。
注意我们假设主串S和要匹配的子串T的长度存在S[0]与T[0]中。

//返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0
//T非空，1<=pos<=StrLength(S)
int Index(String S, String T, int pos)
{
  int i = pos; //i用于主串S中当前位置下标，若pos不为1，则从pos位置开始匹配
  int j = 1; //j用于子串T中当前位置下标值
  while(i <= S[0] && j <= T[0]) 若i小于S且j长度小于T的长度时循环
  {
    if (S[i] == T[j]) //两字母相等则继续
    {
      i++;
      j++;
    }
    else //指针后退重新开始匹配
    {
      i = i - k + 2; //i退回到上次匹配首位的下一位
      j = 1; //j退回到字符串T的首位
    }
  }
  if (j > T[0])
  {
    return i - T[0];
  }
  else
  {
    return 0;
  }
}

这种算法的时间复杂度为O((n - m + 1) * m)。非常慢。

而且在实际应用中，计算机处理的都是二进位的0和1的串，一个字符的ASCII码也可以看成是8位的二进位0/1串，当然，汉字等所有的字符也都可以看成是多个0和1串。
再比如像计算机图形也可以理解为是由许许多多个0和1的串组成。所以在计算机的运算当中，模式匹配操作可说是随处可见的，而刚才的这个算法，显得太低效了。

KMP模式匹配算法

小结

串是一种简单而又重要的数据结构。虽然现在的高级语言都有针对串的函数可以调用。但我们在使用这些函数的时候，同时也应该理解它当中的原理，以便于在碰到复杂的问题时，可以更加灵活的使用。

比如KMP模式匹配算法的学习，就是更有效地去理解index函数当中的实现细节。

树(Tree)

树的定义

前言

树(Tree)是n(n>=0)个结点的有限集。n = 0时称为空树。
在任意一颗非空树中：

• 有且仅有一个特定的称为根(Root)的结点；
• 当n>1时，其余结点可分为m(m > 0)个互不相交的有限集T1、T2、…、T(n)，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

树的诞生

之前我们一直在谈的是一对一的线性结构，可现实中，还有很多一对多的情况需要处理，所以我们需要研究这种一对多的数据结构————树，考虑它的各种特性，来解决我们在编程中遇到的各种问题。

概念解析

对于树的定义还需要强调两点：

1. n>0时根节点是唯一的，不可能存在多个根结点，别和现实中的大树混在一起，数据结构中的树只能有一个根节点。
2. m>0时，子树的个数没有限制，但它们一定是互不相交的。

结点分类

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。

• 度为0的结点称为叶结点或终端结点。
• 读不为0的结点称为分支结点或非终端结点。
  • 除根结点之外，分支结点也称为内部结点。

树的度是树内各结点的度的最大值。

结点间关系

结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲。同一个双亲的孩子之间互称兄弟(Sibling)。

结点的祖先是从根到该结点所经分支上的所有结点。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。

其他概念

结点的层次(Level)从根开始定义起，根为第一层，根的孩子为第二层。

树中结点的最大层次称为树的深度(Depth)或高度。

如果将树中结点的各子树看成是从左至右是有次序的，不能互换的，则称该书为有序数，否则称为无序树。

森林(Forest)是m(m>=0)颗互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

和线性表对比

线性表：

• 第一个数据元素： 无前驱
• 最后一个数据元素： 无后继
• 中间元素： 一个前驱一个后继

树结构：

• 根结点： 无双亲，唯一
• 叶结点：无孩子，可以多个
• 中间结点： 一个双亲多个孩子

树的抽象数据类型

相对于线性结构，树的操作就完全不同了，这里我们给出一些基本和常用操作。

ADT 树(tree)

• Data
  • 树是由一个根结点和若干颗子树构成。树中结点具有相同数据类型及层次关系。
• Operation
  • InitTree(*T): 构造空树T。
  • DestoryTree(*T): 销毁树T。
  • CreateTree(*T, definition): 按definition中给出树的定义来构造树。
  • ClearTree(*T): 若树T存在，则将树T清为空树。
  • TreeEmpty(T): 若T为空树，返回true，否则返回flase。
  • TreeDepth(T): 返回T的深度。
  • Root(T): 返回T的根结点。
  • Value(T, cur_e): cur_e是树T中的一个结点，返回此结点的值。
  • Assign(T, cur_e): 给树T的结点cur_e赋值为value。
  • Parent(T, cur_e): 若cur_e是树T的非根结点，则返回它的双亲，否则返回空。
  • LeftChild(T, cur_e): 若cur_e是树的非叶结点，则返回他的最左孩子，否则返回空。
  • RightSibling(T, cur_e): 若cur_e有右兄弟，则返回它的右兄弟，否则返回空。
  • InsertChild(T, p, i, c): 其中p指向树T的某个结点，i为所指结点p的度加上1，非空树C与T不相交，操作结果为插入C为树T中p指结点的第i颗子树。
  • DeleteChild(T, p, i): 其中p指向树T的某个结点，i为所指结点p的度，操作结果为删除T中p所指结点的第i颗子树。

endADT

树的存储结构

前言

说到存储结构，就会想到我们之前提过的顺序存储和链式存储两种结构。

但是简单的顺序存储无法反应树中的一对多关系。

不过充分利用顺序存储和链式存储结构的特点，完全可以实现堆树的存储结构的表示。

双亲表示法

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。

也就是说，每个结点除了知道自己是谁以外，还知道它的双亲在哪里。

//树的双亲表示法结点结构定义
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型，目前暂定为整型
typedef struct PTNode //结点结构
{
  TElemType data; //结点数据
  int parent; //双亲位置
} PTNode;
typedef struct //树结构
{
  PTNode nodes[MAX_TREE_SIZE]; //结点数组
  int r,n;
} PTree;

有了这样的结构定义，我们就可以来实现双亲表示法了。由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有它双亲的位置。

存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构的运算是否适合、是否方便，时间复杂度好不好等。

孩子表示法

由来

换一种完全不同的考虑方法。由于树中每个结点可能有多颗子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一颗子树的根结点，我们把这种方法叫做多重链表表示法。

方案A

每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数。

这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。

最终方案

仔细想想，我们为了要遍历正棵树，把每个结点放到一个顺序存储的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系。

这就是我们要讲的孩子表示法。把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

为此，设计两种结点结构，一个是孩子链表的孩子结点，由数据域child(用来存储某个结点在表头数组中的下标)和指针域next(用来存储指向某结点的下一个孩子结点的指针)组成。

另一个是表头数组的表头结点。由数据域data(存储某结点的数据信息)和头指针域firstchild(存储该结点的孩子链表的头指针)。

// 树的孩子表示法结构定义
#define MAX_TREE_SIZE 100
typedef struct CTNode //孩子结点
{
  int child;
  struct CTNode *next;
} *ChildPtr;
typedef struct //表头结构
{
  TElemType data;
  ChildPtr firstchild;
} CTBox;
typedef struct //树结构
{
  CTBox nodes[MAX_TREE_SIZE]; //结点数组
  int r,n; //根的位置和结点数
} CTree;

但是这也存在着问题，我们要怎么知道某个结点的双亲是谁呢？比较麻烦，需要整棵树遍历才行，难道就不可以把双亲表示法和孩子表示法综合一下吗？当然是可以的。

我们把这种方法称为双亲孩子表示法。

孩子兄弟表示法

前言

刚才我们分别从双亲的角度和孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又会如何呢？
当然，对于树这样的层级结构来说，只研究结点的兄弟是不行的，我们观察后发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。

因此，我们设置两个指针，分别指向该结点的第一个孩子和次结点的右兄弟。

结构实现

结点由数据域data、指针域firstchild(存储该结点的第一个孩子结点的存储地址)、指针域rightsib(存储该结点的右兄弟结点的存储地址组成。

//树的孩子兄弟表示法结构定义
typedef struct CSNode
{
  TElemType data;
  struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

我们可以看出这种表示法给查找某个结点的某个孩子带来了方便，只需要通过firstchild一直往下找就好了。
当然，如果想要解决快速查找双亲的问题，再加一个parent指针域就好了。

这个表示法的最大好处是它把一颗复杂的树变成了一颗二叉树。

二叉树

二叉树的定义

对于这种在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对与错、正面与反面等，都适合用树状结构来建模，而这种树是一种很特殊的树状结构，叫做二叉树。

二叉树(Binary Tree)是n(n>=0)个结点的有限集合，该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树特点

• 每个结点最多有两棵子树。没有子树或者有一棵子树都是可以的。
• 左子树和右子树是有顺序的，次序不能任意颠倒。就像人是双手、双脚，但显然左手和右手、左脚和幼教是不一样的。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树具有五种计本形态：

1. 空二叉树
2. 只有一个根节点
3. 根节点只有左子树
4. 根节点只有右子树
5. 根节点既有左子树又有右子树

特殊二叉树

斜树

顾名思义，斜树一定要是斜的。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。

满二叉树

即完美二叉树。你懂的

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：

• 叶子只能出现在最下一层。出现在其他层就不可能达成平衡。
• 非叶子结点的度一定是2。否则就是”缺胳膊少腿”了。
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

完全二叉树的特点：

• 叶子结点只能出现在最下两层。
• 最下层的叶子一定集中在左部连续位置。
• 倒数二层，若有叶子结点，一定都在右部连续位置。
• 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
• 同样结点数的二叉树，完全二叉树的深度最小。

二叉树的性质们

在二叉树的第i层上至多有(2的i-1次方)个结点

深度为k的二叉树至多有(2的k次方)-1个结点

对任何一颗二叉树T，如果其终端结点数为n0,度为2的结点树为n2，则n0 = n2 + 1

终端结点数就是叶子结点数，而一颗二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n1为度是1的结点数。则树T的结点总数n = n0 + n1 + n2。而n = n1 + n2 * 2 + 1。所以n0 = n2 + 1。

具有n个结点的完全二叉树的深度为|log2n|+1 (|x|表示不大于x的最大整数)。

如果对一颗有n个结点的完全二叉树(其深度为|log2n| + 1)的结点按层序编号(从第1层到第|log2n|+1层，每层从左向右)，对任一结点i(1<=n)有：

1. 如果i=1,则结点i是二叉树的跟，无双亲；如果i>1则其双亲是结点[i/2]。
2. 如果2i>n，则结点i无做孩子(结点i为叶子结点)；否则其左孩子是结点2i。
3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1.

二叉树的存储结构

二叉树的顺序存储结构

前面我们已经谈到了树的存储结构，并且谈到顺序存储对树这种一对多的关系结构实现起来是比较困难的。
但是，二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构也可以实现。

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是**数组的下表要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

即顺序存储结构一般只用于完全二叉树。

二叉链表

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

由数据域data和lchild和rchild两个指针域组成。

以下是我们的二叉链表的结点结构定义：

//二叉树的二叉链表结点结构定义
typedef struct BitNode //结点结构
{
  TElemType data; //结点数据
  struct BitNode *lchild, *rchild; //左右孩子指针
} BitNode, *BitTree;

就如同树的存储结构中讨论的一样，如果有需要，还可以再增加一个指向其双亲的指针域，那样就称为三叉链表。

遍历二叉树

前言

二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

这里有两个关键词：访问和次序。

二叉树遍历方法

前序遍历

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

中序遍历

规则是若树为空，则空操作返回，否则从根节点开始(注意不是先访问根结点)，中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。

后序遍历

规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。

层序遍历

规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在统一曾中，按从左到右的顺序对结点逐个访问。

遍历是为了干什么

我们用图形的方式来表现树的结构，应该说是非常直观和容易理解，但对于计算机来说，它只有循环、判断等方式来处理，也就是说，它只会处理线性序列。

而我们刚才提到的四种遍历方法，其实都是在把树中的结点编程某种意义的线性序列，这就给程序的是先带来了好处。

另外不同的遍历提供了对结点依次处理的不同方式，可以在遍历过程中对结点进行各种处理。

前序遍历算法

二叉树的定义是用递归的方式，所以，实现遍历算法也可以采用递归，而且及其简单明了。

//二叉树的前序遍历递归算法
void PreOrderTraverse(BitTree T)
{
  if (T == NULL)
  {return ;}
  printf("%C\n", T->data); //显示结点数据，可以更改为其他的对结点的操作
  PreOrderTraverse(T->lchild); //再先序遍历左子树
  PreOrderTraverse(T->rchild); //最后先序遍历右子树
}

中序遍历算法

二叉树的中序遍历算法和前序遍历算法仅仅知识代码的顺序上的差异。

//二叉树的中序遍历递归算法
void PreOrderTraverse(BitTree T)
{
  if (T == NULL)
  {return ;}
    PreOrderTraverse(T->lchild); //中序遍历左子树
  printf("%C\n", T->data); //显示结点数据，可以更改为其他的对结点的操作
  PreOrderTraverse(T->rchild); //最后中序遍历右子树
}

后序遍历算法

//二叉树的后序遍历递归算法
void PreOrderTraverse(BitTree T)
{
  if (T == NULL)
  {return ;}
  PreOrderTraverse(T->lchild); //先后序遍历左子树
    PreOrderTraverse(T->rchild); //再后序遍历右子树
  printf("%C\n", T->data); //显示结点数据，可以更改为其他的对结点的操作
}

推导遍历结果

**已知前序和后续遍历，是不能确定一颗二叉树的。

线索二叉树

线索二叉树原理

我们把这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树（Threaded Binary Tree）。

其实线索二叉树，等于是把一颗二叉树转变成了一个双向链表，这样对我们的插入删除结点、查找某个结点都带来了方便。所以我们对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化。

彻底解决问题

但问题还没有彻底解决。我们如何知道某一个结点的lchild是指向它的左孩子还是指向前驱？

显然我们在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要一个区分标志的。
因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag知识存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。

线索二叉树结构实现

//二叉树的二叉线索存储结构定义
typedef enum {Link, Thread} PointerTag; //Link == 0表示指向左右孩子指针，Thread == 1表示指向前驱或后继的线索
typedef struct BiThrNode //二叉线索存储结点结构
{
  TElemType data; //结点数据
  struct BiThrNode *lchild, *rchild; //左右孩子指针
  PointerTag LTag;
  PointerTag Rtag; //左右标志
} BiThrNode, *BithrTree;

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，所以线索化的过程就是在遍历的过程中修改空指针的过程。

中序遍历线索化实现

中序遍历线索化的递归函数代码如下：

BiThrTree pre; //全局变量，始终指向刚刚访问过的结点
//中序遍历进行中序线索化
void InThreading(BiThrTree p)
{
  if (p)
  {
    InThreading(p->lchild); //递归左子树线索化
    if (!(p->child) //没有左孩子
    {
      p->LTag = Thread; //前驱线索
      p->lchild = pre; //做孩子指针指向前驱结点
    }
    if (!(pre->rchild)) //前驱没有右孩子
    {
      pre->Rtag = Thread; //后继线索
      pre->rchild = p; //前驱右孩子指针指向后继
    }
    pre = p; //保持pre指向p的前驱
    InThreading(p->rchild); //递归右子树线索化
  }
}

花式遍历

有了线索二叉树后，我们对它进行遍历时发现，其实就等于是操作一个双向链表结构。

和双向链表结构一样，在二叉树线索链表上增加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。
反之，另二叉树的中序序列中的第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点。

这样定义的好处是我们**既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。

//花式遍历
//T指向头结点，头结点在左链lchild指向根结点，头结点右链指向中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T
Status InOrderTraverse_Thr(BiThrTree T)
{
  BiThrTree p;
  p = T->lchild; //p指向根结点
  while (p != T) //空树或遍历结束时，P == T
  {
    while (p->LTag == Link) // 当LTag == 0时循环到中序序列第一个结点
    {
      p = p->lchild;
    }
    printf("%c\t", p->data); //显示结点数据，可以更改为对其他结点操作
    while (p->RTag == Thread && p->rchild != T)
    {
      p = p->rchild;
      printf("%c", p->data);
    }
    p = p->rchild; //p进入它的右子树根
  }
  return OK;
}

从这段代码可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。

小结

由于线索二叉树充分利用了空指针域的空间(这等于节省了时间)，又保证了创建时的一次遍历就可以终生受用前驱后继的信息(这意味着节省了时间)。

所以在实际问题中，如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。

树、森林与二叉树的转换

树转换为二叉树

将树转换为二叉树的步骤如下：

1. 加线。在所有兄弟结点之间加一条连线。
2. 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3. 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的做孩子，兄弟转换过来的孩子是结点的右孩子。

森林转换为二叉树

森林是由若干颗树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤如下：

1. 把每棵树转换为二叉树。
2. 第一颗二叉树不动，从第二棵二叉树开始，依次把后一颗二叉树的根结点作为前一颗二叉树的根节点的右孩子，用线连起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，也就是反过来做而已。步骤如下：

1. 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子结点…。反正就是左孩子的n个右孩子结点都作为次结点的孩子。将该结点与这些右孩子结点用线连接起来。
2. 去线。删除原二叉树中所有结点与其右孩子结点的连线。
3. 层次调整，使之结构层次分明。

二叉树转换为森林

判断一棵二叉树能够转换成一棵树还是森林，标准很简单：

只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。

那么二叉树如果转换成森林，步骤如下：

1. 从根节点开始，若右孩子存在，则把右孩子结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除…，知道所有的右孩子连线都删除为止，得到分离的二叉树。
2. 再将每棵分离后的二叉树转换为树即可。

树与森林的遍历

树的遍历分为两种方式：

1. 先根遍历树，即先访问树的根节点，然后一次先根遍历根的每颗子树。
2. 另一种是后根遍历，即先一次后根遍历每颗子树，然后再访问根结点。

森林的遍历也分为两种方式：

1. 前序遍历：先访问森林中第一棵树的根节点，然后再依次先根遍历根的每颗子树，再依次用同样方式遍历除去第一棵树的剩余树构成的森林。
2. 后序遍历：先访问森林中的第一棵树，后根遍历的方式遍历每棵子树，然后再访问根结点，再依次同样方式遍历除去第一棵树的剩余树构成的森林。

小结

森林的前序遍历、后序遍历和二叉树的前序遍历、后序遍历结果相同。

这也就告诉我们，当以二叉链表作为树的存储结构时，树的先根遍历和后根遍历完全可以借用二叉树的前序遍历和中序遍历的算法来实现。

这其实也就证实，我们找到了对树和森林这种复杂问题的简单解决办法。

赫夫曼树及其应用

前言

文本压缩是一个非常重要的技术。因为它除了可以减少文档在磁盘上的空间外，还有最重要的一点，就是我们可以在网路上以压缩的形式传输大量数据，使得保存和传递都更加高效。

那么压缩而不出错是怎么做到的呢？
简单说，就是把我们要压缩的文本进行重新编码，以减少不必要的空间。尽管现在最新技术在编码上已经很好很强大，但这一切都来自于曾经的技术积累。

而赫夫曼编码，则是一种最基本的压缩编码方法。

赫夫曼树定义与原理

定义

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称作路径长度。
树的路径长度就是从树根到每一结点的路径长度之和。

如果考虑到带权的结点，结点的带权路径长度为树中所有结点的带全路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。

其中带权路径长度WPL最小的二叉树称作赫夫曼树。也有不少书中也成为最优二叉树。

原理

我们可以构造赫夫曼树的赫夫曼算法描述

1. 根据给定的n个权值{w1, w2, …, wn}构成n颗二叉树的集合F = {T1, T2, … , Tn}，其中每颗二叉树Ti中只有一个带权为wi根结点，其左右子树均为空。
2. 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
4. 重复2和3步骤，知道F只含有一颗树为止。这棵树便是赫夫曼树。

赫夫曼编码(Huffman)

赫夫曼研究这种最优树的目的不是为了我们可以转化一下成绩。他的更大目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。

一般地，设需要编码的字符集为{d1,d2,…,dn}，各个字符在电文中出现的次数或频率集合为{W1,w2,…,wn}，以d1,d2,…,dn作为叶子结点，以w1,w2,…wn作为相应叶子结点的权值来构造一颗赫夫曼树。规定赫夫曼树的左分支代表0，右分支代表1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码。

小结

树的复杂性和变化丰富度是前面的线性表所不可比拟的。

我们首先提到了树的定义，讲到了递归在树定义中的应用。提到了如子树、结点、度、叶子、分支结点、双亲、孩子、层次、深度、森林等诸多概念，这些概念需要在理解中记忆。

接着提到了树的存储结构，讲了双亲表示法、孩子表示法、孩子兄弟表示法等不同的存储结构。

并由孩子兄弟表示法引出了我们这章中最重要的一种树————二叉树。

二叉树每个结点最多有两颗子树，有左右之分。提到了斜树，满二叉树、完全二叉树等特殊二叉树的概念。
我们接着谈到它的各种性质，这些性质给我们研究二叉树带来了方便。

二叉树的存储结构由于其特殊性使得既可以用顺序存储结构又可以用链式存储结构表示。

遍历是二叉树最重要的一门学问，前序、中序、后续以及层序遍历都是需要熟练掌握的知识。要让自己学会用计算机的运行思维去模拟递归的实现，可以加深我们对递归的理解。
不过，并非二叉树遍历就一定要用到递归，只不过递归的实现比较优雅而已。这点需要明确。

二叉树的建立自然也是可以通过递归来实现。

研究中发现，二叉链表有很多浪费的空指针可以引用，查找某个结点的前驱和后继为什么非要每次遍历才可以得到，这就引出了如何构造一棵线索二叉树的问题。线索二叉树给二叉树的结点查找和遍历带来了高效率。

树、森林看似复杂，其实它们都可以转化为简单的二叉树来处理，我们提供了树、森林与二叉树的互相转换的办法，这样就使得面对树、森林这样的数据结构时，编码实现成为了可能。

最后，我们提到了关于二叉树的一个应用，赫夫曼树和赫夫曼编码，对于带权路径的二叉树做了详尽地讲述，让你初步理解数据压缩的原理，并明白其是如何做到无损编码和无错解码的。

图(Graph)

前言

图(Graph)是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：

G(V, E),其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

对于图的定义，我们需要明确几个注意的地方。

• 线性表中我们把数据叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点(Vertex)。
• 线性表中可以没有元素，称为空表。树中可以没有结点，叫做空树。但是图不允许没有结点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

各种图定义

无向图：

若顶点vi到vj之间的边没有方向，则称这条边为无向边(Edge)，用吴旭偶对(vi,vj)来表示。
如果图中任意两个顶点之间的边都是无向边，则称该图为无向图(Undirected graphs)。

有向图与无向图相反。

但是要注意，无向边用小括号”()”表示，而有向边则是用尖括号”<>”表示。

在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

在无向图中，如果任意两个顶点之间都存在边，则称该图为完全无向图。

与之对应，在有向图中，如果任意两个顶点都存在方向互为相反的两条弧，则称该图为有向完全图。

有很少条边或弧的图称为稀疏图，反之称为稠密图。

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权(Weight)。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网(Network)。

第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复的路径称为简单路径。
除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或者简单环。

如果对于图中任意两个顶点vi、vj属于E，vi和vj都是连通的，则称G是连通图(Connected Graph)。

在有向图G中，如果对于每一处vi,vj属于V，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0，其余顶点入读为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

图的抽象数据类型

图作为一种数据结构，它的抽象数据类型带有自己的特点，正因为它的复杂，运用广泛，使得不同的应用需要不同的运算集合，构成不同的抽象数据操作。我们这里就来看看图的基本操作。

ADT 图(Graph)

• Data
  • 顶点的有穷非空集合和边的集合
• Operation
  • CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G
  • DestroyGraph(*G): 图G存在则销毁
  • LocateVex(G, u): 若图G中存在顶点u，则返回图中的位置
  • GetVex(G, v): 返回图G中顶点v的值
  • PutVex(G, v, value): 将图G中顶点赋值value
  • FirstAdjVex(G, *v): 返回顶点v的一个邻接结点，若顶点在G中无邻接顶点返回空
  • NextAdjVex(G, v, *w): 返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最后一个邻接点，则返回”空”
  • InsertVex(*G, v): 在图G中增添新结点v
  • DeleteVex(*G, v): 删除图G中顶点v及其相关的弧
  • InsertArc(*G, v, w): 在图G中增添弧<v, w>，若G是无向图，还需要增添对称弧<w, v>。
  • DeleteArc(*G, v, w): 在图G中删除弧<v, w>,若G是无向图，则还删除对称弧<w, v>
  • DFSTraverse(G): 对图G中进行深度优先遍历，在遍历过程中对每个顶点调用。
  • HFSTraverse(G): 对图G中进行广度优先遍历，在遍历过程中对每个顶点调用。

endADT

图的存储结构

前言

图的存储结构想较线性表与树来讲就更加复杂了。我们口头上说的”顶点的位置”或”邻接点的位置”只是一个相对的概念。
其实从图的概念逻辑结构定义来看，图上任何一个顶点都可以被看成是第一个顶点，任何一个顶点的临界点之间也不存在次序关系。

邻接矩阵

定义

考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。
顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一纬搞不定，那就考虑用一个二维数组来存储。于是我们的邻接矩阵的反感就诞生了。

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

邻接矩阵存储结构

typedef char VertexType; //顶点类型由用户定义
typedef int EdgeType; //边上的权值类型由用户定义
#define MAXVEX 100 //最大定点数，应由用户定义
#define INFINITY 65535 //用65535来代表无穷大
typedef struct
{
  VertexType vexs[MAXVEX]; //顶点表
  EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边表
  int numVertexes, numEdges; //图中当前的定点数和边数
} MGraph;

有了这个结构定义，我们构造一个图，其实就是给顶点表和边表输入数据的过程。我们来看看无向网图的创建代码。

无向网图创建

//建立无向网图的邻接矩阵表示
void CreateMGraph (MGraph *G)
{
  int i,j,k,w;
  printf("请输入顶点数和边数：\n");
  scanf("%d,%d", &G->numVertexes, &G->numEdges); //输入顶点数和边数
  for (i = 0; i < G->numVertexes; i++) //读入顶点信息，建立顶点表
  {
    scanf(&G->vexs[i]);
  }
  for (i = 0; i < G->numVertexes; i++)
  {
    for (j = 0; j < G->numVertexes; j++)
    {
      G->arc[i][j] = INFINITY; //邻接矩阵初始化
    }
  }
  for (k = 0; k < G->numEdges; k++) //读入numEdges条边，建立邻接矩阵
  {
    printf("输入边(vi, vj)上的下标i，下标j和权w：\n")
    scanf("%d, %d, %d", &i, &j, &w);
    G->arc[i][j] = w;
    G->arc[j][i] = G->arc[i][j];
  }
}

从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n + nn + e)，其中对邻接矩阵初始化耗费了O(nn)的时间。

邻接表

由来

邻接矩阵是一种不错的图存储结构，但是我们也发现，对于边树相对顶点较少的图，这种结构是存在堆存储空间的极大浪费的。

因此我们考虑另外一种存储结构方式。会议我们在线性表时谈到，顺序存储结构就存在预先分配内存可能造成存储空间浪费的问题，于是引出了链式存储的结构。同样的，我们也可以考虑堆边或弧使用链式存储的方式来避免空间浪费的问题。

再回忆我们在树中谈存储结构时，讲到了一种孩子表示法，将结点存入数组，并对结点的孩子进行链式存储，不管有多少孩子也不会存在空间浪费问题。
这个思路同样适用于图的存储。我们把这种数组与链表相结合的存储方法称为邻接表(Adjacency List)。

处理办法

邻接表的处理办法是这样：

1. 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易的读取顶点信息**，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个临界点的指针，以便于查找该顶点的边信息。
2. 图中每个顶点V1的所有邻接点构成一个线性表，由于临界点的个数不定，所以用单链表存储，无向图称为顶点v1的边表，有向图则称为顶点v1作为弧尾的出边表。

结点定义

下面是关于结点定义的实现

typedef char VertexType; // 顶点类型由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义

typedef struct EdgeNode //边表结点
{
  int adjvex; //邻接点域，存储该顶点对应的下表
  EdgeType weight; //用于存储权值，对于非网图可以不需要
  struct EdgeNode *next; //链域， 指向下一个邻接点
} EdgeNode;

typedef struct VertexNode //邻接表结点
{
  VertexType data; //顶点域，存储顶点信息
  EdgeNode *firstedge; //边表头指针
} VertexNode, AdjList[MAXSIZE];

typedef struct
{
  AdjList adjList;
  int numVertexes, numEdges; //图中当前顶点数和边数
} GraphAdjList;

邻接表的创建

对于邻接表的创建，也就是顺理成章之事。无向图的邻接表创建代码如下

//建立图的邻接表结构
void CreateALGraph(GraphAdjList *G)
{
  int i, j, k;
  EdgeNode *e;
  printf("输入顶点数和边数：/n");
  scanf("%d, %d\n", &G->numVertexes, &G->numEdges); //输入定点数和边数
  for (i = 0; i < G->numVertexes; i++)
  {
    scanf(&G->adjList[i].data);
    G->adjList[i].firstedge == NULL; //将边表置为空表
  }
  for (k = 0; k < G->numEdges; k++)
  {
    printf("请输入边(vi, vj)上的顶点序号：\n");
    scanf("%d,%d", &i, &j); //输入边(vi， vj)上的顶点序号
    e = (EdgeNode *)malloc(sizeof(EdgeNode)); //向内存中申请空间，生成边表结点
    e->adjvex = j; //邻接序号为j
    e->next = G->adjList[i].firstedge; //将e指针指向当前顶点指向的结点
    G->adjList[i].firstedge = e; //将当前顶点的指针指向a
    e = (EdgeNode *)malloc(sizeof(EdgeNode)); //向内存中申请空间，生成边表结点
    e->adjvex = i; //邻接序号为i
    e->next = G->adjList[j].firstedge; //将e指针指向当前结点指向的结点
    G->adjList[j].firstedge = e; //将当前顶点的指针指向e
  }
}

对于无向图，一条边对应都是两个顶点，所以在循环中，一次就针对i和j分别进行了插入。本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n + e).

十字链表

对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解出度就必须要遍历整个图才知道，反之，逆邻接表解决了入读却不了解出度的情况。

而我们的办法就是把它们整合在一起。这就是————十字链表(Orthogonal List)。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。

而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

邻接多重表

十字链表是针对有向图做的优化。因此，我们也仿照十字链表的方式，对边表结点的结构进行一些改造。

邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

这样对边的操作就方便多了。

边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weight)组成。

显然边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边一次进行处理的操作，而不适合对顶点相关的操作。

图的遍历

定义

图的遍历是和树的遍历类似，我们希望从图中某一个顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)。

图比起树来就复杂多了，因为它的任一个顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点却还没有遍历到的情况。因此我们需要在遍历过程中把访问过的顶点打上标记，以避免访问多次。

具体办法是设置一个访问数组visited[n],n是图中顶点的个数，初值为0，访问过后设置为1。

深度优先遍历(DFS)

原理

深度优先遍历(Depth_First_Search)，也有称为深度优先搜索，简称为DFS。

它从图中某个顶点v出发，访问次顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。

事实上，我们这里讲到的是连通图，对于非连通图，只需要对它的连通分量分别进行深度优先遍历。
即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到位置。

邻接矩阵方式

如果我们用的是邻接矩阵的方式，则代码如下：

Boolean visited[MAX] //访问标志的数组
// 邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i)
{
  int j;
  visited[i] = TRUE;
  printf("%c", G.vex[i]); //打印顶点
  for (j = 0; j < G.numVertexes; j++)
  {
    if (G.arc[i][j] == 1 && !visited[j])
    {
      DFS(G, j); //对未访问到的邻接结点递归调用
    }
  }
}
//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
  int i;
  for (i = 0; i < G.numVertexes; i++)
  {
    visited[i] = FALSE; //初始所有顶点
  }
  for (i = 0; i < G.numVertexes; i++)
  {
    if (!visited[i])
    {
      DFS(G, i);
    } //对未访问到的顶点调用DFS，若是连通图，只会执行一次
  }
}

邻接表结构

如果图结构是邻接表结构，其DFSTraverse函数代码几乎是相同的，知识在递归函数中因为将数组换成了链表而有所不同

//邻接表的深度优先递归算法
void DFS(GraphAdjList GL, int i)
{
  EdgeNode *p;
  visited[i] = TRUE;
  printf("%c", GL->addList[i].data); //打印顶点，也可以是其他操作
  p = GL->adjList[i].firstedge;
  while (p)
  {
    if (!visited[p->adjvex])
    {
      DFS(GL, p->adjvex); //对未访问到的邻接结点递归调用
    }
    p = p->next;
  }
}
//邻接表的深度遍历操作
void DFSTraverse(GraphAdjList GL)
{
  int i;
  for (i = 0; i < GL->numVertexes; i++)
  {
    visited[i] = FALSE; //初始所有顶点状态都是未访问状态
  }
  for (i = 0; i < GL->numVertexes; i++)
  {
    if (!visited[i])
    {
      DFS(GL, i);
    } //对未访问到的顶点调用DFS，若是连通图，只会执行一次
  }
}

小结

对比两个不同存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找每个顶点的临界点需要访问矩阵中的所有元素，因此都需要O(n*n)的时间。

而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

广度优先遍历(BFS)

最小生成树

我们把构造联通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)。

简单点说有几个城市你要设计一个路线，这个路线能走完所有的这几个城市，而且路程最短，这个路线就是最小生成树的含义。

最短路径

定义

在网图和非网图中，最短路径的含义是不同的。

• 由于非网图它没有边上的权值，所谓的最短路径就是指两顶点之间经过的边数最少的路径；
• 对于网图来说，最短路径是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

Dijkstra算法

它不是一下子就求出了v0到vn的最短路径，而是一步步求出它们之间顶点的最短路径，过程都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径。

#define MAXVEX 9
#define INFINITY 65535
typedef int Pathmatrix[MAXVEX]; //用于存储最短路径下标的数组
typedef int ShortPathTable[MAXVEX]; //用于存储到各点最短距离的权值和
//Dijstra算法，求有向网G的v0顶点到其余顶点v最短路径P[v]及带权长度D[V]
//P[v]的数值为前驱顶点下标，D[v]表示v0到v的最短路径长度和
void ShortestPath_Dijkstra(MGraph G, int v0, Pathmatrix *p)
{
  int v,w,k,min;
  int final[MAXVEX]; //final[w] = 1表示求得顶点v0至vw的最短路径
  for (v = 0; v < G.numVertexes; v++) //初始化数据
  {
    final[v] = 0; //全部顶点初始化为未知最短路径状态
    (*D)[v] = G.matrix[v0][v]; //将与v0有连线的顶点加上权值
    (*P)[v] = 0; //初始化路径数组P为0
  }
  (*D)[v0] = 0; //v0到v0路径为0
  final[v0] = 1; //v0到v0不需要求路径
  //开始主循环，每次求得v0到某个v顶点的最短路径
  for (w = 0; w < G.numVertexes; w++)
  {
    if (!final[w] && (*D)[w] < min)
    {
      k = w;
      min = (*D)[w]; //w顶点距离v0顶点更近
    }
  }
  final[k] = 1; //将目前找到的最近的顶点置为1
  for (w = 0; w < G.numVertexes; w++) //修正当前最短路径及距离
  {
    //如果经过v顶点的路径比现在这条路径的长度短的话
    if (!final[w] && (min + G.matrix[k][w] < (*D)[w]))
    {
      //说明找到了更短的路径，修改D[w]和P[w]
      (*D)[w] = min + G.matrix[k][w]; //修改当前路径长度
      (*P)[w] = k;
    }
  }
}

我们容易看出此算法时间复杂度为O(n*n)

可如果我们还需要知道如v3到v5，v1到v7这样任一顶点到其余所有顶点的最短路径怎么办呢？此时简单的办法就是堆每个顶点当作源点运行一次Dijkstra算法，等于在原有算法的基础上，再来一次循环，此时整个算法的时间复杂度就成了O(nnn)。

Floyd算法

对比Dijstra算法，另一个求最短路径的算法就是佛罗伊德(Floyd)算法，虽然它求所有顶点到所有顶点的时间复杂度也是O(nnn)。但其算法非常简介优雅，能让人感觉到智慧的无线魅力。

拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的有限关系，这样的有向图为顶点表示活动的图，我们称为AOV网(Activity On Vertex Network)。(不存在回路)

设G = (V, E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必须在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

查找

定义

对于那些可以识别多个数据元素(或记录)的关键词，我们称为次关键字(Secondary Key)。
次关键字也可以理解为**不是唯一表示一个数据元素(或记录)的关键字，它对应的数据项就是次关键码。

动态查找表(Dynamic Search Table): 在查找过程中同时插入查找表中不存在数据元素，或者从查找表中删除已经存在的某个数据元素。

为了提高查找的效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。

顺序表查找

定义

顺序查找(Sequential Search)又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个(或最后一个)记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个(或第一个)记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

算法实现

//顺序查找的算法实现如下
int Sequential_Search(int *a, int n, in key)
{
  int i;
  for (i = 1; i <= n; i++)
  {
    if (a[i] = key)
    {return i;}
  }
  return 0;
}

这段代码很简单，就是在数组a中查看有没有关键字(key)，当你需要查找复杂表结构的记录时，只需要把数组a与关键字key定义成你需要的表结构和数据类型即可。

顺序表查找优化

到这里并非足够完美，因为每次循环时都需要对i判断是否越界。

事实上，还有更好一点的办法：设置一个哨兵，可以解决不需要每次让i与n作比较。

// 有哨兵的顺序查找
int Sequential_Search2(int *a, int n, int key)
{
  int i;
  a[0] = key; //设置a[0]为关键字值，我们称之为"哨兵"
  i = n; //循环从数组尾部开始
  while (a[i] != key)
  {
    i--;
  }
  return i; //返回0则说明查找失败
}

这种在查找方向的劲头放置”哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧，看似与原先差别不大，但是在总数据较多时，效率提高很大，是非常好的编码技巧。
当然，”哨兵”也不一定就一定要在数组开始，也可以在末端。

时间复杂度为O(n)。

小结

很显然，顺序查找技术是有很大缺点的，n很大时，查找效率极为低下，不过优点是这个算法非常简单，对静态查找表的记录没有任何要求，在一些小型数据的查找时，是可以适用的。

另外，也正由于查找概率的不同，我们完全可以将容易查找到的记录放在前面，而不常用的记录放置在后面，效率就可以有大幅提高。

有序表查找

前言

我们如果仅仅是把书整理在书架上，要找到一本书还是比较困难的，也就是刚才讲的需要逐个顺序查找。但如果我们在整理书架时，将图书按照书名的拼音排序放置，那么要找到某一本书就相对容易了。
说白了，就是对图书做了有序排列，一个线性表有序时，对于查找总是很有帮助的。

折半查找

定义

折半查找(Binary Search)技术，又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序)，线性表必须采用顺序存储。

折半查找的基本思想是：

在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；反之亦然。
不断重复上述过程，直到查找成功，或所有查找区域没有记录，查找失败为止。

实现

//折半查找
int Binary_Search(int *a, int n, in key)
{
  int low, high, mid;
  low = 1; //定义最低下标为首位
  high = n; //定义最高下标为末位
  while (low <= high)
  {
    mid = (low + high) / 2; //折半
    if (key < a[mid])
    {
      high = mid - 1; //最高位置下标调整到比中位下表大一
    }
    else if (key > a[mid])
    {
      low = mid + 1;
    }
    else
    {return mid;} //若相等则说明mid为要查找的位置
  }
}

优缺点

我们折半算法的时间复杂度为O(logn)，它显然远远好于顺序查找的O(n)。

不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。
但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不晓得工作量，那就不建议使用。

插值查找

插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的插找方法，其核心在于插值的计算公式。

它的重点在于改变了mid的计算方式
即将

mid = (low + high) / 2; //折半

改为了

mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); //插值

应该说，从时间复杂度来看，它也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。

斐波那契查找

实现

//斐波那契查找
int Fibonacci_Search(int *a, int n, int key)
{
  int low, high, mid, i, k;
  low = 1; //定义最低下标为记录首位
  high = n; //定义最高下标为记录末位
  k = 0;
  while (n > F[k] - 1) //计算n位于斐波那契数列的位置
  {
    k++;
  }
  for (i = n; i < F[k] - 1; i++) //将不满的数值补全
  {
    a[i] = a[n];
  }
  while (low <= high)
  {
    mid = low + F[k - 1] - 1; //计算当前分割的下标
    if (key < a[mid]) //若查找记录小于当前分割记录
    {
      high = mid - 1;  //最高下标调整到分割下标mid - 1处
      k = k - 1;
    }
    else if (kye > a[mid])
    {
      low = mid + 1;
      k = k - 2;    //斐波那契树立下标减两位
    }
    else
    {
      if (mid <= n)
      {return mid;}
      else
      {return n;} //若id > n说明是补全数值，返回
    }
  }
  return 0;
}

核心

斐波那契查找算法的核心在于：

1. 当key = a[mid]时，查找就成功；
2. 当key < a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k - 1] - 1个。
3. 当key > a[mid]时，新范围是第mid + 1个到第high个，此时范围个数为F[k - 2] - 1个。

即『黄金比例查找法』

小结

尽管斐波那契查找的时间也为O(logn)，但就平均性能来说，斐波那契查找要优于折半查找。

可惜如果结果是最坏情况，比如这里key = 1，那么始终都处于左侧长半区查找，则查找效率要低于折半查找。

还有比较关键的一点，折半查找是进行假发与出发运算(mid = (low + high) / 2)，插值查找是进行复杂的四则运算(mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]))，而斐波那契查找只是最简单的加减法运算(mid = low + F[k - 1] - 1)，在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。

应该说，三种有序表的查找本质上是分割点的选择不同，各有优劣，实际开发时可根据数据的特点综合考虑再做出选择。

线性索引查找

前言

前面几种比较高效的查找方法都是基于有序的基础之上的，但事实上，很多数据集可能增长非常快。

如twitter、微博等

那么对于这样的查找表，我们如何能够快速查找到需要的数据呢？方法就是————索引。

数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程，一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。

索引技术是组织大型数据库以及磁盘文件的一种重要技术。

索引按照结构可以分为线性索引、树形索引和多级索引。我们这里就只介绍线性索引技术。所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。我们重点介绍以下三中线性索引。

稠密索引

稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项。

对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列。

但是如果数据集非常大，比如上亿，那也就意味着索引也得同样的数据集长度规模，对于内存有限的计算机来说，可能就需要反复去访问磁盘，查找性能反而大大下降了。

分块索引

前言

稠密索引因为索引项与数据集的记录个数相同，所以空间代价很大。为了减少索引项的个数，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项，从而减少索引项的个数。

分块有序，是把数据集的记录分成了若干块，并且这些块需要满足两个条件：

• 块内无序：即每一块内的的记录不要求有序。当然，如果能够让快内有序则对查找来说更理想，不过这就要付出大量时间和空间的代价，因此我们不要求快内有序。
• 块间有序：例如，要求第二块所有记录的关键字均要大雨第一块中所有记录的关键字，第三块的所有记录的关键字均要大于第二块所有记录的关键字。因为**只有块间有序，才有可能在查找时带来效率。

索引项

对于分块有序的数据集合，将每块对应一个索引项，这种索引方法叫做分块索引。

我们定义的分块索引的索引项结构分为三个数据项：

• 最大关键码，它存储每一块中的最大关键字，这样的好处就是使得它之后的下一快中的最小关键字也能比这一块的最大的关键字要大；
• 存储了块中的记录个数，以便于循环时使用；
• 用于指向块首数据元素的指针，便于开始对这一块中记录进行遍历。

查找

在分块索引表中查找，就是分两步进行：

1. 在分块索引表中查找要查关键字所在的块。由于分块索引表是块间有序的，因此很容易利用折半、插值等算法得到结果。
2. 根据块首指针找到相应的块，并在块中顺序查找关键码。因为块中可以是无序的，因此只能顺序查找。

小结

分块索引的时间复杂度为O(根号n+1)。可见，分块索引的效率比顺序查找的O(n)是高了不少，不过显然它与折半查找的O(logn)相比还有不小的差距。
因此在确定所在块的过程中，由于块间有序，还可以应用折半、插值等手段来提高效率。

总的来说，分块索引在兼顾了对细分块不需要有序的情况下，大大增加了整体查找的速度，所以普遍被用于数据库查找等技术的应用当中。

倒排索引

倒排索引源于实际应用中需要根据属性(或字段、次关键码)的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。
由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。

倒排索引的有点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。
但它的缺点是这个记录好不是定长的。

二叉排序树

前言

有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢？

二叉排序树(Binary Sort Tree)，又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结构的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树。

构造一棵二叉排序树的目的，其实并不是为了排序，而是为了提高查找和插入删除关键字的速度。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。

实现

二叉树的结构

首先我们提供一个二叉树的结构

//二叉树的二叉链表结点结构定义
typedef struct BitNode //结点结构
{
  int data; //结点数据
  struct BitNode *lchild, *rchild; //左右孩子指针
} BitNode, *BitTree;

二叉排序树的查找

//递归查找二叉排序树T中是否存在key
//指针f指向T的双亲，其初始调用值为NULL
//若查找成功，则指针p指向该数据元素结点，并返回TRUE
//否则指针p指向查找路径上访问的最后一个结点并返回FALSE
Status SearchBST(BitTree T, int key, BitTree f, BitTree *p)
{
  if (!T) //查找不成功
  {
    *p = f;
    return FALSE;
  }
  else if (key == T->data) //查找成功
  {
    *p = T;
    return TRUE;
  }
  else if (key < T->data)
  {
    return SearchBST(T->lchild, key, T, p);
  }
  else
  {
    return SearchBST(T->rchild, key, T, p);
  }
}

二叉排序树的插入

有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已。

//当二叉排序树T中不存在关键字等于key的数据元素时
//插入key并返回TRUE，否则返回FALSE
Status InsertBST(BiTree *T, int key)
{
  BitTree p, s;
  if (!SearchBST(*T, key, NULL, &p)) //查找不成功
  {
    s = (BitTree)malloc(sizeof(BitNode));
    s->data = key;
    s->lchild = s->rchild = NULL;
    if (!p)
    {
      *T = s; //插入s为新的根节点
    }
    else if (key < p->data)
    {
      p->lchild = s; //插入s为左孩子
    }
    else
    {
      p->rchild = s; //插入s为右孩子
    }
    return TRUE;
  }
  else
  {return FALSE}; //树中已经有关键字相同的结点
}

B树

B树(B-tree)是一种平衡的多路查找书，2-3树和2-3-4树都是B树的特列。结点最大的孩子数目称为B树的阶(order)。

因此，2-3树是3阶B树，2-3-4树是4阶B树。

可以说，B树的数据结构就是为内外存的数据交互准备的。

B+树

B树是有缺陷的，对于树结构来说，我们都可以通过中序遍历来顺序查找树中的元素，这一切都在内存中进行。

可是在B树结构中，我们往返于每个结点之间也就意味着，我们必须得在硬盘的页面之间进行多次访问。

所以B+树就出现了，它最大的不同是**在分支结点存储了待查找的关键字。

散列表查找

前言

为了查找结果，之前的方法里面”比较”都是不可避免的，但这是否真的有必要？能否直接通过关键字key得到要查找的记录内存存储位置呢？

定义

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f**(key)。查找时，根据这个确定的对应关系找到给定值key的映射f(key),若查找集合中存在这个记录，则必定在f(key)的位置上。

这里我们把这种对应关系f称为散列函数，又称哈希函数(Hash)。

采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表(Hash able)。那么关键字对应的记录存储位置我们称为散列地址。

面向查找

散列技术既是一种存储方法，也是一种查找方法。

然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。

除留余数法

除留余数法为最常用的构造散列函数的方法。

根据前辈们的经验，若散列表表长为m，通常p为小于或等于表长(最好接近m)的最小质数或不包含小于20质因子的合数。

但是没有完美的办法。在现实中，应该视不同的情况采用不同的散列函数。我们只能给出一些考虑的因素来提供参考：

1. 计算散列地址所需要的时间
2. 关键字的长度
3. 散列表的大小
4. 关键字的分布情况
5. 记录的查找频率

综合这些因素，我们才能决策哪种散列函数更合适。

处理散列冲突

• 开放地址法(对冲突的再次计算函数)
• 再散列函数法则(准备多个散列函数)
• 链地址法
• 公共溢出区法

小结

我们这一章全都是围绕一个主题”查找”来作文章的。

首先我们要弄清楚查找表、记录、关键字、主关键字、静态查找表、动态查找表等这些概念。

然后，对于顺序表查找来说，尽管很土(简单)，但它确实很多后面查找的基础，注意设置『哨兵』的技巧，可以使得本已经很难提升的简单算法里还是提高了性能。

有序查找，我们着重讲了折半查找的思想，它在性能上比原来的顺序查找有了质的飞跃，由O(n)变成了O(logn)。之后我们又讲解了另外两种优秀的有序查找：插值查找和斐波那契查找，三者各有优缺点，我们要仔细体会。

线性索引查找，我们提到了稠密索引、分块索引和倒排索引。索引技术被广泛的用于文件检索、数据库和搜索引擎等技术领域，是我们进一步学习这些技术的基础。

二叉排序树是动态查找最重要的数据结构，它可以在兼顾查找性能的基础上，让插入和删除也变得效率较高。不过为了达到最优的状态，二叉排序树最好是构造成平衡的二叉树才最佳。因此我们就需要再学习关于平衡二叉树(AVL 树)的数据结构，了解AVL树是如何处理平衡性的问题。这部分是本章重点，需要认证掌握。

B树这种数据结构是针对内存与外存之间的存取而专门设计的。由于内外存的查找性能更多取决于读取的次数，因此在设计中要考虑B树的平衡和层次。我们先通过最简单的B树(2-3树)来理解如何构建、插入、删除元素的操作，再通过(2-3-4)树的深化，最终来理解B树的原理。之后，我们还介绍了B+树的设计思想。

散列表是一种非常高效的查找数据结构，在原理上业与前面的查找不尽相同，它回避了关键字之间反复比较的繁琐，而是直接一步到位查找结果。当然，这也就带来了记录之间没有任何关联的弊端。应该说，散列表对于那种查找性能要求高，记录之间关系无要求**的数据有非常好的适用性。在学习中要注意的是散列函数的选择和处理冲突的方法。