数据结构之顺序栈SqStack

时间：2023-03-09 00:37:08
数据结构之顺序栈SqStack

顺序栈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=;

 const int ERROR=;

 const int INFEASIBLE=-;

 const int STACK_INIT_SIZE=;//存储空间初始分配量

 const int STACKINCREMENT=;//存储空间分配增量

 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=;

         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-);

         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==)visit=OutputInt;

         else if(p==)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=;i<=;i++)

             S.Push(i);

     }

     printf("栈中元素依次为：");

     S.StackTraverse();

     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();

     printf("栈中元素依次为：");

     S.StackTraverse();

     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%);

         n/=;

     }

     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=;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();

         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 ;

 }

 /*

 //

 //

 */

马踏棋盘问题（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[]={-,-,,,,,-,-};

 int dy[]={,,,,-,-,-,-};

 const int OK=;

 const int ERROR=;

 const int INFEASIBLE=-;

 const int STACK_INIT_SIZE=;//存储空间初始分配量

 const int STACKINCREMENT=;//存储空间分配增量

 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=;

         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-);

         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==)visit=OutputInt;

         else if(p==)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=;i<N;i++,puts(""))

         for(j=;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,);mem(u,);

         S.InitStack();

         SElemType e,to;

         e.x=n,e.y=m,e.dir=-;

         u[n][m]=;

         S.Push(e);

         loop : while(S.top-S.base<N*N && !S.StackEmpty())

         {

             SElemType & now=*(S.top-);

             for(++now.dir;now.dir<;now.dir++)

             {

                 xx=now.x+dx[now.dir],yy=now.y+dy[now.dir];

                 if(xx>= && xx<N && yy>= && yy<N && !u[xx][yy])

                 {

                     u[xx][yy]=;

                     to.x=xx,to.y=yy,to.dir=-;

                     S.Push(to);

                     goto loop;

                 }

             }

             S.Pop(e);

             u[e.x][e.y]=;

         }

         if(S.StackEmpty()){puts("No Answer\n");continue;}

         SElemType *id;

         for(id=S.base,cas=;id!=S.top;id++)

         {

             e=(*id);

             a[e.x][e.y]=++cas;

         }

         print();

         S.DestroyStack();

     }

     return ;

 }

马踏棋盘贪心优化

 //

 //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[]={-,-,,,,,-,-};

 int dy[]={,,,,-,-,-,-};

 struct xxx

 {

     int c,num;

 };

 bool cmp(xxx aa,xxx bb)

 {

     return aa.c<bb.c;

 }

 void print()

 {

     int i,j;

     for(i=;i<N;i++,puts(""))

         for(j=;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=;i<;i++)

     {

         d[i].c=;d[i].num=i;

         xx=x+dx[i],yy=y+dy[i];

         if(xx>= && xx<N && yy>= && yy<N && !u[xx][yy])

         {

             d[i].c++;

             for(j=;j<;j++)

             {

                 x1=xx+dx[j],y1=yy+dy[j];

                 if(x1>= && x1<N && y1>= && y1<N && !u[x1][y1])

                 {

                     d[i].c++;

                 }

             }

         }

     }

 }

 void dfs(int x,int y,int top)

 {

     if(top==)

     {

         print();

         lll++;

         return;

     }

     int i,j,xx,yy;

     xxx d[];

     cal(x,y,d);

     sort(d,d+,cmp);

     for(i=;i<;i++)

     {

         if(d[i].c==)continue;

         j=d[i].num;

         xx=x+dx[j],yy=y+dy[j];

         if(xx>= && xx<N && yy>= && yy<N && !u[xx][yy])

         {

             u[xx][yy]=;

             a[xx][yy]=top;

             dfs(xx,yy,top+);

             if(lll==cas)return;

             u[xx][yy]=;

             a[xx][yy]=;

         }

     }

 }

 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,);mem(u,);lll=;

         a[n][m]=;u[n][m]=;

         dfs(n,m,);

         k=clock();

         printf("用时 %.3lf s\n",0.001*(k-j));

         puts("输入起点坐标和需要的解的数量");

     }

     return ;

 }

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

相关文章