数据结构-使用C语言（第7版）课件全套 朱战立 第1-11章 绪论 -查找

数据结构

使用C语言(第7版)第1章绪论主要知识点数据结构的基本概念抽象数据类型和软件构造方法算法和算法的时间复杂度1.1数据结构的基本概念基本术语(1)数据：人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。(2)数据元素：表示一个事物的一组数据。(3)数据项：构成数据元素的数据。例如，学生信息可包括学生的学号、姓名、性别、年龄等数据。这些数据构成学生情况的描述的数据项；包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。基本术语(4)抽象数据元素：没有实际含义的数据元素。(5)抽象数据元素的数据类型：没有确切定义的数据类型。(6)数据的逻辑结构：数据元素之间的相互联系方式。(7)数据的存储结构：数据元素在计算机中的存储方式。(8)数据的操作：对一种数据类型的数据进行的某种处理。(9)数据的操作集合：对一种数据类型的数据进行的所有操作。数据的逻辑结构线性结构：除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。树结构：除根结点外，每个数据元素只有一个前驱数据元素，可有０个或若干个后继数据元素。图结构：每个数据元素可有０个或若干个前驱数据元素和０个或若干个后继数据元素。线性结构树结构图结构数据的存储结构

顺序存储结构：把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。链式存储结构：使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。顺序存储结构链式存储结构数据的操作

从抽象角度，数据的操作主要讨论某种数据类型数据应具备操作的逻辑功能。抽象角度下的操作一般和数据的逻辑结构一起讨论。具体说，数据的操作主要讨论操作的具体实现算法。具体问题的操作实现必须在数据的存储结构确定后才能进行。

数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。另外，还讨论查找和排序算法的实现方法。1.2抽象数据类型和软件构造方法类型是一组值的集合。数据类型是指一个类型和定义在这个类型上的操作集合。抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合。数据类型和抽象数据类型的不同之处仅仅在于数据类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。

抽象数据类型使软件设计成为工业化流水线生产的一个中间环节。一方面，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；另一方面，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司可以安全、快速、方便的完成应用软件系统的设计。

软件的设计采用模块化方法，抽象数据类型就是构造大型软件的最基本模块。1.3算法及其时间复杂度算法是描述求解问题方法的操作步骤集合。描述算法的语言形式1.文字形式:用中文或英文这样的文字来描述算法。2.伪码形式:用一种仿程序设计语言的语言来描述算法。3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。例1-1:设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1逆置的算法，要求逆置后的新数组b中数据元素序列为an-1,…,a1,a0,并要求原数组中的数据元素值不被改变。voidReverse(intn,DataTypea[],DataTypeb[]){inti;for(i=0;i<n;i++)b[i]=a[n-1-i];//把数组a的元素逆置后赋给数组b}例1-2:设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1就地逆置的算法，即要求逆置后的原数组中数据元素序列改变为an-1,…,a1,a0。voidReverse(intn,DataTypea[]){inti,m=n/2;DataTypetemp;for(i=0;i<m;i++){

//进行m次调换

temp=a[i];a[i]=a[n-1-i];a[n-1-i]=temp;}}

(1)输入性(2)输出性(3)有限性

(4)确定性(5)可执行性算法满足性质:

(1)正确性(2)可读性(3)健壮性

(4)高时间效率(5)高空间效率算法设计目标:算法时间效率的度量算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种:

(1)事后（实际）统计方法(2)事前（理论）分析方法程序运行消耗时间的有关因素:(1)书写算法的程序设计语言(2)编译产生的机器语言代码质量(3)机器执行指令的速度(4)问题的规模，即算法的时间效率与算法所处理的数据个数n的函数关系。算法的时间效率是算法所处理的数据个数n的函数，算法的时间效率也称作算法的时间复杂度。定义:T(n)=O(f(n)),当且仅当存在正常数c和n0，对所有的n(n≥n0)满足T(n)≤c×f(n)。例1-3设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本语句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本语句2}解:设基本语句的执行次数为f(n),有f(n)=c1×n2+c2×n3,因 T(n)=f(n)=c1×n2+c2×n3≤c×n3,其中c1,c2,c均为常数，所以该算法的时间复杂度为

T(n)=O(n3)

例1-4设n为如下算法处理的数据个数，求如下算法的时间复杂度。

for(i=1;i<=n;i=2*i) cout<<"i="<<i;解:设基本语句的执行次数为f(n),有2f(n)≤n,即有f(n)≤lbn。因T(n)=f(n)≤lbn≤c×

lbn,所以该算法的时间复杂度为

T(n)=O(lbn)。例1-5:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a[0]~a[n-1])，从小到大进行排序，求该算法的时间复杂度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];[j+1]=temp;}}}}解:设基本语句的执行次数为f(n),最坏情况下有

f(n)≈n+4*n2/2因 T(n)=f(n)≈n+2*n2≤c*

n2,其中c为常数，所以该算法的时间复杂度为

T(n)=O(n2)。例1-6下面的算法是在一个有n个数据元素的数组a中删除第i个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至n-1。intDelete(inta[],int&n,inti){intj;if(i<0||i>=n)return0;//删除位置错误，失败返回for(j=i+1;j<n;j++)a[j-1]=a[j];//顺次移位填补n--;//数组元素个数减1return1;//删除成功返回}解:假设删除任何位置上的数据元素都是等概率的,设Pi为删除第i个位置上数据元素的概率，则有Pi=1/n，设E为删除数组元素的平均次数，则有因T(n)=E≤(n+1)/2≤

c*n,其中c为常数，所以该算法的等概率平均时间复杂度为

T(n)=O(n)

例1-7对比在数据元素个数为30000时，冒泡排序算法和快速排序算法的实际耗时。根据问题的要求，设计测试程序，并在计算机上实际运行。程序运行结果：冒泡排序:6.00秒；快速排序:0.00秒程序运行结果说明：系统中的difftime(end,start)函数以秒为单位计时，快速排序的实际耗时少于0.5秒，所以输出显示为0.00秒。程序运行结果说明，当数据元素个数足够大时，理论分析的快速排序算法优于冒泡排序算法的结果，和程序的实际测试结果吻合。算法耗时的实际测试算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度（如O(n)、O(n2)、O(n6)、O(n8)等）的算法，是可接受、可实际使用的算法；而具有指数时间复杂度（如O(2n)、O(nn)、O(n！)等）的算法，是理论上可以计算，但实际上不可计算的问题，通常称作难解的问题。对于具有多项式时间复杂度的算法，无论数据元素个数多大（只要是有限的数值），算法都可以在有限的时间内运行完成；而对于难解的问题，当n足够小时，算法可以在有限的时间内运行完成，当n比较大时，其运行时间将是一个天文数字！

数据元素个数和时间复杂度

习题1-1，1-2，1-5，1-7，1-8， 1-9，1-10，1-11习题1-13，1-14，1-15

作业

第2章线性表主要知识点线性表抽象数据类型顺序表单链表循环单链表循环双向链表静态链表设计举例2.1

线性表抽象数据类型1.线性表的定义线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。线性结构:2.线性表抽象数据类型数据:｛a0,a1,…,an-1｝,ai的数据类型为DataType操作:(1)ListInitiate(L)初始化线性表(2)ListLength(L)求当前数据元素个数(3)ListInsert(L,i,x)插入数据元素(4)ListDelete(L,i,x)删除数据元素(5)ListGet(L,i,x)取数据元素｛a0,a1,…,an-1｝表示数据元素有次序关系。2.2线性表的顺序表示和实现1、顺序表的存储结构

实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。顺序表的存储结构如图所示顺序存储结构的线性表称作顺序表a0a1a2a3a4a5…listsize=6MaxSize-10123456其中a0,a1,

a2等表示顺序表中存储的数据元素，list表示顺序表存储数据元素的数组，MaxSize表示存储顺序表的数组的最大存储单元个数，size表示顺序表当前存储的数据元素个数。

typedefstruct{DataTypelist[MaxSize]; intsize;}SeqList;2、顺序表操作的实现

（1）初始化ListInitiate(L)voidListInitiate(SeqList*L) {L->size=0; //定义初始数据元素个数}

（2）求当前数据元素个数ListLength(L)intListLength(SeqListL) {returnL.size;}

（3）插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataTypex){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];

//从后向前依次后移

L->list[i]=x; //插入x L->size++; //元素个数加1

return1;}（4）删除数据元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x) {intj;

*x=L->list[i]; //保存删除的元素到x中

for(j=i+1;j<=L->size-1;j++)

L->list[j-1]=L->list[j];

//依次前移

L->size--; //数据元素个数减1

return1;}（5）取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0||i>L.size-1){printf("参数i不合法!\n"); return0;}else{ *x=L.list[i];return1;}}3、顺序表操作的效率分析时间效率分析:算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作(最深层语句频度)T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置i.若i=size，则根本无需移动（特别快）；若i=0，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。设Pi是在第i个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1/(n+1),则

插入时的平均移动次数为:n(n+1)/2÷（n+1）＝n/2≈O(n)同理可证:顺序表删除一元素的时间效率为:T（n)=(n-1)/2≈O(n)

顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度都为O(1)主要优点是算法简单，空间单元利用率高；主要缺点是需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。主要优缺点4、顺序表应用举例例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过100个。

实现方法：

1、采用直接编写一个主函数实现。

2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h中，通过#include“SeqList.h”）程序设计如下：#include<stdio.h> #defineMaxSize100 typedefintDataType;#include"SeqList.h"

voidmain(void){SeqListmyList;inti,x;ListInitiate(&myList);for(i=0;i<10;i++)ListInsert(&myList,i,i+1);ListDelete(&myList,4,&x);for(i=0;i<ListLength(myList);i++) ListGet(myList,i,&x);}程序运行结果：12346789102.3线性表的链式表示和实现1、单链表的结构(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。结点结构如图示：指针域数据域nextdata或数据域：存储元素数值数据指针域：存储直接后继的存储位置(2)头指针、头结点和首元结点的区别头指针头结点首元结点a0heada1…an^示意图如下：头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a０的结点。(3)带头结点单链表和不带头结点单链表的比较pa0a1an-1∧…headdatanextx∧s(a)插入前pa0a1an-1∧…headdatanextx∧s(b)插入后1).在带头结点单链表第一个数据元素前插入结点2).删除带头结点单链表第一个数据元素结点pa0a1an-1∧…headdatanext3).在不带头结点单链表第一个数据元素前插入结点a0a1an-1∧…headx∧s(a)插入前a0a1an-1∧…headxs(b)插入后4).在不带头结点单链表其他数据元素前插入结点pai-1a0aian-1∧…headdatanextxs…×5).删除不带头结点单链表第一个数据元素结点a0a1an-1∧…headdatanext×6).删除不带头结点单链表其他数据元素结点pai-1a0aian-1∧…headdatanext…×ai+1结论：（1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样（2）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数（4）因此，带头结点单链表的算法设计简单结点定义：typedefstructNode{DataTypedata;structNode*next;}SLNode2、单链表的操作实现（1）初始化ListInitiate(head)voidListInitiate(SLNode**head){*head=(SLNode*)malloc(sizeof(SLNode));(*head)->next=NULL; }（2）求当前数据元素个数ListLength(head)intListLength(SLNode*head){SLNode*p=head;intsize=0; while(p->next!=NULL) {p=p->next; size++; }returnsize;}（3）插入ListInsert(head,i,x)intListInsert(SLNode*head,inti,DataTypex){SLNode*p,*q;intj;

p=head;j=-1; while(p->next!=NULL&&j<i-1){p=p->next;j++;}

if(j!=i-1){printf(“插入位置参数错！”);return0;}

q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=p->next;p->next=q; return1;}说明：①要在带头结点的单链表第i（0≤i≤size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后动态申请一个结点存储空间并由指针q指示，并把数据元素x的值赋予新结点的数据元素域（即q->data=x），最后修改新结点的指针域指向ai结点（即q->next=p->next），并修改ai-1结点的指针域指向新结点q（即p->next=q）。②循环条件由两个子条件逻辑与组成，其中子条件p->next!=NULL保证指针所指结点存在，子条件j<i-1保证最终让指针p指向ai-1结点。

（4）删除ListDelete(head,i,x)intListDelete(SLNode*head,inti,DataType*x){SLNode*p,*s;intj;

p=head;j=-1;while(p->next!=NULL&&p->next->next!=NULL&&j<i-1){p=p->next; j++;}

if(j!=i-1){printf(“插入位置参数错！”); return0;}

s=p->next;*x=s->data;p->next=p->next->next;free(s);return1;}

说明：要在带头结点的单链表中删除第i（0≤i≤size-1）个结点，首先要在单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向ai结点（即s=p->next），并把数据元素ai的值赋予x（即*x=s->data），最后把ai结点脱链（即p->next=p->next->next），并动态释放ai结点的存储空间（即free(s)）。删除过程如图2-14所示。图中的①对应算法中的删除语句。（5）取数据元素ListGet(head,i,x)intListGet(SLNode*head,inti,DataType*x){SLNode*p;intj;

p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next; j++;}

if(j!=i){printf(“取元素位置参数错！”); return0;}

*x=p->data;return1;}

（6）撤消单链表内存空间Destroy(head)voidDestroy(SLNode**head){SLNode*p,*p1;

p=*head;while(p!=NULL){p1=p;p=p->next;free(p1); }*head=NULL;}4、单链表操作的效率分析单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为：删除一个数据元素时比较数据元素的平均次数为：另外，单链表求数据元素个数操作的时间复杂度为O(n)。和顺序表相比主要优点是不需要预先确定数据元素的最大个数，插入和删除操作不需要移动数据元素；主要缺点是查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。单链表和顺序表相比，单链表的优点和缺点正好相反。5、单链表应用举例例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用单链表实现。#include<stdio.h> #include<stdlib.h> #include<malloc.h>typedefintDataType;#include"LinList.h"

voidmain(void){SLNode*head;inti,x;ListInitiate(&head);

for(i=0;i<10;i++)ListInsert(head,i,i+1);ListDelete(head,4,&x); for(i=0;i<ListLength(head);i++){ListGet(head,i,&x)==0); printf(“%d”,x);

} Destroy(&head);}程序运行结果：12346789102.4循环单链表循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。它的优点是从链尾到链头比较方便。循环单链表也有带头结点和不带头结点两种结构。一个带头结点的循环单链表如下图示：a0a1an-1…headhead(a)空链表(b)非空链表程序设计：p!=NULL 改为 p!=headP->next!=NULL 改为 p->next!=head2.5双向链表双向链表是每个结点除后继指针域外还有一个前驱指针域，它有带头结点和不带头结点，循环和非循环结构，双向链表是解决查找前驱结点问题的有效途径。结点结构如图示：priordatanext下图是带头结点的循环双向链表的结构，可见，其前驱指针和后继指针各自构成自己的循环单链表。head(a)空链表a0a1an-1head(b)非空链表…在双向链表中:设指针p指向第i个数据元素结点，则p->next指向第i+1个数据元素结点，p->next->prior仍指向第i个数据元素结点，即p->next->prior=p;同样p->prior->next=p。循环双向链表的插入过程如图示：a0aian-1head…xs…ai-1××…④①②③p删除过程如图示：ai+1aian-1head……ai-1××①②p2.6静态链表在数组中增加一个(或两个)指针域用来存放下一个(或上一个)数据元素在数组中的下标，从而构成用数组构造的单链表。因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称做仿真指针。结构如下：ABCE∧headD(a)常规链表A1B2C3D4E-1┇(b)静态链表1datanext01234┇maxSize-1A2E-1B4D1C3┇(b)静态链表2datanext01234┇maxSize-12.7设计举例例2-4设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。算法思想：首先，找到要删除元素的位置，然后，从这个位置到最后一个元素，逐个前移，最后，把元素个数减1。intListDataDelete(SeqList*L,DataTypex){inti,j;

for(i=0;i<L->size;i++) if(x==L->list[i])break;

if(i==L->size)return0; else {for(j=i;j<L->size;j++)

L->list[j]=L->list[j+1];

L->size--; return1;}}例2-5构造一个顺序表的删除算法，把顺序表L中所有值相同的数据元素x全部删除。算法思想：在例2-4所设计的删除算法的基础上，增加外重循环进行查找，查找到元素x则删除，然后继续进行这样的过程和删除过程，直到元素末尾结束。intListMoreDataDelete(SeqList*L,DataTypex){inti,j; inttag=0; for(i=0;i<L->size;i++){if(x==L->list[i]) {for(j=i;j<L->size-1;j++)

L->list[j]=L->list[j+1]; L->size--;

i--;

tag=1; }}

returntag;}例2-6设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。算法思想：从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。voidLinListInsert(SLNode*head,DataTypex){SLNode*curr,*pre,*q;curr=head->next;pre=head;while(curr!=NULL&&curr->data<=x){pre=curr; curr=curr->next;}q=(SLNode*)malloc(sizeof(SLNode));q->data=x;q->next=pre->next;pre->next=q;}算法设计说明：（1）在循环定位插入位置时，循环条件必须首先是curr!=NULL，然后是curr->data<=x。如果次序颠倒，则当curr为空（即等于链表结束标记NULL）时,将因为curr->data不存在而出错；次序不颠倒时，当curr等于NULL时将退出循环，不会进行后边条件curr->data<=x的比较。（2）当比较到最后一个结点仍有data小于等于x时，此时有pre指向最后一个结点，curr等于NULL，则上述算法把新结点插入到了单链表尾作为了单链表新的表尾结点。

例2-7设head为单链表的头指针，并设单链表带有头结点，编写算法将单链表中的数据元素按照数据元素的值递增有序的顺序进行就地排序。算法思想：在例2-6算法的基础上，再增加一重循环即可实现全部数据元素的排序。由于此时的排序过程没有申请新的结点空间，所以这样的排序算法满足就地排序，即不增加新的内存空间的设计要求。具体实现过程是：

把头指针head所指单链表置空（即初始时head所指单链表仅包含一个头结点），把去掉头结点的原单链表（设由头指针p指示）中的数据元素逐个重新插入head所指单链表中。每次插入从head所指单链表的第一个数据元素结点开始，逐个比较head所指单链表每个结点的data域值和p所指单链表的当前第一个数据元素结点的data域值，当前者小于或等于后者时，用head所指单链表的下一个结点进行比较；否则就找到了插入结点的合适位置，从p所指单链表中取下当前第一个数据元素结点插入到head所指单链表的合适位置。这样的过程一直进行到p所指单链表为空时结束。voidLinListSort(SLNode*head){SLNode*curr,*pre,*p,*q;p=head->next;head->next=NULL;while(p!=NULL){curr=head->next;pre=head; while(curr!=NULL&&curr->data<=p->data) {pre=curr;curr=curr->next; } q=p;p=p->next;q->next=pre->next;pre->next=q;}}

习题2-1，2-2，2-3习题2-4，2-10，2-14习题2-16习题2-5，2-6，2-15习题2-20，2-21习题2-18，2-22作业

第3章栈和队列主要知识点栈栈应用队列队列应用优先级队列3.1

堆栈1、栈的基本概念(1)定义:限定只能在固定一端进行插入和删除操作的线性表。特点：后进先出。(2)允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。作用：可以完成从输入数据序列到某些输出数据序列的转换2、栈抽象数据类型数据集合:{a0,a1,…,an-1}ai的数据类型为DataType。操作集合：

(1)StackInitiate(S)：初始化栈S(2)StackNotEmpty(S)：栈S非空否

(3)StackPush(S,x)：入栈

(4)StackPop(S,d)：出栈

(5)StackTop(S,d)：取栈顶数据元素3、顺序栈

顺序栈：顺序存储结构的栈。

顺序栈的存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素.a0a1a2a3a4stack栈底栈顶MaxStackSize-1012345=toptypedefstruct{DataTypestack[MaxStackSize]; inttop;}SeqStack;顺序栈的操作实现：

（1）初始化StackInitiate(S)voidStackInitiate(SeqStack*S) {S->top=0; }（2）非空否StackNotEmpty(S)intStackNotEmpty(SeqStackS){if(S.top<=0)return0;elsereturn1;}（3）入栈StackPush(S,x)intStackPush(SeqStack*S,DataTypex){if(S->top>=MaxStackSize){printf("栈已满无法插入!\n"); return0;}else{S->stack[S->top]=x; S->top++;return1;}}（4）出栈StackPop(S,d)intStackPop(SeqStack*S,DataType*d){if(S->top<=0){printf("栈已空无数据元素出栈!\n"); return0;}else{S->top--;*d=S->stack[S->top];

return1;}}（5）取栈顶数据元素StackTop(SeqStackS,DataType*d)intStackTop(SeqStackS,DataType*d){if(S.top<=0){printf("栈已空!\n"); return0;}else{*d=S.stack[S.top-1]; return1;}}

测试主程序：任务：建立一个顺序栈，首先依次输入数据元素1,2,3,......,10，然后依次出栈数据元素并显示。假设该顺序栈的数据元素个数在最坏情况下不会超过100个。

#include<stdio.h>#include<stdlib.h> #defineMaxStackSize100 typedefintDataType; #include"SeqStack.h"

voidmain(void){SeqStackmyStack;inti,x;StackInitiate(&myStack);for(i=0;i<10;i++)StackPush(&myStack,i+1)StackTop(myStack,&x)printf("当前栈顶数据元素为：%d\n",x);printf("依次出栈的数据元素序列如下：\n");while(StackNotEmpty(myStack)){StackPop(&myStack,&x); printf("%d",x);} }程序运行输出结果如下：当前栈顶数据元素为：10依次出栈的数据元素序列如下：109876543214、链式栈1)链式栈

链式存储结构的栈。2)链式栈的存储结构它是以头指针为栈顶，在头指针处插入或删除，带头结点的链式栈结构：头结点an-1an-2a0∧…h栈底栈顶链栈中每个结点由两个域构成：data域和next域结点结构体定义如下：typedefstructsnode{DataTypedata;structsnode*next;}LSNode;3)链式栈的操作实现

（1）初始化StackInitiate(head)voidStackInitiate(LSNode**head){*head=(LSNode*)malloc(sizeof(LSNode)); (*head)->next=NULL;}（2）非空否StackNotEmpty(head)intStackNotEmpty(LSNode*head){if(head->next==NULL)return0;elsereturn1;}（3）入栈StackPush(head,x)intStackPush(LSNode*head,DataTypex){LSNode*p;

p=(LSNode*)malloc(sizeof(LSNode));

p->data=x;p->next=head->next;head->next=p;

return1;}（4）出栈StackPop(head,*d)intStackPop(LSNode*head,DataType*d){LSNode*p=head->next;if(p==NULL){printf("栈已空出错！"); return0;}

head->next=p->next;*d=p->data; free(p);return1;}（5）取栈顶数据元素StackTop(head,d)intStackTop(LSNode*head,DataType*d){LSNode*p=head->next; if(p==NULL) { printf("栈已空出错！"); return0; }

*d=p->data; return1;}（6）撤消链式栈内存空间Destroy(*head)voidDestroy(LSNode*head){LSNode*p,*p1;

p=head; while(p!=NULL) {p1=p; p=p->next; free(p1); }}

说明：1)链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成。

2)一般不会出现栈满情况；除非没有空间导致malloc分配失败。3)采用链栈存储方式的优点是，当栈中元素个数变化较大，准确数字难以确定时，链栈较顺序栈方便。3.2

栈应用1、括号匹配问题例：假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。解题：这是一个输入元素序列到特定输出元素序列转换问题。算法思想：算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”栈操作特点，因此可以借助一个栈来进行判断。括号匹配共有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号；（4）左右括号匹配正确。具体方法：顺序扫描算术表达式（表现为一个字符串），当遇到三种类型的左括号时让该括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈继续进行判断；若当前栈顶括号与当前扫描的括号不相同，则左右括号配对次序不正确；若字符串当前为某种类型左括号而栈已空，则右括号多于左括号；字符串循环扫描结束时，若栈非空（即栈中尚有某种类型左括号），则说明左括号多于右括号；否则，左右括号匹配正确。括号匹配共有四种情况：（1）左右括号配对次序不正确： "(())abc{[]()]"（2）右括号多于左括号： "(()))abc{[]}"（3）左括号多于右括号： "(()()abc{[]}"（4）左右括号匹配正确： "(())abc{[]}"voidExpIsCorrect(charexp[],intn){SeqStackmyStack;inti;charc;

StackInitiate(&myStack);for(i=0;i<n;i++){if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))StackPush(&myStack,exp[i]);

elseif(exp[i]==')'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='(')StackPop(&myStack,&c); elseif(exp[i]==')'&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c!='(') {printf("左右括号配对次序不正确！\n"); return; }

elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='['] StackPop(&myStack,&c);

elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='[') {printf("左右括号配对次序不正确！\n"); return; }

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='{'} StackPop(&myStack,&c);

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='{') {printf("左右括号配对次序不正确！\n"); return; } elseif(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}')) &&!StackNotEmpty(myStack)) { printf("右括号多于左括号！\n"); return; } }

if(StackNotEmpty(myStack)) printf("左括号多于右括号！\n"); else printf("左右括号匹配正确！\n");}2、表达式计算问题

表达式计算是编译系统中的基本问题，其实现方法是栈的一个典型应用。在编译系统中，要把便于人理解的表达式翻译成能正确求值的机器指令序列，通常需要先把表达式变换成机器便于理解的形式，这就要变换表达式的表示序列。假设计算机高级语言中的一个算术表达式为

A+(B-C/D)*E这种表达式称为中缀表达式，写成满足四则运算规则的相应的后缀表达式即为

ABCD/-E*+

优点：可以直接计算中缀表达式的值。

编译系统中表达式的计算分为两个步骤：（1）把中缀表达式变换成相应的后缀表达式；（2）根据后缀表达式计算表达式的值。其中，步骤（1）这种数据序列的特定变换可以利用栈来实现；步骤（2）的算法也可借助栈来实现。

中缀表达式变换为后缀表达式的算法步骤可以总结为：

(1)设置一个栈，初始时将栈顶元素置为“＃”。

(2)顺序读入中缀表达式，当读到的单词为操作数时就将其输出，并接着读下一个单词。

(3)令x1为当前栈顶运算符的变量，x2为当前扫描读到运算符的变量，当顺序从中缀表达式中读入的单词为运算符时就赋予x2，然后比较x1的优先级与x2的优先级，若x1的优先级高于x2的优先级，将x1退栈并作为后缀表达式的一个单词输出，然后接着比较新的栈顶运算符x1的优先级与x2的优先级；若x1的优先级低于x2的优先级，将x2进栈然后读下一个字符；若x1的优先级等于x2的优先级，特别处理。 如：中缀表达式A+(B-C/D)*E＃ 后缀表达式ABCD/-E*+运算符优先级关系表

把中缀表达式A+(B-C/D)*E变换成后缀表达式的过程

计算后缀表达式的值的过程仍是一个栈应用问题算法思想是：设置一个栈存放操作数，从左到右依次扫描后缀表达式，每读到一个操作数就将其进栈；每读到一个运算符就从栈顶取出两个操作数施以该运算符所代表的运算操作，并把该运算结果作为一个新的操作数入栈；此过程一直进行到后缀表达式读完，最后栈顶的操作数就是该后缀表达式的运算结果。后缀表达式ABCD/-E*+求值过程:3.3

队列1、队列的基本概念(1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。一个队列的示意图如下：队尾插入队头删除a0a1a2…an-1队头队尾数据集合:{a0,a1,…,an-1}，ai的数据类型为DataType。操作集合：（1）初始化QueueInitiate(Q)（2）非空否QueueNotEmpty(Q)（3）入队列QueueAppend(Q,x)（4）出队列QueueDelete(Q,d)（5）取队头数据元素QueueGet(Q,d)

3、顺序队列(1)顺序队列：顺序存储结构的队列。2、队列抽象数据类型(2)顺序队列的存储结构有6个存储空间的顺序队列动态示意图(a)空队列frontrear=012345CBA(b)入队列A、B、C后front=012345C(c)出队列A、B后front=012345rear=EDC(d)入队列D、E后front=012345rear=(3)顺序队列的“假溢出”问题①假溢出顺序队列因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况。

可采取四种方法：

1)采用顺序循环队列；（教材中的方法）

2)按最大可能的进队操作次数设置顺序队列的最大元素个数；（最差的方法）

3)修改出队列算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置；４)修改入队列算法，增加判断条件，当假溢出时，把队列中的数据元素向队头移动，然后完成入队列操作。②如何解决顺序队列的假溢出问题？(4)顺序循环队列的基本原理把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。顺序队列a3a2a1frontrear0123..N-1a3a2a10123N-1rearfront循环队列(5)顺序循环队列的队空和队满判断问题新问题：在顺序循环队列中，队空特征是front=rear；队满时也会是front=rear；判决条件将出现二义性！解决方案有三：①使用一个计数器记录队列中元素个数（即队列长度）；（教材中的方法）判队满：count>0&&rear==front

判队空：count==0②设标志位，出队时置０,入队时置１,则可识别当前front=rear属于何种情况判队满：tag==1&&rear==front

判队空：tag==0&&rear==front③少用一个存储单元判队满：front=＝(rear+1)%MaxQueueSize

判队空：rear==front4、顺序循环队列顺序循环队列的结构体定义如下：typedefstruct{DataTypequeue[MaxQueueSize];intrear;intfront;intcount;}SeqCQueue;（1）初始化QueueInitiate(Q)voidQueueInitiate(SeqCQueue*Q){Q->rear=0; Q->front=0;Q->count=0;}（2）非空否QueueNotEmpty(Q)intQueueNotEmpty(SeqCQueueQ){if(Q.c