c - 如何在双向链表中正确使用方向开关?
问题描述
我有一个双向链表,我想改变列表的方向。例如:
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) 的堆栈吗?
解决方案
这是由我的/最热门的评论开头的。
我仍然不确定你想要什么。但是,这与我能猜到的一样接近。
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
推荐阅读
- c - 是否有任何情况下 C 静态关键字应该或可以在头文件中用于变量?
- javascript - 只需调用 jQuery 函数一次
- reactjs - 如何使用 react-transition-group 触发动画
- javascript - 在不停止站点加载的情况下将数据上传到数据库
- java - 有没有使用 Junrar 库读取版本 5 的 RAR 文件的解决方案?
- reactjs - 根据 react-final-form 的更改更新表单值的简单方法
- php - 如何在 PHP 中将 mysql 查询的结果转换为 json 格式?
- go - golang renderer.HTML 没有从模板中选择 javascript 文件
- credentials - 我如何在不制作网站的情况下验证创建的插件
- php - 如何在 WooCommerce 中为未登录用户(访客)添加功能?