In this assignment, you will write a C program to: 1. Read texts from a file 2.
ID: 3903149 • Letter: I
Question
In this assignment, you will write a C program to: 1. Read texts from a file 2. Build a doubly linked list from the texts; 3. Perform a quick-sort (in the ascending order) for the above linked list. I. General Requirements Your doubly linked list node data structure is defined as in the following: struct mynode [ const char 'text: struct mynode next struct mynode prev: Your program's implementation must include the following features: .Your program must read lexts from a file. The name of the file is given as the first argument. · The program will read one line a time from the file. Each line is put into a node. The nodes form a doubly link list. The program prints the initial, unsorted list and a sorted list. .Your program must be compiled from 3 source files: o main.c (Handles input and output, as well as top-level program logic.) o nodeh (Declares the data structure and function quicksort, which sorts a given doubly linked list with the ascending order), and printlist, which prints a linked list to the screen. o node.c (Defines the function quicksort and printlist, as declared in node.h.) .Your node.h file must contain the proper preprocessor directives to prevent multiple inclusion. The function quicksort must be declared exactly as follows o return value: struct mynode o argument (only one): struct mynode ", which is the head of the given linked list. The function printlist must be declared exactly as follows o return value: void. o argument (only one): struct mynode *, which is the head of the given linked list. .You may use any systems or tools to create and run your program However, your program must run correctly on a departmental Linux computer. .Please follow the guidelines in the programming guideline document. . A sample run may look like this: %./a.out poen, txt original text: ime flies, and memories fade People change and new friendships are made Only the true remain forever at our side Eventually the disappointment and pain will subside Sorted text: Eventually the disappointment and pain will subside Only the true remain forever at our side People change and new friendships are made Time flies, and memories fadeExplanation / Answer
//node.h
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct Node
{
char *text;
struct Node *next;
struct Node *prev;
};
void swap ( char* a, char* b );
struct Node *lastNode(struct Node *root);
struct Node* partition(struct Node *l, struct Node *h);
void _quickSort(struct Node* l, struct Node *h);
void quickSort(struct Node *head);
void printList(struct Node *head);
void push(struct Node** head_ref, char *new_text);
node.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "node1.h"
void swap ( char* a, char* b )
{
char *t = (char *) malloc(sizeof(char)*30);
strcpy(t,a);
strcpy(a,b);
strcpy(b,t);
}
struct Node *lastNode(struct Node *root)
{
while (root && root->next)
root = root->next;
return root;
}
struct Node* partition(struct Node *l, struct Node *h)
{
char *x = (char *) malloc(sizeof(char)*30);
strcpy(x,h->text);
struct Node *j;
struct Node *i = l->prev;
for (j = l; j != h; j = j->next)
{
if (strcmp(j->text,x) <= 0)
{
i = (i == NULL)? l : i->next;
swap(i->text, j->text);
}
}
i = (i == NULL)? l : i->next;
swap(i->text, h->text);
return i;
}
void _quickSort(struct Node* l, struct Node *h)
{
if (h != NULL && l != h && l != h->next)
{
struct Node *p = partition(l, h);
_quickSort(l, p->prev);
_quickSort(p->next, h);
}
}
void quickSort(struct Node *head)
{
struct Node *h = lastNode(head);
_quickSort(head, h);
}
void printList(struct Node *head)
{
while (head)
{
printf("%s ", head->text );
head = head->next;
}
printf(" ");
}
void push(struct Node** head_ref, char *new_text)
{
struct Node* new_node = (struct Node *)malloc(sizeof(struct Node));
new_node->text = (char *)malloc(sizeof(char));
strcpy(new_node->text,new_text);
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL) (*head_ref)->prev = new_node ;
(*head_ref) = new_node;
}
main.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "node1.h"
int main(int argc, char *argv[])
{
struct Node *a = NULL;
FILE *fp;
fp = fopen(argv[1],"r");
if (fp == NULL){
printf("Error opening file ");
return 0;
}
char line[100];
while(fgets((char *)line,100,fp) != NULL){
push(&a, (char *)line);
}
/*
while (fscanf(fp,"%s",word) > 0){
push(&a, (char *)word);
}
*/
printf( "Linked List before sorting ");
printList(a);
quickSort(a);
printf("Linked List after sorting ");
printList(a);
return 0;
}