# 数据结构(C语言版)第三章:栈和队列 原

fzyz_sb

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_STACK_SIZE 100
int stack[ MAX_STACK_SIZE ];
int top = -1;

/*

*/
void add( int *top, int element );

int delete( int *top );

int isFull();

int isEmpty();

int main( void )
{
int i = 0;
for ( i = 0; i < 10; i++ ){
}
while ( !isEmpty() ){
printf("%d ", delete( &top ) );
}

printf("\n");

return 0;
}

int isFull()
{
}

int isEmpty()
{
return -1 == top;
}

void add( int *top, int element )
{
if ( *top >= MAX_STACK_SIZE - 1 ){
printf("full\n");
return;
}

stack[ ++*top ] = element;
}

int delete( int *top )
{
if ( -1 == *top ){
printf("empty\n");
return -1;
}

return stack[ (*top)-- ];
}``````

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 10

int isFull( int queue[], int front, int rear );
int isEmpty( int queue[], int front, int rear );
void add( int queue[], int *front, int *rear, int element );
int delete( int queue[], int *front, int *rear );

int main( void )
{
int queue[ MAX_SIZE ];
int front = -1;
int rear = -1;
int i = 0;
for ( i = 0; i < 11; i++ ){
add( queue, &front, &rear, i );
}
printf("delete element:\n");
for ( i = 0; i < 5; i++ ){
printf("%d  ", delete( queue, &front, &rear ) );
}
for ( i = 100; i < 110; i++ ){
add( queue, &front, &rear, i );
}

printf("\nthe element is:\n");
for ( i = 0; i < MAX_SIZE; i++){
printf("%d ", queue[ i ] );
}
printf("front:%d---rear:%d\n", front, rear );

printf("\n");

return 0;
}

int isFull( int queue[], int front, int rear )
{
return !( ( front + 1 - rear ) % MAX_SIZE );
}

int isEmpty( int queue[], int front, int rear )
{
return ( front == rear );
}

void add( int queue[], int *front, int *rear, int element )
{
if ( isFull( queue, *front, *rear ) ){
printf("full\n");
return;
}
*front += 1;
*front %= MAX_SIZE;
queue[ *front ] = element;
}

int delete( int queue[], int *front, int *rear )
{
if ( isEmpty( queue, *front, *rear ) ){
printf("empty\n");
return -1;
}

*rear += 1;
*rear %= MAX_SIZE;
return queue[ *rear ];
}``````

3.3 迷宫问题

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int mark[ 11 ][ 8 ];	//用于标记走过的位置
//迷宫,9 * 7,增加的两行两列为1,用于当围墙
int maze[ 11 ][ 8 ] = { {1,1,1,1,1,1,1,1},{1,0,0,0,0,0,1,1},{1,1,1,1,1,1,0,1},{1,1,0,0,0,0,1,1},{1,0,1,1,1,1,1,1},{1,1,0,0,0,0,1,1},{1,1,1,1,1,1,0,1},{1,1,0,0,0,0,1,1},{1,0,1,1,1,1,1,1},{1,1,0,0,0,0,0,1},{1,1,1,1,1,1,1,1}};
#define EXIT_ROW 9
#define EXIT_COL 6
/*

*/
typedef struct OFFSETS{
short int vert;
short int horiz;
}Offsets;
Offsets move[ 8 ];

/*

*/
#define MAX_STACK_SIZE 100
typedef struct ELEMENT{
short int row;
short int col;
short int dir;
}Element;
Element stack[ MAX_STACK_SIZE ];
int top = -1;

Element delete( void )
{
if ( -1 == top ){
printf("the stack is empty\n");
}
return stack[ top-- ];
}

{
if ( MAX_STACK_SIZE == top + 1 ){
printf("the stack is full\n");
return;
}
stack[ ++top ] = position;
}

/*

*/
void initOffsets()
{
move[ 0 ].vert = -1;
move[ 0 ].horiz = 0;
move[ 1 ].vert = -1;
move[ 1 ].horiz = -1;
move[ 2 ].vert = 0;
move[ 2 ].horiz = 1;
move[ 3 ].vert = 1;
move[ 3 ].horiz = 1;
move[ 4 ].vert = 1;
move[ 4 ].horiz = 0;
move[ 5 ].vert = 1;
move[ 5 ].horiz = -1;
move[ 6 ].vert = 0;
move[ 6 ].horiz = -1;
move[ 7 ].vert = -1;
move[ 7 ].horiz = -1;
}

void path( void )
{
int i, row, col, next_row, next_col, dir, found = 0;
Element position;
mark[ 1 ][ 1 ] = 1;
position.row = 1;
position.col = 1;
position.dir = 0;
while ( top > -1 && !found ){
position = delete();
row = position.row;
col = position.col;
dir = position.dir;
while ( dir < 8 && !found ){
next_row = row + move[ dir ].vert;
next_col = col + move[ dir ].horiz;
if ( next_row == EXIT_ROW && next_col == EXIT_COL ){
found = 1;
}
else if ( !maze[ next_row ][ next_col ] && !mark[ next_row ][ next_col ] ){
mark[ next_row ][ next_col ] = 1;
position.row = row;
position.col = col;
position.dir = ++dir;
row = next_row;
col = next_col;
dir = 0;
}
else{
++dir;
}
}
}

if ( found ){
printf("the path is:\n");
for ( i = 0; i <= top; i++ ){
printf("(%d,%d)     ", stack[ i ].row, stack[ i ].col );
if ( 0 == ( i + 1 ) % 5 ){
printf("\n");
}
}
printf("(%d,%d)     ", row, col );
printf("(%d,%d)\n", EXIT_ROW, EXIT_COL );
}
else{
printf("the maze does not have a path\n");
}
}

int main( void )
{
initOffsets();
path();

return 0;
}``````

3.4 表达式求值

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_STACK_SIZE 100
int stack[ MAX_STACK_SIZE ];
int top = -1;

void eval( char *str )
{
int op1;
int op2;
while ( *str ){
if ( isdigit( *str ) ){
stack[ ++top ] = *str - '0';
str++;
continue;
}
else if ( ' ' == *str ){
str++;
continue;
}
else{
op1 = stack[ top-- ];
op2 = stack[ top-- ];
switch( *str ){
case '+' :
stack[ ++top ] = op2 + op1;
break;
case '-':
stack[ ++top ] = op2 - op1;
break;
case '*':
stack[ ++top ] = op2 * op1;
break;
case '/':
if ( 0 == op2 ){
printf("zero can not be dived\n");
return;
}
stack[ ++top ] = op2 / op1;
break;
case '%':
stack[ ++top ] = op2 % op1;
break;
}
str++;
}
}
}

int main( void )
{
char *str = "6 2 / 3 - 4 2 * +";
eval( str );

printf("%d\n", stack[ 0 ] );

return 0;
}``````

``````#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

/*

*/
void translate( char *str, char *result )
{
char *temp = result;
int isSub = 0;
int isMul = 0;
int isDiv = 0;
int isMod = 0;
int whatOpe = 0;
while ( *str ){
if ( isdigit( *str ) ){
if ( isMul || isDiv ){
while ( isMul && 3 != whatOpe ){
*result++ = '*';
isMul--;
}
while ( isDiv && 4 != whatOpe ){
*result++ = '/';
isDiv--;
}
}
else{
if ( isMod ){
while ( isMod && 5 != whatOpe ){
*result++ = '%';
isMod--;
}
}
else{
while ( isAdd && 1 != whatOpe ){
*result++ = '+';
}
while ( isSub && 2 != whatOpe ){
*result++ = '-';
isSub--;
}
}
}
*result++ = *str++;
continue;
}
else if ( ' ' == *str ){
str++;
continue;
}
else{
if ( '+' == *str ){
whatOpe = 1;
}
else if ( '-' == *str ){
isSub++;
whatOpe = 2;
}
else if ( '*' == *str ){
isMul++;
whatOpe = 3;
}
else if ( '/' == *str ){
isDiv++;
whatOpe = 4;
}
else if ( '%' == *str ){
isMod++;
whatOpe = 5;
}
str++;
}
}

while ( isMul ){
*result++ = '*';
isMul--;
}
while ( isDiv ){
*result++ = '/';
isDiv--;
}
while ( isMod ){
*result++ = '%';
isMod--;
}
*result++ = '+';
}
while ( isSub ){
*result++ = '-';
isSub--;
}
*result = '\0';
}

int main( void )
{
//	char *str = "6 2 / 3 - 4 2 * +";
//	char *str = "6 / 2 - 3 + 4 * 2";
char *str = "1 + 2 * 3 * 4 * 5 * 6";
char result[ 100 ];
memset( result, 0, sizeof( char ) * 100 );
translate( str, result );

printf("%s\n", result );

return 0;
}``````

3.5 多栈和多队列

``````#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100
#define N 10

int isFull( int fullarr[] )
{
int i = 0;
for ( i = 0; i < N; i++ ){
if ( 0 == fullarr[ i ] ){
return 0;
}
}

return 1;
}
int main( void )
{
int arr[ MAX_SIZE ];
int *p[ N ];
int fullarr[ N ];
int i = 0;
int index = 0;
memset( arr, 0, sizeof( int ) * MAX_SIZE );
memset( fullarr, 0, sizeof( int ) * N );
p[ 0 ] = arr;
for ( i = 1; i < N; i++ ){
index = ( MAX_SIZE / N ) * i;
p[ i ] = arr + index;
arr[ index - 1 ] = -1;
}
arr[ MAX_SIZE - 1 ] = -1;

srand( ( unsigned int )time( NULL ) );
for ( i = 0; i < MAX_SIZE; i++ ){
index = rand() % N;
if ( isFull( fullarr ) ){
break;
}
while ( fullarr[ index ] == 1 ){
index = rand() % N;
}
*p[ index ] = i;
p[ index ]++;
if ( -1 == *p[ index ] ){
fullarr[ index ] = 1;
}
}

for ( i = 0; i < MAX_SIZE; i++ ){
if ( -1 == arr[ i ] ){
printf("\n");
continue;
}
printf("%3d ", arr[ i ] );
}

return 0;
}``````

PS:开源中国怎么改页面的显示了:

### fzyz_sb

200 行 Java 代码搞定计算器程序

CarpenterLee
01/10
0
0

himayan46
2016/09/28
0
0

20111564
2014/10/16
0
0
《java数据结构和算法》读书笔记

《Java多线程编程核心技术》读书笔记 常用数据结构 第2章 数组 最简单的数据结构，在查找上比链表有优势，但是在插入与删除上比不上链表。 Java中的数组有长度限制，为int值。在内存模型中，...

2016/05/27
155
0

2012/03/09
318
1

9分钟前
0
0

kyle960
9分钟前
0
0
call方法的模拟实现

call方法的模拟实现 初步思考 const person = { name:"小明" } function sayName() { console.log(this.name) } sayName.call(person) //result: 小明 上面的代码有两...

lsner
13分钟前
0
0
apache 报错 AH01089: search for temporary

19分钟前
1
0
java源码Integer.bitCount算法解析，分析原理

117
21分钟前
0
0