#include <iostream>
#include <string>using namespace std;typedef char Etype;/************************四染色算法*************************/
#define PRODUCTS ETypestruct PRODUCTS {char name[8];int weight;int number;char place[20];
};struct MAP {int AreaIndex;int color;char palce[20];
};struct SType {int AreaIndex;int ColorIndex;
};struct Stack {SType* element;int top;int maxsize;
};//创建空堆栈
void CreateStack(Stack& S, int MaxStackSize) {S.maxsize = MaxStackSize;S.element = new SType[S.maxsize];//创建数组元素S.top = -1;//top指向的是数据空间的第一个元素,本身的值代表数据元素的下表,空表设top为-1
}//判断堆栈是否为空
bool IsEmpty(Stack& S) {if (S.top == -1) return true;else return false;
}//判断堆栈是否满了
bool IsFull(Stack& S) {if (S.top >= S.maxsize - 1) return true;else return false;
}//返回栈顶元素的值
bool GetTop(Stack& S, SType& result) {if (IsEmpty(S)) return false;result = S.element[S.top];return true;
}//出栈操作,将栈顶元素取出,并且将top指向下一个元素的位置
bool Pop(Stack& S, SType& result) {if (IsEmpty(S)) return false;result = S.element[S.top];S.top--;//栈顶指向下一个元素地址return true;
}//进栈操作,将top+1,输入元素存入新的栈顶
bool Push(Stack& S, SType& x) {//传入的是x的地址if (IsEmpty(S)) return false;S.top++;S.element[S.top] = x;return true;
}Stack MapColor(int r[8][8], int n) {//将地图用四种颜色染色,n个地区间的相邻关系在r数组中表示int currentArea = 1;//当前准备染色区域编号,从1号开始int currentColor = 1;//当前准备染色色素编号,从1号开始Stack S;//定义染色堆栈SType x;//SType 是堆栈元素的数据类型int topkeep;bool flag;int MaxStackSize = 10;CreateStack(S, MaxStackSize);x.AreaIndex = currentArea;x.ColorIndex = currentColor;Push(S, x);//1号地区以1号色素染色,入栈currentArea++;//地区编号加一,为新的地区染色while (currentArea <= n) {topkeep = S.top;//保留当前栈顶指针flag = true; //flag为真时,表示与堆栈中易染色的区域比较时未发现重色while (!IsEmpty(S) && flag) {Pop(S, x);//读取栈中的一个数据if (x.ColorIndex == currentArea && r[currentArea][x.AreaIndex]) {//从栈中读出的区域已使用色素与当前准备染色区域要使用的色素相同,且两个区域相连flag = false;//无法使用当前色素,需要改变色素或者退栈,结束比较}}if ((IsEmpty(S)) &&(x.ColorIndex != currentColor)||(IsEmpty(S)&&!r[currentArea][x.AreaIndex])) {//与已染色区域比较,无一同色//将当前区域号及使用色素进栈,并准备下一区域号,从色素1开始尝试x.AreaIndex = currentArea;x.ColorIndex = currentColor;S.top = topkeep;Push(S, x);currentArea++;currentColor = 1;}else {currentColor++;//准备用下一色素,重新尝试S.top = topkeep;//从栈顶开始尝试while (currentColor > 4) {//如果当前使用色素或推出的栈顶使用的色素超过4,说明栈顶染色不对,需要退栈Pop(S, x);currentColor = x.ColorIndex + 1;currentArea = x.AreaIndex;}flag = true;}}return S;}
详细解决方案
深入理解数据结构——堆栈应用(四染色算法)
热度:12 发布时间:2024-01-17 05:10:02.0
相关解决方案
- 算法效率(数据结构),该如何解决
- 数据结构,很无力~该怎么处理
- 数据结构,该怎么处理
- java 数据结构,该如何解决
- 数据库 数据结构 关于索引解决办法
- 数据结构,离散数学什么的重要吗。该怎么解决
- 数据结构 - 线性表学习(php模拟)
- 【数据结构】【归并排序】
- 数据结构 05——树与二叉树
- 数据结构——01数据结构绪论
- 数据结构——02算法简介
- 《数据结构(C语言版)》课程学习(15)——实验项目名称:矩阵的转置
- 数据结构--连续内存分配的实现
- n叉树 数据结构
- 链表 数据结构
- Hash表 数据结构
- 数据结构——红黑数学习
- c(数据结构)下树的创建的非递归算法
- 数据结构-时间复杂度大O排名
- 数据结构---顺序表
- 数据结构----顺序栈
- 【数据结构】#数据结构复习提纲
- 数据结构 递归遍历二叉树 C/C++
- 数据结构 C/C++ 冒泡排序
- 数据结构 C/C++ 关键路径
- 数据结构 C/C++ 链栈
- 数据结构 C/C++ 链式队列
- 数据结构 C/C++ 对角矩阵
- 数据结构 C/C++ 对称矩阵
- C/C++ 数据结构 单链表