Как правильно использовать переключатель направления в двусвязном списке?

Question

У меня есть дважды связанный список, и я хочу изменить направление списка. Например:

1 -> 2 -> 3

становится

3 -> 2 -> 1

Я использовал логическое выражение в моем структура для определения направления.

typedef struct Node Node;

struct Node {
char character;
Node *link[2];
bool dir;
} direction;

Я определяю направление с помощью этого формата:

Node *p;
p->link[p->dir];

или

Node *p;
p->link[!p->dir];

Проблема, с которой я столкнулся, заключается в том, что я хочу перевернуть эти логические значения направления с методом, который использует время выполнения O (1). Я попытался создать функцию, которая обрабатывает ее следующим образом:

//global variable
int d = 0;

//function
void switchStack ( ) {
    if (d == 0) {
        d = 1;
        direction->link[direction->dir] = direction->link[!direction->dir];
    else if (d == 1) {
        d = 0;
        direction->link[direction->dir] = direction->link[!direction->dir];
    }

Эта функция, похоже, ничего не делает, и любые другие варианты, которые я пробую, вызывают сбой программы при ее вызове. Кто-нибудь имеет представление о том, как правильно использовать переключатель направления для реверса стека со временем выполнения 0 (1)?

Answer 1

Это предваряется моими / главными комментариями.

Я до сих пор не уверен, что именно вы хотите. Но это настолько близко, насколько я могу угадать / угадать.

listadd всегда добавляет к хвосту списка (то есть он игнорирует dir).

Но listprint чтит dir. Это модель для других функций, которые вы можете написать.

Но, я думаю, только listprint нужно посмотреть на dir. Все остальные функции могут обрабатывать данный список как прямой список (т. Е. Посмотреть, как работает listadd).

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

typedef struct node Node;
struct node {
    Node *links[2];
    int value;
};
#define PREV    0
#define NEXT    1

typedef struct {
    Node *begend[2];
    int dir;
} List;
#define HEAD    0
#define TAIL    1

static inline Node *
listfirst(List *list)
{
    return list->begend[list->dir ? TAIL : HEAD];
}

static inline Node *
listlast(List *list)
{
    return list->begend[list->dir ? HEAD : TAIL];
}

static inline Node *
nodenext(List *list,Node *cur)
{
    return cur->links[list->dir ? PREV : NEXT];
}

static inline Node *
nodeprev(List *list,Node *cur)
{
    return cur->links[list->dir ? NEXT : PREV];
}

List *
listnew(void)
{
    List *list = calloc(1,sizeof(List));

    return list;
}

Node *
nodenew(int value)
{
    Node *cur = calloc(1,sizeof(Node));

    cur->value = value;

    return cur;
}

void
listadd(List *list,int value)
{
    Node *node = nodenew(value);
    Node *prev = list->begend[TAIL];

    do {
        if (prev != NULL) {
            prev->links[NEXT] = node;
            node->links[PREV] = prev;
            break;
        }

        list->begend[HEAD] = node;
    } while (0);

    list->begend[TAIL] = node;
}

void
listprint(List *list)
{
    Node *cur;

    for (cur = listfirst(list);  cur != NULL;  cur = nodenext(list,cur))
        printf("%d\n",cur->value);
}

int
main(void)
{
    List *list = listnew();

    listadd(list,1);
    listadd(list,2);
    listadd(list,3);

    printf("\n");
    printf("list in forward direction\n");
    listprint(list);

    // reverse the list
    list->dir = ! list->dir;

    printf("\n");
    printf("list in reverse direction\n");
    listprint(list);

    return 0;
}

---

Это вывод программы:

list in forward direction
1
2
3

list in reverse direction
3
2
1