Home > Blockchain >  How to delete all smallest numbers in doubly linked list
How to delete all smallest numbers in doubly linked list

Time：12-08

I have a function that deletes the smallest node in a doubly-linked list. But if there are more than one same-valued integers, the function deletes the first one. I need to do, that function deletes all the smallest values.

I think I need to make a loop, to check all the values in the linked list and delete them if they are == to the smallest one.

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

typedef struct node{
    struct node *prev;
    int number;
    struct node *next;
} node;

node *createList(struct node *head, int n);
node *addToEmpty(node *head, int data);
node *addAtEnd(node *head, int data);
node *deleteSmallest(node *head, int n);
void cleanUp(node *head);

int main()
{
    node *head = NULL;
    node *ptr;
    int n;

    printf("Enter number of the nodes: ");
    scanf("%d", &n);

    head = createList(head, n);
    printf("\nN: %d\n\n", n);

    ptr = head;

    while(ptr != NULL)
    {
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n", ptr->number, ptr, ptr->prev, ptr->next);
        ptr = ptr->next;
    }

    head = deleteSmallest(head, n);

    printf("\n\n");

    ptr = head;

    while(ptr != NULL)
    {
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n", ptr->number, ptr, ptr->prev, ptr->next);
        ptr = ptr->next;
    }

    // Free all the pointers
    cleanUp(head);

    return 0;
}

node *createList(struct node *head, int n)
{
    int data;

    if(n <= 0)
        return head;

    printf("Enter number of the 1 node: ");
    scanf("%d", &data);

    head = addToEmpty(head, data);

    for(int i = 1; i < n;   i)
    {
        printf("Enter number of the %d node: ", i   1);
        scanf("%d", &data);
        head = addAtEnd(head, data);
    }
    return head;
}

node *addToEmpty(node *head, int data)
{
    node *temp = malloc(sizeof(node));
    temp->prev = NULL;
    temp->next = NULL;
    temp->number = data;
    head = temp;

    return head;
}

node *addAtEnd(node *head, int data)
{
    node *temp, *tp;

    temp = malloc(sizeof(node));
    temp->prev = NULL;
    temp->next = NULL;
    temp->number = data;
    tp = head;

    while (tp->next != NULL)
        tp = tp->next;

    tp->next = temp;
    temp->prev = tp;

    return head;
}

node *deleteSmallest(node *head, int n)
{
    node *smallest, *temp, *temporaryHead;
    int position = 1;
    temporaryHead = head;
    smallest = head;

    // Finding which node has the smallest int
    for(int i = 1; temporaryHead != NULL;   i)
    {
        temp = temporaryHead->next;
        if(smallest->number > temporaryHead->number)
        {
            smallest = temporaryHead;
            position = i;
        }
        temporaryHead = temp;
    }

    temporaryHead = NULL;

    temp = head;

    // If node is in the middle
    if(position > 1 && position < n)
    {
        while (position > 1) {
            temp = temp->next;
            --position;
        }
        temporaryHead = temp->prev;
        temporaryHead->next = temp->next;
        temp->next->prev = temporaryHead;
        free(temp);
        temp = NULL;
    }else if(position == 1)             // If node is the first element
    {
        head = head->next;
        free(head->prev);
        head->prev = NULL;
    }else                               // If node is the last element
    {
        while(temp->next != NULL)
            temp = temp->next;
        temporaryHead = temp->prev;
        temporaryHead->next = NULL;
        free(temp);
        temp = NULL;
    }

    return head;
}

void cleanUp(node *head)
{
    node *next;

    while(head != NULL)
    {
        next = head->next;
        free(head);
        head = next;
    }
}

CodePudding user response：

I would split the logic into parts:

  • A function to find the least value (an integer) in a list
  • A function to delete nodes from a list that have a given value
  • Use the above two functions to implement deleteSmallest

Here is how that could look:

int getSmallestValue(node *head) {
    int smallest = head == NULL ? 0 : head->number;
    while (head != NULL) {
        if (head->number < smallest) {
            smallest = head->number;
        }
        head = head->next;
    }
    return smallest;
}

node* deleteValue(node *head, int n) {
    node* temp, *current;
    while (head != NULL && head->number == n) {
        temp = head;
        head = head->next;
        free(temp);
    }
    head->prev = NULL;
    current = head->next;
    while (current != NULL) {
        temp = current;
        current = current->next;
        if (temp->number == n) {
            temp->prev->next = current;
            if (current != NULL) {
                current->prev = temp->prev;
            }
            free(temp);
        }
    }
    return head;
}

node *deleteSmallest(node *head, int n) {
    return deleteValues(head, getSmallestValue(head));
}

CodePudding user response：

I think I need to make a loop, to check all the values in the linked list and delete them if they are == to the smallest one.

I didn't quite understand the logic of your current function (particularly, the n argument).

Here is a function that will allow just one element to be removed or all matching smallest elements. If there is only one it is a single scan pass. If there are more, it is just two scan passes:

// deleteSmallAll -- delete all nodes that are the smallest
node *
deleteSmallAll(node *head,int allflg)
// allflg -- 1=delete all, 0=delete first
{
    node *small = head;
    int smcount = 0;
    int smnum = 0;
    node *cur = head;

    // skip over the first element (and assume it is the smallest)
    if (cur != NULL) {
        cur = cur->next;
        smcount = 1;
        smnum = small->number;
    }

    // find the smallest
    for (;  cur != NULL;  cur = cur->next) {
        int curnum = cur->number;

        // got a smaller element
        if (curnum < smnum) {
            smcount = 1;
            small = cur;
            smnum = curnum;
            continue;
        }

        // keep count of duplicate small numbers
        if (curnum == smnum) {
            if (allflg)
                smcount  = 1;
            continue;
        }
    }

    // start with the _first_ smallest node we found
    cur = small;

    // remove a single smallest and loop if more to do
    while (cur != NULL) {
        node *next = cur->next;
        node *prev = cur->prev;

        // unlink it
        if (prev != NULL)
            prev->next = next;
        else
            head = next;

        // unlink it
        if (next != NULL)
            next->prev = prev;
// NOTE: no tail pointer
#if 0
        else
            tail = prev;
#endif

        // release the node
        free(cur);

        // bug out if no more of that match
        if (--smcount <= 0)
            break;

        // find the next in the list that is the same match
        for (cur = next;  cur != NULL;  cur = cur->next) {
            if (cur->number == smnum)
                break;
        }
    }

    return head;
}

UPDATE:

Hopefully, you've gotten an answer for your basic question.

But, as others pointed out, what's the point to have a doubly linked list if you only traverse it in the forward direction?

Below is an updated version. It uses a separate list struct and passes a pointer to that instead of passing in head and always returning the updated value.

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

typedef struct node {
    struct node *prev;
    int number;
    struct node *next;
} node;

typedef struct {
    node *head;
    node *tail;
} list;

int
getnum(const char *prompt)
{
    char buf[100];
    int data = 0;

    // debug hook for input from redirected file (e.g. ./myprogram < input.txt)
    struct termios tio;
    int fileflg = tcgetattr(fileno(stdin),&tio) < 0;

    while (1) {
        printf("%s: ",prompt);
        fflush(stdout);

        if (fgets(buf,sizeof(buf),stdin) == NULL) {
            printf("getnum: premature EOF\n");
            if (fileflg)
                exit(1);
        }

        // echo the file input
        if (fileflg)
            fputs(buf,stdout);

        if (sscanf(buf,"%d",&data) == 1)
            break;
    }

    return data;
}

void
addAtEnd(list *lst, int data)
{
    node *temp;

    temp = malloc(sizeof(node));
    temp->number = data;

    if (lst->head == NULL)
        lst->head = temp;

    node *tail = lst->tail;
    if (tail != NULL) {
        temp->next = tail->next;
        tail->next = temp;
        temp->prev = tail;
    }
    else
        temp->prev = NULL;

    lst->tail = temp;
    temp->next = NULL;
}

void
createList(list *lst, int n)
{
    int data;
    char msg[100];

    for (int i = 0; i < n;   i) {
        sprintf(msg,"Enter number of the %d node", i   1);
        data = getnum(msg);
        addAtEnd(lst, data);
    }
}

// deleteSmallAll -- delete all nodes that are the smallest
void
deleteSmallAll(list *lst,int allflg)
// allflg -- 1=delete all, 0=delete first
{
    node *small = lst->head;
    int smcount = 0;
    int smnum = 0;
    node *cur = lst->head;

    // skip over the first element (and assume it is the smallest)
    if (cur != NULL) {
        smcount = 1;
        smnum = small->number;
        cur = cur->next;
    }

    // find the smallest
    for (;  cur != NULL;  cur = cur->next) {
        int curnum = cur->number;

        // got a smaller element
        if (curnum < smnum) {
            smcount = 1;
            small = cur;
            smnum = curnum;
            continue;
        }

        // keep count of duplicate small numbers
        if (curnum == smnum) {
            if (allflg)
                smcount  = 1;
            continue;
        }
    }

    // start with the _first_ smallest node we found
    cur = small;

    // remove a single smallest and loop if more to do
    while (cur != NULL) {
        node *next = cur->next;
        node *prev = cur->prev;

        // unlink it
        if (prev != NULL)
            prev->next = next;
        else
            lst->head = next;

        // unlink it
        if (next != NULL)
            next->prev = prev;
        else
            lst->tail = prev;

        // release the node
        free(cur);

        // bug out if no more of that match
        if (--smcount <= 0)
            break;

        // find the next in the list that is the same match
        for (cur = next;  cur != NULL;  cur = cur->next) {
            if (cur->number == smnum)
                break;
        }
    }
}

void
cleanUp(list *lst)
{
    node *next;

    for (node *cur = lst->head;  cur != NULL;  cur = next) {
        next = cur->next;
        free(cur);
    }

    lst->head = NULL;
    lst->tail = NULL;
}

void
print_fwd(list *lst,const char *msg)
{
    node *ptr = lst->head;

    printf("\n%s:\n",msg);
    for (;  ptr != NULL;  ptr = ptr->next)
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n",
            ptr->number, ptr, ptr->prev, ptr->next);
}

void
print_bwd(list *lst,const char *msg)
{
    node *ptr = lst->tail;

    printf("\n%s:\n",msg);
    for (;  ptr != NULL;  ptr = ptr->prev)
        printf("NUMBER:%d ADDRESS:%p PREVADD:%p NEXTADD:%p\n",
            ptr->number, ptr, ptr->prev, ptr->next);
}

int
main(void)
{
    list lstx = { NULL, NULL };
    list *lst = &lstx;
    node *ptr;
    int n;

    n = getnum("Enter number of the nodes");

    createList(lst, n);
    printf("\nN: %d\n", n);
    print_fwd(lst,"orig/fwd");
    print_bwd(lst,"orig/bwd");

    deleteSmallAll(lst, 0);
    print_fwd(lst,"after1/fwd");
    print_bwd(lst,"after1/bwd");

    deleteSmallAll(lst, 1);
    print_fwd(lst,"afterN/fwd");
    print_bwd(lst,"afterN/bwd");

    // Free all the pointers
    cleanUp(lst);

    return 0;
}

Here is the sample input:

6
2
6
2
7
8
2

Here is the sample output:

Enter number of the nodes: 6
Enter number of the 1 node: 2
Enter number of the 2 node: 6
Enter number of the 3 node: 2
Enter number of the 4 node: 7
Enter number of the 5 node: 8
Enter number of the 6 node: 2

N: 6

orig/fwd:
NUMBER:2 ADDRESS:0x11a4280 PREVADD:(nil) NEXTADD:0x11a42a0
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:0x11a4280 NEXTADD:0x11a42c0
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)

orig/bwd:
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:0x11a4280 NEXTADD:0x11a42c0
NUMBER:2 ADDRESS:0x11a4280 PREVADD:(nil) NEXTADD:0x11a42a0

after1/fwd:
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42c0
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)

after1/bwd:
NUMBER:2 ADDRESS:0x11a4320 PREVADD:0x11a4300 NEXTADD:(nil)
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:0x11a4320
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42c0 NEXTADD:0x11a4300
NUMBER:2 ADDRESS:0x11a42c0 PREVADD:0x11a42a0 NEXTADD:0x11a42e0
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42c0

afterN/fwd:
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42e0
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42a0 NEXTADD:0x11a4300
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:(nil)

afterN/bwd:
NUMBER:8 ADDRESS:0x11a4300 PREVADD:0x11a42e0 NEXTADD:(nil)
NUMBER:7 ADDRESS:0x11a42e0 PREVADD:0x11a42a0 NEXTADD:0x11a4300
NUMBER:6 ADDRESS:0x11a42a0 PREVADD:(nil) NEXTADD:0x11a42e0

Page link：https//www.codepudding.com/Blockchain/635642.html

Prev:Can't get file size when path contains UTF-8 character in C
Next:Argument incompatible in print linked list - C
  • Related

About Us:  Contact Us      Terms of Service       Privacy Policy

Copyright © 2010-2023，Powered By CodePudding