数据结构day5

一、思维导图

二、课后练习

1、使用循环链表完成约瑟夫环问题

2、使用栈，完成进制转换（输入：一个整数，进制数，输出：该数的对应的进制数）

//头文件

#ifndef DEC_TO_BIN_H
#define DEC_TO_BIN_H

#include <myhead.h>

typedef int datatype;
#define MAX 100

typedef struct
{
	datatype *data;
	int top;
}Stack,*StackPtr;

//创建栈
StackPtr stack_create();

//判空
int stack_empty(StackPtr S);

//判满
int stack_full(StackPtr S);

//入栈
void stack_push(StackPtr S,datatype element);

//出栈
void stack_pop(StackPtr S);

//遍历栈
void stack_show(StackPtr S);

//将整数转换成对应的进制数
void Dec_to_Bin(StackPtr S, int element,int num);



#endif

//功能函数

#include "Dec_to_Bin.h"

//创建栈
StackPtr stack_create()
{
	//在堆区申请一个栈大小的空间
	StackPtr S = (StackPtr)malloc(sizeof(Stack));
	if(NULL == S)
	{
		printf("创建失败\n");
		return NULL;
	}

	//栈申请成功,申请存储栈的空间
	//申请MAX个datatype类型数据大小的空间
	S->data = (datatype *)malloc(sizeof(datatype) * MAX);
	if(NULL == S->data)
	{
		printf("申请栈存储空间失败\n");
		return NULL;
	}

	//给空间内容初始化
	memset(S->data,0,sizeof(datatype)*MAX);

	//栈顶元素变量初始化
	S->top = -1;
	//返回栈地址
	return S;
}

//判空
int stack_empty(StackPtr S)
{
	return S->top == -1;
}
//判满
int stack_full(StackPtr S)
{
	return S->top == MAX-1;

}
//入栈
void stack_push(StackPtr S,datatype element)
{
	//判断逻辑
	if(NULL == S || stack_full(S))
	{
		printf("入栈失败\n");
		return;
	}

	//入栈
	//先偏移栈顶位置
	S->top++;
	//再将数据压入栈中
	S->data[S->top] = element;
}
//出栈
void stack_pop(StackPtr S)
{
	//判断逻辑
	if(NULL == S || stack_empty(S))
	{
		printf("出栈失败\n");
		return;
	}

	//出栈
	//先弹后减
	printf("%d出栈成功\n",S->data[S->top]);
	S->top--;
}

//遍历栈
void stack_show(StackPtr S)
{
	//判断逻辑
	if(NULL == S ||stack_empty(S))
	{
		printf("遍历失败\n");
		return;
	}

	for(int i=S->top;i>=0;i--)
	{
		printf("%d",S->data[i]);
	}
	printf("\n");
}


//将整数转换成对应的进制数
void Dec_to_Bin(StackPtr S, int element,int num)
{
	//对element循环取余并压入栈中
	while(element)
	{
		stack_push(S,element%num);
		//将element除以num
		element /= num;
	}
}

//主函数

#include "Dec_to_Bin.h"
int main(int argc, const char *argv[])
{
	while(1)
	{
		//创建栈
		StackPtr S = stack_create();

		//提示输入
		int element,num;
		printf("请输入一个整数和你需要转换的进制数:");
		scanf("%d%d",&element,&num);

		//将整数转换成进制数存入栈中
		Dec_to_Bin(S,element,num);

		//将栈输出
		printf("该整数的%d进制数为：",num);
		stack_show(S);
	}
 
	return 0;
}