3.1 ADT栈
这里就简单的用数组实现,如果为了扩展,推荐使用结构体:
#include#include #include #define MAX_STACK_SIZE 100int 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#include #include #define MAX_SIZE 10int 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#include #include 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 100typedef 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#include #include #include #define MAX_STACK_SIZE 100int 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#include #include #include /*不考虑括号的简单转换*/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#include #include #include #define MAX_SIZE 100#define N 10int 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:开源中国怎么改页面的显示了:
