数据结构(C语言版)第三章:栈和队列
博客专区 > fzyz_sb 的博客 > 博客详情
数据结构(C语言版)第三章:栈和队列
fzyz_sb 发表于4年前
数据结构(C语言版)第三章:栈和队列
  • 发表于 4年前
  • 阅读 150
  • 收藏 2
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

3.1 ADT栈

这里就简单的用数组实现,如果为了扩展,推荐使用结构体:

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

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

/*
这里用*top,只是当top为局部变量时候,通过指针可以修改top,如果top为全局,则没必要
*/
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++ ){
		add( &top, i );
	}
	while ( !isEmpty() ){
		printf("%d ", delete( &top ) );
	}

	printf("\n");

	return 0;
}

int isFull()
{
	return top == MAX_STACK_SIZE - 1;
}

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



堆栈在实际的应用中倒很少涉及到,更多的是链表.程序输出:


3.2 ADT队列

循环队列的实现:

每个人的实现方法不一样,但最主要的是:你懂得原理,知道怎么回事,这才是最重要的:

#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-- ];
}

void add( Element position )
{
	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;
	add( position );
	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;
				add( position );
				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 isAdd = 0;
	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++ = '+';
						isAdd--;
					}
					while ( isSub && 2 != whatOpe ){
						*result++ = '-';
						isSub--;
					}
				}
			}
			*result++ = *str++;
			continue;
		}
		else if ( ' ' == *str ){
			str++;
			continue;
		}
		else{
			if ( '+' == *str ){
				isAdd++;
				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--;
	}
	while ( isAdd ){
		*result++ = '+';
		isAdd--;
	}
	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 多栈和多队列

编写一个函数,将一个数组分成几部分,随机进行存储直到数组存满.如何判断单独的部分是满的则是一个难点.这里用到指针,更方便进行存储.用-1来表示单独部分的末尾--->判断是否已满:

#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;
}



这里用到了指针数组的知识,属于比较容易出错的程序.如果熟悉C++,推荐使用C++的容器来实现.话说C++11很牛逼,找段时间学习一下.程序输出:

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



标签: 数据结构 C
共有 人打赏支持
粉丝 362
博文 209
码字总数 447144
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: