大学数据结构——用C语言描述-蔡明志-大学教学资料课件PPT
收藏
资源目录
压缩包内文档预览：(预览前20页/共30页)
编号：21835942
类型：共享资源
大小：15.84MB
格式：ZIP
上传时间：2019-09-06
上传人：QQ24****1780
认证信息
个人认证
王**（实名认证）
浙江
IP属地：浙江
25
积分
- 关 键 词：
-
大学
数据结构
语言
描述
描写
蔡明志
教学
资料
课件
ppt
- 资源描述：
-
大学数据结构——用C语言描述-蔡明志-大学教学资料课件PPT,大学,数据结构,语言,描述,描写,蔡明志,教学,资料,课件,ppt
- 内容简介：
-
数据结构-用C语言描述,21世纪高等院校规划教材,蔡明志 主编,ISBN 7-5084-3428-5,数据结构课程教学内容（一）,算法分析 算法概念、示例以及算法复杂度。 数组 数组的概念、数组的表示法（上三角形和下三角形标识符、多项式表示法以及魔术方阵）。 堆栈与队列 堆栈与队列的概念、插入与删除，循环队列，堆栈与队列的应用，以及如何计算后序表达式。 链表 单向链表、循环链表、双向链表的插入、删除操作，链表的应用。,数据结构课程教学内容（二）,递归 递归的概念、递归典型范例，何时不要使用递归。 树状结构 树状结构的专有名词，二叉树，二叉树的表示方法，二叉树的遍历，以及线索二叉树。 二叉查找树 二叉查找树的概念，二叉查找树的插入与删除运算。 堆 堆的概念，mini-heap与Deap的插入与删除运算。,数据结构课程教学内容（三）,平衡二叉查找树 平衡二叉查找树的概念，AVL-tree的插入与删除运算。 2-3 tree与2-3-4 tree 2-3 tree、2-3-4tree的插入与删除运算。 B-tree m-way查找树的插入与删除运算，B-tree的插入与删除运算。 图 图的专用名词，图数据结构表示法，图的遍历，最小生成树，最短路径，拓扑排序，关键路径法。,数据结构课程教学内容（四）,排序 起泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、二叉树排序、希尔排序及基数排序。 查找 顺序查找，折半查找，哈希法。,总目录（一）,第1章 算法分析 第2章 数组 第3章 堆栈与队列 第4章 链表 第5章 递归 第6章 树状结构 第7章 二叉查找树,总目录（二）,第8章 堆 第9章 平衡二叉查找树 第10章 2-3 tree与2-3-4 tree 第11章 B-tree 第12章 图 第13章 排序 第14章 查找,谢谢大家,数据结构-用C语言描述21世纪高等院校规划教材蔡明志 主编ISBN 7-5084-3428-5数据结构课程教学内容（一）算法分析 算法概念、示例以及算法复杂度。 数组 数组的概念、数组的表示法（上三角形和下三角形标识符、多项式表示法以及魔术方阵）。 堆栈与队列 堆栈与队列的概念、插入与删除，循环队列，堆栈与队列的应用，以及如何计算后序表达式。 链表 单向链表、循环链表、双向链表的插入、删除操作，链表的应用。数据结构课程教学内容（二） 递归 递归的概念、递归典型范例，何时不要使用递归。 树状结构 树状结构的专有名词，二叉树，二叉树的表示方法，二叉树的遍历，以及线索二叉树。 二叉查找树 二叉查找树的概念，二叉查找树的插入与删除运算。 堆 堆的概念，mini-heap与Deap的插入与删除运算。数据结构课程教学内容（三） 平衡二叉查找树 平衡二叉查找树的概念，AVL-tree的插入与删除运算。 2-3 tree与2-3-4 tree 2-3 tree、2-3-4tree的插入与删除运算。 B-tree m-way查找树的插入与删除运算，B-tree的插入与删除运算。 图 图的专用名词，图数据结构表示法，图的遍历，最小生成树，最短路径，拓扑排序，关键路径法。数据结构课程教学内容（四） 排序 起泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、二叉树排序、希尔排序及基数排序。 查找 顺序查找，折半查找，哈希法。 总目录（一）第1章 算法分析第2章 数组第3章 堆栈与队列第4章 链表第5章 递归第6章 树状结构第7章 二叉查找树总目录（二）第8章 堆第9章 平衡二叉查找树第10章 2-3 tree与2-3-4 tree第11章 B-tree第12章 图第13章 排序第14章 查找第1章 算法分析,21世纪高等院校规划教材,返回总目录,1.2 2006,算法分析,关于算法 算法复杂度（Big-O）,1.3 2006,关于算法,是解决问题（problems）的有限步骤程序 利用算法可以实现顺序查找,1.4 2006,数组元素相加的算法,将数组中每个元素相加后返回总和。实现该算法的程序段如下所示： 执行次数 int sum(int arr, int n) int i, total=0; 1 for(i=0; in; i+) n+1 total+=arri; n return total; 1 上述程序段中语句的执行次数总和为1+n+1+n+1=2n+3。,1.5 2006,矩阵相乘的算法,void mul(int a, int b, int c, int n) 执行次数 Inti,j,k,sum; 1 for(i=0;in;i+) n+1 for(j=0;jn;j+) n(n+1) sum=0; n2 for (k=0;kn;k+) n2(n+1) sum=sum+aik * bkj; n3 cij = sum; n2 ,1.6 2006,折半查找的算法,int search(int data, int target, int n) int i, mid, lower=0, upper=n-1; mid=(lower+upper)/2; while(lower target) upper = mid - 1;,1.7 2006,折半查找的算法（续）,else lower = mid + 1; mid=(lower+upper)/2; ,1.8 2006,斐波那契数列（递归的程序段）,int Fibonacci(int n) if(n = 0) return 0; else if (n = 1) return 1; else return (Fibonacci(n-1) + Fibonacci(n-2); ,1.9 2006,斐波那契数列（非递归的 程序段）,int Fibonacci(int n) int prev1,prev2,item, i; if (n = 0) return 0; else if (n = 1) return 1; else ,prev2 = 0; prev1 = 1; for(i=2;i=n;i+) item = prev1 + prev2; prev2 = prev1; prev1 = item; return item; ,1.10 2006,顺序查找的算法,int search(int data,int target,int n) int i; for(i=0;in;i+) if(target = datai) return i; ,1.11 2006,顺序查找Big-O计算,最坏的情形，即要查找的给定值是表中的最后一个，因此需要n次才能查找到给定值（假设表中含有n个值） 最好的情形，此情形与第一种刚好相反，表示欲查找的给定值在第一个，故只要1次便可查找到给定值 平均情况，平均查找的次数如下面公式所示：,因此顺序查找的Big-O为O(n)。,1.12 2006,Big-O（复杂度）,算法中Big-O（复杂度）表示算法执行的时间，包括语句执行的次数和每一次执行所需的时间 如果有两个常数c与n0，当所有nn0时都满足f(n)cg(n)，则f(n)=O(g(n) 数组元素的Big-O为O(n)，起泡排序为O(n2)，而矩阵乘法为O(n3)，顺序查找为O(n)，折半查找为O(logn)，而斐波那契数列若以递归处理则为O(2n/2)，若以非递归方式处理则为O(n),1.13 2006,图,使用递归方式的斐波那契数列的示意图, 第1章 算法分析21世纪高等院校规划教材 返回总目录 算法分析关于算法算法复杂度（Big-O）关于算法是解决问题（problems）的有限步骤程序利用算法可以实现顺序查找数组元素相加的算法 将数组中每个元素相加后返回总和。实现该算法的程序段如下所示： 执行次数 int sum(int arr, int n) int i, total=0; 1 for(i=0; in; i+) n+1 total+=arri; n return total; 1 上述程序段中语句的执行次数总和为1+n+1+n+1=2n+3。 矩阵相乘的算法 void mul(int a, int b, int c, int n) 执行次数 Inti,j,k,sum; 1 for(i=0;in;i+) n+1 for(j=0;jn;j+) n(n+1) sum=0; n2 for (k=0;kn;k+) n2(n+1) sum=sum+aik * bkj; n3 cij = sum; n2 折半查找的算法int search(int data, int target, int n) int i, mid, lower=0, upper=n-1;mid=(lower+upper)/2;while(lower target) upper = mid - 1; 折半查找的算法（续） else lower = mid + 1; mid=(lower+upper)/2; 斐波那契数列（递归的程序段） int Fibonacci(int n)if(n = 0) return 0;else if (n = 1) return 1; else return (Fibonacci(n-1) + Fibonacci(n-2); 斐波那契数列（非递归的程序段） int Fibonacci(int n)int prev1,prev2,item, i;if (n = 0) return 0;else if (n = 1) return 1; else prev2 = 0; prev1 = 1; for(i=2;i=n;i+) item = prev1 + prev2; prev2 = prev1; prev1 = item; return item; 顺序查找的算法int search(int data,int target,int n)int i;for(i=0;in0时都满足f(n)cg(n)，则f(n)=O(g(n)数组元素的Big-O为O(n)，起泡排序为O(n2)，而矩阵乘法为O(n3)，顺序查找为O(n)，折半查找为O(logn)，而斐波那契数列若以递归处理则为O(2n/2)，若以非递归方式处理则为O(n) 图 使用递归方式的斐波那契数列的示意图 7.1 2006,第7章 二叉查找树,21世纪高等院校规划教材,返回总目录,7.2 2006,二叉查找树,什么是二叉查找树 二叉查找树的插入 二叉查找树的删除,7.3 2006,什么是二叉查找树,二叉查找树是二叉树加上一些限制条件所形成的，二叉查找树常被用来建立一棵树状结构的程序。 二叉查找树的定义： 二叉查找树可以是空节点集合，假使不是空集合，树中的每一节点（node）均含有一键值（key value）， 二叉查找树的特征： - 在左子树的所有键值均小于树根的键值。 - 在右子树的所有键值均大于树根的键值。 - 左子树和右子树也是二叉查找树。 - 每个键值都不一样。,二叉查找树示意图,7.4 2006,二叉查找树的插入,二叉查找树的插入： 二叉查找树的插入和删除很简单，根据二叉查找树的特征，插入某一值只要逐一比较，依据键值的大小往右或往左，便可找到此键值欲插入的位置。,例：假设有棵二叉查找树A如图7-5所示。插入48后，二叉查找树如图7-6所示。,图7-5 二叉树A示意图,图7-6 插入48后的二叉树A示意图,7.5 2006,二叉查找树的删除,删除某一节点时，若删除的是树叶节点，则直接删除之，假若删除不是树叶节点，则在左子树找一最大的节点或在右子树找一最小的节点，取代将被删除的节点如图7-8所示。,图7-8 二叉树A示意图,二叉查找树的删除的规则和其插入的规则不同，在实际操作中可以可以交互使用，防止最后的结果变成一棵倾斜的二叉查找树。,7.6 2006,删除操作示例,删除50，可以使用下列两种方法之一，如图7-9和7-10所示。,图7-9 以右子树最小的节点取代节点 50后的二叉树A示意图,图7-10 以左子树最大的节点取代节点50后的二叉树A示意图, 第7章 二叉查找树21世纪高等院校规划教材 返回总目录 二叉查找树什么是二叉查找树二叉查找树的插入二叉查找树的删除什么是二叉查找树二叉查找树是二叉树加上一些限制条件所形成的，二叉查找树常被用来建立一棵树状结构的程序。二叉查找树的定义： 二叉查找树可以是空节点集合，假使不是空集合，树中的每一节点（node）均含有一键值（key value），二叉查找树的特征： - 在左子树的所有键值均小于树根的键值。 - 在右子树的所有键值均大于树根的键值。 - 左子树和右子树也是二叉查找树。 - 每个键值都不一样。 二叉查找树示意图二叉查找树的插入二叉查找树的插入： 二叉查找树的插入和删除很简单，根据二叉查找树的特征，插入某一值只要逐一比较，依据键值的大小往右或往左，便可找到此键值欲插入的位置。例：假设有棵二叉查找树A如图7-5所示。插入48后，二叉查找树如图7-6所示。图7-5 二叉树A示意图 图7-6 插入48后的二叉树A示意图 二叉查找树的删除删除某一节点时，若删除的是树叶节点，则直接删除之，假若删除不是树叶节点，则在左子树找一最大的节点或在右子树找一最小的节点，取代将被删除的节点如图7-8所示。 图7-8 二叉树A示意图 二叉查找树的删除的规则和其插入的规则不同，在实际操作中可以可以交互使用，防止最后的结果变成一棵倾斜的二叉查找树。删除操作示例删除50，可以使用下列两种方法之一，如图7-9和7-10所示。图7-9 以右子树最小的节点取代节点50后的二叉树A示意图图7-10 以左子树最大的节点取代节点50后的二叉树A示意图 3.1 2006,第3章 堆栈与队列,21世纪高等院校规划教材,返回总目录,3.2 2006,堆栈与队列,堆栈与队列的基本概念 堆栈的插入与删除 队列的插入与删除 循环队列 堆栈与队列的应用 如何计算后序表达式,3.3 2006,堆栈与队列的基本概念,堆栈与队列是数据结构最基本的两个主题，它们的功能却是相 当强，用途相当广。 在计算机算法（algorithms）中，堆栈（stack）与队列 （queue）是常用到的数据结构。 堆栈：是一有序表（order list），其插入（insert）和删除（delete）操 作都在同一端，此端通常称之为栈顶（top）。插入一元素于堆栈， 此操作称为入栈（push），与之相反的是从堆栈删除一元素；此操作 称为出栈（pop）。由于堆栈具有后进先出的特性，所以又称堆栈是 一种后进先出（Last In First Out，LIFO）列表。 队列：也是属于线性表，与堆栈不同的是插入和删除不在同一端，删除的那 一端为队头（front），而插入的一端称为队尾（rear）。由于队列 具有先进先出（First In First Out，FIFO）的特性，因此也称队列 为先进先出列表。假若队列两端皆可做插入或删除的操作，则称之为 双端队列（double-ended queue,deque）。,3.4 2006,堆栈与队列的示意图,(a) 堆栈,（b） 队列,图3-1 堆栈与队列示意图,3.5 2006,堆栈的插入与删除,堆栈的插入：插入一个元素（push an item）到堆栈，主要考虑会不会因为插入此元素而溢出（overflow），亦即插入要考虑不可超出栈的最大容量。若没有超出，则先将top插入，再将元素填入atop中。 堆栈的删除：从堆栈删除一个元素等于出栈（pop）一个元素，此时必须注意堆栈是否为空，亦即top的值是否为-1，若不为空，表示堆栈有元素存在，此时，先将atop的元素移除，然后将top减1。,3.6 2006,堆栈的插入示意图,插入元素10于堆栈如图3-2所示：,（1）top 的起始值,（2）top加1,（3）再将元素（假设10）填入,图3-2 插入10于堆栈的示意图,3.7 2006,插入元素10于堆栈的程序段,void push(void) if(top = MAX-1) /*当堆栈已满时，显示出错误信息*/ printf(“The Stack is full n“); else top+; printf(“please enter an item to stack:“); scanf(“%d“, ,3.8 2006,从堆栈中删除元素40的示意图,如图3-3所示，从堆栈中删除元素40,（1）堆栈初始状况top值为3 （2）将a3，即40删除 （3）将top减1,图3-3 删除堆栈中的40,3.9 2006,从堆栈中删除元素40的程序段,void pop(void) if (top 0) printf(“The stack is empty n“); else printf(“pop %d from stack n“, atop); top -; ,3.10 2006,堆栈的插入和删除 程序实例,/* file name : stack.c */ /* 使用堆栈处理数据新增、删除、输出 */ #include #include #include #define MAX 100 void push_f(void); /* 入栈函数 */ void pop_f(void); /* 出栈函数 */ void list_f(void); /* 输出函数 */ char itemMAX20; int top = -1;,3.11 2006,堆栈的插入和删除 程序实例（续1）,void main(void) char option; while(1) printf(“n *n“); printf(“ insert (push)n“); printf(“ delete (pop)n“); printf(“ listn“); printf(“ quitn“); printf(“ *n“); printf(“ Please enter your choice.“); option = getche(); switch(option) ,3.12 2006,堆栈的插入和删除 程序实例（续2）,case 1: push_f(); break; case 2: pop_f(); break; case 3: list_f(); break; case 4: exit(0); ,3.13 2006,堆栈的插入和删除 程序实例（续3）,void push_f(void) if(top = MAX-1) /* 当堆栈已满时，显示错误 */ printf(“nnStack is full !n“); else top+; printf(“nn Please enter item to insert: “); gets(itemtop); ,3.14 2006,堆栈的插入和删除 程序实例（续4）,void pop_f(void) if(top 0) /* 当堆栈没有数据存在时，则显示错误 */ printf(“nn No item, stack is empty !n“); else printf(“nn Item %s deletedn“, itemtop); top-; ,3.15 2006,堆栈的插入和删除 程序实例（续5）,void list_f(void) int count = 0, i; if(top 0) printf(“nn No item, stack is emptyn“); else printf(“nn ITEMn“); printf(“ -n“); for(i = 0; i = top; i+),3.16 2006,堆栈的插入和删除 程序实例（续6）, printf(“ %-20sn“, itemi); count+; if(count % 20 = 0) getch(); printf(“ -n“); printf(“ Total item: %dn“, count); getch(); ,3.17 2006,队列的插入与删除,队列的操作行为是先进先出，此种方式类似排队，排在前面的会先被服务，因此，可以设想数组的两端分别为front和rear端，每次插入都加在rear端，而删除（即将被服务）在front端。 当rear为MAX-1时，表示数组已到达最大容量了，此时不能再加任何元素进来，反之则数组未达最大容量，因此可以插入任何元素（如图3-4所示 ）。 删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front = rear时，表示队列是空的。 上述队列是线性队列（linear queue），表示方式为Q(0MAX-1)，但此线性队列当rear到达MAX-1时，任何插入都是不允许的，因为上述插入片段程序打印出队列是满的信息，因此它没考虑队列的前面是否还有空的位子，（如图3-5所示）。,3.18 2006,队列的插入与删除示意图,图3-4 队列示意图,图3-5 rear到达MAX-1时，进行插入元素所对应的队列图,3.19 2006,队列的插入程序段,void enqueue(void) if (rear = MAX-1) printf(“The Queue is full n“); else rear+; printf(“please enter an item to queue: “); scanf(“%d“, ,3.20 2006,队列的删除程序段,删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front = rear时，表示队列是空的，实现该功能的程序段如下： void dequeue(void) if (front = rear) printf(“The queue is Empty n“); else front +; printf(“pop %d from queue n“); ,3.21 2006,循环队列,队列常常以循环队列（circle queue）来表示，即 CQ(0MAX-1)，如图3-6所示。,图3-6 循环队列示意图,循环队列的初始值为front=rear=MAX-1，当有元素要插入时，利用rear=(rear+1) % MAX语句求出rear，以便能够使rear回到前面，看看是否还有空的位置可放。,循环队列的删除，是判断front是否和rear在同一个位置，若是 则打印出循环队列是满的信息，否则，将front往前移，并插入 元素。,3.22 2006,循环队列程序实例,/* file name: cqueue.c */ /* 使用环形队列处理数据新增、删除、输出 */ #include #include #include #define MAX 20 void enqueue_f(void); /* 新增函数 */ void dequeue_f(void); /* 删除函数 */ void list_f(void); /* 输出函数 */,3.23 2006,循环队列程序实例（1）,char itemMAX20; int front = MAX-1, rear = MAX-1, tag = 0; /* tag为记忆front所在是否已储存数据，0时为没有存放数据，1 时为存放数据 */ void main(void) char option; while(1) ,3.24 2006,循环队列程序实例（2）,printf(“n *n“); printf(“ insert (enqueue)n“); printf(“ delete (dequeue)n“); printf(“ listn“); printf(“ quitn“); printf(“ *n“); printf(“ Please enter your choice.“); option = getche(); switch(option) ,3.25 2006,循环队列程序实例（3）,case 1: enqueue_f(); break; case 2: dequeue_f(); break; case 3: list_f(); break; case 4: exit(0); ,3.26 2006,循环队列程序实例（4）,void dequeue_f(void) If(front = rear ,3.27 2006,循环队列程序实例（5）,void enqueue_f(void) if(front = rear ,3.28 2006,循环队列程序实例（6）,void list_f(void) int count = 0, i; if(front = rear ,3.29 2006,循环队列程序实例（7）, printf(“ %-20sn“, itemi); printf(“ -n“); printf(“ Total item: %dn“, +count); getch(); ,3.30 2006,堆栈与队列的应用,由于堆栈具有先进后出的特性，因此凡是具有后来先处理特性的，都可以使用堆栈来解决。 堆栈还有一些很好的用途，就是如何将算术表达式由中序表达式变为后序表达式。 运算符有优先顺序与结合性，以及又有括号先处理的问题，为了避免上述的问题，编译程序将一般的中序表达式先转化为后序表达式。 假如所要解决的问题是有先进先出特性的，则宜用队列来解决，例如操作系统的工作调度（job scheduling）。,3.31 2006,堆栈应用示例子程序调用,假设主程序X调用子程序Y，子程序Y调用子程序Z，此时可以用堆栈来 存储返回（return）的地址，当子程序Z执行完后，从堆栈弹出返回 子程序Y的地址，子程序Y执行完再从堆栈弹出返回主程序X的地址， 如图3-8所示。这里所指的返回地址是调用子程序的下一条指令。,图3-8 使用堆栈来解决子程序调用的示意图,3.32 2006,堆栈与队列的应用 程序实例,/* file name: intopost.c */ /* 将数学式子由中序表示法转为后序表示法 */ #include #define MAX 20 void infix_to_postfix(char , int); /* 由中序转后序函数 */ int compare(char, char); /* 比较两个运算子函数 */ /* 在中序表示法队列及暂存堆栈中，运算符的优先级表，其优先值为INDEX/2 */,3.33 2006,堆栈与队列的应用 程序实例（续1）,char infix_priority9=#,),+,-,*,/, , (; char stack_priority8=#,(,+,-,*,/, ; void main(void) int rear = -1; char infix_qMAX; /* 储存使用者输入中序式的队列 */ printf(“*n“); printf(“ - Usable operator -n“); printf(“ : Exponentiationn“); printf(“ *: Multiply /: Dividen“);,3.34 2006,堆栈与队列的应用 程序实例（续2）,printf(“ +: Add -: Subtractionn“); printf(“ (: Left Brace ): Right Bracen“); printf(“*n“); printf(“Please enter infix expression: “); while(infix_qrear != n) infix_q+rear = getchar(); infix_qrear = #; /*队列结束时插入#为结束符号 */ printf(“Postfix expression: “); infix_to_postfix(infix_q, rear); printf(“n“); ,3.35 2006,堆栈与队列的应用 程序实例（续3）,void infix_to_postfix(char infix_q, int rear) int top = 0, ctr, tag=1; char stack_tMAX; /* 用以储存还不必输出的运算符 */ stack_ttop = #; /* 于堆栈最底下插入#为结束符号 */ for(ctr = 0; ctr = rear; ctr+) switch(infix_qctr) ,3.36 2006,堆栈与队列的应用 程序实例（续4）,/* 输入为)，则应输出堆栈内运算符，直到堆栈内为( */ case ): while(stack_ttop != () printf(“%c“, stack_ttop-); top-; break; /* 输入为#，则将堆栈内还未输出的运算符输出 */ case #: while(stack_ttop != #),3.37 2006,堆栈与队列的应用 程序实例（续5）,printf(“%c“, stack_ttop-); break; /* 输入为运算符，若小于TOP在堆栈中所指运算符， 则将堆栈所指运算符输出，若大于等于TOP在堆栈 中所指运算符，则将输入之运算符放入堆栈 */ case (: case : case *: case /:,3.38 2006,堆栈与队列的应用 程序实例（续6）,while(compare(stack_ttop, infix_qctr) printf(“%c“, stack_ttop-); stack_t+top = infix_qctr; tag=1; break; case +: case -: if(tag=1) stack_t+top = infix_qctr;,3.39 2006,堆栈与队列的应用 程序实例（续7）,tag=2; else while(compare(stack_ttop, infix_qctr) printf(“%c“, stack_ttop-); stack_t+top = infix_qctr; tag=1; break;,3.40 2006,堆栈与队列的应用 程序实例（续8）,/* 输入为操作数，则直接输出 */ default : printf(“%c“, infix_qctr); if(tag=2) printf(“%c“,stack_ttop-); tag=0; break; ,3.41 2006,堆栈与队列的应用 程序实例（续9）,/* 输入为操作数，则直接输出 */ default : printf(“%c“, infix_qctr); if(tag=2) printf(“%c“,stack_ttop-); tag=0; break; ,3.42 2006,堆栈与队列的应用 程序实例（续10）,/* 比较两运算符优先权，若输入运算符小于堆栈中运算符，则传回值为1，否则为0 */ int compare(char stack_o, char infix_o) int index_s = 0, index_i = 0; while(stack_priorityindex_s != stack_o) index_s+; while(infix_priorityindex_i != infix_o) index_i+; return index_s/2 = index_i/2 ? 1 : 0; ,3.43 2006,程序实例输出结果（1）,* - Usable operator - : Exponentiation *: Multiply /: Divide +: Add -: Subtraction (: Left Brace ): Right Brace * Please enter infix expression: a+b*(c-d)/ef-g*h Postfix expression: abcd-*ef/+gh*- *,3.44 2006,程序实例输出结果（2）,- Usable operator - : Exponentiation *: Multiply /: Divide +: Add -: Subtraction (: Left Brace ): Right Brace * Please enter infix expression: a*b-cd*e/(f+g) Postfix expression: ab*cde*fg+/- Press any key to continue,3.45 2006,程序说明（1）,这段程序的重点在于 infix_to_postfix函数。 在程序中先设定一堆栈 stack_t来存放从表达式infix_q中读入运算符或操作数，并以for循环来控制每一个运算符或操作数的读入操作，并于堆栈底下置入“#”表示结束，共有4种情况。 1输入为)时，则输出堆栈内的运算符，直到遇到(为止。 2输入为#，则将堆栈内还未输出的所有运算符输出。 3输入为运算符，其优先权若小于stack_ttop中的运算符，则将stack_ttop输出，若优先权大于等于stack_ttop存放的运算符，则将输入的运算符放入堆栈中。 4输入若为运算符，则直接输出。,3.46 2006,程序说明（2）,其中运算符的优先权是以以下数组来建立的： char infix_priority9 = #,+,-,*,/, ,(; /*在表达式中的优先权*/ char stack_priority8 = #,(,+,-,*,/, ; /*在堆栈中的优先权*/ 运算符优先权的比较由compare函数（由infix_to_postfix函数所调用）来做，在代表优先权的两个数组中，将每一个运算符在数组中所在的索引值除以2，即为运算符的优先权，如infix_priority 中，)为infix_priority1，其优先权为1除以2等于0；+为infix_priority2，其优先权为2除以2等于1，依此类推。所以在compare函数中，先找到两运算符在数组中的索引值，分别除以2来比较即可得知优先权的高低。,3.47 2006,算术表达式由中序变为后序,算术表达式由中序变为后序的步骤： 将式子中的运算单元适当的加上括号，此时须考虑运算符的运 算优先顺序。 将所有的运算符移到其对应的右括号。 将所有的括号去掉。,如将A*B/C转化为后序表达式，步骤如下： （1）(A*B)/C) （2）(A*B)/C)=(AB)*C)/ （3） AB*C/,3.48 2006,如何计算后序表达式,当将中序表达式转为后序表达式后，就可以很容 易地将此式子的值计算出来，其步骤如下： 1将此后序表达式用一个字符串表示。 2每次取一个字符，若此字符为一操作数将它push到堆栈 中，若此字符为一个运算符，则自堆栈中弹出两个操作 数并做适当的运算，若此字符为0，则转到步骤4。 3将步骤2的结果再压入到堆栈中，转到步骤2。 4弹出堆栈中的数据，此数据即为此后序表达式计算的结 果。, 第3章 堆栈与队列 21世纪高等院校规划教材 返回总目录 堆栈与队列 堆栈与队列的基本概念 堆栈的插入与删除 队列的插入与删除 循环队列 堆栈与队列的应用 如何计算后序表达式 堆栈与队列的基本概念 堆栈与队列是数据结构最基本的两个主题，它们的功能却是相 当强，用途相当广。 在计算机算法（algorithms）中，堆栈（stack）与队列 （queue）是常用到的数据结构。 堆栈：是一有序表（order list），其插入（insert）和删除（delete）操 作都在同一端，此端通常称之为栈顶（top）。插入一元素于堆栈， 此操作称为入栈（push），与之相反的是从堆栈删除一元素；此操作 称为出栈（pop）。由于堆栈具有后进先出的特性，所以又称堆栈是 一种后进先出（Last In First Out，LIFO）列表。 队列：也是属于线性表，与堆栈不同的是插入和删除不在同一端，删除的那 一端为队头（front），而插入的一端称为队尾（rear）。由于队列 具有先进先出（First In First Out，FIFO）的特性，因此也称队列 为先进先出列表。假若队列两端皆可做插入或删除的操作，则称之为 双端队列（double-ended queue,deque）。 堆栈与队列的示意图 (a) 堆栈 （b） 队列图3-1 堆栈与队列示意图 堆栈的插入与删除堆栈的插入：插入一个元素（push an item）到堆栈，主要考虑会不会因为插入此元素而溢出（overflow），亦即插入要考虑不可超出栈的最大容量。若没有超出，则先将top插入，再将元素填入atop中。堆栈的删除：从堆栈删除一个元素等于出栈（pop）一个元素，此时必须注意堆栈是否为空，亦即top的值是否为-1，若不为空，表示堆栈有元素存在，此时，先将atop的元素移除，然后将top减1。堆栈的插入示意图插入元素10于堆栈如图3-2所示： （1）top 的起始值 （2）top加1 （3）再将元素（假设10）填入 图3-2 插入10于堆栈的示意图 插入元素10于堆栈的程序段void push(void)if(top = MAX-1) /*当堆栈已满时，显示出错误信息*/ printf(The Stack is full n);else top+; printf(please enter an item to stack:); scanf(%d,&atop); 从堆栈中删除元素40的示意图如图3-3所示，从堆栈中删除元素40 （1）堆栈初始状况top值为3 （2）将a3，即40删除 （3）将top减1 图3-3 删除堆栈中的40从堆栈中删除元素40的程序段void pop(void) if (top 0) printf(The stack is empty n); else printf(pop %d from stack n, atop); top -; 堆栈的插入和删除程序实例/* file name : stack.c */ /* 使用堆栈处理数据新增、删除、输出 */#include #include #include #define MAX 100void push_f(void); /* 入栈函数 */void pop_f(void); /* 出栈函数 */void list_f(void); /* 输出函数 */ char itemMAX20; int top = -1; 堆栈的插入和删除程序实例（续1）void main(void) char option; while(1) printf(n *n); printf( insert (push)n); printf( delete (pop)n); printf( listn); printf( quitn); printf( *n); printf( Please enter your choice.); option = getche(); switch(option) 堆栈的插入和删除程序实例（续2） case 1:push_f();break;case 2:pop_f();break;case 3:list_f();break;case 4:exit(0); 堆栈的插入和删除程序实例（续3）void push_f(void) if(top = MAX-1) /* 当堆栈已满时，显示错误 */ printf(nnStack is full !n); else top+; printf(nn Please enter item to insert: ); gets(itemtop); 堆栈的插入和删除程序实例（续4）void pop_f(void) if(top 0) /* 当堆栈没有数据存在时，则显示错误 */ printf(nn No item, stack is empty !n); else printf(nn Item %s deletedn, itemtop); top-; 堆栈的插入和删除程序实例（续5）void list_f(void) int count = 0, i; if(top 0) printf(nn No item, stack is emptyn); else printf(nn ITEMn); printf( -n); for(i = 0; i = rear时，表示队列是空的。 上述队列是线性队列（linear queue），表示方式为Q(0MAX-1)，但此线性队列当rear到达MAX-1时，任何插入都是不允许的，因为上述插入片段程序打印出队列是满的信息，因此它没考虑队列的前面是否还有空的位子，（如图3-5所示）。 队列的插入与删除示意图图3-4 队列示意图图3-5 rear到达MAX-1时，进行插入元素所对应的队列图 队列的插入程序段 void enqueue(void) if (rear = MAX-1) printf(The Queue is full n); else rear+; printf(please enter an item to queue: ); scanf(%d,&arear); 队列的删除程序段 删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front = rear时，表示队列是空的，实现该功能的程序段如下： void dequeue(void) if (front = rear) printf(The queue is Empty n); else front +; printf(pop %d from queue n); 循环队列队列常常以循环队列（circle queue）来表示，即 CQ(0MAX-1)，如图3-6所示。图3-6 循环队列示意图 循环队列的初始值为front=rear=MAX-1，当有元素要插入时，利用rear=(rear+1) % MAX语句求出rear，以便能够使rear回到前面，看看是否还有空的位置可放。 循环队列的删除，是判断front是否和rear在同一个位置，若是 则打印出循环队列是满的信息，否则，将front往前移，并插入 元素。 循环队列程序实例/* file name: cqueue.c */ /* 使用环形队列处理数据新增、删除、输出 */ #include #include #include #define MAX 20void enqueue_f(void); /* 新增函数 */void dequeue_f(void); /* 删除函数 */ void list_f(void); /* 输出函数 */ 循环队列程序实例（1）char itemMAX20;int front = MAX-1, rear = MAX-1, tag = 0;/* tag为记忆front所在是否已储存数据，0时为没有存放数据，1 时为存放数据 */void main(void) char option; while(1) 循环队列程序实例（2） printf(n *n); printf( insert (enqueue)n); printf( delete (dequeue)n); printf( listn); printf( quitn); printf( *n); printf( Please enter your choice.); option = getche(); switch(option) 循环队列程序实例（3） case 1:enqueue_f();break;case 2:dequeue_f();break;case 3:list_f();break;case 4:exit(0); 循环队列程序实例（4）void dequeue_f(void) If(front = rear & tag = 0) /* 当队列中没有数据存 在时，显示错误 */ printf(nn No item, queue is empty !n); else front = (front + 1) % MAX; printf(nn Item %s deletedn, itemfront); if(front = rear) tag = 0; 循环队列程序实例（5）void enqueue_f(void) if(front = rear & tag = 1) /* 当队列已满时，显示错误 */ printf(nnQueue is full !n); else rear = (rear + 1) % MAX; printf(nn Please enter item to insert: ); gets(itemrear); if(front = rear) tag = 1; 循环队列程序实例（6）void list_f(void) int count = 0, i; if(front = rear & tag = 0) printf(nn No item, queue is emptyn); else printf(nn ITEMn); printf( -n); for(i = (front + 1) % MAX; i != rear; i = +i % MAX) printf( %-20sn, itemi); count+; if(count % 20 = 0) getch();循环队列程序实例（7） printf( %-20sn, itemi); printf( -n); printf( Total item: %dn, +count); getch(); 堆栈与队列的应用由于堆栈具有先进后出的特性，因此凡是具有后来先处理特性的，都可以使用堆栈来解决。 堆栈还有一些很好的用途，就是如何将算术表达式由中序表达式变为后序表达式。运算符有优先顺序与结合性，以及又有括号先处理的问题，为了避免上述的问题，编译程序将一般的中序表达式先转化为后序表达式。假如所要解决的问题是有先进先出特性的，则宜用队列来解决，例如操作系统的工作调度（job scheduling）。堆栈应用示例子程序调用 假设主程序X调用子程序Y，子程序Y调用子程序Z，此时可以用堆栈来 存储返回（return）的地址，当子程序Z执行完后，从堆栈弹出返回 子程序Y的地址，子程序Y执行完再从堆栈弹出返回主程序X的地址， 如图3-8所示。这里所指的返回地址是调用子程序的下一条指令。图3-8 使用堆栈来解决子程序调用的示意图 堆栈与队列的应用程序实例/* file name: intopost.c */* 将数学式子由中序表示法转为后序表示法 */#include #define MAX 20void infix_to_postfix(char , int); /* 由中序转后序函数 */int compare(char, char); /* 比较两个运算子函数 */* 在中序表示法队列及暂存堆栈中，运算符的优先级表，其优先值为INDEX/
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号