数据结构实验课_实验三 栈

一、实验内容
1．采用顺序存储实现栈的初始化、入栈、出栈操作。
2．采用链式存储实现栈的初始化、入栈、出栈操作。
3．写一个程序，实现十进制数据M向N进制(2或8或16）的转换。
(1）采用顺序存储结构实现栈。
(2）采用链表结构实现栈。

第一个:数组__栈
代码实现:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define Stack_Size 100
#define OK    1
#define ERROR    0
typedef int ElemType;
typedef struct Stack
{ElemType elem[Stack_Size];//用来存放栈中元素的一维数组int  top;//用来存放栈顶元素的下标
}Stack;
int InitStack(Stack **s)//初始化顺序栈 
{*s=(Stack *)malloc(sizeof(Stack));(*s)->top=-1;return 0;
}
int EmptyStack(Stack s)//判断栈空 
{return s.top==-1;
}
int GetTop(Stack s,int *e)//取栈顶元算 
{if(EmptyStack(s))return 0;*e=s.elem[s.top];return 1;
}
void Push(Stack *s,int e)//入栈 
{if(s->top==Stack_Size-1)return;s->top++;s->elem[s->top]=e;
}
void PrintStack(Stack s)//打印栈中数据 
{int i;for(i=0;i<=s.top;i++)printf("%d ",s.elem[i]);printf("\n");
}
int Pop(Stack *s,int *e)//出栈 
{if(EmptyStack(*s))return 0;*e=s->elem[s->top];s->top--;return 1;
}
void Conversion(Stack *S)
{int N,n1,t;printf("输入一个十进制数字:\n");scanf("%d",&N);//输入一个十进制数字printf("输入要转换的n进制数字(2、8、16):\n");scanf("%d",&n1);//输入要转换的进制while(N){Push(S,N%n1);N=N/n1;}printf("该数转化为%d进制数为：\n");while(!EmptyStack(*S)){Pop(S,&t);if(t==10) {printf("A");continue;}if(t==11) {printf("B");continue;}if(t==12) {printf("C");continue;}if(t==13) {printf("D");continue;}if(t==14) {printf("E");continue;}if(t==15) {printf("F");continue;}printf("%d",t);}printf("\n");
}int main()
{Stack *s;int i,num;printf("请输入你要生成多少随机数压入栈: ");InitStack(&s);scanf("%d",&num);srand((unsigned)time(NULL));for(i=0;i<num;i++)Push(s,rand()%100);PrintStack(*s);while(!EmptyStack(*s)){Pop(s,&num);printf("%d ",num);}printf("\n");Conversion(s);return 0;
}

程序演示:

第二个 链表__栈
代码实现:

#include <stdio.h>
#include <stdlib.h>
#include<time.h> 
#define Stack_Size 100
#define OK    1
#define ERROR    0
typedef int ElemType;
typedef struct stacknode 
{ElemType data;struct stacknode *next;
}StackNode;
typedef struct
{StackNode *top;  /*栈顶指针*/
}Stack;
void InitStack(Stack **s)//初始化栈 
{*s=(Stack*)malloc(sizeof(Stack));(*s)->top=NULL;
}
int EmptyStack(Stack s)//判断栈空 
{return s.top==NULL;  
}
int GetTop(Stack s,int *e)//取栈顶元素 
{if(EmptyStack(s))return 0;*e=s.top->data;return 1;
}
void Push(Stack *s,int e)//入栈 
{StackNode *p=(StackNode*)malloc(sizeof(StackNode));p->data=e;p->next=s->top;s->top=p;
}int Pop(Stack *s,int *e)//出栈 
{StackNode *p;if(EmptyStack(*s))return 0;p=s->top;*e=p->data;s->top=p->next;free(p);return 1;
}
void PrintStack(Stack s)//打印栈中元素 
{StackNode *p=s.top;while(p){printf("%d ",p->data);p=p->next;}printf("\n");
}
void Conversion(Stack *S)
{int N,n1,t;printf("输入一个十进制数字:\n");scanf("%d",&N);//输入一个十进制数字printf("输入要转换的n进制数字(2、8、16):\n");scanf("%d",&n1);//输入要转换的进制while(N){Push(S,N%n1);N=N/n1;}printf("该函数转化为%d进制数为：\n",n1);while(!EmptyStack(*S)){Pop(S,&t);if(t==10){printf("A");continue;}if(t==11){printf("B");continue;}if(t==12){printf("C");continue;}if(t==13){printf("D");continue;}if(t==14){printf("E");continue;}if(t==15){printf("F");continue;}if(t==16){printf("G");continue;}printf("%d",t);}printf("\n");
}
int main()
{Stack *s;int i,num;InitStack(&s);printf("请输入你要生成多少个随机数:\t");scanf("%d",&num);srand((unsigned)time(NULL));for(i=0;i<num;i++)Push(s,rand()%100);PrintStack(*s);while(!EmptyStack(*s))  {Pop(s,&num);printf("%d ",num);}  printf("\n");Conversion(s);return 0;
}

程序演示:

分析:栈程序需要判断栈空,在顺序栈总用结构体专门定义一个数据域存放栈顶元素的下标,链表栈则直接定义一个栈顶指针.