笔记
2026-06-26 22:39:30
发布于:云南
高精度算法
一、什么是高精度算法
C++中的int最大约21亿,long long最大约9.22×10¹⁸。当需要计算远超这个范围的数(比如100位的数字)时,普通数据类型存不下。高精度算法的核心思想是:用数组的每个元素存储大数的一位数字,然后模拟人工手算的过程进行运算。
通常我们用字符串读入大数,逆序存入数组(个位放在下标1,十位放在下标2……这样方便进位)。
二、高精度加法
原理:从个位开始逐位相加,满10进1。比如123+456,个位3+6=9,十位2+5=7,百位1+4=5,结果是579。
步骤:
- 用字符串读入两个大数
- 逆序存入整型数组
- 从低位到高位逐位相加并处理进位
- 逆序输出结果
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN];
char s1[MAXN],s2[MAXN];
int main() {
scanf("%s %s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
int len=max(l1,l2);
for(int i=1;i<=len;i++) {
c[i]+=a[i]+b[i];
if(c[i]>=10) {
c[i]-=10;
c[i+1]++;
}
}
if(c[len+1]>0) len++;
for(int i=len;i>=1;i--) {
printf("%d",c[i]);
}
printf("\n");
return 0;
}
三、高精度减法
原理:从个位开始逐位相减,如果被减数某位小于减数对应位,就向高位借1当10。
步骤:
- 先比较两个数的大小,确保大数减小数(如果结果是负数,记录符号)
- 逆序存入数组
- 逐位相减,不够就借位
- 去除前导零后输出
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN];
char s1[MAXN],s2[MAXN];
int cmp(char x[],char y[]) {
int lx=strlen(x),ly=strlen(y);
if(lx!=ly) return lx>ly;
for(int i=0;i<lx;i++) {
if(x[i]!=y[i]) return x[i]>y[i];
}
return 1;
}
int main() {
scanf("%s %s",s1,s2);
int sign=1;
if(!cmp(s1,s2)) {
sign=-1;
swap(s1,s2);
}
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
int len=l1;
for(int i=1;i<=len;i++) {
if(a[i]<b[i]) {
a[i]+=10;
a[i+1]--;
}
c[i]=a[i]-b[i];
}
while(len>1&&c[len]==0) len--;
if(sign==-1) printf("-");
for(int i=len;i>=1;i--) {
printf("%d",c[i]);
}
printf("\n");
return 0;
}
四、高精度乘法
原理:模拟竖式乘法。a的第i位乘以b的第j位,结果应累加到c的第i+j-1位。比如123×45,3×5=15放在第1位,3×4=12放在第2位,2×5=10放在第2位……最后统一进位。
步骤:
- 逆序存入数组
- 双重循环逐位相乘并累加
- 统一处理进位
- 去除前导零后输出
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN*2];
char s1[MAXN],s2[MAXN];
int main() {
scanf("%s %s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
for(int i=1;i<=l1;i++) {
for(int j=1;j<=l2;j++) {
c[i+j-1]+=a[i]*b[j];
}
}
int len=l1+l2;
for(int i=1;i<=len;i++) {
if(c[i]>=10) {
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
while(len>1&&c[len]==0) len--;
for(int i=len;i>=1;i--) {
printf("%d",c[i]);
}
printf("\n");
return 0;
}
五、高精度除法(高精除以低精)
原理:从最高位开始逐位处理。每次用上一位的余数乘以10加上当前位,然后除以除数,得到当前位的商,余数留给下一位。
步骤:
- 用字符串存储被除数(不逆序,因为从高位开始处理)
- 从高位到低位逐位计算
- 去除前导零后输出商和余数
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],c[MAXN];
char s[MAXN];
int main() {
int b;
scanf("%s %d",s,&b);
int l=strlen(s);
for(int i=1;i<=l;i++) {
a[i]=s[i-1]-'0';
}
int r=0;
for(int i=1;i<=l;i++) {
int cur=r*10+a[i];
c[i]=cur/b;
r=cur%b;
}
int st=1;
while(st<l&&c[st]==0) st++;
for(int i=st;i<=l;i++) {
printf("%d",c[i]);
}
printf("\n");
printf("%d\n",r);
return 0;
}
六、高精度除法(高精除以高精)
原理:用减法模拟除法。对于每一位,用被除数减去除数,能减多少次,该位商就是多少。为了提升效率,采用倍增思想,每次把除数扩大10倍来试商。
步骤:
- 判断被除数是否小于除数,若是则商0
- 从最高位开始,每次将除数左移(即乘以10的幂次)
- 用被除数不断减去除数,统计次数作为该位商
- 更新被除数,继续下一位
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],b[MAXN],c[MAXN],t[MAXN];
char s1[MAXN],s2[MAXN];
int cmpArr(int x[],int y[],int lx,int ly) {
if(lx!=ly) return lx>ly;
for(int i=lx;i>=1;i--) {
if(x[i]!=y[i]) return x[i]>y[i];
}
return 1;
}
void subArr(int x[],int y[],int &len) {
for(int i=1;i<=len;i++) {
if(x[i]<y[i]) {
x[i]+=10;
x[i+1]--;
}
x[i]-=y[i];
}
while(len>1&&x[len]==0) len--;
}
int main() {
scanf("%s %s",s1,s2);
int l1=strlen(s1),l2=strlen(s2);
for(int i=1;i<=l1;i++) {
a[i]=s1[l1-i]-'0';
}
for(int i=1;i<=l2;i++) {
b[i]=s2[l2-i]-'0';
}
if(l1<l2||(l1==l2&&!cmpArr(a,b,l1,l2))) {
printf("0\n");
for(int i=l1;i>=1;i--) printf("%d",a[i]);
printf("\n");
return 0;
}
int ansLen=l1-l2+1;
for(int i=ansLen;i>=1;i--) {
memset(t,0,sizeof(t));
for(int j=1;j<=l2;j++) {
t[i+j-1]=b[j];
}
int tLen=l2+i-1;
while(cmpArr(a,t,l1,tLen)) {
c[i]++;
subArr(a,t,l1);
}
}
while(ansLen>1&&c[ansLen]==0) ansLen--;
for(int i=ansLen;i>=1;i--) printf("%d",c[i]);
printf("\n");
while(l1>1&&a[l1]==0) l1--;
for(int i=l1;i>=1;i--) printf("%d",a[i]);
printf("\n");
return 0;
}
七、总结
| 运算 | 时间复杂度 | 关键点 |
|---|---|---|
| 加法 | O(n) | 逐位相加,处理进位 |
| 减法 | O(n) | 先比较大小,逐位借位 |
| 乘法 | O(n²) | 逐位相乘后统一进位 |
| 除法(低精) | O(n) | 从高位逐位求商 |
| 除法(高精) | O(n²) | 减法模拟,倍增试商 |
高精度算法是算法竞赛中的基础技能,掌握后可以处理任意大的整数运算。实际应用中,通常用加法、减法和乘法较多,除法相对较少,但原理都需要理解透彻。
指针单双链表
一、什么是指针链表
链表是一种线性数据结构,由一系列节点组成。每个节点包含数据域和指针域,指针域指向下一个节点(或上一个节点)。链表的优点是插入删除操作快,不需要移动元素,缺点是查找需要遍历,不能随机访问。
指针链表的特点:
- 节点动态分配内存
- 通过指针连接节点
- 插入删除时间复杂度O(1)
- 查找时间复杂度O(n)
二、单链表
单链表:每个节点只包含指向下一个节点的指针,只能从前往后遍历。
节点结构
struct Node {
int data;
Node* next;
};
基本操作
1. 创建链表
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head,* tail;
int n;
int main() {
scanf("%d",&n);
head=NULL;
tail=NULL;
for(int i=1;i<=n;i++) {
int x;
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->next=NULL;
if(head==NULL) {
head=p;
tail=p;
} else {
tail->next=p;
tail=p;
}
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
2. 在头部插入
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->next=head;
head=p;
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
3. 在指定位置插入
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,pos,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->next=head;
head=p;
}
scanf("%d %d",&pos,&x);
if(pos==1) {
Node* p=new Node();
p->data=x;
p->next=head;
head=p;
} else {
Node* cur=head;
for(int i=1;i<pos-1;i++) {
if(cur==NULL) return 0;
cur=cur->next;
}
if(cur==NULL) return 0;
Node* p=new Node();
p->data=x;
p->next=cur->next;
cur->next=p;
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
4. 删除指定元素
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,x,del;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->next=head;
head=p;
}
scanf("%d",&del);
while(head!=NULL&&head->data==del) {
Node* tmp=head;
head=head->next;
delete tmp;
}
if(head==NULL) return 0;
Node* cur=head;
while(cur->next!=NULL) {
if(cur->next->data==del) {
Node* tmp=cur->next;
cur->next=tmp->next;
delete tmp;
} else {
cur=cur->next;
}
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
5. 查找元素
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,x,target,pos=0;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->next=head;
head=p;
}
scanf("%d",&target);
Node* cur=head;
while(cur!=NULL) {
pos++;
if(cur->data==target) {
printf("%d\n",pos);
return 0;
}
cur=cur->next;
}
printf("-1\n");
return 0;
}
6. 反转链表
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->next=head;
head=p;
}
Node* pre=NULL;
Node* cur=head;
Node* nxt=NULL;
while(cur!=NULL) {
nxt=cur->next;
cur->next=pre;
pre=cur;
cur=nxt;
}
head=pre;
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
三、双链表
双链表:每个节点包含指向前一个节点和后一个节点的指针,可以从前往后遍历,也可以从后往前遍历。
节点结构
struct Node {
int data;
Node* prev;
Node* next;
};
基本操作
1. 创建双链表
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head,* tail;
int main() {
head=NULL;
tail=NULL;
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->prev=NULL;
p->next=NULL;
if(head==NULL) {
head=p;
tail=p;
} else {
tail->next=p;
p->prev=tail;
tail=p;
}
}
printf("从头到尾:");
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
printf("从尾到头:");
for(Node* p=tail;p!=NULL;p=p->prev) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
2. 在头部插入
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->prev=NULL;
p->next=head;
if(head!=NULL) {
head->prev=p;
}
head=p;
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
3. 在指定位置插入
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,pos,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->prev=NULL;
p->next=head;
if(head!=NULL) {
head->prev=p;
}
head=p;
}
scanf("%d %d",&pos,&x);
if(pos==1) {
Node* p=new Node();
p->data=x;
p->prev=NULL;
p->next=head;
if(head!=NULL) {
head->prev=p;
}
head=p;
} else {
Node* cur=head;
for(int i=1;i<pos-1;i++) {
if(cur==NULL) return 0;
cur=cur->next;
}
if(cur==NULL) return 0;
Node* p=new Node();
p->data=x;
p->prev=cur;
p->next=cur->next;
if(cur->next!=NULL) {
cur->next->prev=p;
}
cur->next=p;
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
4. 删除指定元素
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head;
int main() {
head=NULL;
int n,x,del;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->prev=NULL;
p->next=head;
if(head!=NULL) {
head->prev=p;
}
head=p;
}
scanf("%d",&del);
while(head!=NULL&&head->data==del) {
Node* tmp=head;
head=head->next;
if(head!=NULL) {
head->prev=NULL;
}
delete tmp;
}
if(head==NULL) return 0;
Node* cur=head;
while(cur!=NULL) {
if(cur->data==del) {
Node* tmp=cur;
if(cur->prev!=NULL) {
cur->prev->next=cur->next;
}
if(cur->next!=NULL) {
cur->next->prev=cur->prev;
}
cur=cur->next;
delete tmp;
} else {
cur=cur->next;
}
}
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
5. 双向遍历
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* prev;
Node* next;
};
Node* head,* tail;
int main() {
head=NULL;
tail=NULL;
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
Node* p=new Node();
p->data=x;
p->prev=NULL;
p->next=NULL;
if(head==NULL) {
head=p;
tail=p;
} else {
tail->next=p;
p->prev=tail;
tail=p;
}
}
printf("正向遍历:");
for(Node* p=head;p!=NULL;p=p->next) {
printf("%d ",p->data);
}
printf("\n");
printf("反向遍历:");
for(Node* p=tail;p!=NULL;p=p->prev) {
printf("%d ",p->data);
}
printf("\n");
return 0;
}
四、单链表 vs 双链表对比
| 特性 | 单链表 | 双链表 |
|---|---|---|
| 存储空间 | 每个节点1个指针 | 每个节点2个指针 |
| 遍历方向 | 只能向前 | 可以向前向后 |
| 插入操作 | O(1)(已知前驱) | O(1)(已知前驱或后继) |
| 删除操作 | 需要知道前驱节点 | 直接删除(已知自身) |
| 反向遍历 | 不支持 | 支持 |
| 应用场景 | 简单的线性结构 | 需要双向访问的场景 |
注意事项:
- 指针链表每次插入都要new新节点,删除时要delete释放内存
- 操作时要防止空指针访问(检查NULL)
- 双链表比单链表多维护一个prev指针,操作时要注意同时维护前后关系
- 链表适合频繁插入删除的场景,不适合频繁查找的场景
栈
一、什么是栈
栈是一种先进后出(Last In First Out,LIFO)的线性数据结构。就像一摞盘子,后放上去的盘子先被拿走,先放上去的盘子后被拿走。
核心操作:
- 入栈(push):在栈顶添加元素
- 出栈(pop):移除栈顶元素
- 取栈顶(top):查看栈顶元素但不移除
- 判空(empty):判断栈是否为空
- 获取大小(size):获取栈中元素个数
二、栈的两种实现方式
1. 数组实现栈(静态栈)
原理:用数组存储元素,用一个变量top指向栈顶位置。top初始为0表示空栈,入栈时先top++再赋值,出栈时top--。
优点:简单高效,访问速度快
缺点:大小固定,不能动态扩展
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],top;
int main() {
top=0;
int n,op,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&op);
if(op==1) {
scanf("%d",&x);
if(top<MAXN-5) {
stk[++top]=x;
printf("入栈成功:%d\n",x);
} else {
printf("栈已满\n");
}
} else if(op==2) {
if(top>0) {
printf("出栈元素:%d\n",stk[top--]);
} else {
printf("栈为空\n");
}
} else if(op==3) {
if(top>0) {
printf("栈顶元素:%d\n",stk[top]);
} else {
printf("栈为空\n");
}
} else if(op==4) {
printf("栈中元素个数:%d\n",top);
} else if(op==5) {
printf("栈是否为空:%s\n",top==0?"是":"否");
}
}
return 0;
}
2. STL栈(标准模板库)
C++的STL提供了现成的栈容器,方便使用。
#include <bits/stdc++.h>
using namespace std;
stack<int> st;
int main() {
int n,op,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&op);
if(op==1) {
scanf("%d",&x);
st.push(x);
printf("入栈成功:%d\n",x);
} else if(op==2) {
if(!st.empty()) {
printf("出栈元素:%d\n",st.top());
st.pop();
} else {
printf("栈为空\n");
}
} else if(op==3) {
if(!st.empty()) {
printf("栈顶元素:%d\n",st.top());
} else {
printf("栈为空\n");
}
} else if(op==4) {
printf("栈中元素个数:%d\n",st.size());
} else if(op==5) {
printf("栈是否为空:%s\n",st.empty()?"是":"否");
}
}
return 0;
}
三、栈的经典应用
1. 括号匹配
原理:遍历字符串,遇到左括号入栈,遇到右括号则检查栈顶是否是对应的左括号。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char stk[MAXN],s[MAXN];
int top;
int main() {
scanf("%s",s+1);
int len=strlen(s+1);
top=0;
int flag=1;
for(int i=1;i<=len;i++) {
if(s[i]=='('||s[i]=='['||s[i]=='{') {
stk[++top]=s[i];
} else if(s[i]==')') {
if(top>0&&stk[top]=='(') {
top--;
} else {
flag=0;
break;
}
} else if(s[i]==']') {
if(top>0&&stk[top]=='[') {
top--;
} else {
flag=0;
break;
}
} else if(s[i]=='}') {
if(top>0&&stk[top]=='{') {
top--;
} else {
flag=0;
break;
}
}
}
if(flag&&top==0) {
printf("括号匹配正确\n");
} else {
printf("括号匹配错误\n");
}
return 0;
}
2. 表达式求值(中缀转后缀)
原理:利用栈的优先级比较,将中缀表达式转换为后缀表达式再求值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
char stk[MAXN],s[MAXN];
int top;
int getPri(char c) {
if(c=='*'||c=='/') return 2;
if(c=='+'||c=='-') return 1;
return 0;
}
int main() {
scanf("%s",s+1);
int len=strlen(s+1);
top=0;
for(int i=1;i<=len;i++) {
if(s[i]>='0'&&s[i]<='9') {
printf("%c",s[i]);
} else if(s[i]=='(') {
stk[++top]=s[i];
} else if(s[i]==')') {
while(top>0&&stk[top]!='(') {
printf("%c",stk[top--]);
}
if(top>0) top--;
} else {
while(top>0&&getPri(stk[top])>=getPri(s[i])) {
printf("%c",stk[top--]);
}
stk[++top]=s[i];
}
}
while(top>0) {
printf("%c",stk[top--]);
}
printf("\n");
return 0;
}
3. 单调栈(求下一个更大元素)
原理:维护一个单调递减的栈,当前元素比栈顶大时,栈顶的下一个更大元素就是当前元素。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int a[MAXN],ans[MAXN],stk[MAXN];
int top;
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
top=0;
for(int i=n;i>=1;i--) {
while(top>0&&a[stk[top]]<=a[i]) {
top--;
}
if(top>0) {
ans[i]=a[stk[top]];
} else {
ans[i]=-1;
}
stk[++top]=i;
}
for(int i=1;i<=n;i++) {
printf("%d ",ans[i]);
}
printf("\n");
return 0;
}
4. 模拟递归(DFS)
栈可以用来模拟递归调用,避免递归深度过大的问题。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
struct Node {
int x,y,step;
};
Node stk[MAXN];
int top;
int main() {
int n,start;
scanf("%d %d",&n,&start);
top=0;
stk[++top]={start,0,1};
while(top>0) {
Node cur=stk[top--];
printf("%d ",cur.x);
if(cur.x*2<=n) {
stk[++top]={cur.x*2,cur.y+1,cur.step+1};
}
if(cur.x+1<=n) {
stk[++top]={cur.x+1,cur.y+1,cur.step+1};
}
}
printf("\n");
return 0;
}
四、栈的常见题型
1. 最小栈
设计一个栈,支持push、pop、top和getMin操作,getMin能在O(1)时间返回最小值。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],minStk[MAXN];
int top,minTop;
int main() {
top=0;
minTop=0;
int n,op,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&op);
if(op==1) {
scanf("%d",&x);
stk[++top]=x;
if(minTop==0||x<=minStk[minTop]) {
minStk[++minTop]=x;
}
} else if(op==2) {
if(top>0) {
if(stk[top]==minStk[minTop]) {
minTop--;
}
printf("出栈:%d\n",stk[top--]);
}
} else if(op==3) {
if(top>0) {
printf("栈顶:%d\n",stk[top]);
}
} else if(op==4) {
if(minTop>0) {
printf("最小值:%d\n",minStk[minTop]);
}
}
}
return 0;
}
2. 栈排序
使用辅助栈对栈进行排序。
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
int stk[MAXN],tmpStk[MAXN];
int top,tmpTop;
int main() {
top=0;
tmpTop=0;
int n,x;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&x);
while(top>0&&stk[top]>x) {
tmpStk[++tmpTop]=stk[top--];
}
stk[++top]=x;
while(tmpTop>0) {
stk[++top]=tmpStk[tmpTop--];
}
}
while(top>0) {
printf("%d ",stk[top--]);
}
printf("\n");
return 0;
}
五、栈的总结
| 特性 | 数组实现 | STL实现 |
|---|---|---|
| 时间复杂度 | O(1) | O(1) |
| 空间限制 | 固定大小 | 动态扩展 |
| 操作直观 | 需要手动管理 | 封装完善 |
| 适用场景 | 已知最大大小 | 大小不确定 |
栈的核心思想:
- 先进后出是根本特性
- 递归本质上就是栈的应用
- 适用于需要回溯的场景
- 常用于深度优先搜索(DFS)
- 表达式求值、括号匹配等是经典应用
注意事项:
- 使用数组实现时注意栈溢出(top超过MAXN)
- 出栈前检查栈是否为空
- 递归深度过大时考虑用栈模拟
- 栈擅长处理具有嵌套结构的数据
全部评论 1
这可能是作者发的唯一一个和学习有关的帖子昨天 来自 云南
0






















有帮助,赞一个