使用堆栈回文

Question

我们的教授要求我们使用堆栈来检查一个单词是否是回文。 每次运行它时，都会出现错误：未处理的异常。访问冲突 我做错了什么？我该如何改进我的代码？我的代码如下：

 typedef struct stack{
    char name;
    struct stack * next;
}Stack;

void push(Stack**head, char value);
char pop(Stack**head);


int main(){
   char word[11];
   int i=0;
   int lenght = 0; 
   Stack*head = NULL;
   printf("Please type the word: ");
   scanf("%s", word);
   lenght = strlen(word);
   while(word[i]!='\0'){
       push(&head, word[i]);
       i++;
   }
   i = 0;
   while(pop(&head)==word[i]){
       i++;
   }
   if(i==lenght) printf("The word is a palindrome");
   else printf("The word is not a palindrome");
}

Answer 1

您的 push 函数应该获取

• 堆栈头的地址（您已经正确）和
• 需要推入的字符（这需要修复）。

因此，方法签名变为：

void push(Stack**head, char value);

在函数主体中，您将 value 添加到堆栈顶部，如下所示：

temp->name = value;

另外，您必须始终检查 malloc 的返回值。

由于您要从函数 pop 返回弹出的值，因此它的返回类型不得为 void，因此请在声明和声明中将其更改为 char定义为：

char pop(Stack**head)

还有另一个逻辑错误：

首先将输入的所有字符推入堆栈。接下来你开始弹出字符。你的弹出没有终止条件。当您弹出所有字符（因此堆栈为空）时，下一次调用 pop 将导致崩溃，因为您将取消引用 NULL 指针（ < code>*head 将为 NULL）。

要解决此问题，您只需弹出已推送的字符：

while(i<lenght && pop(&head)==word[i]){

由于 && 是短路的，因此一旦弹出所有字符，就不会调用 pop人物。

或者（也是首选方法）是编写另一个名为 isEmpty 的函数，当堆栈为空时返回 true/1 并在您之前使用此方法调用 pop 方法。

Answer 2

你应该检查你的代码是否丰富了堆栈末尾：

while(i < length && pop(&head)==word[i]){
       i++;
   }

Answer 3

我认为你应该将 'void pop(Stack **head){' 更改为

char pop(Stack **head) {

并防止空堆栈：

char pop(Stack**head){
Stack* temp;
char val;
temp = *head;
if (!temp) return 0;
val = temp->name;
*head = (*head)->next;
free(temp);
return val;
}

Answer 4

您还可以考虑使用“递归”，这在某种程度上类似于构造堆栈，只是它是为您的方法调用隐式完成的。
回文问题是学习递归威力的经典练习:)

Answer 5

这是您调用它的函数：

push(&head, i, word[i]);

这是声明和定义的函数：

void push(Stack**head, int i, char value[i]);

因此声明中的 arg 3 是一个字符数组，而调用部分中的 arg 3 是一个字符。更改您的 push() 以使用字符作为 value 并省略 i：

void push(Stack**head, char value){
    Stack *temp = (Stack*)malloc(sizeof(Stack));
    temp->name = value;
    temp->next = *head;
    *head = temp; 
}

现在用以下方式调用它：

push(&head, word[i]);

Answer 6

您的代码在 while-pop 部分出现问题。

为了您的方便，我已为您附上修改后的工作代码：

typedef struct stack{
    char name;
    struct stack * next;
}Stack;

void push(Stack**head, char value);
char pop(Stack**head);



int main (int argc, const char * argv[]) {


    char word[11];
    int i=0;
    int lenght = 0; 
    Stack*head = NULL;
    printf("Please type the word: ");
    scanf("%s", word);
    lenght = strlen(word);
    while(word[i]!='\0'){
        push(&head, word[i]);
        i++;
        }

    //i = 0;
    //while(pop(&head)==word[i]){
    //  i++;
    //}

    int counter=0;
    i=0;
    for (counter=0; counter<lenght; counter++) {
    if (pop(&head) == word[counter])
    {
        i++;
    }
    }


    if(i==lenght) printf("The word is a palindrome");
    else printf("The word is not a palindrome");


    return 0;
}

void push(Stack**head,char value){

    Stack *temp = (Stack*)malloc(sizeof(Stack));
    temp->name = value;
    temp->next = *head;
    *head = temp; 
}

char pop(Stack**head){

    Stack* temp;

    char val;
    temp = *head;
    val = temp->name;
    *head = (*head)->next;

    free(temp);
    return val;
}