文档章节

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

fzyz_sb
 fzyz_sb
发布于 2013/12/05 00:20
字数 1594
阅读 162
收藏 2
点赞 0
评论 0

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:开源中国怎么改页面的显示了:



© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
200 行 Java 代码搞定计算器程序

原文出处:CarpenterLee 发现了大学时候写的计算器小程序,还有个图形界面,能够图形化展示表达式语法树,哈哈;) 只有200行Java代码,不但能够计算加减乘除,还能够匹配小括号~ 代码点评: ...

CarpenterLee
01/10
0
0
算法-第四版习题索引汇总

算法-第四版习题索引汇总 持续更新中。。。 第一章 基础 算法-第四版-1.1 基础编程模型-习题索引汇总 算法-第四版-1.2 数据抽象-习题索引汇总 算法-第四版-1.3 背包、队列和栈-习题...

himayan46
2016/09/28
0
0
考研-专业课-c语言

为了我家娘子,猪猪臭 本人计划考研:报考学校北京工业大学--计算机 专业课编号985:教材为C语言程序设计案例教程和严蔚敏的数据结构那本 我知道 本书是没有答案的 下面的全都是 自己写的 并在...

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

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

刀狂剑痴
2016/05/27
155
0
推荐阅读的多核编程技术书籍

多核编程技术好书推荐 多核程序设计技术——通过软件多线程提升性能 , 作 者: (孟加拉)阿克特(Akhter,S.),(美)罗伯茨(Roberts,J.) 著,李宝峰,富弘毅,李韬 译 本书从原理、技术...

晨曦之光
2012/03/09
318
1
C语言实现数据结构之栈的详解

在函数调用的过程中,需要的就是先进后出的特点,因此,栈就出现了。 栈是一种数据结构,是计算机怎么处理程序运行的一种方式。具有先进后出的特点,下面看的就是这些抽象的数据结构怎么用C...

ningcaichen66
2017/09/21
0
0
Java数据结构与算法(第四章栈和队列)

本章涉及的三种数据存储类型:栈、队列和优先级队列。 不同类型的结构 程序员的工具 数组是已经介绍过的数据存储结构,和其他结构(链表、树等等)一样,都适用于数据应用中作数据记录。 然而...

小风89
2015/10/24
250
0
入职学习(2)--一个程序员的成长史(22)

看了代是雄对这几个问题的回复之后,唐师傅叫代是雄先熟悉一下办公的电脑及一些办事流程,他要找一些资料作为培训计划中的材料。 代是雄先到公司的IT网站上去逛了一下,发现上面的东西相当的...

zhouzxi
2017/01/12
0
0
业余爱好者的C程序设计学习之路

我学习和工作的方向都是化工,和 IT 专业一点边都不搭,属于程序设计爱好者一类。坚持了很多年了,谈谈我的认识。 一、为什么是C 汇编太难,直接下手会吓死宝宝的。 basic 不能考虑,因为“对...

四彩
2016/02/04
107
2
数据结构(C语言版)第九章:堆结构

9.1 最小-最大堆 双端优先队列是一种支持如下操作的数据结构: 1. 插入一个具有任意关键字值的元素. 2. 删除关键字值最大的元素. 3. 删除关键字值最小的元素. 当仅支持插入和其中的一种删除操...

fzyz_sb
2013/12/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周一乱弹 —— 你的朋友圈有点生锈了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @Devoes :分享Trademark的单曲《Only Love (电视剧《妙手仁心 II》插曲)》: 《Only Love (电视剧《妙手仁心 II》插曲)》- Trademark 手机党少...

小小编辑
今天
162
6
【面试题】盲人坐飞机

有100位乘客乘坐飞机,其中有一位是盲人,每位乘客都按自己的座位号就坐。由于盲人看不见自己的座位号,所以他可能会坐错位置,而自己的座位被占的乘客会随便找个座位就坐。问所有乘客都坐对...

garkey
今天
1
0
谈谈神秘的ES6——(二)ES6的变量

谈谈神秘的ES6——(二)ES6的变量 我们在《零基础入门JavaScript》的时候就说过,在ES5里,变量是有弊端的,我们先来回顾一下。 首先,在ES5中,我们所有的变量都是通过关键字var来定义的。...

JandenMa
今天
1
0
arts-week1

Algorithm 594. Longest Harmonious Subsequence - LeetCode 274. H-Index - LeetCode 219. Contains Duplicate II - LeetCode 217. Contains Duplicate - LeetCode 438. Find All Anagrams ......

yysue
今天
2
0
NNS拍卖合约

前言 关于NNS的介绍,这里就不多做描述,相关的信息可以查看NNS的白皮书http://doc.neons.name/zh_CN/latest/nns_background.html。 首先nns中使用的竞价货币是sgas,关于sgas介绍可以戳htt...

红烧飞鱼
今天
1
0
Java IO类库之管道流PipeInputStream与PipeOutputStream

一、java管道流介绍 在java多线程通信中管道通信是一种重要的通信方式,在java中我们通过配套使用管道输出流PipedOutputStream和管道输入流PipedInputStream完成线程间通信。多线程管道通信的...

老韭菜
今天
0
0
AB 压力测试

Ubuntu 安装AB apapt-get install apache2-utils 使用AB 压力测试 -c 并发数 -n请求总数 ab -c 3000 -n 10000 http://localhost/test/index.php AB只能测试localhost 返回结果 This is Apac......

xiawet
今天
0
0
用Python绘制红楼梦词云图,竟然发现了这个!

Python在数据分析中越来越受欢迎,已经达到了统计学家对R的喜爱程度,Python的拥护者们当然不会落后于R,开发了一个个好玩的数据分析工具,下面我们来看看如何使用Python,来读红楼梦,绘制小...

猫咪编程
今天
1
0
Java中 发出请求获取别人的数据(阿里云 查询IP归属地)

1.效果 调用阿里云的接口 去定位IP地址 2. 代码 /** * 1. Java中远程调用方法 * http://localhost:8080/mavenssm20180519/invokingUrl.action * @Title: invokingUrl * @Description: * @ret......

Lucky_Me
今天
1
0
protobuf学习笔记

相关文档 Protocol buffers(protobuf)入门简介及性能分析 Protobuf学习 - 入门

OSC_fly
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部