C语言 C编程链表删除位置N处的节点

Question

提问by Grant

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.

编辑：找出问题所在。此外，如果您是通过谷歌或其他搜索引擎找到的，这里就是我出错的地方以及如何解决它。

My deleteNode() method was moving through the list properly with the correct temp and keeping the head untouched. Where I was going wrong was in what I was returning as the result of the method. I was returning either temp or newNode which is incorrect because it goes through the list until it finds defined position. Once it finds that defined position it it would reassign the ->next pointer to point to the next->next> pointer which is correct but again I was returning the wrong thing. Because we had moved through the list using temp/NewNode we lost the header and we were returning the position we found and whatever was still in the next positions of the list.

我的 deleteNode() 方法正在使用正确的温度正确地在列表中移动并保持头部不变。我出错的地方在于我作为方法的结果返回的内容。我返回的是 temp 或 newNode ，这是不正确的，因为它遍历列表直到找到定义的位置。一旦找到定义的位置，它就会重新分配 ->next 指针以指向 next->next> 指针，这是正确的，但我又返回了错误的东西。因为我们已经使用 temp/NewNode 在列表中移动，所以我们丢失了标题，我们正在返回我们找到的位置以及列表的下一个位置中的任何内容。

How we fix this is returning the head (which is what is passed into the method). The reason why this works is because we have to understand how LinkedLists work. The pointers of each node point to the next node. Ex. we have a linked list |A|| - |B|| - |C|| - |D|| - |E|| - |F||

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

If we want to delete Node C we move to node B using the temp pointer and then assign the B->next to temp->next->next Thus skipping over C node and assigning D node.

如果我们想删除节点 C，我们使用临时指针移动到节点 B，然后将 B->next 分配给 temp->next->next 从而跳过 C 节点并分配 D 节点。

NOTE: (From what I know this does not actually free the memory of C node so it isn't best practice because you can cause memory leaks this way) You should use the free() method on the C node.

注意：（据我所知，这实际上并没有释放 C 节点的内存，因此这不是最佳实践，因为这样会导致内存泄漏）您应该在 C 节点上使用 free() 方法。

Here is the code I ended up using

这是我最终使用的代码

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;
}

Hopefully that helps understand how I went out fixing it.

希望这有助于理解我是如何修复它的。

//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
ORIGINAL POST
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////////////////////////////// ////////////////////////////////////////////////
// ///////////////////////////////////////////////// ///////////////////////////////////////////
原始帖子
// ///////////////////////////////////////////////// //////////////////////////////////////////////
//// ///////////////////////////////////////////////// ////////////////////////////////////////////

EDIT: 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

编辑：注意：这是我花了几天（估计 4 小时）编程的家庭作业，我只是停留在这一部分。你可以在下面查看我的尝试

I've been able to insert and delete from begining/end however I can't seem to get my delete node at position N in linkedlist to work.

我已经能够从头/尾插入和删除，但是我似乎无法让我的删除节点在链表中的位置 N 工作。

My psuedocode looks like this:

我的伪代码如下所示：

LinkedList: 1,3,5,7,9,23
Grab LinkedList
Create new struct node A = head
Move through linkedlist until position
Assign node to node->next
return linkedlist

链表：1,3,5,7,9,23
抓取链表
创建新的结构节点 A = head
在链表中移动直到位置
将节点分配给节点->下一步
返回链表

EXAMPLE INPUT

示例输入

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);

Which should leave the llist with the values 3, 5, 9 once the code has been run However, It is replacing the first node with a 0

一旦代码运行，它应该将值 3, 5, 9 保留在列表中但是，它正在用 0 替换第一个节点

Actual Code:

实际代码：

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;
}

EDIT #2: Code typo

编辑#2：代码错别字

Thanks for any help in advance. From what I have concluded my problem is that I am not moving through the list properly but I am unsure as to why I am not.

提前感谢您的任何帮助。从我得出的结论来看，我的问题是我没有正确浏览列表，但我不确定为什么我没有。

Answer 1

采纳答案by Clark Gaebel

In your code, you have the line

在您的代码中，您有一行

newNode->next;

in your forloop. That operation doesn't do anything.

在你的for循环中。该操作没有任何作用。

You also have

你还有

newNode-> = NULL;

which is not valid C, and I have no idea how you got that to compile.

这不是有效的 C，我不知道你是如何编译它的。

But really, don't use that loop. A linked list is one of the most basic recursive data structures. As a result, almost all algorithms manipulating them are most elegant as a recursive solution.

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

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. */
}

Answer 2

回答by caf

Removing a given node nfrom a singly-linked list can be boiled down to this operation:

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

Set the pointer that points to nto point instead to n->next.

设置指针指向n，而不是指向n->next。

You can break this down into two operations:

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

Find the pointer that points to n;
Set that pointer to n->next.

找到指向的指针n；
将该指针设置为n->next。

The complication arises because the pointer that points to nmight either be the p->nextfield of the previous node in the list, or the headpointer (if nis the first node in the list).

复杂性的出现是因为指向的指针n可能是p->next列表中前一个节点的字段，或者是head指针（如果n是列表中的第一个节点）。

Your code does not appear to be complete - it doesn't ever set the ->nextfield of any node to anything, so it's hard to say what's actually wrong.

您的代码似乎并不完整 - 它从未将->next任何节点的字段设置为任何内容，因此很难说到底出了什么问题。

Answer 3

回答by Jim Balter

Your DeleteNode doesn't delete a node, it removes pos nodes from the front of the list. So you're trying to remove 9 items from a list that only contains 6, resulting of course in an empty list (NULL). Also, your code is overly complex and contains remnants of previous attempts. Please don't do that to yourself or to us; provide simple clean code and it will be easier to understand and to fix.

您的 DeleteNode 不会删除节点，它会从列表的前面删除 pos 节点。因此，您试图从仅包含 6 个项目的列表中删除 9 个项目，这当然会导致一个空列表 (NULL)。此外，您的代码过于复杂，并且包含以前尝试的残余。请不要对自己或我们这样做；提供简单干净的代码，它会更容易理解和修复。

Answer 4

回答by Jagmohan Singh

Figured out your for loop isn't reaching the desired position you wanted. Better use equal to sign for the constraint it will work. e.g.

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

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

}

Answer 5

回答by Alex Kotliarov

// 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;   
}

C语言 C编程链表删除位置N处的节点

提问by Grant

采纳答案by Clark Gaebel

回答by caf

回答by Jim Balter

回答by Jagmohan Singh

回答by Alex Kotliarov

相关推荐

最近更新

标签

C语言 C编程链表删除位置N处的节点

提问by Grant

采纳答案by Clark Gaebel

回答by caf

回答by Jim Balter

回答by Jagmohan Singh

回答by Alex Kotliarov

相关推荐

C语言 你如何将一个链表复制到另一个列表中？

C语言 函数 'close' 的隐式声明

C语言 如何将整数值转换为罗马数字字符串？

C语言 无符号长十六进制表示

相关推荐

最近更新

标签

C语言你如何将一个链表复制到另一个列表中？

C语言函数 'close' 的隐式声明

C语言如何将整数值转换为罗马数字字符串？

C语言无符号长十六进制表示