数据结构栈与队列

1、1E-mail: 第8章 数据结构（2）2主要内容 数据与数据结构 线性表 栈与队列 图和树3栈与队列栈与队列是操作受限的线性表结构。线性表例如：InsertList(L,i,x)-在表L的第i个位置插入元素xDeleteFromList(L,i)-删除表L中第i个位置的元素4回顾：一. 栈的概念在顺序表结构中，插入或删除操作可以在表的任意位置进行。5 列车仅从调度站的一端进和出。一摞盘子生活中遇到的其它现象顶端取和放操作在其顶端进行“盘子线性表”：表中“元素”为盘子，但存放和取出操作限制在表的一端进行。“列车调度站线性表”：表中“元素”为列车，但进站和出站操作也限制在表的一端进行。6将限制在

2、一端进行插入和删除操作的线性表称为棧。 棧在软件设计中有着广泛的应用。利用棧可方便实现“元素”的“后进先出”功能。共同特征对上述现象抽象利用栈的“后进先出”特性进行“数制转换”问题：（22）10=（ ） 2算法：整数棧22201121 5 21 220 12 0011011除入栈、出栈操作外，栈的基本操作还有哪些？这些基本操作算法如何实现？n=22do r=n % 2; r入栈 n=n / 2; while(n!=0);while(栈非空)栈顶元素出栈并输出例：对于输入序列A,B,C，经过入栈和出棧操作，能得到的出栈序列有哪些。ABC,ACB,BAC,BCA,CBA,CAB8只有CAB是不可能

3、的。二.栈的基本操作定义及其实现置空栈-Clear(s)求棧的长度-GetLength(s)判断棧是否为空-IsEmpty(s)入栈-Push(s,x)出棧-Pop(s)取栈顶元素-GetTop(s)销毁栈-Destroy(s)9栈的基本操作包括： 用数组作为栈的存储结构-顺序栈定义栈类型（结构类型）实现栈的基本操作编写主函数进行测试10编写步骤：栈类型定义-顺序栈11例：整数棧类型定义在C中，顺序栈是用数组作为存储结构的。顺序栈类型的三要素：声明一维数组作为栈的存储空间（也可动态分配）；声明指示栈顶位置的变量；声明指示栈底位置的变量。typedef struct STACK int *sta

4、ckArray; int top; int bottom; Stack;其中，Stack为栈类型栈的元素类型定义：typedef int DataType;栈变量的定义12S棧012345679899例：定义Stack类型变量S，其栈的空间预设为100个元素。 #define MAXLEN 100 Stack s； s.stackArray= (int *)malloc(sizeof(int)*MAXLEN);空栈约定：栈顶和栈底标记为数组的0号元素位置。其中：s为整数栈变量 s.stackArray指向100元素的存储空间； s.top表示栈顶位置； s.bottom表示栈底位置。这时S栈已

5、满进栈操作-Push(S,x) 将元素X进栈，栈顶指针后移 13 整数0进栈过程0123456798990提示：进棧操作时，应检查棧满的情况。if( s-top=棧的长度) 输出信息“棧空间已满！”else s-stackArrays-top=x; s-top+=1;S棧最后一个元素代码：s-stackArrays-top=x; s-top+=1;Push(S,x)操作的完整代码入栈操作 void Push(Stack * s , int x) if( s-top=MAXLEN) printf(“棧空间已满！n”); else s-stackArrays-top=x; s-top+=1; 14

6、出栈操作-Pop(S)15提示：出棧操作时，应检查棧空的情况。if(s-tops-bottom ) s-top-; return s-stackArrays-top;else printf(“棧空间已空！n”); return -1;/失败 栈顶指针前移（即下移），使其指向当前栈顶元素返回栈顶元素0123456798990棧S s-top-; return s-stackArrays-top;此时栈空Pop(S) 操作的完整代码16int Pop(Stack *s) if(s-tops-bottom ) s-top-; return s-StackArrays-top; else printf

7、(“棧空间已空！n”); return -1;/失败 其他操作17 求栈的长度-GetLength(S) 置空栈-Clear(s)令：s-top=0; s-bottom=0;void Clear(Stack *s) s-top=0; s-bottom=0;int GetLength(Stack *s) return s-bottom-s-top;销毁栈-DestroyStack(S)void DestroyStack(Stack *s) free(s-stackArray); free(s);18Stack *CreateStack(int len)Stack *s=(Stack *)mall

8、oc(sizeof(Stack);if (s != NULL)s-stackArray = (int *)malloc(sizeof(int)*len);if (s-stackArray = NULL)printf(内存溢出!);return NULL;Clear(s);return s; 创建一个空栈-CreateStack (len)三. 栈的应用 利用顺序栈将十进制整数转换为二进制数。19例1：int main 定义栈变量s 定义整型变量n 键盘输入n s栈初始化 do 将n%2余数进s栈 n=n/2 while(n!=0); 输出“二进制数为：” while(栈非空) 输出栈顶元素 程

9、序结构顺序栈类型定义置空栈 进栈 出栈 20int main()int n;Stack *s;s = CreateStack(MAXLEN);/创建栈printf(请输入一个十进制整数:); if (s != NULL)scanf(%d, &n);printf(对应的二进制数:);do Push(s, n % 2); n = n / 2; while (n != 0);while (GetLength(s) != 0)/输出栈printf(%d, Pop(s);printf(n);DestroyStack(s); /销毁栈return 0;请补充其它代码，即可上机调试。例2:利用栈实现字符串的

10、反序输出。21int main() char ch;Stack *s;s = CreateStack(MAXLEN);while (ch = getchar() != n) Push(s, ch);while (GetLength(s) != 0) printf(%c, Pop(s);printf(n);DestroyStack(s); /销毁栈return 0;例3：检查表达式的括号是否匹配输入表达式： (a+b)*(5+c)*(22-c)/23+56) 22处理方法：从左向右扫描表达式，遇到“（”进栈，遇到“)”出栈，扫描完表达式后，若栈空，表示括号匹配。否则，（1）当扫描完表达式后-棧不

11、空（2）表达式未扫描完，需要出棧时棧是空的，此时可断定括号是不匹配的。23int main() char ch;Stack *s;s = CreateStack(MAXLEN);while (ch = getchar() != n) if (ch = () Push(s, ch);else if (ch = ) if (GetLength(s) = 0) printf(表达式括号不匹配!n); DestroyStack(s); /销毁栈 return 1; else Pop(s); if (GetLength(s) = 0) printf(表达式括号匹配!n);else printf(表达式括

12、号不匹配!n);DestroyStack(s); /销毁栈return 0;二. 队列队列也是一种操作受限的线性表。队列只允许在表的前端（队头）进行删除操作，在表的后端（队尾）进行插入操作。队列又称为先进先出（FIFO）的线性表。24生活中排队现象25队列中的两个基本操作：入队-在队尾进行 出队-在队头进行队头队尾 用数组作为队列的存储结构-顺序队列26出队BACDEF rear 队尾入队 front 队头约定：front存放实际队头的前一个位置 rear存放实际队尾元素所在的位置顺序队列类型定义2727例：整数队列类型定义在C中，顺序队列是用数组作为存储结构的。顺序队列类型的三要素：声明一维

13、数组作为队列的存储空间（也可动态分配）；声明队头变量front声明队尾变量reartypedef struct QUEUE int *queArray; int front; int rear; Queue;其中，Queue为队列类型队列的元素类型可定义：typedef int DataType;队头、队尾初值为0空队列：front=rear满队列：rear到达数组上界 队列常用的操作（1）初始化队列-ClearQue(Q)（2）求队列长度-GetQueLength(Q)（3）入队-EnQueue(Q,x)（4）出队-DelQueue(Q)（5）销毁队列-DestroyQue(Q)28 队列的

14、基本操作实现（1）初始化队列-ClearQue(q) void ClearQue( Queue * q) q-front=0; q-rear=0; 29（2）求队列长度-GetQueLength(q) int GetQueLength(Queue *q) return q-rear - q-front; 30（3）入队-EnQueue(q,x)void EnQueue(Queue *q,int x) /没有考虑队列满的情况 q-rear=q-rear+1; q-queArrayq-rear=x;31等价于： q-queArray+q-rear=x;（4）出队-DelQueue(q,data)

15、int DelQueue(Queue *q,int *data) /空队列时，删除失败，返回0；否则,删除成功，队头元素由data带回，函数返回1。 if(GetQueLength(q)=0) return 0; /空队列 else q-front=q-front+1; *data=q-queArrayq-front; return 1; 32（5）销毁队列-DestroyQue(q)void DestroyQue(Queue *q) free(q-queArray); free(q);33创建一个空队列-CreateQue (len)34Queue *CreateQue(int len)Qu

16、eue *q=(Queue *)malloc(sizeof(Queue);if (q != NULL)q-queArray = (int *)malloc(sizeof(int)*len);if (q-queArray = NULL)printf(内存溢出!);return NULL;ClearQue(q);/置空队列return q;输出整个队列-PrintQue(q)void PrintQue(Queue *q) int data; while(GetQueLength(q)0) DelQueue(q,&data); printf(%d ,data); printf(n); 35例1:使用

17、整数队列完成以下操作,1.将三个整数3，4，5依次入队；2.一个元素出队，并输出该元素；3.再入队三个整数10，11，12；4.依次输出队中所有元素直到队空。36队列的应用int main 定义队列变量queue; 创建空队列； 入队三次； 出队一次并输出； 再入队三次； 整个队列元素出队并输出37int main() const int MAXLEN=100; Queue *queue; int data; queue=CreateQue( MAXLEN); if(queue=NULL)return 1; /创建失败 EnQueue(queue,3);EnQueue(queue,4);EnQ

18、ueue(queue,5); if(DelQueue(queue,&data)=0) printf(“出队操作失败！”);return 1; else printf(“%dn”,data); EnQueue(queue,10); EnQueue(queue,11); EnQueue(queue,12); PrintQue(queue); DestroyQue(queue); return 0; 数据结构-栈与队列习题5，6，7，838第8章 补充讲义（P100）39三. 图和树 图的基本概念 带权图和最短路径 树的基本概念39树线性图图和树是非线性数据结构。图的基本概念柯尼斯堡七桥问题4017

19、36年，欧拉使用图的方法解决了柯尼斯堡七桥问题图论之父-数学家 欧拉（Euler)从图的任一点出发，经过每条边一次且仅经过1次后能回到原出发点，要求与每个点关联的边数均为偶数。图的基本概念（续）图（Graph)的概念 图是由节点和连接节点的边（Edge）所构成的图形,其中节点又称为顶点(Vertex) 图G可记为：或 其中V为图中节点的集合，E为图中边的集合。 有n个顶点和m条边的图记为（n,m)图或称为n阶图。41图的基本概念（续）42例：4个城市v1,v2,v3和v4。v1和其他3个城市都有道路连接，v2和v3之间有道路连接，画出该图并用集合表示该图。节点集合：V=V1,v2,v3,v4边

20、集合：E= （V1，V2）， （V1，v3）， （V1，v4）， （V2，v3） （由节点对构成）图的基本概念（续）无向边-不区分起点和终点的边（不带箭头）。无向图-所有边都是无向边的图。无向图中的节点对用圆括号表示43例：节点对（v1，v2）表示节点v1与节点v2的一条无向边 节点对（v1，v3）表示节点v1与节点v3的一条无向边 节点对（v1，v4）表示节点v1与节点v4的一条无向边图的基本概念（续）有向边-区分起点和终点的边（带箭头）。有向图-所有边都是有向边的图。有向图中的节点对用尖括号表示。44例：节点对表示节点v1到节点v2的一条有向边。V=V1,v2,v3,v4E=,图的基本概念

21、（续）节点的度-与节点关联的边的个数。例： 45V1的度为3V2的度为2V3的度为2V4的度为1 出度与入度（针对有向图） 由节点指向外的边的个数为出度，反之称为入度。图的基本概念（续）邻接矩阵 用于存储图的一个矩阵46V1的出度为2，入度为1V2的出度为1，入度为1V3的出度为1，入度为1V4的出度为0，入度为1 V1 V2 V3 V4V1 0 1 0 1V2 0 0 1 0V3 1 0 0 0V4 0 0 0 0例如：将上述有向图以邻接矩阵的方式存储到计算机中。首先为节点指定一个次序。这里按照节点的下标次序排列:v1,v2,v3,v4,可构成一个4*4矩阵存放。其元素值为0和1。如果vi到

22、vj之间存在一条有向边，则对应元素值为1,反之为0例：带权图和最短路径案例：学校选址47带权图和最短路径权-图中的每一条边都带有一个“非负实数”，将该数称为权。带权图-图连同它边上的权称为带权图。最短路径-在带权图中，给定两个节点vi和vj,如果vi到vj有多条路径，构成某路径的边权的和叫做该路径的“长度”；从vi到vj的所有路径中，“长度”最小的路径叫做从vi到vj的最短路径。求最短路径的Dijkstra算法。4849最短路径算法- Dijkstra50最短路径算法（续）51例：使用Dijkstra算法完成学校选址问题52求出D到各节点的最短路径求出E到各节点的最短路径计算到达D节点学生所走

23、路程的总长度计算到达E节点学生所走路程的总长度1. 求出D到各节点的最短路径53542. 求出E到各节点的最短路径55565758 图G表示的无向带权图，其中节点A-H表示8个村庄，边表示村庄之间的道路。边上的权值表示距离。图G问题：求A到F的最短距离是多少？求最短路径的算法-Dijkstra算法即求图中的节点V0到某节点V的最短路径将图中所有节点分成两部分: P标号集合和T标号集合 P标号结点-指从V0到该节点的最短路径的长度。 T标号结点-指从V0到该节点的某条路径的长度。 在Dijkstra算法中，首先将V0取为P标号节点，其余节点均为T标号节点。 然后将T标号中的节点逐步改为P标号节点，当目的节点V已被改为P标号，则找到从V0到V的一条最短路径。59Dijkstra算法思想：例：计算图G从A到F的最短路径图G首先，将起点A划归为P标号集合， A到A的距离为0，则A的P