版本27和28间的区别

栈Stack

教学目标

依据《数据结构》教学大纲，设定以下教学目标：
理解栈的定义和特点
掌握栈的两种实现方式
了解栈的简单应用

教学重点和难点

重点为栈逻辑结构的特点（限制一端插入删除，先进后出）以及链式栈实现时栈顶位置（栈顶在链表头部）的选择
难点为栈在表达式分析中的应用

教学方法

因为栈与线性表非常相似，所以让学生通过与原有知识内容的比较，引申出新的知识。
通过课堂讨论，不单知道它是怎么实现的，还要理解它为什么是这样实现的。
根据学生普遍程序设计能力弱的特点，在讲解程序中使用黑板来带领学生一步一步写出程序。

教学手段

使用幻灯片展示基本概念、重要结论以及最终的程序实现，使用黑板来引导学生写出程序，使用计算机运行实例程序。

学习方法

根据已有的知识和新教授的概念，推出其实现的方法。
根据原理，与老师一起动手，一步一步得到程序实现。
培养学生计算机程序设计的基本思维，使用栈这种基本数据结构来解决实际问题的能力。

教学过程

新课导入：因为栈与前一章线性表有相同的逻辑结构，所以通过与线性表的比较导入栈的概念：“线性表是一种可以在任意位置进行插入和删除的线性结构，但是实际接触的线性结构中不都是这样的，比如一叠碗碟，铁路调度站，子弹夹等。”通过生活中这些的实例来对栈有一个初步的感性认识。
概念部分：通过实例给出栈的定义，并用图形来形象地表示栈的逻辑结构，在图上讲解栈顶、栈底的概念，出栈、入栈的基本操作。讲解操作中突出先进后出的顺序关系。最后给出栈的抽象数据类型（ADT）来完整的认识栈的逻辑结构及其相关的操作。
实现部分：因为学生已经掌握的线性表的实现方法，而栈与线性表非常类似，所以通过栈与与线性表的比较，让学生自己得出栈的两种实现方式：顺序的和链式的。顺序栈的实现方法与顺序表雷同。链式栈使用单链表来实现，就栈顶在单链表的头部还是尾部的问题展开课堂讨论，并得出结论：栈顶是在练表的头部而不是尾部。从而让学生理解链式栈为什么是这样子的。在讲解程序时，使用黑板与学生一起将程序一步一步从无到有的完成。
应用部分：就栈的应用进行举例，包括：数制转换，括号匹配，表达式求值等。

检测训练

为更进一步理解栈的逻辑结构，理解入栈和出栈顺序的关系，让学生练习列举一组元素入栈后各种不同的出栈顺序。
为了掌握栈的应用，练习使用栈来实现回文判断。

总结巩固

让学生思考和讨论栈在实际中还可以用在哪些地方，来结束这次课的内容。最后布置作业和实验习题。

板书设计

1. 逻辑结构

栈是一种特殊的线性表。对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行。进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。
栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。

实例

一叠饭碗

图示

attachment:stack.jpg

2. 操作

init(st) 初始化
is_empty(st)判断栈是否为空
get_top(st) 取得栈顶结点值
push(st, x) 栈的插入操作
pop(st) 栈的删除操作

3. 顺序实现（顺序栈）

栈的顺序存储方式实现又称作顺序栈栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行，所以同顺序表一样也可用一维数组表示。

3.1. 存储结构定义

用数组定义的顺序栈

   1 #define MAXSIZE 100
   2 typedef int elem_type;
   3 struct seq_stack{
   4     elem_type elem[MAXSIZE]; //栈的存储空间
   5     int size; //栈中元素的个数
   6 };
   7 typedef struct seq_stack seq_stack;

3.2. 算法实现

顺序栈初始化

   1 void init ( seq_stack * st )
   2 {
   3     st->size=0;
   4 }

判断栈是否为空

   1 int is_empty(seq_stack *st)
   2 {
   3     return st->size==0;
   4 }

获取顺序栈栈顶元素

   1 elem_type get_top(seq_stack *st)
   2 {
   3    return st->elem[st->size-1];
   4 }

入栈

   1 void push(seq_stack *st, elem_type x)
   2 {
   3     if(st->size < MAXSIZE) {
   4         st->elem[st->size]=x;
   5         st->size++;
   6     }
   7 }

出栈

   1 elem_type pop(seq_stack *st)
   2 {
   3     return st->elem[--st->size];
   4 }

打印栈

   1 void print_stack (seq_stack *st)
   2 {
   3    int i;
   4    for(i = 0; i < st->size; i++) 
   5        printf("%5d", st->elem[i]);
   6 }

判断顺序栈是否已满

   1 int is_full(seq_stack *st) {
   2    return st->size == MAXSIZE;
   3 }

4. 链式实现

栈的链式存储称为链式栈。链式栈就是一个特殊的单链表，对于这特殊的单链表，它的插入和删除只在单链表的头部进行。这里采用带头结点的单链表实现。

4.1. 存储结构结构定义

数据结构定义同带头结点的单链表。

   1 typedef int elem_type;
   2 struct node {
   3    elem_type data;
   4    struct node *next;
   5 };
   6 typedef struct node node;
   7 typedef struct node *link_list

4.2. 算法实现

初始化

同带头结点的单链表

取栈顶元素

   1 ElemType get_top(node *head) {
   2    return head->next->data;
   3 }

入栈

   1 void push(node *head, ElemType x){
   2    Node*p=(Node*)malloc(sizeof(Node));
   3    p->data=x;
   4    p->next=head->next;
   5    head->next = p;
   6 }

出栈

   1 ElemType pop(node *head) {
   2    Node *p = head->next;
   3    ElemType x = p->data;
   4    head->next = p->next;
   5    free(p);
   6    return x;
   7 }

5. 应用

5.1. 括号匹配

5.1.1. 问题描述

设一个表达式中可以包含三种括号：小括号、中括号和大括号，各种括号之间允许任意嵌套，如小括号内可以嵌套中括号、大括号，但是不能交叉。举例如下：

  ([]{})  正确的
  ([()])  正确的
  {([])}  正确的
  {[(])}  不正确的
  {(}[])  不正确的

5.1.2. 算法思路

自左向右扫描一个表达式，当遇到的左括号，都期待后面有一个和它对应的右括号与之匹配。我们将所遇到的开括号存放入一个栈中，等待匹配。
当遇到一个右括号时，就查看这个栈的栈顶结点，如果它们匹配，则删除栈顶结点，如果不匹配，则说明表达式中括号是不匹配的。
如果扫描它整个表达式后，这个栈是空的，则说明表达式中的括号是匹配的，否则表达式的括号是不匹配的。

5.1.3. 算法实现

   1 int match_kuohao (char *s) {
   2     int i;
   3     seq_stack st;
   4     init_stack(&st);
   5     for(i = 0; s[i]!='\0'; i++) {
   6         switch (s[i]) {
   7         case '{': case '[': case '(':
   8             push(&st, s[i]); break;
   9         case '}':
  10             if(!is_empty(&st)&&get_top(&st)=='{')
  11                 { pop(&st);break; } else return 0;
  12         case ']':
  13             if(!is_empty(&st)&&get_top(&st)=='[')
  14                 { pop(&st);break; } else return 0;
  15         case ')':
  16             if(!is_empty(&st)&&get_top(&st)=='(')
  17                 { pop(&st);break; } else return 0;
  18         }
  19     }
  20     return  is_empty(&st);
  21 }

5.2. 算术表达式求值

对简单的中缀表达式进行求值

从左到右扫描表达式，进行如下处理： 1. 遇到运算数进operand栈 1. 遇到运算符，与operator栈顶运算符比较优先级

如果比栈顶运算优先级高，则入栈。
否则operator出栈，operand出栈，进行运算，结果入栈。重做2

5.3. 递归算法改非递归算法

队列Queue

1. 逻辑结构

只允许在一端插入元素，在另一端删除元素的线性表。

队列具有先进先出的特性

插入的一端称作队尾，删除的一端称为队头。

2. 操作

init_queue 初始化
is_empty 判断空
is_full 判断满
enter_queue 入队列
delete_queue 出队列
get_head 取队列头部元素

3. 顺序实现(循环队列)

3.1. 存储结构

   1 #define MAXSIZE 100
   2 typedef int elem_type;
   3 struct seq_queue{
   4     elem_type elem[MAXSIZE]; //元素的存储空间
   5     int front; //第一个元素位置
   6     int rear; //最后一个元素的下一个位置
   7 };
   8 typedef struct seq_queue seq_queue;

3.2. 操作实现

初始化

   1 void init(seq_queue *q) 
   2 {
   3    q->rear = 0;
   4    q->front = 0;
   5 }

入队操作

   1 void push(seq_queue *q, elem_type e) 
   2 {
   3    q->elem[q->rear] = e;
   4    q->rear = (q->rear+1) % MAXSIZE;
   5 }

出队操作

   1 elem_type pop(seq_queue *q) 
   2 {
   3    int pos = q->front;
   4    q->front = (q->front + 1) % MAXSIZE;
   5    return q->elem[pos];
   6 }

取队首

   1 elem_type get_head() {
   2    return q->elem[q->front];
   3 }

判断是否为空

   1 bool is_empty(seq_queue *q)
   2 {
   3    return q->rear == q->front;
   4 }

判断是否满

   1 bool is_full(seq_queue *q)
   2 {
   3    return (q->rear+1)%MAXSIZE == q->front;
   4 }

4. 链式实现(单循环链表实现)

4.1. 存储结构定义

数据结构定义同带头结点的循环单链表。

   1 typedef int elem_type;
   2 struct node {
   3    elem_type data;
   4    struct node *next;
   5 };
   6 typedef struct node node;
   7 typedef struct node *link_list
   8 struct link_queue {
   9    node *front;
  10    node *rear;
  11 };
  12 typedef struct link_queue link_queue;

4.2. 操作实现

初始化

   1 void init(link_queue *q){
   2    q->front = (node*)malloc(sizeof(node));
   3    q->front->next = NULL;
   4    q->rear = q->front;
   5 }

入队

   1 void push(link_queue *q, elem_type e){
   2    node *p = (node *)malloc(sizeof(node));
   3    p->data = e;
   4    p->next = NULL;
   5    q->rear->next = p;
   6    q->rear = p;   
   7 }

出队

   1 elem_type pop(link_queue *q){
   2    node *p = q->front->next;
   3    elem_type e = p->data;
   4    q->front->next = p->next;
   5    if( q->rear == p)
   6       q->rear = q->front;
   7    free(p);
   8    return e;
   9 }

判断空

   1 int is_empty(link_queue *q) {
   2    return q->front == q->rear;
   3 }

取队首

   1 elem_type get_top(link_queue *q) {
   2    return q->front->next->data;
   3 }

-  ⇤ ← 于2006-03-29 15:53:55修订的的版本27 → 
  大小: 10938
  编辑: czk
  备注:
+   ← 于2006-03-29 15:54:42修订的的版本28 → ⇥
  大小: 10943
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 29:
-   新课导入：因为栈与前一章线性表有相同的逻辑结构，所以通过与线性表的比较导入栈的概念：“线性表是一种可以在任意位置进行插入和删除的线性结构，但是实际接触的线性结构中不都是这样的，比如一叠碗碟，铁路调度站，子弹夹等。”通过生活中这些的实例来对栈有一个初步的感性认识。

   概念部分：通过实例给出栈的定义，并用图形来形象地表示栈的逻辑结构，在图上讲解栈顶、栈底的概念，出栈、入栈的基本操作。讲解操作中突出先进后出的顺序关系。最后给出栈的抽象数据类型（ADT）来完整的认识栈的逻辑结构及其相关的操作。

   实现部分：因为学生已经掌握的线性表的实现方法，而栈与线性表非常类似，所以通过栈与与线性表的比较，让学生自己得出栈的两种实现方式：顺序的和链式的。顺序栈的实现方法与顺序表雷同。链式栈使用单链表来实现，就栈顶在单链表的头部还是尾部的问题展开课堂讨论，并得出结论：栈顶是在练表的头部而不是尾部。从而让学生理解链式栈为什么是这样子的。在讲解程序时，使用黑板与学生一起将程序一步一步从无到有的完成。

   应用部分：就栈的应用进行举例，包括：数制转换，括号匹配，表达式求值等。
+ * 新课导入：因为栈与前一章线性表有相同的逻辑结构，所以通过与线性表的比较导入栈的概念：“线性表是一种可以在任意位置进行插入和删除的线性结构，但是实际接触的线性结构中不都是这样的，比如一叠碗碟，铁路调度站，子弹夹等。”通过生活中这些的实例来对栈有一个初步的感性认识。

 * 概念部分：通过实例给出栈的定义，并用图形来形象地表示栈的逻辑结构，在图上讲解栈顶、栈底的概念，出栈、入栈的基本操作。讲解操作中突出先进后出的顺序关系。最后给出栈的抽象数据类型（ADT）来完整的认识栈的逻辑结构及其相关的操作。

 * 实现部分：因为学生已经掌握的线性表的实现方法，而栈与线性表非常类似，所以通过栈与与线性表的比较，让学生自己得出栈的两种实现方式：顺序的和链式的。顺序栈的实现方法与顺序表雷同。链式栈使用单链表来实现，就栈顶在单链表的头部还是尾部的问题展开课堂讨论，并得出结论：栈顶是在练表的头部而不是尾部。从而让学生理解链式栈为什么是这样子的。在讲解程序时，使用黑板与学生一起将程序一步一步从无到有的完成。

 * 应用部分：就栈的应用进行举例，包括：数制转换，括号匹配，表达式求值等。
 行号 39:
-   为更进一步理解栈的逻辑结构，理解入栈和出栈顺序的关系，让学生练习列举一组元素入栈后各种不同的出栈顺序。为了掌握栈的应用，练习使用栈来实现回文判断。
+ * 为更进一步理解栈的逻辑结构，理解入栈和出栈顺序的关系，让学生练习列举一组元素入栈后各种不同的出栈顺序。
 * 为了掌握栈的应用，练习使用栈来实现回文判断。
-行号 42:
+行号 43:
-   让学生思考和讨论栈在实际中还可以用在哪些地方，来结束这次课的内容。最后布置作业和实验习题。
+ * 让学生思考和讨论栈在实际中还可以用在哪些地方，来结束这次课的内容。最后布置作业和实验习题。

"栈"版本比较

栈Stack

1. 逻辑结构

2. 操作

3. 顺序实现（顺序栈）

3.1. 存储结构定义

3.2. 算法实现

4. 链式实现

4.1. 存储结构结构定义

4.2. 算法实现

5. 应用

5.1. 括号匹配

5.1.1. 问题描述

5.1.2. 算法思路

5.1.3. 算法实现

5.2. 算术表达式求值

5.3. 递归算法改非递归算法

队列Queue

1. 逻辑结构

2. 操作

3. 顺序实现(循环队列)

3.1. 存储结构

3.2. 操作实现

4. 链式实现(单循环链表实现)

4.1. 存储结构定义

4.2. 操作实现