堆栈和队列的基本操作.doc

实践教学*软件学院2012学年秋季学期上机实验 报告册课程名称：_实验名称：_指导教师：_ 小组成员： * * * 堆栈和队列的基本操作(上机二） 一 实验目的 1.熟悉栈这种特殊现行结构特性； 2.熟悉并掌握栈在顺序存储结构和链表存储结构下的基本运算； 3.熟悉队列这种特殊线性结构的特性； 4.熟悉掌握队列在链表存储结构下的基本运算； 二 实验原理 堆栈顺序存储结构下的基本算法 堆栈链式存储结构下的基本算法 队列顺序存储结构下的基本算法 队列顺序存储结构下的基本算法1、堆栈的定义：堆栈是一种只允许在表的一端进行插入和删除运算的特殊的线性表。允许进行插入和删除运算的一端称为栈顶，另一端称为栈底，当链表中没有元素时，称为空栈。2、堆栈的插入运算称为入栈或者进栈，删除运算称为出栈或者退栈，栈顶的当前位置是动态的，标识栈顶当前位置的指针称为栈顶指针。每次进栈的数据元素都放在原当前栈顶元素之前成为新的栈顶元素，每次退栈的数据元素都是原当前栈顶元素，最后进入堆栈的数据元素总是最先退出堆栈。3、堆栈的存储结构：（1） 顺序存储结构：栈的顺序存储结构称为顺序栈。顺序栈的本质是顺序表的简化。（2） 链式存储结构：栈的链式存储结构称为链栈，通常用单链表示。链栈的插入和删除操作只需处理栈顶的情况。4、队列的定义：队列是允许在表的一端进行插入，而在表的另一端进行删除的特殊线性表。允许进行插入的一端称为队尾，允许进行删除的一端称为队头。队列的插入运算称为进队或者入队，删除运算称为出队或者离队，因此队列又称为先进先出表。5、队列的存储结构队列的存储结构同线性表一样，可以分为顺序结构和链式结构。（1） 顺序存储结构：用顺序存储结构存储队列称为顺序队列。顺序队列会出现假溢出问题，解决办法是用首尾相接的书顺序存储结构，称为循环队列。在队列中，只要涉及队头或者队尾指针的修改都要对其求模。（2） 链式存储结构：用链式存储结构存储的队列称为链队列。链队列的基本操作的实现基本上也是单链表操作的简化。通常附设头结点，并设置队头指针指向头结点，队尾指针指向终端结点。插入数据时只考虑在链队列的尾部进行，删除数据时只考虑在链队列的头部进行。三 实验内容 进行堆栈（包括顺序结构、链式结构）和队列的基本操作：初始化栈、判 断栈空、出栈、取出栈顶元素、入栈、显示栈中所有元素等运算。四 程序代码：链式队列：#include#include#define NULL 0typedef int QElemType;typedef struct QNodeQElemType data;struct QNode *next; QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;void CreateQueue(LinkQueue *Q) int a;QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) printf(创建失败) ;else p-next=NULL; Q-front=p; Q-rear=p; scanf(%d,&a); while(a!=-1) p=(QueuePtr)malloc(sizeof(QNode);p-next=NULL; if(!p) printf(创建失败) ; else p-data=a; Q-rear-next=p; Q-rear=p; scanf(%d,&a); void PrintfQueue(LinkQueue *Q) QueuePtr p;for(p=Q-front-next;p!=NULL;p=p-next) printf( %d,p-data); void EnQueue(LinkQueue *Q,QElemType x) QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) printf(创建失败) ;else p-data=x;p-next=NULL;Q-rear-next=p;Q-rear=p;void DeQueue(LinkQueue *Q,QElemType *f) QueuePtr p;if(Q-front=Q-rear) printf(nError);else p=Q-front-next; *f=p-data; Q-front-next=p-next;if(Q-rear=p) Q-rear=Q-front;free(p);void DeleteQueue(LinkQueue *Q)QueuePtr p; for(;Q-front!=NULL;free(p) p=Q-front; Q-front=Q-front-next;void main() int *f,e; LinkQueue Queue,*Q; e=0;f=&e;Q=&Queue;printf(n*输入队列的元素依次为:*n);printf(n（直到用户输入数字-1为止）n);CreateQueue(Q);printf(n初始队列为:);PrintfQueue(Q);printf(n要入队的元素为:);scanf(%d,&e);EnQueue(Q,e);printf(n入队后的队列为:);PrintfQueue(Q);DeQueue(Q,f);printf(n出队的元素为:);printf(%d,e); printf(n出队后的队列为:);PrintfQueue(Q);printf(n);DeleteQueue(Q);printf(n);链式栈：#include#includetypedef int ElemType;typedef struct linknode ElemType data; /数据域 struct linknode *next; /指针域 LiStack; /链栈类型的定义/初始化栈void InitStack(LiStack *&s) s=(LiStack *)malloc(sizeof(LiStack); s-next=NULL;/销毁栈void ClearStack(LiStack *&s) LiStack *p=s-next; while(p!=NULL) free(s); s=p; p=p-next; free(s); /求战的长度void StackLength(LiStack *s) int i=0; LiStack *p; p=s-next; while(p!=NULL) i+; p=p-next; printf(目前此栈的长度为： %dn,i);/判断栈是否为空栈void StackEmpty(LiStack *s) if(s-next=NULL) printf(目前此栈是空栈n); else printf(目前此栈不是空栈n);/进栈void Push(LiStack *&s,ElemType e) LiStack *p; p=(LiStack *)malloc(sizeof(LiStack); p-data=e; p-next=s-next; /插入*p结点作为第一个数据结点 s-next=p;/出栈void Pop(LiStack *&s,ElemType &e) LiStack *p; if(s-next=NULL) printf(目前此栈是空栈，此次出栈失败了！n); else p=s-next; /p指向第一个数据结点 e=p-data; s-next=p-next; free(p); printf(此次出栈成功，出栈元素是:%dn,e); /取栈顶元素void GetTop(LiStack *s,ElemType &e) LiStack *p; p=s-next; if(p=NULL) printf(目前此栈是空栈，此次取栈顶元素失败了n); else e=p-data; printf(此次取栈顶的元素是：%dn,e); /显示栈中元素void DispStack(LiStack *s) LiStack *p; p=s-next; if(p=NULL) printf(此栈目前是空栈n); else printf(下面输出链栈里的各个元素:n); while(p!=NULL) printf(%d ,p-data); p=p-next; printf(n); void main() LiStack *s; int e; InitStack(s); printf(*欢迎使用 链栈操作*n); printf(*请输入第一个进栈元素:*n); scanf(%d,&e); while(e!=0) Push(s,e); DispStack(s); StackLength(s); printf(*请输入一个进栈元素:*n); printf(（若不需继续输入 请按数字0）n); scanf(%d,&e); StackEmpty(s); GetTop(s,e); int i; printf(如果你想出栈元素,请按数字1n); scanf(%d,&i); while(i=1) Pop(s,e); DispStack(s); StackLength(s); printf(如果你想继续出栈元素,请按1n);printf(*按下其他键退出本栈操作*n); scanf(%d,&i); printf(链栈的基本运算,到此操作完毕了哦！n);顺序队列：#include #define QueueSize 100typedef char ElemType;typedef struct ElemType dataQueueSize;/*保存队中元素*/int front,rear;/*队头和队尾指针*/ SqQueue;void InitQueue(SqQueue &qu) qu.rear=qu.front=-1; /*指针初始化*/ int EnQueue(SqQueue &qu,ElemType x) if (qu.rear+1)%QueueSize=qu.front) /*队满*/return 0;qu.rear=(qu.rear+1)%QueueSize; /*队尾指针进1*/qu.dataqu.rear=x;return 1;int DeQueue(SqQueue &qu,ElemType &x)/*出队运算*/ if (qu.rear=qu.front)return 0; qu.front=(qu.front+1)%QueueSize; /*队头指针进1*/ x=qu.dataqu.front; return 1;int GetHead(SqQueue qu,ElemType &x)/*取队头元素运算*/if (qu.rear=qu.front)/*队空*/return 0;x=qu.data(qu.front+1)%QueueSize;return 1;int QueueEmpty(SqQueue qu)/*判断队空运算*/if (qu.rear=qu.front)/*队空*/return 1;elsereturn 0;void main()SqQueue qu;ElemType e;InitQueue(qu);printf(队%sn,(QueueEmpty(qu)=1?空:不空);printf(a进队n);EnQueue(qu,a);printf(b进队n);EnQueue(qu,b);printf(c进队n);EnQueue(qu,c);printf(d进队n);EnQueue(qu,d);printf(队%sn,(QueueEmpty(qu)=1?空:不空);GetHead(qu,e);printf(队头元素:%cn,e);printf(出队次序:);while (!QueueEmpty(qu) DeQueue(qu,e);printf(%c ,e);printf(n);顺序栈：#include typedef char ElemType; #define StackSize 100 /*顺序栈的初始分配空间*/typedef struct ElemType dataStackSize; /*保存栈中元素*/int top;/*栈顶指针*/ SqStack;void InitStack(SqStack &st)st.top=-1;int Push(SqStack &st,ElemType x)/*进栈运算*/if (st.top=StackSize-1)/*栈满*/return 0;else/*栈不满*/st.top+;st.datast.top=x;return 1; int Pop(SqStack &st,ElemType &x) /*出栈运算*/if (st.top=-1)/*栈空*/return 0;else/*栈不空*/x=st.datast.top;st.top-;return 1;int GetTop(SqStack st,ElemType &x)/*取栈顶元素*/if (st.top=-1)/