当前位置: 代码迷 >> 综合 >> 深入理解数据结构——划分子集算法
  详细解决方案

深入理解数据结构——划分子集算法

热度:19   发布时间:2024-01-17 05:09:25.0
#include <iostream>
#include <string>using namespace std;typedef int EType;     // 自定义链表的数据元素为整数。//定义队列顺序存储结构
struct Queue
{QType* element;          // 存放结点的数据元素。int front;				//对头节点int rear;				//队尾节点int maxsize;			//队列最大容量
};//构造空队列算法
void CreatQueue(Queue& Q, int MaxQueueSize) {Q.maxsize = MaxQueueSize;Q.element = new QType[Q.maxsize];Q.front = 0;Q.rear = 0;
}//判断队列是否为空
bool IsEmpty(Queue& Q) {if (Q.front == Q.rear) return true;return false;
}//判断队列是否满了front=rear+1;
bool IsFull(Queue& Q) {if (Q.front == (Q.rear + 1) % (Q.maxsize + 1)) return true;return false;
}//返回队头元素的值
bool GetFront(Queue& Q, QType& result) {//将font后面一个位置的队列元素的值取出if (IsEmpty(Q)) return false;result = Q.element[(Q.front + 1) % (Q.maxsize + 1)];return true;
}//返回队尾元素的值
bool GetRear(Queue& Q, QType& result) {//将font后面一个位置的队列元素的值取出if (IsEmpty(Q)) return false;result = Q.element[(Q.rear + 1) % (Q.maxsize + 1)];return true;
}//进队运算
//将一个新的的元素x存储到当前rear所指空间的下一个位置,首先要判断队列是否为满了
bool EnQueue(Queue& Q, QType& x) {if (IsFull(Q)) return false;Q.rear = (Q.rear) % (Q.maxsize + 1); //rear指向空间Q.element[Q.rear] = x;//存入xreturn true;
}//出队运算
//将front所指空间的下一个位置的元素取出,首先要判断队列是否为空
bool OutQueue(Queue& Q, QType& result) {if (IsEmpty(Q)) return false;Q.front = (Q.front + 1) % (Q.maxsize + 1); //front指向空间的下一个位置result = Q.element[Q.front];return true;
}struct QType {int ProjectNumber;
};void Division(int *r[],int set[], int n) {//n个项目划分不冲突的字节,冲突关系再r数组中Queue Q;QType x;int rearkeep;//项目编号int current;int setindex;//子集编号int MaxQueueSize;CreatQueue(Q, MaxQueueSize);for (int i = 1; i < n;i++) {//项目编号进队,结果输出话状态数组x.ProjectNumber = 1;EnQueue(Q, x);set[i] = 0;}setindex = 1;//子集编号while (!IsEmpty(Q)) {rearkeep = Q.rear;//保留当前队尾指针OutQueue(Q, x);//出队当前进入子集的第一个项目编号current = x.ProjectNumber;set[current] = setindex;//第一个进入信自己的项目改变状态数组值while (!(Q.front==rearkeep)) {//当前队列中的所有项目舱室进入当前子集OutQueue(Q, x);//出队下一个项目current = x.ProjectNumber;for (int i = 1; i <= n; i++) {//current与已经入的当前子集的所有项目比较,是否发生冲突if (setindex == set[i] && r[current][i]) {x.ProjectNumber = current;EnQueue(Q, x);  //current重新入队break;}if (i > n) set[current] = setindex;//current进入当前子集}setindex++;}}
}