2.设计包含min函数的栈。
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
分析:既然要求“求最小”时间复杂度为O(1),所以一定要在top指针结构内记录最小量。就是在push 时将最小值
#include "stdio.h"
#include"malloc.h"
#define STACK_LEN 50
/*
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
*/
typedef struct
{
int val; // 存储值
int min;
} stack_item;
typedef struct
{
stack_item data[STACK_LEN]; //使用另一个数据结构
int top;
} stack;
void push(stack *stk, int val)//放入
{
//printf("%d",stk->top);
stk->data[++stk->top].val = val;
//printf("sssssss");
if (stk->top > 0)
{
if (val < stk->data[stk->top - 1].min)//如果当前push进的元素小于栈中最小元素
stk->data[stk->top].min = val; //把当前元素置为栈中最小元素
else //否则,不更新
stk->data[stk->top].min = stk->data[stk->top - 1].min; //新插入值后的 最小值与 插入之前最小值相同
}
else //栈 初始化 为空的情况
stk->data[stk->top].min = val;
}
int pop(stack *stk)
{
return stk->data[stk->top--].val;
}
int min(stack *stk)
{
return stk->data[stk->top].min;
}
int main()
{
int i;
int a[9]={10,7,3,3,8,5,2,6};
stack *stk;
stk=(stack*)malloc(sizeof(stack));//这里一定要
stk->top=-1;//这里需要添加
for(i=0;i<8;++i)
push(stk, a[i]);
printf("%d",min(stk));
return 0;
}
分享到:
相关推荐
01第-章第二章p1-p29.rar 网盘文件永久链接 02第三章第四章D30-p59.ram 03第五章第五章P60-P85.rar 04第六章第章第八章P85-P8113.ram 05第九章第十章p114-P137.rar 06第十章第章P138-P165.rar 07第十■章第十■章...
《网络工程师考前冲刺100题》内容简介:一直以来,计算机技术与软件专业技术资格(水平)考试(以下简称“软考”)是国内难度最高的计算机专业资格考试之一,其平均通过率在10%左右。自网络工程师开考以来,其通过率...
01 第一章 第二章P1-P29 02 第三章 第四章P30-P59 03 第五章 第五章P60-P85 04 第六章 第七章第八章P85-P8113 05 第九章 第十章P114-P137 06 第十一章 第十二章P138-P165 07 第十二章 第十二章P165-P185 08 第十三章...
[第二部分]精选微软等公司结构+算法面试100题[前41-60题]: http://download.csdn.net/source/28117034 [第1题-60题汇总]微软等数据结构+算法面试100题 http://download.csdn.net/source/2826690答案系列: 5.[最新...
3. **组合与排除**:第2题和第10题需要通过比较图形间的相似性和差异,进行去异存同或组合,以找出规律。 4. **符号规律**:第3题中,图形被看作“+”和“-”,通过横向排列形成新的图形,这是对图形符号的一种理解...
2. **第二题**:该题要求找出1到100之间能被7或11整除,但不能同时被7和11整除的数字。这个问题涉及到模运算(%),以及逻辑或(||)和逻辑非(!)操作。在C语言中,可以用`if`语句结合模运算来实现这个逻辑。 3. ...
入队时直接将元素压入第一个栈,出队时将第一个栈中的元素依次弹出并压入第二个栈,再从第二个栈中弹出元素。 ### 第58题:链表中删除特定值的节点 **题目描述**:给定一个链表和一个值,删除链表中所有值为该值的...
猿人学第二届第一题解题小记
1. 加减法:题目中多次出现,如第1题、第2题、第4题等,主要训练孩子的基本运算能力。 2. 问题解决策略:第1题要求用两种方法计算,培养孩子灵活运用数学知识解决问题的能力。 3. 应用题:第3题、第5题等,涉及实际...
第二题是奖金计算问题,需要根据利润的不同范围计算奖金提成。程序通过一系列的if-else语句来判断利润区间,并计算相应的提成比例,最终得出总奖金。这个问题考察了条件判断和数值计算的能力。 第三题要求找到一个...
尚硅谷周阳互联网大厂面试题(第2季) 脑图。包括JUC多线程并发、JVM和GC等目前大厂笔试中会考、面试中会问、工作中会用的高频难点知识。上半场,从多线程并发入手,分层递进讲解,逐步让大家掌握volatile、原子类和...
例如,第1题中的`score`数组用于存储成绩,第2题的`a`数组用于存储符合条件的数,第4题的`pp`数组用于统计字母出现的次数。数组的操作包括遍历、元素赋值、计算平均值等。 2. **函数设计**:题目中的每个问题都要求...
第2题 函数fun的功能是求出1到100之内能被7或者11整除,但不能同时被7和11整除的所有数字,并将他们放在a所指的数组中,通过n返回这些数的个数。知识点: * 循环语句的使用 * 条件语句的使用 * 数组的使用 * 整除的...
2. 减法应用题:第二题的小图书室问题,需要从总数中减去借出的数量,即90 - 43 = 47,考察的是两位数减法。 3. 数量关系理解:如第三题的合唱队问题,通过已知男生人数求女生人数,即42 - 25 = 17,需要理解整体与...
2019,尚硅谷,周阳,互联网面试题脑图,第2季,.mmap版
高中联赛难度几何题100道(精华双图版) 本资源包含100道高中联赛难度的几何题,涵盖圆、线、角、点等基本几何元素的性质和关系。本资源可以帮助学生深入理解几何知识,提高解题能力和空间想象力。 知识点: 1. ...
北航 数值分析大作业 第二题 C++ 北航 数值分析大作业 第二题 C++ 北航 数值分析大作业 第二题 C++ 北航 数值分析大作业 第二题 C++
- **第二种方案**(无忧id14):不使用额外的`isP()`函数,而是直接在`jsValue()`函数内部实现素数判断逻辑。这种方法同样通过循环遍历大于`m`的所有数,并逐个检查每个数是否为素数。 ```c void jsValue(int m, ...