数据结构 —— 数塔问题
今日一言：
不要去学你认为不需要的东西。
—— 秋山耀平
数据结构 —— 数塔问题
咱也不知道写点什么，更新道数据结构题吧。
C语言
很少拿C++，Java之类的写算法，
其实也不是因为不会啦，只是压根就不会而已。
#include "stdio.h"#include "stdlib.h"#define LEFT 0 // 往左走的标志#define RIGHT 1 // 往右走的标志#define BACK 2 // 往回走的标志// 其实可以回溯迭代，但想想，写都写了，就算了#define MAX_LAYER 5 // 层级// 存储数塔数据int tower[MAX_LAYER][MAX_LAYER] = { {19,7,10,4,16},{2,18,9,5},{10,6,18},{12,15},{9} }; //[layer][index]// 下面的逻辑其实很简单，就是用了栈。// 当时刚学数据结构的栈，便这么用了。typedef struct { int index; int flag;} Elem; // 栈元素类型typedef struct { Elem* base; Elem* top; int layer;} Stack; // 栈容器类型int tempValue = 0;// 缓存值，为全局Stack* Tstack; // 操作的栈变量，为全局int tempPath[MAX_LAYER]; // 缓存路径// 这次的写法缺陷是不能存储所有路径的情况，只会一直存储最佳路径void initStack() { // 初始化栈 Tstack = (Stack*)malloc(sizeof(Stack)); Tstack->base = (Elem*)malloc(sizeof(Elem) * MAX_LAYER); if (!Tstack->base) { printf("error\n"); exit(0); } Tstack->top = Tstack->base; Tstack->layer = -1; printf("初始化完成\n");}void pushStackByTstack(Stack* Tstack, Elem elem) { //压栈 函数名长了点 Tstack->top++; *Tstack->top = elem; Tstack->layer++; //printf("压入%d : %d : %d\n",Tstack->layer,Tstack->top->flag,Tstack->top->index); //if( Tstack->layer == MAX_LAYER-1 ) printf("top\n");}void pushStack(Elem elem) { // 压栈 函数名就短了 pushStackByTstack(Tstack, elem);}Elem popStackByTstack(Stack* Tstack) { // 出栈 函数名长了点 Elem elem = *Tstack->top; Tstack->top--; Tstack->layer--; //printf("取出%d : %d : %d\n",Tstack->layer,Tstack->top->flag,Tstack->top->index); return elem;}Elem popStack() { // 出栈 函数名就短了 popStackByTstack(Tstack);}int getMaxIndexByLayer(int layer) { // 获取每层的最大索引 return MAX_LAYER - layer - 1;}void GoGoGo(int index) { // 核心逻辑程序 int tempV = 0; //压入栈底 Elem elemBase; elemBase.flag = (index) ? LEFT : RIGHT; //printf("flag:%d\n",elemBase.flag); elemBase.index = index; tempV += tower[0][index]; pushStack(elemBase); while (1) { // 未达到顶层 if (Tstack->top->flag == LEFT) { Elem elemLeft; //前往左上 if (Tstack->layer == MAX_LAYER - 2) elemLeft.flag = BACK; else elemLeft.flag = (Tstack->top->index <= 1) ? RIGHT : LEFT; elemLeft.index = (Tstack->top->index) ? Tstack->top->index - 1 : 0; tempV += tower[Tstack->layer + 1][elemLeft.index]; pushStack(elemLeft); } else if (Tstack->top->flag == RIGHT) { Elem elemRight; //前往右上 elemRight.index = (Tstack->top->index); if (Tstack->layer == MAX_LAYER - 2) elemRight.flag = BACK; else elemRight.flag = (Tstack->top->index == getMaxIndexByLayer(Tstack->layer + 1)) ? LEFT : RIGHT; Tstack->top->flag = BACK; tempV += tower[Tstack->layer + 1][elemRight.index]; pushStack(elemRight); } else if (Tstack->top->flag == BACK) { // 到达顶层 if (Tstack->layer == MAX_LAYER - 1) { //printf("tempV:%d\n",tempV); if (tempValue < tempV) { // 保存最大值 tempValue = tempV; int i; for (i = 0; i < MAX_LAYER; i++) { tempPath[i] = (*(Tstack->top - i)).index; } } } tempV -= tower[Tstack->layer][Tstack->top->index]; popStack(); if (Tstack->layer == -1) break; if (Tstack->top->flag == LEFT) { Tstack->top->flag = (Tstack->top->index == getMaxIndexByLayer(Tstack->layer)) ? BACK : RIGHT; //printf("%d->%d->%d\n",Tstack->top->index,Tstack->layer,getMaxIndexByLayer(Tstack->layer)); } else if (Tstack->top->flag == RIGHT) { Tstack->top->flag = BACK; } } else { printf("error flag is invalid\n"); exit(0); } }}//遍历数塔void itTheTower() { int i; initStack(); for (i = 0; i <= getMaxIndexByLayer(0); i++) { //printf("%d！\n",i); GoGoGo(i); } printf("The maxValue of all paths: %d\n", tempValue); printf("path: "); for (i = MAX_LAYER - 1; i >= 0; i--) { printf("%d", tower[i][tempPath[MAX_LAYER - i - 1]]); if (i) printf("->"); else { printf(";\n"); } }}void main() { itTheTower();}运行结果
初始化完成The maxValue of all paths: 63path: 9->15->18->5->16;