华南农业大学数据结构上机答案实验(共59页)

1、精选优质文档-倾情为你奉上华南农业大学数据结构上机答案实验 8583 顺序栈的基本操作时间限制:1000MS 内存限制:1000K提交次数:530 通过次数:212 题型: 编程题 语言: 无限制Description创建一个空的顺序栈，并实现栈的入栈、出栈、返回栈的长度、返回栈顶元素、栈的遍历等基本算法。请将下#include<malloc.h> #include<stdio.h> #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 / 存储空间初始分配量#define STACKINCREMENT 10 /

2、存储空间分配增量typedef int SElemType; / 定义栈元素类型typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等struct SqStackSElemType *base; / 在栈构造之前和销毁之后，base的值为NULLSElemType *top; / 栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位; / 顺序栈Status InitStack(SqStack &S) / 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZE/ 请补全代码S.base=(SElemType

3、*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e) / 在栈S中插入元素e为新的栈顶元素/ 请补全代码if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(

4、!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e) / 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR/ 请补全代码if(S.top=S.base) return ERROR;e=*-S.top;return OK;Status GetTop(SqStack S,SElemType &e) / 若栈不空，则用e返回S的栈顶元素，并返回O

5、K；否则返回ERROR/ 请补全代码if(S.top=S.base) return ERROR;e=*(S.top-1);return OK;int StackLength(SqStack S) / 返回栈S的元素个数/ 请补全代码return S.top-S.base;Status StackTraverse(SqStack S)/ 从栈顶到栈底依次输出栈中的每个元素SElemType *p = (SElemType *)malloc(sizeof(SElemType); p = S.top ; /请填空if(S.top=S.base)printf("The Stack is Em

6、pty!"); /请填空elseprintf("The Stack is: ");p-;while(p>=S.base) /请填空printf("%d ", *p);p- ; /请填空printf("n");return OK;int main()int a;SqStack S;SElemType x, e;if(InitStack(S) / 判断顺序表是否创建成功，请填空printf("A Stack Has Created.n");while(1)printf("1:Push n2:P

7、op n3:Get the Top n4:Return the Length of the Stackn5:Load the Stackn0:ExitnPlease choose:n");scanf("%d",&a);switch(a)case 1: scanf("%d", &x);if(!Push(S,x) printf("Push Error!n"); / 判断Push是否合法，请填空else printf("The El ement %d is Successfully Pushed!n&qu

8、ot;, x); break;case 2: if(!Pop(S,e) printf("Pop Error!n"); / 判断Pop是否合法，请填空else printf("The Element %d is Successfully Poped!n", e);break;case 3: if(!GetTop(S,e)printf("Get Top Error!n"); / 判断Get Top是否合法，请填空else printf("The Top Element is %d!n", e);break;case 4

9、: printf("The Length of the Stack is %d!n",StackLength(S); /请填空break;case 5: StackTraverse(S); /请填空break;case 0: return 1;8584 循环队列的基本操作时间限制:1000MS 内存限制:1000K提交次数:366 通过次数:157 题型: 编程题 语言: 无限制Description创建一个空的循环队列，并实现入队、出队、返回队列的长度、返回队头元素、队列的遍历等基本算法。请将下面的程序补充完整。#include<malloc.h> #incl

10、ude<stdio.h> #define OK 1#define ERROR 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef int QElemType;#define MAXQSIZE 100 / 最大队列长度(对于循环队列，最大队列长度要减1)typedef structQElemType *base; / 初始化的动态分配存储空间int front; / 头指针,若队列不空,指向队列头元素int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置SqQueue;Status InitQueue

11、(SqQueue &Q) / 构造一个空队列Q，该队列预定义大小为MAXQSIZE/ 请补全代码Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base) return ERROR;Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue &Q,QElemType e) / 插入元素e为Q的新的队尾元素/ 请补全代码if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%M

12、AXQSIZE;return OK;Status DeQueue(SqQueue &Q, QElemType &e) / 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR/ 请补全代码if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;Status GetHead(SqQueue Q, QElemType &e)/ 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR/ 请补全代码if(Q.front=Q.

13、rear) return ERROR;e=Q.baseQ.front;return OK;int QueueLength(SqQueue Q) / 返回Q的元素个数/ 请补全代码return (Q.rear+MAXQSIZE-Q.front)%MAXQSIZE;Status QueueTraverse(SqQueue Q) / 若队列不空，则从队头到队尾依次输出各个队列元素，并返回OK；否则返回ERROR.int i;i=Q.front;if(Q.front=Q.rear)printf("The Queue is Empty!"); /请填空elseprintf("

14、;The Queue is: ");while(i<Q.rear) /请填空printf("%d ",Q.basei); /请填空i = i+1; /请填空printf("n");return OK;int main()int a;SqQueu e S;QElemType x, e;if(InitQueue(S) / 判断顺序表是否创建成功，请填空printf("A Queue Has Created.n");while(1)printf("1:Enter n2:Delete n3:Get the Front

15、 n4:Return the Length of the Queuen5:Load the Queuen0:ExitnPlease choose:n");scanf("%d",&a);switch(a)case 1: scanf("%d", &x);if(!EnQueue(S,x) printf("Enter Error!n"); / 判断入队是否合法，请填空else printf("The Element %d is Successfully Entered!n", x); break;

16、case 2: if(!DeQueue(S,e) printf("Delete Error!n"); / 判断出队是否合法，请填空else printf("The Element %d is Successfully Deleted!n", e);break;case 3: if(!GetHead(S,e)printf("Get Head Error!n"); / 判断Get Head是否合法，请填空else printf("The Head of the Queue is %d!n", e);break;case

17、 4: printf("The Length of the Queue is %d!n",QueueLength(S); /请填空break;case 5: QueueTraverse(S); /请填空break;case 0: return 1;8585 栈的应用进制转换时间限制:1000MS 内存限制:1000K提交次数:320 通过次数:203 题型: 编程题 语言: 无限制Description利用顺序栈的基本操作算法，编写满足下列要求的数制转换程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。 #include<malloc.h> #

18、include<stdio.h>#include<stdlib.h>#define OVERFLOW -1 #define OK 1#define ERROR 0#define STACK_INIT_SIZE 20 / 存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量typedef int SElemType; / 定义栈元素类型typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等typedef struct SqStackSElemType *base; / 在栈构造之前和销毁

19、之后，base的值为NULLSElemType *top; / 栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位SqStack; / 顺序栈Status InitStack(SqStack &S) / 构造一个空栈S，该栈预定义大小为STACK_INIT_SIZES.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; Status Push

20、(SqStack &S,SElemType e) / 在栈S中插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize)S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status StackTraverse(SqStack S)/ 从栈顶到栈底依

21、次输出栈中的每个元素SElemType *p; p = S.top; /请填空if(!p)printf("The Stack is Empty!"); /请填空elsep-; while(p!=S.base) /请填空 printf("%d", *p);p-; /请填空printf("%d", *p);printf("n");return OK;Status Modulo (SqStack &S,int x)int y=x;if(y!=0)Push(S,y%8);Modulo(S,y/8); return

22、OK;int main()int a;SqStack S;SElemType x, e;InitStack(S); scanf("%d", &x);Modulo(S,x); StackTraverse(S);8586 括号匹配检验时间限制:1000MS 内存限制:1000K提交次数:679 通过次数:182 题型: 编程题 语言: 无限制Description利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即()或()等为正确的格式，(或()或()均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配

23、对。本题给出部分check()函数，要求将check()函数补充完整，并完成整个程序。typedef char SElemType;#include"malloc.h" #include"stdio.h"#include"math.h"#include"stdlib.h" / exit()#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等#define

24、STACK_INIT_SIZE 10 / 存储空间初始分配量#define STACKINCREMENT 2 / 存储空间分配增量struct SqStackSElemType *base; / 在栈构造之前和销毁之后，base的值为NULLSElemType *top; / 栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位; / 顺序栈Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR

25、;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; Status StackEmpty(SqStack S)if(S.top=S.base) return TRUE;else return FALSE;Status Push(SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) return E

26、RROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK;void check() / 对于输入的任意一个字符串，检验括号是否配对SqStack s;SElemType ch80,*p,e;if(InitStack(s) / 初始化栈成功/printf("请输入表达式n");scanf(&quo

27、t;%s",ch);p=ch;while(*p) / 没到串尾switch(*p)case '(':case '':Push(s,*p);p+;break; / 左括号入栈，且p+case ')':case '':if(!StackEmpty(s) / 栈不空Pop(s,e); / 弹出栈顶元素if(*p=')'&&e!='('|*p=''&&e!='') / 弹出的栈 顶元素与*p不配对printf("isn

28、9;t matched pairsn");exit(ERROR);elsep+;break; / 跳出switch语句else / 栈空printf("lack of left parenthesisn");exit(ERROR);default: p+; / 其它字符不处理，指针向后移if(StackEmpty(s) / 字符串结束时栈空printf("matchingn");elseprintf("lack of right parenthesisn");int main()check();8587 行编辑程序时间限制:

29、1000MS 内存限制:1000K提交次数:578 通过次数:173 题型: 编程题 语言: 无限制Description利用栈编写简单的行编辑程序：接受用户从终端输入的程序或数据，在输入过程中，允许用户输入出差错，并在发现有误时可以及时更正。例如：当用户发现刚刚键入的一个字符是错的时，可以补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“”，以表示当前行中的字符均无效。例如：假设从终端接受了这样两行字符： whli#ilr#e (s#*s) outchaputchar(*s=#+); 则实际有效的是下列两行： while (*s) p

30、utchar(*s+); 本题目给出部分函数，要求将行编辑函数补充完整，并完成整个程序。 typedef char SElemType;#include"malloc.h" #include"stdio.h"#include"math.h"#include"stdlib.h" / exit()#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等#defin

31、e STACK_INIT_SIZE 10 / 存储空间初始分配量#define STACKINCREMENT 2 / 存储空间分配增量struct SqStackSElemType *base; / 在栈构造之前和销毁之后，base的值为NULLSElemType *top; / 栈顶指针int stacksize; / 当前已分配的存储空间，以元素为单位; / 顺序栈Status InitStack(SqStack &S) / 构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)

32、return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S) / 若栈S为空栈，则返回TRUE，否则返回FALSEif(S.top=S.base) return TRUE;else return FALSE;Status ClearStack(SqStack &S) / 把S置为空栈S.top=S.base;return OK;Status DestroyStack(SqStack &S) / 销毁栈S，S不再存在free(S.base);S.base=N

33、ULL;S.top=NULL;S.stacksize=0;return OK;Status Push(SqStack &S,SElemType e) / 插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S. stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;retur

34、n OK;Status Pop(SqStack &S,SElemType &e)/ 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top=S.base) return ERROR;e=*-S.top;return OK;Status StackTraverse(SqStack S,Status(*visit)(SElemType)/ 从栈底到栈顶依次对栈中每个元素调用函数visit()。/ 一旦visit()失败，则操作失败while(S.top>S.base)visit(*S.base+);printf("n")

35、;return OK;Status visit(SElemType c)printf("%c",c);return OK;void LineEdit() / 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2SqStack s;char ch,c;int n,i;InitStack(s);scanf("%d",&n);ch=getchar();for(i=1;i<=n;i+) ch=getchar();while(ch!='n')switch(ch)case '#':Pop(s,c);break;

36、 / 仅当栈非空时退栈case '':ClearStack(s);break; / 重置s为空栈default :Push(s,ch); / 有效字符进栈ch=getchar(); / 从终端接收下一个字符StackTraverse(s,visit); / 将从栈底到栈顶的栈内字符输出ClearStack(s); / 重置s为空栈DestroyStack(s);void main()LineEdit(); 8588 表达式求值时间限制:1000MS 内存限制:1000K提交次数:182 通过次数:84 题型: 编程题 语言: 无限制Description利用栈编写表达式求值程序

37、：输入含有“+”、“-”、“*”、“/”四则运算的表达式，其中负数要用（0-正数）表示，并以=结束。要求输出表达式的值（两运算符号的优先关系见教材表3.1）。此题目可选做。#include<stdio.h>#include <math.h>#define True 1#define False 0#define size 1005/字符栈typedef char stack;struct nodestack asize;int top;int Isempty(struct node *s)return (s->top=-1?True:False);int Isfu

38、ll(struct node *s)return (s->top+1=size?True:False);int Push(struct node *s,stack x)if(!Isfull(s) s->top+;s->as->top=x;return True;elsereturn False;int Pop(struct node *s, stack *x) if(!Isempty(s)*x=s->as->top;s->top-;return True;elsereturn False;int Gettop(struct node *s) stack

39、 x;if(!Isempty(s)x=s->as->top;return x;else return False;/整形 栈typedef int sta;struct node1sta asize;int top;int Isempty1(struct node1 *s)return (s->top=-1?True:False);int Isfull1(struct node1 *s)return (s->top+1=size?True:False);int Push1(struct node1 *s,sta x)if(!Isfull1(s) s->top+;

40、s->as->top=x;return True;elsereturn False;int Pop1(struct node1 *s, sta *x) if(!Isempty1(s)*x=s->as->top;s->top-;return True;elsereturn False;sta Gettop1(struct node1 *s) sta x;if(!Isempty1(s)x=s->as->top;return x;else return False;int In(char ch)if(ch>=48&&ch<=57)

41、return True;elsereturn False;char compare(char a,char b) int i,j;char c7='+','-','*','/','(',')','#'char d77='>','>','<','<','<','>','>','>','>',

42、'<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<',

43、'<','<','<','<','=','','>','>','>','>','','>','>','<','<','<','<','<','','=',;if(b='=') return '>'for(i=0;ci!=a;i+)for(j=0;cj!=b;j+)return d