C编程链表删除位置N处的节点 [英] C programming Linked Lists delete node at position N
问题描述
找出问题所在.此外，如果您是通过 google 或其他搜索引擎发现的，这里就是我出错的地方以及如何解决它.
我的 deleteNode() 方法以正确的温度在列表中正确移动并保持头部不变.我出错的地方在于我作为方法的结果返回的内容.我返回的是 temp 或 newNode ，这是不正确的，因为它遍历列表直到找到定义的位置.一旦找到定义的位置，它就会重新分配 ->next 指针以指向 next->next> 指针，这是正确的，但我又返回了错误的东西.因为我们已经使用 temp/NewNode 在列表中移动，所以我们丢失了标题，我们正在返回我们找到的位置以及列表的下一个位置中的任何内容.
我们如何解决这个问题是返回头部(这是传递给方法的内容).这之所以有效是因为我们必须了解 LinkedLists 是如何工作的.每个节点的指针指向下一个节点.前任.我们有一个链表 |A||- |B||- |C||- |D||- |E||- |F||
如果我们想删除节点 C，我们使用临时指针移动到节点 B，然后将 B->next 分配到 temp->next->next 从而跳过 C 节点并分配 D 节点.
注意:(据我所知，这实际上并没有释放 C 节点的内存，因此这不是最佳实践，因为这样会导致内存泄漏)您应该在 C 节点上使用 free() 方法.
这是我最终使用的代码
struct node* DeleteNode(struct node* head, int pos) {结构节点*临时=头；int length = LinkedListLength(temp);国际我;if(pos <= 0 || pos > 长度){printf("错误:节点不存在！
");}别的{如果(位置 == 1){头=头->下一个;//从头(第一个节点)移动到第二个节点}别的{for(i = 1; i < pos-1; ++i){//在列表中移动temp = temp->next;}temp->next = temp->next->next;}}回头；}希望这有助于了解我是如何修复它的.
////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////
原帖
/////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////>
注意:这是我花了几天(估计 4 小时)编程的家庭作业，我只是停留在这一部分.你可以在下面查看我的尝试
我已经能够从头/尾插入和删除，但是我似乎无法让我在链表中位置 N 的删除节点工作.
我的伪代码如下所示:
- 链表:1,3,5,7,9,23
- 抓取链表
- 创建新的结构节点 A = head
- 在链表中移动直到位置
- 将节点分配给节点->下一步
- 返回链表
示例输入
节点结构整数数据；结构节点*下一个；整数值[] = {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 但是，它用 0 替换第一个节点
实际代码:
struct node* DeleteNode(struct node* head, int pos) {结构节点*临时=头；结构节点*新节点=头；整数长度；国际我;printf("DeleteNode: position = %d
Before:", pos);打印列表(临时)；if(pos <= 0){//节点不存在printf("错误:节点不存在！
");}else{//节点确实存在长度 = LinkedListLength(temp);if(length < pos){//如果长度 <位置节点不存在printf("错误:节点不存在！
");}别的{如果(位置 == 0){newNode = temp->next;}else if(pos == 1){newNode = temp->next;}别的{for(i = 1; i next;newNode->next;}if(temp->next == NULL){新节点 = NULL;}别的{newNode = temp->next;}}printf("之后:");打印列表(新节点)；printf("
");}}返回新节点；} 编辑 #2:代码错别字
提前感谢您的任何帮助.从我得出的结论来看，我的问题是我没有正确浏览列表，但我不确定为什么我没有.
在你的代码中，你有一行
newNode->next;在您的 for 循环中.该操作没有任何作用.
你也有
newNode->= 空；这不是有效的 C，我不知道你是如何编译它的.
但是真的，不要使用那个循环.链表是最基本的递归数据结构之一.因此，几乎所有操作它们的算法都是最优雅的递归解决方案.
typedef struct node node_t;node_t* delete_at_index(node_t* head, unsigned i){node_t* 下一个；如果(头 == NULL)回头；下一个=头->下一个；返回 i == 0?(free(head), next)/* 如果 i == 0，第一个元素需要死亡.做吧.*/: (head->next = delete_at_index(next, i - 1), head);/* 如果它不是第一个元素，我们递归检查其余元素.*/}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.
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||
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.
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.
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!
");
}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
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.
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
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
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
Before: ", pos);
PrintList(temp);
if(pos <= 0){ //node does NOT exist
printf("ERROR: Node does not exist!
");
}else{ //node DOES exist
length = LinkedListLength(temp);
if(length < pos){ //if length < position Node does not exist
printf("ERROR: Node does not exist!
");
}else{
if(pos == 0){
newNode = temp->next;
}else if(pos == 1){
newNode = temp->next;
}else{
for(i = 1; i < pos; i++){
printf("i = %d
", i);
temp = temp->next;
newNode->next;
}
if(temp->next == NULL){
newNode = NULL;
}else{
newNode = temp->next;
}
}
printf("After: ");
PrintList(newNode);
printf("
");
}
}
return newNode;
}
EDIT #2: Code typo
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.
In your code, you have the line
newNode->next;
in your for loop. That operation doesn't do anything.
You also have
newNode-> = NULL;
which is not valid C, and I have no idea how you got that to compile.
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. */
}
这篇关于C编程链表删除位置N处的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
