You cannot submit for this problem because the homework's deadline is due.

Upload file

Just compress your ex7.c, which has #include "linked_list.h" and doesn't has main() function, and upload the compressed zip

Description

Based on the header file below complete the implementation of the linked list.

#ifndef LIST_H
#define LIST_H

typedef struct node {
    char ch;
    struct node *next;
} node_t;

typedef enum {
    false, true
} bool;

node_t *Initialize(char ch);

void PrintList(node_t *head);

void FreeList(node_t **head);

bool IsEmptyList(node_t *head); // Return true if the list is empty, false otherwise

void InsertFirstList(node_t **head, char insert_char); // Prepend a node

void InsertLastList(node_t **head, char insert_char); // Append a node

void DeleteFirstList(node_t **head); // Delete the first element in the list

void DeleteLastList(node_t **head); // Delete the last element in the list

int SizeList(node_t *head); // Return the size of the list

int SearchList(node_t **head, char target); // Count how many times target appears

void SplitList(node_t **head, node_t **tail, int pos); // Split into [0;pos-1] and [pos,end]

void MergeList(node_t **head1, node_t **head2); // Merge two lists

#endif

Hint: test case #1 - #5 don't contain split and merge.

Format

Files

You should submit a tar file containing a c source file ex7.c. It should be like:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linked_list.h"

node_t *Initialize(char ch) {
    node_t *head;
    head = (node_t *) calloc(1, sizeof(node_t));
    if (head == NULL) {
        fprintf(stderr, "Failed to assign memory!\n");
        exit(-1);
    }
    head->next = NULL;
    head->ch = ch;
    return head;
}

void PrintList(node_t *head) {
    node_t *temp = head;
    printf("***Print Linked List***\n");
    while (temp != NULL) {
        printf("%c ", temp->ch);
        temp = temp->next;
    }
    printf("\n****Print Finished****\n\n");
}

void FreeList(node_t **head) {
    node_t *tmp = NULL;
    node_t *pHead = *head;
    while (pHead->next != NULL) {
        tmp = pHead;
        pHead = pHead->next;
        free(tmp);
    }
    free(pHead);
}

bool IsEmptyList(node_t *head) {
    // Add some code
}

void InsertFirstList(node_t **head, char insert_char) {
    // Add some code
}

void InsertLastList(node_t **head, char insert_char) {
    // Add some code
}

void DeleteFirstList(node_t **head) {
    // Add some code
}

void DeleteLastList(node_t **head) {
    // Add some code
}

int SizeList(node_t *head) {
    // Add some code
}

int SearchList(node_t **head, char target) {
    // Add some code
}

void SplitList(node_t **head, node_t **tail, int pos) {
    // Add some code
}

void MergeList(node_t **head1, node_t **head2) {
    // Add some code
}

Test Program

We will test your linked list with a testing program. You don't need to consider too much about it, only for a reference.

//
// Created by liu on 7/7/18.
//

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "linked_list.h"

int main() {
    node_t *list1 = Initialize('1');
    node_t *list2 = NULL;
    char buffer[100];
    PrintList(list1);

    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        printf("%d\n", i);
        scanf("%s", buffer);
        if (strcmp(buffer, "insert") == 0) {
            scanf("%s", buffer);
            if (strcmp(buffer, "first") == 0) {
                scanf("%s", buffer);
                InsertFirstList(&list1, buffer[0]);
            } else if (strcmp(buffer, "last") == 0) {
                scanf("%s", buffer);
                InsertLastList(&list1, buffer[0]);
            } else {
                assert(0);
            }
            PrintList(list1);
        } else if (strcmp(buffer, "delete") == 0) {
            scanf("%s", buffer);
            if (!IsEmptyList(list1)) {
                if (strcmp(buffer, "first") == 0) {
                    DeleteFirstList(&list1);
                } else if (strcmp(buffer, "last") == 0) {
                    DeleteLastList(&list1);
                } else {
                    assert(0);
                }
                PrintList(list1);
            }
        } else if (strcmp(buffer, "size") == 0) {
            printf("%d\n", SizeList(list1));
        } else if (strcmp(buffer, "search") == 0) {
            scanf("%s", buffer);
            printf("%d\n", SearchList(&list1, buffer[0]));
        } else if (strcmp(buffer, "split") == 0) {
            int pos;
            scanf("%d", &pos);
            if (!IsEmptyList(list2)) {
                FreeList(&list2);
                list2 = NULL;
            }
            SplitList(&list1, &list2, pos);
            PrintList(list1);
            PrintList(list2);
        } else if (strcmp(buffer, "merge") == 0) {
            MergeList(&list1, &list2);
            PrintList(list1);
        } else {
            assert(0);
        }
    }
    FreeList(&list1);
    if (!IsEmptyList(list2)) {
        FreeList(&list2);
    }
    return 0;
}

Input

operation number \(n\) on the first line.
an operation on the next \(n\) lines

Output

try the test program yourselves to get the output

Sample 1

Input

5
insert first 8
delete last
insert last k
insert last v
insert first T

Output

***Print Linked List***
1 
****Print Finished****

0
***Print Linked List***
8 1 
****Print Finished****

1
***Print Linked List***
8 
****Print Finished****

2
***Print Linked List***
8 k 
****Print Finished****

3
***Print Linked List***
8 k v 
****Print Finished****

4
***Print Linked List***
T 8 k v 
****Print Finished****

Hint

• Do not forget to judge whether a linked list is already an empty list, or a list with only one element before removing an element.
• Also, for merge function, you should set *head2 to a NULL pointer after merging it with *head1.
• For split function, pay attention to the case when pos==0 and when pos exceed the total length of the input linked list.
  

Limitation

1s, 32MiB for each test case.