数据结构实验二――顺序栈,链栈,循环队列,链队列.doc

《数据结构实验二――顺序栈,链栈,循环队列,链队列.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告二实验课名称：数据结构与程序设计实验实验名称：顺序栈，链栈，循环队列，链队列班级：学号：姓名：时间：一、问题描述（1）顺序栈l顺序栈的C语言描述l基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶、输出栈、判栈满（2）链栈l链栈的C语言描述l基本运算的算法——置空栈、判栈空、进栈、出栈、读栈顶（3）循环队列l循环队列的C语言描述l基本运算的算法——置空队、判队空、进队、出队、读队头元素、输出循环队列（4）链队列l链队列的C语言描述l基本运算的算法——置空队、判队空、进队、出队、读队头元素二、数据结构设计1.顺序栈typedefstruct{//定义栈的数据结构SEle

2、mType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈当前存储大小}sqstack;2.链栈typedefstructStackNode{SElemTypedata;//数据域structStackNode*next;//结点指针}StackNode,*LinkStack;3.循环队列typedefstruct{QElemType*base;intrear;//队尾intfront;//队首intcount;//队内元素数目intsize;//队列存储大小}sqQueue;为了方便循环队列判定队满队空，故加了一个数据域存储当前

3、元素个数。4.链队列typedefstructQNode{//结点结构体QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;//结点，节点指针typedefstruct{//队列结构体QueuePtrfront;//头指针QueuePtrrear;//尾指针}LinkQueue;二、算法设计1)顺序栈l构造空栈：malloc分配内存；判断是否分配失败，失败则exitS.top=S.base;初始化栈顶初始化存储容量l置空栈：S.top=S.base;栈顶重新指向栈底l判栈空：if(S.top==S.base)；l判

4、栈满：if(S.top-S.base>=S.stacksize)；看栈首尾差距是否>=栈当前存储大小l进栈：判栈满；若满realloc重新分配内存判断是否分配失败，失败则exitS.top=S.base+S.stacksize;赋值新栈顶S.stacksize+=stackincrement;赋值给新的当前存储大小*S.top++=e;进栈元素赋值给top后，top上移l出栈：判栈空，若空返回errore=*--S.top;，下移top指针后赋值给el读取栈顶元素：判栈空，若空返回errore=*(S.top-1);顶元素赋值给el输出栈：for循环输出，须满足条件top>ba

5、se2)链栈l构造空栈：malloc分配内存；判断是否分配失败，失败则exitS->next=NULL;使指针指向空l判栈空：if(!S->next)判断s是否指向空指针l置空栈：暂存S的下一个节点指针到pwhile（p）循环q=p把p赋值给qp=p->next;p指向下一个释放q通过该循环则从第一个结点开始逐个释放到最后一个l进栈：定义结点指针p，通过while(p->next)循环使其指向栈顶结点malloc分配结点内存；判断是否分配失败，失败则exit新节点的数据域赋值e；p指向新结点新节点指向空l出栈：判栈空，若空返回error定义结点指针p和q，通过while(p->

6、next)循环使p指向栈顶，q指向栈顶前一个把p的数据域赋值给e释放pq的指针指向空l读取栈顶元素：判栈空，若空返回error定义结点指针p，通过while(p->next)循环使其指向栈顶结点把p的数据域赋值给e1)循环队列l构造空队列：malloc分配内存；判断是否分配失败，失败则exit初始化队首、队尾、队内元素个数为0初始化队列存储空间l置空队列：将队首、队尾、队内元素个数重新置0l判空队列：if(Q.count==0)l入队：判队满，若满，realloc重新分配内存if判断是否分配成功，不成功则退出更新队列存储的值队尾赋值为e队尾后移队列元素个数加1l出对：判队空，若

7、空则返回error取队首元素队首后移队内元素个数减1l读取队头元素：判队空，若空则返回error队首的值赋值给el输出队列：for循环输出队首，循环次数为队内元素个数每循环一次，队首后移2)链队列l构造空队列：malloc分配队首队尾指针同一内存判空，若空则exit将队首指向空l置空队列：l判空队列：if(!Q.front->next)l入队：分配新结点q的内存判q空，若空则exitq的数据域赋值给eq指向空队尾指向ql出队：判空，若空返回error定义p并赋值为队首结点将其数据赋值给e将队