Q1. Method to convert sparse matrix to linked list in c ......................... ?

-

 /**

 * Lab assignment 1

 * CSL 210 

 * Deadline: Saturday September 4 by 6am.

 * Submit the c implementation file for this header file

 * Filename should be of format YourEnrollmentNumber_lab1.c (lower case); e.g., bt20cse999.c

 * 

 * Implement all the functions even if the solution is imperfect. If you dont implement all functions,

 * it will result in a compilation error

 *

 * 

 * Compilation error = 0

 * Late submission = 0

 * Presence of uncommented main function in the submission file = 0

 * Cheating/plagiarism = 0

 * */


#define EMPTYNODE 0

#define SIZE_HASH_TABLE 5


struct nodeQ{

    unsigned short row;

    unsigned short column;

    short value;

    struct nodeQ* next;

};


typedef struct nodeQ nodeQ_t;


struct priorityNodeQ{

    unsigned short value;

    unsigned short priority;

    struct priorityNodeQ* next;

};


typedef struct priorityNodeQ priorityNodeQ_t;


priorityNodeQ_t* g_priorityHashTable[SIZE_HASH_TABLE] = {0};


/**

 * Method to convert sparse matrix to linked list

 * Input -

 *      matrix: is a 2d array with values pre-populated 

 *      rows: number of rows in a 2d array

 *      columns: number of columns in a 2d array

 * Output - 

 *      Linked list that represents the input matrix

 *      The memory for ouput linked list must be allocated inside the function

 *      The caller will take care of freeing the memory

 * */

nodeQ_t* convertSparseMatrixToLinkedList(unsigned short** matrix, unsigned short rows, unsigned short columns);


/**

 * Multiply two sparse matrices that are represented as linked list

 * Input -

 *      matrix_llist_1: linked list output using convertSparseMatrixToLinkedList function

 *      matrix_llist_2: linked list output using convertSparseMatrixToLinkedList function

 * Output - 

 *      Linked list that represents the input matrix

 *      The memory for ouput linked list must be allocated inside the function

 *      The caller will take care of freeing the memory

 * */

nodeQ_t* multiplySparseMatricesLinkedLists(nodeQ_t* matrix_llist_1, nodeQ_t* matrix_llist_2);


/**

 * DO NOT DELETE OR REIMPLEMENT THIS FUNCTION

 * */

unsigned short hashFuncLab1(unsigned short key){

    return key % SIZE_HASH_TABLE;

}


/**

 * Insert elements in g_priorityHashTable (defined above)

 * The function must use the implementation of hashFuncLab1 defined above

 * The input hashFuncLab1 is the "value" member of priorityNodeQ_t

 * In case of collision, separate chaining must be used.

 * Every chain (linked list) in the hash table must be a priority queue

 * The priority value will be in the range 1 - 5, 1 being the highest. 

 * The head node in the chain must be the node with highest priority and tail with the lowest.

 * Input -

 *      item will be instatiated in memory before passing it in

 * */

void insertPriorityHashTable(priorityNodeQ_t* item);


/**

 * Function to remove/dequeue the element from g_priorityHashTable with the highest priority for the input key

 * The element with highest priority is the head node in the chain

 * Output - 

 *      The element with the highest priority (1 on the scale of 1-5) for the input key must be dequeued and returned

 * */

priorityNodeQ_t* dequeueFromPriorityHashTable(unsigned short key);


                                          ANSWER

#include <stdio.h>
#include <stdlib.h>
#include"csl210_lab1.h"


nodeQ_t *convertSparseMatrixToLinkedList(unsigned short **matrix, unsigned short rows, unsigned short columns)
{
  nodeQ_t *head;
  head = (nodeQ_t *)malloc(sizeof(nodeQ_t));
  head->value = 0;
  head->row = rows;
  head->column = columns;
  head->next = EMPTYNODE;
  nodeQ_t *tem = head->next;
  for (int j = 0; j < rows; j++)
  {
    for (int i = 0; i < columns; i++)
    {
      if (matrix[j][i] != 0)
      {
        if (tem == EMPTYNODE)
        {
         // printf("a\t");
          tem = (nodeQ_t *)malloc(sizeof(nodeQ_t));
          tem->row = j;
          tem->column = i;
          tem->value = matrix[j][i];
          tem->next = EMPTYNODE;
          head->next = tem;
        }
        else
        {
          while (tem->next != EMPTYNODE)
          {
           // printf("a\t");
            tem = tem->next;
          }
          nodeQ_t *new_node = EMPTYNODE;
          new_node = (nodeQ_t *)malloc(sizeof(nodeQ_t));
          new_node->row = j;
          new_node->column = i;
          new_node->value = matrix[j][i];
          new_node->next = EMPTYNODE;
          tem->next = new_node;
        }
      }
    }
  }

  return head;
}

nodeQ_t *multiplySparseMatricesLinkedLists(nodeQ_t *matrix_llist_1, nodeQ_t *matrix_llist_2)
{
  nodeQ_t *temp = matrix_llist_1;
  nodeQ_t *temp2 = matrix_llist_2;

  if (temp->column != temp2->row)
    return 0;

  nodeQ_t *head;
  head = (nodeQ_t *)malloc(sizeof(nodeQ_t));
  head->row = temp->row;
  head->value = 0;
  head->column = temp2->column;
  head->next = EMPTYNODE;
  nodeQ_t *tem = head->next;
  temp2 = matrix_llist_2->next;
  temp = matrix_llist_1->next;

  while (1)
  {
    temp2 = matrix_llist_2;
    while (1)
    {
      if (temp->column == temp2->row)
      {
        int flag1 = 0, flag3 = 0;
        temp = head->next;
        if (temp != EMPTYNODE)
        {
          while (1)
          {
            if (temp->row == temp->row && temp->column == temp2->column)
            {
              flag1 = 1;
              temp->value += (temp->value) * (temp2->value);
            }
            if (temp->next == EMPTYNODE)
            {
              break;
            }
            temp = temp->next;
          }
        }
        if (flag1 == 0)
        {
          if (temp == EMPTYNODE)
          {
            temp = (nodeQ_t *)malloc(sizeof(nodeQ_t));
            temp->row = temp->row;
            temp->column = temp2->column;
            temp->value = (temp->value) * (temp2->value);
            temp->next = EMPTYNODE;
            head->next = temp;
          }
          else
          {
            nodeQ_t *new_node = EMPTYNODE;
            new_node = (nodeQ_t *)malloc(sizeof(nodeQ_t));
            new_node->row = temp->row;
            new_node->column = temp2->column;
            new_node->value = temp->value * temp2->value;
            new_node->next = EMPTYNODE;
            temp->next = new_node;
          }
        }
      }
      if (temp2->next == EMPTYNODE)
      {
        break;
      }
      temp2 = temp2->next;
    }
    if (temp->next == EMPTYNODE)
    {
      break;
    }
    temp = temp->next;
  }
  return head;
}

//---------------------------------------------------------------------------------------

void insertPriorityHashTable(priorityNodeQ_t *item)
{
  unsigned short hashKey = hashFuncLab1(item->value);
  priorityNodeQ_t *temp = g_priorityHashTable[hashKey];
  priorityNodeQ_t *temp2 = EMPTYNODE;

  if (EMPTYNODE == g_priorityHashTable[hashKey])
  {
    g_priorityHashTable[hashKey] = item;
  }
  else
  {
    while (temp != EMPTYNODE && temp->priority <= item->priority)
    {
      temp2 = temp;
      temp = temp->next;
    }
    if (temp == g_priorityHashTable[hashKey])
    {
      item->next = g_priorityHashTable[hashKey];
      g_priorityHashTable[hashKey] = item;
    }
    else
    {
      item->next = temp2->next;
      temp2->next = item;
    }
  }
}

priorityNodeQ_t *dequeueFromPriorityHashTable(unsigned short key)
{
  unsigned short hashKey = hashFuncLab1(key);
  if (g_priorityHashTable[hashKey] == EMPTYNODE)
    return 0;
  priorityNodeQ_t *temp1 = g_priorityHashTable[hashKey];
  g_priorityHashTable[hashKey] = g_priorityHashTable[hashKey]->next;
  return temp1;
}

   //************************** MAIN FUNCTION******************************//

void printTable(){
for(int i=0;i<SIZE_HASH_TABLE;i++){
priorityNodeQ_t* temp = g_priorityHashTable[i];
printf("[%d] -> ",i);
while(temp){
printf("(v:%d,p:%d) -> ",temp->value,temp->priority);
temp = temp->next;
}
printf("NULL\n");
}
}

void printlist(nodeQ_t *head)
{
  nodeQ_t *temp = head;
  while (temp != EMPTYNODE)
  {
    printf("v:%d\tr:%d\tc:%d\t\n", temp->value, temp->row, temp->column);
    temp = temp->next;
  }
}

int main(){
unsigned short row=0,column=0;
// arr1 m1 3x3
row=3; column=3;
unsigned short ** arr1 = (unsigned short **)malloc(row * sizeof(unsigned short));

for (int r = 0; r < row; r++){
arr1[r] = (unsigned short *)malloc(column * sizeof(unsigned short));
}

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
arr1[i][j]=0;
}
}

arr1[0][1]=1;
arr1[1][0]=2;
arr1[1][2]=2;
arr1[2][1]=1;
arr1[2][2]=3;

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
printf("%d ",arr1[i][j]);
}
printf("\n");
}

nodeQ_t* m1=convertSparseMatrixToLinkedList(arr1,row,column);
printlist(m1);
printf("\n");

//------------
// arr2 m2 3x3

row=3; column=3;
unsigned short ** arr2 = (unsigned short **)malloc(row * sizeof(unsigned short));

for (int r = 0; r < row; r++){
arr2[r] = (unsigned short *)malloc(column * sizeof(unsigned short));
}

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
arr2[i][j]=0;
}
}

arr2[0][0]=2;
arr2[1][1]=2;
arr2[2][0]=2;
arr2[2][2]=2;

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
printf("%d ",arr2[i][j]);
}
printf("\n");
}

nodeQ_t* m2=convertSparseMatrixToLinkedList(arr2,row,column);
printlist(m2);
printf("\n");
//------------
// arr3 m3 3x1

row=3; column=1;
unsigned short ** arr3 = (unsigned short **)malloc(row * sizeof(unsigned short));

for (int r = 0; r < row; r++){
arr3[r] = (unsigned short *)malloc(column * sizeof(unsigned short));
}

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
arr3[i][j]=0;
}
}

arr3[0][0]=1;
arr3[2][0]=3;

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
printf("%d ",arr3[i][j]);
}
printf("\n");
}

nodeQ_t* m3=convertSparseMatrixToLinkedList(arr3,row,column);
printlist(m3);
printf("\n");

//------------
// arr4 m4 1x3

row=1; column=3;
unsigned short ** arr4 = (unsigned short **)malloc(row * sizeof(unsigned short));

for (int r = 0; r < row; r++){
arr4[r] = (unsigned short *)malloc(column * sizeof(unsigned short));
}

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
arr4[i][j]=0;
}
}

arr4[0][1]=2;
arr4[0][2]=1;

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
printf("%d ",arr4[i][j]);
}
printf("\n");
}

nodeQ_t* m4=convertSparseMatrixToLinkedList(arr4,row,column);
printlist(m4);
printf("\n");

//------------
// arr5 m5 3x4

row=3; column=4;
unsigned short ** arr5 = (unsigned short **)malloc(row * sizeof(unsigned short));

for (int r = 0; r < row; r++){
arr5[r] = (unsigned short *)malloc(column * sizeof(unsigned short));
}

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
arr5[i][j]=0;
}
}

arr5[0][3]=1;
arr5[1][0]=2;
arr5[1][2]=4;
arr5[2][3]=3;

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
printf("%d ",arr5[i][j]);
}
printf("\n");
}

nodeQ_t* m5=convertSparseMatrixToLinkedList(arr5,row,column);
printlist(m5);
printf("\n");

//------------
// arr6 m6 4x3

row=4; column=3;
unsigned short ** arr6 = (unsigned short **)malloc(row * sizeof(unsigned short));

for (int r = 0; r < row; r++){
arr6[r] = (unsigned short *)malloc(column * sizeof(unsigned short));
}

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
arr6[i][j]=0;
}
}

arr6[0][1]=4;
arr6[1][0]=1;
arr6[1][2]=5;
arr6[2][2]=6;
arr6[3][0]=1;

for(int i=0;i<row;i++){
for(int j=0;j<column;j++){
printf("%d ",arr6[i][j]);
}
printf("\n");
}

nodeQ_t* m6=convertSparseMatrixToLinkedList(arr6,row,column);
printlist(m6);
printf("\n");
//------------
// mul1=m1 x m2 [3x3:3x3]==3x3
nodeQ_t* mul1 = multiplySparseMatricesLinkedLists(m1,m2);
printlist(mul1);
printf("\n");
// mul2=m2 x m3 [3x3:3x1]==3x1
nodeQ_t* mul2 = multiplySparseMatricesLinkedLists(m2,m3);
printlist(mul2);
printf("\n");
// mul3=m3 x m4 [3x1:1x3]==3x3
nodeQ_t* mul3 = multiplySparseMatricesLinkedLists(m3,m4);
printlist(mul3);
printf("\n");
// mul4=m4 x m3 [1x3:3x1]==1x1
nodeQ_t* mul4 = multiplySparseMatricesLinkedLists(m4,m3);
printlist(mul4);
printf("\n");
// mul5=m1 x m5 [3x3:3x4]==3x4
nodeQ_t* mul5 = multiplySparseMatricesLinkedLists(m1,m5);
printlist(mul5);
printf("\n");
// mul6=m5 x m6 [3x4:4x3]==3x3
nodeQ_t* mul6 = multiplySparseMatricesLinkedLists(m5,m6);
printlist(mul6);
printf("\n");
// mul7=m6 x m5 [4x3:3x4]==4x4
nodeQ_t* mul7 = multiplySparseMatricesLinkedLists(m6,m5);
printlist(mul7);
printf("\n");

// [0] v=0 p=2
priorityNodeQ_t* temp=NULL;
    temp = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp->next=EMPTYNODE;
    temp->value=0;
    temp->priority=2;
insertPriorityHashTable(temp);
printTable();
printf("\n");
// [0] v=10 p=5
priorityNodeQ_t* temp1=NULL;
    temp1 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp1->next=EMPTYNODE;
    temp1->value=10;
    temp1->priority=5;
insertPriorityHashTable(temp1);
printTable();
printf("\n");
// [0] v=5 p=1
priorityNodeQ_t* temp2=NULL;
    temp2 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp2->next=EMPTYNODE;
    temp2->value=5;
    temp2->priority=1;
insertPriorityHashTable(temp2);
printTable();
printf("\n");
// [0] v=15 p=5
priorityNodeQ_t* temp3=NULL;
    temp3 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp3->next=EMPTYNODE;
    temp3->value=15;
    temp3->priority=5;
insertPriorityHashTable(temp3);
printTable();
printf("\n");
// [0] v=105 p=5
priorityNodeQ_t* temp4=NULL;
    temp4 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp4->next=EMPTYNODE;
    temp4->value=105;
    temp4->priority=5;
insertPriorityHashTable(temp4);
printTable();
printf("\n");


// [1] v=1 p=1
priorityNodeQ_t* temp5=NULL;
    temp5 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp5->next=EMPTYNODE;
    temp5->value=1;
    temp5->priority=1;
insertPriorityHashTable(temp5);
printTable();
printf("\n");
// [1] v=11 p=2
priorityNodeQ_t* temp6=NULL;
    temp6 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp6->next=EMPTYNODE;
    temp6->value=11;
    temp6->priority=2;
insertPriorityHashTable(temp6);
printTable();
printf("\n");
// [1] v=21 p=1
priorityNodeQ_t* temp7=NULL;
    temp7 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp7->next=EMPTYNODE;
    temp7->value=21;
    temp7->priority=1;
insertPriorityHashTable(temp7);
printTable();
printf("\n");
// [1] v=31 p=4
priorityNodeQ_t* temp8=NULL;
    temp8 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp8->next=EMPTYNODE;
    temp8->value=31;
    temp8->priority=4;
insertPriorityHashTable(temp8);
printTable();
printf("\n");
// [1] v=6 p=3
priorityNodeQ_t* temp9=NULL;
    temp9 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp9->next=EMPTYNODE;
    temp9->value=6;
    temp9->priority=3;
insertPriorityHashTable(temp9);
printTable();
printf("\n");
// [1] v=16 p=1
priorityNodeQ_t* temp0=NULL;
    temp0 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp0->next=EMPTYNODE;
    temp0->value=16;
    temp0->priority=1;
insertPriorityHashTable(temp0);
printTable();
printf("\n");


// [3] v=3 p=3
priorityNodeQ_t* temp10=NULL;
    temp10 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp10->next=EMPTYNODE;
    temp10->value=3;
    temp10->priority=3;
insertPriorityHashTable(temp10);
printTable();
printf("\n");
// [3] v=8 p=5
priorityNodeQ_t* temp20=NULL;
    temp20 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp20->next=EMPTYNODE;
    temp20->value=8;
    temp20->priority=5;
insertPriorityHashTable(temp20);
printTable();
printf("\n");
// [3] v=13 p=3
priorityNodeQ_t* temp30=NULL;
    temp30 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp30->next=EMPTYNODE;
    temp30->value=13;
    temp30->priority=3;
insertPriorityHashTable(temp30);
printTable();
printf("\n");
// [3] v=18 p=3
priorityNodeQ_t* temp40=NULL;
    temp40 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp40->next=EMPTYNODE;
    temp40->value=18;
    temp40->priority=3;
insertPriorityHashTable(temp40);
printTable();
printf("\n");
// [3] v=23 p=2
priorityNodeQ_t* temp50=NULL;
    temp50 = (priorityNodeQ_t*)malloc(sizeof(priorityNodeQ_t));
    temp50->next=EMPTYNODE;
    temp50->value=23;
    temp50->priority=2;
insertPriorityHashTable(temp50);
printTable();
printf("\n");

priorityNodeQ_t* test;
// deques [0]
test = dequeueFromPriorityHashTable(0);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");
// deques [0]
test = dequeueFromPriorityHashTable(0);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");

// deques [0]
test = dequeueFromPriorityHashTable(0);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");
// deques [0]
test = dequeueFromPriorityHashTable(0);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");
// deques [0]
test = dequeueFromPriorityHashTable(0);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");

// deques [0]
test = dequeueFromPriorityHashTable(0);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");

// deques [1]
test = dequeueFromPriorityHashTable(1);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");

// deques [3]
test = dequeueFromPriorityHashTable(3);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");

// deques [1]
test = dequeueFromPriorityHashTable(1);
if(test){
printf("%d\n",test->value);
}else{
printf("%d\n",test);
}
printTable();
printf("\n");
}

Comments

Post a Comment

Popular posts from this blog

Basic Data types | HackerRank Solution...

-
                Basic data types Solution Input Format Input consists of the following space-separated values:  int ,  long ,  char ,  float , and  double , respectively. Output Format Print each element on a new line in the same order it was received as input. Note that the floating-point value should be correct up to 3 decimal places and the double to 9 decimal places. #include   < iostream > #include   < cstdio > #include   < iomanip > using   namespace  std; int  main() {      // Complete the code.      int  a;      long   int  ld;      char  ch;      float  f;      double  lf;     cin >> a;     cin >> ld;     cin...
Read more

There are three people sitting in a room - Alice, Bob, and Charlie. They need to decide on the temperature to set on the air conditioner. Everyone has a demand each:

-
  Problem There are three people sitting in a room - Alice, Bob, and Charlie. They need to decide on the temperature to set on the air conditioner. Everyone has a demand each: Alice wants the temperature to be at least  A A  degrees. Bob wants the temperature to be at most  B B  degrees. Charlie wants the temperature to be at least  C C  degrees. Can they all agree on some temperature, or not? Input Format The first line of input will contain a single integer  T T , denoting the number of test cases. Each test case consists of a single line which contains three integers -  A, B, C A , B , C . Output Format For each test case, output on a new line, "Yes" or "No". "Yes", if they can decide on some temperature which fits all their demands. Or "No", if no temperature fits all their demands. You may print each character of the string in either uppercase or lowercase (for example, the strings  NO ,  nO ,  No , and  no  will...
Read more

Chef has recently introduced a feature which allows you to open any user’s submitted code (not just your own), and ask an AI to explain that code in English. For example, you can go to https://www.codechef.com/viewsolution/70530506 and click on "Analyse This Code".

-
  Problem Chef has recently introduced a  feature  which allows you to open any user’s submitted code (not just your own), and ask an AI to explain that code in English. For example, you can go to  https://www.codechef.com/viewsolution/70530506  and click on "Analyse This Code". But there is a restriction that the feature works only on codes which are at most  1000 1000  characters long. Given the number of characters,  C C , in a particular code, output whether the feature is available on this code or not. Input Format The only line of input will contain a single integer  C C , denoting the number of characters in the code. Output Format Output a single line which contains either "Yes", if the feature is available on this code, or "No", if not. You may print each character of the string in either uppercase or lowercase (for example, the strings  NO ,  nO ,  No , and  no  will all be treated as identical). Constraints...
Read more