回文使用栈

Question

我的教授要求我们使用栈来检查一个单词是否是回文。每次运行时，都会出现错误：Unhandled Exception. Access violation。我做错了什么？如何改进我的代码？以下是我的代码：

 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");
}

- newbie

---

еңЁеҮҪж•°зӯҫеҗҚдёӯдҪҝз”ЁvalueиҖҢдёҚжҳҜvalue[i]гҖӮ - ruslik

Answer 1

你的push函数应该接收：

• 栈顶地址（你已经正确实现了）和
• 需要被压入的字符（这个需要修正）。

因此，方法签名应该是：

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

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

temp->name = value;

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

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

char pop(Stack**head)

这里存在另一个逻辑错误：

首先，您将输入的所有字符推入堆栈中。接下来开始弹出字符。没有终止条件来停止弹出操作。当您弹出所有字符（使堆栈为空）后，下一次调用pop会导致崩溃，因为您将引用NULL指针（*head将为NULL）。

要解决此问题，请仅弹出您已经推入的字符，方法如下：

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

由于&&是短路的，所以一旦您弹出所有字符，pop将不会被调用。

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

- codaddict

---

我的第二个错误是无法忽略的空值，它应该被处理。 - newbie

@新手：很高兴我能帮到你。确保你理解所做的更改。 - codaddict

Answer 2

我认为您应该将'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;
}

- YudhiWidyatama

Answer 3

在你的代码中，你应该检查是否已经到达了堆栈的末尾：

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

- Saeed Amiri

Answer 4

您也可以考虑使用“递归”，它与构造堆栈有些相似，只是它是隐式地为您的方法调用完成的。
回文问题是学习递归强大之处的经典练习 :)

- Juri

Answer 5

这是你调用的函数：

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

这是声明和定义的函数：

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

因此，在声明中，第3个参数是一个字符数组，而在调用部分中，第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]);

- chrisaycock

---

我的第二个错误是无法忽略的空值。 - newbie

@新手函数pop()声明为无返回值，但正在返回val值。 - chrisaycock

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;
}

- Neilvert Noval