使用双向链表首次在C中实现堆栈,不进行打印。

huangapple go评论65阅读模式
英文:

Stack using doubly linked list for the first time in C, with no printing

问题

我已经使用双向链表实现了我的堆栈,但我不知道为什么它不打印,我认为这与正确的C语法或其他什么东西有关。

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

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

//---------------------Stack---------------------

typedef struct Stack {
    int size;
    Node* head;
    Node* tail;
    int top;
} Stack;

const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };

Node* create_node(int elm) {
    Node* node = malloc(sizeof * node);
    if (!node) return node;
    node->data = elm;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void push(Stack s, int elm) {
    Node* updated_head = create_node(elm);
    if (!s.head) {
        s.head = updated_head;
        s.tail = s.head;
    }
    else {
        updated_head->next = s.head;
        s.head->prev = updated_head;
        s.head = updated_head;
    }
    s.size++;
    s.top = s.head->data;
    // printf("%d ", s.tail->data);
}

int pop(Stack s) {
    Node* node = s.head;
    int elm = node->data;
    s.head = s.head->next;
    if (s.head) {
        s.head->prev = NULL;
        s.top = s.head->data;
    }
    else {
        s.tail = NULL;
        s.top = -1;
    }
    s.size--;
    free(node);
    return elm;
}

int top(Stack s) {
    return s.top;
}

void clear_s(Stack s) {
    while (s.tail)
        pop(s);
}

Stack reverse_s(Stack s) { // iterative
    Stack s2 = stack_init;
    while (s.tail) {
        push(s2, pop(s));
    }
    while (s2.tail) {
        push(s, pop(s2));
    }
    return s;
}

int is_empty_s(Stack s) {
    return s.tail == NULL;
}

void print_s(Stack s) {
    Node* trav = s.head;
    while (trav) {
        printf("%d ", trav->data);
        trav = trav->next;
    }
    printf("\n");
}

int main() {

    Stack s1 = stack_init;
    push(s1, 5);
    push(s1, 4);
    push(s1, 3);
    push(s1, 2);
    push(s1, 1);
    print_s(s1);
    
    return 0;
}

如您所见,堆栈基于我的双向链表,该链表是可用的,但从head节点开始的打印函数没有输出任何内容。

英文:

I have implemented my stack using doubly linked list and I don't know why it's not printing, I think it has something to do with the right C syntax or something?

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
//---------------------Stack---------------------
typedef struct Stack {
int size;
Node* head;
Node* tail;
int top;
} Stack;
const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };
Node* create_node(int elm) {
Node* node = malloc(sizeof * node);
if (!node) return node;
node-&gt;data = elm;
node-&gt;prev = NULL;
node-&gt;next = NULL;
return node;
}
void push(Stack s, int elm) {
Node* updated_head = create_node(elm);
if (!s.head) {
s.head = updated_head;
s.tail = s.head;
}
else {
updated_head-&gt;next = s.head;
s.head-&gt;prev = updated_head;
s.head = updated_head;
}
s.size++;
s.top = s.head-&gt;data;
// printf(&quot;%d &quot;, s.tail-&gt;data);
}
int pop(Stack s) {
Node* node = s.head;
int elm = node-&gt;data;
s.head = s.head-&gt;next;
if (s.head) {
s.head-&gt;prev = NULL;
s.top = s.head-&gt;data;
}
else {
s.tail = NULL;
s.top = -1;
}
s.size--;
free(node);
return elm;
}
int top(Stack s) {
return s.top;
}
void clear_s(Stack s) {
while (s.tail)
pop(s);
}
Stack reverse_s(Stack s) { // iterative
Stack s2= stack_init;
while (s.tail) {
push(s2, pop(s));
}
while (s2.tail) {
push(s, pop(s2));
}
return s;
}
int is_empty_s(Stack s) {
return s.tail == NULL;
}
void print_s(Stack s) {
Node* trav = s.head;
while (trav) {
printf(&quot;%d &quot;, trav-&gt;data);
trav = trav-&gt;next;
}
printf(&quot;\n&quot;);
}
int main() {
Stack s1 = stack_init;
push(s1, 5);
push(s1, 4);
push(s1, 3);
push(s1, 2);
push(s1, 1);
print_s(s1);
return 0;
}

As you can see, the stack is based off my doubly linked list which is functional and working, but the print function when starting from the head node doesn't output anything.

答案1

得分: 1

C使用值传递,这意味着push(s1, 5)实际上会传递s1的一个副本和数字5给函数。如果您想要进行变异,您需要传递s1的地址。拷贝操作可能会很昂贵,所以即使对于非变异操作,您可能更喜欢(也为了一致性)传递指向Stack的指针,但要标记它为const

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

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct Stack {
    int size;
    Node* head;
    Node* tail;
    int top;
} Stack;

const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };

Node* create_node(int elm) {
    Node* node = malloc(sizeof *node);
    if (node) {
        node->data = elm;
        node->prev = NULL;
        node->next = NULL;
    }
    return node;
}

void push(Stack *s, int elm) {
    Node* updated_head = create_node(elm);
    if (!s->head) {
        s->head = updated_head;
        s->tail = s->head;
    } else {
        updated_head->next = s->head;
        s->head->prev = updated_head;
        s->head = updated_head;
    }
    s->size++;
    s->top = s->head->data;
}

void print_s(Stack *s) {
    Node* trav = s->head;
    while (trav) {
        printf("%d ", trav->data);
        trav = trav->next;
    }
    printf("\n");
}

int main() {
    Stack s1 = stack_init;
    push(&s1, 5);
    push(&s1, 4);
    push(&s1, 3);
    push(&s1, 2);
    push(&s1, 1);
    print_s(&s1);
}

输出结果如下:

1 2 3 4 5

正如@Fe2O3在下面指出的那样,考虑从struct Stack中删除int top,因为它与s->head->data是多余的。

int size也是多余的,但在运行时计算它需要O(n)的时间,因此这是一个更可接受的选择。不过,如果你在每次变异时都要更新大小,那么你就要付出更新大小的代价,如果你从不需要它,那么这就是纯粹的开销。只有在多次调用它时,才有必要缓存大小。对我来说,这是一个提示,调用者应该在需要时缓存size

尽量在适用的情况下使用for循环。例如,print_s()可以这样编写:

for (Node* trav = s->head; trav; trav = trav->next)
    printf("%d%s", trav->data, trav->next ? " " : "\n");

尽量避免使用全局值。不过,将其设置为const是个好主意。您可以用一个同名的函数替换stack_init。这可以隐藏实现细节,使您的代码更容易修改。

对于库来说,最佳实践是为每个符号添加一个命名空间前缀。在您的情况下,也许是"Stack"?我更喜欢蛇形命名法而不是驼峰命名法,所以我更喜欢的前缀是"stack_",甚至可以使用更具描述性的前缀,因为堆栈通常是作为数组或单链表实现的。

英文:

C uses call by value which means that push(s1, 5) will actually pass a copy of s1 and 5 are to the function. As you want to mutation you need to pass the address of s1. Copies can be expensive, so even for a non-mutation you may prefer (also for consistency) to pass a pointer to Stack, but mark it const:

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
typedef struct Node {
int data;
struct Node* prev;
struct Node* next;
} Node;
typedef struct Stack {
int size;
Node* head;
Node* tail;
int top;
} Stack;
const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL, .top = -1 };
Node* create_node(int elm) {
Node* node = malloc(sizeof * node);
if (node) {
node-&gt;data = elm;
node-&gt;prev = NULL;
node-&gt;next = NULL;
}
return node;
}
void push(Stack *s, int elm) {
Node* updated_head = create_node(elm);
if (!s-&gt;head) {
s-&gt;head = updated_head;
s-&gt;tail = s-&gt;head;
} else {
updated_head-&gt;next = s-&gt;head;
s-&gt;head-&gt;prev = updated_head;
s-&gt;head = updated_head;
}
s-&gt;size++;
s-&gt;top = s-&gt;head-&gt;data;
}
void print_s(Stack *s) {
Node* trav = s-&gt;head;
while (trav) {
printf(&quot;%d &quot;, trav-&gt;data);
trav = trav-&gt;next;
}
printf(&quot;\n&quot;);
}
int main() {
Stack s1 = stack_init;
push(&amp;s1, 5);
push(&amp;s1, 4);
push(&amp;s1, 3);
push(&amp;s1, 2);
push(&amp;s1, 1);
print_s(&amp;s1);
}

and the resulting output is:

1 2 3 4 5

As @Fe2O3 points outs out below consider eliminating int top from your struct Stack as it's redundant with s-&gt;head-&gt;data;.

int size is also redundant but takes O(n) to compute at run-time so that is a more acceptable choice. That said, you pay the price for updating size on every mutation, and if you never need it that is pure overhead. Only if you call it more than once does it make sense to cache the size. To me that is a hint that caller should be caching the size if needed.

Prefer using for-loops when applicable. For instance print_s() could be written like this:

	for(Node* trav = s-&gt;head; trav; trav = trav-&gt;next)
printf(&quot;%d%s&quot;, trav-&gt;data, trav-&gt;next ? &quot; &quot; : &quot;\n&quot;);	
}

Avoid global values whenever possible. It is, however, a good call to make it a const. You could replace stack_init with a function of the same name. This hides implementation details which makes you code easier to change.

For a library it's best practice prefix each symbol with a namespace. In your case perhaps "Stack"? I prefer snake case to camel case so my preferred prefix would "stack_" and maybe even something more descriptive as a stack is usually either implemented as array or a single linked list.

huangapple
  • 本文由 发表于 2023年2月14日 08:01:51
  • 转载请务必保留本文链接:https://go.coder-hub.com/75442284.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定