31
备注:
|
8231
|
删除的内容标记成这样。 | 加入的内容标记成这样。 |
行号 1: | 行号 1: |
在这里详述 栈和队列. | = 栈Stack = 教学目标 依据《数据结构》教学大纲,设定以下教学目标: * 理解栈的定义和特点 * 掌握栈的两种实现方式 * 了解栈的简单应用 教学重点和难点 * 重点为栈逻辑结构的特点(限制一端插入删除,先进后出)以及链式栈实现时栈顶位置(栈顶在链表头部)的选择 * 难点为栈在表达式分析中的应用 == 逻辑结构 == 栈是一种特殊的线性表。对于这种线性表规定它的插入运算和删除运算均在线性表的同一端进行。 进行插入和删除的那一端称为栈顶,另一端称为栈底。栈的插入操作和删除操作也分别简称进栈和出栈。 栈具有“先进后出”(FILO:Fisrt In Last Out)、“后进先出”的特性。 实例 一叠饭碗 图示 attachment:stack.jpg == 操作 == * init(st) 初始化 * is_empty(st)判断栈是否为空 * get_top(st) 取得栈顶结点值 * push(st, x) 栈的插入操作 * pop(st) 栈的删除操作 == 顺序实现(顺序栈) == 栈的顺序存储方式实现又称作顺序栈 栈的顺序存储方式就是在顺序表的基础上对插入和删除操作限制它们在顺序表的同一端进行,所以同顺序表一样也可用一维数组表示。 === 存储结构定义 === 用数组定义的顺序栈 {{{#!cplusplus #define MAXSIZE 100 typedef int elem_type; struct seq_stack{ elem_type elem[MAXSIZE]; //栈的存储空间 int size; //栈中元素的个数 }; typedef struct seq_stack seq_stack; }}} === 算法实现 === 顺序栈初始化 {{{#!cplusplus void init ( seq_stack * st ) { st->size=0; } }}} 判断栈是否为空 {{{#!cplusplus int is_empty(seq_stack *st) { return st->size==0; } }}} 获取顺序栈栈顶元素 {{{#!cplusplus elem_type get_top(seq_stack *st) { return st->elem[st->size-1]; } }}} 入栈 {{{#!cplusplus void push(seq_stack *st, elem_type x) { if(st->size < MAXSIZE) { st->elem[st->size]=x; st->size++; } } }}} 出栈 {{{#!cplusplus elem_type pop(seq_stack *st) { return st->elem[--st->size]; } }}} 打印栈 {{{#!cplusplus void print_stack (seq_stack *st) { int i; for(i = 0; i < st->size; i++) printf("%5d", st->elem[i]); } }}} 判断顺序栈是否已满 {{{#!cplusplus int is_full(seq_stack *st) { return st->size == MAXSIZE; } }}} == 链式实现 == 栈的链式存储称为链式栈。链式栈就是一个特殊的单链表,对于这特殊的单链表,它的插入和删除只在单链表的头部进行。 这里采用带头结点的单链表实现。 === 存储结构结构定义 === 数据结构定义同带头结点的单链表。 {{{#!cplusplus typedef int elem_type; struct node { elem_type data; struct node *next; }; typedef struct node node; typedef struct node *link_list }}} === 算法实现 === 初始化 同带头结点的单链表 取栈顶元素 {{{#!cplusplus ElemType get_top(node *head) { return head->next->data; } }}} 入栈 {{{#!cplusplus void push(node *head, ElemType x){ Node*p=(Node*)malloc(sizeof(Node)); p->data=x; p->next=head->next; head->next = p; } }}} 出栈 {{{#!cplusplus ElemType pop(node *head) { Node *p = head->next; ElemType x = p->data; head->next = p->next; free(p); return x; } }}} == 应用 == === 括号匹配 === ==== 问题描述 ==== 设一个表达式中可以包含三种括号:小括号、中括号和大括号,各种括号之间允许任意嵌套,如小括号内可以嵌套中括号、大括号,但是不能交叉。举例如下: {{{ ([]{}) 正确的 ([()]) 正确的 {([])} 正确的 {[(])} 不正确的 {(}[]) 不正确的 }}} ==== 算法思路 ==== 1. 自左向右扫描一个表达式,当遇到的左括号,都期待后面有一个和它对应的右括号与之匹配。我们将所遇到的开括号存放入一个栈中,等待匹配。 1. 当遇到一个右括号时,就查看这个栈的栈顶结点,如果它们匹配,则删除栈顶结点,如果不匹配,则说明表达式中括号是不匹配的。 1. 如果扫描它整个表达式后,这个栈是空的,则说明表达式中的括号是匹配的,否则表达式的括号是不匹配的。 ==== 算法实现 ==== {{{#!cplusplus int match_kuohao (char *s) { int i; seq_stack st; init_stack(&st); for(i = 0; s[i]!='\0'; i++) { switch (s[i]) { case '{': case '[': case '(': push(&st, s[i]); break; case '}': if(!is_empty(&st)&&get_top(&st)=='{') { pop(&st);break; } else return 0; case ']': if(!is_empty(&st)&&get_top(&st)=='[') { pop(&st);break; } else return 0; case ')': if(!is_empty(&st)&&get_top(&st)=='(') { pop(&st);break; } else return 0; } } return is_empty(&st); } }}} === 算术表达式求值 === 对简单的中缀表达式进行求值 从左到右扫描表达式,进行如下处理: 1. 遇到运算数进operand栈 1. 遇到运算符,与operator栈顶运算符比较优先级 * 如果比栈顶运算优先级高,则入栈。 * 否则operator出栈,operand出栈,进行运算,结果入栈。重做2 === 递归算法改非递归算法 === = 队列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; } }}} |
栈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. 存储结构定义
用数组定义的顺序栈
3.2. 算法实现
顺序栈初始化
判断栈是否为空
获取顺序栈栈顶元素
入栈
出栈
打印栈
判断顺序栈是否已满
4. 链式实现
- 栈的链式存储称为链式栈。链式栈就是一个特殊的单链表,对于这特殊的单链表,它的插入和删除只在单链表的头部进行。 这里采用带头结点的单链表实现。
4.1. 存储结构结构定义
数据结构定义同带头结点的单链表。
4.2. 算法实现
初始化
- 同带头结点的单链表
取栈顶元素
入栈
出栈
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. 存储结构
3.2. 操作实现
初始化
入队操作
出队操作
取队首
判断是否为空
判断是否满
4. 链式实现(单循环链表实现)
4.1. 存储结构定义
数据结构定义同带头结点的循环单链表。
4.2. 操作实现
初始化
入队
出队
判断空
取队首