《数据结构》课程实验报告

注：空间不够，可以增加页码。

 

第二篇：数据结构栈与队列的实验报告

数据结构

栈与队列实验报告

学院：数学与计算机学院

班级：计算机科学与技术

姓名：杨理源

学号：201310401069

实验三   栈与队列

一、实验目的：

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

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

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

（4）掌握栈的应用；

二、实验要求：

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

(2) 对源程序给出注释。

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

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

 

 

 

 

 

 

 

 

 

四、实验内容：

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

#include <stdio.h>

#include <stdlib.h>

 #include <malloc.h> 

#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",&n); 

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

scanf("%d",&flag); 

printf("将十进制数%d 转化为%d 进制是：\n",n,flag); 

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",e);      

} 

}    

printf("\n");   

return 0;   }    

int main()  

{     

sqstack s;    

StackInit(&s);    

conversion(&s);   

 return 0;

}

2、回文数判断

#include<stdio.h>

#include<string.h>

#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",MAX);

   for(i = 0;i<MAX+1;i++)

   {

          scanf("%c",&a[i]);

          if(a[i] == '*')

                 break;

   }

   cnt = i;

   InitStack(&s);

   InitQuene(&q);

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

   {

          EnterQuene(&q,a[i],cnt);

          Push(&s,a[i],cnt);

   }

   for(i = 0;i<cnt+1;i++)

   {

          DeleteQuene(&q,&b[i],cnt);

          printf("%c",b[i]);

   }

   printf("\n");

   for(i = 0;i<cnt+1;i++)

   {

          Pop(&s,&c[i]);

          printf("%c",c[i]);

   }

   printf("\n");

   for(i = 0;i<cnt+1;i++)

   {

          if(b[i] == c[i])

                 flag = 1;

          else

          {

                 flag = 0;

                 break;

          }

   }

   if(flag)

          printf("Right");

   else

          printf("Wrong");

   printf("\n");

}

五、运行结果