数据结构栈与队列的实验报告

数据结构

栈与队列实验报告

学院：数学与计算机学院 班级：计算机科学与技术 姓名：*** 学号：************

实验三 栈与队列

一、实验目的：

（1）熟练掌握栈和队列的结构以及这两种数据结构的特点、栈与队列的基本操作。

（2）能够在两种存储结构上实现栈的基本运算，特别注意栈满和栈空的判断条件及描述方法；

（3）熟练掌握链队列和循环队列的基本运算，并特别注意队列满和队列空的判断条件和描述方法； （4）掌握栈的应用；

二、实验要求：

(1) 给出程序设计的基本思想、原理和算法描述。 (2) 对源程序给出注释。

(3) 记录程序的运行结果，并结合程序进行分析。

三、程序设计的基本思想、原理和算法描述：

四、实验内容：

1、利用栈的基本操作将一个十进制的正整数转换成R进制数据，并将其转换结果输出。

#include #include #include #define stack_init_size 100 #define stackincrement 10 typedef struct sqstack { int *base; int *top; int stacksize; } sqstack;

int StackInit(sqstack *s)

{ s->base=(int *)malloc(stack_init_size *sizeof(int)); if(!s->base) return 0; s->top=s->base;

s->stacksize=stack_init_size; return 1; }

int Push(sqstack *s,int e) {

if(s->top-s->base>=s->stacksize) {

s->base=(int *)realloc(s->base,(s->stacksize+stackincrement)*sizeof(int)); if(!s->base) return 0;

s->top=s->base+s->stacksize; s->stacksize+=stackincrement; }

*(s->top++)=e; return e; }

int Pop(sqstack *s,int e) {

if(s->top==s->base) return 0; e=*--s->top; return e; }

int stackempty(sqstack *s) {

if(s->top==s->base) {

return 1; } else {

return 0; } }

int conversion(sqstack *s) {

int n,e=0,flag=0; printf(\"

输入要转化的十进制数： \\n\");

scanf(\"%d\

printf(\"要转化为多少进制：2 进制、8 进制、16 进制填数字！\\n\"); scanf(\"%d\

printf(\"将十进制数%d 转化为%d 进制是：\\n\ while(n) {

Push(s,n%flag); n=n/flag; }

while(!stackempty(s)) {

e=Pop(s,e); switch(e) {

case 10: printf(\"A\"); break;

case 11: printf(\"B\"); break;

case 12: printf(\"C\"); break;

case 13: printf(\"D\"); break;

case 14: printf(\"E\"); break;

case 15: printf(\"F\"); break;

default: printf(\"%d\ } }

printf(\"\\n\"); return 0; } int main() {

sqstack s; StackInit(&s); conversion(&s); return 0; }

2、回文数判断 #include #include #define MAX 50 #define FALSE 0 #define TURE 1 //定义栈 typedef struct {

char elem[MAX]; int top; }SeqStack;

//定义循环队列 typedef struct {

char element[MAX]; int front; int rear; }SeqQuene; //初始化栈

void InitStack(SeqStack *S) {

S->top = -1;//构造一个空栈 }

//入栈

int Push(SeqStack *S,char x,int cnt) {

if(S->top == cnt-1) return(FALSE); S->top++;

S->elem[S->top] = x;

return(TURE); }

//出栈

int Pop(SeqStack * S,char * x) {

if(S->top == -1) return(FALSE); else { *x = S->elem[S->top]; S->top--; return(TURE); } }

//初始化队列

void InitQuene(SeqQuene *Q) {

Q->front = Q->rear = 0; }

//入队

int EnterQuene(SeqQuene *Q,char x,int cnt) {

if((Q->rear+1)%(cnt+1) == Q->front) return(FALSE);

Q->element[Q->rear] = x;

Q->rear = (Q->rear+1)%(cnt+1); return(TURE); }

//出队

int DeleteQuene(SeqQuene *Q,char *x,int cnt) {

if(Q->front == Q->rear) return(FALSE);

*x = Q->element[Q->front];

Q->front = (Q->front+1)%(cnt+1); return(TURE); }

//主函数 void main() {

int i,cnt,flag; SeqStack s; SeqQuene q;

char a[MAX],b[MAX],c[MAX]; flag=0;

printf(\"请输入由*结束且小于%d的回文序列：\\n\ for(i = 0;icnt = i;

InitStack(&s); InitQuene(&q); for(i = 0;ifor(i = 0;iprintf(\"\\n\"); for(i = 0;iprintf(\"\\n\");

for(i = 0;iif(flag) printf(\"Right\"); else printf(\"Wrong\");

printf(\"\\n\"); }

五、运行结果