如何从列表L1中删除要在有序列表L2中找到其位置的节点? [英] How I delete from list L1 nodes whose position are to be found in an ordered list L2?
问题描述
struct 节点* DeleteNode( struct 节点*头， int pos){
struct 节点* temp =头；
int length = LinkedListLength(temp);
int i;
如果(pos < = 0 | | | pos > 长度){
printf(" )；
} 其他 {
如果(pos == 1 ){
头=头->下一个;
} 其他 {
for (i = 1 ; i >< pos-1; ++ i){
temp = temp-> next;
}
temp-> next = temp-> next-> next;
}
}
返回头；
}
您已经提供了问题的解决方案.功能
DeleteNode (struct node* head, int pos)
已经完成了大部分您想做的事情.它从作为参数head传递的列表中删除索引(基于1的索引)的节点.您要做的就是循环遍历第二个包含要删除的索引的列表，并为第二个列表中的每个元素调用DeleteNode.因此，您最终得到如下代码:
struct node* p; for (p = list2Head; p != NULL; p = p->next) DeleteNode (list1Head, p->value);
但是在开始之前，我想对您的函数DeleteNode进行简短的讨论.
(1)我建议将pos定义为从零开始的索引；仅仅是因为这是大多数C程序员习惯的. (不要忘记相应地修改您的第二个列表.)
(2)在函数开始时，调用LinkedListLength以获取该列表中的元素数.这可能需要对列表中的所有元素进行完整循环，从而耗尽许多不必要的CPU内存.而且，您无论如何都要遍历列表，可以轻松避免这种情况.这是合并(1)和(2)之后的代码:
struct node* DeleteNode (struct node* head, int idx) { struct node* temp = head; int i; if (head != NULL && idx == 0) head = head->next; else { // set temp to the node before the node // that should be deleted for (i = 1; i < idx && temp->next; ++i) temp = temp->next; // if we reached the end of the list, idx does // not refer to a valid element if (temp->next == NULL) printf ("ERROR: Node does not exist!\n"); else // remove the node temp->next = temp->next->next; } return head; }
(3)DeleteNode函数总是返回列表的头指针，这不是很有用.它可能应该返回已删除的元素.该元素很可能已被动态分配，因此在删除后必须将其返回到堆中.通过返回其指针，函数的调用者有机会执行必要的free.同时，我们可以删除printf语句，这在低级例程中有点讨厌.并非您的函数的所有未来用户都可能希望您的函数将任何内容打印到标准输出.现在我们返回了Deleted元素，调用者可以通过查看返回的节点指针来检测问题.如果为NULL，则函数失败.
struct node* DeleteNode (struct node* head, int idx) { struct node* delNode = NULL; // check for a valid list if (head == 0) return NULL; if (head != NULL && idx == 0) { delNode = head; head = head->next; } else { // set temp to the node before the node // that should be deleted struct node* p = head; int i; for (i = 1; i < idx && p->next; ++i) p = p->next; // if we reached the end of the list, idx does // not refer to a valid element if (p->next == NULL) return NULL; // remove the node delNode = p->next; p->next = delNode->next; } return delNode; }
我没有测试和调试上面的代码，但只是想传递一些想法来改进您的代码.我建议单步执行代码并包含几个测试用例.
希望对您有帮助. > 如果列表l1 =(abcd)和L2 =(2 3)，我们必须删除两个列表l1的位置，即b和3位置，即列表l1中的c.
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;
}else{
for(i = 1; i < pos-1; ++i){
temp = temp->next;
}
temp->next = temp->next->next;
}
}
return head;
}You have already provided the solution in your question. Function
DeleteNode (struct node* head, int pos)
does already most of what you want to do. It deletes the node with (1-based) indexposfrom the list passed as argumenthead. All you have to do is loop over your second list that contains the indices which are to be deleted and call DeleteNode for every element in your second list. So you end up with code like:
struct node* p; for (p = list2Head; p != NULL; p = p->next) DeleteNode (list1Head, p->value);
But before you go for it, I want to put in a brief discussion of your functionDeleteNode.
(1) I would suggest to define pos as a zero-based index; just because that''s what most C programmers are used to. (Don''t forget to modify your second list accordingly.)
(2) At the start of the function you call LinkedListLength to get the number of elements in that list. This will probably require a full loop over all elements in the list, eating up many unnecessary CPU cylces. And it can easily be avoided as you are going to iterate over the list anyhow. Here is the code after (1) and (2) have been incorporated:
struct node* DeleteNode (struct node* head, int idx) { struct node* temp = head; int i; if (head != NULL && idx == 0) head = head->next; else { // set temp to the node before the node // that should be deleted for (i = 1; i < idx && temp->next; ++i) temp = temp->next; // if we reached the end of the list, idx does // not refer to a valid element if (temp->next == NULL) printf ("ERROR: Node does not exist!\n"); else // remove the node temp->next = temp->next->next; } return head; }
(3) The DeleteNode function always returns the head-pointer of the list, which is not very useful. It probably should return the deleted element. It is very likely that the element has been dynamically allocated and hence must be returned to the heap after removal. By returning its pointer, the caller of the function has a chance to perform the necessaryfree. At the same time we can remove the printf statement, which is kind of nasty in a low level routine. Not all future users of your function may want your function to print anything to stdout. Now that we return the deleted element, the caller can detect the problem by looking at the returned node pointer. If it''s NULL the function has failed.
struct node* DeleteNode (struct node* head, int idx) { struct node* delNode = NULL; // check for a valid list if (head == 0) return NULL; if (head != NULL && idx == 0) { delNode = head; head = head->next; } else { // set temp to the node before the node // that should be deleted struct node* p = head; int i; for (i = 1; i < idx && p->next; ++i) p = p->next; // if we reached the end of the list, idx does // not refer to a valid element if (p->next == NULL) return NULL; // remove the node delNode = p->next; p->next = delNode->next; } return delNode; }
I have not tested and debugged the code above, but just wanted to pass on a couple of ideas how to improve your code. I''d recommend single-stepping through the code with several test cases.
Hope that was helpful.
deleting elements from certain positions in list1.I must create both lists and go to the last element of list l2 and wipe in certain positions in list l1.
if the list l1 = (a b c d) and L2 = (2 3) we have to delete the position of the two lists l1 and that is b and also a 3 position and that is the c in list l1.
这篇关于如何从列表L1中删除要在有序列表L2中找到其位置的节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
