查看“3栈和队列”的源代码
←
3栈和队列
跳转至:
导航
、
搜索
因为以下原因,你没有权限编辑本页:
您所请求的操作仅限于该用户组的用户使用:
用户
您可以查看并复制此页面的源代码:
== 栈的定义 == === 基本概念 === 定义:栈是限定仅在表尾进行插入和删除操作的线性表。栈 (Stack)是一种后进先出(last in first off,LIFO)的数据结构,又称为LIFO结构。把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的找称为空栈。 注意事项:首先它是一个线性表,也就是说,栈元素具有线性关系,即前驱后继关系。只不过它是一种特殊的线性表而已。 基本操作:栈的插入操作,叫作进栈,也称压栈、入栈。栈的删除操作,叫作出找,也有的叫作弹栈。 [[文件:zhan.jpg|缩略图]] === 进栈出栈变化形式 === n个元素进栈共有多少种出栈顺序? 我们把n个元素的出栈个数的记为f(n), 那么对于1,2,3, 我们很容易得出: f(1) = 1 //即 1 f(2) = 2 //即 12、21 f(3) = 5 //即 123、132、213、321、231 然后我们来考虑f(4), 我们给4个元素编号为a,b,c,d, 那么考虑:元素a只可能出现在1号位置,2号位置,3号位置和4号位置(很容易理解,一共就4个位置,比如abcd,元素a就在1号位置)。 分析: 1) 如果元素a在1号位置,那么只可能a进栈,马上出栈,此时还剩元素b、c、d等待操作,就是子问题f(3); 2) 如果元素a在2号位置,那么一定有一个元素比a先出栈,即有f(1)种可能顺序(只能是b),还剩c、d,即f(2), 根据乘法原理,一共的顺序个数为f(1) * f(2); 3) 如果元素a在3号位置,那么一定有两个元素比1先出栈,即有f(2)种可能顺序(只能是b、c),还剩d,即f(1),根据乘法原理,一共的顺序个数为f(2) * f(1); 4) 如果元素a在4号位置,那么一定是a先进栈,最后出栈,那么元素b、c、d的出栈顺序即是此小问题的解,即 f(3);结合所有情况,即f(4) = f(3) + f(2) * f(1) + f(1) * f(2) + f(3); 为了规整化,我们定义f(0) = 1;于是f(4)可以重新写为: f(4) = f(0)*f(3) + f(1)*f(2) + f(2) * f(1) + f(3)*f(0) 然后我们推广到n,推广思路和n=4时完全一样,于是我们可以得到: f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ... + f(n-1)*f(0) [[文件:ruzhan.png|缩略图]] == 栈的抽象数据类型 == === 栈的ADT定义 === ADT 栈(stack) Data 同线性表。元素具有相同的类型,相邻元素具有前驱和后堆关系。 Operation InitStack ( *S ):初始化操作.建立一个空栈S。 DestroyStack ( *S ):若栈存在,則销毁它。 ClearStack (*S):将栈清空。 StackEmpty ( S ):若栈为空,返回true,否則返回 false。 GetTop (S,*e):若栈存在且非空,用e返回S的栈顶元素。 Push (*S,e):若栈S存在,插入新元素e到栈S中并成为栈頂元素。 Pop (*S,*e):删除栈S中栈顶元素,并用e返回其值。 StackLength (S):返回回栈S的元素个数。 endADT == 栈的顺序存储结构及实现 == === top指针 === 定义一个top变量来指示栈顶元素在数组中的位置,这top就如同中学物理学过的游标卡尺的游标,如上图所示,它可以来回移动,意味着栈顶的top可以变大变小,但无论如何游标不能超出尺的长度。同理,若存储栈的长度为StackSize,则栈顶位置top必须小于StackSize。当栈存在一个元素时,top等于0,因此通常把空栈的判定条件定为top等于-1。 [[文件:top2.jpg|缩略图]] === 结构体定义 === #include "stdio.h" /* 存储空间初始分配量 */ #define MAXSIZE 20 /* SElemType类型根据实际情况而定,这里假设为int */ typedef int SElemType; /* 顺序栈结构 */ typedef struct { SElemType data[MAXSIZE]; int top; /* 用于栈顶指针 */ }SqStack; int main() { } === 进栈操作--push === 如图所示,进栈操作push大概分为两步: 1.栈顶指针 S->top 先自增1,给需要进栈的元素腾出内存空间; 2.再赋值。就是给对应的数组元素赋值:S->data[S->top]=e。 代码实现: /* 插入元素e为新的栈顶元素 */ Status Push(SqStack *S,SElemType e) { if(S->top == MAXSIZE -1) /* 栈满 */ { return ERROR; } S->top++; /* 栈顶指针增加一 */ S->data[S->top]=e; /* 将新插入元素赋值给栈顶空间 */ return OK; } [[文件:入栈.jpg|缩略图]] === 出栈操作--pop === 代码实现: /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */ Status Pop(SqStack *S,SElemType *e) { if(S->top==-1) return ERROR; *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */ S->top--; /* 栈顶指针减一 */ return OK; } 完整可实现代码: #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 /* 存储空间初始分配量 */ #define MAXSIZE 20 typedef int Status; /* SElemType类型根据实际情况而定,这里假设为int */ typedef int SElemType; /* 顺序栈结构 */ typedef struct { SElemType data[MAXSIZE]; int top; /* 用于栈顶指针 */ }SqStack; /* 构造一个空栈S */ Status InitStack(SqStack *S) { /* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */ S->top=-1; return OK; } /* 从栈底到栈顶依次对栈中每个元素显示 */ Status StackTraverse(SqStack S) { int i; i=0; while(i<=S.top) { visit(S.data[i++]); } printf("\n"); return OK; } Status visit(SElemType c) { printf("%d ",c); return OK; } /* 插入元素e为新的栈顶元素 */ Status Push(SqStack *S,SElemType e) { if(S->top == MAXSIZE -1) /* 栈满 */ { return ERROR; } S->top++; /* 栈顶指针增加一 */ S->data[S->top]=e; /* 将新插入元素赋值给栈顶空间 */ return OK; } /* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */ Status Pop(SqStack *S,SElemType *e) { if(S->top==-1) return ERROR; *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */ S->top--; /* 栈顶指针减一 */ return OK; } int main() { SqStack s; int opp; int j, value, e; if(InitStack(&s)==OK) { printf("顺序栈初始化成功。"); StackTraverse(s); } printf("\n1.随机给栈赋值 \n2.栈遍历 \n3.进栈 \n4.出栈"); printf("\n0.退出 \n请选择你的操作:\n"); while(opp != '0'){ scanf("%d",&opp); switch(opp){ case 1: srand(time(0)); for(j=1;j<=10;j++) { Push(&s,rand()%100+1); } StackTraverse(s); break; case 2: StackTraverse(s); break; case 3: printf("请输入需要进栈的元素:"); scanf("%d", &value); Push(&s, value); StackTraverse(s); break; case 4: Pop(&s,&e); printf("弹出的栈顶元素 e=%d\n",e); StackTraverse(s); break; case 0: exit(0); } } }
返回至
3栈和队列
。
导航菜单
个人工具
登录
命名空间
页面
讨论
变种
视图
阅读
查看源代码
查看历史
更多
搜索
导航
首页
Linux
Java
PHP
Android
ios
数据库
大数据
前端技术
基础知识
辅助技术
其他热点
git仓库
项目管理
团队博客
最近更改
帮助
实验室管理
相关制度
成长之路
全家福
学术杂谈
学术工具
我的兴趣
架构之美
教育教学
我的课程
软件综合实训
讲座
电子商务
电商平台开发
电商资料
成功案例
鲁泰在线
济南铁路局供电检测系统
工具
链入页面
相关更改
特殊页面
页面信息
MediaWiki spam
blocked by CleanTalk.