Demo entry 6340034

233

   

Submitted by anonymous on Dec 27, 2016 at 09:11
Language: C. Code size: 8.7 kB.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10007	//Size of hash table
typedef struct Entry *PtrToEntry;
typedef struct ListNode *PtrToNode;
typedef PtrToNode Position;
typedef PtrToNode *HashTable;

/*Struct to store one entry of record, each of which corresponds to an entry of record*/
struct Entry
{
	char Plate[8];			//plate number
	int Time_Sec;			//time of the record (in seconds)
	int Status;				//in or out of the compus: 1 for in, 0 for out
	int Valid;				//validity of the record: 1 for valid, 0 for invalid
};
/*List node of the seperate chaining hash table, each of which corresponds to a certain car*/
struct ListNode
{
	char Plate[8];			//plate number
	int Time_Sec;			//nearest time of coming in (in seconds)
	int Status;				//most recent status: 1 for in, 0 for out
	PtrToEntry PrevEntry;	//most recent record of coming in
	int ParkTime;			//tatol park time of the car
	PtrToNode Next;			//pointer to the next list node
};
/*Global variables*/
int N, K;					//number of records, number of queries
int MaxParkTime = 0;		//maximum park time		
char *MaxPlates[10000];		//string arrays of the plate numbers of the cars which parked for the longest time
int PlateCount = 0;			//number of cars which parked for the longest time

/*Function to read in the records and queries*/
/*Both a struct array and a struct pointer array is allcocated. 
  However after connecting the latter to the former, the array name of the struct array is discarded*/
void ReadEntry(PtrToEntry **PtrToRecord, int **PtrToQuery)
{
	int i;
	int h, m, s;//hour, minute, second of a time point
	scanf("%d%d", &N, &K);
	//Allocate space for Record, storing an array of pointers to struct Entry
	*PtrToRecord = (PtrToEntry *)malloc(N*sizeof(PtrToEntry));
	//Allocate space for EntryArray, storing an array of struct Entry
	PtrToEntry EntryArray = (PtrToEntry)malloc(N*sizeof(struct Entry));
	for(i = 0; i < N; i++)//Loop to read in records
	{
		char status[4];
		scanf("%s", EntryArray[i].Plate);
		scanf("%d:%d:%d", &h, &m, &s);
		scanf("%s", status);
		EntryArray[i].Time_Sec = 3600*h + 60*m + s;//Store time in the format of seconds
		EntryArray[i].Status = (status[0] == 'i'? 1: 0);
		EntryArray[i].Valid = 0;//Valid initialized as 0
		(*PtrToRecord)[i] = EntryArray + i;//Connect the struct pointer array and the struct array
	}
	*PtrToQuery = (int *)malloc(K*sizeof(int));//Allocate time for Query
	for(i = 0; i < K; i++)//Loop to read in queries
	{
		scanf("%d:%d:%d", &h, &m, &s);
		(*PtrToQuery)[i] = 3600*h + 60*m + s;
	}
}
/*Compare function for qsort, which compares two records in time order*/
/*The record with earlier time should appear, relatively, in the front of the array after sorting*/
int CompareEntry(const void *p1, const void *p2)
{
	const PtrToEntry *a1 = (const PtrToEntry *)p1;
	const PtrToEntry *a2 = (const PtrToEntry *)p2;
	if((*a1)->Time_Sec < (*a2)->Time_Sec)
		return -1;
	else if((*a1)->Time_Sec > (*a2)->Time_Sec)
		return 1;
	else
		return 0;
}
/*Function to initialize hash table: 
  allocate space for an array of pointers, and initialize all pointers to NULL*/
HashTable InitializeTable(void)
{
	HashTable H = (HashTable)malloc(TABLE_SIZE*sizeof(Position));
	int i;
	for(i = 0; i < TABLE_SIZE; i++)
		H[i] = NULL;
	return H;
}

/*Hash function: converts strings to integers ranging from 0 to TABLE_SIZE-1*/
unsigned int Hash(char *Key)
{
	unsigned int Index = 0;
	while(*Key)//All characters are evaluated
		Index = (Index << 4) + *Key++;//implemented via bit-wise shift
	return Index % TABLE_SIZE;
}

/*Function to find the list node in the hash table corresponding to the given Key*/
/*If the node is found, return a pointer to the node; Else return NULL*/
Position Find(char *Key, HashTable H)
{
	Position P = H[Hash(Key)];
	while(P && strcmp(P->Plate, Key))//Traverse down the list of nodes that hash to the same value
		P = P->Next;
	return P;
}

/*CheckEntry & UpdateTable: Function to check the validity of each entry,
  meanwhile compute the park time of each car and hence obtain the maximum park time*/
void UpdateTable(PtrToEntry ThisEntry, HashTable H)
{
	Position P = Find(ThisEntry->Plate, H);
	if(P)//there is a node in the hash table corresponding to this car
	{
		if(ThisEntry->Status)//the car comes in
		{
			P->Time_Sec = ThisEntry->Time_Sec;//update the nearest time of coming in
            P->Status = 1;//set most recent status as <in>
            P->PrevEntry = ThisEntry;//update most recent record of coming in
		}
		else if(P->Status)//the car gets out
		{
			/*Update park time and maximum park time*/
			P->ParkTime += ThisEntry->Time_Sec - P->Time_Sec;
			if(P->ParkTime > MaxParkTime)
			{
				MaxParkTime = P->ParkTime;
				MaxPlates[0] = ThisEntry->Plate;
				PlateCount = 1;
			}
			else if(P->ParkTime == MaxParkTime)
				MaxPlates[PlateCount++] = ThisEntry->Plate;
			P->Status = 0;//set most recent status as <out>
			P->PrevEntry->Valid = 1;//mark most recent <in> record as valid
			ThisEntry->Valid = 1;//mark this record as valid
		}
	}
	else if(ThisEntry->Status)
	//no corresponding node in the hash table and the car comes into the campus: add new node in hash table
	{
		Position NewNode = (Position)malloc(sizeof(struct ListNode));//Allocate a new node in hash table
		unsigned index = Hash(ThisEntry->Plate);//compute the hash value of the car
		/*insert the new node*/
		NewNode->Next = H[index];
		H[index] = NewNode;
		/*fill in the data for new node*/
		strcpy(NewNode->Plate, ThisEntry->Plate);
		NewNode->Time_Sec = ThisEntry->Time_Sec;
		NewNode->Status = 1;
		NewNode->PrevEntry = ThisEntry;//most recent <in> record is ThisEntry
        NewNode->ParkTime = 0;//total park time initianlized as 0
	}
}
void CheckEntry(PtrToEntry *Record, HashTable H)//Iterate through all the records
{
	int i;
	for(i = 0; i < N; i++)
		UpdateTable(Record[i], H);
}
/*Function to count and output the car amount at certain time points*/
void CountCars(PtrToEntry *Record, int *Query)
{
    int i = 0, j = 0, count = 0;//i traverses throngh array Record, j array Query
    while(i < N && j < K)//both i and j shouldn't be out of range
    {
        if(Record[i]->Valid)//if this record is valid
        {
            while(j < K && Record[i]->Time_Sec > Query[j])
			//output the car amount at the time points earlier than this record
            {
                printf("%d\n", count);
                j++;
            }
            /*Count this record in*/
            if(Record[i]->Status) count++;
            else count--;
        }
        i++;
    }
    while(j < K)//output the car amount at the time points later than all the records
    {
        printf("%d\n", count);
        j++;
    }
}

/*A simple function to convert the time in seconds back to 24-hour format*/
void ToString(char *TimeStr, int Time)
{
	int n;
	n = Time/3600;
	TimeStr[0] = n/10 + 48; TimeStr[1] = n%10 + 48; TimeStr[2] = ':';
	Time %= 3600; n = Time/60;
	TimeStr[3] = n/10 + 48; TimeStr[4] = n%10 + 48; TimeStr[5] = ':';
	Time %= 60; n = Time;
	TimeStr[6] = n/10 + 48; TimeStr[7] = n%10 + 48; TimeStr[8] = 0;
}
/*Another compare function for qsort, which compares two strings of equal length alphabetically*/
int ComparePlate(const void *p1, const void *p2)
{
    const char **a1 = (const char **)p1;
    const char **a2 = (const char **)p2;
    int difference = strcmp(*a1, *a2);
    if(difference < 0)
        return -1;
    else if(difference > 0)
        return 1;
    else
        return 0;
}
/*Function to sort the MaxPlates array, convert MaxParkTime to 24-hour format and output*/
void PrintResult(void)
{
    qsort(MaxPlates, PlateCount, sizeof(char *), ComparePlate);//Sort string array
    int i;
    for(i = 0; i < PlateCount; i++)
        printf("%s ",MaxPlates[i]);
    char Time[9];
    ToString(Time, MaxParkTime);
	printf("%s\n", Time);
}
int main(void)
{
	PtrToEntry *Record;
	int *Query;
	ReadEntry(&Record, &Query);//read in records and queries
	qsort(Record, N, sizeof(PtrToEntry), CompareEntry);//sort records in time order
	HashTable H = InitializeTable();//initialize hash table
	CheckEntry(Record, H);//check the validity of all the records, and compute the total park time of each car
	CountCars(Record, Query);//count and output the amount of cars at certain time points pinpointed by queries
    PrintResult();//output the plate numbers of the cars which parked for the longest time as well as the time they parked
    return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).