Learning Outcomes In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter 10) and extend your program design, testing, and debugging skills. You will also learn about the problem of process discovery and implement a simple algorithm for discovering a process model from event data. Progoce Dicoorom

#include #include #include // event node struct node { int event; int freq; struct node* next; struct node* prev; }; // event list struct eventList { struct node* head; struct node* tail; int size; }; //create new event node struct node* createNode(int event) { struct node* ptr = (struct node*) malloc (sizeof(struct node)); ptr->event = event; ptr->freq = 1; ptr->next = NULL; ptr->prev = NULL; return ptr; } // insert new event void eventInsert(struct eventList* L, int event) { struct node* newNode = createNode(event); struct node* ptr = L->head; if(L->head == NULL) { L->head = newNode; L->tail = newNode; } else if(event head->event) { // insert as first node newNode->next = L->head; L->head->prev = newNode; L->head = newNode; } else { while (ptr != NULL && ptr->event next; } if(ptr != NULL) { // insert before ptr newNode->next = ptr; ptr->prev->next = newNode; newNode->prev = ptr->prev; ptr->prev = newNode; } else //insert as last node { newNode->prev = L->tail; L->tail->next = newNode; L->tail = newNode; } } L->size++; } // print events void eventPrint(struct eventList* L) { struct node* ptr = L->head; while(ptr != NULL) { if(ptr->event event, ptr->freq); } else { printf("%d = %d\n", ptr->event, ptr->freq); } ptr = ptr->next; } } // increase freqency of an event void increaseEventFreq(struct eventList* L, int event) { struct node* ptr = L->head; while(ptr != NULL) { if(ptr->event == event) { ptr->freq++; break; } ptr = ptr->next; } } // search for an event int eventSearch(struct eventList* L, int event) { struct node* ptr = L->head; while(ptr != NULL) { if(ptr->event == event) { return 1; } ptr = ptr->next; } return 0; } // trace node struct trace { int* t; int traceLength; int frequency; struct trace* next; struct trace* prev; }; // trace list struct traceList { struct trace* head; struct trace* tail; int size; }; // create trace node struct trace* createTrace(int* trace, int length) { struct trace* ptr = (struct trace*) malloc (sizeof(struct trace)); ptr->t = trace; ptr->traceLength = length; ptr->frequency = 1; ptr->next = NULL; ptr->prev = NULL; return ptr; } // insert new trace void traceInsert(struct traceList* L, int* trace, int length) { struct trace* newNode = createTrace(trace, length); if(L->head == NULL) { L->head = newNode; L->tail = newNode; } else { newNode->prev = L->tail; L->tail->next = newNode; L->tail = newNode; } L->size++; } // print events in a trace void printTrace(int *a, int len) { int i; for(i = 0; i head; while(ptr != NULL) { printTrace(ptr->t, ptr->traceLength); ptr = ptr->next; } } // compare two traces int compareTraces(int* t1, int l1, int* t2, int l2) { if(l1 != l2) { return 0; } int i; for(i = 0; i head; while(ptr != NULL) { if(compareTraces(ptr->t, ptr->traceLength, trace, traceLength) == 1) { return 1; } ptr = ptr->next; } return 0; } // increase frequecy of a trace void increaseTraceFreq(struct traceList* L, int* trace, int traceLength) { struct trace* ptr = L->head; while(ptr != NULL) { if(compareTraces(ptr->t, ptr->traceLength, trace, traceLength) == 1) { ptr->frequency++; break; } ptr = ptr->next; } } // find max int max(int a, int b) { if(a > b) { return a; } return b; } // main function int main() { // create new list to store unique events struct eventList* L; L = (struct eventList*) malloc (sizeof(struct eventList)); L->head = NULL; L->tail = NULL; L->size = 0; // create new list to store all traces struct traceList* T; T = (struct traceList*) malloc (sizeof(struct traceList)); T->head = NULL; T->tail = NULL; T->size = 0; // create new list to store unique traces struct traceList* UT; UT = (struct traceList*) malloc (sizeof(struct traceList)); UT->head = NULL; UT->tail = NULL; UT->size = 0; char ch; int* trace; int maxfreq = 0; int traceLength = 0; int totalEvents = 0; //array to store events in a trace trace = (int*) malloc (sizeof(int)); // read data and fill L, T, and UT while(scanf("%c", &ch) == 1) { if(ch != EOF && ch != '\n') { if(isalpha(ch) > 0) { trace[traceLength] = ch; totalEvents++; if(eventSearch(L, ch) == 0) { // new event add it to L eventInsert(L, ch); } else { // old event, ncrease frequecy increaseEventFreq(L, ch); } traceLength++; trace = (int *) realloc(trace, sizeof(int) * (traceLength + 1)); } } else { if(traceSearch(UT, trace, traceLength) == 0) { //new trace, add it to UT traceInsert(UT, trace, traceLength); } else { // old trace, increase its frequency in UT increaseTraceFreq(UT, trace, traceLength); } traceInsert(T, trace, traceLength); // add all traces to T traceLength = 0; trace = (int*) malloc (sizeof(int)); } } //add last trace if needed if(traceSearch(UT, trace, traceLength) == 0) { //last one is a new trace traceInsert(UT, trace, traceLength); } else { increaseTraceFreq(UT, trace, traceLength); } traceInsert(T, trace, traceLength); //insert last trace //find the most frequent trace struct trace* ptr1 = UT->head; while(ptr1 != NULL) { if(maxfreq frequency) { maxfreq = ptr1->frequency; } ptr1 = ptr1->next; } printf("==STAGE 0============================\n"); printf("Number of distinct events: %d\n", L->size); printf("Number of distinct traces: %d\n", UT->size); printf("Total number of events: %d\n", totalEvents); printf("Total number of traces: %d\n", T->size); printf("Most frequent trace frequency: %d\n", maxfreq); // print all the traces with maxfreq ptr1 = UT->head; while(ptr1 != NULL) { if(ptr1->frequency == maxfreq) { printTrace(ptr1->t, ptr1->traceLength); } ptr1 = ptr1->next; } //print events and frequencies eventPrint(L); return 0; }