用链表实现任意索引的序列插入

Question

我试图在这里使用add_to_front函数实现sequence_insert_at

之前的一切

typedef struct sequence *Sequence;

是从另一个c文件粘贴过来的。

void sequence_insert_at(Sequence s, int pos, int item)
{
    struct node* temp = s->lst;
    for(; pos > 0; --pos)
    {
        temp = temp->rest;
    }
    add_to_front(&temp, item);
    ++s->length;
    if(!temp->rest)
    {
        s->end = temp;
    }
    //s->lst = temp;
}

我不知道为什么我总是得到一个运行时错误。如果我克隆s->lst并遍历克隆，我没有修改指向s中的节点的指针，但是如果我改变temp, s->lst应该有反映的变化，因为节点仍然是链接的。关于如何解决这个问题，有什么想法吗?我尝试在遍历后创建另一个节点，该节点在temp之前，然后将其设置为->rest = temp，但也失败了。

Answer 1

下面的错误a可以发现，但只能得到主函数运行

new_sequence不初始化它创建的Sequence中的任何内容。lst在sequence_insert_at

中访问时未初始化

struct node* temp = s->lst;

应该是什么样子

Sequence new_sequence()
{
    Sequence s = malloc(sizeof(struct sequence));
    if(!s)
    {
        printf("Out of memory. Can't allocate sn");
        exit(EXIT_FAILURE);
    }
    s->lst = malloc(sizeof(struct node));
    if(! s->lst) {
        printf("Out of memory. Can't allocate lstn");
    }
    s->lst->rest = NULL;
    s->length = 0;
    return s;
}

还必须将s->lst->rest设置为NULL，这表明列表中没有更多的元素，而end也不会过时。

struct sequence
{
    struct node* lst;
    int length;
};

你应该把序列本身传递给你的函数，而不是一个指向序列内部数据的指针。

add_to_front(&temp, item);

你的sequence_insert_at函数应该是一个可以处理任何位置而不是add_to_front()的函数，所以从add_to_front()调用位置0更容易，并且你在一个函数中完成了孔工作，而不是这里一半，那里一半。

void sequence_insert_at(Sequence s, int pos, int item)
{
    if(s && pos <= s->length) {
        print_sequence(s);
        struct node *newnode = malloc(sizeof(struct node));
        if (newnode == NULL) {
            printf("ERROR! add_to_front ran out of memory!n");
            exit(EXIT_FAILURE);
        }
        newnode->first = item;
        struct node* temp = s->lst;
        struct node* prv = NULL;
        for(int i = 0; i < pos; i++) {
            printf("skip %dn", temp->first);
            prv = temp;
            temp = temp->rest;
        }
        newnode->rest = temp;
        if(pos == 0) {
            printf("insert as firstn");
            s->lst = newnode;
        } else {
            printf("insert before %dn", temp->first);
            prv->rest = newnode;
        }
        ++s->length;
    }
}

在add_to_front中只需要一条语句

void add_to_front(Sequence s, int item) {
    sequence_insert_at(s, 0, item);
}

用于在列表的后面插入

void add_to_back(Sequence s, int item) {
    sequence_insert_at(s, s->length, item);
}

main函数的小测试

void print_sequence(Sequence s)
{
    struct node* temp = s->lst;
    for(int i = 0; i < s->length; temp = temp->rest) {
        printf("%d ", temp->first);
        i++;
    }
    printf("n");
}
int main()
{
    Sequence derp = new_sequence();
    sequence_insert_at(derp, 0, 14);
    add_to_front(derp, 16);
    sequence_insert_at(derp, 0, 17);
    sequence_insert_at(derp, 2, 15);
    add_to_back(derp, 13);
    print_sequence(derp);
    delete_sequence(derp);
    return 0;
}

输出是:

17 16 15 14 13

你必须遍历其他函数并修复它们。

最后我要注意的是，你所选择的变量名有点令人困惑，如果不是误导的话，我会这样命名

typedef struct node {
  int data; /* the data that a node holds */
  struct node* next; /* the pointer to the next node */
} Node_t;
typedef struct sequence {
    struct node* head; /* head or first element of the sequence/list */
    int length; /* length is ok but size is better */
} Sequence_t;