4、循环队列基本操作
- 格式：docx
- 大小：60.97 KB
- 文档页数：7
第1页共7页 数据结构实验报告 姓名学号专业实验日期 一、【程序清单】 //DataStructure Test //数据结构 #include #include #include char *name = "XXXXXXX"; char *id = "E0000000" ; //循环队列(共10分) #defineMAXQSIZE 30 typedefstruct { char elem[MAXQSIZE]; int front; int rear; }Queue; void InitQueue(Queue *Q) { if(Q) { Q->rear = 0; Q->front = 0; } } //判断队空:如果空，返回TRUE，否则返回FALSE bool IsEmpty(Queue* Q) { //请在下面补充代码 if(Q->front == Q->rear)returntrue; elsereturnfalse; } //判断队满:如果满，返回TRUE，否则返回FALSE bool IsFull(Queue* Q) { //请在下面补充代码 if((Q->rear+1) % MAXQSIZE == Q->front) returntrue; elsereturnfalse; } //入队 第2页共7页
bool EnQueue(Queue *Q, chare) { //把元素e插入队列中 //请在下面补充代码 if((Q->rear+1) % MAXQSIZE == Q->front) returnfalse; Q->elem[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE; returntrue; } //出队 bool DeQueue(Queue *Q, char *e) { //把队首元素放入e中 //请在下面补充代码 if(Q->front==Q->rear) returnfalse; *e = (Q->elem[Q->front]); Q->front=(Q->front+1)%MAXQSIZE; returntrue; } void PrintQueue(Queue *Q) { if(!Q || IsEmpty(Q)) return; for(int k = Q->front;k!=Q->rear;k = (k+1)%MAXQSIZE) { putchar(Q->elem[k]); } } //栈（共10分） //实现顺序栈。参考课本pp46-49 #defineMAX_STACK_ELEMENTS 100 typedefstruct { char *base; char *top; int size; }SqStack; //构造一个空栈，分配内存，设置相关元素的初值。（2分） bool InitStack(SqStack *S) { if (S == 0) returnfalse; //请在下面补充你的代码 S->base=(char*)malloc(MAX_STACK_ELEMENTS * sizeof(char)); if(!S->base) exit(false); S->top =S->base; 第3页共7页
S->size=MAX_STACK_ELEMENTS; returntrue; } //销毁一个栈，释放所有元素的内存，并修改相关数据域的值 bool DestroyStack(SqStackS) { //请在下面补充你的代码 free(S.base); S.base=S.top=NULL; S.size=0; returntrue; } //清除站内元素，不释放内存。 bool ClearStack(SqStack *S) { //请在下面补充你的代码 S->base=S->top; returntrue; } //判断栈是否为空 bool StackEmpty(SqStackS) { //请在下面补充你的代码 if(S.top==S.base) returntrue; elsereturnfalse; } //取栈顶元素的值 bool GetTop(SqStackS, char *data) { //请在下面补充你的代码 if(S.top==S.base) returnfalse; data=S.top-1; returntrue; } //元素入栈（2分） //注意，此处不需要重新分配内存。 //如果栈内元素已经达到最大数目MAX_ELEMENTS， //就返回false，不执行任何其它操作 bool Push(SqStack *S, chardata) { if (S->top - S->base >= S->size) returnfalse; //请在下面补充代码，将新元素data放入栈顶 if(S->top-S->base==MAX_STACK_ELEMENTS) returnfalse; if(S->top-S->base>=S->size) 第4页共7页
{ S->base=(char*)realloc(S->base,MAX_STACK_ELEMENTS*sizeof(char)); if(!S->base) exit(false); S->top=S->base+S->size; S->size=MAX_STACK_ELEMENTS; } *(S->top)++ =data; returntrue; } //元素出栈（2分） bool Pop(SqStack *S, char *data) { if (S == 0 || S->top == S->base) returnfalse; //请在下面补充代码，将栈顶元素值放入data中 if(S->top==S->base) returnfalse; (*data)=*--S->top; returntrue; } //括号匹配检验（4分）（课本pp49） //利用前面的栈，检查括号串s中的括号是否匹配 //s中的括号有(),[],{}三种 bool Check(char* s) { if (s == 0) returnfalse; SqStack T; InitStack(&T); bool result = true; //第一个括号入栈 Push(&T, s[0]); putchar(s[0]); char e, v; for (int j=1;j{ putchar(s[j]); //从第二个括号开始，检查是否不匹配 if (s[j] == '(' || s[j] == '[' || s[j] == '{') { //如果s[j]为左括号，直接入栈 //请在下面补充入栈代码 Push(&T,s[j]); } else { //如果s[j]为右括号，需要与栈顶元素进行匹配， 第5页共7页
//如果匹配成功，继续检查下一个括号。 //否则，输出"Error"，并停止检查下一个括号,同时将result赋值为false //请在下面补充你的代码 if(*(T.top-1)=='('&&s[j]==')' || *(T.top-1)=='['&&s[j]==']' ||*(T.top-1)=='{'&&s[j]=='}') --T.top; else { returnfalse; bool result=false; } } } if (StackEmpty(T)){ result = true; printf("Correct!"); } DestroyStack(T); return result; }
int main(intargc,char* argv[]) { printf("\n%s, %s\n",name,id); int score = 0; int error = 0; printf("\n================================\n栈(共5分)\n"); printf("\n初始化(1分)"); SqStack T; InitStack(&T); if (!T.base || T.top != T.base || T.size != MAX_STACK_ELEMENTS) printf("错误\n"); else { score += 2; printf("正确\n"); } printf("\n入栈(1分)"); char* s = "abcde"; for (int j = 0; jerror = 0; for (int j = 0; j{ putchar(T.base[j]); if (T.base[j] != s[j]) error = 1; } if (error == 1) printf("错误\n"); else { printf("正确\n"); score += 1; } printf("\n出栈(1分)"); char c; error = 0; for (int j = 0; j<6; j++) { if (true == Pop(&T, &c))
