版本23和24间的区别

栈Stack

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-20 21:02:02修订的的版本23 → 
  大小: 7842
  编辑: czk
  备注:
+   ← 于2006-03-29 15:46:48修订的的版本24 → ⇥
  大小: 7823
  编辑: czk
  备注:
-删除的内容标记成这样。
+加入的内容标记成这样。
 行号 1:
-[[TableOfContents]]

"栈"版本比较

栈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. 操作实现