【数据结构】——【栈】算法代码实现（C/C++语言实现）（整理不易，请多关注）
目录
1.顺序栈表示：类型和界面函数声明
2.顺序栈表示：函数定义
3.栈链接表示：类型和界面函数声明
4.栈链接表示：函数定义
5.简化背包问题的递归算法
6.简化背包问题的非递归算法
7.迷宫问题的递归算法
8.迷宫问题的非递归算法(栈实现)
1.顺序栈表示：类型和界面函数声明
enum { MAXNUM = 20 /* 栈中最大元素个数，应根据需要定义 */
};typedef int DataType; /* 栈中元素类型，应根据需要定义 */struct SeqStack
{ /* 顺序栈类型定义 */int t; /* 栈顶位置指示 */DataType s[MAXNUM];
};typedef struct SeqStack SeqSack, *PSeqStack; /* 顺序栈类型和指针类型 */ /*创建一个空栈;为栈结构申请空间，并将栈顶变量赋值为-1*/
PSeqStack createEmptyStack_seq( void );/*判断pastack所指的栈是否为空栈，当pastack所指的栈为空栈时，则返回1，否则返回0*/
int isEmptyStack_seq( PSeqStack pastack );/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x );/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack );/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack );2.顺序栈表示：函数定义
#include
#include #include "sstack.h"/*创建一个空栈;为栈结构申请空间，并将栈顶变量赋值为-1*/
PSeqStack createEmptyStack_seq( void )
{ PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack));if (pastack==NULL)printf("Out of space!! \n");elsepastack->t = -1;return pastack;
}/*判断pastack所指的栈是否为空栈，当pastack所指的栈为空栈时，则返回1，否则返回0*/
int isEmptyStack_seq( PSeqStack pastack )
{return pastack->t == -1;
}/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x )
{ if( pastack->t >= MAXNUM - 1 )printf( "Stack Overflow! \n" );else { pastack->t++;pastack->s[pastack->t] = x;}
}/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack )
{ if (pastack->t == -1 )printf( "Underflow!\n" );elsepastack->t--;
}/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack )
{return pastack->s[pastack->t];
} 3.栈链接表示：类型和界面函数声明
typedef int DataType;
struct Node; /* 单链表结点 */
typedef struct Node *PNode; /* 指向结点的指针类型 */struct Node
{ /* 单链表结点结构 */DataType info;PNode link;
};struct LinkStack
{ /* 链接栈类型定义 */PNode top; /* 指向栈顶结点 */
};typedef struct LinkStack *PLinkStack; /* 链接栈类型的指针类型 *//*申请链栈结构空间，创建一空链接栈，返回指向空链接栈的指针*/
PLinkStack createEmptyStack_link(void);/*判单链形式栈是否为空栈*/
int isEmptyStack_link( PLinkStack plstack );/* 在栈中压入一元素x */
void push_link( PLinkStack plstack, DataType x );/*出栈*/
void pop_link( PLinkStack plstack );/* 对非空栈求栈顶元素 */
DataType top_link( PLinkStack plstack );4.栈链接表示：函数定义
#include
#include#include "lstack.h"/*申请链栈结构空间，创建一空链接栈，返回指向空链接栈的指针*/
PLinkStack createEmptyStack_link(void)
{PLinkStack plstack;plstack = (PLinkStack )malloc( sizeof(struct LinkStack));if (plstack != NULL)plstack->top = NULL;elseprintf("Out of space! \n"); return plstack;
}/*判单链形式栈是否为空栈*/
int isEmptyStack_link( PLinkStack plstack )
{return plstack->top == NULL;
}/* 在栈中压入一元素x */
void push_link( PLinkStack plstack, DataType x )
{ PNode p;p = (PNode)malloc( sizeof( struct Node ) );if ( p == NULL )printf("Out of space!\n");
else
{ p->info = x;p->link = plstack->top;plstack->top = p;}
}/*出栈*/
void pop_link( PLinkStack plstack )
{ if( isEmptyStack_link( plstack ) )printf( "Empty stack pop.\n" );
else
{ PNode p = plstack->top;plstack->top = plstack->top->link;free(p);}
}/* 对非空栈求栈顶元素 */
DataType top_link( PLinkStack plstack )
{return plstack->top->info;
} 5.简化背包问题的递归算法
#include
#includeint knap(int s, int n, int w[])
{if ( s == 0 )return (1);else if ( s<0 || s>0 && n<1 )return(0);
else if ( knap(s - w[n-1], n - 1, w)==1 )
{ printf("result: n=%d ,w[%d]=%d \n", n, n-1, w[n-1]);return (1);}elsereturn ( knap(s, n - 1, w) );
}int main()
{int* w;int s = 0, n = 0, result = 0, i = 0;printf("please input s = ");/*输入s*/scanf("%d", &s);printf("please input n = ");/*输入n*/scanf("%d", &n);w = (int*)malloc(n*sizeof(int));printf("please input the %d numbers(weight):\n", n);/*输入重量*/for (i = 0; i < n; i++)scanf("%d", w+i);result = knap(s, n, w);if (result == 0)printf("no solution!\n");return 0;
} 6.简化背包问题的非递归算法
#include
#include
#define MAXNUM 20
#define TRUE 1
#define FALSE 0struct NodeBag { /* 栈中元素的定义 */int s , n ;int r ; /* r的值为1,2,3 */int k;
};typedef struct NodeBag DataType;struct SeqStack
{ /* 顺序栈类型定义 */int t; /* 指示栈顶位置 */DataType s[MAXNUM];
};typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */PSeqStack createEmptyStack_seq( void )
{PSeqStack pastack;pastack = (PSeqStack)malloc(sizeof(struct SeqStack));if (pastack==NULL)printf("Out of space!! \n");elsepastack->t=-1;return (pastack);
}/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x )
{ if( pastack->t >= MAXNUM - 1 )printf( "Overflow! \n" );else {pastack->t++;pastack->s[pastack->t] = x;}
}/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack )
{ if (pastack->t == -1 )printf( "Underflow!\n" );elsepastack->t--;
}/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack )
{return pastack->s[pastack->t];
}int nknap(int s, int n, int w[])
{ struct NodeBag x; PSeqStack st; int k;st = createEmptyStack_seq( ); /* entry0: 初始调用入口 */x.s = s; x.n = n; x.r = 1; push_seq(st,x);
entry1: /* 递归调用入口 */x = top_seq(st);pop_seq(st); /* 该函数与后面最接近的一个push_seq函数对是为了完成修改栈顶元素 */
if (x.s == 0)
{ x.k = TRUE; push_seq(st,x); goto exit2; }
else if (x.s<0 || (x.s>0 && x.n<1))
{x.k = FALSE;push_seq(st,x);goto exit2;}
else
{push_seq(st,x); /* 由于此处需要进一步往下递归，所以需再次入栈 */x.s = x.s - w[x.n-1]; x.n = x.n - 1; x.r = 2; push_seq(st, x); goto entry1;}
exit2: /* 返回处理 */x = top_seq(st);pop_seq(st);
switch (x.r)
{ case 1:free(st);return(x.k);case 2: goto L3;case 3: goto L4; }L3: /* 继续处理1 */
if (x.k == TRUE)
{ x = top_seq(st);pop_seq(st); x.k = TRUE; push_seq(st,x);printf("result n=%d , w=%d \n", x.n, w[x.n-1]); goto exit2; }
else
{ x = top_seq(st);x.s = x.s; x.n = x.n - 1; x.r = 3; push_seq(st,x); goto entry1; }
L4: /* 继续处理2 */k = x.k; x = top_seq(st); pop_seq(st); x.k = k; push_seq(st,x); goto exit2;
}int main()
{int* w;int s = 0, n = 0, result = 0, i = 0;printf("please input s = ");/*输入s*/scanf("%d", &s);printf("please input n = ");/*输入n*/scanf("%d", &n);w = (int*)malloc(n*sizeof(int));printf("please input the %d numbers(weight):\n", n);/*输入重量*/for (i = 0; i < n; i++)scanf("%d", w+i);result = nknap(s,n, w);if (result == 0)printf("no solution!\n");return 0;
} 7.迷宫问题的递归算法
#include
#include #define M 8
#define N 11 /* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
int mazePath(int* maze[], int* direction[], int x1, int y1, int x2, int y2)
{int k,g,h;
for (k = 0; k < 4; k++)
{g = x1 + direction[k][0];h = y1 + direction[k][1];if (g == x2 && h == y2 && maze[g][h] == 0)
{ /* 找到路径*/printf("The revers path is:\n");printf("the node is: %d %d\n",x2,y2);printf("the node is: %d %d\n",x1,y1);return 1;}if(maze[g][h] == 0)
{maze[g][h] = 2;if (mazePath(maze, direction, g, h, x2, y2) == 1)
{/*如能找到路径*/printf("the node is: %d %d\n",x1,y1);return 1;}}}return 0;
}int direction[][2] = {0,1,1,0,0,-1,-1,0};
int maze[][N] =
{1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1
};int main()
{int *m[M] ; int *d[4];int i;for (i = 0; i < M; i++)m[i] = maze[i]; for (i = 0; i < 4; i++)d[i] = direction[i];mazePath(m, d, 1, 1, 6, 9);getchar();return 0;
} 8.迷宫问题的非递归算法(栈实现)
#define MAXNUM 100/* 栈中最大元素个数 */
#define N 11 /*地图的第一维长度*/
#include
#include typedef struct
{int x;/* 行下标 */int y;/* 列下标 */int d;/* 运动方向 */
} DataType;struct SeqStack
{ /* 顺序栈类型定义 */int t; /* 指示栈顶位置 */DataType s[MAXNUM];
};typedef struct SeqStack *PSeqStack; /* 顺序栈类型的指针类型 */
PSeqStack pastack; /* pastack是指向顺序栈的一个指针变量 */PSeqStack createEmptyStack_seq( void )
{PSeqStack pastack;pastack = (PSeqStack)malloc(sizeof(struct SeqStack));if (pastack == NULL)printf("Out of space!! \n");elsepastack->t = -1;return pastack;
}int isEmptyStack_seq( PSeqStack pastack )
{return pastack->t == -1;
}/* 在栈中压入一元素x */
void push_seq( PSeqStack pastack, DataType x )
{if( pastack->t >= MAXNUM - 1 )printf( "Overflow! \n" );else {pastack->t++;pastack->s[pastack->t] = x;}
}/* 删除栈顶元素 */
void pop_seq( PSeqStack pastack )
{if (pastack->t == -1 )printf( "Underflow!\n" );elsepastack->t--;
}/* 当pastack所指的栈不为空栈时，求栈顶元素的值 */
DataType top_seq( PSeqStack pastack )
{return (pastack->s[pastack->t]);
}void pushtostack(PSeqStack st, int x, int y, int d)
{DataType element;element.x = x;element.y = y;element.d = d;push_seq(st, element);
}void printpath(PSeqStack st)
{DataType element;printf("The revers path is:\n"); /* 打印路径上的每一点 */
while(!isEmptyStack_seq(st))
{element = top_seq(st);pop_seq(st);printf("the node is: %d %d \n", element.x, element.y);}
}/* 迷宫maze[M][N]中求从入口maze[x1][y1]到出口maze[x2][y2]的一条路径 */
/* 其中 1<=x1,x2<=M-2 , 1<=y1,y2<=N-2 */
void mazePath(int maze[][N], int direction[][2], int x1, int y1, int x2, int y2)
{int i, j, k, g, h;PSeqStack st;DataType element;st = createEmptyStack_seq( );maze[x1][y1] = 2; /* 从入口开始进入,作标记 */ pushtostack(st, x1, y1, -1); /* 入口点进栈 */while ( !isEmptyStack_seq(st))
{ /* 走不通时,一步步回退 */element = top_seq(st);pop_seq(st);i = element.x; j = element.y; for (k = element.d + 1; k <= 3; k++)
{ /* 依次试探每个方向 */g = i + direction[k][0];h = j + direction[k][1];if (g == x2 && h == y2 && maze[g][h] == 0)
{ /* 走到出口点 */printpath(st); /* 打印路径 */return;}if (maze[g][h] == 0)
{ /* 走到没走过的点 */maze[g][h] = 2; /* 作标记 */pushtostack(st, i, j, k); /* 进栈 */i = g; j = h; k = -1; /* 下一点转换成当前点 */}}}printf("The path has not been found.\n");/* 栈退完未找到路径 */
}int main()
{int direction[][2]={0,1,1,0,0,-1,-1,0};int maze[][N] = {1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,0,0,0,1,0,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,1,1,1,0,0,1,0,1,1,0,0,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1};mazePath(maze,direction,1,1,6,9);getchar();return 0;
} 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！