1

I trying to write a queue(String Version) program in C by using linked lists.

Here is the structure:

struct strqueue;
typedef struct strqueue *StrQueue;

struct node {
  char *item;
  struct node *next;
};

struct strqueue {
  struct node *front;//first element
  struct node *back;//last element in the list
  int length;
};

I creates a new StrQueue first

StrQueue create_StrQueue(void) {
  StrQueue q = malloc(sizeof (struct strqueue));
  q->front = NULL;
  q->back = NULL;
  q->length = 0;
  return q;
}

makes a copy of str and places it at the end of the queue

void push(StrQueue sq, const char *str) {
  struct node *new = malloc(sizeof(struct node));
  new->item = NULL;
  strcpy(new->item,str);//invalid write size of 1 ?
  new->next = NULL;
  if (sq->length == 0) {
  sq->front = new;
  sq->back = new;
} else {
  sq->back->next = new;
  sq->back = new;
}
sq->length++;
}

frees the node at the front of the sq and returns the string that was first in the queue

char *pop(StrQueue sq) {
 if (sq->length == 0) {
 return NULL;
}
 struct node *i = sq->front;
 char *new = sq->front->item;
 sq->front = i->next;
 sq->length --;
 free(sq->front);
 return new;
}

I got invalid write size of 1 at strcpy(new->item,str); I dont understand why I got this error. Can anyone tell me why and tell me how should I fix it? Thanks in advance.

4

2 回答 2

5

好的，首先，在下面的答案中，我不是在修复你的双向链表概念，我只是在向你展示如何在你的问题范围内修复上面的代码。您可能想研究如何完成双向链表。

在：

void push(StrQueue sq, const char *str) {
  struct node *new = malloc(sizeof(struct node));
  new->item = NULL;

下一个陈述是错误的：

  strcpy(new->item,str);

有两种方法可以解决它：

  1. 确保在使用列表时 *str 是列表管理上下文之外的有效指针。

  2. 让列表管理字符串分配（可能还有解除分配）。

    1. 是一种快速而肮脏的方法，以后调试起来更容易，但更大的代码库使它变得很麻烦。
    2. 看起来更干净的代码，但需要初始设置规则，除了列表管理例程之外，您还应该创建对象（字符串）管理例程。本身就很麻烦。

案例1：const char *str保证在 StrQueue 的生命周期内有效（这就是您真正要寻找的）

它应该是：

new->item = str;

这里我们假设 str 是在别处分配的动态字符串

现在，当你弹出字符串时，你可以在 pop 中。因为您返回的指针仍然有效（您在其他地方保证它）

案例 2：const char *str不保证在 StrQueue 的生命周期内有效

然后使用：

new->item = strdup(str);

现在，当你弹出字符串时，你可以在 pop 中

  1. 取消分配 strdup 并且不返回任何内容，（与您所做的不完全相同）
  2. 将容器指针传递给 pop 内容item被复制的地方（干净）
  3. 返回弹出的指针，但完成后必须单独释放它（丑陋）

这将使您的 pop 功能成为以下之一：

案例 2.1：

 void pop(StrQueue sq) {

    if (sq->length == 0) {
       return NULL;
    }
    struct node *node = sq->front;
    sq->front = node->next;
    sq->length--;
    free(node->item);
    free(node);
}

案例 2.2：

 char *pop(StrQueue sq, char *here) {

    if (sq->length == 0) {
       return NULL;
    }
    struct node *node = sq->front;
    sq->front = node->next;
    sq->length--;
    strcpy(here, node->item);
    free(node->item);
    free(node);
}

案例 2.3：

 char *pop(StrQueue sq) {

    char *dangling_item = NULL;
    if (sq->length == 0) {
       return NULL;
    }
    struct node *node = sq->front;
    sq->front = node->next;
    sq->length--;
    dangling_item = node->item;
    free(node);
    return dangling_item;
}
于 2013-07-28T00:53:44.457 回答
1

I got invalid write size of 1 at strcpy(new->item,str); I dont understand why I got this error. Can anyone tell me why and tell me how should I fix it?

Why:

This code:

new->item = NULL;
strcpy(new->item,str);//invalid write size of 1 ?

You're not suppose to pass a null pointer to the first argument, it should be a pointer to allocated memory. The reason why you're getting this error message, I can imagine, is because the implementation of strcpy probably looks like this:

for (int i = 0; str2[i]; i++) str1[i] = str2[i];

And in the first iteration of the for loop, it writes to address 0 (a read-only section of memory) - this gives you the invalid write of size 1. I'm not sure, however, why you are only getting a size of 1, though (I would imagine it would be the entire size of the string). This could be because either a) str is only of size 1 or b) because the signal, SIGSEGV stops the program.

How to fix:

Allocate space for new->item before calling strcpy, like this:

new->item = malloc (strlen (str) + 1); // + 1 for null-terminating character

But you could probably include some error checking, like this:

int len = strlen (str) + 1;
if (len){
    new->item = malloc (len);
    if (!new->item){
        return;
    }
}
于 2013-07-28T01:30:41.840 回答