Inventory with Linked List

Lab C Advanced 30 points

Keep an inventory as a linked list sorted by item name. Commands: add NAME QTY (adds to an existing item or inserts a new one in order), sell NAME QTY (print short if not enough), list (print NAME QTY lines, or empty).

Input

n, then n commands.

Output

Messages and listings.

Example

Input

7
add pen 10
add apple 5
add zip 1
sell pen 4
sell apple 9
add pen 1
list

Output

short
apple 5
pen 7
zip 1

Sample input available Sample output available

Editor

Hints

Keep the list sorted on insert so list needs no sorting.

Reuse find() for both add and sell.

Solution explanation

A sorted linked list keeps data ordered without ever moving existing items.

Show solution

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

struct Item {
    char name[30];
    int qty;
    struct Item *next;
};

struct Item *head = NULL;

struct Item *find(char *name) {
    for (struct Item *p = head; p != NULL; p = p->next) {
        if (strcmp(p->name, name) == 0) return p;
    }
    return NULL;
}

void add(char *name, int qty) {
    struct Item *it = find(name);
    if (it != NULL) {
        it->qty += qty;
        return;
    }
    struct Item *node = malloc(sizeof(struct Item));
    strcpy(node->name, name);
    node->qty = qty;
    if (head == NULL || strcmp(name, head->name) < 0) {
        node->next = head;
        head = node;
        return;
    }
    struct Item *p = head;
    while (p->next != NULL && strcmp(p->next->name, name) < 0) p = p->next;
    node->next = p->next;
    p->next = node;
}

int main() {
    int n, qty;
    char cmd[10], name[30];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", cmd);
        if (strcmp(cmd, "list") == 0) {
            if (head == NULL) printf("empty\n");
            for (struct Item *p = head; p != NULL; p = p->next) printf("%s %d\n", p->name, p->qty);
            continue;
        }
        scanf("%s %d", name, &qty);
        if (strcmp(cmd, "add") == 0) {
            add(name, qty);
        } else {
            struct Item *it = find(name);
            if (it == NULL || it->qty < qty) printf("short\n");
            else it->qty -= qty;
        }
    }
    return 0;
}

Output

Answer