数据结构之顺序栈SqStack

时间：2021-04-22 10:22:47


顺序栈SqStack


基本操作


Status InitStack()//构造一个空栈S
Status DestroyStack()//销毁栈S，S不再存在
Status ClearStack()//把S置为空栈
Status StackEmpty()//若S为空栈，则返回true，否则返回false
int StackLength()//返回S的元素个数，即栈的长度
Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
Status Push(SElemType e)//插入元素e为新的栈顶元素
Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR
Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败


几个小程序（代码正误检验，数制转换，括号匹配检验，行编辑程序）


CheckStackCode();//测试Stack代码正确性
Conversion();//数制转换
BracketsMatching();//括号匹配的检验
LineEdit();//行编辑程序



//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-10)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define N 104

using namespace std;
typedef long long LL;
/*
double anss;
LL aans,sum;
int cas,cass;
int n,m,lll,ans;
*/


const int OK=1;
const int ERROR=0;
const int INFEASIBLE=-1;
const int STACK_INIT_SIZE=100;//存储空间初始分配量
const int STACKINCREMENT=10;//存储空间分配增量
typedef int Status;
typedef int SElemType;

Status OutputInt(SElemType e);
Status OutputChar(SElemType e);
typedef struct
{
SElemType *base;//栈构造之前和销毁之后，base的值为NULL
SElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间，以元素为单位

Status InitStack()//构造一个空栈S
{
base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!base)exit(OVERFLOW);//存储分配失败
top=base;
stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack

Status DestroyStack()//销毁栈S，S不再存在
{
free(base);
base=NULL;
top=NULL;
stacksize=0;
return OK;
}//DestroyStack

Status ClearStack()//把S置为空栈
{
top=base;
return OK;
}//ClearStack

Status StackEmpty()//若S为空栈，则返回true，否则返回false
{
if(top==base)return true;
return false;
}//StackEmpty

int StackLength()//返回S的元素个数，即栈的长度
{
return top-base;
}//StackLength

Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
{
if(top==base)return ERROR;
e=*(top-1);
return OK;
}//GetTop

Status Push(SElemType e)//插入元素e为新的栈顶元素
{
if(top-base>=stacksize)//栈满，追加存储空间
{
base=(SElemType *)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!base)exit(OVERFLOW);//存储分配失败
top=base+stacksize;
stacksize+=STACKINCREMENT;
}
(*top++)=e;
return OK;
}//Push

Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR
{
if(top==base)return ERROR;
e=(*--top);
return OK;
}//Pop

Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败
{
SElemType *i=base;
Status (*visit)(SElemType);
if(p==1)visit=OutputInt;
else if(p==0)visit=OutputChar;
while(top>i)
visit(*i++);
puts("");
return OK;
}//StackTraverse
}SqStack;

Status OutputInt(SElemType e)
{
printf("%d ",e);
return OK;
}
Status OutputChar(SElemType e)
{
printf("%c",e);
return OK;
}


void CheckStackCode()
{
typedef int SElemType;
int i;
SqStack S;
SElemType e;
if(S.InitStack()==OK)
{
for(i=1;i<=12;i++)
S.Push(i);
}
printf("栈中元素依次为：");
S.StackTraverse(1);
S.Pop(e);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1：空 0：否)\n",S.StackEmpty());
S.GetTop(e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,S.StackLength());
S.Push(13);
printf("栈中元素依次为：");
S.StackTraverse(1);
S.GetTop(e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,S.StackLength());
S.DestroyStack();
printf("销毁栈后，S.top=%d  S.base=%d  S.stacksize=%d\n",S.top,S.base,S.stacksize);
}

void Conversion()//对于输入的任意一个非负十进制整数n，打印输出与其等值的八进制数
{
typedef int SElemType;
int n;
SqStack S;
SElemType e;

S.InitStack();//构造空栈
scanf("%d",&n);
while(n)
{
S.Push(n%8);
n/=8;
}
while(!S.StackEmpty())
{
S.Pop(e);
printf("%d",e);
}
puts("");

S.DestroyStack();
}

void BracketsMatching()//三种括号()[]{}，检验是否合法
{

char s[N];
SqStack S;
SElemType e;
int i;
S.InitStack();
scanf("%s",s);

for(i=0;i<strlen(s);i++)
{
if(s[i]=='(' || s[i]=='{' || s[i]=='[')
S.Push(s[i]);
else if(s[i]==')' || s[i]=='}' || s[i]==']')
{
if(S.GetTop(e) && ((e=='(' && s[i]==')') || (e=='[' && s[i]==']') || (e=='{' && s[i]=='}')))
S.Pop(e);
else
{
puts("NO");
S.DestroyStack();
return;
}
}
}
if(S.StackEmpty())puts("YES");
else puts("NO");
S.DestroyStack();
}

void LineEdit()//从终端接收一行并传送至调用过程的数据区，#为退格符，@为退行符
{
int i;
char ch;
SqStack S;
SElemType e;
S.InitStack();
while(ch!=EOF)
{
for(ch=getchar();ch!=EOF && ch!='\n';ch=getchar())
{
if(ch=='#')S.Pop(e);
else if(ch=='@')S.ClearStack();
else S.Push(ch);
}
S.StackTraverse(0);
S.ClearStack();
}
S.DestroyStack();
}


int main()
{
#ifndef ONLINE_JUDGEW
freopen("1.txt","r",stdin);
//freopen("2.txt","w",stdout);
#endif
int i,j,k;
//init();
//for(scanf("%d",&cass);cass;cass--)
//for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
//while(~scanf("%s",s))
/*
while(~scanf("%d%d",&n,&m))
{

}
*/

CheckStackCode();//测试Stack代码正确性

Conversion();//数制转换

BracketsMatching();//括号匹配的检验

LineEdit();//行编辑程序

return 0;
}
/*
//

//
*/


马踏棋盘问题（NxN）

暴力(顺序栈实现)

//
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-10)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define N 8
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
LL n,m,lll,ans;
int a[N][N];
bool u[N][N];
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1};

const int OK=1;
const int ERROR=0;
const int INFEASIBLE=-1;
const int STACK_INIT_SIZE=10000;//存储空间初始分配量
const int STACKINCREMENT=10000;//存储空间分配增量
typedef int Status;

typedef struct
{
int x,y,dir;
}SElemType;

Status OutputInt(SElemType e);
Status OutputChar(SElemType e);
typedef struct
{
SElemType *base;//栈构造之前和销毁之后，base的值为NULL
SElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间，以元素为单位

Status InitStack()//构造一个空栈S
{
base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!base)exit(OVERFLOW);//存储分配失败
top=base;
stacksize=STACK_INIT_SIZE;
return OK;
}//InitStack

Status DestroyStack()//销毁栈S，S不再存在
{
free(base);
base=NULL;
top=NULL;
stacksize=0;
return OK;
}//DestroyStack

Status ClearStack()//把S置为空栈
{
top=base;
return OK;
}//ClearStack

Status StackEmpty()//若S为空栈，则返回true，否则返回false
{
if(top==base)return true;
return false;
}//StackEmpty

int StackLength()//返回S的元素个数，即栈的长度
{
return top-base;
}//StackLength

Status GetTop(SElemType &e)//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR
{
if(top==base)return ERROR;
e=*(top-1);
return OK;
}//GetTop

Status Push(SElemType e)//插入元素e为新的栈顶元素
{
if(top-base>=stacksize)//栈满，追加存储空间
{
base=(SElemType *)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!base)exit(OVERFLOW);//存储分配失败
top=base+stacksize;
stacksize+=STACKINCREMENT;
}
(*top++)=e;
return OK;
}//Push

Status Pop(SElemType &e)//若栈不空，则删除S的栈顶元素，并用e返回其值，并返回OK，否则返回ERROR
{
if(top==base)return ERROR;
e=(*--top);
return OK;
}//Pop

Status StackTraverse(int p)//从栈底到栈顶依次对栈中每个元素调用函数visit().一旦visit()失败则操作失败
{
SElemType *i=base;
Status (*visit)(SElemType);
if(p==1)visit=OutputInt;
else if(p==0)visit=OutputChar;
while(top>i)
visit(*i++);
puts("");
return OK;
}//StackTraverse
}SqStack;
Status OutputInt(SElemType e)
{
printf("%d ",e);
return OK;
}
Status OutputChar(SElemType e)
{
printf("%c",e);
return OK;
}

SqStack S;
void print()
{
int i,j;
for(i=0;i<N;i++,puts(""))
for(j=0;j<N;j++)
printf("%d ",a[i][j]);
puts("");
}
int main()
{
#ifndef ONLINE_JUDGEW
freopen("1.txt","r",stdin);
//freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z,xx,yy;
//init();
//for(scanf("%d",&cass);cass;cass--)
//for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
//while(~scanf("%s",s))
while(~scanf("%d%d",&n,&m))
{
mem(a,0);mem(u,0);
S.InitStack();
SElemType e,to;
e.x=n,e.y=m,e.dir=-1;
u[n][m]=1;
S.Push(e);
loop : while(S.top-S.base<N*N && !S.StackEmpty())
{
SElemType & now=*(S.top-1);
for(++now.dir;now.dir<8;now.dir++)
{
xx=now.x+dx[now.dir],yy=now.y+dy[now.dir];
if(xx>=0 && xx<N && yy>=0 && yy<N && !u[xx][yy])
{
u[xx][yy]=1;
to.x=xx,to.y=yy,to.dir=-1;
S.Push(to);
goto loop;
}
}
S.Pop(e);
u[e.x][e.y]=0;
}
if(S.StackEmpty()){puts("No Answer\n");continue;}
SElemType *id;
for(id=S.base,cas=0;id!=S.top;id++)
{
e=(*id);
a[e.x][e.y]=++cas;
}
print();
S.DestroyStack();
}
return 0;
}

马踏棋盘贪心优化

// 
//by coolxxx
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<iomanip>
#include<map>
#include<stack>
#include<queue>
#include<set>
#include<bitset>
#include<memory.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include<stdbool.h>
#include<math.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define eps (1e-10)
#define J 10000
#define mod 1000000007
#define MAX 0x7f7f7f7f
#define PI 3.14159265358979323
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define N 8
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
LL n,m,lll,ans;
int a[N][N];
bool u[N][N];
int dx[]={-2,-1,1,2,2,1,-1,-2};
int dy[]={1,2,2,1,-1,-2,-2,-1};
struct xxx
{
int c,num;
};
bool cmp(xxx aa,xxx bb)
{
return aa.c<bb.c;
}
void print()
{
int i,j;
for(i=0;i<N;i++,puts(""))
for(j=0;j<N;j++)
printf("%d ",a[i][j]);
puts("");
}
void cal(int x,int y,xxx d[])
{
int i,j,xx,yy,x1,y1;
for(i=0;i<8;i++)
{
d[i].c=0;d[i].num=i;
xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<N && yy>=0 && yy<N && !u[xx][yy])
{
d[i].c++;
for(j=0;j<8;j++)
{
x1=xx+dx[j],y1=yy+dy[j];
if(x1>=0 && x1<N && y1>=0 && y1<N && !u[x1][y1])
{
d[i].c++;
}
}
}
}
}
void dfs(int x,int y,int top)
{
if(top==65)
{
print();
lll++;
return;
}
int i,j,xx,yy;
xxx d[8];
cal(x,y,d);
sort(d,d+8,cmp);
for(i=0;i<8;i++)
{
if(d[i].c==0)continue;
j=d[i].num;
xx=x+dx[j],yy=y+dy[j];
if(xx>=0 && xx<N && yy>=0 && yy<N && !u[xx][yy])
{
u[xx][yy]=1;
a[xx][yy]=top;
dfs(xx,yy,top+1);
if(lll==cas)return;
u[xx][yy]=0;
a[xx][yy]=0;
}
}
}
int main()
{
#ifndef ONLINE_JUDGEW
//freopen("1.txt","r",stdin);
//freopen("2.txt","w",stdout);
#endif
int i,j,k;
int x,y,z,xx,yy;
//init();
//for(scanf("%d",&cass);cass;cass--)
//for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
//while(~scanf("%s",s))
puts("输入起点坐标和需要的解的数量");
while(~scanf("%d%d",&n,&m))
{
scanf("%d",&cas);
j=clock();
mem(a,0);mem(u,0);lll=0;
a[n][m]=1;u[n][m]=1;
dfs(n,m,2);
k=clock();
printf("用时 %.3lf s\n",0.001*(k-j));
puts("输入起点坐标和需要的解的数量");
}
return 0;
}


为了写的快就随便优化没怎么细想，如果觉得我的算法复杂度还是太高可以转http://blog.csdn.net/bone_ace/article/details/41579957




标签：

相关文章