全套课件-数据结构

数据结构第一章绪论随着计算机技术的飞速发展，计算机应用的范围越来越广泛。因此，要想高效地处理这些数据，必须深入研究数据本身的特性、数据之间的关系，以及如何有效地将数据存储在计算机内，这正是数据结构所要研究的主要问题。本章主要介绍数据结构的基本概念，数据的逻辑结构、存储结构及关系，算法及算法时间复杂度的分析。1.1

数据结构的课程地位及研究内容

一、数据结构的课程地位数据结构是计算机及相关专业的一门专业基础课，是介于数学、计算机硬件和计算机软件之间的一门核心课程，是程序设计的后续课程，同时也是编译原理、操作系统、数据库等课程的基础。

二、数据结构的研究内容例1-1公司员工信息管理系统。员工数据按照一定的顺序线性排列。这就是解决该问题的模型（线性表）。

员工号姓名性别年龄住址电话所属部门01002王清男25南京路10号3562财务01003李力女28甘肃路6号5673总务01004张娟女30杭州路25号2345经理办公室01005张爱民男35洛阳路12号2436销售……………………………………例1-2计算机和人对弈问题若将对弈从开始到结束的过程中所有可能出现的格局都画在一张图上，则可得到一棵倒长的“树”。由以上几个例子可见，描述非数值计算问题的数学模型不再是数学方程，而是诸如线性表、树、图之类的数据结构。因此，数据结构课程是研究非数值计算的程序设计问题中计算机处理对象以及它们之间关系和操作的学科。它的主要研究：（1）数据元素之间的逻辑关系——数据的逻辑结构；（2）数据元素及关系在计算机内的表示——数据的存储结构；（3）数据的操作及实现。1.2基本概念和术语

1数据（data）数据是所有能被输入计算机、且能被计算机处理的符号的集合，是计算机加工处理的对象。2数据元素（dataelement）数据元素是数据的基本单位。学生信息检索系统中学生信息表中的一个记录、教学计划编排问题中的一个顶点等，都被称为一个数据元素。有时，一个数据元素可由若干个数据项组成。3数据项（dataitem）数据项是组成数据元素的单位，是数据的不可分割的最小单位。4数据结构(DataStructure)

指的是数据之间的相互关系，即数据的组织形式，是互相之间存在着一种或多种关系的数据元素的集合。数据结构包括三个方面的内容：数据的逻辑结构存储结构对数据的运算（或操作）。（1）数据的逻辑结构(LogicalStructure)在形式上，数据结构可以采用二元组来表示：Data_Structure=(D,R)其中D是数据元素集合，R是D中元素之间关系的集合。（2）数据的存储结构(StorageStructure)是指数据的逻辑结构用计算机语言的实现，即数据元素及其关系在计算机存储器内的表示①顺序存储。②链式存储③索引存储方法

④散列存储方法（3）数据的运算数据的运算即对数据施加的操作，如插入、删除、检索等。在数据结构中，这些运算需要通过算法来实现。数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。最后通过例子来增加对数据结构三方面内容的感性认识。5数据类型（DataType）数据类型是程序设计语言中所允许使用的变量种类。一个数据类型不仅定义了相应变量可以设定的值的集合，而且还规定了对变量允许进行的一组运算及其规则。例如，在C语言中定义的整型（int）是32768~32767范围内所有整数的集合，以及可以对整数进行的加、减、乘、除、求余等运算。6抽象数据类型(AbstractDataType，ADT)抽象数据类型是指基于一类逻辑关系的数据类型以及定义在这个类型上的一组操作。抽象数据类型的描述格式如下：ADT抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>}ADT抽象数据类型名1.3算法的描述和分析瑞士计算机科学家N.Wirth指出:“程序=数据结构+算法”它描述了计算机程序是由组织信息的数据结构和处理信息的算法组成。二者相辅相成，不可分割，对实际问题的求解，就是选择一种好的数据结构，加上设计一个好的算法。1.3.1算法算法是对特定问题求解过程的描述，是一个能够解决问题的、有具体步骤的方法，是指令的有限序列。算法可以用伪码、自然语言和框图等形式描述，也可以用程序设计语言描述。从易于实现的角度考虑，通常用某种程序设计语言来描述算法，例1-5已知n个整数，求n个整数中的最大数。一个算法应该具有下列特性：（1）有穷性（2）确定性（3）可行性（4）有输入（5）有输出1.3.2算法的设计要求程序设计的实质是对确定的问题选择一种“好结构和好算法”，一个好的算法应符合以下算法设计要求：（1）正确性（2）可读性（3）健壮性（4）高效率与低存储量需求1.3.3算法度量及分析通常对于一个实际问题的解决，可以提出若干个算法，那么如何从这些可行的算法中找出最有效的算法呢？或者有了一个解决实际问题的算法，我们如何来评价它的好坏？这些问题需要通过算法分析来确定。1时间复杂度（TimeComplexity）一个算法的时间复杂度是指该算法的运行时间与问题规模的对应关系。为了便于比较同一问题的不同算法，通常的做法是，从算法中选出一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数（也称为频度）作为算法的时间度量。一般情况下，算法中基本语句重复执行的次数T（n）是问题的规模n的某个函数f（n），因此，算法的时间度量可记作T（n）=O（f（n））记号“O”读作“大O”,它表示随着问题规模n的增大，执行时间的增长率和f（n）的增长率相同。也称作算法的渐进时间复杂度（AsymptoticTimeComplexity），简称为时间复杂度。时间复杂度往往不是精确的执行次数，而是估算的数量级，它着重体现的是随着问题规模n的增大，算法执行时间的变化趋势。因此，“大Ο表示法”通常只关注T(n)的最高阶，忽略其低次项和常数项。例如，一个程序的实际执行时间为T(n)＝2.7n3+3.8n2+5.3，在这个多项式中随着n变大，n3项的成长比其它二项的成长速度快得多，这二项因此可以被忽略，可以说对于较大的n值，这个子程序基本上是一个2.7n3的处理程序。故T(n)＝Ο(n3)。例1-6求如下两个N×N矩阵相乘的算法的时间复杂度。在以上代码中，乘法运算是“矩阵相乘问题”的基本操作。整个算法的执行时间与该基本操作（乘法）重复执行的次数n3成正比，记作：T(n)=O(n3)常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。且：O(1)≤O(log2n)≤O(n)≤O(nlog2n)≤O(n2)≤O(n3)≤…≤O(nk)≤O(2n)。2空间复杂度（SpaceComplexity）除了时间以外，空间代价也是程序员要经常考虑的计算机资源。类似于时间复杂度，一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，记作S(n)=O(f(n))它也是问题规模（或大小）n的函数。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量以外，也需要一些对数据操作的工作单元和存储一些为实现计算所需信息的辅助空间。程序本身所有指令所占空间对不同算法一般来说不会有数量级的差别，在比较算法时可以不加考虑；若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑。故对算法空间复杂度的分析通常只需要分析实现计算所需信息的辅助空间。1.4应用实践：学生管理系统登录模块设计1实践目的（1）掌握程序设计的三大结构：顺序结构、选择结构、循环结构。（2）掌握结构体的定义和应用。（3）掌握指针的定义和应用。（4）掌握函数的编写和调用方法。1.4应用实践：学生管理系统登录模块设计2实践内容利用结构体和指针实现学生管理系统登录模块设计，要求先对多个用户信息进行初始化，用户信息包括账号和密码两部分，然后输人当前用户的账号和密码进行验证，正确则显示“登录成功!”，错误则显示“账号或者密码错误!”。1.4应用实践：学生管理系统登录模块设计图1-4-1运行结果

本章小结

本章主要介绍了数据、数据元素、数据结构等基本概念和抽象数据类型的定义、表示和实现方法，并详细阐述了算法设计的要求以及从时间和空间角度分析算法的方法。要求同学们熟悉各名词、术语的含义，掌握数据的逻辑结构和存储结构之间的关系，掌握常见的四种逻辑结构和常用的四种存储结构；了解抽象数据类型相关内容；理解算法的特性及设计要求；掌握计算语句频度和估算算法时间复杂度的方法。第二章线性表线性表是最简单、最基本、最常用的一种数据结构，是线性结构的抽象。线性结构的特点是元素之间具有一对一的线性关系，元素是“一个接一个”的排列。本章将首先介绍线性表的抽象数据类型定义，然后给出实现线性表的两种存储结构──顺序存储结构与链式存储结构，进一步给出在相应存储结构上实现的线性表运算。2.1工作场景导入

【工作场景】某学校准备建立一个学生成绩系统，该系统具有查询成绩、删除成绩、添加成绩、询全班平均成绩等功能。要求设计具体的算法并编写程序实现之，结果如图所示。【引导问题】如何定义一个线性表？如何选择合适的线性表存储结构？如何利用线性表实现查询、删除、添加等功能？2.2线性表的逻辑结构线性表(Linear_List)是一种线性结构，是由n(n≥0)个相同类型的数据元素a1，a2，…，an组成的有限序列，记作:(a1，a2，…，ai-1，ai，ai+1，…，an)其中n为表长，n=0时称为空表。数据元素ai(1≤i≤n)的具体含义在不同情况下可以不同线性表中的各元素在位置上是有序的。每个数据元素最多有一个直接前驱和一个直接后继。

对线性表进行的运算有如下几种：（1）初始化运算InitList(L):（2）求表长运算ListLength(L)：（3）元素定位运算LocateElem(L,x):（4）取元素运算GetElem(L,i，e):（5）插入运算ListInsert(L,i,x):（6）刪除运算ListDelete(L，i,c):（7）遍历运算ListTraverse(L):2.3.1线性表的顺序存储

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的存储单元中。假设线性表中有n个数据元素，每个数据元素占K个存储单元，第一个元素a1的存储地址用LOC(a1)表示，第i个数据元素ai的地址用LOC(ai)表示，则：第i个数据元素的地址为：

LOC(ai)=LOC(a1)+(i-1)×K(1≤i≤n)线性表的顺序存储结构可定义为：#defineMaxSize100/*线性表的最大长度/*typedefintElemType;/*假设元素类型为int型*/typedefstruct{ElemTypedata[MaxSize]；/*data数组用于存放表中元素*/intlength；/*当前表的长度*/}SeqList；

定义一个顺序表：SeqList*L；2.3.2顺序表上基本运算的实现

1初始化线性表该运算的结果是构造一个空的线性表L。实际上只需将length成员设置为0即可。voidInitList(SeqList*L){L=(SeqList*)malloc(sizeof(SeqList));L->length=0;}2插入线性表的插入运算是指在表的第i(1≤i≥n+1，n为当时的表长)个位置上，插入一个新元素x，使长度为n的线性表(a1，……，ai-1，ai，……，an)变成长度为n+1的线性表(a1，……，ai-1，x，ai，……，an)，插入后数据元素ai-1和ai之间的逻辑关系发生了变化。

算法描述如下：intInsert_Sq(SeqList*L，ElemTypex，inti)/*在顺序表L中第i个数据元素之前插入一个新元素x*/{intk；if((i<1)||(i>L->Length+1)){printf(“插入位置错”);return0；}/*非法位置，退出运行*/if(L->Length>=MaxSize){printf(“表空间满”);return0；}/*表空间溢出，退出运行*/for(k=L->length-1；k>=i-1；k--)L->data[k+1]=L->data[k]；/*为插入元素而移动元素*/L->data[i-1]=x；/*插入X*/L->length++；/*表长加1*/return1;}3删除线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(a1，……，ai-1，ai，ai+1，……，an)变成长度为n-1的线性表(a1，……，ai-1，ai+1，……，an)intDeleteList(SeqList*L，inti)/*在顺序表L中删除第i个数据元素*/{intk；

if((i<1)||(i>L->length)){printf(“插入位置错”);return0；}/*非法位置*/for(k=i-1；k<=L->length-1；k++)L->data[k-1]=L->data[k]；/*元素前移*/L->length--；/*表长减1*/return1;}在顺序表上每插入或删除一个元素平均需要移动表中一半元素，当n较大时，算法的效率较低，所以一般适用于表不大或插入，删除不频繁的情况。

4按值查找intLocateElem(SeqList*L，ElemTypex){inti=0;while(<L->length&&L->data[i]!=x)i++;if(i>=L->length)return0;elsereturni+1;}2.4线性表的链式存储结构

链式存储结构用一组任意的存储单元依次存储线性表里元素，这组存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存的任何位置上。

为反映出各元素在线性表中的逻辑关系，对每个数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成一个数据元素的存储映象，称为结点（Node）。

例如，图2-4-2所示为线性表（dog，pig，cat，fox，hen，bat，bee，bird）的单链表存储结构，整个链表的存取需从头指针开始进行，依次顺着每个结点的指针域next找到线性表的各个元素，直至next域为空为止。通常我们用箭头表示链域中的指针：

typedefstructNode{ElemTypedata；/*数据域*/structNode*next；/*指针域*/}ListNode，*LinkList；假设P是ListNode型的变量，它指向线性表中的第i个数据元素（结点ai即其数据域为ai的结点），则p->next是指向第i+1个数据元素（结点ai+1）的指针。换句话说，若p->data=ai，则p->next->data=ai+1。由此，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。1初始化单链表VoidInitList(LinkList*head){/*初始化单链表*/head=(LinkList)malloc(Sizeof(ListNode))/*申请头结点空间，并使头指针head指向头结点*/head->next=NULL；/*置链尾标记NULL*/}按序号查找

ListNode*GetElem(LinkListhead，inti)/*在带头结点的单链表head中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置；否则返回NULL*/{intj；

ListNode*p；

p=head；j=0；/*从头结点开始扫描*/while(p!=NULL&&j<i){p=p->next；/*扫描下一结点*/j++；/*已扫描结点计数*/}if(i==j&&i!=0)returnp；/*找到第i个结点*/else/*当i<=0或i>n时找不到*/returnNULL}3插入运算voidInsertList(LinkListhead，ElemTypex，inti){ListNode*pre，*s；

intj；pre=head；j=0；

while(pre!=NULL&&k<i-1)/*在第i个元素之前插入，则先找到第i-1个数据元素的存储位置，使指针pre指向它*/{pre=pre->next；j++；}if(j!=i-1)printf(“positionerror”)；else{s=(ListNode)malloc(sizeof(ListNode))/*为x申请一个新的结点并由s指向它*/s->data=x；s->next=pre->next；/*完成插入操作*/pre->next=s；}}4删除运算

voidDeleteList(LinkListhead，inti)/*删除带头结点的单链表head上的第i个结点*/{ListNodepre，r；intj；

pre=head；j=0；

while(pre->next!=NULL&&j<i-1)/*寻找被删除结点i的前驱结点i-1，使pre指向它*/{pre=pre->next；

j++；

}if(j!=i-1)/*即while循环是因为pre->next=NULL或i<1而跳出的*/printf(“未找到该结点”)；

else{r=pre->next；

pre->next=r->next/*删除结点r*/free(r)；}/*释放被删除的结点所占的内存空间*/}5建立单链表头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。

LinkListCreateFromHead(){/*用头插法建立带头结点的单链表*/LinkListhead；/*头指针*/ListNode*s；/*工作指针*/charch；

intflag=1；/*设置一个标志变量flag，初值为1，当输入“$”时将flag置0，建表结束*/head=(Linklist)malloc(sizeof(ListNode))；

head->next=NULL；/*链表开始时为空*/while(flag){ch=getchar()；if(ch!=’$’)/*插入读入的字符*/{s=(LinklList)malloc(sizeof(listNode))；

s->data=ch；

s->next=head->next；

head->next=s；}elseflag=0；}returnhead；/*返回头指针*/}尾插法建表将新结点插到当前链表的表尾上。为此，必须增加一个尾指针r，使之始终指向当前链表的表尾。其建表过程如图算法描述如下：

LinkListCreateFromTail(){/*用尾插法建立头结点的单链表*/LinkListhead；

ListNode*r，*s；charch；

intflag=1；/*设置一个标志，初值为1，当输入”$”时，flag为0，建表结束*/head=(LinkList)malloc(sizeof(ListNode))；/*为头结点分配存储空间*/if(head==NULL)error(“Nospacefornodecanbeobtained”)；/*动态分配空间失败,退出运行*/head->next=NULL；/*初始化为空链表*/r=head；/*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初始值指向头结点*/while(flag){ch=getchar()；

if(ch!=’$’){s=(ListNode*)malloc(sizeof(ListNode))；

s->data=ch；

r->next=s；

r=s；

}else{flag=0；

r->next=NULL；/*将最后一个结点的next域置为空，表示链表的结束*/}}/*while*/returnhead；}

2.4.2循环链表

循环链表(CircularLinkedList)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，整个链表形成一个环，这样从表中任一结点出发都可找到表中其它结点。2.4.3双向链表

在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双向链表(DoubleLinkedList)。双链表的结构定义如下：

typedefstructDuLNode { ElemType data；

structDuLNode *prior；

structDuLNode *next；

}DuLNode,*DuLinkList；

插入：设要在p所指结点的前面插入一个新结点*s

①s->prior=p->prior；②s->next=p；③p->prior->next=s；④p->prior=s删除：设p指向待删除的结点，则需修改两个指针①p->prior->next=p->next②p->next->prior=p->prior2.5顺序表与链表的比较

基于空间的考虑当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜于采用顺序表作为存储结构。2.基于时间的考虑若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。对于频繁进行插入和删除的线性表，应采用链表做存储结构。若表的插入和删除主要发生在表的两端，则宜采用尾指针表示的循环单链表为宜。2.6回到工作场景

【工作过程1】项目分析与算法流程设计。【工作过程2】编写代码【工作过程3】系统运行2.7应用实践：一元多项式的表示及相加

1实践内容用线性表实现一元多项式的表示及相加2实践目的懂得如何使用线性表解决问题3实践过程一般情况下的一元多项式可写成

Pn(x)=p1xe1+p2xe2+┄+pmxem其中：pi

是指数为ei

的项的非零系数，

0≤e1<e2<┄<em=n可以下列线性表表示：（（p1,e1）,(p2,e2),┄,(pm,em)）例如：P999(x)=7x3-2x12-8x999可用线性表

((7,3),(-2,12),(-8,999))表示为了有效利用存储空间，通常用链式存储结构来表示多项式。实现方法：每个结点代表一个非0系数项。数据域包含系数项和指数项，指针域指示下一个非0系数项所在结点的存储位置。-1A703198517^系数指数8算法的设计：定义指针pa和pb分别指向两个多项式链表，比较它们结点的指数域，

pa->exp<pb->exp:pa->exp>pb->exp:pa->exp=pb->exp:2=∧

72238

pa175∧

29

1307

pb89∧

72238

pbpa175∧

89

1307

pb8-9∧

72218

pb8程序运行结果如图小结

线性表是一种最基本、最常用的数据结构。用顺序存储结构存储的线性表称为顺序表，顺序表是由数组实现的；用链式存储结构存储的线性表称为链表，链表是用指针实现的。链表又可按连接形式的不同分为单链表、双链表和循环链表。在实际应用中，线性表采用哪种存储结构，要根据具体情况而定，主要考虑的是算法求解时的时间复杂度和空间复杂度。第三章栈和队列

栈和队列是两种特殊的线性结构。从数据的结构角度看，它们是线性表，从操作的角度看，它们是操作受限的线性表。在日常生活中经常会遇到栈或队列的实例。例如，停车场车辆的调度要用到栈，排队购物要用到队列。3.1工作场景导入

【工作场景】某公司有一个地下停车场如图3-1-1，此停车场是一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出.汽车在停车场内按照车辆到达时间的先后顺序,依次从停车场最里向大门口处停放(最先到达的第一辆车放在停车场的最里面)。若车场内已停满n辆汽车,则后来的汽车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内的某辆车要开走时,在它之后进入的车辆必须退出车场为它让路,待该辆车开出大门外,其他车辆再按照原次序进入车场,每辆车停放在车场的车在它离开停车场时必须按照它停留的时间长短交纳费用.如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。编制程序模拟该停车场的管理。3.2.1栈的定义及基本运算栈（Stack），是一种运算受限的线性表，即它只允许在表的一端进行插入和删除操作。通常，我们把这一端称为栈顶（Top），另一端称为栈底（Botton）。当栈中没有元素时称为空栈。向栈中插入新元素的过程称为进栈或入栈；从栈中删除元素的过程称为出栈或退栈栈又被称为后进先出（LastInFirstOut）的线性表，简称为LIFO表

栈的基本操作：InitStack(&S)：构造一个空栈S。DestroyStack(&S)：栈S已存在，将栈S销毁。ClearStack(&S)：栈S已存在，将S清为空栈。StackEmpty(S)：栈S已存在，若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)：栈S已存在，返回S的元素个数，即栈的长度。GetTop(S,&e)：栈S已存在且非空，用e返回S的栈顶元素。Push(&S,e)：栈S已存在，插入元素e为新的栈顶元素。Pop(&S,&e)：栈S已存在且非空，删除S的栈顶元素，并用e返回其值。3.2.2栈的表示和实现

1顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，在高级程序设计语言中，通常以一固定大小的一维数组来表示顺序栈。栈的顺序存储结构为typedefstruct{ElemTypeelem［MAXSIZE］;inttop;}SqStack;当栈满时不允许有元素再进栈，栈满时如还有元素要进栈，则发生上溢，上溢可能使有用信息丢失，因此要尽量避免；

当所有元素都已出栈，此时为栈空状态，这时如还要出栈，则发生下溢，下溢常常用来作为控制转移的条件或程序结束的标志。顺序栈的主要算法描述如下：（1）栈初始化：voidInitStack（SqStack*S）{/*建立一个空栈S*/S->top=0;}（2）判空栈操作：intStackEmpty（SqStack*S）{/*判断栈S是否为空，空则返回1，非空则返回0*/if（S->top==0）/*栈空条件为S->top==0*/return1;elsereturn0;}

（3）元素进栈操作：intPush（SqStack*S,ElemTypex）{/*若栈S未满，则将元素x进栈*/if(S->top==MAXSIZE)/*栈满条件为S->top==MAXSIZE*/{printf（″栈上溢出!＼n″）;return0;}else{/*否则将x赋值给栈顶指针所指空间，然后将栈顶指针后移*/S->elem［S->top］=x;S->top++;return1;}}

（4）元素出栈操作：intPop（SqStack*S，ElemType*x）{/*从栈中弹出栈顶元素*/if（S->top==0）

{printf（″栈下溢出!＼n″）;return0;}else{S->top--;/*否则栈顶指针减1，即栈顶下移*/*x=S->elem［S->top］;return1;}}

共享栈在栈的共享技术中最常用的是两个栈的共享技术，它主要利用了“栈底位置不变，而栈顶位置动态变化”的特性。将两个栈的栈底设在数组空间的两端，让两个栈各自向中间延伸

栈的链式存储结构栈的链接存储结构与线性表的链接存储结构相似，每个结点除了存储本身的信息之外，还需存储一个指示其直接后继的指针。

数据进栈相当于向链栈的表头插入新的结点并成为新的表头结点，数据出栈相当于删除链栈的表头结点#defineLENsizeof(SNode) typedefstructSNode { ElemTypedata； /*结点的数据域*/ structSNode*next； /*结点的指针域*/ }SNode，*Link； /*Link为结点指针类型*/链栈操作示意图3.2.3栈的简单应用例3.1：设计算法，实现把十进制整数用2-9之间的任一进制数输出。由计算过程可知，由低到高依次得到r进制中的每一位数字，而输出却是从高到低依次输出每一位，所以此类问题正符合栈后进先出的思想，适合用栈来解决此类问题，具体算法描述如下：voidAlter(longn，intr) {LinkS；/*假定使用链栈*/InitStack(S)； /*初始化栈*/while(n)/*由低到高求出每一个余数并入栈{k=n%r；push(S，k)；n/=r；} while(!StackEmpty(S)){pop(S，k)；printf(“%d”，k)；}}例3.3表达式中括号匹配问题。假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的算法。算法思想：算术表达式中三种括号出现的次序正好符合后到的括号要最先被匹配的“后进先出”的栈的操作特点，因此可以利用一个栈来存储三种左括号。当右括号出现时，看当前栈顶括号是否与之匹配，若匹配则退栈，若不匹配说明算术表达式中括号配对不正确。若算术表达式中所有括号都能正确的别消解，则改算术表达式中括号配对正确，否则该算术表达式中括号配对不正确。用顺序栈实现如下：voidCorrect(SqStack*S)/*判别表达式中括弧是否正确配对*/{ inttag; charch,x; InitStack(S); printf("请输入算术表达式，检查其括弧是否正确配对,以#结束,如{5*[b-(c+d)]}#\n"); ch=getchar(); tag=1;/*标志位。tag=1，表达式中括弧正确配对；tag=0表达式中括弧不正确配对*/ while((ch!='#')&&(tag==1)) /*如果字符串没有结束且标志位为1，则做如下操作*/ {if(ch=='('||ch=='['||ch=='{')Push(S,ch); /*如果遇到'('、'['或'{'，则将其入栈*/ if(ch==')') /*如果遇到')'，则弹出栈顶字符；若栈顶字符不等于'('，则置tag为0*/ {Pop(S,&x); if(x!='(')tag=0; }/*if(ch=')')结束*/ if(ch==']')/*如果遇到']'，则弹出栈顶字符；若栈顶字符不等于'['，则置tag为0*/ {Pop(S,&x); if(x!='[')tag=0; }//if(ch=']')结束

if(ch=='}')/*如果遇到'}'，则弹出栈顶字符；若栈顶字符不等于'{'，则置tag为0*/ {Pop(S,&x); if(x!='{')tag=0; }/*if(ch='}')结束*/ ch=getchar();/*继续读取下一个字符*/ }/*while结束*/if(StackEmpty(S))&&(tag==1)) printf("\n括弧正确配对!\n");/*如果栈为空且tag为1，则打印配对成功*/else printf("括弧不正确配对!\n");/*如果栈不空或者tag为0，则打印配对不成功*/}队列(Queue)也是一种操作受限制的线性表。其所有的插入操作均限定在表的一端进行，该端称为队尾（Rear），而所有的删除操作则限定在表的另一端进行，该端则称为队头（Front）。队列的插入和删除操作分别称为入队和出队。队列具有先进先出（FirstInFirstOut，FIFO）的特性。

3.3队列队列的基本操作可以归纳为以下几种。（1）InitQueue（Q）初始化操作（2）Empty（Q）判空操作（3）EnQueue（Q，x）入队列操作（4）DeQueue（Q）出队列操作（5）GetHead（Q）取队头元素（6）Clear（Q）队列置空操作（7）Currentsize（Q）利用一组连续的存储单元(一维数组)依次存放从队首到队尾的各个元素，称为顺序队列。由于随着入队和出队操作的变化，队列的队头和队尾的位置是变动的，因此设置两个整型变量front和rear分别指示队头和队尾在数组空间中的位置，其类型定义如下：#defineMAXSIZE100//队列的最大容量typedefstruct{ElemTypeelem[MAXSIZE];//队列的存储空间intfront，rear;//队头队尾指针}SqQueue;3.3.2队列的顺序存储表示当front=rear时队列为空队列。当rear=MAXSIZE时，队列已经无法再插入元素了，但是实际上前面还有空的位置可供元素插入。通常将该现象称为假溢出。这种现象致使被删除元素的空间无法重新利用。为充分利用向量空间，克服上述“假溢出”现象，可以将队列空间看成为一个首尾相接的圆环，并称这种队列为循环队列(CircularQueue)。循环队列循环队列的基本操作的实现1初始化操作

voidInit_SeQueue(CirSeQueue*sq){sq->front=sq->rear=0;}2入列操作intEnQueue（SqQueue*Sq,ElemTypex）{/*在循环队列Sq的尾部插入一个新的元素x*/if（（Sq->rear+1）%MAXSIZE==Sq->front）return0;/*若循环队列已满*/Sq->elem［Sq->rear］=x;/*若循环队列未满，则先插入元素，后将尾指针后移*/Sq->rear=（Sq->rear+1）%MAXSIZE;return1;}3出列操作intDeQueue（SqQueue*Sq,ElemType*x）{if（Sq->front==Sq->rear）return0;/*若循环队列已空*/*x=Sq->elem［Sq->front］;Sq->front=（Sq->front+1）%MAXSIZE;return1;}3.3.3队列的链式存储表示

队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。链队列的类型描述如下：typedefstructLQNode{ElemTypedata;StructLQNode*next;}LQNode,*LinkedQNode;//链队结点的类型typedefstruct{StructLQNode*front,*rear;}LQueue,*LinkedQueue;//将头尾指针封装在一起的链队列3.4队列的应用

队列可应用于杨辉三角形的打印。杨辉三角形的特点是两个腰上的数字都为1，其他位置上的数字是其上一行与之相邻的两个数之和。所以在打印过程中，第i行上的元素由第i-1行中的元素来生成。我们可以利用循环队列实现打印杨辉三角形的过程。在循环队列中依次存放第i-1行上的元素，然后逐个出队列并打印，同时生成第i行元素并入列。下面给出打印杨辉三角形的前n行元素的具体算法，N为杨辉三角形的行数：voidYangHuiTriangle(){SeqQueueQ;InitQueue(&Q);EnQueue(&Q,1);/*第一行元素入队*/for(n=2;n<=N;n++)/*产生第n行元素并入队，同时打印第n-1行的元素*/{EnQueue(&Q,1);/*第n行的第一个元素入队*/for(i=1;i<=n-2;i++)/*利用队中第n-1行元素产生第n行的中间n-2个元素并入队*/{DeQueue(&Q,&temp);Printf(″%d″,temp);/*打印第n-1行的元素*/GetHead(Q,&x);/*取新的队头元素*/temp=temp+x;/*利用队中第n-1行元素产生第n行元素*/

EnQueue(&Q,temp);

}

DeQueue(&Q,&x);

printf(″%d″,x);/*打印第n-1行的最后一个元素*/

EnQueue(&Q,1)/*第n行的最后一个元素入队*/

}}3.5回到工作场景

通过学习，我们应该已经掌握了栈的创建方法以及栈的基本操作的实现，足以完成工作场景中的任务。下面我们回到第3.1节的工作场景中，完成工作任务。【工作过程一】问题解析：【工作过程二】编写代码，实现算法：【工作过程3】系统运行

3.6应用实践

3.6.1嵌入式系统中断模拟设计1.实践内容单片机或嵌入式系统中断模拟设计。2.实践目的懂得如何使用栈解决问题。掌握栈在单片机或者嵌入式系统中的简单应用。3、实践过程3.6.2学生舞会舞伴配对系统设计

1.实践内容舞会舞伴配对系统设计2.实践目的懂得如何使用队列解决问题。3、实践过程假设在舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题，先入队的男士或女士亦先出队配成舞伴。本章小结

本章主要讨论了两种运算受限的线性表：栈和队列。同时给出了它们的基本概念、存储结构以及基本操作的实现，通过例子的讨论来加深对栈和队列的理解。对于栈来说，它的插入和删除都是在线性表的同一端进行的。存储结构有两种：顺序存储和链式存储。请注意顺序存储结构时的栈空和栈满的判断条件，出栈之前要判断栈是否空，入栈之前要判断栈是否满。对于队列来说，它的插入运算在表的一端进行，而删除运算却在表的另一端进行。它的存储结构也有两种：顺序存储和链式存储。在使用顺序存储结构时，为了能够重复利用有限的存储空间，提出循环队列，应注意循环队列队空和队满的判断条件。第四章串

串是一种特殊的线性表，它的每个结点仅由一个字符组成。字符串简称为串。计算机的非数值串处理的对象基本上是字符串数据。在信息检索系统、文字编辑系统、问答系统以及自然语言的翻译系统等等，都是以字符串数据作为处理对象的。

4.1工作场景导入

【工作场景】某公司为保证一些信息不外泄，需要编写加密解密程序使信息加密存放。我们可以用事先给定的密码对照表进行加密。等要查看信息时，再按照密码对照表将其解密并输出，编写程序实现之，得到如图4-1-1所示的输出结果。

。【引导问题】（1）如何定义一个串？（2）如何应用串的基本操作？（3）如何显示一个串？4.2串及其类型定义

1串的定义串（String）（或字符串）：由零个或多个字符组成的有限序列,记作S=“a1a2…an”(n≥0)

其中，S是串的名字，用双引号括起来的字符序列是串的值。要注意的是，双引号不属于串值，它只是用来标识串的开始和终止。

ai(1≤i≤n)一般是字母、数字或其它字符。2串的有关术语串的长度：串中字符的个数n称作串的长度。空串：零个字符的串称为空串(NullString)，它的长度为零。空格串：由一个或多个空格组成的串。子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。例如，设有串A和B分别是：A=“Thisisastring”，B=“is”,则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号为3。串相等：如果两个串的串值相等(相同)，称这两个串相等。即只有当两个串的长度相等，且各个对应位置的字符都相同时才相等。4.2.2串的基本运算

在线性表的基本操作中，大多以“单个元素”作为操作对象；而在串的基本操作中，通常以“串的整体”作为操作对象。串的基本操作有：StrAssign（&T，chars）生成一个串T：StrCopy（&T，S）串复制：StrCompare（S，T）串比较：StrLength（S）串的长度：ConCat（&T，S1，S2）串连接：SubString（&Sub，S，pos，len）求子串：Index（S，T，pos）串定位：StrInsert（&S，pos，T）串插入：StrDelete（&S，pos，len，&T）串删除：4.3串的存储结构及基本操作的实现

串的存储可以有两种处理方式：一种是将串定义成字符型数组，从串名可以直接访问到串值，串的存贮空间分配是在编译时完成的，不能更改，这种方式称为串的静态存储结构；另一种是串的存储空间分配是在程序运行时动态分配的，这种方式称为串的动态存储结构。串的静态存储结构采用定长顺序结构。串的动态存储结构有两种方式：一种采用链式存储结构；另一种是堆结构的存储方式。

4.3.1串的定长顺序存储

用一组地址连续的存储单元存储串的字符序列，构成串的顺序存储，简称为顺序串。在C语言中，对字符串处理的两个要素是：数组名，结束标记符号。我们选用字符”\0”作为串的结束标记符号，串s=”thisisastring”的顺序存储结构，如图4-3-1所示。顺序串的类型定义如下：#defineMAXSTRLEN 255 typedefstruct{ charch[MAXSTRLEN]； int len； }SString；串的基本运算的实现串连接statusConcat(SString*S，SStringS1，SStringS2){/*返回由S1和S2连接形成的新串S*/ S->len=S1.len+S2.Len；

for(i=0；i<S1.len；i++)/*将S1.ch[0]～S1.ch[s1.len-1]复制到S*/S->ch[i]=S1.ch[i]；

for(i=0；i<S2.len；i++)/*将S2.ch[0]～S2.ch[s2.len-1]复制到S*/S->ch[S1.len+i]=S2.ch[i]；

returnOK；}串的基本运算的实现求子串

statusSubString(SString*Sub，SStringS，intpos，intlen){/*返回串S中从第pos个字符开始的，由连续len个字符组成的子串Sub*/ intk，Sub->len=0；

if（pos<=0||pos>StrLength(S)||len<0||pos+len-1>Length(S)）

return ERROR；for(k=pos-1；k<pos+len-1；k++) Sub->ch[k-pos+1]=S.ch[k]；/*将S.ch[pos-1]～S.ch[pos+len-2]复制到Sub串*/ Sub->len=len；

returnOK；}4.3.2串的堆分配存储表示

仍然以一组地址连续的存储空间来存储字符串值，但其所需的存储空间是在程序执行过程中动态分配，故是动态的，变长的。串的堆式存储结构的类型定义：typedefstruct{char*ch;//若非空，按长度分配，否则为NULLintlength;//串的长度}TString;下面以串的连接操作为例介绍串的堆分配存储表示。StatusTString*StrConcat(TString*T,TString*s1,TString*s2)//用T返回由s1和s2联结而成的串{intk,j,t_len;if(T->ch)free(T->ch);//释放旧空间t_len=s1->length+s2->length;if((p=(char*)malloc(sizeof((char)*t_len))==NULL){printf(“系统空间不够，申请空间失败！\n”);returnERROR;}for(j=0;j<s->length;j++)T->ch[j]=s1->ch[j];//将串s复制到串T中for(k=s1->length,j=0;j<s2->length;k++,j++)T->ch[j]=s1->ch[j];//将串s2复制到串T中free(s1->ch);free(s2->ch);returnOK;}4.3.3串的链式存储结构串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。4.4串的模式匹配及算法

子串的定位操作通常称作串的模式匹配(其中T被称为模式串)，是各种串处理系统中最重要的操作之一。很多软件，若有“编辑”菜单项的话，则其中必有“查找”子菜单项。或者在文本编辑程序中，经常要查找某一单词在特定文本中出现的位置，即匹配。4.4串的模式匹配及算法

设有两个串s和t，且

s=”s1s2…sn”t=”t1t2…tm”其中0≤m≤n（通常有m<n）。子串定位是要在主串s中找出一个与子串t相同的子串。一般把主串s称为目标，把子串t称为模式，把从目标s中查找模式为t的子串的过程称为“模式匹配”。匹配的结果有两种：如果s中有模式为t的子串，就返回该子串在s中的位置，当s中有多个模式为t的子串时，通常只要找出第一个子串即可，这种情况称为匹配成功；否则称匹配失败。4.4串的模式匹配及算法

基本思想是：从主串s的第pos个字符起和模式串t的第一个字符比较，若相等，则继续逐个比较后续字符，否则从主串s的下一个字符起再重新和模式t的字符比较。依次类推，直至模式t中的每个字符依次和主串s中的一个连续的字符序列相等，则称匹配成功，函数值为和模式t中第一个字符相等的字符在主串s中的序号，否则称匹配不成功，函数值为0。以s=”abbaba”和t=”aba”为例，用上述做法进行模式匹配的过程如图intIndex(SStringS，SStringT，intpos){/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。*/ inti=pos，j=1；

while(i<＝S.len&&j<＝T.len)if(S.ch[i-1]==T.ch[i-1])/*第i个字符的下标为i-1*/{++i；++j；}/*继续比较后续字符*/else{i=i-j+2；j=1；}/*指针后退重新开始匹配*/ if(j>T.len) return(i-T.len)；/*匹配成功*/ else return0；/*匹配不成功*/}在最好情况下，每趟不成功的匹配都是模式t的第一个字符与s中相应字符比较时就不相等。最好情况下，该算法的平均时间复杂度是O（n+m）。在最坏情况下，每趟不成功的匹配都是在模式t的最后一个字符，它与s中相应的字符比较时才不相等，新的一趟匹配开始前，指针i要回溯到i-m+2的位置上。时间复杂度是O（m×n）4.4.2KMP算法

KMP算法的思想是：设S为主串，P为模式串，并设i指针和j指针分别指示主串和模式串中正待比较的字符，令i和j的初值均为1。若有Si=Pj，则i和j分别增1，否则i不变（无需回溯主串指针），j退回到j=next[j]位置（即将模式向右“滑动”一段距离），继续比较Si和Pj。next[j]表示当模式中第j个字符与主串中相应字符失配时，在模式中需重新和主串中该字符进行比较的字符的位置。模式串的next[j]定义如下：在求得模式的next[j]后，匹配可如下进行：当Si和Pj失配时，j退回到j=next[j]位置，依次类推，直至下列两种可能：一种是j退到某个next值时字符比较相等，则指针各自增1，继续进行匹配；另一种是j退到值为0（即模式的第一个字符失配），则此时需将模式继续向右滑动一个位置，即从主串的下一个字符Si＋1起和模式重新开始匹配。算法实现如下：intIndexKMP(SStringS，SStringT，intpos){/*算法中假定串S和T中的字符下标是从1开始，下标为0的单元不存储串内容*/ inti=pos，j=1；

while(i<=S.len&&j<=T.len) if(j==0||S.ch[i]==T.ch[i]){i++；j++；}/*继续比较后续字符*/ else j=next[j]；/*模式串向右移动*/ if(j>T.len) return(i-T.len)； /*匹配成功*/else return0；/*匹配不成功*/}当栈满时不允许有元素再进栈，栈满时如还有元素要进栈，则发生上溢，上溢可能使有用信息丢失，因此要尽量避免；

当所有元素都已出栈，此时为栈空状态，这时如还要出栈，则发生下溢，下溢常常用来作为控制转移的条件或程序结束的标志。顺序栈的主要算法描述如下：（1）栈初始化：voidInitStack（SqStack*S）{/*建立一个空栈S*/S->top=0;}（2）判空栈操作：intStackEmpty（SqStack*S）{/*判断栈S是否为空，空则返回1，非空则返回0*/if（S->top==0）/*栈空条件为S->top==0*/return1;elsereturn0;}

（3）元素进栈操作：intPush（SqStack*S,ElemTypex）{/*若栈S未满，则将元素x进栈*/if(S->top==MAXSIZE)/*栈满条件为S->top==MAXSIZE*/{printf（″栈上溢出!＼n″）;return0;}else{/*否则将x赋值给栈顶指针所指空间，然后将栈顶指针后移*/S->elem［S->top］=x;S->top++;return1;}}

（4）元素出栈操作：intPop（SqStack*S，ElemType*x）{/*从栈中弹出栈顶元素*/if（S->top==0）

{printf（″栈下溢出!＼n″）;return0;}else{S->top--;/*否则栈顶指针减1，即栈顶下移*/*x=S->elem［S->top］;return1;}}

共享栈在栈的共享技术中最常用的是两个栈的共享技术，它主要利用了“栈底位置不变，而栈顶位置动态变化”的特性。将两个栈的栈底设在数组空间的两端，让两个栈各自向中间延伸

栈的链式存储结构栈的链接存储结构与线性表的链接存储结构相似，每个结点除了存储本身的信息之外，还需存储一个指示其直接后继的指针。

数据进栈相当于向链栈的表头插入新的结点并成为新的表头结点，数据出栈相当于删除链栈的表头结点#defineLENsizeof(SNode) typedefstructS