如何在双向链接列表中正确使用方向开关？

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 总是追加到列表的tail（即，它忽略 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