数据结构第二实验

1、8583顺序栈的基本操作时间限制:1000MS 内存限制:1000K提交次数:530 通过次数:212题型: 编程题语言: 无限制Description创建一个空的顺序栈，并实现栈的入栈、出栈、返回栈的长度、返回栈顶元素、栈的遍历等基本算法。请将下面的程序补充完整。#include #include #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 / 存储空间初始分配量#define STACKINCREMENT 10 / 存储空间分配增量typedef int SElemType; / 定义栈元素类型typedef int Sta

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

3、qStack &S,SElemType &e) / 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR/ 请补全代码Status GetTop(SqStack S,SElemType &e) / 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR/ 请补全代码int StackLength(SqStack S) / 返回栈S的元素个数/ 请补全代码Status StackTraverse(SqStack S)/ 从栈顶到栈底依次输出栈中的每个元素SElemType *p = (SElemType *)malloc(sizeof(SElemType); p

4、= _ /请填空if(_)printf(The Stack is Empty!); /请填空elseprintf(The Stack is: );p-;while(_) /请填空printf(%d , *p);_ /请填空printf(n);return OK;int main() int a; SqStack S;SElemType x, e; if(_) / 判断顺序表是否创建成功，请填空printf(A Stack Has Created.n);while(1) printf(1:Push n2:Pop n3:Get the Top n4:Return the Length of the

5、 Stackn5:Load the Stackn0:ExitnPlease choose:n);scanf(%d,&a);switch(a)case 1: scanf(%d, &x); if(_) printf(Push Error!n); / 判断Push是否合法，请填空 else printf(The Element %d is Successfully Pushed!n, x); break;case 2: if(_) printf(Pop Error!n); / 判断Pop是否合法，请填空 else printf(The Element %d is Successfully Poped

6、!n, e); break;case 3: if(_)printf(Get Top Error!n); / 判断Get Top是否合法，请填空 else printf(The Top Element is %d!n, e); break;case 4: printf(The Length of the Stack is %d!n,_); /请填空 break;case 5: _ /请填空 break;case 0: return 1;Input测试样例格式说明：根据菜单操作：1、输入1，表示要实现Push操作，紧跟着输入要Push的元素2、输入2，表示要实现Pop操作3、输入3，返回栈顶元素4

7、、输入4，返回栈的元素个数5、输入5，表示从栈顶到栈底输出栈的所有元素6、输入0，表示程序结束Sample Input121416534252220Sample OutputA Stack Has Created.1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 2 is Successfully Pushed!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:

8、Load the Stack0:ExitPlease choose:The Element 4 is Successfully Pushed!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 6 is Successfully Pushed!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:Th

9、e Stack is: 6 4 2 1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Top Element is 6!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Length of the Stack is 3!1:Push 2:Pop 3:Get the Top 4:Return the Le

10、ngth of the Stack5:Load the Stack0:ExitPlease choose:The Element 6 is Successfully Poped!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Stack is: 4 2 1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The

11、 Element 4 is Successfully Poped!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:The Element 2 is Successfully Poped!1:Push 2:Pop 3:Get the Top 4:Return the Length of the Stack5:Load the Stack0:ExitPlease choose:Pop Error!1:Push 2:Pop 3:Get the Top 4:Re

12、turn the Length of the Stack5:Load the Stack0:ExitPlease choose:ProviderYqm8584循环队列的基本操作时间限制:1000MS 内存限制:1000K提交次数:366 通过次数:157题型: 编程题语言: 无限制Description创建一个空的循环队列，并实现入队、出队、返回队列的长度、返回队头元素、队列的遍历等基本算法。请将下面的程序补充完整。#include #include #define OK 1#define ERROR 0typedef int Status; / Status是函数的类型,其值是函数结果状态代

13、码，如OK等typedef int QElemType;#define MAXQSIZE 100 / 最大队列长度(对于循环队列，最大队列长度要减1)typedef struct QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针,若队列不空,指向队列头元素 int rear; / 尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue;Status InitQueue(SqQueue &Q) / 构造一个空队列Q，该队列预定义大小为MAXQSIZE/ 请补全代码Status EnQueue(SqQueue &Q,QElemType e)

14、/ 插入元素e为Q的新的队尾元素/ 请补全代码Status DeQueue(SqQueue &Q, QElemType &e) / 若队列不空, 则删除Q的队头元素, 用e返回其值, 并返回OK; 否则返回ERROR/ 请补全代码Status GetHead(SqQueue Q, QElemType &e)/ 若队列不空，则用e返回队头元素，并返回OK，否则返回ERROR/ 请补全代码int QueueLength(SqQueue Q) / 返回Q的元素个数/ 请补全代码Status QueueTraverse(SqQueue Q) / 若队列不空，则从队头到队尾依次输出各个队列元素，并返回O

15、K；否则返回ERROR.int i;i=Q.front;if(_)printf(The Queue is Empty!); /请填空elseprintf(The Queue is: );while(_) /请填空printf(%d ,_ ); /请填空i = _; /请填空printf(n);return OK;int main()int a; SqQueue S;QElemType x, e; if(_) / 判断顺序表是否创建成功，请填空printf(A Queue Has Created.n);while(1)printf(1:Enter n2:Delete n3:Get the Fro

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

17、Element %d is Successfully Deleted!n, e); break;case 3: if(_)printf(Get Head Error!n); / 判断Get Head是否合法，请填空 else printf(The Head of the Queue is %d!n, e); break;case 4: printf(The Length of the Queue is %d!n,_); /请填空 break;case 5: _ /请填空 break;case 0: return 1;Input测试样例格式说明：根据菜单操作：1、输入1，表示要实现入队操作，紧跟

18、着输入要入队的元素2、输入2，表示要实现出队操作3、输入3，返回队头元素4、输入4，返回队列的元素个数5、输入5，表示从队头到队尾输出队的所有元素6、输入0，表示程序结束Sample Input11121352350Sample OutputA Queue Has Created.1:Enter 2:Delete 3:Get the Front 4:Return the Length of the Queue5:Load the Queue0:ExitPlease choose:The Element 1 is Successfully Entered!1:Enter 2:Delete 3:G

19、et the Front 4:Return the Length of the Queue5:Load the Queue0:ExitPlease choose:The Element 2 is Successfully Entered!1:Enter 2:Delete 3:Get the Front 4:Return the Length of the Queue5:Load the Queue0:ExitPlease choose:The Element 3 is Successfully Entered!1:Enter 2:Delete 3:Get the Front 4:Return

20、the Length of the Queue5:Load the Queue0:ExitPlease choose:The Queue is: 1 2 3 1:Enter 2:Delete 3:Get the Front 4:Return the Length of the Queue5:Load the Queue0:ExitPlease choose:The Element 1 is Successfully Deleted!1:Enter 2:Delete 3:Get the Front 4:Return the Length of the Queue5:Load the Queue0

21、:ExitPlease choose:The Head of the Queue is 2!1:Enter 2:Delete 3:Get the Front 4:Return the Length of the Queue5:Load the Queue0:ExitPlease choose:The Queue is: 2 3 1:Enter 2:Delete 3:Get the Front 4:Return the Length of the Queue5:Load the Queue0:ExitPlease choose:8585栈的应用进制转换时间限制:1000MS 内存限制:1000K

22、提交次数:320 通过次数:203题型: 编程题语言: 无限制Description利用顺序栈的基本操作算法，编写满足下列要求的数制转换程序：对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。Input第一行：输入一个非负的十进制整数Output第一行：与输入等值的八进制数Sample Input15Sample Output178586括号匹配检验时间限制:1000MS 内存限制:1000K提交次数:679 通过次数:182题型: 编程题语言: 无限制Description利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即

23、()或()等为正确的格式，(或()或()均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。本题给出部分check()函数，要求将check()函数补充完整，并完成整个程序。typedef char SElemType;#includemalloc.h #includestdio.h#includemath.h#includestdlib.h / exit()#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等#defi

24、ne STACK_INIT_SIZE 10 / 存储空间初始分配量#define STACKINCREMENT 2 / 存储空间分配增量struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位 ; / 顺序栈Status InitStack(SqStack &S) Status StackEmpty(SqStack S) Status Push(SqStack &S,SElemType e) Status Pop(SqSt

25、ack &S,SElemType &e) void check() / 对于输入的任意一个字符串，检验括号是否配对 SqStack s; SElemType ch80,*p,e; if(InitStack(s) / 初始化栈成功 /printf(请输入表达式n); _; p=ch; while(*p) / 没到串尾 switch(*p) case (: case :_; break; / 左括号入栈，且p+ case ): case :if(!StackEmpty(s) / 栈不空 _; / 弹出栈顶元素 if(*p=)&e!=(|_&_) / 弹出的栈顶元素与*p不配对 printf(isn

26、t matched pairsn); exit(ERROR); else _; break; / 跳出switch语句 else / 栈空 printf(lack of left parenthesisn); exit(ERROR); default: _; / 其它字符不处理，指针向后移 if(StackEmpty(s) / 字符串结束时栈空 printf(matchingn); else printf(lack of right parenthesisn); int main() check(); Input第一行：输入一个包含圆括号或方括号、不超过80个字符的表达式串。Output第一行

27、：若输入表达式括号匹配，输出matching; 若不匹配，输出具体信息:isnt matched pairs, 或lack of left parenthesis或lack of right parenthesisSample Input8*3*(35-23)Sample Outputmatching8587行编辑程序时间限制:1000MS 内存限制:1000K提交次数:578 通过次数:173题型: 编程题语言: 无限制Description利用栈编写简单的行编辑程序：接受用户从终端输入的程序或数据，在输入过程中，允许用户输入出差错，并在发现有误时可以及时更正。例如：当用户发现刚刚键入的一个

28、字符是错的时，可以补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符“”，以表示当前行中的字符均无效。例如：假设从终端接受了这样两行字符： whli#ilr#e (s#*s) outchaputchar(*s=#+); 则实际有效的是下列两行： while (*s) putchar(*s+); 本题目给出部分函数，要求将行编辑函数补充完整，并完成整个程序。typedef char SElemType;#includemalloc.h #includestdio.h#includemath.h#includestdlib.h / exit(

29、)#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等#define STACK_INIT_SIZE 10 / 存储空间初始分配量 #define STACKINCREMENT 2 / 存储空间分配增量struct SqStack SElemType *base; / 在栈构造之前和销毁之后，base的值为NULL SElemType *top; / 栈顶指针 int stacksize; / 当前已分配的存储空间，以元素为单位; /

30、 顺序栈Status InitStack(SqStack &S) / 构造一个空栈S Status StackEmpty(SqStack S) / 若栈S为空栈，则返回TRUE，否则返回FALSE Status ClearStack(SqStack &S) / 把S置为空栈 S.top=S.base; return OK; Status DestroyStack(SqStack &S) / 销毁栈S，S不再存在 free(S.base); S.base=NULL; S.top=NULL; S.stacksize=0; return OK; Status Push(SqStack &S,SEle

31、mType e) / 插入元素e为新的栈顶元素 Status Pop(SqStack &S,SElemType &e) / 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR Status StackTraverse(SqStack S,Status(*visit)(SElemType) / 从栈底到栈顶依次对栈中每个元素调用函数visit()。 / 一旦visit()失败，则操作失败 while(S.topS.base) visit(*S.base+); printf(n); return OK; Status visit(SElemType c) printf(%c,c); return OK; void LineEdit() / 利用字符栈s，从终端接收一行并送至调用过程的数据区。算法3.2 SqStack s; char ch,c; int n,i; InitStack(s); scanf(%d,&n); ch=getchar(); for(i=1;i=n;i+) ch=_; while(ch!=n) switch(_) case #:Pop(s,c); break; / 仅当栈非空时退栈 ca