数据结构实验报告.doc

数据结构实验报告 想必学计算机专业的同学都知道数据结构是一门比较重要的课程，那么，下面是给大家整理收集的数据结构实验报告，供大家阅读参考。数据结构实验报告1 一、实验目的及要求 1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。 本实验训练的要点是栈和队列的观点; 二、实验内容 1) 利用栈，实现数制转换。 2) 利用栈，实现任一个表达式中的语法检查(选做)。 3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列); 三、实验流程、操作步骤或核心代码、算法片段 顺序栈： Status InitStack(SqStack ) S.base=(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 ) free(S.base); return OK; Status ClearStack(SqStack ) S.top=S.base; return OK; Status StackEmpty(SqStack S) if(S.base=S.top) return OK; return ERROR; int StackLength(SqStack S) return S.top-S.base; Status GetTop(SqStack S,ElemType ) 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(SqStack ,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 ,ElemType ) if(S.top=S.base) return ERROR; e=*-S.top; 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 ) int flag,TURE=OK,FALSE=ERROR; ElemType e,x; InitStack(S); flag=OK; printf(请输入要进栈或出栈的元素：); while(x= getchar)!=#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; else return ERROR; 链队列： 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) return 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 ) 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.front-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 ) QueuePtr p; if (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-next; 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 DeQueue(SqQueue Q,QElemType ) 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%MAXQSI