首页 文章

C编程链接列表删除位置N处的节点

提问于
浏览 次
4

EDIT: Figured out the problem. Also if you found this through google or another search engine here is where I went wrong and how to fix it.

我的deleteNode（）方法正确地使用正确的temp移动列表并保持头部不变 . 我出错的地方是因为该方法的结果我正在返回 . 我正在返回temp或newNode，这是不正确的，因为它通过列表直到找到定义的位置 . 一旦找到定义的位置，它就会重新分配 - > next指针指向next-> next>指针，这是正确的，但我又回到了错误的位置 . 因为我们使用temp / NewNode移动了列表，所以我们丢失了 Headers ，我们返回了我们找到的位置以及列表中下一个位置的任何位置 .

我们如何解决这个问题就是返回头部（这是传递给方法的内容） . 这之所以有效，是因为我们必须了解LinkedLists的工作原理 . 每个节点的指针指向下一个节点 . 防爆 . 我们有一个链表| A || - | B || - | C || - | D || - | E || - | F ||

如果我们要删除Node C，我们使用temp指针移动到节点B，然后在temp-> next-> next旁边分配B->从而跳过C节点并分配D节点 .

注意:(据我所知，这实际上并没有释放C节点的内存，所以这不是最佳实践，因为你可以通过这种方式导致内存泄漏）你应该在C节点上使用free（）方法 .

这是我最终使用的代码

struct node* DeleteNode(struct node* head, int pos) {

     struct node* temp = head;
     int length = LinkedListLength(temp);
     int i;

    if(pos <= 0 || pos > length){
        printf("ERROR: Node does not exist!\n");
    }else{
        if(pos == 1){
            head = head->next; //move from head (1st node) to second node
        }else{
            for(i = 1; i < pos-1; ++i){ //move through list
                    temp = temp->next;
            }
            temp->next = temp->next->next;
        }
    }
    return head;
}

希望这有助于了解我如何修复它 .

////////////////////////////////////////////////// ////////////////////////////////////////////////
////////////////////////////////////////////////// ////////////////////////////////////////////////
原始邮政
////////////////////////////////////////////////// ////////////////////////////////////////////////
////////////////////////////////////////////////// ////////////////////////////////////////////////

编辑： Note: This is a homework assignment I have spent a few days (estimated 4 hours) programming it I am just stuck on this one part. You can view my attempt below

我已经能够从开始/结束插入和删除但是我似乎无法在链接列表中的位置N处获取我的删除节点 .

我的伪代码看起来像这样：

  • LinkedList：1,3,5,7,9,23

  • grab LinkedList

  • 创建新的结构节点A = head

  • 移动链表直到位置

  • 将节点分配给node-> next

  • 返回链表

示例输入

Node structure 
int data;
struct node* next;

int values[] = {1,3,5,7,9,23};
struct node* llist = CreateList(values,6);

llist = DeleteNode(llist, 1);
llist = DeleteNode(llist, 5);
llist = DeleteNode(llist, 3);

一旦代码运行，哪个应该留下值为3,5,9的llist但是，它正在用0替换第一个节点

实际代码：

struct node* DeleteNode(struct node* head, int pos) {

struct node* temp = head;
struct node* newNode = head;
int length;
int i;

printf("DeleteNode: position = %d \nBefore: ", pos);
PrintList(temp);

if(pos <= 0){ //node does NOT exist
    printf("ERROR: Node does not exist!\n");
}else{ //node DOES exist
    length = LinkedListLength(temp);

    if(length < pos){ //if length < position Node does not exist
        printf("ERROR: Node does not exist!\n");
    }else{
        if(pos == 0){
            newNode = temp->next;
        }else if(pos == 1){
            newNode = temp->next;
        }else{
            for(i = 1; i < pos; i++){
                printf("i = %d\n", i);
                temp = temp->next;
                newNode->next;
            }
            if(temp->next == NULL){
                newNode = NULL;
            }else{
                newNode = temp->next;
            }
        }
    printf("After: ");
    PrintList(newNode);
    printf("\n");
    }
}
return newNode;
}

编辑＃2：代码拼写错误

在此先感谢您的帮助 . 从我的结论来看，我的问题是我没有正确地通过列表，但我不确定为什么我不是 .

c data-structures struct linked-list

5 回答

  • 1

    在你的代码中，你有这条线

    newNode->next;

    在你的 for 循环中 . 那个操作没有做任何事情 .

    你也有

    newNode-> = NULL;

    这是无效的C，我不知道你是如何编译的 .

    但实际上，不要使用那个循环 . 链表是最基本的递归数据结构之一 . 因此，几乎所有操作它们的算法都是最优雅的递归解决方案 .

    typedef struct node node_t;

node_t* delete_at_index(node_t* head, unsigned i)
{
    node_t* 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. */
}
    回复于
  • 1

    想出你的for循环没有达到你想要的所需位置 . 更好地使用等于符号来表示它将起作用的约束 . 例如

    for (i=1;i<=position-1;i++)
{

}
    回复于
  • 0
    // Remove list's node located at specified position.
// Arguments:
//  head -- list's head
//  pos -- index of a node to be removed (1-based!!!)

struct node* DeleteNode(struct node* head, int pos) 
{

    struct node* node;
    struct node* prev;
    int length;
    int i;

    printf("DeleteNode: position = %d \nBefore: ", pos);
    PrintList(head);

    // Check position's lower bound. Should be >= 1
    if(pos <= 0) { //node does NOT exist
        printf("ERROR: Node does not exist!\n");
        return head;
    }

    // Seek to the specified node, and keep track of previous node.
    // We need previous node to remove specified node from the list.

    for(i=1, prev = 0, node = head; i < pos && node != 0; i++) {
        prev = node;
        node = node->next;
    }

    // Out of range
    if(0 == node) {
        printf("ERROR: Index out of bounds!\n");
        return head;
    }

    // @node points to a list's node located at index pos 
    // @prev points to a previous node.

    // Remove current node from the list.
    if(0 == prev) {
        head = node->next;
    }
    else {
        prev->next = node->next;
    }
    free(node);

    return head;   
}
    回复于
  • 1

    您的DeleteNode不会删除节点，它会从列表的前面删除pos节点 . 所以你试图从一个只包含6的列表中删除9个项目，当然这会产生一个空列表（NULL） . 此外，您的代码过于复杂，并包含以前尝试的残余 . 请不要对自己或我们这样做;提供简单干净的代码，它将更容易理解和修复 .

    回复于
  • 0

    从单链接列表中删除给定节点 n 可以归结为此操作：

    • 将指向 n 的指针设置为指向 n->next .

    您可以将其分解为两个操作：

    • 找到指向 n 的指针;

    • 将该指针设置为 n->next .

    由于指向 n 的指针可能是列表中上一个节点的 p->next 字段，或者 head 指针（如果 n 是列表中的第一个节点），则会出现复杂情况 .

    您的代码似乎并不完整 - 它不会将任何节点的 ->next 字段设置为任何内容，因此's hard to say what'实际上是错误的 .

    回复于

相关问题