break;
case 6:
xh1=0;
break;
} } system(“pause”);}
心得体会:
完成时间:2010-10-30
实验总结报告—栈和队列
学号:
姓名: 时间:
一、目的 1.做实验的目的
加深对线性结构栈和队列的理解,学会定义栈和队列的存储结构,加强对栈和队列操作机制的理解,掌握栈和队列的基本操作,了解栈和队列的一些应用。2.撰写实验报告的目的
对本次实验情况进行总结,加强对实验内容的理解,对实验过程有一个系统的认识,从中获得本次试验的经验,并对实验结果进行适当的分析,加深对栈和队列的理解和认识。
二、内容
1.说明实验次数及实验内容 本次实验用一次实验课时完成 实验内容:
(1)、编写函数CreatStack_sq(), DestoryStack_sq(), Push_sq(), Pop_sq(),StackEmpty_sq()和
StackTraverse_sq(),分别完成创建空栈,销毁栈,入栈,出栈,判断栈是否为空,遍历栈底到栈顶依
次打印栈内元素等功能(不要修改原栈),完成后进行测试。测试要求:在main 中,建立栈;判断栈是否为空;将0~9 入栈;将栈顶两个元素出栈, 两元素求和后再入栈;从栈底到栈顶依次打印元素,再从栈顶到栈底打印元素;销毁栈。
void CreatStack_sq(SqStack &S, int msize = STACK_INIT_SIZE){...} void DestoryStack_sq(SqStack &S){...}void Push_sq(SqStack &S, ElementType e){...} bool Pop_sq(SqStack &S, ElementType &e){...} bool StackEmpty_sq(SqStack S){...} bool StackTraverse_sq(SqStack S){...}(2)、编写函数, CreateQueue_L(), DestoryQueue_L(), EnQueue_L(),DeQueue_L(),分别完
成创建队列,销毁队列,入队列,出队列等操作,完成后进行测试。测试要求:在主程序中,建立队列,将0~9 依次入队列,按入队列顺序出队列并打印, 销毁队列。
void CreateQueue_L(LinkQueue &Q){ } void DestoryQueue_L(LinkQueue &Q){ } void EnQueue_L(LinkQueue &Q,int e){ } bool DeQueue_L(LinkQueue &Q, int &e){ }(3)、回文是指正读反读均相同的字符序列,如”abba”和”abdba”均是回文, 但”good”不是回文。根据第四章栈和队列所学内容,试写一个算法判
定给定的字符向量是否为回文。测试数据: 2.1 char* ch = “abccba”;2.2 char* ch = “abccbd”;(4)、(附加题)编写函数void Knapsack(int w[],int T,int n),完成背包求解问题。测试数据: w[6] = {2,8,6,5,1,4};2.做实验完成情况
实验内容在实验课时时间内完成(提前编写了大概1/3部分的代码),选做内容也完成。
本次实验内容较多,为使代码看着简洁有条理,采用了建工程的方式。栈部分:
自定义了头文件 L_stack.h: /*自定义头文件*/ #include
#define STACK_INIT_SIZE 100;#define STACKINCREMENT 100;
/*自定义头文件(栈相关)*/
#include typedef char ElemType;//typedef int ElemType;
/*栈的结构体定义*/ typedef struct{
ElemType *elem;int top;int stacksize;}SqStack;
void CreateStack_sq(SqStack &S,int msize);//创建栈,msize为栈的大小 void DestroyStack_sq(SqStack &S);//销毁栈
void Push(SqStack &S, ElemType e);// 进栈操作,e为入栈元素 int Pop_sq(SqStack &S, ElemType &e);//出站操作,成功返回0,不成功返回-1 void Increment(SqStack &S, int inc_size);//增加栈空间 int StackEmpty_sq(SqStack S);//判断栈空,栈空返回0,栈非空返回-1; void StackTraverse_sq1(SqStack S);//遍历栈底到栈顶,若栈非空则依次打印栈中元素
void StackTraverse_sq2(SqStack S);//遍历栈顶到栈底,若栈非空则依次打印栈中元素
void Test_sq();//栈的检测程序
void MatchBracket_sq(char exp[]);// 括号匹配 void MatchWord_sq(char exp[]);//判断回文 void knapsack(int w[], int T, int n);//背包问题
在头文件中对所有要用到的自定义函数进行了声明,各函数的功能可见代码注释部分。
栈的创建:
#include“L_stack.h”
void CreateStack_sq(SqStack &S,int msize){
S.elem = new ElemType[msize];S.stacksize = msize;S.top =-1;}//end CreateStack_sq 此操作完成栈的创建,创建完成得到一个空栈。
栈的销毁:
#include“L_stack.h”
void DestroyStack_sq(SqStack &S){
delete S.elem;S.top =-1;S.stacksize = 0;}//end DestroyStack_sq 此操作将栈销毁。
入栈:
#include“L_stack.h” #include
void Push(SqStack &S, ElemType e){
if(S.top == S.stacksize0;break;case '}':
if(!Pop_sq(S, e)|| e!= '{')matchstat = 0;break;}//end switch ch = *exp++;}//end while
if(matchstat&&StackEmpty_sq(S))printf(“括号匹配n”);else printf(“括号不匹配n”);}//end MatchBracket_sq 该操作完成括号的匹配;
回文判断:
#include“L_stack.h”
void MatchWord_sq(char exp[]){
int i, len=0,flag=1;SqStack S;CreateStack_sq(S, 100);char ch,e;for(i = 0;exp[i]!=' ';i++)len++;//printf(“%dn”, len);if(len % 2!= 0){ printf(“非回文序列n”);return;}//序列长度为奇数,不可能为回文序列
else{
for(i = 0;i <(len / 2);i++){
ch = exp[i];
Push(S,ch);
}//前一半元素入栈
while(i < len&&flag){
ch = exp[i];
if(!Pop_sq(S, e)|| e!= ch)
flag = 0;
i++;}//end while }//end else if(flag == 1)printf(“回文序列n”);else printf(“非回文序列n”);} 该操作完成回文的判断;
主函数:
#include #include
//元素与栈顶元素不匹配 #include“L_stack.h”
//#define STACK_INIT_SIZE 100;
int main(){
char exp1[20] = { '(', '8', '+', '9', ')', '/', '{', '[', '(', 'a', '*', 'b', ')', '/', '7', ']', '+', '9', '}', '#' }, exp2[20]
=
{
'}','8','+', '9',')','/','{','[','(','a','*','b',')','/','7',']','+','9','}','#'},} exp3[] = “abccba”, exp4[] = “abccbd”;int w[6] = { 2, 8, 6, 5, 1, 4 };Test_sq();MatchBracket_sq(exp1);MatchBracket_sq(exp2);MatchWord_sq(exp3);MatchWord_sq(exp4);//knapsack(w, 10, 6);
system(“pause”);return 0;主函数中调用test()完成栈的检验,以及实现括号匹配和回文判断。实验结果:
为方便后面实现括号匹配和回文判断,我直接将0~9定义成的char型,头文件中ElemType定义成char。
第一步将0~9入栈;第二步从栈底到栈顶遍历栈中元素并打印,可以看出正确创建了栈并成功将0~9入栈;第三、四步将栈顶元素出栈,并分别赋给e[0]、e[1],打印操作之后的结果可以看出成功操作;第五步将e[0]、e[1]相加并入栈,从遍历栈结果来看成功操作(由于0~9存的是char型,所以是ASCII码相加得到q);第六步从栈顶到栈底遍历栈中元素,操作正确;第七步销毁栈,从遍历栈的结果来看成功销毁栈。到此栈的功能检验结束。然后进行括号匹配和回文判断,结果正确。
接下来利用栈进行背包问题:
由于背包问题是对int型数据进行处理,为了偷点懒直接在上面的程序中进行修改
首先将头文件中ElemType定义为int;背包问题中用到的函数为 CreateStack_sq()、Pop_sq()、Push()、StackTraverse_sq1()、StackEmpty_sq()、DestroyStack_sq(),对这些函数涉及到char型的改成int型;然后将主函数中test()、MatchBracket_sq()、MatchWord_sq()注释掉;最后调用背包问题的函数: #include“L_stack.h”
void knapsack(int w[], int T, int n){
SqStack S;int k = 0,r;CreateStack_sq(S, 100);do{
while(T > 0 && k < n){
if(T-w[k] >= 0){ Push(S, k);T-= w[k];}//end if k++;}//end while if(T == 0){
}
} printf(“The Result is:n”);StackTraverse_sq1(S);if(!StackEmpty_sq(S)){
r=Pop_sq(S, k);T += w[k];k++;}//end if } while(!StackEmpty_sq(S)|| k!= n);DestroyStack_sq(S);主函数:
#include #include #include“L_stack.h”
//#define STACK_INIT_SIZE 100;
int main(){
char exp1[20] = { '(', '8', '+', '9', ')', '/', '{', '[', '(', 'a', '*', 'b', ')', '/', '7', ']', '+', '9', '}', '#' },exp2[20] = { '}', '8','+', '9',')','/','{','[','(','a','*','b',')','/','7',']','+','9','}','#'},} 输出结果: exp3[] = “abccba”, exp4[] = “abccbd”;int w[6] = { 2, 8, 6, 5, 1, 4 };//Test_sq();//MatchBracket_sq(exp1);//MatchBracket_sq(exp2);//MatchWord_sq(exp3);//MatchWord_sq(exp4);knapsack(w, 10, 6);
system(“pause”);return 0;
可见操作正确。队列部分: 自定义了头文件 Queue.h: /*自定义头文件*/
#include /*队列的结构体定义*/ typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;
typedef LinkList Queueptr;
typedef struct{ Queueptr front;Queueptr rear;}LinkQueue;
/*自定义函数*/ void CreateQueue_L(LinkQueue &Q);//创建队列 void DestroyQueue_L(LinkQueue &Q);//销毁队列 void EnQueue_L(LinkQueue &Q, int e);//入队列操作
int DeQueue_L(LinkQueue &Q, int &e);//出队列操作,并将队首元素赋给e,返回1,队空返回0 void QueueTraverse_L(LinkQueue Q);//遍历队列元素并打印 void test();//检查队列是否正确
头文件中声明了需要用到的自定义函数,各个函数的功能见注释
创建队列:
void CreateQueue_L(LinkQueue &Q){
Q.front = Q.rear = new LNode;Q.front->next = NULL;}//end CreateQueue_L 销毁队列:
#include“Queue.h”
void DestroyQueue_L(LinkQueue &Q){
while(Q.front){
Q.rear = Q.front->next;delete Q.front;Q.front = Q.rear;}//end while }//end DestroyQueue_L 进队列: #include“Queue.h”
void EnQueue_L(LinkQueue &Q, int e){
LinkList p;p = new LNode;p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;}//end EnQueue_L 出队列:
#include“Queue.h”
int DeQueue_L(LinkQueue &Q, int &e){
LinkList p;p = new LNode;if(Q.front == Q.rear)return 0;p = Q.front->next;Q.front->next = p->next;
e = p->data;if(Q.rear == p)Q.rear = Q.front;delete p;return 1;}//end DeQueue_L 主函数:
#include #include #include“Queue.h”
int main(){
} 主函数调用test()函数检验队列的正确性 test()函数: #include“Queue.h” system(“pause”);return 0;test();void test(){
} 输出结果: LinkQueue Q;int i,a[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },b[10],r[10];CreateQueue_L(Q);for(i = 0;i < 10;i++)EnQueue_L(Q, a[i]);QueueTraverse_L(Q);for(i = 0;i < 10;i++){
} r[i] = DeQueue_L(Q, b[i]);QueueTraverse_L(Q);
从输出结果来看符合要求,队列正确。
三、总结
数理学院实验指导书
实验三 栈与队列的实现,栈的应用
【实验目的】
1、掌握栈和队列的特点,即先进后出与先进先出的原则。
2、掌握栈和队列的顺序存储结构和链式存储结构及其基本操作,以便在实际问题中灵活运用。
3、掌握栈和队列的基本操作实现方法。【实验内容】
1、栈的实现:
用C语言实现栈,包括类型定义和各种基本运算的实现,并在此基础上设计一个主程序,测试栈的一些基本运算:
(1).初始化(2).入栈(3).出栈
(4).取栈顶元素(5).遍历栈(6).置空栈 请根据下面给出的程序(改进的顺序栈),完成这次实验,并与链栈的实现方法相比较:
/*Common.h*/ #define TRUE 1 //逻辑,是 #define FALSE 0 //逻辑,否 #define OK 1 //状态,成功
#define FAILURE 0 //状态,未成功 #define ERROR-1 //状态,失败 #define OVERFLOW 1 //溢出
typedef int BOOL;typedef int Status;
/*seqstack.h*/ #include #include #include “common.h” #define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10// 线性表存储空间的分配增量
typedef int ElemType;
//栈
typedef struct { ElemType *elem;// 存储空间基址
int top;// 栈顶指示
int currentsize;// 当前分配的长度 }SeqStack;
/*构造一个空的栈*/ SeqStack *CreateStack();/*释放栈分配的空间*/ void DestroyStack(SeqStack *S);/*判空*/ int IsEmpty(SeqStack *S);/*入栈*/ Status Push(SeqStack *S, ElemType e);/*出栈*/ Status Pop(SeqStack *S, ElemType *e);/*取栈顶元素*/ Status GetTop(SeqStack *S, ElemType *e);/*遍历*/ void Traverse(SeqStack *S, void(*visit)(ElemType, int));
/*seqstack.c*/ #include #include #include “common.h” #include “seqstack.h”
/*构造一个空的栈*/ SeqStack *CreateStack(){ SeqStack *S=(SeqStack *)malloc(sizeof(SeqStack));
if(S==NULL){ exit(OVERFLOW);} S->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(S->elem==NULL){ exit(OVERFLOW);} S->top =-1;S->currentsize = LIST_INIT_SIZE;return S;}
/*释放栈分配的空间*/ void DestroyStack(SeqStack *S){ if(S!=NULL){
if(S->elem!=NULL)
{
free(S->elem);
}
S->elem=NULL;} }
/*判空*/ int IsEmpty(SeqStack *S){ return S->top==-1;}
/*入栈*/ Status Push(SeqStack *S, ElemType e){ if(S->top >= S->currentsize)// 当前存储空间已满,增加分配
{
ElemType *newbase=(ElemType *)realloc(S->elem,(S->currentsize + LISTINCREMENT)*sizeof(ElemType));
if(newbase==NULL)// 存储分配失败
{
exit(OVERFLOW);
}
S->elem = newbase;// 新基址
S->currentsize += LISTINCREMENT;//增加存储容量
} ++(S->top);S->elem[S->top]=e;return OK;}
/*出栈*/ Status Pop(SeqStack *S, ElemType *e){ if(S->top==-1)//空栈
{
return FAILURE;}(*e)=S->elem[S->top];--(S->top);// 表长减1 return OK;}
/*取栈顶元素*/ Status GetTop(SeqStack *S, ElemType *e){ if(S->top==-1)//空栈
{
return FAILURE;}(*e)=S->elem[S->top];return OK;}
/*遍历*/ void Traverse(SeqStack *S, void(*visit)(ElemType, int)){ int i;
for(i=0;i<=S->top;i++){
(*visit)(S->elem[i], i+1);} } 2.利用栈实现数制转换:
在上述栈实现的基础上,设计一个算法实现输入一个10进制整数,输出相应的2进制表示,并利用计算器工具设计若干测试数据后编写测试代码进行测试.#include //itoa()是这个文件里的库函数 #include using namespace std;void Chg10To2(int n,char result[]);int Chg2To10(char a[]);int Nmi(int m,int n);//计算m的n次方 int Check(char ch);int main(){ char str[33]={0};char data1[50]={0};char data2[50]={0};char ch;cout<<“华锐学院C++作业”<>data1;cout<<“您的输入是:”<>data2;cout<<“您的输入是:”<>ch;switch(ch){ case '+': value=num1+num2;break;case '-': value=num1-num2;break;case '*': value=num1*num2;break;case '/': if(num2==0){
cout<<“除数不能为零”<0;i--){ // cout<sum*=m;return sum;} int Check(char ch){ switch(ch){ case '0':
return 0;
break;case '1':
return 1;
break;} return-1;}
3.队列的实现:
用C语言实现队列,包括类型定义和各种基本运算的实现,并在此基础上设计一个主程序,测试队列的一些基本运算:
(1).初始化(2).入队列(3).出队列
(4).取对头元素(5).遍历队列
请根据下面给出的程序(改进的链队列),完成这次实验,并与顺序队列的实现方法相比较,结合上述改进顺序栈的方法改进书上的顺序队列使之能根据队列使用情况自动扩展或缩短,从而解决顺序队列“上溢”的问题:
/*Common.h*/ 见栈的实现
/*queue.h*/ #include #include #include “common.h” typedef int ElemType;
//链队列
/*定义链队列中的结点类型*/ typedef struct node { ElemType data;struct node *next;}LinkNode;
typedef struct { LinkNode *front;LinkNode *rear;}LinkQueue;
/*构造一个空的链队列*/ LinkQueue *CreateQueue();/*销毁链队列*/ void DestroyQueue(LinkQueue *Q);/*判空*/ int IsEmpty(LinkQueue *Q);/*入队列*/ Status AddQueue(LinkQueue *Q, ElemType e);/*出队列*/ Status OutQueue(LinkQueue *Q, ElemType *e);/*取队列头元素*/ Status GetHead(LinkQueue *Q, ElemType *e);/*遍历*/ void Traverse(LinkQueue *Q, void(*visit)(ElemType, int));
/*queue.c*/ #include #include #include “common.h” #include “Queue.h”
/*构造一个空的队列*/ LinkQueue *CreateQueue(){ LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue));if(Q==NULL){
exit(OVERFLOW);} Q->front=(LinkNode *)malloc(sizeof(LinkNode));
if(Q->front==NULL){ exit(OVERFLOW);} Q->front->next=NULL;/*填头结点的next域为NULL*/ Q->rear=Q->front;
/*让尾指针也指向头结点*/ return Q;}
/*销毁队列*/ void DestroyQueue(LinkQueue *Q){ LinkNode *p;
if(Q!=NULL){
while(Q->front!=Q->rear)
{
p=Q->front->next;
free(Q->front);
Q->front=p;
}
free(Q->front);
Q->front=NULL;
Q->rear=NULL;} }
/*判空*/ int IsEmpty(LinkQueue *Q){ return Q->front==Q->rear;}
/*入队列*/ Status AddQueue(LinkQueue *Q, ElemType e){ LinkNode *p;p=(LinkNode *)malloc(sizeof(LinkNode));
if(p==NULL){ exit(OVERFLOW);} p->data=e;
/*填入元素值*/ p->next=NULL;
/*指针域填NULL值*/ Q->rear->next=p;
/*新结点插入队尾*/ Q->rear=p;
/*修改队尾指针*/ return OK;}
/*出队列*/ Status OutQueue(LinkQueue *Q, ElemType *e){ LinkNode *p;if(Q->front==Q->rear)//空队列
{ return FAILURE;
} p=Q->front;
/*p指向头结点*/ Q->front=Q->front->next;free(p);(*e)= Q->front->data;return OK;}
/*取队列顶元素*/ Status GetHead(LinkQueue *Q, ElemType *e){ if(Q->front==Q->rear)//空队列
{
return FAILURE;
}(*e)= Q->front->next->data;return OK;}
/*遍历*/ void Traverse(LinkQueue *Q, void(*visit)(ElemType, int)){ LinkNode *p;int i;p=Q->front;i=1;while(p!=Q->rear){
(*visit)(p->next->data, i);
p=p->next;
i++;} } 【实验安排】
课时安排:2学时 【实验提示】 1.实验流程
根据所给的代码编辑源程序,注意编写的规范和体会实现的方法;设计一个主程序实现要求的测试;设计一个算法利用栈实现数制转换..2.注意事项
记录输入和编译的错误提示,书写心得体会;记录测试数据和程序的输出;注意总结.作者:王鹤 QQ:583241212
VC++6.0中调式通过的代码: #include “stdafx.h” #include #include using namespace std;typedef char* ELEM;class Link { public: ELEM element;Link* next;Link(const ELEM& elemval,Link* nextp=NULL){element=elemval;next=nextp;} Link(Link* nextp=NULL){next=nextp;} ~Link(){} };class Queue { private: Link* front;Link* rear;public: Queue(const int sz){front=rear=NULL;} ~Queue(){clear();} void clear();void enqueue(const ELEM&);ELEM dequeue();ELEM firstValue()const {assert(!isEmpty());return front->element;} bool isEmpty()const {return front==NULL;} };void Queue::clear(){ while(front!=NULL){rear=front;front=front->next;delete rear;} } void Queue::enqueue(const ELEM& item){ if(rear!=NULL){ rear->next=new Link(item,NULL);rear=rear->next;} else front=rear=new Link(item,NULL);} ELEM Queue::dequeue(){ assert(!isEmpty());ELEM temp=front->element;Link* ltemp=front;front=front->next;delete ltemp;if(front==NULL)rear=NULL;return temp;} int main(){ Queue qu(5);ELEM ee[5];ee[0]=“QQLove1”;ee[1]=“QQLove2”;ee[2]=“QQLove3”;ee[3]=“QQLove4”;ee[4]=“QQLove5”;for(int i=0;i<5;i++){ cout<<“入队”<栈和队列上机实习
1、实验目的:
(1)熟练掌握栈的逻辑结构和操作规则,能在相应的实际问题中正确选用该结构。(2)熟练掌握栈的2种存储结构实现方法(顺序栈和链栈),两种存储结构和基本运算的实
现算法,注意栈空盒满的判断条件及它们的描述方法。
(3)熟练掌握队列的逻辑结构和操作规范,能在相应的实际问题中正确选用该结构。(4)掌握循环队列与链队列两种存储结构的实现,熟练掌握各种队列基本运算的实现。
2、实验要求:
(1)顺序栈的插入、删除,栈顶数据元素的读取。(2)链栈的插入、删除,栈顶数据元素的读取。(3)循环队列的插入、删除。(4)链队列的插入、删除。
3、实验内容: ① 栈
(1)抽象数据类型定义
typedef struct
{
ElemType data[MaxSize];
//栈的空间大小为MaxSize
int top;
//设置栈顶指针
}SqStack;
//栈的结构定义
在本次实验中,首先建立一个空栈,进入主程序后首先初始化栈为其分配空间,然后进入菜单选择界面,通过不同的数字输入,实现入栈,出栈,读取栈顶元素,显示栈的所有元素,栈的长度,释放栈等操作。
(2)存储结构定义及算法思想
在栈结构体的定义中,typedef int Typeelem 为整型,存储结构(入栈)如下:
cin>>a;
s->top++;
//在入栈是首先将栈顶指针向上加1
s->data[s->top]=a;
//与数组赋值一样,直接赋值
//其他存储与此类似,都是直接赋值与数组的某一位
退栈函数模块:
void Pop(SqStack * &s){
//对指针的引用
if(s->top ==-1){
cout<<“栈是空栈,不能退栈”<//首先判断是否为空栈,若为空,则退出
return;} cout<<“退栈的元素为:”<data[s->top]<//显示退栈元素
s->top--;
//栈顶元素减1,指向实际栈的最上面 }
显示栈所有元素函数模块:
void DispStack(SqStack *s){
//从栈顶到栈底顺序显示所有元素
int i;cout<<“栈的元素分别为:”<top;i>=0;i--){ cout<data[i]<<“ ”;
//同过循环实现实现从栈顶元素到栈底元素的遍历以输出
} cout<栈结构的入栈和退栈是两个相反的过程,先进后出,入栈是先让栈顶指针加1,指向未被赋值位置,然后进行赋值,退栈是先取出退栈元素,然后栈顶元素减1,指向推展后的实际栈顶。诸如读取栈顶元素,显示栈的元素,读取栈的长度,都是用过对栈顶指针实现相关操作。
(3)实验结果与分析
② 循环队列
(1)抽象数据类型定义
typedef struct {
ElemType elem[Maxqsize];
//循环队列的长度为MaxSize
int front,rear;
//设置队列的头指针和尾指针
}SqQueue;
//循环队列的结构体定义
在本次实验中,首先建立一个空队列,进入主程序后首先初始化队列为其分配空间,然后进入菜单选择界面,通过不同的数字输入,实现入队,出队,显示队列的所有元素,队列的长度,释放队列等操作。
(2)存储结构定义及算法思想
在队列结构体的定义中,typedef int Typeelem 为整型,存储(入队)结构如下:
q->rear=(q->rear+1)%Maxqsize;
//尾指针加1
q->elem[q->rear]=a;
//将入队元素装到新的空尾部
在此队列的存储结构的实现:先让队尾指针进1,再将新的元素加入到队尾指针所指示的位置,因此,队尾指针指示实际的队尾位置,队头指针指示实际队头的前一位置,要想退出队头元素,必须先让队头指针进1,才能取出队头元素。
退队函数模块如下:
void deQueue(SqQueue *&q){
//对指针的引用
if(QueueEmpty(q))
{
//调用带返回值的判断空队函数
cout<<“队列为空”<//判断队列是否为空
}
q->front=(q->front+1)%Maxqsize;
//队头指针进1
cout<<“退队的元素为:”<elem[q->front]<//取出队头元素 }
遍历队表函数:
void displayqueue(SqQueue *q){
int m;m=q->front+1;
//队头元素进1,指向实际队头
if(QueueEmpty(q))
{
cout<<“队列为空”<//判断是够为空队
}
cout<<“所有队列元素为:”<while(q->rear+1>m){
cout<elem[m]<<“ ”;
//通过循环遍历所有元素
m++;
}
cout<循环队列的入队和退队分别是在队尾与队头跟别进行操作的,通过队头队尾指针的操作便可实现对队列的相关操作。
(3)实验结果与分析
③ 心得体会
本次上机是做栈与队列的操作,这次实验,我有意的用到了对指针的引用与指针实现子函数功能的调用,刚开始编译的时候也有错误,但是在慢慢的摸索中,也逐渐掌握了它们的用法,这次实验也让我熟练了对队列与栈存储结构的应用。
附录:
顺序表源代码: 栈:
#include using namespace std;#define MaxSize 5 typedef int ElemType;int e;typedef struct { ElemType data[MaxSize];int top;}SqStack;
void InitStack(SqStack * &s)
//建立一个空栈,即将栈顶指针指向-1即可 的引用 { s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}
void ClearStack(SqStack * &s)
//释放栈s占用的存储空间 { free(s);}
void StackLength(SqStack *s)
{ cout<<“栈的长度为:” <<(s->top +1)<int StackEmpty(SqStack *s){ return(s->top==-1);}
void Push(SqStack *&s){ if(s->top==MaxSize-1)
{
cout<<“栈满”<//
s=(SqStack *)realloc(s,sizeof(SqStack));} int a;
指针
cout<<“请输入入栈元素”<>a;s->top++;s->data[s->top]=a;}
void Pop(SqStack * &s){ if(s->top ==-1){
cout<<“栈是空栈,不能退栈”<return;} cout<<“退栈的元素为:”<data[s->top]<top--;}
void GetTop(SqStack * &s,ElemType &e){ if(s->top==-1){cout<<“空栈”<data[s->top];}
void DispStack(SqStack *s)
//从栈顶到栈底顺序显示所有元素 { int i;cout<<“栈的元素分别为:”<top;i>=0;i--){ cout<data[i]<<“ ”;} cout<cout<<“请选择功能”<cout<<“
入栈
1”<cout<<“
出栈
2”<cout<<“
读取栈顶元素
3”<cout<<“
显示栈所有元素
4”<cout<<“
栈的长度
5”<cout<<“
释放栈
6”<cin>>k;
switch(k)
{
case 1: Push(s);break;
case 2: Pop(s);break;
case 3: GetTop(s,e);cout<<“栈顶元素为: ”<case 4: DispStack(s);break;
case 5: StackLength(s);break;
case 6: ClearStack(s);break;
default :break;
} } }
队列:
#include using namespace std;#define Maxqsize 8 typedef int TypeElem;typedef struct {
TypeElem elem[Maxqsize];
int front,rear;}SqQueue;void InitQueue(SqQueue *&q){
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=0;} void ClearQueue(SqQueue *&q){
free(q);exit(0);} void QueueLength(SqQueue *q){
cout<<“队列长度为:”<<(q->rear-q->front+Maxqsize)%Maxqsize<return(q->front==q->rear);
} void enQueue(SqQueue *&q){ int a;
if((q->rear+1)%Maxqsize==q->front)
{
cout<<“队列已满,无法插入”<}
cout<<“请输入插入元素”<cin>>a;
q->rear=(q->rear+1)%Maxqsize;
q->elem[q->rear]=a;} void deQueue(SqQueue *&q){
if(QueueEmpty(q))
{
cout<<“队列为空”<}
q->front=(q->front+1)%Maxqsize;
cout<<“退队的元素为:”<elem[q->front]<}
void displayqueue(SqQueue *q){
int m;m=q->front+1;
if(QueueEmpty(q))
{
cout<<“队列为空”<}
cout<<“所有队列元素为:”<while(q->rear+1>m)
{
cout<elem[m]<<“ ”;
m++;
}
cout<int k=0;
SqQueue *q;
InitQueue(q);
if(QueueEmpty(q))cout<<“队列为空”<while(1){
cout<<“请选择功能”<cout<<“
入队
cout<<”
出队
cout<<“
队列长度
cout<<”
显示队列元素
cout<<“
释放栈
cin>>k;
switch(k)
{
case 1: enQueue(q);break;
case 2: deQueue(q);break;
case 3: QueueLength(q);break;
case 4: displayqueue(q);break;
case 5: ClearQueue(q);break;
default :break;
} } }
1”<2“<4“<