文章目录
-
- 专栏题解
- 原题题目
- 测试数据
- 闲谈
- 思路
- 代码实现
- 结束语
专栏题解
浙大数据结构C语言 错不在我的全题解
原题题目
测试数据
闲谈
今天晚上遇到了一些事情
导致这道题思考特别缓慢
可能是 最近 春天是不是快到来了
运气比较好hhh 但是这不能阻挡我 在前往编程的路上越走越快
编程的路上注定是孤独的 独行才能走得更快
我也希望大二下的暑假 能够如愿进到好公司实习吧
思路
其实现在心情比较复杂
但是还是能够讲一下大概怎么做的
还是一部分一部分来分析叭
首先我认为最棘手 也是一个比较困惑我的地方
就是对于我们的Indegree究竟怎么存储
因为我发现 Indegree只能放在一个单独的数组里面
而且如果哈希表里面的数字 和 Indegree里面的数字又是分开的
那么我们创建Indegree数组的上线必须还是要比较大的
但是如果里面没有多少元素的话 其实空间还是很浪费的
但是如果在Indegree检查入度的时候
度的数组是单独存放的 然后我们哈希表每个的头结点里面存放数据
就是当前表的那个数据 然后后面跟着的链表
就是这个头结点数据的出度是哪些
哎 现在毕竟心情有点复杂 还是直接给出代码 不懂的地方我会给出注释
代码实现
#include <stdio.h>
#include <stdlib.h>//MAXN是Indegree最大值上限
#define MAXN 100000
#define INF 99999999//这个就是哈希链表的基本结构
typedef struct list
{
int data;struct degree *Next;
} *LNode;//哈希表
typedef struct map
{
int size;LNode Heads;
} *HashMap;//对入度初始化
int Indegree[MAXN] = {
0};//创造哈希表
HashMap CreateHashMap()
{
int HashMapSize,i;HashMap H;scanf("%d",&HashMapSize);H = (HashMap)malloc(sizeof(struct map));H->size = HashMapSize;H->Heads = (LNode)malloc(sizeof(struct list) * H->size);//初始化数据for(i=0;i< H->size;i++){
H->Heads[i].data = -1;H->Heads[i].Next = NULL;} return H;
}//解决入度数组
void FindInDegree(HashMap H)
{
int i,temp,position,number;LNode NewNode;for(i=0;i < H->size;i++){
scanf("%d",&temp);//忽略掉 -1if(temp > 0){
position = temp % H->size;//如果哈希表位置不等于本来属于他的位置while(i != position){
//创造结点就是等于 把这个霸占了原来属于他的位置//霸主的出度给记录下来NewNode = (LNode)malloc(sizeof(struct list));NewNode->data = temp;NewNode->Next = H->Heads[position].Next;H->Heads[position].Next = NewNode;//这个被霸占的数字出度+1Indegree[temp]++;position++;//如果超出当前哈希表最大数 则减去 从头开始if(position >= H->size)position -= H->size;}//找到属于他的位置 赋值即可H->Heads[position].data = temp;}}return;
}void Print(HashMap H)
{
int count = 0,i,j,min,temp,data;//工具人指针 负责确定位置的LNode position;//为了把 -1的数字给排除掉int Visit[1000] = {
0};for(i=0;i < H->size;i++){
if(H->Heads[i].data < 0 && !Visit[i]){
Visit[i] = 1;count++;}}while(count != H->size){
min = INF;for(i=0;i < H->size;i++){
if(!Visit[i]){
if(!Indegree[H->Heads[i].data] && H->Heads[i].data < min){
min = H->Heads[i].data;temp = i;}}}count++;Visit[temp] = 1;//入度-1Indegree[min]--;position = H->Heads[temp].Next;//把访问过的结点后面记录入度的链表访问一遍//并重新计算入度while(position){
Indegree[position->data]--;position = position->Next;}if(count==H->size)printf("%d",min);elseprintf("%d ",min);}return;
}int main()
{
int i;HashMap H;int HashMapSize;H = CreateHashMap();FindInDegree(H);Print(H);return 0;
}
结束语
人还是要做出选择的吧
做自己认为正确的事
怎么现在每个博客下面都是我对生活的哲理
变成哲理大师了
就这样吧 我把生活中的很多东西都寄托在了博客中
和一串串的代码中 也希望和大家一起
能够好好的在大学时光中 度过充实的每一天
