Cython双向链表按顺序打印

Question

您好，我正在构建一个双向链表结构，我希望按字母顺序打印我的测试 names/words。

最终产品应如下所示：

BRAIDEN
BRANT
DAVE
KIM

目前 show_all 将显示复制在所有先前条目之上的最后一个条目。

示例：如果最后输入“DAVE”，所有输出将是：

DAVE
DAVE
DAVE
DAVE

如果我在 create() 函数中打印，我得到输出：

BRAIDEN
BRANT
KIM
DAVE

这不是字母顺序，而是我输入的顺序。

注意：到目前为止，我的双向链表似乎并未通过其结构进行打印。我的意思是，您现在可以简单地打印节点或调用 show_all 两种方式，它不是通过结构打印，就好像它们是单独打印的一样。

Program.pyx

from libc.stdlib cimport malloc, free

cdef struct Node
cdef struct Node:
    char* word
    Node* prev
    Node* next

cdef class DoublyLinkedList:

    cdef Node* head
    cdef Node* tail
    cdef Node* last_node
    cdef Node* next_node

    def __cinit__(self):
        self.head = NULL
        self.tail = NULL
        self.last_node = NULL
        self.next_node = NULL

    def create(self, word):
        cdef Node* new_node = <Node*>malloc(sizeof(Node*))
        if not new_node:
            raise MemoryError()

        new_node.word = word
        new_node.prev = NULL
        new_node.next = NULL

        if (self.head == NULL):
            self.head = new_node
            self.tail = new_node
        elif (self.head.word >= new_node.word):
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        else:

            last_node = self.head
            next_node = self.head.next
            while (next_node != NULL):
                if (next_node.word >= new_node.word):
                    break
                last_node = next_node
                next_node = next_node.next

            new_node.prev = last_node
            new_node.next = next_node
            last_node.next = new_node

        if (next_node == NULL):
            self.tail = new_node
        else:
            next_node.prev = new_node
    
    def show_all(self):
        while (self.head != NULL):
            print(self.head.word)
            self.head = self.head.next

testing_interface.py

import program

algo = program.DoublyLinkedList()

algo.create(bytes("BRAIDEN", encoding="utf-8"))
algo.create(bytes("BRANT", encoding="utf-8"))
algo.create(bytes("KIM", encoding="utf-8"))
algo.create(bytes("DAVE", encoding="utf-8"))
algo.show_all()

Answer 1

你应该为一个节点分配，而不是为一个指针分配一个节点。

换句话说，行

cdef Node* new_node = <Node*>malloc(sizeof(Node*))

应该是

cdef Node* new_node = <Node*>malloc(sizeof(Node))

Answer 2

node.word 不拥有自己的记忆。它指向 Python bytes 对象拥有的内存。该内存仅在 bytes 对象存在时有效。

由于您使用传递给构造函数的临时变量对其进行初始化，因此内存仅在构造函数期间有效，不再有效。

您需要让 bytes 对象保持活动状态，或者将它们的内容复制到您管理的内存中。

Cython双向链表按顺序打印

Cython Doubly Linked list printing in order

c

python

cython