Create a singly linked list to store a sorted list of ints. The first line in th

ID: 3554514 • Letter: C

Question

Create a singly linked list to store a sorted list of ints. The first line in the input file represents the number of elements to be stored in the singly linked list and the second line contains the values of the singly linked list as ints separated by a single space. Your program must use a structure for every node in the list. The node structure's members should be the value of the node and a pointer to another node. Your program must also use an insertion sort like method to insert the elements into the singly linked list one by one until every element has been added to The singly linked list. The result should be singly linked list where each node points to a node with a value greater than itself (sorted in ascending order). Your program should print out the sorted values in ascending order. Note: that there is no comma after the last value is printed. *HINT* The last structure in the list should point to Null instead of another node Input file (list.txt) 8 8 20 1 45 6 2 30 12 Output: Sorted values 1,2,6,8,12,20,30,45 Read in a square NxN matrix from the file matrix txt where the first line in the file contains the number of rows and the number of columns since the matrix is a square. The subsequent lines contain the matrix values in the format where each line represents a row with every element in the row separated by a single space. The example below represents a 3x3 matrix as input. Your program must:

Explanation / Answer

Question 1

Requires a file data.txt (in the format as mentioned in the program)

eg:

8
8 20 11 23 5 4 1 2

This program writes an output file "output1.txt" with the output (for the input given above):

Sorted Values:
1,2,4,5,8,11,20,23

-------------------------------------------------------------------------------------------------

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

//Structure for a linked list node
typedef struct node{
int data;
struct node *ptr;
} node;

//returns the head after adding new node into the sorted list
node* insert(node* head, int num) {
    node *temp, *prev, *next;
    temp = (node*)malloc(sizeof(node));       //allocating space to a temporary node    its position will be determined below
    temp->data = num;
    temp->ptr = NULL;                       //if inserted at last position the next would point to NULL
    if(!head){                               //in case no value has been added to the list yet
        head=temp;
    } else{
        prev = NULL;
        next = head;
        while(next && next->data<=num){       //will go forward till the data to be added is less than the no's in the list
            prev = next;
            next = next->ptr;
        }
        if(!next){                           //if the node to be inserted is the last node(ie is bigger than the biggest node in the sorted list) . eg inserting 10 in a list 1->2->3->4, temp ie containing data 10 , would be the next node of prev (containing data 4)
            prev->ptr = temp;
        } else{                               //if node to be inserted lies between to values prev and next. eg. inserting 3 in 1->2->4->5 , it lies btw 2(prev) and 4(prev->ptr ie prev's next node)
            if(prev) {
                temp->ptr = prev->ptr;       // next node to temp(node with data 3) is previous's next node (node with data 4)
                prev-> ptr = temp;           // next node to prev(node with data 2) is temp(node with data 3)
            } else {
                temp->ptr = head;
                head = temp;
            }
        }
    }
    return head;
}

//Deletes the whole list
void free_list(node *head) {
    node *prev = head;
    node *cur = head;
    while(cur) {
        prev = cur;
        cur = prev->ptr;
        free(prev);                   //free the space of every node individually
    }
}

int main(){
    int num,n,i;
    node *head, *p;
    head = NULL;
   FILE *file;
   FILE *output;

   //Input File
   file=fopen("data.txt","r");           //opening file in read mode
   fscanf(file,"%d",&n);                   //reading the size of the list

   //Output File
   output=fopen("output1.txt","w");           //opening file in read mode

   //Reading the list no's from the input file into a sorted list
   for(i=0;i<n;i++){
        fscanf(file,"%d",&num);
        if(num) {
            head = insert(head, num);   //insert() returns the head pointer after inserting the new value in the sorted list
        }
    }
    p = head;

   fprintf(output," Sorted Values: ");


   //printing the sorted list
   while(p) {
        fprintf(output,"%d", p->data);
        p = p->ptr;
       if(p)
           fprintf(output,",");       //to ensure a comma is not written for the last output
    }


   //free the list memory
   free_list(head);

   //closing the input file
   fclose(file);
   fclose(output);
    return 0;
}

-------------------------------------------------------------------------------------------------

Question 2

Requires an input file "input.txt" (in the same format as mentioned in the question)

3
1 2 3
4 5 6
7 8 9

This program produces an output file "output2.txt" with output(for the input given above):

Original Matrix:

1 2 3
4 5 6
7 8 9

Transpose Matrix:

1 4 7
2 5 8
3 6 9

-------------------------------------------------------------------------------------------------

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

int main()
{
   int i;
   int j;
   int n;

   /*matrix*/
   FILE *file;
   FILE *output;
   output=fopen("output2.txt", "w");               //opening file output2.txt in write mode
   file=fopen("input.txt", "r");               //opening file input.txt in read mode
   fscanf(file, "%d", &n);                       //reading the size of the matrix
   int** mat=malloc(n*sizeof(int*));            //dynamically allocating the memory for the matrix
   for(i=0;i<n;++i)
       mat[i]=malloc(n*sizeof(int));

   fprintf(output," Original Matrix: ");
   //reading the matrix "mat" from the input file
   for(i = 0; i < n; i++)
          for(j = 0; j < n; j++)
               if (!fscanf(file, "%d", &mat[i][j]))
                   break;

   //printing the matrix read
    for(i = 0; i < n; i++){
       for(j = 0; j < n; j++)
           fprintf(output,"%d ",mat[i][j]);
          fprintf(output," ");
   }


   fprintf(output," Transpose Matrix: ");


   //allocating memory for the transpose matrix "mat_t"
   int** mat_t=malloc(n*sizeof(int*));
   for(i=0;i<n;++i)
       mat_t[i]=malloc(n*sizeof(int));


   //using the original matrix filling the transpose matrix
   for(i = 0; i < n; i++)
       for(j = 0; j < n; j++)
           mat_t[i][j]=mat[j][i];

   //printing the transpose matrix
   for(i = 0; i < n; i++){
       for(j = 0; j < n; j++)
           fprintf(output,"%d ",mat_t[i][j]);
      fprintf(output," ");
   }


   //this will free the memory for each row of matrix
   for (i=0; i<n; ++i) {
       free(mat[i]);
   }

   //free the top level matrix pointer
   free(mat);


   //this will free the memory for each row of transpose matrix
   for (i=0; i<n; ++i) {
       free(mat_t[i]);
   }
   //free the top level transpose matrix pointer
   free(mat_t);

   //closing the input file
   fclose(file);

   //closing the output file
   fclose(output);
}

-----------------------------------------------------------------------------------------

Navigate

Create a singly linked list to store a sorted list of ints. The first line in th

Create a small Family database with one table to include data about members of y

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Create a singly linked list to store a sorted list of ints. The first line in th

Question

Explanation / Answer

Related Questions

Navigate