软件技术基础-栈,队列,矩阵.ppt

  1. 1、本文档共21页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
软件技术基础-栈,队列,矩阵

栈结构 栈的基本运算: 1. SETNULL(s);置空操作 2. EMPTY (s); 判空操作 3. PUSH (s,x); 压栈 4. POP(s); 弹栈 5. TOP(s); 取栈顶元素 用数组实现栈 用数组实现栈 用数组实现栈 用链表实现栈 2.2用链表实现栈 用链表实现栈 用链表实现栈 练一练 练一练 练一练 练一练 * * 段景山 * 软件技术基础 主讲:杨建军 线性结构 1 2 3 4 5 6 6 5 6 5 1、堆栈 stack 栈是特殊的线性表,仅在表的一端进行插入或删除操作 an ... a2 a1 栈顶 入栈 出栈 栈底 特点:(1)对栈内数据的操作总在栈顶进行 (2)数据进栈称为“压入”push (3)数据出栈称为“弹出”pop (4)遵循“后进先出”的原则LIFO 2.1用数组实现栈 a[max] ... a[1] a[0] ... a[top] 栈顶 a[0]为栈底,top为栈顶 (1)定义 typedef struct stack_type{ elemtype data[MAXNUM]; int top; }stack_type; (2)压入 push 当新元素入栈时,栈顶上移,新元素放在栈顶。 ... stack.top = stack.top + 1; stack.data[stack.top] = new_one; new_one 栈顶元素 所在位置 a1 a2 ... (3)弹出 pop 从栈顶移出一个数据。 a[max] ... a[1] a[0] a1 a2 栈顶 栈顶元素拷贝出栈,栈顶下移 out out = stack.data[stack.top]; stack.top = stack.top - 1; elemptype pop(stack_type *stack){ elemtype out; if(stack-top = 0) error(3); else{ out = stack-data[stack-top]; stack-top = stack-top -1; } return out; } a[top] (4)栈空判断 stack.top = = 0 stack.top 0 (5)置栈空 stack.top = -1; 栈满判断:stack.top = MAXNUM - 1; a[0] stack.top 栈顶元素所在位置 a1 a2 an …… head 栈顶在 表头 (1)定义 typedef struct lstack_type{ struct node * top; int length; }lstack_type; 入栈 出栈 top typedef struct node{ elemtype data; struct node* next; }lstack_type; (2)压入push void push(stack, new_node){ new_node-next = stack-top; stack-top = new_node; stack-length ++; } (3)弹出pop node_type * pop(stack){ node_type* out; out = stack-top; stack-top = stack-top-next; stack-length --; return out; } a1 new …… stack-top (4)栈空判断 stack.top == NULL; (5)置栈空 能否简单的使用 stack.top = NULL ? 如果栈中还有链点,必须逐个将链点占用的空间释放 void clean(stack){ node_type * temp; while( ! empty(stack)){ temp = pop(stack); free(temp); } } int empty(stack){ if(stack.top == NULL) return YES; else return NO; } 1、逐个将链点弹出 2、释放链点空间 *** 栈的应用 数制转换 十进制数向 d 进制数的转换。 反向考虑: d 进制数向十进制数的转换 例, (02504)8 = (1348)10 0×8+2 ( 0×8+2 ) ×8+5 ( ( 0×8+2 ) ×8+5 ) ×8+0 ( ( ( 0×8+2 ) ×8+5 ) ×8+0) ×8+4 = 1348 ( ( ( 0×8+2 ) ×8+5 ) ×8+0) ×8+4 = 1348 N

文档评论(0)

qwd513620855 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档