史上最全最完整栈施用 C语言源代码可直接运行

2012-06-20

史上最全最完整栈应用 C语言源代码可直接运行一共包括六个程序，分别是：l 数制转换，l 括号匹配的检验，l

史上最全最完整栈应用 C语言源代码可直接运行

一共包括六个程序，分别是：

l > 数制转换，

l > 括号匹配的检验，

l > 行编辑程序问题，

l > 迷宫求解，

l > 表达式求值，

l > 汉诺塔递归实现

这些栈的应用都是严蔚敏的数据结构那本书中的例子，但是那本书中的例子大都是用伪代码的形式写的，不是很容易理解和实现，对初学者造成了不小的困扰，在这里我们将其详尽的实现出来，以便初学者调试和运行，并从中有所收获。

上述的六个程序，每个程序的实现在一个文件中，每个程序都由C语言编写，只是借用C++中的两个东西，一是注释符‘//’，一是引用符‘&’。每个程序可以在C++兼容的编译器上直接运行，经过测试，运行情况良好，有什么问题，欢迎留言交流。

文件一：数制转换

/********************** 声明部分 **********************/#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 10   //定义最初申请的内存的大小#define STACK_INCREMENT 2    //每一次申请内存不足的时候扩展的大小#define OVERFLOW 0#define FALSE 0#define TRUE 1#define ERROR 0#define INFEASIBLE 0#define OK  1typedef int SElemType;typedef int Status;int Length;/********************** 结构类型部分 **********************/typedef struct SqStack{       SElemType *base; // 栈底指针       SElemType *top; // 栈顶指针       int stacksize;}SqStack; // 顺序栈/********************** 基本操作函数部分 **********************//********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S       if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType))))              exit(OVERFLOW); // 存储分配失败       S.top = S.base;       S.stacksize = STACK_INIT_SIZE; //初始栈容量       return OK;}/********************** 输入栈元素 **********************/Status Push(SqStack &S, SElemType e){       if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间       {              //可能会改变栈底地址，新栈底指针S.base              S.base = (SElemType *) realloc(S.base, //原栈底指针                     (S.stacksize + STACK_INCREMENT) * sizeof (SElemType)); //新大小              if (!S.base)                     exit(OVERFLOW); // 存储分配失败              //给SqStack结构对象S的3个成员赋值              S.top = S.base + S.stacksize;              S.stacksize += STACK_INCREMENT;       }       *S.top++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置       return OK;}/********************** 输出栈元素 **********************/void OutList(SqStack S){       S.top=S.base;  //  从栈底开始输出       for(int i=0;i<Length;i++)  //用长度控制输出的个数       {              printf("%d\t",*(S.top)++);       }       printf("\n");  //  输出后换行}/********************** 判断栈是否是空的 **********************/Status StackEmpty(SqStack S){ // 若栈S为空栈，则返回TRUE，否则返回FALSE       //栈顶指针S.top是否等于栈底指针S.base是判断栈是否为空的条件       if (S.top == S.base)              return TRUE;       else              return FALSE;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return ERROR;       e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回       return OK;}/********************** 算法主程序 **********************/void conversion() // 算法3.1{ // 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数       SqStack s; //顺序栈s       unsigned n, m; // 非负整数       SElemType e; //栈元素e       InitStack(s); // 构造空栈s       printf("请输入十进制数n（>=0） = ");       scanf("%u", &n); // 输入非负十进制整数n       printf("\n请输入需要转换到的进制： ");       scanf("%u", &m); // 输入非负十进制整数n       printf("十进制数%u的八进制数是", n);       while (n) // 只要n不等于0就循环              //从n为用户输入的十进制数开始，一直到n等于0为止       {              Push(s, n % m); // n除以8的余数(8进制的低位)入栈              //把n除以8的余数压入栈s              //先压入的余数是八进制的低位，后压入的余数是八进制的高位              n = n / m; //令n等于n整除以8的商，进入下轮循环       }       //循环结束时，n等于0       while (!StackEmpty(s)) // 只要栈s没弹空就不断循环，              //直到弹出栈底元素栈s为空为止       {              Pop(s, e); // 弹出栈顶元素且赋值给e              //依次弹出栈s的栈顶元素交给e带回              //先弹出的是八进制的高位，后弹出的是八进制的低位              printf("%d", e); // 依次输出e       }       //循环结束时，栈s为空       printf("\n");}/********************** 主函数部分 **********************/int main(){       /********************** 函数声明区 **********************/       Status InitStack(SqStack &S);       Status Push(SqStack &S, SElemType e);       void OutList(SqStack S);       /********************** 函数执行区 **********************/       conversion();       return 0;}

文件二：括号匹配的检验

/********************** 声明部分 **********************/#include<stdio.h>  //输入输出函数头文件#include<stdlib.h>  //内存申请函数头文件#define OVERFLOW false  //异常抛出返回值#define FALSE false  //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false  //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true  //程序正确执行抛出返回值typedef bool Status;  //别名声明#define STACK_INIT_SIZE 100 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量 typedef char SElemType;/********************** 结构类型部分 **********************/typedef struct SqStack{       //栈的数据元素类型在应用程序中定义typedef int SElemType;       SElemType *base; // 栈底指针       //在栈构造之前和销毁之后，base为NULL       SElemType *top; // 栈顶指针       //初值指向栈底，top = base可做栈空标记       //插入新栈顶元素时，top增1；删除栈顶元素时，top减1       //非空栈的top始终在栈顶元素的下一个位置上       int stacksize; // 当前已分配的存储空间，以元素为单位       //栈当前可使用的最大容量       int len;}SqStack;// 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S       //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间       if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType))))              exit(OVERFLOW); // 存储分配失败       //必须给SqStack结构对象S的3个成员赋值       S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base       S.stacksize = STACK_INIT_SIZE; //初始栈容量       S.len = 0;       return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR       if (S.top > S.base)       {              e = *(S.top - 1); //因为S.top指向栈顶元素的下一个位置，              //所以栈顶元素就是e = *(S.top - 1)              return OK;       }       else              return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e为新的栈顶元素       if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间              //如果栈长度大于栈容量       {              //可能会改变栈底地址，新栈底指针S.base              S.base = (SElemType *) realloc(S.base, //原栈底指针                     (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小              if (!S.base)                     exit(OVERFLOW); // 存储分配失败              //给SqStack结构对象S的3个成员赋值              S.top = S.base + S.stacksize;              S.stacksize += STACKINCREMENT;       }       *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置       S.len++;       return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return ERROR;       e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回       S.len--;       return OK;}Status IsEmpty(SqStack &S){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return TRUE;        return FALSE;}void BraceMatch(){char e,a[20];int i=0;int flag=1;SqStack S;InitStack(S);  printf("input the braces (<=20) and press '#' to show the end:\n");  //输入字符  do{      scanf("%c",&e);      a[i]=e;      i++;    }while(e!='#');    printf("%s\n",a);  i=0;  e=a[0];  while(e!='#'&& flag) {     switch(e)    {case '(': Push(S,e); break;     case '[': Push(S,e); break;     case '{': Push(S,e); break;     case ')': if(!IsEmpty(S))     {Pop(S,e);if(e!='(')flag=0;     }     else flag=0;     break;     case ']':if(!IsEmpty(S))    {   Pop(S,e);       if(e!='[') flag=0;    }    else flag=0;    break;    case '}':if(!IsEmpty(S))    {  Pop(S,e);       if(e!='{')   flag=0;    }    else flag=0;    break;    }    i++;    e=a[i];    printf("The length of the stack is %d\n",S.len); }   if(!IsEmpty(S)) flag=0;   if(flag)printf("MATCH!\n");   else  printf("MIS MATCH!\n"); }int main(){    BraceMatch();    return 0;}

文件三：行编辑程序问题

/********************** 声明部分 **********************/#include<stdio.h>#include<stdlib.h>#define STACK_INIT_SIZE 10  //定义最初申请的内存的大小#define STACK_INCREMENT 2  //每一次申请内存不足的时候扩展的大小#define OVERFLOW false  //异常抛出返回值#define FALSE false  //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false  //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true  //程序正确执行抛出返回值typedef int SElemType;  //别名声明，其实int可以用任意的名字代入typedef bool Status;  //别名声明/********************** 结构类型部分 **********************/struct SqStack{       SElemType *base; // 栈底指针       //在栈构造之前和销毁之后，base为NULL       SElemType *top; // 栈顶指针       //初值指向栈底，top = base可做栈空标记       //插入新栈顶元素时，top增1；删除栈顶元素时，top减1       //非空栈的top始终在栈顶元素的下一个位置上       int stacksize; // 当前已分配的存储空间，以元素为单位}; // 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S       //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间       if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType))))              exit(OVERFLOW); // 存储分配失败       //必须给SqStack结构对象S的3个成员赋值       S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base       S.stacksize = STACK_INIT_SIZE; //初始栈容量       return OK;}/********************** 把S置为空栈 **********************/Status ClearStack(SqStack &S){ // 把S置为空栈       S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base       return OK;}/********************** 销毁栈S **********************/Status DestroyStack(SqStack &S){ // 销毁栈S，S不再存在       ClearStack(S);       free(S.base); //释放栈底指针S.base       //必须给SqStack结构对象S的3个成员赋值       S.base = NULL;       S.top = NULL;       S.stacksize = 0;       return OK;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, char e){ // 插入元素e为新的栈顶元素       if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间              //如果栈长度大于栈容量       {              //可能会改变栈底地址，新栈底指针S.base              S.base = (SElemType *) realloc(S.base, //原栈底指针                     (S.stacksize + STACK_INCREMENT) * sizeof (SElemType)); //新大小              if (!S.base)                     exit(OVERFLOW); // 存储分配失败              //给SqStack结构对象S的3个成员赋值              S.top = S.base + S.stacksize;              S.stacksize += STACK_INCREMENT;       }       *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置       return OK;}/********************** 输出栈元素 **********************/int Length=0;void OutList(SqStack S){       S.top=S.base;  //  从栈底开始输出       for(int i=0;i<Length;i++)  //用长度控制输出的个数       {              printf("%c",*(S.top)++);       }       printf("\n");  //  输出后换行}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, char &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return ERROR;       e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回       return OK;}/********************** 行编辑函数 **********************/void LineEdit(){ // 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2       SqStack s;       char ch, c;       InitStack(s); //构造空栈s       printf("please input the strings:\n");       ch = getchar(); //初始化循环条件变量       while (ch != EOF)       { // EOF为^Z键，全文结束符              //行内循环              while (ch != EOF && ch != '\n')              {                     switch (ch)                     {                            //也可以输入中文，一个#只能删掉半个汉字，剩下一半汉字显示一个?                     case '#': //如果ch是退格符#                            Length--;                            Pop(s, c); //把栈s的栈顶元素弹出到c                            break; // 仅当栈非空时退格                     case '@': //如果ch是退行符@                            Length = 0;                            ClearStack(s); //清空栈s                            break; // 重置s为空栈                     default : //如果ch不是^Z、\n、#、@，而是其他有效字符                            Push(s, ch); // 那么有效字符ch进栈s                            Length++;                            break;                     }                     ch = getchar(); // 从终端接收下一个字符，准备下轮（行内下个字符）循环              }              printf("The input string is : \n");              OutList(s);  //输出缓存区输入的数据              printf("\n");              Length=0;  //初始化输出长度为0              ClearStack(s); // 一行遍历完毕，栈中所有元素已经全写入fp指向的文件，重置s为空栈              if (ch != EOF) //只要ch不是^Z                     ch = getchar(); //就继续接收字符，进入下轮（行）循环       }       //用户输入^Z时循环结束       DestroyStack(s); //销毁栈s}int main(){       LineEdit();       return 0;}

文件四：迷宫求解

/********************** 声明部分 **********************/#include<stdio.h>  //输入输出函数头文件#include<stdlib.h>  //内存申请函数头文件#define STACK_INIT_SIZE 10  //定义最初申请的内存的大小#define STACK_INCREMENT 2  //每一次申请内存不足的时候扩展的大小#define OVERFLOW false  //异常抛出返回值#define FALSE false  //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false  //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true  //程序正确执行抛出返回值typedef bool Status;  //别名声明#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量/*  typedef int ElemType;  */typedef struct{    int r;    int c;}PosType;typedef struct{int ord;          /* 通道块在路径上的序号  */PosType seat;    /*  通道块在迷宫中的“坐标位置”  */int di;           /*  从此通道块走向下一个通道块的“方向” */}SElemType;typedef struct{    char arr[10][10];}MazeType;/********************** 结构类型部分 **********************/typedef struct SqStack{       //栈的数据元素类型在应用程序中定义typedef int SElemType;       SElemType *base; // 栈底指针       //在栈构造之前和销毁之后，base为NULL       SElemType *top; // 栈顶指针       //初值指向栈底，top = base可做栈空标记       //插入新栈顶元素时，top增1；删除栈顶元素时，top减1       //非空栈的top始终在栈顶元素的下一个位置上       int stacksize; // 当前已分配的存储空间，以元素为单位       //栈当前可使用的最大容量}SqStack;// 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S       //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间       if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType))))              exit(OVERFLOW); // 存储分配失败       //必须给SqStack结构对象S的3个成员赋值       S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base       S.stacksize = STACK_INIT_SIZE; //初始栈容量       return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR       if (S.top > S.base)       {              e = *(S.top - 1); //因为S.top指向栈顶元素的下一个位置，              //所以栈顶元素就是e = *(S.top - 1)              return OK;       }       else              return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e为新的栈顶元素       if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间              //如果栈长度大于栈容量       {              //可能会改变栈底地址，新栈底指针S.base              S.base = (SElemType *) realloc(S.base, //原栈底指针                     (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小              if (!S.base)                     exit(OVERFLOW); // 存储分配失败              //给SqStack结构对象S的3个成员赋值              S.top = S.base + S.stacksize;              S.stacksize += STACKINCREMENT;       }       *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置       return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return ERROR;       e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回       return OK;}Status IsEmpty(SqStack &S){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return TRUE;        return FALSE;}int pass(MazeType MyMaze, PosType CurPos);void footPrint(MazeType &MyMaze, PosType CurPos);void markPrint(MazeType &MyMaze, PosType CurPos);PosType nextPos(PosType CurPos, int Dir);int pass( MazeType MyMaze,PosType CurPos){  if (MyMaze.arr[CurPos.r][CurPos.c]==' ')    return 1;     // 如果当前位置是可以通过，返回1  else return 0;  // 其它情况返回0}void footPrint(MazeType &MyMaze,PosType CurPos){  MyMaze.arr[CurPos.r][CurPos.c]='*';}void markPrint(MazeType &MyMaze,PosType CurPos) {  MyMaze.arr[CurPos.r][CurPos.c]='!';}PosType nextPos(PosType CurPos, int Dir) {  PosType ReturnPos;  switch (Dir) {    case 1:        ReturnPos.r=CurPos.r;        ReturnPos.c=CurPos.c+1;        break;    case 2:        ReturnPos.r=CurPos.r+1;        ReturnPos.c=CurPos.c;        break;    case 3:        ReturnPos.r=CurPos.r;        ReturnPos.c=CurPos.c-1;        break;    case 4:        ReturnPos.r=CurPos.r-1;        ReturnPos.c=CurPos.c;        break;  }  return ReturnPos;}/* 迷宫函数  *//* 判断是否存在一条从开口到结尾的路径 */int mazePath(MazeType &maze, PosType start, PosType end){SqStack s;InitStack(s);PosType curpos = start;  // 设定"当前位置"为"入口位置"SElemType e;    int curstep = 1;     // 探索第一步  do {    if (pass(maze,curpos))    {  // 当前位置可通过，即是未曾走到过的通道块      footPrint(maze,curpos); // 留下足迹      e.di =1;      e.ord = curstep;      e.seat= curpos;      Push(s,e);              // 加入路径      if (curpos.r == end.r && curpos.c==end.c)        return TRUE;        // 到达终点（出口）      curpos = nextPos(curpos, 1);        // 下一位置是当前位置的东邻      curstep++;                          // 探索下一步    }    else    {  // 当前位置不能通过      if (!IsEmpty(s))      {        Pop(s,e);        while (e.di==4 && !IsEmpty(s))        {          markPrint(maze,e.seat);          Pop(s,e);    // 留下不能通过的标记，并退回一步        } // while        if (e.di<4)        {          e.di++;          Push(s, e);  // 换下一个方向探索          curpos = nextPos(e.seat, e.di); // 当前位置设为新方向的相邻块        } // if      } // if    } // else  } while (!IsEmpty(s) );  return  FALSE;} // MazePathint main(){    //printf("Hello world!");    MazeType maze;    maze.arr = {       {'0','0','0','0','0','0','0','0','0','0'},                   {'0',' ',' ','0',' ',' ',' ','0',' ','0'},   {'0',' ',' ','0',' ',' ',' ','0',' ','0'},   {'0',' ',' ',' ',' ','0','0',' ',' ','0'},   {'0',' ','0','0','0',' ',' ',' ',' ','0'},   {'0',' ',' ',' ','0',' ',' ',' ',' ','0'},   {'0',' ','0',' ',' ',' ','0',' ',' ','0'},   {'0',' ','0','0','0',' ','0','0',' ','0'},   {'0','0',' ',' ',' ',' ',' ',' ',' ','0'},   {'0','0','0','0','0','0','0','0','0','0'}               };    PosType start = {1,1};    PosType end = {8,8};    if(mazePath(maze,start,end))        printf("You can go through the maze~~\n");    else        printf("there is no path~~\n");    return 0;}

文件五：表达式求值

/********************** 声明部分 **********************/#include<stdio.h>  //输入输出函数头文件#include<stdlib.h>  //内存申请函数头文件#define STACK_INIT_SIZE 10  //定义最初申请的内存的大小#define STACK_INCREMENT 2  //每一次申请内存不足的时候扩展的大小#define OVERFLOW false  //异常抛出返回值#define FALSE false  //异常抛出返回值#define TRUE true //异常抛出返回值#define ERROR false  //异常抛出返回值#define INFEASIBLE false //异常抛出返回值#define OK true  //程序正确执行抛出返回值typedef int SElemType;  //别名声明，其实int可以用任意的名字代入typedef bool Status;  //别名声明#define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量/********************** 结构类型部分 **********************/struct SqStack{       //栈的数据元素类型在应用程序中定义typedef int SElemType;       SElemType *base; // 栈底指针       //在栈构造之前和销毁之后，base为NULL       SElemType *top; // 栈顶指针       //初值指向栈底，top = base可做栈空标记       //插入新栈顶元素时，top增1；删除栈顶元素时，top减1       //非空栈的top始终在栈顶元素的下一个位置上       int stacksize; // 当前已分配的存储空间，以元素为单位       //栈当前可使用的最大容量}; // 顺序栈/********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ // 构造一个空栈S       //栈底指针S.base指向新分配的STACK_INIT_SIZE个SElemType大小的空间       if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType))))              exit(OVERFLOW); // 存储分配失败       //必须给SqStack结构对象S的3个成员赋值       S.top = S.base; //空栈的栈顶指针S.top = 栈底指针S.base       S.stacksize = STACK_INIT_SIZE; //初始栈容量       return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ // 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR       if (S.top > S.base)       {              e = *(S.top - 1); //因为S.top指向栈顶元素的下一个位置，              //所以栈顶元素就是e = *(S.top - 1)              return OK;       }       else              return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ // 插入元素e为新的栈顶元素       if (S.top - S.base >= S.stacksize) // 栈满，追加存储空间              //如果栈长度大于栈容量       {              //可能会改变栈底地址，新栈底指针S.base              S.base = (SElemType *) realloc(S.base, //原栈底指针                     (S.stacksize + STACKINCREMENT) * sizeof (SElemType)); //新大小              if (!S.base)                     exit(OVERFLOW); // 存储分配失败              //给SqStack结构对象S的3个成员赋值              S.top = S.base + S.stacksize;              S.stacksize += STACKINCREMENT;       }       *(S.top)++ = e; //先把e压入栈顶，S.top再增1指向栈顶元素e的下一个位置       return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR       if (S.top == S.base) //如果空栈，报错              return ERROR;       e = *--S.top; //S.top先减1指向栈顶元素，再取值，交给e带回       return OK;}/********************** 判断两符号的优先关系 **********************/SElemType Precede(SElemType t1, SElemType t2){       SElemType f; //栈元素f，准备存放<、=、>供函数返回值使用       switch (t2)       {       case '+':       case '-':              if (t1 == '(' || t1 == '#') //(、# < +、-                     f = '<';              else //其余 > +、-                     f = '>';              break;       case '*':       case '/':              if (t1 == '*' || t1 == '/' || t1 == ')') //*、/、) > *、/                     f = '>';              else //其余 < *、/                     f = '<';              break;       case '(':              if (t1 == ')') //)后面不能紧跟(，紧跟报错              {                     printf("ERROR1\n");                     exit(ERROR);              }              else //其余 < (                     f = '<';              break;       case ')':              switch (t1)              {              case '(':                     f = '='; //( = )                     break;              case '#': //#后面不能紧跟)，紧跟报错                     printf("ERROR2\n");                     exit(ERROR);              default: //其余 > )                     f = '>';              }              break;              case '#':                     switch (t1)                     {                     case '#':                            f = '='; //# = #                            break;                     case '(': //(后面不能紧跟#，紧跟报错                            printf("ERROR3\n");                            exit(ERROR);                     default: //其余 > #                            f = '>';                     }       }       return f;}/********************** 判断是否为运算符 **********************/Status In(SElemType c){ // 判断c是否为运算符       switch (c)       {       case'+':       case'-':       case'*':       case'/':       case'(':       case')':       case'#':              return TRUE;       default:              return FALSE;       }}/********************** 计算函数 **********************/SElemType Operate(SElemType a, SElemType theta, SElemType b) //栈元素a、theta、b{ // 二元运算c = a theta b       SElemType c; //栈元素c，准备存放运算结果，供函数返回值使用       a = a - 48;       b = b - 48;       switch (theta)       {       case '+':              c = a + b + 48; //运算完毕后再把数字转换成字符              break;       case '-':              c = a - b + 48;              break;       case '*':              c = a * b + 48;              break;       case '/':              c = a / b + 48;       }       return c; //返回运算结果}/********************** 主算法函数 **********************/SElemType EvaluateExpression() // 算法3.4{      // 算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈       SqStack OPTR, OPND; //顺序栈OPTR、OPND       SElemType a, b, c, x, theta; //栈元素a、b、c、x、theta       InitStack(OPTR); //构造空栈OPTR，准备装运算符       Push(OPTR, '#'); //栈OPTR的栈底元素是#       InitStack(OPND); //构造空栈OPND，准备装操作数       //初始化循环变量       c = getchar(); //输入字符c       GetTop(OPTR, x); //取OPTR的栈顶元素交给x       //只要栈顶元素x、或输入字符c不为#，就循环       while (c != '#' || x != '#')       {              if (In(c)) // 如果c是7种运算符之一，In(c)返回TRUE              switch (Precede(x, c)) //比较栈顶元素x、输入字符c的优先权              {                case '<': // 如果栈顶元素x优先权低于输入字符c                    Push(OPTR, c); //输入字符c入运算符栈OPTR                    c = getchar(); //接收下个字符，准备下轮循环                    //接收不到就用原来在c中的值参加下轮和x的比较                    break;                case '=': // 如果栈顶元素x优先权等于输入字符c                    Pop(OPTR, x); //栈OPTR的栈顶元素出栈，赋给栈顶元素x                        //消括号(、)，只有(和)、#和#的优先权相等；                        //但是#不用这消，而是用while循环的判断条件消                        //(的优先权最高，)的优先权最低，                        //如果(在栈顶、)在输入，则( = )；                        //如果)在栈顶、(在输入，则报错                    c = getchar(); //接收下个字符，准备下轮循环                        //接收不到就用原来在c中的值参加下轮和x的比较                    break;                case '>': // 如果栈顶元素x优先权高于输入字符c                    Pop(OPTR, theta); // 栈顶元素x出运算符栈OPTR，赋给theta                    Pop(OPND, b); //操作数出操作数栈OPND，赋给b                    Pop(OPND, a); //操作数出操作数栈OPND，赋给a                    Push(OPND, Operate(a, theta, b)); //运算结果Operate(a, theta, b)入操作数栈OPND                    break;              }              else if (c >= '0' && c <= '9') // 如果c在0到9之间，是操作数              {                     Push(OPND, c); //操作数c入操作数栈OPND                     c = getchar(); //接收下个字符，准备下轮循环              }              else // 如果c既不是7种运算符也不是0到9的操作数，那么c是非法字符，报错              {                     printf("ERROR4\n");                     exit(ERROR);              }              GetTop(OPTR, x); //只要运算符栈OPTR的栈顶元素x或当前读入字符c不为#，              //就不断地取运算符栈OPTR的栈顶元素赋给x       }       //循环结束时，操作数栈OPND的栈顶元素是运算结果       GetTop(OPND, x); //取操作数栈OPND的栈顶元素（运算结果）赋给x       return x; //返回运算结果}int main(){       printf("请输入算术表达式（中间值及最终结果要在0～9之间），并以#结束\n");       printf("%c\n", EvaluateExpression()); //算术表达式求值       return 0;}

文件六：汉诺塔递归实现

/*********** 汉诺塔 *********/#include <stdio.h>int c = 0; // 全局变量，搬动次数//x源塔，第n个圆盘（编号n），z目标塔void move(char x, int n, char z){ // 将编号为n的圆盘从塔座x搬到塔座z       printf("第%i步: 将%i号盘从%c移到%c\n", ++c, n, x, z);}//n个圆盘（编号从1到n），x源塔，y辅助塔，z目标塔void hanoi(int n, char x, char y, char z){ // 将塔座x上按直径由小到大且自上而下编号为1至n的n个圆盘       // 按规则搬到塔座z上，y作辅助塔       if (n == 1)              move(x, 1, z); // 将编号为1的圆盘从塔座x搬到塔座z       else       {              hanoi(n - 1, x, z, y); // 将塔座x上编号为1至n - 1的圆盘搬到塔座y，z作辅助塔              move(x, n, z); // 将编号为n的圆盘从塔座x搬到塔座z              hanoi(n - 1, y, x, z); // 将塔座y上编号为1至n - 1的圆盘搬到塔座z，x作辅助塔       }}int main(){       int n;       printf("3个塔座为a、b、c，圆盘最初在a座，借助b座移到c座。请输入圆盘数：");       scanf("%d", &n);       hanoi(n, 'a', 'b', 'c'); // 将塔座a上编号为1至n的n个圆盘搬到塔座c上，b作辅助塔       return 0;}

1楼Wentasy6天前 20:41

[e01] 学习了。

Re: daringpig5天前 10:18: 回复Wentasyn相互学习~~

热点排行

C语言

史上最全最完整栈施用 C语言 源代码 可直接运行

史上最全最完整栈施用 C语言源代码可直接运行