记一次离散作业
题目是：用C语言写出一个通用算法，用该算法求出下面哈斯图表示的任务被执行的次序。
然而是一道很简单的题。
（然而我作死的写了两百多行c）
（然而果然用c写东西就像拿小刀砍树能累死人）
##思路
其实核心很简单，输入序偶，建立矩阵，输出。
主要代码量是在输入序偶的时候来建立矩阵。
首先定义一个结构用于存储偏序集和关系矩阵。
typedef struct {
_Element *set; //a normal array
int **matrix;
int size;
} _POSetOrigin; //integer marked the size of array
typedef _POSetOrigin* _POSet; //...together with its pointer
其中_Element是表示集合元素的类型
typedef char* _String; //the type of string
typedef _String _Element;
在这里直接是字符串char *
###输入部分
输入序偶 —> 读取序偶第一个元素（字符串） —> 判断是否存在
—> （存在）跳过
—> （不存在）往偏序集中加入新元素，并往矩阵中加入新行列
加入新元素是为*set重新分配内存，并将size成员加一。
矩阵添加新行即是将二维数组**matrix重新分配新行，每一行重新分配新列。
（于是写了这些就一百多行了）
###查找输出
搜索矩阵 —> 某一列均为0则为最小元
（关系矩阵中未包含传递和自反关系）
（包含了的话输入部分就特么不止这么点了）
取得最小元的index —> 从数组中删除 —> 从矩阵中删除 —> 返回指向最小元的指针 —>输出
直到size=0，结束。
删除元素用是直接创建数组副本，复制其余元素，释放源数组。
##完整代码
/*
哈斯图输出流程蛋疼版(用矩阵)
生命在于折腾.
构建了偏序集和元素类型.
每次添加元素/删除元素时维护矩阵
根据矩阵找极小元.
*/
/***********************************
* Includes *
***********************************/
/***********************************
* Macros *
***********************************/
/***********************************
* Environment *
***********************************/
typedef char* _String; //the type of string
typedef _String _Element;
typedef struct {
_Element *set; //a normal array
int **matrix;
int size;
} _POSetOrigin; //integer marked the size of array
typedef _POSetOrigin* _POSet; //...together with its pointer
/***********************************
* Methods *
***********************************/
_POSet creatPOSet();
//创建一个偏序集
_POSet inputPO(_POSet);
//输入偏序序偶
int addEle(_POSet, _String);
//往偏序集中添加元素
_Element creatEle(_String);
//创建空元素
void deleteEle(_Element);
//删除元素释放内存
int isElExist(_POSet, _Element);
//判断是否是已经存在的元素
int outputEle(_Element);
//输出元素
_Element popEle(_POSet, int);
//将元素从偏序集中移除
_POSet deleteMatrix(_POSet, int);
//将删除的元素从矩阵中移除
int getMinimal(_POSet);
//取得极小元的序号
/***********************************
* Main *
***********************************/
int main(int argc, char const *argv[])
{
_POSet POset = creatPOSet();
while (inputPO(POset));//输入偏序序偶
printf("\n");
while (
outputEle(
popEle(
POset, getMinimal(POset)
)
)
);//取得极小元,将极小元从偏序集中删除,输出极小元.
return 0;
}
/***********************************
* Type methods body *
***********************************/
_POSet creatPOSet() {
_POSet new_set; //创建新的集合指针
new_set = (_POSet)malloc(sizeof(_POSetOrigin)); //分配内存
new_set->set = NULL;
new_set->matrix = NULL;
new_set->size = 0; //初始化
return new_set;
}
_POSet inputPO(_POSet po_set) {
_String tmp_str = (_String)malloc(sizeof(char) * ORIGIN_N); //新字符串
int index1, index2;
scanf("%s", tmp_str); //接受输入
if (strcmp(tmp_str, "END") == 0) { //判断结束标志
return 0;//结束
}
if ((index1 = isElExist(po_set, tmp_str)) == -1) { //不是已经存在的元素
index1 = addEle(po_set, tmp_str); //则创建新元素并加入集合中
}
scanf("%s", tmp_str);
if ((index2 = isElExist(po_set, tmp_str)) == -1) {
index2 = addEle(po_set, tmp_str);
}
po_set->matrix[index1][index2] = 1; //将矩阵中对应位置设为1
return po_set;
}
int addEle(_POSet po_set, _String name) {
_String tmp_str = (_String)malloc(strlen(name)); //新字符串
int index;
int loop;
strcpy(tmp_str, name);
po_set->size++;
po_set->set = (_Element *)realloc(po_set->set, sizeof(_Element)* po_set->size); //将集合容量扩大1
index = po_set->size - 1;
po_set->set[index] = creatEle(tmp_str); //集合新位置指针指向元素
po_set->matrix = (int **)realloc(po_set->matrix, sizeof(int *)* po_set->size); //矩阵新行
if (po_set->size > 1) {
for (loop = 0; loop < po_set->size - 1; loop++) {
po_set->matrix[loop] = (int *)realloc(po_set->matrix[loop], sizeof(int) * po_set->size); //每一行容量扩大1
}
po_set->matrix[po_set->size - 1] = (int *)malloc(sizeof(int) * po_set->size); //新行分配空间
}
else {
po_set->matrix[0] = (int *)malloc(sizeof(int));
}
for (loop = 0; loop < po_set->size; loop++) {
po_set->matrix[index][loop] = 0; //将新行和列初始化为0
po_set->matrix[loop][index] = 0;
}
return index; //返回值为新元素在集合中的位置
}
_Element creatEle(_String str_name) {
_Element new_el = (_Element)malloc(sizeof(char) * (strlen(str_name) + 1)); //创建元素..懒得注释了
strcpy(new_el, str_name);
return new_el;
}
void deleteEle(_Element el) {
free(el);
}
int isElExist(_POSet set, _Element el) {
int loop;
for (loop = 0; loop < set->size; loop++) {
if (strcmp(set->set[loop], el) == 0) {
return loop;
}
}
return -1;
}
int outputEle(_Element el) {
if (el == NULL) {
return 0;
}
printf("%s\n", el);
deleteEle(el);
return 1;
}
_Element popEle(_POSet set, int pos) {
_Element *newArray;
_Element tmp;
int i, j;
if (pos == -1) {
return NULL; //如果取得极小元的返回值是-1(集合为空)直接结束
}
(set->size)--;
newArray = (_Element *)malloc(sizeof(_Element)* (set->size)); //创建新的集合副本,容量是现有-1
for (i = 0, j = 0; i < set->size; ++j, ++i) {
if (j == pos) {
j++;
}
newArray[i] = (set->set)[j]; //现有集合的元素除了要删除的,全部拷贝
}
tmp = (set->set)[pos]; //指针指向被删除的元素
free(set->set);
set->set = newArray; //释放原来的集合,指针指向新的集合副本
deleteMatrix(set, pos); //删除矩阵对应行和列
return tmp; //返回指向 被删除元素的指针
}
_POSet deleteMatrix(_POSet set, int pos) {
int **new_matrix;
int loop, index, i, j;
new_matrix = (int **)malloc(sizeof(int *)* set->size);
for (loop = 0; loop < set->size; ++loop) {
new_matrix[loop] = (int *)malloc(sizeof(int)* set->size); //从矩阵中删除行列,和集合删除元素差不多...
}
for (index = 0, i = 0; index < set->size; ++index, ++i) {
if (i == pos) {
i++;
}
for (loop = 0, j = 0; loop < set->size; ++loop, ++j) {
if (j == pos) {
j++;
}
new_matrix[index][loop] = set->matrix[i][j];
}
}
/*
其实也可以简单地把删除元素对应的行列设置成0
反正添加流程只有一次。。。
*/
for (index = 0; index < set->size + 1; ++index) {
free(set->matrix[index]);
}
free(set->matrix);
set->matrix = new_matrix;
return set;
}
int getMinimal(_POSet set) {
int index;
int loop;
_Bool flag = 1;
if (set->size == 0) {
return -1;
}
for (index = 0; index < set->size; flag = 1, index++) { //矩阵中全是0的那一列是极小元
for (loop = 0; loop < set->size; loop++) {
if (set->matrix[loop][index] == 1) {
flag = 0;
break;
}
}
if (flag) {
return index; //返回极小元在集合中的位置
}
}
}
发布于
tags:
{ math }