CODEWITHSUNDEEP
clistpointersswap
오경식
오경식

Reputation: 11

I have a problem with swap code in Doubly linked list

I made swap code in C but I didn't get perfect grade in school compiler. I think there is a problem with following code. I made doubly linked list with struct and pointer. Node is defined that:

struct node* newnode(char x)
{
    struct node* new = (struct node*)malloc(sizeof(struct node));
    new->next = NULL;
    new->prev = NULL;
    new->c = x;

    return new;
}

And the following code is swap code that I made each function factor mean that "struct node*p" is full list from head to tail, "int a and b" is rank of list and "count1(p)" is function that count node in full list and return number of node (exclude head and tail).

void swap(struct node* p, int a, int b)
{
    int x, y; 
    struct node* x1, * x2, emp = { 0 };
    int i = 0;
    x1 = p;
    x2 = p;

    if (a >= b) {
        x = b;
        y = a;
    }
    else {
        x = a;
        y = b;
    }
if (b <= 0 || a <= 0 || a > N || a > count1(p) || b > N || b > count1(p)) {
        printf("invalid position\n");
        return;
    }while (i < x && x1 != tail) {
        x1 = x1->next;
        i++;
    }
    i = 0;
    while (i < y && p != tail) {
        x2 = x2->next;
        i++;
    }
    if (x1->next != x2)
    {
        x1->prev->next = x2;
        x1->next->prev = x2;
        x2->prev->next = x1;
        x2->next->prev = x1;
        emp.next = x1->next;
        emp.prev = x1->prev;
        x1->next = x2->next;
        x1->prev = x2->prev;
        x2->next = emp.next;
        x2->prev = emp.prev;
    }
    if (x1->next == x2)
    {
        emp.prev = x1->prev;
        emp.next = x1->next;
        x1->prev->next = x2;
        x2->next->prev = x1;
        x1->prev = x2;
        x1->next = x2->next;
        x2->prev = emp.prev;
        x2->next = x1;


    }

}

The following code is my full code:

#include<stdio.h>
#include<stdlib.h>
int N;
struct node {
    struct node* next;
    struct node* prev;
    char c;
};
struct node* head, * tail;

void reset() {

    head = (struct node*)malloc(sizeof(struct node));
    tail = (struct node*)malloc(sizeof(struct node));
    head->prev = NULL;
    head->next = tail;
    head->c = NULL;
    tail->prev = head;
    tail->next = NULL;
    tail->c = NULL;
}
struct node* newnode(char x)
{
    struct node* new = (struct node*)malloc(sizeof(struct node));
    new->next = NULL;
    new->prev = NULL;
    new->c = x;

    return new;
}
void prcount(struct node* p)
{

    printf("%d\n", count1(p));
}
int count1(struct node* p)
{
    int sum = 0;

    while (p != tail) {
        p = p->next;

        sum++;

    }
    return sum + -1;
}
void add1(struct node* p, int n, char x)
{
    struct node* new1 = newnode(x);
    int i = 1;
    if (n <= 0 || n > N || n > count1(p) + 1) {
        printf("invalid position\n");
        return;
    }
    while (i < n && p != tail) {
        p = p->next;

        i++;

    }
    p->next->prev = new1;
    new1->prev = p;
    new1->next = p->next;
    p->next = new1;

}
void delete1(struct node* p, int n)
{
    int i = 0;
    if (n <= 0 || n > N || n > count1(p)) {
        printf("invalid position\n");
        return;
    }
    while (i < n && p != tail)
    {
        p = p->next;
        i++;
    }
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);


}
void get1(struct node* p, int n) {
    int i = 0;
    if (n <= 0 || n > N || n > count1(p)) {
        printf("invalid position\n");
        return;
    }while (i < n && p != tail) {
        p = p->next;
        i++;
    }
    printf("%c\n", p->c);
}
void print1(struct node* p)
{
    int i = 0;
    if (count1(p) == 0) {
        printf("invalid position\n");
        return;
    }
    while (i < N && p->next != tail)
    {
        p = p->next;
        printf("%c", p->c);
        i++;
    }
    printf("\n");

}void removeall(struct node* p)
{

    struct node* emp;
    p = p->next;


    while (p != tail)

    {
        emp = p->next;
        free(p);
        p = emp;
    }
    head->prev = NULL;
    head->next = tail;
    head->c = NULL;
    tail->prev = head;
    tail->next = NULL;
    tail->c = NULL;
}
void swap(struct node* p, int a, int b)
{
    int x, y;
    struct node* x1, * x2, emp = { 0 };
    int i = 0;
    x1 = p;
    x2 = p;

    if (a >= b) {
        x = b;
        y = a;
    }
    else {
        x = a;
        y = b;
    }

    if (b <= 0 || a <= 0 || a > N || a > count1(p) || b > N || b > count1(p)) {
        printf("invalid position\n");
        return;
    }while (i < x && x1 != tail) {
        x1 = x1->next;
        i++;
    }
    i = 0;
    while (i < y && x2 != tail) {
        x2 = x2->next;
        i++;
    }
    if (x1->next != x2)
    {
        x1->prev->next = x2;
        x1->next->prev = x2;
        x2->prev->next = x1;
        x2->next->prev = x1;
        emp.next = x1->next;
        emp.prev = x1->prev;
        x1->next = x2->next;
        x1->prev = x2->prev;
        x2->next = emp.next;
        x2->prev = emp.prev;
    }
    if (x1->next == x2)
    {
        emp.prev = x1->prev;
        emp.next = x1->next;
        x1->prev->next = x2;
        x2->next->prev = x1;
        x1->prev = x2;
        x1->next = x2->next;
        x2->prev = emp.prev;
        x2->next = x1;


    }

}
int main()
{
    int i;
    int r, n;
    char x, y;

    reset();

    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf(" %c", &x);
        if (x == 'A') {//A mean add(head,int a, char x) -> add 'x' on a rank in list
            scanf("%d", &r);

            scanf(" %c", &y);

            add1(head, r, y);
        }
        else if (x == 'D') {// D mean delete(struct node *head, int a) -> delete element on int a rank
            scanf("%d", &r);

            delete1(head, r);
        }
        else if (x == 'G') {//G mean Get(head,int a)-> print element on int a rank
            scanf("%d", &r);
            get1(head, r);

        }
        else if (x == 'P') {//P mean print(head) -> print all element in list
            print1(head);
        }
        else if (x == 'R') {//R mean Removeall(head) -> remove all node (exclude head and tail0
            removeall(head);
        }
        else if (x == 'C')//C Mean prcount(head) -> count and print number of node in list (exclude head and tail)
        {
            prcount(head);
        }
        else if (x == 'S') {//S mean Swap(head, int a, int b) -> swap element of int a rank with int b rank 
            scanf("%d", &r);
            scanf("%d", &n);
            swap(head, r, n);
        }
    }
    removeall(head);
}

It's my full code. I want to know is there any problem Or more effective way to make swap code?

Upvotes: 1

Views: 52

Answers (2)

Armali
Armali

Reputation: 19395

int N is used as the number of input commands in main. The comparisons with N in your list functions (as if N would denote the number of nodes) make no sense - you could just drop them.

Besides that, there are some places where a compiler with appropriate options would issue warnings - perhaps that's why you didnt get perfect grade in school compiler.

     head->c = NULL;

Since c is of type char and NULL is a null pointer constant this doesn't fit; change to

     head->c = '\0';    // or head->c = 0;

     printf("%d\n", count1(p));

There you call count1 before it is declared. Declare it before use with

int count1(struct node* p);

or move the function definition before the first function using it.

Upvotes: 0

오경식
오경식

Reputation: 11

#include<stdio.h>
#include<stdlib.h>
int N;
struct node {
    struct node* next;
    struct node* prev;
    char c;
};
struct node* head, * tail;

void reset() {

    head = (struct node*)malloc(sizeof(struct node));
    tail = (struct node*)malloc(sizeof(struct node));
    head->prev = NULL;
    head->next = tail;
    head->c = NULL;
    tail->prev = head;
    tail->next = NULL;
    tail->c = NULL;
}
struct node* newnode(char x)
{
    struct node* new = (struct node*)malloc(sizeof(struct node));
    new->next = NULL;
    new->prev = NULL;
    new->c = x;

    return new;
}
void prcount(struct node* p)
{
    
    printf("%d\n", count1(p));
}
int count1(struct node* p)
{
    int sum = 0;

    while (p != tail) {
        p = p->next;

        sum++;

    }
    return sum + -1;
}
void add1(struct node* p, int n, char x)
{
    struct node * new1 = newnode(x);
    int i = 1;
    if (n<=0||n > N || n > count1(p) + 1) {
        printf("invalid position\n");
        return;
    }
    while (i < n && p != tail) {
        p = p->next;

        i++;

    }
    p->next->prev = new1;
    new1->prev = p;
    new1->next = p->next;
    p->next = new1;

}
void delete1(struct node* p, int n)
{
    int i = 0;
    if (n <= 0 || n > N || n > count1(p)) {
        printf("invalid position\n");
        return;
    }
    while (i < n && p != tail)
    {
        p = p->next;
        i++;
    }
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);


}
void get1(struct node* p, int n) {
    int i = 0;
    if (n <= 0 || n > N || n > count1(p)) {
        printf("invalid position\n");
        return;
    }while (i < n && p != tail) {
        p = p->next;
        i++;
    }
    printf("%c\n", p->c);
}
void print1(struct node* p)
{
    int i = 0;
    if (count1(p) == 0) {
        printf("invalid position\n");
        return;
    }
    while (i < N && p->next != tail)
    {
        p = p->next;
        printf("%c", p->c);
        i++;
    }
    printf("\n");

}void removeall(struct node* p)
{

    struct node* emp;
    p = p->next;

    
    while (p != tail)

    {
        emp = p->next;
        free(p);
        p = emp;
    }
    head->prev = NULL;
    head->next = tail;
    head->c = NULL;
    tail->prev = head;
    tail->next = NULL;
    tail->c = NULL;
}
void swap(struct node* p, int a, int b)
{
    int x, y; 
    struct node* x1, * x2, emp = { 0 };
    int i = 0;
    x1 = p;
    x2 = p;

    if (a >= b) {
        x = b;
        y = a;
    }
    else {
        x = a;
        y = b;
    }
    
    if (b <= 0 || a <= 0 || a > N || a > count1(p) || b > N || b > count1(p)) {
        printf("invalid position\n");
        return;
    }while (i < x && x1 != tail) {
        x1 = x1->next;
        i++;
    }
    i = 0;
    while (i < y && p != tail) {
        x2 = x2->next;
        i++;
    }
    if (x1->next != x2)
    {
        x1->prev->next = x2;
        x1->next->prev = x2;
        x2->prev->next = x1;
        x2->next->prev = x1;
        emp.next = x1->next;
        emp.prev = x1->prev;
        x1->next = x2->next;
        x1->prev = x2->prev;
        x2->next = emp.next;
        x2->prev = emp.prev;
    }
    if (x1->next == x2)
    {
        emp.prev = x1->prev;
        emp.next = x1->next;
        x1->prev->next = x2;
        x2->next->prev = x1;
        x1->prev = x2;
        x1->next = x2->next;
        x2->prev = emp.prev;
        x2->next = x1;


    }

}
int main()
{
    int i;
    int r, n;
    char x, y;

    reset();

    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf(" %c", &x);
        if (x == 'A') {
            scanf("%d", &r);

            scanf(" %c", &y);

            add1(head, r, y);
        }
        else if (x == 'D') {
            scanf("%d", &r);

            delete1(head, r);
        }
        else if (x == 'G') {
            scanf("%d", &r);
            get1(head, r);

        }
        else if (x == 'P') {
            print1(head);
        }
        else if (x == 'R') {
            removeall(head);
        }
        else if (x == 'C')
        {
            prcount(head);
        }
        else if (x == 'S') {
            scanf("%d", &r);
            scanf("%d", &n);
            swap(head, r, n);
        }
    }
    removeall(head);
}

it is my full code

Upvotes: 0

Related Questions