栈的顺序表示和实现一、实验目的1. 了解栈和队列的特性。

2. 掌握栈的顺序表示和实现。

3. 掌握栈的链式表示和实现。

4. 掌握队列的顺序表示和实现。

5. 掌握队列的链式表示和实现。

6. 掌握栈和队列在实际问题中的应用。

二、实验要求1.认真阅读和掌握本实验的程序。

2. 上机运行本程序。

3. 保存和打印出程序的运行结果，并结合程序进行分析。

4. 按照对顺序表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。

三、实验内容编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初始化顺序栈。

（2）插入元素。

（3）删除栈顶元素。

（4）取栈顶元素。

（5）遍历顺序栈。

（6）置空顺序栈。

四，解题思路五、程序清单#include<stdio.h>#include<stdlib.h>#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef struct{ ElemType stack[MAXNUM];int top;}SqStack;/*初始化顺序栈*/void InitStack(SqStack *p){ if(! p)printf("内存分配失败！");p->top=-1;}/*入栈*/void Push(SqStack *p,ElemType x){ if(p->top<MAXNUM-1){ p->top=p->top+1;p->stack[p->top]=x;}elseprintf("Overflow!\n");}/*出栈*/ElemType Pop(SqStack *p){ ElemType x;if(p->top>=0){ x=p->stack[p->top];printf("以前的栈顶数据元素%d已经被删除！\n",p->stack[p->top]);p->top=p->top-1;return(x);}else{ printf("Underflow!\n");return(0);}}/*获取栈顶元素*/ElemType GetTop(SqStack *p){ ElemType x;if(p->top>=0){ x=p->stack[p->top];printf("\n栈顶元素喂：%d\n",x);return(x);}else{ printf("Underflow!\n");return(0);}}/*遍历顺序栈*/void OutStack(SqStack *p){ int i;printf("\n");if(p->top<0)printf("这是一个空栈！");printf("\n");for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d\n",i,p->stack[i]);}/*置空顺序栈*/void setEmpty(SqStack *p){ p->top=-1;}/*主函数*/void main(){ SqStack *q;int cord;ElemType a;printf("第一次使用必须初始化！\n");do{printf("\n");printf("\n----------主菜单-----------\n");printf("\n 1 初始化顺序栈\n");printf("\n 2 插入一个元素\n");printf("\n 3 删除栈顶元素\n");printf("\n 4 取栈顶元素\n");printf("\n 5 置空顺序栈\n");printf("\n 6 结束程序运行\n");printf("\n-----------------------------\n");printf("清输入您的选择（1，2，3，4，5，6）");scanf("%d",&cord);printf("\n");switch(cord){ case 1:{ q=(SqStack *)malloc(sizeof(SqStack));InitStack(q);OutStack(q);}break;case 2:{ printf("清输要插入的元素：a=");scanf("%d",&a);Push(q,a);OutStack(q);}break;case 3:{ Pop(q);OutStack(q);}break;case 4:{ GetTop(q);OutStack(q);}break;case 5:{ setEmpty(q);printf("\n顺序栈被置空！\n");OutStack(q);}break;case 6:exit(0);}}while(cord<=6);}六、调试心得及收获七、其他所想到的队列基本操作一．预备知识1．队列的学习要点熟练掌握在两种存储结构上实现队列的基本运算，特别注意队满和队空的条件以及如何描述；掌握队列的特点、操作原则；熟练掌握循环队列和链队列的基本操作；懂得在什么情况下会应用到队列。

2．队列的概念和操作原则队列是限定只能在表的一端进行插入，另一端进行删除的线性表。

通过定义我们要注意以下几点：队列还是线性表，不过在操作中不能随心所欲，只能做限定的某些动作；队列的操作原则是先进先出（FIFO）；入队操作只能从称为队尾的一端进行；出队操作只能从队列的另外一端，即称为队头的一端进行；队列的中间不能进、出元素；同一个队列中的元素类型是相同的。

?3．队列的两种存储结构队列的顺序存储结构中，规定了将变量front指向队头元素所在位置，变量rear指向队尾元素所在位置的下一个空位，这样的规定是为了方便操作。

注意队列的顺序存储结构在入队出队的时候要考虑队满和队空的情况。

普通队列会产生一个假溢出的问题，解决方案是采用循环队列。

循环队列以牺牲一个存储单元为代价，解决循环队列队空队满标志冲突的问题，所以容量为n的循环队列最多可以存放n-1个元素。

#include<iostream.h>#include<malloc.h>#include<stdlib.h>#define MAXSIZE 100#define TRUE 1#define FALSE 0typedef int DataType;typedef struct{DataType data[MAXSIZE];int front; //头指针指示器int rear; //为指针指示器}SeqQueue;//初始化操作void InitQueue(SeqQueue *Q){//将*Q初始化为一个空的循环队列Q->front=Q->rear=0;}//判断队列是否为空或满void IsEmpty_full(SeqQueue *Q){if(Q->front==Q->rear)cout<<"该队列为空"<<endl;else if((Q->rear+1)%MAXSIZE==Q->front)cout<<"该队列为满"<<endl;elsecout<<"该队列既不为空也不为满"<<endl;}//入队操作int EnterQueue(SeqQueue *Q,DataType x){//将元素x入队if((Q->rear+1)%MAXSIZE==Q->front) //队列已经满了return(FALSE);Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE; //重新设置队尾指针return(TRUE); //操作成功}//出队操作int DeleteQueue(SeqQueue *Q,DataType *x){//删除队列的队头元素，用x返回其值if(Q->front==Q->rear) //队列为空return(FALSE);*x=Q->data[Q->front];Q->front=(Q->front+1)%MAXSIZE; //重新设置队头指针return(TRUE); //操作成功}//清空元素void ClearQueue_Sq(SeqQueue &Q){Q.front=Q.rear=0;}//构造队列，数据元素由键盘输入void CreateQueue_Sq(SeqQueue &Q){DataType temp;cout<<"输入数据元素（按-1结束）"<<endl;cin>>temp;while(temp!=-1){if((Q.rear+1)%MAXSIZE == Q.front) cout<<"队列已经满了";else{Q.data[Q.rear]=temp;Q.rear=(Q.rear+1)%MAXSIZE;cin>>temp;}}}//队列的长度int QueueLength_Sq(SeqQueue Q){return (Q.rear-Q.front+MAXSIZE) % MAXSIZE;}//由头到尾依次输出队列的数据元素void OutputQueue_Sq(SeqQueue Q){if(Q.front==Q.rear) cout<<"空队列，没有元素"<<endl;else{cout<<"该循环队列各元素依次为：";for(int k=0; k<=QueueLength_Sq(Q)-1; k++)cout<<Q.data[(Q.front+k)%MAXSIZE]<<" ";cout<<endl;}}void main(){int flag=1,select;cout<<" ☆☆☆☆循环队列的基本操作☆☆☆☆"<<endl;cout<<" ☆1.请输入循环队列元素：☆ "<<endl;cout<<" ☆2.判断队列是否为空或是否为满☆"<<endl;cout<<" ☆3.当前队头元素出队并将其输出循环队列的各元素☆ "<<endl;cout<<" ☆4.将x入队并输出循环队列的各元素☆ "<<endl;cout<<" ☆5.当前循环队列的长度☆ "<<endl;cout<<" ☆6.清空队列☆ "<<endl;cout<<" ☆7.退出☆ "<<endl;while(flag){cout<<"请选择: ";cin>>select;SeqQueue Q;int x,a,e;switch(select){case 1:InitQueue(&Q);CreateQueue_Sq(Q);OutputQueue_Sq(Q);break;cout<<"请选择: ";case 2:IsEmpty_full(&Q);break;cout<<"请选择: ";case 3:DeleteQueue(&Q,&a);OutputQueue_Sq(Q);break;cout<<"请选择: ";case 4:cout<<"请输入入队的元素x：";cin>>x;EnterQueue(&Q,x);OutputQueue_Sq(Q);break;cout<<"请选择: ";case 5:cout<<"当前循环队列的长度是："<<(Q.rear-Q.front+MAXSIZE) % MAXSIZE<<endl;break;cout<<"请选择: ";case 6:ClearQueue_Sq(Q);cout<<"该循环队列已清空, ";break;case 7:flag=0;break;}}}串的基本操作的实现一、实验目的：掌握串的运算（赋值、连接、比较、求子串等）。