# 2020q3 Homework (lab0)
contributed by < `nickchenchj` >
###### tags: `sysprog2020`
###### Note: all codes can be found in my [GitHub repository](https://github.com/nickchenchj/lab0-c).
## Prerequisite
* [I01: lab0](https://hackmd.io/@sysprog/2020-lab0)
## Programming Task
Your task is to modify the code in queue.h and queue.c to fully implement the following functions.
* `q_new`: Create a new, empty queue.
* `q_free`: Free all storage used by a queue.
* `q_insert_head`: Attempt to insert a new element at the head of the queue (LIFO discipline).
* `q_insert_tail`: Attempt to insert a new element at the tail of the queue (FIFO discipline).
* `q_remove_head`: Attempt to remove the element at the head of the queue.
* `q_size`: Compute the number of elements in the queue.
* `q_reverse`: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.
* `q_sort`: Sort elements of queue in ascending order. No effect if q is NULL or empty. In addition, if q has only one element, do nothing.
## Implementation
### queue.h
In order to efficiently `q_size` and `q_insert_tail`, I changed the original queue structure from:
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
} queue_t;
```
to
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
#### `q_new`
* Function:
* Create empty queue.
* Return `NULL` if it could not allocate space.
* code snippet of `q_new`:
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
#### `q_free`
* Function:
* Free all storage used by queue
* code snippet of `q_free`:
```c=
void q_free(queue_t *q)
{
if (!q)
return;
for (list_ele_t *curr = q->head, *next; curr != NULL; curr = next) {
next = curr->next;
free(curr->value);
free(curr);
}
free(q);
}
```
#### `q_insert_head`
* Function:
* Attempt to insert element at head of queue.
* Return `true` if successful.
* Return `false` if `q` is `NULL` or could not allocate space.
* Argument `s` points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
* code snippet of `q_insert_head`:
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc((len + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = newh;
q->size++;
return true;
}
```
#### `q_insert_tail`
* Function:
* Attempt to insert element at tail of queue.
* Return `true` if successful.
* Return `false` if `q` is `NULL` or could not allocate space.
* Argument `s` points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
* code snippet of `q_insert_tail`:
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q)
return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc((len + 1) * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
newh->next = NULL;
if (q->size == 0)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
```
#### `q_remove_head`
* Function:
* Attempt to remove element from head of queue.
* Return `true` if successful.
* Return `false` if `q` is `NULL` or empty.
* If `sp` is non-NULL and an element is removed, copy the removed string to `*sp`
* (up to a maximum of `bufsize-1` characters, plus a `null` terminator.)
* The space used by the list element and the string should be freed.
* code snippet of `q_remove_head`:
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *target = q->head;
q->head = q->head->next;
/* Copies removed string to sp */
if (sp) {
int len = strlen(target->value);
int max_len = len > bufsize - 1 ? bufsize - 1 : len;
strncpy(sp, target->value, max_len);
sp[max_len] = '\0';
}
q->size--;
if (q->size == 0)
q->tail = NULL;
free(target->value);
free(target);
return true;
}
```
#### `q_size`
* Function:
* Return number of elements in queue.
* Return `0` if `q` is `NULL` or empty.
* code snippet of `q_size`:
```c=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
#### `q_reverse`
* Function:
* Reverse elements in queue
* No effect if `q` is `NULL` or empty
* This function should not allocate or free any list elements (e.g., by calling `q_insert_head`, `q_insert_tail`, or `q_remove_head`).
* It should rearrange the existing ones.
* code snippet of `q_reverse`:
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *prev = NULL, *curr = q->tail = q->head;
while (curr) {
list_ele_t *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
q->head = prev;
}
```
#### `q_sort` (selection sort)
* Function:
* Sort elements of queue in ascending order
* No effect if `q` is `NULL` or empty. In addition, if `q` has only one element, do nothing.
* code snippet of `q_sort`:
```c=
/* Selection Sort */
void q_sort(queue_t *q)
{
/* Assures there are more than one element in the queue */
if (!q || !q->head)
return;
for (list_ele_t **front = &q->head; (*front)->next != NULL;
front = &(*front)->next) {
list_ele_t **prev_of_min = front;
/* Finds the previous element of minimum element in the list */
for (list_ele_t **ele = &(*front)->next; *ele != NULL;
ele = &(*ele)->next) {
bool is_smaller = strcmp((*ele)->value, (*prev_of_min)->value) < 0;
if (is_smaller)
prev_of_min = ele;
}
if (prev_of_min != front) {
list_ele_t *min = *prev_of_min;
list_ele_t *next = min->next;
if (min->next == NULL)
q->tail = *front;
/* Adjacent elements */
if ((*front)->next == *prev_of_min) {
min->next = *front;
(*front)->next = next;
} else {
min->next = (*front)->next;
(*front)->next = next;
*prev_of_min = *front;
}
*front = min;
}
}
}
```
* **ERROR**: Not sorted in ascending order
* From this error message, I figured it out that it should be a natural, case insensitive sorting. So I replace `strcmp` with my own string comparing function `strnatcasecmp` (case insensitive string comparisons using a "natural order" algorithm).
* code snippet of `strnatcasecmp`:
```c=
/* Case insensitive string comparisons using a "natural order" algorithm */
int strnatcasecmp(const char *s1, const char *s2)
{
/* Converts the first letters to lowercase */
char c1 = s1[0] | ' ', c2 = s2[0] | ' ';
if (c1 < c2)
return -1;
if (c1 > c2)
return 1;
size_t s1_len = strlen(s1);
size_t s2_len = strlen(s2);
if (s1_len < s2_len)
return -1;
if (s1_len > s2_len)
return 1;
for (int i = 1; i < s1_len; i++) {
c1 = s1[i] | ' ';
c2 = s2[i] | ' ';
if (c1 != c2)
return c1 < c2 ? -1 : 1;
}
return 0;
}
```
* After the changes, however, new error occurred. This time, the system showed that I have reached the time limit, which means that my sorting method is too inefficient. Therefore, I decided to change the sorting method from `selection_sort` to `merge_sort`.
* `q_sort` succeeded in a small number of elements:
* `q_sort` failed in a large number of elements (TLE):
#### Improved version of `q_sort` (merge sort):
###### Reference: [2020q3 Homework1 (lab0) - Sort](https://hackmd.io/@RinHizakura/ByuY_q6AU#Sort) (contributed by [RinHizakura](https://hackmd.io/@RinHizakura))
* function prototypes:
```c=
void q_sort(queue_t *q);
void merge_sort(list_ele_t **head);
void front_back_split(list_ele_t *head,
list_ele_t **front_ref,
list_ele_t **back_ref);
list_ele_t *merge_sorted_list(list_ele_t *a, list_ele_t *b);
void insert_tail(list_ele_t **destRef, list_ele_t **sourceRef);
```
* `q_sort` (merge sort):
```c=
void q_sort(queue_t *q)
{
if (q == NULL || q->head == NULL)
return;
merge_sort(&q->head);
list_ele_t *tmp = q->head;
while (tmp->next != NULL)
tmp = tmp->next;
q->tail = tmp;
}
```
* `merge_sort`:
```c=
void merge_sort(list_ele_t **head)
{
/* Returns if there are less than two elements */
if (*head == NULL || (*head)->next == NULL)
return;
list_ele_t *a;
list_ele_t *b;
front_back_split(*head, &a, &b);
merge_sort(&a); /* Merges the left part of the list starting from a */
merge_sort(&b); /* Merges the right part of the list starting from b */
*head = merge_sorted_list(a, b);
}
```
* `front_back_split`: Split the list in half (`a` and `b`).
```c=
void front_back_split(list_ele_t *head,
list_ele_t **front_ref,
list_ele_t **back_ref)
{
list_ele_t *slow = head;
list_ele_t *fast = head->next;
/* Finds the middle element (slow) in the list */
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
/* Cuts the list in half */
*front_ref = head;
*back_ref = slow->next;
slow->next = NULL;
}
```
* `merge_sorted_list`: Merge two sorted list and return the new `head`.
```c=
list_ele_t *merge_sorted_list(list_ele_t *a, list_ele_t *b)
{
list_ele_t dummy; /* dummy.next points to the first element in the
destination list */
list_ele_t *tail = &dummy;
dummy.next = NULL;
while (1) {
if (a == NULL) {
/* Appends the rest elements in b to the list */
tail->next = b;
break;
} else if (b == NULL) {
/* Appends the rest elements in a to the list */
tail->next = a;
break;
}
/* Inserts an element to the end of the list */
if (strcmp(a->value, b->value) < 0) {
insert_tail(&(tail->next), &a);
} else {
insert_tail(&(tail->next), &b);
}
tail = tail->next;
}
return dummy.next;
}
```
* `insert_tail`: Insert an element to the end of a list.
```c=
void insert_tail(list_ele_t **dest_ref, list_ele_t **source_ref)
{
/* Points to the first element in the source list */
list_ele_t *new_node = *source_ref;
/* Advances the source pointer */
*source_ref = new_node->next;
/* Links new_node to the first element in the destination list */
new_node->next = *dest_ref;
/* Lets new_node become the first element in the destination list */
*dest_ref = new_node;
}
```
* After I changed the sorting method from `selection_sort` to `merge_sort`, it successfully pass the test.
* However, I noticed that `q_sort` sorted well even without using `strnatcasecmp` (case insensitive string comparisons using a “natural order” algorithm), so I was confused what **ascending order** actually meant.
Sign in with Wallet
Connect another wallet