Demo entry 6780749

C

   

Submitted by anonymous on Dec 28, 2018 at 15:52
Language: C. Code size: 2.0 kB.

/** 
 * \brief     main function
 * \author    XXX
 * \file      main.c
 * 
 * Using topological sorting and minimum heap 
 * to Solve the problem: Hashing - Hard Version
 *    
 * \date 2018/12/18  XXX: created
 *
 */
#include "Hashing.h"

int *Indegree;	/* Create an array to instore the indegree of each nodes in the graph */
int *Hash;		/* Create an hash table to instore the input data */
int VertexNum;	/* The sum of nodes in the graph */
int main()
{
	int i;
	LGraph G;
	scanf("%d", &VertexNum);

	Indegree = ( int * )malloc( sizeof(int) * VertexNum );
	Hash 	 = ( int * )malloc( sizeof(int) * VertexNum );
	G 		 = CreatGraph( VertexNum );

	/* read in data and initialize indegree */
	for(i = 0; i < VertexNum; i++)
	{
		scanf("%d", &Hash[i]);
		if( Hash[i] < 0 ) Indegree[i] = -1; /* if it is empty, then indegree = -1 */
		else Indegree[i] = 0;				/* otherwise indegree = 0 */
	}

	/* Build the Graph */
	for(i = 0; i < VertexNum; i++)
	{
		if( Hash[i] < 0 ) continue; /* if it's empty, ignore it and move to the next */

		int j;
		int CurrentPosition = i;	
		int HashPosition = Hash[i] % VertexNum;

		/* Calculate the number of collisions, which is also its indegree */
		/* Mind that CurrentPosition may be less than HashPosition. Therefore we need
		   add another VertexNum before we take the remainder of it, which won't do 
		   any affect if CurrentPosition is larger than HashPosition*/
		Indegree[i] = ( CurrentPosition - HashPosition + VertexNum ) % VertexNum;

		/* Each nodes betwenn CurrenPosition and HashPosition affect its final position,
		   which means in the graph, they all should point to it*/
		for(j = 0; j < Indegree[i]; j++)
		{
			Edge E;
			E = ( Edge )malloc( sizeof(struct ENode) );
			E->V1 = i;
			/*Calculate each index of the nodes between CurrentPosition and HashPosition */
			E->V2 = ( HashPosition + j + VertexNum ) % VertexNum; 

			InsertEdge( G, E );
		}
	}
	TopSort( G );
}

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).