《数据结构实验与实训教程（第4版）》程序代码(5)

sout[ off++ ] = c; } pushc( s, MAXN, &top, sin[i] ); /* '+','-'符号入栈 */ break; case '*': /* 为'*','/', 将栈顶'*','/'符号出栈, 存入数组 */ case '/': while( top>0 && (s[top-1] == '*' || s[top-1] == '/' ) ){ popc( s, &top, &c );

sout[ off++ ] = c;

} /*这段循环如何用if语句实现？ */

pushc( s, MAXN, &top, sin[i] ); /* '*','/'符号入栈 */ break; } while( 6 ) /* 所有元素出栈, 存入数组 */ sout[ off++ ] = c; sout[ off ] = '\\0'; /* 加休止符 */ return 0; }

void main() { char *sin; /* 输入表达式指针, 中缀表示 */ char *sout; /* 输出表达式指针, 后缀表示 */

int i; sin = (char *)malloc( 1024 * sizeof(char) ); sout = (char *)malloc( 1024 * sizeof(char) ); if( 7 ) { printf( \内存申请错误!\\n\ return; }

printf( \请输入表达式: \

gets( sin );

if( 8 ) { /* 转换成功 */ printf( \后缀表达式为:[%s]\\n\ switch( 9 ) { case 0: printf( \计算结果为: [%d]\\n\ break; case -1:

printf( \表达式错误\\n\

20

} } }

break; case -2: printf( \栈操作错误\\n\ break;

21

实验4 队列的基本操作

四、参考程序

程序1：题1 链接队列的基本操作函数 #include #include

typedef struct queue { /* 定义队列结构 */ int data; /* 队列元素类型为int */ struct queue *link; }QUEUE;

void EnQueue( QUEUE **head, QUEUE **tail, int x ) /* 进队操作 */ { QUEUE *p;

p = (QUEUE *)malloc( sizeof(QUEUE) ); 1 p->link = NULL; /* 队尾指向空 */

if( *head == NULL ) /* 队首为空，即为空队列 */ 2 else {

(*tail)->link = p; /* 新单元进队列尾 */

*tail = p; /* 队尾指向新入队单元 */ } }

int DeQueue( QUEUE **head, QUEUE **tail, int *cp ) /* 出队操作 1:对空 */ { QUEUE *p;

p = *head; if( *head == NULL ) /* 队空 */ return 1; *cp = (*head)->data; *head = 3 if( *head == NULL ) /* 队首为空，队尾也为空 */ *tail = NULL; free( p ); /* 释放单元 */ return 0;

22

}

void OutputQueue( QUEUE *head ) /* 输出队列中元素 */ { while 4 () { printf( \ head = head->link; }

printf( \

程序2：题2 主程序： void main() { QUEUE *head, *tail; int op, i; head = tail = NULL; /* 1 */

while( 1 ) { printf( \请选择操作，1：进队 2：出队 0：退出 \ fflush( stdin ); /* 清空标准输入缓冲区 */ scanf( \ switch( op ) { case 0: /* 退出 */

return;

case 1: /* 进队 */

printf( \请输入进队元素：\ scanf( \ 2 ; printf( \队内元素为:\\n\ OutputQueue( head ); break; case 2: /* 出队 */ if( 3 == 0 ) { /* 出队成功 */ printf( \出队元素为: [%d] , 队内元素为:\\n\ OutputQueue( head ); }

else printf( \队空\\n\

break;

}

23

}

}

程序3：题3 环型队列的基本操作函数 #include #include

#define MAXN 11 /* 定义环行顺序队列的存储长度 */

int EnQueue( int *queue, int maxn, int *head, int *tail, int x )/* 进队操作, 返回1:队满 */

{ if( 1 == *head ) /* 队尾指针赶上队首指针, 队满 */ return 1;

*tail = 2 /* 队尾指针+1 */ queue[*tail] = x; /* 元素入对尾 */ return 0; }

int DeQueue( int *queue, int maxn, int *head, int *tail, int *cp ) /* 出队操作 返回1:队空 */ { if( *head == *tail ) /* 队首=队尾, 表明队列为空 */ return 1; *head = ( *head + 1 ) % maxn; /* 队首指针+1 */ 3 /* 取出队首元素 */

return 0; }

void OutputQueue( int *queue, int maxn, int h, int t ) /* 输出队列中元素 */ { while( 4 ) { /* */ h = ( h + 1 ) % maxn;

printf( \

}

printf( \}

程序4：题4 主程序： void main() { int q[MAXN]; /* 假设环行队列的元素类型为int */

24