第3章 CHAPTER 3 数 据 结 构 数据结构是研究非数值计算程序设计中计算机的操作对象以及它们之间关系和运算的科学。数据结构与数学、计算机硬件和计算机软件等有着密切的关系，数据结构与算法密不可分，是操作系统、编译原理、数据库、情报检索、人工智能等学科的重要基础。 3.1数据的逻辑结构与存储结构 3.1.1基本概念 数据是信息的载体，是描述客观事物的数、字符以及所有能被输入计算机中并被计算机程序识别和处理的符号的集合，包括数值性数据和非数值性数据。 1. 数据元素、数据项和数据对象 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以由若干个数据项组成。数据项是在数据处理时不能再分割的最小单位。数据对象是性质相同的数据元素的集合。数据对象亦称为数据元素类。数据元素是数据对象的一个实例。 例如，学生张强的学籍信息集合（表）是数据元素，学生学籍信息表中的每一项，如学号、姓名、性别等各自为一个数据项。特征相同且具有共同数据项的众多学生数据可形成一个学生数据对象student。例如： student = { 张强，李兵，… } 任何问题中，数据元素之间都不是孤立的，它们之间存在着某种关系，数据元素之间的关系称为结构。 2. 数据结构 数据结构是互相之间存在关系的数据元素的集合。数据结构将数据按某种逻辑关系组织起来，按一定的存储表示方式把它们存储在计算机存储器中，并在这些数据上定义一个运算的集合。数据结构与数据类型和数据对象不同，它不仅要描述数据类型的数据对象，还要描述数据对象各元素之间的相互关系。 数据结构通常包括逻辑结构和存储结构。逻辑结构用于描述数据之间的逻辑关系，存储结构描述数据如何在计算机内存储。 通常，用计算机解决一个具体问题时，可分为以下步骤。 (1) 从具体问题抽象出一个适当的数学模型。 (2) 设计一个解此数学模型的算法。 (3) 编出程序，进行测试、调试，直至得到最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数值问题可以用诸如方程等描述。而非数值计算问题的数学模型则是用诸如表、树和图之类的数据结构描述。 3. 数据操作 数据操作亦称为数据运算。数据运算是数据结构的一个重要方面，对任何一种数据结构的研究都离不开对该结构上的数据运算及其实现算法的研究。最常用的数据操作有5种： 插入、删除、修改、查找和排序。例如针对线性表，常见的基本操作如下。 (1) 线性表初始化。构造一个空的线性表。 (2) 求线性表的长度。返回线性表中所含元素的个数。 (3) 取表元。返回线性表L中的第i个元素的值或地址。 (4) 按值查找。在线性表L中查找值为x的数据元素，其结果返回在L中首次出现的值为x的元素的地址； 若未找到，返回一个特殊值表示查找失败。 (5) 插入操作。在线性表L的第i个位置插入一个值为x的新元素。 (6) 删除操作。删除线性表L中序号为i的数据元素。 数据结构的操作定义在逻辑结构层次上，而操作的具体实现建立在存储结构基础上。每个操作的算法只有在存储结构确立之后才能实现。 图31描述了数据结构的3个研究内容。 数据结构 逻辑结构线性结构线性表 栈 队列 非线性结构树 图 存储结构顺序存储 链式存储 数据运算： 检索、排序、插入、删除、修改等 图31数据结构的研究内容 3.1.2数据的逻辑结构 数据的逻辑结构反映数据之间的逻辑关系，是对数据之间关系的描述，可以用一个二元组来表示： S=(D，R)。其中D是有限个数据元素构成的集合，R是有限个结点间关系的集合。数据的逻辑结构主要有线性表、树、图等形式。数据的逻辑结构和存储结构是密不可分的两方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 1. 线性表、栈与队列 线性表是最常用、最简单的一种数据结构，其基本特点是线性表中的数据元素是有序且有限的。线性表中数据元素用结点描述，结点之间是一对一的关系。在线性表里有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个前驱和一个后继。现实中有很多一对一的线性关系，如英文字母表、一个班中的学生关系(通过学号关联)，图书馆中的书籍(通过书号关联)。 栈与队列是两种特殊的线性结构。从结构看它们与普通线性表一样，但执行数据操作时它们受特定规则限制。 栈是定义在线性结构上的抽象数据类型，其操作类似线性表操作，但元素的插入、删除和访问都必须在表的一端进行，其操作如图32所示。为形象起见，允许操作端称为栈顶(top)，另一端为栈底(base)，栈的特性为先进后出、后进先出。编程中嵌套函数和递归函数的调用控制、括号匹配问题、运算表达式的计算等均可用栈模拟。 队列是另一种线性表，类似日常生活中排队，队列元素的插入和删除分别在表的两端进行，如图33所示。允许插入的一端为队尾(rear)，允许删除的一端为队头(front)。队列的特性为先进先出、后进后出，操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟。 图32栈示意图 图33队列示意图 2. 树与图 图34资源管理器 树与图结构均为非线性结构。树结构中数据元素之间是一对多的关系。在树中有且仅有一个结点没有前驱，类似于树的根，称为根结点； 其他结点有且仅有一个前驱。它的结构特点具有明显的层次关系。 日常生活及计算机中有很多数据关系是树结构，例如家谱、行政组织机构、源程序的语法结构、资源管理器、人机对弈问题等，如图34和图35所示。 图35对弈问题 图结构中数据元素之间是多对多的关系，图是由结点的有穷集合V和边的集合E组成。其中，为了与树结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。图结构也称作网状结构。 互联网结构、教学计划编排问题、交通网络图等都可以用图结构描述，如图36和图37所示。 图36教学计划编排问题 图37交通网络图 3.1.3数据的存储结构 数据的逻辑结构从逻辑关系上描述数据，是独立于计算机的； 数据的存储结构是逻辑结构在计算机存储器里的实现，是依赖于计算机的。数据的存储结构主要有顺序存储结构、链式存储结构、索引存储结构、散列存储结构4种，并可以根据需要组合成其他更复杂的结构。 1. 顺序存储结构 顺序存储结构是一种最基本的存储方法，是借助元素在存储器中的相对位置来表示数据元素间的逻辑关系。这种方法主要用于线性的数据结构，它把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。在C语言中，通常借助一维数组表示顺序存储结构。 2. 链式存储结构 链式存储结构即在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针来表示数据元素之间的逻辑关系，由此得到的存储表示称为链表。链表既可以表示线性结构，也可以表示非线性结构。 链表中每一个元素称为结点。在C语言中，用结构体类型表示结点，链表由一系列结点组成，结点可以在运行时动态生成。结点所占的存储单元分为两部分： 一部分存放结点本身的信息，称为数据项； 另一部分存放结点的后继结点所对应的存储单元的地址，称为指针项。指针项可以包含一个或多个指针，以指向结点的一个或多个后继。 3. 索引存储结构 索引存储结构指除建立存储结点信息外，还建立附加的索引表标识结点的地址。索引存储结构的优点是检索速度快，缺点是增加了附加的索引表，会占用较多的存储空间。 4. 散列存储结构 散列存储结构又称hash存储结构，是一种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。 若数据结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不须比较便可直接取得所查记录，称这个对应关系f（k）为散列函数，按这个思想建立的表为散列表。散列技术除了可以用于查找外，还可以用于存储。 同一个逻辑结构可以用不同的存储结构存储，本章主要介绍顺序存储与链式存储。具体选择哪一种需根据数据特点及实际运算的效率来确定。 3.2线性表 线性表是n(n≥0)个具有相同属性的数据元素a1，a2，…，an组成的有限序列，线性表中每一个数据元素均有一个直接前驱和一个直接后继数据元素。当n=0时，称为空表，空表不含有任何元素。 3.2.1线性表的顺序存储和操作 1. 线性表的顺序存储 线性表的顺序存储是指在内存中把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。顺序表中数据元素之间的逻辑关系以元素在计算机内物理位置相邻来表示。 图38顺序表的存储地址 由于顺序表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间(字节数)相同。因此，要在此结构中查找某一个元素是很方便的，只要知道顺序表首地址和每个数据元素在内存所占字节的大小就可求出第i个数据元素的地址，因此顺序存储结构的线性表可以随机存取其中的任意元素。 假设顺序表中有n个元素，每个元素占k个单元，第一个元素的地址loc(a1)称为基地址，第i个元素的地址loc(ai)可以通过如下公式计算： loc(ai)=loc(a1)+(i-1)k，如图38所示。 顺序存储结构在C语言中用一维数组表示，一维数组的下标等于元素在顺序表中的序号减1。 typedef struct {datatype data［MAXSIZE］; int last; }SeqList; 其中： datatype为抽象数据类型； MAXSIZE为线性表中最多可以存放的元素个数； last为最后一个元素的位置。 2. 顺序表的操作 顺序表的操作主要包括顺序表的初始化、插入及删除数据、数据的查询及求顺序表的长度等。 (1) 顺序表的初始化。 初始化即构造一个空的顺序表，为顺序表命名及分配空间。 SeqList *init_SeqList() { SeqList *L; L=(SeqList*)malloc(sizeof(SeqList)); L->last=-1; return L; } (2) 插入运算。 插入运算是指在顺序表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素。对于长度可变的顺序表，必须按可能达到的最大长度分配空间。 已知顺序表(4，9，15，28，30，30，42，51，62)，需在第4个元素之前插入一个元素“21”，则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入第4个位置，如图39所示。 图39顺序表中插入元素 代码如下： int Insert_SeqList(SeqList *L,int i,datatype x) { int j; if(L->last==MAXSIZE-1) { printf("table is full!"); return(-1); } if(i<1||i>(L->last+2)) { printf("place is wrong!"); return(0); } for(j=L->last;j>=i-1;j--) { L->data［j+1］=L->data［j］; } L->data［i-1］=x; L->last++; return(1); } (3) 删除运算。 顺序表的删除运算是将表的第i(1≤i≤n)个元素删除，使长度为n的顺序表(e1，…，ei-1，ei，ei+1，…，en)变成长度为n-1的顺序表(e1，…，ei-1，ei+1，…，en)。删除第i个元素(1≤i≤n)时需将第i+1至第n(共n-i)个元素依次向前移动一个位置。 例如，删除顺序表(4，9，15，21，28，30，30，42，51，62)第5个元素，则需将第6个元素到第10个元素依次向前移动一个位置，如图310所示。 图310顺序表中删除元素 代码如下： int Delete_SeqList(SeqList *L,int i) { int j; if(i<1||i>(L->last+1)) { printf("this element don't exist!"); return(0); } for(j=i;j<=L->last;j++) { L->data［j-1］=L->data［j］; } L->last--; return(1); } 在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设pi为在第i个元素之前插入元素的概率，平均移动次数为 E=∑n+1i=1pi(n-i+1) 假设在任何位置上插入的概率相等，即pi=1/(n+1)，i=1，2，…，n+1，平均移动次数为 E=1n+1 ∑n+1i=1(n-i+1)=n2 同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即Qi=1/n，i=1，2，…，n。删除一个元素所需移动元素的平均次数为 E=1n ∑ni=1(n-1)=n-12 由此可得，在顺序表中作插入或删除运算时，平均有一半元素需要移动，时间复杂度为O(n)。(时间复杂度的概念详见4.1.3节) (4) 顺序表的查找操作。 在线性表中查找关键字为x的元素，并返回其位置。 int Locate_list(int s［］, int n, int x) { int i; for (i=1; i<=n; i++) if (s［i］==x) return(i); return(0); } 例3.1从一个有序顺序表中删除重复的元素并返回新的表长，要求空间复杂度为O(1)。 代码如下： #include typedef int ElemType; typedef struct { ElemTypedata［100］; int length; }SeqList; int removeSame (SeqList &B) { ElemTypee=B.data［0］; int index=1; for(int i=1;inext=NULL; //创建链表的表头结点head while (1) { scanf("%d", &data) ; p= (LNode *)malloc(sizeof(LNode)); p–>data=data; //数据域赋值 p–>next=head–>next ; head–>next=p ; //新创建的结点总是作为第一个结点 } return(head); } 创建函数create_LinkList1()，实现尾插法创建单链表函数，链表的头结点head作为返回值。代码如下： LNode *create_LinkList1(void) { int data ; LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode)); p->next=NULL; //创建单链表的表头结点head while (1) { scanf("%d",& data); q= (LNode *)malloc(sizeof(LNode)); q–>data=data; //数据域赋值 q–>next=p–>next; p–>next=q; p=q ; 　　//新创建的结点总是作为最后一个结点 } return(head); } 无论是哪种插入方法，如果要插入建立的单链表的结点是n个，算法的时间复杂度均为O(n)。 (2) 单链表的插入运算。 链表中插入元素只需修改插入元素及其前趋元素的指针即可，操作步骤如图313所示。 图313线性链表插入元素 创建函数Inset()，实现在第i个结点前插入数据值为x的结点的函数。代码如下： int Insert (NODE *head， int i， int x) { NODE *p， *q; int j; if (i<=0) return(0); p=head; j=1; while ((j<=i-1)&&(p!=NULL)) {p=p->link; j++;} if (p==NULL) return(0); q=(NODE *)malloc(sizeof(NODE)); q->data=x; q->link=p->link; p->link=q; return(1); } (3) 单链表的删除运算。 链表中删除操作只需修改被删除元素前趋元素指针即可，操作步骤如图314所示。 图314线性链表删除元素 创建函数Delete()，实现删除指定位置(第i个)元素。代码如下： int Delete (NODE *head， int i) { NODE *p，*q; int j; if (i==0) { p=head; head=head->link; free(p); return(1); } j=1;p=head; while ((jlink!=NULL)) p=p->link; if (p->link==NULL) return (0); q=p->link; p->link=q->link; free(q); return(1); } (4) 线性链表的查找运算。 创建函数Locate_LinkList()，实现链表中按元素值查找。代码如下： Lnode *Locate_LinkList(LinkList L,datatype x) { LNode *p=L->next; while(p!=NULL&&p->data!=x) p=p->next; return p; } 3. 循环链表的操作 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。从循环链表的任意一个结点出发都可以找到链表中的其他结点，使得表处理更加方便灵活。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为NULL，而是指向头一个结点，成为一个由链指针链接的环，也就是算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。循环链表示意图如图315所示。 图315循环链表示意图 循环链表的操作与单链表相似。 4. 双向链表的操作 若结点中有两个指针域，一个指向直接后继，另一个指向直接前趋，这样的链表称为双向链表，如图316所示。双向链表可以克服单链表的单向性缺陷。 图316双向链表示意图 双向链表存储结构如下： struct Double_node { int data; struct Double_node *llink, *rlink; }; typedef struct Double_node NODE; 对指向双向链表任一结点的指针d，具有关系： d->rlink->llink=d->llink->rlink=d，即当前结点后继的前趋是自身，当前结点前趋的后继也是自身。与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。 (1) 双向链表的插入操作。 在数据值为y的结点后，插入数据值为x的结点，如图317所示。 图317双向链表插入结点示意图 创建函数Insert2()，实现双向链表插入结点操作。代码如下： int Insert2(NODE *head，int x，int y) { NODE *p， *q; q=head->rlink; while (q!=head && q->data!=y) q=q->rlink; if (q==head) return(0); p=(NODE *)malloc(sizeof(NODE)); p->data=x; p->llink=q; p->rlink=q->rlink; (q->rlink)->llink=p; q->rlink=p; return(1) } (2) 双向链表的删除操作。 在双向链表中删除数据值为x的结点，如图318所示。 图318双向链表删除结点 创建函数Delete2()，实现双向链表删除结点操作。代码如下： int Delete2 (NODE *head，int x) { NODE *q; q=head->rlink; while(q!=head && q->data!=x) q=q->rlink; if(q==head) return(0); (q->llink)->rlink=q->rlink; (q->rlink)->llink=q->llink; free(q); return(1); } 3.2.3小结 链表的优缺点恰好与顺序表相反。在实际应用中选取何种存储结构，通常从以下几方面考虑。 1. 基于空间的考虑 顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。若线性表长度n变化较大，则存储规模很难预先正确估计。估计太大将造成空间浪费，估计太小又将使空间溢出机会增多。链表不用事先估计存储规模，是动态分配，只要内存空间尚有空闲，就不会产生溢出，所以当对线性表的长度或存储规模难以估计时，不宜采用顺序存储结构而宜采用动态链表作为存储结构。但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于1的，顺序表的存储密度等于1。 2. 基于时间的考虑 线性表如果主要做查找，则时间性能为O(1)； 而在链表中按序号访问的时间性能为O(n)。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。 顺序表中做插入、删除操作时，要平均移动表中一半的元素； 尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观，不容忽视。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。 3. 基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型； 链表的操作是基于指针的，其使用受语言环境的限制。 总之，两种存储结构各有特点，选择哪种结构根据实际使用线性表的主要因素决定。通常较稳定的线性表选择顺序存储结构； 而插入或删除操作频繁的动态性较强的线性表宜选择链式存储结构。 3.2.4栈 1. 栈的定义 栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈按照先进后出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，即最后一个数据被第一个读出来。栈的进出操作如图319所示。 图319进出栈操作 栈的插入和删除操作分别称为进栈和出栈。进栈是将一个数据元素存放在栈顶，出栈是将栈顶元素取出。栈按存储方式可分为两种： 顺序栈和链栈。 例3.2假设有3个数据元素a，b，c，入栈顺序是a，b，c，则它们的出栈顺序有几种可能？ 出栈顺序共有如下几种。 (1) abc顺序进栈则出栈顺序为cba。 (2) a进栈，a出栈，然后b、c进栈，再顺序出栈，则出栈顺序为acb。 (3) a进栈，a出栈； b进栈，b出栈； c进栈，c出栈； 则出栈顺序为abc。 (4) a、b进栈，a、b出栈，然后c进栈，再出栈，则出栈顺序为bac。 (5) a、b进栈，b出栈； c进栈，然后出栈，则出栈顺序为bca。 2. 顺序栈的存储和操作 顺序栈即栈的顺序存储，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。指针top值随着插入和删除而变化。 在栈的操作中有两种异常状态需设法避免，即栈满时做进栈运算和栈空时做退栈运算将产生溢出。因此，入栈要先判断栈是否满，出栈要先判断栈是否空。 (1) 顺序栈描述。 #define M 10 typedef struct { int elem［M］; int top; } SQSTACK; (2) 顺序栈的操作。 ① 判断栈是否为空。 int StackEmpty(SQSTACK stack) { if (stack.top==-1) return(1); return(0); } ② 进栈。 int Push(SQSTACK *stack， int x) { if (stack->top==M-1) return(0); stack->top++; stack->elem［stack->top］=x; return(1); } ③ 出栈。 int Pop(SQSTACK *stack， int *x) { if (StackEmpty(*stack)) return(0); *x=stack->elem［stack->top］; stack->top--; return(1); } ④ 取栈顶元素。 int GetTop(SQSTACK stack， int *x) { if (stack->top==-1) return(0); *x=stack->elem［stack->top］; return(1); } 3. 链栈的存储和操作 栈的链式存储结构称为链栈，因为栈是运算受限的单链表，其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附设头结点，栈顶指针top就是链表的头指针。 (1) 链栈初始化。 Stack_Node *Init_Link_Stack(void) { Stack_Node *top ; top=(Stack_Node *)malloc(sizeof(Stack_Node )) ; top->next=NULL ; return(top) ; } (2) 进栈。 Status push(Stack_Node *top , ElemType e) { Stack_Node *p ; p=(Stack_Node *)malloc(sizeof(Stack_Node)) ; if (!p) return ERROR; //申请新结点失败，返回错误标志 p->data=e ; p->next=top->next; top->next=p; return OK; } (3) 出栈。 Status pop(Stack_Node *top , ElemType *e) { Stack_Node *p ; ElemType e ; if (top->next==NULL ) return ERROR ; //栈为空，返回错误标志 p=top->next ; e=p->data ; 　　//取栈顶元素 top->next=p->next ; 　　//修改栈顶指针 free(p) ; return OK ; } 3.2.5队列 1. 队列的定义 队列是一种先进先出、后进后出的线性表，限定所有的插入只能在表的一端进行，允许插入的一端称为队尾(rear)，删除的一端称为队头(front)，所有的删除运算都在表的另一端队头进行。如果队列按照a1，a2，…，an顺序入队，则出队顺序同样为a1，a2，…，an，即先进队列的元素先出队列，后进队列的元素后出队列。插入元素通常称为入队，删除元素通常称为出队。 队列的物理存储有两种方式，顺序存储的称为顺序队列，链式存储的称为链队列。 2. 顺序队列的存储和操作 在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素，附设两个指针front和rear分别指示队头和队尾的位置，如图320所示。 图320顺序队列操作 指针front和rear值的变化体现了队列的操作。 队列初始化： front=rear=0。 入队： 将新元素插入rear所指的位置，rear加1。 出队： 删去front所指的元素，front加1并返回被删元素。 队列为空： front=rear=0。 队满： rear=MAXSIZE-1。 (1) 顺序队列的创建。 #define MAXSIZE 10 typedef struct { elemtype elem［MAXSIZE］; int front， rear; } SQQUEUE; (2) 判断队列是否为空。 int QueueEmpty (SQQUEUE q) { if(q.front==0&q.rear==0) return(1); return(0); } (3) 顺序队列入队。 int AddQueue (SQQUEUE *q，elemtype e) { if(q->rear==MAXSIZE-1) return(0); q->rear=q->rear+1; q->elem［q->rear］=e; return(1); } (4) 顺序队列出队。 int DelQueue (SQQUEUE *q, elemtype *e) { if(q->front==0&q.rear==0) return(0); q->front = q->front+1; *e = q->elem［q->front］; return(1); } 3. 循环队列的存储和操作 以数组方式顺序存储队列时，会发生假溢出现象，即在队列进出操作中，由于入队时尾指针向前追赶头指针； 出队时头指针向前追赶尾指针，造成队列为空和队列为满时头指针与尾指针均相等，无法通过条件rear=MAXSIZE-1来判读队列为“满”，为了更合理地利用空间，可将队列空间想象为一个首尾相接的圆环，这种队列称为循环队列，如图321所示。当尾指针移动到队列长度位置时，会再从0开始循环。 图321循环队列 循环队列中队列为空条件依然是front==rear，队列为满可通过以下两种方式判断。 (1) 设置一个标志变量flag，当front==rear,且flag=0时为队列为空，当front==rear,且flag=1时为队列为满。 (2) 另设一个标志位以区分队列是空还是满，即少用一个元素空间，当队列头指针在队列尾指针的下一个位置上时为队列满，即(rear%MAXSIZE)+1==front。 //循环队列实现 #include #include #define MAXSIZE 100 //最大队列长度 typedef int ElemType; typedef struct { ElemType*base;//存储内存分配基地址 int front;//队列头索引 int rear; //队列尾索引 }circularQueue; //初始化队列 InitQueue(circularQueue*q) { q->base=(ElemType*)malloc((MAXSIZE)*sizeof(ElemType)); if(!q->base)exit(0); //存储分配失败 q->front=q->rear=0; } //入队列操作 InsertQueue(circularQueue*q,ElemType e) { if((q->rear+1)%MAXSIZE==q->front) return;//队列已满时，不执行入队操作 q->base［q->rear］=e;//将元素放入队列尾部 q->rear=(q->rear+1)%MAXSIZE;/*尾部元素指向下一个空间位置,取模运算 保证了索引不越界(余数一定小于除数)*/ } //出队列操作 DeleteQueue(circularQueue*q,ElemType*e) { if(q->front==q->rear) return;//空队列，直接返回 *e=q->base［q->front］;//头部元素出队 q->front=(q->front+1)%MAXSIZE; } 4. 链队列的存储和操作 用链表表示的队列简称为链队列。一个链队列需要两个指针分别指向队头和队尾元素，如图322所示。 图322链队列 (1) 链队列的描述。 typedef struct node { elemtype data; struct node *link; } NODE，*NODEPTR; typedef struct { NODEPTR front， rear; }LINKQUEUE; (2) 创建空的链队列。 void InitQueue (LINKQUEUE *q) { q->front=NULL; q->rear=NULL; } (3) 判断链列队是否为空。 int QueueEmpty (LINKQUEUE q) { if (q.front==NULL) return(1); return(0); } (4) 链队列的入队。 void AddQueue (LINKQUEUE *q， elemtype e) { NODEPTR p; p=(NODEPTR)malloc(sizeof(NODEPTR)); p->data=e; p->link=NULL; if (q->front==NULL) { q->front=p; q->rear=p; } else { q->rear->link=p; q->rear=p; } } (5) 链队列的出队。 int DelQueue (LINKQUEUE *q， elemtype *e) { NODEPTR p; if (q->front==NULL) return(0); *e=q->front->data; p=q->front; q->front=p->link; free(p); if (q->front==NULL) q->rear=NULL; return(1); } 3.2.6栈和队列的应用 栈在计算机中的应用非常广泛，许多程序语言本身就是建立于栈结构之上的，例如，在编译和运行程序的过程中，需要利用堆栈进行语法检查(如检查括号是否配对)、表达式求值、实现递归算法、数制转换与函数调用等。 队列在计算机及其网络自身内部的各种计算资源分配等场合有广泛的应用，例如，共享打印机、消息队列和广度优先搜索等，都需要借助队列结构实现合理和优化的分配。 1. 括号匹配的检验 假设表达式中包含3种括号： 圆括号、方括号和花括号，其嵌套顺序随意，即“{(［］())}”等为正确的格式，“［()］}”“(［()］”或“(()}”均为不正确的格式。检验括号是否匹配可以用栈来实现： 当遇到“(”“［”或“{”时进栈，遇到“}”“］”或“)”时出栈并进行匹配检验，如果出现不匹配的情况立即结束，否则继续取下一个字符。如果没有遇到不匹配的情况，最后判断栈是否为空： 栈为空，括号匹配； 否则不匹配。在算法的开始和结束时，栈都应该是空的。 2. 数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，通常采用“除以基数取余数”方法，依次对除以基数得到的商再次求余数，这样得到的为待转换进制数从低位到高位的值，当商为0时转换完毕。 具体实现时使用栈暂时存放每次计算得到的余数，当算法结束时(也就是商为0时)，从栈顶到栈底就是转换后从高位到低位的数值。 3. 表达式求值 表达式求值是程序设计语言编译中的一个基本问题。它的实现是栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。 一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例如，1+2*3有“+”“*”两个运算符，“*”的优先级高于“+”，1、2、3是操作数。界定符有括号和表达式结束符等。 为了实现算符优先算法，可以使用两个工作栈： 一个称作OPTR，用以寄存运算符； 另一个称作OPND，用以寄存操作数或运算结果。算法的基本思路如下。 (1) 首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素。 (2) 依次将表达式中的每个字符进栈，若是操作数，则进OPND栈； 若是运算符，则和OPTR栈的栈顶运算符比较优先级后做相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#”)。 4. 迷宫求解 求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。用计算机求解迷宫的方法是从入口出发，顺着某一方向向前探索，若能走通，则继续往前走，否则沿原路退回，换一个方向再继续探索，直到所有的通路都探索到为止。 迷宫问题求解算法中，一般将迷宫建模成图，将迷宫中的点建模为图中的点，将迷宫中相连并且相通的两点建模为图中的一条边，采用矩阵方式存储图，使用一个栈来存储访问过的顶点信息，栈中元素(即顶点信息)由顶点位置和搜索方向两部分组成，前者记载该顶点在迷宫中的位置，后者记载下一个顶点的访问方向，例如，右、下、左、上四个相连的方向。 求一条路径算法的基本思想是： 假设以栈S记录当前路径，则栈顶中存放的是“当前路径上最后一个通道块”。 (1) 若当前路径可通，则纳入“当前路径”——当前位置入栈操作，并继续朝下一个位置“探索”，即切换下一位置为当前位置，如此重复直至到达出口。 (2) 若当前位置不可通，则应该顺着“来向”退回到前一通道块，然后朝着除来向之外的其他方向继续探索。 (3) 若该通道的4个方向均不可走通，则应该从“当前路径”上删除该通道块——出栈操作。由于用计算机解决迷宫问题时，通常用的是“穷举求解”的方法，即从入口出发，顺着某一个方向向前探索，若能走通，则继续往前走； 否则沿原路退回，换另一个方向再继续探索，直至所有可能的通路都探索完为止。为了保证在任何位置上都能沿原路退回，显然需要一个后进先出的结构保存入口到当前位置的路径。因此，在求解迷宫通路的算法中应用“栈”也就是自然而然的事了。 在计算机中可以用方块图表示迷宫，每个方块或为通道(以空白方块表示)，或为墙(以带阴影线的方块表示)，所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。 5. 共享打印机 目前，打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲池技术的数据结构支持。每台打印机具有一个队列(缓冲池)，用户提交打印请求被写入队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除它。这样，利用队列的先进先出特性，就可完成打印机网络共享的先来先服务功能。 6. 消息队列 操作系统中的消息队列也是队列的应用之一，消息队列遵循先进先出的原则，发送进程将消息写入队列尾，接收进程则从队列头读取消息。 3.3树 树是以分支关系定义的层次结构，是一类非常重要的非线性结构，其中以二叉树最为常用。用树结构描述的信息模型在客观世界普遍存在，在计算机科学及软件工程中应用十分广泛。 3.3.1常用术语 树是n(n≥0)个结点的有限集，在任意一棵非空树中存在以下特性。 (1) 有且仅有一个被称为根的结点。 (2) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，称为根的子树(递归定义)。 图323是一棵树的示意图，具有13个结点，A为根结点，它有子树B、C、D。 图323树的结构 关于树的常用术语如下。 (1) 结点的度。每个结点的子树个数。 (2) 叶子。叶子又称终端结点，是指度为0的结点。 (3) 树的度。树中所有结点的度的最大值。 (4) 结点的层次。规定根为第一层，其下面的一层为第二层，以此类推。 (5) 树的深度。树中结点的最大层次数。 (6) 孩子。一个结点的子树的根结点称为此结点的孩子。 (7) 双亲。若结点1是结点2的孩子，则结点2就被称为是结点1的双亲。 (8) 兄弟。同一双亲的孩子之间互称兄弟。 (9) 有序树。树中每个结点的各个子树从左到右依次有序(即不能互换)。 (10) 森林。由m(m≥0)棵互不相交的树构成的集合。 树的存储结构一般用具有多个指针域的多重链表来表示，结点中指针域的个数由树的度来决定。图324(a)中树的存储结构如图324(b)所示。由于树的度为3，因此树中每个结点各具有1个数据域和3个指针域。 图324树及其存储结构示意图 3.3.2二叉树 1. 二叉树的定义 二叉树是度为2的有序树，即每个结点最多有两棵子树，并且二叉树的子树有左右之分，次序不能任意颠倒，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。图325给出了二叉树的5种基本形态。 图325二叉树的5种基本形态 和树结构的定义类似，二叉树的定义也可以用递归形式给出。 2. 二叉树的性质 性质1： 在二叉树的第i层上至多有2i-1个结点(i≥1)。 性质2： 深度为k的二叉树至多有2k-1个结点(k≥1)。 性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 满二叉树和完全二叉树是两种特殊形态的二叉树。满二叉树是深度为k且具有2k-1个结点的二叉树。如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，则称这棵二叉树为完全二叉树，如图326所示。 图326两种特殊形态的二叉树 若一棵二叉树中每个结点的左、右子树的深度之差(平衡因子)均不大于1，则称其为平衡二叉树。满二叉数、完全二叉树一定是平衡二叉树。完全二叉树具有如下性质。 性质4： 具有n个结点的完全二叉树的深度为|log2n|+1，即以2为底n的对数下取整加1。 性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)有以下几种结论。 (1) 如果i=1，则结点i是二叉树的根，无双亲； 如果i>1，则双亲PARENT(i)是结点i/2。 (2) 如果2i>n，则结点i无左孩子(结点i为叶子结点)； 否则其左孩子LCHILD(i)是结点2i。 (3) 如果2i+1>n，则结点i无右孩子； 否则其右孩子RCHILD(i)是结点2i+1。 3. 二叉树的存储结构 图327二叉树 二叉树可以用顺序存储结构和链式存储结构两种存储结构。 (1) 顺序存储结构。 按照顺序存储结构的定义，将一棵二叉树按完全二叉树顺序依次自上而下、自左至右存放到一个一维数组中。若该二叉树为非完全二叉树，则将相应位置空出来，使存放的结果符合完全二叉树的形状。例如，如图327所示的二叉树的顺序存储结构如表31所示。 表31二叉树的顺序存储结构 结点编号123456789101112131415 结点值ABCD0EF0G0000H0 在顺序存储结构中，第i个结点的左、右孩子一定保存在第2i及2i+1个单元中。顺序存储的优点是容易理解，缺点是对非完全二叉树而言，大量空结点浪费存储空间。 二叉树顺序存储结构为： #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree［MAX_TREE_SIZE］;//TElemType为结点数据类型 SqBiTree bt; (2) 链式存储结构。 在一般情况下，常用链式存储结构表示二叉树。由二叉树的定义可知，一个二叉树的结点至少保存3种信息： 数据元素、左孩子位置、右孩子位置。对应地，链式存储二叉树的结点至少包含3个域： 数据域、左指针域、右指针域，如图328所示。 图328含有两个指针域的二叉树结点及其存储结构 二叉树链式存储结构为： typedef struct treenode { elemtype data; struct treenode *lchild， *rchild; } TREENODE,*TREENODEPTR,*BTREE 3.3.3森林、树与二叉树的转换 森林是m(m≥0)棵互不相交的树的集合。可以说树是森林的特例，二叉树又是树的特例。通过一定规则，森林和树可以转换为二叉树。数据结构中一般着重研究二叉树的相关性质及处理方法，通过转换，使用二叉树的一些算法去解决树和森林中的问题。 1. 树转换为二叉树 树转换为二叉树的步骤如下。 (1) 在原树所有兄弟结点之间加一连线。 (2) 对每个结点，除保留与其长子间的连线外，将该结点与其余孩子间的连线全部删除。 (3) 以根结点为轴心，顺时针旋转45°。 图329示范了将树转换为二叉树的步骤。 图329树转换为二叉树 2. 森林转换为二叉树 森林转换为二叉树的步骤如下。 (1) 在森林中所有树的根结点之间加一连线。 (2) 将森林中的每棵树转换成相应的二叉树。 (3) 以第一棵树的根结点为轴心，顺时针旋转45°。 图330示范了将森林转换为二叉树的步骤。 图330森林转换为二叉树 同理也可以将一个二叉树转换为对应的树或森林。 3.3.4树的应用举例 树结构广泛应用于分类、检索、数据库及人工智能等多个方面。例如哈夫曼树常用于通信及数据传送中构造传送效率最高的二进制编码(哈夫曼编码)以及用于编程中构造平均执行时间最短的最佳判断过程等。 1. 哈夫曼树的有关概念 图331树的路径 哈夫曼树又称为最优二叉树，是一类带权路径最短的树。设有n个权值{w1，w2，…，wn}，构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，1