使用链表中的堆栈反转C中的字符串

Question

我正在尝试使用堆栈反转给定的字符串。我使用链表，因为与数组相比，它占用的内存更少。这是我的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define M 100
struct Stack{
char ele;
struct Stack *next;
};
struct Stack* next_node(char element){
struct Stack *node=(struct Stack *)malloc(sizeof(struct Stack));
node->ele=element;
node->next=NULL;
return node;
}
int isEmpty(struct Stack *node){
return node==NULL;
}
void push(struct Stack **node, char element){
struct Stack *temp=next_node(element);
temp->next=*node;
*node=temp;
}
char pop(struct Stack **node){
if(isEmpty(*node)){
return 'a';
}
struct Stack *temp=*node;
*node=(*node)->next;
free(temp);
}
void rev(char str[]){
int i;
int n=strlen(str);
struct Stack *s=(struct Stack *)malloc(sizeof(struct Stack));
for(i=0;i<n;i++)
push(&s, str[i]);
for(i=0;i<n;i++)
str[i]=pop(&s);
printf("The reversed string is: %sn", str);
}
int main()
{
char string[M], op[1];
do{
printf("Enter the string to be reversed: ");
scanf("%s", string);
rev(string);
printf("Do you want to go again?(Y/N): ");
scanf("%s", op);
}while(op[0]=='Y');
}

然而，我没有得到任何输出，它只是简单地说，"相反的字符串是："；

我通过替换尝试了一个稍微不同的代码

node->ele=element;

带有

strcpy(node->ele, element);

但这给了我一个警告，上面写着：

warning: passing argument 1 of 'strcpy' makes pointer from integer without a cast

我无法理解为什么会发生这样的事情。感谢您的帮助！：-(

Answer 1

您可以完全跳过堆栈，做一些更简单、更快的事情，比如：

void rev(char str[])
{
int i;
int n = strlen(str);

for(i=0; i<n/2; i++) {
char tempChar = str[i];
str[i] = str[n-i-1];
str[n-i-1] = tempChar;
}
printf("The reversed string is: %sn", str);
}

基本上，只需遍历字符串的一半(如果长度为奇数，则不包括中间字符(，并交换字符串左半部分和右半部分的字符。

Answer 2

您的代码中有一些错误：

• 您在rev中分配的第一个元素从未初始化，因此它包含垃圾。只是不要分配这个，而是让push来做所有的工作
• pop函数不返回任何内容，它需要返回从堆栈中弹出的字符

---

char pop(struct Stack** node) {
if (isEmpty(*node)) {
return 0;                // return 0, not 'a'. Anyway this should never happen
}
struct Stack* temp = *node;
*node = (*node)->next;
char retval = temp->ele;   // retrieve char to return
free(temp);
return retval;             // return the char
}
void rev(char str[]) {
int i;
int n = strlen(str);
struct Stack* s = NULL;   // don't allocate anything here, just set it to NULL,
// but this is not even necessary here.
for (i = 0; i < n; i++)
push(&s, str[i]);
for (i = 0; i < n; i++)
str[i] = pop(&s);
printf("The reversed string is: %sn", str);
}

Answer 3

首先，不要强制转换malloc()的结果，并始终检查它是否返回NULL。按照这里写的内容，最好写struct Stack *s = malloc(sizeof(*s));(*s周围的括号是可选的，因为它是一个变量而不是类型(。

至于你的推理，我不确定链表是否真的比数组使用更少的内存。给定n是元素的数量，size是单个元素的大小(以字节为单位(，数组总是使用连续分配的内存的n * size字节，因此访问其所有元素也是非常高效和快速的；链表必须为每个节点保留指向下一个节点的指针，因此它需要n * size + n * 8字节，并且节点可以存储在整个内存中，因此在很大的列表中访问它们的效率也较低，速度也较慢。

由于你只是在反转一个字符串，所以你不需要一个在运行时可以正常增长的数据结构，或者至少你可以在主循环的每次迭代中分配一个合适大小的新数组。如果你想尝试一些很酷的链表练习，你可以尝试不同版本的头插入(堆栈(、尾插入(队列(或排序插入；然后，当你完成了基本的数据结构后，你可以用它们来解决其他问题，比如写一个后缀计算器或检查字符串中的括号是否平衡。