使用链表中的堆栈反转 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: %s\n", 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: %s\n", str);
}

基本上，只在字符串的中间步进（如果长度为奇数，则不包括中间字符），并从字符串的左半部分和右半部分交换字符。

Answer 2

首先，不要强制转换 malloc() 的结果，并始终检查它是否 return NULL。在写成here之后，最好也写成struct Stack *s = malloc(sizeof(*s));（*s两边的括号是可选的，因为它是变量而不是类型）。

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

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

Answer 3

您的代码中存在一些错误：

您在 rev 中分配的第一个元素从未被初始化，因此它包含垃圾。只是不要分配这个，让 push 完成所有工作。
pop 函数没有 return 任何东西，它需要 return 您从堆栈中弹出的字符。

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: %s\n", str);
}

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

Reversing a string in C using stack in linked list

c

stack

linked-list