Question

用栈判断是否回文，急急急

自己写的程序如下 检验没有错误 但就是结果输出不对，求大神解答啊！！
#include<stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct linknode
{
ElemType data;
struct linknode *next;
}LiStack;

void InitStack(LiStack *s)
{
s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}

void push(LiStack *s, ElemType e)
{
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e;
p->next=s->next;
s->next=p;
}

ElemType pop(LiStack *s, ElemType e)
{
LiStack *p;
if(s->next==NULL)
return 0;
p=s->next;
e=p->data;
s->next=p->next;
free(p);
return e;
}

int compare(ElemType str[])
{
int i,m;

ElemType e=' ';
LiStack *s=NULL;
m=10;
for(i=0;i<m;i++)
{
scanf("str[i]\n",e);
}

InitStack(s);
for(m=0;str[m]!='\0';m++)
for(i=0;i<(m+1)/2;i++)
{
push(s,str[i]);
}
pop(s,e);
for(i=m/2;i<m;i++)
if(str[i]!=e)
return 0;
else
return 1;
return 0;
}

void main()
{
ElemType str[50];
printf("输入字符串：");
scanf("%s",str);
if(compare(str))
printf("\n字符串为回文");
else
printf("\n字符串不为回文");

}

Answer 1

我没仔细看你的代码，但是我觉得你想的复杂了，所以你的编程看起来十分分复杂。

我的思路更加简单，你为什么不把字符串整个翻转，然后和源字符串比对不就可以了。你这样太复杂了。下边我写一个翻转的函数，c++的泛型。应该很容易改成C语言。

#include<assert.h>
#include<algorithm>
template<class T>
void Rerverse(T *begin, T* end)
{
    assert(begin < end);
    if (begin < end)
    {
        swap(*begin, *end);
        begin++;
        end--;
    }
}

你的程序里面这个是不对的，你的s事传不回来的，这地方你需要使用二级指针，还有其他错误，我直接修改了你的代码，请看下边

 void InitStack(LiStack *s)
{
  s=(LiStack *)malloc(sizeof(LiStack));
  s->next=NULL;
}

#include<stdio.h>
#include <string.h> 
#include <stdlib.h>
 
typedef char ElemType;
 
typedef struct linknode
{
  ElemType data;
  struct linknode *next;
}LiStack;
 
void InitStack(LiStack **s)
{
  *s=(LiStack *)malloc(sizeof(LiStack));
  (*s)->next=NULL;
}
 
void push(LiStack *s, ElemType e)
{
  LiStack *p;
  LiStack *temp = s;
  while(NULL != temp->next)
  {
    temp = temp->next;
  }
  p=(LiStack *)malloc(sizeof(LiStack));
  p->data=e;
  p->next=NULL;
  temp->next=p;
  temp = p;
}
 
ElemType pop(LiStack *s)
{
   LiStack *p = s;
   LiStack *temp = s;
   ElemType e;
   if(p->next==NULL)
       return NULL;
   while(NULL != p->next)
  {
    temp = p;
    p = p->next;
  }
   e=p->data;
   temp->next = NULL;
   free(p);
   return e;
}
 
bool compare(ElemType str[])
{
  int i,m;
  bool flag = true;
  ElemType e=' ';
  LiStack *s=NULL;
  /*
  m=10;
  for(i=0;i<m;i++) 
  {
     scanf("str[i]\n",e);
  }
  
  InitStack(&s);
  for(m=0;str[m]!='\0';m++)
      for(i=0;i<(m+1)/2;i++)
      {
        push(s,str[i]);
      }
  pop(s,e);
  for(i=m/2;i<m;i++)
        if(str[i]!=e)
            return 0;
        else
            return 1;
        return 0;
        */
  InitStack(&s);
  for(i = 0; i < strlen(str); i++)
  {
    push(s,str[i]);
  }
  for(i = 0; i < strlen(str); i++)
  {
    if (str[i] != pop(s))
    {
        flag = false;
        break;
    }
  }
  return flag;
}
 
void main()
{
  ElemType str[50];
  printf("输入字符串：");
  scanf("%s",str);
  if(compare(str))
      printf("\n是字符串文");
      else
      printf("\n不是字符串文");
      
}

Answer 2

#include<stdio.h>
#include <string.h> 
#include <stdlib.h>
typedef char ElemType;
typedef struct linknode
{  
 ElemType data;  
 struct linknode *next;
}LiStack;
void initStack(LiStack *&s)
{
 s = (LiStack *)malloc(sizeof(LiStack));
 s->next = NULL;
}
bool isEmpty(LiStack *s)
{
 if (s == NULL)
  initStack(s);
 return s->next == NULL;
}
void push(LiStack *s, ElemType e)
{
 LiStack *p;
 p = (LiStack *)malloc(sizeof(LiStack));
 p->data = e;
 p->next = s->next;
 s->next = p;
}
bool pop(LiStack *s, ElemType &e)
{
 LiStack *p;
 if (isEmpty(s))
  return false;
 p = s->next;
 e = p->data;
 s->next = p->next;
 free(p);
 return true;
}
bool compare(ElemType str[])
{
 LiStack *s = NULL;
 initStack(s);
 ElemType e;
 int len = strlen(str);
 for (int i = 0; i < len / 2; i++)
  push(s, str[i]);
 for (int i = (len + 1) / 2; i < len; i++)
  if(pop(s, e) && e != str[i])
   return false;
 return isEmpty(s);
}
int main()
{
 ElemType str[50];
 printf("输入字符串: ");
 while (scanf("%s", str) != EOF)
 {
  if (compare(str))
   printf("字符串%s为回文.\n", str);
  else
   printf("字符串%s不为回文.\n", str);
  printf("输入字符串: ");
 }
 return 0;
}