版本25和36间的区别 (跳过第11版)
⇤ ← 于2006-03-29 15:48:27修订的的版本25 →
大小: 8230
编辑: czk
备注:
← 于2008-02-23 15:35:49修订的的版本36 → ⇥
大小: 5170
编辑: localhost
备注: converted to 1.6 markup
删除的内容标记成这样。 加入的内容标记成这样。
行号 1: 行号 1:
= 栈Stack =

教学目标

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

教学重点和难点
 * 重点为栈逻辑结构的特点（限制一端插入删除，先进后出）以及链式栈实现时栈顶位置（栈顶在链表头部）的选择
 * 难点为栈在表达式分析中的应用		 ## page was renamed from 栈和队列
<<TableOfContents>>
= 栈 =
行号 15: 行号 6:
   栈是一种特殊的线性表。对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行。

   进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。

   栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。
 栈(Stack)是一种线性的逻辑结构，但是
 * 它的插入运算和删除运算均在同一端进行。
 * 进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。
 * 栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。
行号 25: 行号 14:
   attachment:stack.jpg    {{attachment:stack.jpg}}
行号 217: 行号 206:

= 队列Queue =

== 逻辑结构 ==
只允许在一端插入元素，在另一端删除元素的线性表。

队列具有先进先出的特性

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

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

== 顺序实现(循环队列) ==

=== 存储结构 ===
{{{#!cplusplus
#define MAXSIZE 100
typedef int elem_type;
struct seq_queue{
    elem_type elem[MAXSIZE]; //元素的存储空间
    int front; //第一个元素位置
    int rear; //最后一个元素的下一个位置
};
typedef struct seq_queue seq_queue;

}}}

=== 操作实现 ===
初始化
{{{#!cplusplus
void init(seq_queue *q)
{
   q->rear = 0;
   q->front = 0;
}
}}}

入队操作
{{{#!cplusplus
void push(seq_queue *q, elem_type e)
{
   q->elem[q->rear] = e;
   q->rear = (q->rear+1) % MAXSIZE;
}
}}}

出队操作
{{{#!cplusplus
elem_type pop(seq_queue *q)
{
   int pos = q->front;
   q->front = (q->front + 1) % MAXSIZE;
   return q->elem[pos];
}
}}}

取队首
{{{#!cplusplus
elem_type get_head() {
   return q->elem[q->front];
}
}}}

判断是否为空
{{{#!cplusplus
bool is_empty(seq_queue *q)
{
   return q->rear == q->front;
}
}}}

判断是否满
{{{#!cplusplus
bool is_full(seq_queue *q)
{
   return (q->rear+1)%MAXSIZE == q->front;
}
}}}


== 链式实现(单循环链表实现) ==
=== 存储结构定义 ===
数据结构定义同带头结点的循环单链表。
{{{#!cplusplus
typedef int elem_type;
struct node {
   elem_type data;
   struct node *next;
};
typedef struct node node;
typedef struct node *link_list
struct link_queue {
   node *front;
   node *rear;
};
typedef struct link_queue link_queue;
}}}

=== 操作实现 ===
初始化
{{{#!cplusplus
void init(link_queue *q){
   q->front = (node*)malloc(sizeof(node));
   q->front->next = NULL;
   q->rear = q->front;
}
}}}

入队
{{{#!cplusplus
void push(link_queue *q, elem_type e){
   node *p = (node *)malloc(sizeof(node));
   p->data = e;
   p->next = NULL;
   q->rear->next = p;
   q->rear = p;
}
}}}

出队
{{{#!cplusplus
elem_type pop(link_queue *q){
   node *p = q->front->next;
   elem_type e = p->data;
   q->front->next = p->next;
   if( q->rear == p)
      q->rear = q->front;
   free(p);
   return e;
}
}}}

判断空
{{{#!cplusplus
int is_empty(link_queue *q) {
   return q->front == q->rear;
}
}}}

取队首
{{{#!cplusplus
elem_type get_top(link_queue *q) {
   return q->front->next->data;
}
}}}

目录

  1. 栈
    1. 逻辑结构
    2. 操作
    3. 顺序实现（顺序栈）
      1. 存储结构定义
      2. 算法实现
    4. 链式实现
      1. 存储结构结构定义
      2. 算法实现
    5. 应用
      1. 括号匹配
        1. 问题描述
        2. 算法思路
        3. 算法实现
      2. 算术表达式求值
      3. 递归算法改非递归算法

栈

1. 逻辑结构

栈(Stack)是一种线性的逻辑结构，但是

  • 它的插入运算和删除运算均在同一端进行。
  • 进行插入和删除的那一端称为栈顶，另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。

  • 栈具有“先进后出”（FILO:Fisrt In Last Out）、“后进先出”的特性。

实例

  • 一叠饭碗

图示

  • 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. 算法思路

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

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. 递归算法改非递归算法

栈 (2008-02-23 15:35:49由localhost编辑)

ch3n2k.com | Copyright (c) 2004-2020 czk.