如何正确使用双向链表中的方向开关？

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

本文以 my/the 条热门评论开头。

我还是不确定你到底想要什么。但是，这是我能做到的最接近 divine/guess.

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

如何正确使用双向链表中的方向开关？

How to Properly Use a Direction Switch in a Doubly Linked List?

c

big-o

doubly-linked-list