回文链表

Question

方法：

从头到尾遍历给定列表，并将每个访问过的节点压入堆栈。
再次遍历列表。对于每一个被访问的节点，从栈中弹出一个节点，并将弹出节点的数据与当前访问的节点进行比较。
如果所有节点都匹配，则 return 为真，否则为假。

编辑: 程序编译没有错误但在运行时停止工作

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

struct Node
{
int data;
struct Node *next;
};
struct Stack
{
unsigned capacity;
int top;
int * array;
};
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack=(struct Stack*)malloc(sizeof(struct Stack));
stack->capacity=capacity;
stack->top=-1;
stack->array=(int *)malloc(sizeof(int)*stack->capacity);
return stack;
}
int isFull(struct Stack* stack)
{   return stack->top == stack->capacity - 1; }

// Stack 
int isEmpty(struct Stack* stack)
{   return stack->top == -1;  }

// stack.
void push(struct Stack* stack, int item)
{
if (isFull(stack))
    return;
stack->array[++stack->top] = item;
printf("%d pushed to stack\n", item);
}

// stack.  
int pop(struct Stack* stack)
{
if (isEmpty(stack))
    return INT_MIN;
return stack->array[stack->top--];
}

//  stack
int peek(struct Stack* stack)
{
if (isEmpty(stack))
    return INT_MIN;
return stack->array[stack->top];
}
// linkedlist
void insert(struct Node** head_ref, int new_data)
{

struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

new_node->data  = new_data;


new_node->next = (*head_ref);


(*head_ref)    = new_node;
}

bool compare(struct Stack* stack,struct Node* head)
{
struct Node* temp,* curr=head;
while(temp)
{
    push(stack,temp->data);
    temp=temp->next;
}
while(curr)
{
    if(pop(stack)==curr->data)
    {
       curr=curr->next;
    }
    else
    exit(0);
}
return true;

} 
// Driver program to test above functions
int main()
{
struct Stack* stack = createStack(100);
struct Node* head=NULL;
insert(&head,1);
insert(&head,2);
insert(&head,1);
printf("%s",compare(stack,head));

return 0;
}

Answer 1

struct Node* temp;

temp 未在

中初始化

bool compare(struct Stack* stack,struct Node* head)

struct Node* temp,* curr=head;

不是

struct struct Node* temp=head,* curr=head;

使用未初始化的变量会导致未定义的行为。

Answer 2

你有一个未初始化的局部变量temp:

bool compare(struct Stack* stack,struct Node* head)
{
    struct Node* temp,* curr=head;
    while(temp)  // NOT INITIALIZED
    {
        push(stack,temp->data);
        temp=temp->next;
    }
    while(curr)
    {
        if(pop(stack)==curr->data)
        {
            curr=curr->next;
        }
        else
            exit(0);
    }
    return true;
}

你需要先解决这个问题；我认为以下应该有效：

bool compare(struct Stack* stack,struct Node* head)
{
    struct Node  *curr;

    for (curr = head; curr != NULL; curr = curr->next)
    {
        push(stack, curr->data);
    }

    for (curr = head; curr != NULL; curr = curr->next)
    {
        if (pop(stack) != curr->data)
            return false;
    }
    return true;
}

接下来，您将使用 "%s" 打印布尔结果，这是针对字符串的。您需要执行以下操作：

    c=compare(stack,head);
    printf("%d\n", c);

或者

    printf("%s\n", c ? "true" : "false");

此时，它不再为我崩溃，并且适用于几个简单的测试用例。您可能会考虑如何处理堆栈溢出的情况，并考虑格式化您的代码以使其更具可读性。

Answer 3

bool compare(struct Stack* stack,struct Node* head) {
    struct Node* temp=head;//<- Needs initialising. It wasn't.
    struct Node* curr=head;
    while(temp) {
        push(stack,temp->data);
        temp=temp->next;
    }
    while(curr) {
        if(pop(stack)==curr->data) {
           curr=curr->next;
        } else {
            //exit(0); <--Some mistake surely!
            return false; //Slightly less drastic!
        }
    }
    return true;
}

这有点个人品味问题，但我发现一长串的变量声明难以阅读，因此容易出错。

您实际上只需要一个局部变量 - 但您的编译器可能会优化它。

exit(0) 会突然结束程序。最有可能表示 'success'（0 的出口）。

你应该return false;.

PS：使用 #include <stdbool.h> 的功劳。

Answer 4

函数compare至少有两个错误。第一个是它使用未初始化的指针 temp

bool compare(struct Stack* stack,struct Node* head)
{
struct Node* temp,* curr=head;
while(temp) // <= temp is not initialized
{

第二个是函数从不 returns false 尽管根据赋值它必须 return false 如果列表和堆栈不匹配。您调用函数 exit

而不是 returning false

else
exit(0);

我会按以下方式编写函数

bool compare(struct Stack *stack, struct Node *head )
{
    struct Node *current = head;

    for ( ; current != NULL && !isFull( stack ); current = current->next )
    {
        push( stack, current->data );
    }

    current = head;

    while ( current != NULL && !isEmpty( stack ) && pop( stack ) == current->data )
    {
        current = current->next;
    } 

    return current == NULL && isEmpty( stack );
}

它是唯一正确的函数实现在其他答案的函数实现中。:)

因为 C 没有类型 bool 那么你可以在用 C 编写的程序中使用名称 bool 你必须包含 header <stdbool.h> 或自己将此名称定义为 _Bool 的 typedef （如果你的编译器支持这种类型）或 int.

如果不想包含 header <stdbool.h>，可以将函数的 return 类型声明为 int。例如

int compare(struct Stack *stack, struct Node *head );

考虑到您还需要编写函数来释放所有分配给列表和堆栈的内存。

例如，您可以通过以下方式释放为堆栈分配的内存

void freeStack( struct Stack **stack )
{
    if ( *stack != NULL ) free( ( *stack )->array );
    free( *stack );

    *stack = NULL;
}

释放分配给列表的内存的方式相同

void freeList( struct Node **head )
{
    if ( *head != NULL )
    {
        Node *current = ( *head )->next;

        while ( current != NULL )
        {
            Node *temp = current;
            current = current->next;
            free( temp );
        }
    }

    free( *head );

    *head = NULL;
}

回文链表

Palindrome LinkedList

c