回文LinkedList
回文LinkedList
提问于 2015-01-07 08:09:34
方法：
- 从头到尾遍历给定的列表，并将每个访问的节点推送到堆栈。
- 再看一遍名单。对于每个访问节点，从堆栈中弹出一个节点，并将弹出节点的数据与当前访问的节点进行比较。
- 如果所有节点匹配，则返回true，否则为false。
编辑：程序编译时没有错误，但在运行时停止工作。
#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;
}回答 4
Stack Overflow用户
回答已采纳
发布于 2015-01-07 08:55:15
函数compare至少有两个错误。第一个是它使用未初始化的指针临时。
bool compare(struct Stack* stack,struct Node* head)
{
struct Node* temp,* curr=head;
while(temp) // <= temp is not initialized
{第二个问题是，函数永远不会返回false，但是根据赋值，如果列表和堆栈中的值不匹配，则必须返回false。而不是返回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，所以您必须包含头<stdbool.h>，或者自己将这个名称定义为_Bool (如果编译器支持这种类型)或int的类型。
如果不想包含头<stdbool.h>，可以将函数的返回类型声明为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;
} Stack Overflow用户
发布于 2015-01-07 08:10:39
struct Node* temp;中未初始化temp
bool compare(struct Stack* stack,struct Node* head)
struct Node* temp,* curr=head;不是
struct struct Node* temp=head,* curr=head;使用未初始化的变量会导致未定义的行为。
Stack Overflow用户
发布于 2015-01-07 08:25:45
您有一个未初始化的局部变量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");在这一点上，它不再对我崩溃，并适用于几个简单的测试用例。您可能会考虑如何处理堆栈溢出的情况，还可以考虑格式化代码以提高代码的可读性。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/27814945
复制相关文章
相似问题
腾讯云开发者
