如何删除两个索引之间的链表的节点？

Question

我有以下的链表实现：

struct _node { 
    char *string; 
    struct _node *next; 
} 

struct _list { 
    struct _node *head; 
    struct _node *tail; 
} 

我想作以下功能：

void deleteList(struct _list *list, int from, int to) { 
    int i; 

    assert(list != NULL); 

    // I skipped error checking for out of range parameters for brevity of code 

    for (i = from; i <= to; i++) { 
     deleteNode(list->head, i); 
    } 
} 

//我跑这个链表这样的功能：[First]->[Second]->NULL

这样deleteNodes(list, 1, 1)删除第二行，并得到 [First]->[Second]->NULL但我运行它像这样deleteList(list, 0, 1)与此输入[First]->[Second]->[Third]->NULL我有一个seg故障。

这里是我的deleteNode功能

void deleteNode(struct _node *head, int index) { 
    if (head == NULL) { 
     return; 
    } 

    int i; 
    struct _node *temp = head; 

    if (index == 0) { 
     if (head->next == NULL) { 
      return; 
     } 
     else { 
      head = head->next; 
      free(head); 
      return; 
     } 
    } 

    for (i = 0; temp!=NULL && i<index-1; i++) { 
     temp = temp->next; 
    } 

    if (temp == NULL || temp->next == NULL) { 
     return; 
    } 

    Link next = temp->next->next; 

    free(temp->next); 

    temp->next = next; 
} 

我写了一个单独的函数删除链表的头，如果从或向= 0：

void pop(struct _node *head) { 
    if (head == NULL) { 
     return; 
    } 

    struct _node *temp = head; 
    head = head->next; 
    free(temp); 
} 

，但它给了我赛格故障或内存错误中止trapL 6.

Answer 1

只用一个struct是一个很好的选择，它是您的目的节点。

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

然后你的循环去除两个指数之间的元素不会删除正确的元素，如果你不按照列表的长度变化的调整指数。你还必须返回列表的新头。

struct node *deleteList(struct node *head, unsigned from, unsigned to) { 
    unsigned i; 
    unsigned count = 0; 
    for (i = from; i <= to; i++) { 
     head = delete_at_index(head, i - count); 
     count++; 
    } 
    return head; 
} 

帮助功能delete_at_index如下所示。

struct node *delete_at_index(struct node *head, unsigned i) { 
    struct node *next; 

    if (head == NULL) 
     return head; 

    next = head->next; 

    return i == 0 
      ? (free(head), next)         /* If i == 0, the first element needs to die. Do it. */ 
      : (head->next = delete_at_index(next, i - 
               1), head); /* If it isn't the first element, we recursively check the rest. */ 
} 

下面的完整程序。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

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

void freeList(struct node *head) { 
    struct node *tmp; 

    while (head != NULL) { 
     tmp = head; 
     head = head->next; 
     free(tmp->string); 
     free(tmp); 
    } 

} 

struct node *delete_at_index(struct node *head, unsigned i) { 
    struct node *next; 

    if (head == NULL) 
     return head; 

    next = head->next; 

    return i == 0 
      ? (free(head), next)         /* If i == 0, the first element needs to die. Do it. */ 
      : (head->next = delete_at_index(next, i - 
               1), head); /* If it isn't the first element, we recursively check the rest. */ 
} 

struct node *deleteList(struct node *head, unsigned from, unsigned to) { 
    unsigned i; 
    unsigned count = 0; 
    for (i = from; i <= to; i++) { 
     head = delete_at_index(head, i - count); 
     count++; 
    } 
    return head; 
} 

void pushvar1(struct node **head_ref, char *new_data) { 
    struct node *new_node = malloc(sizeof(struct node)); 
    new_node->string = strdup(new_data); 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 

void printListvar1(struct node *node) { 
    while (node != NULL) { 
     printf(" %s ", node->string); 
     node = node->next; 
    } 
    printf("\n"); 
} 

int main(int argc, char **argv) { 
    struct node *head = NULL; 
    for (int i = 0; i < 5; i++) { 
     char str[2]; 
     sprintf(str, "node%d", i); 
     pushvar1(&head, str); 
    } 

    puts("Created Linked List: "); 
    printListvar1(head); 
    head = deleteList(head, 0, 2); 
    puts("Linked list after deleted nodes from index 0 to index 2: "); 
    printListvar1(head); 
    freeList(head); 
    return 0; 
} 

测试

Created Linked List: 
node4 node3 node2 node1 node0 
Linked list after deleted nodes from index 0 to index 2: 
node1 node0 

Answer 2

每一个规划问题可以通过添加额外的间接层次来解决：使用指针的指针...

---

unsigned deletefromto(struct node **head, unsigned from, unsigned to) 
{ 
unsigned pos,ret; 
struct node *this; 

for (pos=ret=0; this = *head;pos++) { 
     if (pos < from) { head = &(*head)->next; continue; } 
     if (pos > to) break; 
     *head = this->next; 
     free(this); 
     ret++; 
     } 
return ret; /* nuber of deleted nodes */ 
}