#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义蜗牛信息的结构体
struct Snail
{
int ni; // 爬行速度 ni
int mi; // 滑行速度 mi
int height; // 当前高度
int time; // 爬完整棵树所需的时间
};
// 定义链表结点
struct Node
{
struct Snail snail;
struct Node *next;
};
// 定义顺序栈
struct Stack
{
int top;
int data[MAX_SIZE];
};
// 创建链表
struct Node *createList(int n)
{
struct Node *head = NULL;
struct Node *p = NULL;
int i;
for ( i = 0; i < n; i++)
{
struct Snail snail;
printf("输入第 %d 只蜗牛的爬行速度 ni 和滑行速度 mi: ", i + 1);
printf("\n");
scanf("%d%d", &snail.ni, &snail.mi);
snail.height = 0;
snail.time = 0;
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->snail = snail;
node->next = NULL;
if (head == NULL) //链表为空，将新节点作为头结点
{
head = node;
p = node;
}
else
{
p->next = node;
p = node;
}
return head;
}
// 初始化顺序栈
void initStack(struct Stack *stack)
{
stack->top = -1;
}
// 判断栈是否为空
int isStackEmpty(struct Stack *stack)
{
return stack->top == -1;
}
// 判断栈是否已满
int isStackFull(struct Stack *stack)
{
return stack->top == MAX_SIZE - 1;
}
// 入栈
void push(struct Stack *stack, int x)
{
if (isStackFull(stack))
{
printf("栈已满\n");
return;
}
stack->data[++stack->top] = x;
}
// 出栈
int pop(struct Stack *stack)
{
if (isStackEmpty(stack))
{
printf("栈为空\n");
return -1;
}
return stack->data[stack->top--];
}
struct Node *Input()
{
printf("输入树的高度 h 和蜗牛的数量 n: ");
int h, n;
scanf("%d%d", &h, &n);
printf("\n\n");
// 创建链表
struct Node *head = createList(n);
// 初始化顺序栈
struct Stack stack;
initStack(&stack);
// 循环模拟蜗牛的爬行过程
while (1)
{
int flag = 1; // 标记是否还有蜗牛在爬行
struct Node *p = head;
while (p != NULL)
{
while(p->snail.height<h)
{
p->snail.time++;
p->snailheight += p->snail.ni; //爬行
push(&stack, p->snail.height); //压入栈中
if(p->snail.height>=h)
{
break;
}
p->snail.height -= p->snail.mi; //滑行
push(&stack, p->snail.height); //压入栈中
}
if (p->snail.height < 0) //位置小于0，将位置设置为0
{
p->snail.height = 0;
}
if (p->snail.height >=h) //位置大于h，将位置设置为h
{
p->snail.height = h;
}
else
{
flag = 0;
}
p = p->next;
}
if (flag)
{
break;
}
}
return head;
}
void frequency(struct Stack stack,int h)
{
// 统计树的每一米线都有多少次蜗牛爬过
int count[MAX_SIZE];
int j;
for(j=0;j<MAX_SIZE;j++) //数组初始化
{
count[j]=0;
}
while (!isStackEmpty(&stack))
{
int x = pop(&stack); //出栈
count[x]++;
}
// 输出每一米线被爬过的次数
int i;
printf("****************每一米线被爬过的次数****************\n\n");
for (i = 1; i <= h; i++){
printf("第 %d 米线被爬过的次数: %d\n", i, count[i]);
}
printf("\n");
}
int times(struct Node *head)
{
// 找出哪只蜗牛爬得最快
int minTime = -1;
struct Node *p = head;
while (p != NULL)
{
struct Snail snail = p->snail;
if (minTime == -1 ||snail.time < minTime)
{
minTime =snail.time;
}
p = p->next;
}
//输出每只蜗牛的爬行时间
p=head;
int k=0;
printf("*****************每只蜗牛的爬行时间*****************\n\n");
while(p!=NULL)
{
k++;
struct Snail snail=p->snail;
printf("第 %d 只蜗牛的爬行时间：%d\n",k,snail.time);
p=p->next;
}
printf("\n\n");
return minTime;
}
void fast(struct Node *head,int minTime)
{
// 输出爬得最快的蜗牛的爬行速度规律
struct Node *p;
p = head;
printf("***************爬的最快的蜗牛的爬行规律***************\n\n");
while (p != NULL)
{
struct Snail snail = p->snail;
if (snail.time == minTime)
{
printf("爬得最快的蜗牛的爬行速度规律: ni=%d, mi=%d\n\n", snail.ni, snail.mi);
}
p = p->next;
}
}
{
printf("第 %d 米线被爬过的次数: %d\n", i, count[i]);
}
printf("\n");
}int times(struct Node *head)
{
// 找出哪只蜗牛爬得最快
int minTime = -1;
struct Node *p = head;
while (p != NULL)
{
struct Snail snail = p->snail;
if (minTime == -1 ||snail.time < minTime)
{
minTime =snail.time;
}
p = p->next;
}
//输出每只蜗牛的爬行时间
p=head;
int k=0;
printf("*****************每只蜗牛的爬行时间*****************\n\n");
while(p!=NULL)
{
k++;
struct Snail snail=p->snail;
printf("第 %d 只蜗牛的爬行时间：%d\n",k,snail.time);
p=p->next;
}
printf("\n\n");
return minTime;
}
void fast(struct Node *head,int minTime)
{
// 输出爬得最快的蜗牛的爬行速度规律
struct Node *p;
p = head;
printf("***************爬的最快的蜗牛的爬行规律***************\n\n");
while (p != NULL)
{
struct Snail snail = p->snail;
if (snail.time == minTime)
{
printf("爬得最快的蜗牛的爬行速度规律: ni=%d, mi=%d\n\n", snail.ni, snail.mi);
}
p = p->next;
}
}
void menu()
{
int choose;
int h,n,min;
struct Node *head;
struct Stack stack;
system("mode con cols=88 lines=80");
system("color f1");
do
{
printf("\t\t-----------------------蜗牛爬树-----------------------\n");
printf("\t\t***************1.输入高度 h 和蜗牛个数 n *************\n\n");
printf("\t\t**************1.输出每一米线被爬过的次数**************\n\n");
printf("\t\t***************2.输出每只蜗牛的爬行时间***************\n\n");
printf("\t\t*************3.输出爬的最快的蜗牛的爬行规律***********\n");
printf("\t\t------------------------------------------------------\n\n");
printf("请输入你要进行的操作：");
scanf("%d",&choose);
while(1)
{
if(choose<1||choose>4)
{
printf("您输入的指令有误，请重新输入!");
system("pause");
return;
}
else break;
}
switch(choose)
{
case 1:head=Input();break;
case 1:frequency(stack,h);break;
case 2:min=times(head);break;
case 3:fast(head,min);break;
default:printf("您输入的指令有误，请重新输入!");break;
}
}while(1);
}
int main()
{
while(1)
{
menu();
}
return 0;
}
int main()
{
while (1)
{
// 输出菜单
printf("\t\t-----------------------蜗牛爬树-----------------------\n");
printf("\t\t***************1.输入高度 h 和蜗牛个数 n *************\n\n");
printf("\t\t**************2.输出每一米线被爬过的次数**************\n\n");
printf("\t\t***************3.输出每只蜗牛的爬行时间***************\n\n");
printf("\t\t*************4.输出爬的最快的蜗牛的爬行规律***********\n");
printf("\t\t*************5.退出程序*****************************\n");
printf("\t\t请输入你的选择：");
// 读入用户的选择
int choice;
scanf("%d", &choice);
// 根据用户的选择执行相应的操作
switch (choice)
{
case 1:
{
// 输入树的高度和蜗牛的数量
int h, n;
printf("输入树的高度 h 和蜗牛的数量 n: ");
scanf("%d%d", &h, &n);
printf("\n\n");
// 创建链表
struct Node *head = createList(n);
// 模拟蜗牛的爬行过程
simulate(h, head);
break;
}
case 2:
{
// 输出每一米线被爬过的次数
// TODO: 你可以在这里添加代码实现该功能
break;
}
case 3:
{
// 输出每只蜗牛的爬行时间
// TODO: 你可以在这里添加代码实现该功能
break;
}
case 4:
{
// 输出爬的最快的蜗牛的爬行规律
// TODO: 你可以在这里添加代码实现该功能
break;
}
case 5:
{
// 退出程序
return 0;
}
default:
{
printf("输入有误，请重新输入\n");
break;
}
}
}
}