《数据结构实验报告-第1篇》由会员分享,可在线阅读,更多相关《数据结构实验报告-第1篇(22页珍藏版)》请在金锄头文库上搜索。
1、 数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程,那么,下面是小编给大家整理收集的数据结构实验报告,供大家阅读参考。数据结构实验报告1一、实验目的及要求1)掌握栈和队列这两种特殊的线性表,熟悉它们的特性,在实际问题背景下灵活运用它们。本实验训练的要点是“栈”和“队列”的观点;二、实验内容1) 利用栈,实现数制转换。2) 利用栈,实现任一个表达式中的语法检查(选做)。3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);三、实验流程、操作步骤或核心代码、算法片段顺序栈:Status InitStack(SqStack &S)S.bas
2、e=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if(!S.base)return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status DestoryStack(SqStack &S)free(S.base);return OK;Status ClearStack(SqStack &S)S.top=S.base;return OK;Status StackEmpty(SqStack S)if(S.base=S.top)return OK;return ERROR
3、;int StackLength(SqStack S)return S.top-S.base;Status GetTop(SqStack S,ElemType &e)if(S.top-S.base=S.stacksize)S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Push
4、(SqStack &S,ElemType e)if(S.top-S.base=S.stacksize)S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType);if(!S.base)return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,ElemType &e)if(S.top=S.base)return ERROR;e=*-S.top
5、;return OK;Status StackTraverse(SqStack S)ElemType *p;p=(ElemType *)malloc(sizeof(ElemType);if(!p) return ERROR;p=S.top;while(p!=S.base)/S.top上面一个.p-;printf(%d ,*p);return OK;Status Compare(SqStack &S)int flag,TURE=OK,FALSE=ERROR;ElemType e,x;InitStack(S);flag=OK;printf(请输入要进栈或出栈的元素:);while(x= getch
6、ar)!=#&flag)switch (x)case (:case :case :if(Push(S,x)=OK)printf(括号匹配成功!nn);break;case ):if(Pop(S,e)=ERROR | e!=()printf(没有满足条件n);flag=FALSE;break;case :if ( Pop(S,e)=ERROR | e!=)flag=FALSE;break;case :if ( Pop(S,e)=ERROR | e!=)flag=FALSE;break;if (flag & x=# & StackEmpty(S)return OK;elsereturn ERROR
7、;链队列:Status InitQueue(LinkQueue &Q)Q.front =Q.rear=(QueuePtr)malloc(sizeof(QNode);if (!Q.front) return ERROR;Q.front-next = NULL;return OK;Status DestoryQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;Status QueueEmpty(LinkQueue &Q)if(Q.front-next=NULL)ret
8、urn OK;return ERROR;Status QueueLength(LinkQueue Q)int i=0;QueuePtr p,q;p=Q.front;while(p-next)i+;p=Q.front;q=p-next;p=q;return i;Status GetHead(LinkQueue Q,ElemType &e)QueuePtr p;p=Q.front-next;if(!p)return ERROR;e=p-data;return e;Status ClearQueue(LinkQueue &Q)QueuePtr p;while(Q.front-next )p=Q.fr
9、ont-next;free(Q.front);Q.front=p;Q.front-next=NULL;Q.rear-next=NULL;return OK;Status EnQueue(LinkQueue &Q,ElemType e)QueuePtr p;p=(QueuePtr)malloc(sizeof (QNode);if(!p)return ERROR;p-data=e;p-next=NULL;Q.rear-next = p;Q.rear=p; /p-next 为空return OK;Status DeQueue(LinkQueue &Q,ElemType &e)QueuePtr p;i
10、f (Q.front = Q.rear)return ERROR;p = Q.front-next;e = p-data;Q.front-next = p-next;if (Q.rear = p)Q.rear = Q.front; /只有一个元素时(不存在指向尾指针)free (p);return OK;Status QueueTraverse(LinkQueue Q)QueuePtr p,q;if( QueueEmpty(Q)=OK)printf(这是一个空队列!n);return ERROR;p=Q.front-next;while(p)q=p;printf(%ddata);q=p-nex
11、t;p=q;return OK;循环队列:Status InitQueue(SqQueue &Q)Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OWERFLOW);Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue &Q,QElemType e)if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQue
12、ue(SqQueue &Q,QElemType &e)if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;int QueueLength(SqQueue Q)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status DestoryQueue(SqQueue &Q)free(Q.base);return OK;Status QueueEmpty(SqQueue Q) /判空if(Q.front =Q.rear)return OK;return ERROR;Status QueueTraverse(SqQueue Q)if(Q.front=Q.rear)printf(这是一个空队列!);while(Q.front%MAXQSIZE!=