实验三栈和队列及其应用(I)讲解 下载本文

电子信息工程学院2013级《数据结构》实验报告

*/

Status DestoryStack_Sq(SqStack &S) { /*

* 函数原型:Status Push_Sq(SqStack &S, SElemType e) * 函数功能:将元素e入栈

* 入口参数:SqStack类型的结构体变量S的引用&S,SElemType类型元素e * 出口参数:返回函数结果状态 */

Status Push_Sq(SqStack &S, SElemType e) { /*

* 函数原型:Status Pop_Sq(SqStack &S, SElemType &e) * 函数功能:将元素e出栈

* 入口参数:SqStack类型的结构体变量S的引用&S,SElemType类型元素e的引用&e * 出口参数:返回函数结果状态 */

Status Pop_Sq(SqStack &S, SElemType &e) {

if (S.top == S.base) SElemType *newbase;

if (S.top - S.base >= S.stacksize) { }

*S.top++ = e; return OK;

newbase = (SElemType *)realloc(S.base, (STACKINCREMENT + if (!newbase)

return OVERFLOW; S.base = newbase;

S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; SElemType *p;

while (S.base != S.top) { }

return OK;

p = --S.top; free(p);

} //DestoryStack_Sq

S.stacksize)*sizeof(SElemType));

} //Push_Sq

电子信息工程学院2013级《数据结构》实验报告

/*

* 函数原型:Status DecToBin(void) * 函数功能:将十进制数转换为二进制 * 入口参数:void

* 出口参数:返回函数结果状态 */

Status DecToBin(void) {

/***************队 列 结 构 函 数 定 义****************/ /*

* 函数原型:Status InitQueue_Sq(SqQueue &Q) * 函数功能:构造一个空队列Q

* 入口参数:SqQueue类型的结构体变量Q的引用 &Q * 出口参数:返回函数结果状态 */

Status InitQueue_Sq(SqQueue &Q) {

Q.base = (QElemType *)malloc(QUEUE_INIT_SIZE * sizeof(QElemType)); LinkStack S; SElemType e; long data;

printf(\请输入待转换的十进制数:\); scanf_s(\, &data); InitStack_L(S); while (data) { }

printf(\转换后的二进制数:\); while (S->next) { }

printf(\); return OK;

Pop_L(S, e); printf(\, e); Push_L(S, data % 2); data = data / 2;

return ERROR;

e = * --S.top; return OK;

} //Pop_Sq

} //DecToBin

电子信息工程学院2013级《数据结构》实验报告

/*

* 函数原型:Status GetHead_Sq(SqQueue &Q, QElemType &e)

* 函数功能:若队列不空,则返回队头元素e,并返回函数结果状态OK,否则返回ERROR * 入口参数:SqQueue类型的结构体变量Q的引用&Q,QElemType类型元素e的引用&e * 出口参数:返回函数结果状态 */

Status GetHead_Sq(SqQueue &Q, QElemType &e) { /*

* 函数原型:Status EnQueue_Sq(SqQueue &Q, QElemType e) * 函数功能:将元素e插入到队列Q中

* 入口参数:SqQueue类型的结构体变量Q的引用&Q,QElemType类型元素e * 出口参数:返回函数结果状态 */

Status EnQueue_Sq(SqQueue &Q, QElemType e) { /*

* 函数原型:Status DeQueue_Sq(SqQueue &S, QElemType &e) * 函数功能:将元素e从队列中删除并返回

QElemType *newbase;

if (Q.front - Q.rear >= QUEUE_INIT_SIZE) { }

Q.base[Q.rear++] = e; return OK;

newbase = (QElemType *)realloc(Q.base, (STACKINCREMENT + if (!newbase)

return OVERFLOW; Q.base = newbase; if (Q.front == Q.rear)

return ERROR;

e = Q.base[Q.rear - 1]; //队尾指针向量指向下一个元素 return OK; if (!Q.base)

return(OVERFLOW); Q.front = Q.rear = 0; return OK;

} //InitQueue_Sq

} //GetHead_Sq

QUEUE_INIT_SIZE)*sizeof(QElemType));

} //EnQueue_Sq

电子信息工程学院2013级《数据结构》实验报告

* 入口参数:SqQueue类型的结构体变量Q的引用&Q,QElemType类型元素e的引用&e * 出口参数:返回函数结果状态 */ Status DeQueue_Sq(SqQueue &Q, QElemType &e) { if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front++]; return OK; } //DeQueue_Sq 运行结果 实验总结 1、此次实验完成了对顺序存储结构的栈和队列的基本操作及简单应用,加深了对课本知识的理解和掌握。此次实验相对较容易,但却是很基础的,在以后的二叉树、图等高级数据结构都需要用到它,所以栈和队列是非常重要的,有些细节部分是值得高度重视的,也是容易出错的地方。 2、栈顶指针指向的是栈顶元素的下一个位置,在进行出栈操作时,应先将栈顶指针向量自减,指向栈顶元素,才能保证栈中元素正确出栈。当进行连续入队列操作时,要改变的是队尾指针的指向,而不是队头指针;虽然初始状态下队头指针和队尾指针都指向头一个元素,所以做第一个插入时关系不大,但第二次开始就一定要改变尾指针。 3.因为栈是希望当有需要进行入栈操作时就一定能够入栈,一般来说,初始化顺序空栈时,不应限定栈的最大容量,但在顺序结构当中存储空间是由程序员需要时事先指定分配的,一个合理的做法就是:先为栈分配一个基本容量,然后在应用过程中,当栈的空间不够使用时再逐段扩大。