栈和队列实验报告

栈的顺序表示和实现

一、实验目的

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;

}

else

printf("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 0

typedef 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;

else

cout<<"该队列既不为空也不为满"<<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;

}

串的基本操作的实现

一、实验目的：掌握串的运算（赋值、连接、比较、求子串等）。

二、实验内容：串的基本操作的实现。

三、实验要求：

1、用C完成算法设计和程序设计并上机调试通过。

2、撰写实验报告，提供实验结果和数据。

3、分析算法，要求给出具体的算法分析的结果，包括时间复杂度的分析，并简要给出算法设计小结和心得。

四、程序实现

写出每个操作的算法（操作过程），程序运行情况。

五、写出输入数据及运行结果。

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define m 100

typedef struct{

char ch[m];

int length;

}Hstr;

void main()

{

Hstr *l,*p,*r;

char c,w;

int h,j,k;

int i=0;

l=(Hstr *)malloc(sizeof(Hstr));

p=(Hstr *)malloc(sizeof(Hstr));

r=(Hstr *)malloc(sizeof(Hstr));

l->length=0;

p->length=0;

r->length=0;

printf("请选择相关操作（数字1~5控制,输入0结束）\n");

printf("--------------1.建立串---------------\n");

printf("--------------2.显示串长度-----------\n");

printf("--------------3.生成与原来相同的串---\n");

printf("--------------4.串比较---------------\n");

printf("--------------5.串连接---------------\n");

printf("--------------6.返回值---------------\n");

scanf("%c",&w);

getchar();

while(w)

{

switch(w)

{

case '1':{printf("请输入字符(#结束):\n");

scanf("%c",&c);

while(c!='#')

{ l->length++;

l->ch[i]=c;

i++;

scanf("%c",&c);

}

printf("串中字符为\n");

for(i=0;i<l->length;i++)

printf("%c",l->ch[i]);

printf("\n");

}break;

case '2':{

printf("串长度为%d\n",l->length);}break;

case '3':{

for(i=0;i<l->length;i++)

{

p->ch[i]=l->ch[i];

}

p->length=l->length;

printf("复制的串中字符为\n");

for(i=0;i<p->length;i++)

printf("%c",p->ch[i]);

printf("\n");

}break;

case '4':{i=0;

printf("请输入要与原串比较的字符串(#结束):\n");

scanf("%c",&c);

while(c!='#')

{ r->length++;

r->ch[i]=c;

i++;

scanf("%c",&c);

}

printf("第二个串中字符为\n");

for(i=0;i<r->length;i++)

printf("%c",r->ch[i]);

printf("\n");

for(i=0;i<r->length&&i<l->length;i++)

{

if(l->ch[i]!=r->ch[i])

{if((l->ch[i]-r->ch[i])<0){printf("第二个串大"); printf("\n");}

if((l->ch[i]-r->ch[i])>0){printf("第一个串大"); printf("\n");}

break;}

}

if(i==r->length||i==l->length)printf("两个串一样大\n");

}break;

case'5':{i=0;

printf("请输入要与原串连接的串（#结束）\n");

scanf("%c",&c);

while(c!='#')

{r->length++;

r->ch[i]=c;

i++;

scanf("%c",&c);

}

printf("第二个串中字符为\n");

for(i=0;i<r->length;i++)

printf("%c",r->ch[i]);

printf("\n");

for(i=0,j=0;i<r->length;i++,j++)

l->ch[l->length+i]=r->ch[j];

l->length=l->length+r->length;

printf("连接后第一个串中字符为\n");

for(i=0;i<l->length;i++)

printf("%c",l->ch[i]);

printf("\n");

}break;

case '6':{

i=0;

printf("请输入要找串的起始位置（第几个字符？）\n");

scanf("%d",&h);

printf("请输入要找的字符个数\n");

scanf("%d",&k);

printf("内容为：\n");

for(i=0;i<k;i++)

{

printf("%c",l->ch[h-1]);

h++;

}

printf("\n");

}break;

case'0':exit(0);

}

getchar();

printf("请选择相关操作（数字1~6控制,输入0结束）\n");

printf("--------------1.建立串---------------\n");

printf("--------------2.显示串长度-----------\n");

printf("--------------3.生成与原来相同的串---\n");

printf("--------------4.串比较---------------\n");

printf("--------------5.串连接---------------\n");

printf("--------------6.返回值---------------\n");

scanf("%c",&w);

getchar();

}

相关推荐

栈和队列实验报告

专栏推荐