[已解决]用与n无关的方法删除队列的特定元素？

小X学X森

最佳答案

月排行榜 / 总排行榜

＜（￥＿＄）＞

2017-11-16 10:33:22

给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的

1. typedef int ElementType;
   
2. 
   
3. struct ListNode
   
4. {
   
5.     struct ListNode *m_pNext;
   
6.     ElementType m_Data;
   
7. };
   
8. 
   
9. void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
   
10. {
    
11.     assert(pListHead != NULL && pToBeDeleted != NULL);
    
12. 
    
13.     if (pToBeDeleted->m_pNext != NULL) //说明还有后继结点
    
14.     {
    
15.         ListNode *pTmp = pToBeDeleted->m_pNext;
    
16. 
    
17.         //直接把后一个结点赋值给要删除的结点
    
18.         pToBeDeleted->m_Data = pTmp->m_Data;
    
19.         pToBeDeleted->m_pNext = pTmp->m_pNext;
    
20. 
    
21.         //然后删除下一个结点
    
22.         free(pTmp);
    
23.     }
    
24.     else if (pListHead != pToBeDeleted) //如果没有后继结点，而且不是头结点
    
25.     {
    
26.         ListNode *pTmp = pListHead;
    
27. 
    
28.         while (pTmp != NULL)
    
29.         {
    
30.             //找到要删除结点的前一个
    
31.             if (pTmp->m_pNext = pToBeDeleted)
    
32.             {
    
33.                 //删除pToBeDeleted结点
    
34.                 pTmp->m_pNext = pToBeDeleted->m_pNext;
    
35.                 free(pToBeDeleted);
    
36.                 break;
    
37.             }
    
38.         }
    
39.     }
    
40.     else //说明程序只有头结点，删除的也是头结点
    
41.     {
    
42.         free(pToBeDeleted);
    
43.         pListHead = NULL; //这里这个形参被办法返回，所以这个函数的参数定义的有点问题
    
44.     }
    
45. }

复制代码

跳转到最佳答案楼层

＜（￥＿＄）＞

给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的

1. typedef int ElementType;
   
2. 
   
3. struct ListNode
   
4. {
   
5.     struct ListNode *m_pNext;
   
6.     ElementType m_Data;
   
7. };
   
8. 
   
9. void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
   
10. {
    
11.     assert(pListHead != NULL && pToBeDeleted != NULL);
    
12. 
    
13.     if (pToBeDeleted->m_pNext != NULL) //说明还有后继结点
    
14.     {
    
15.         ListNode *pTmp = pToBeDeleted->m_pNext;
    
16. 
    
17.         //直接把后一个结点赋值给要删除的结点
    
18.         pToBeDeleted->m_Data = pTmp->m_Data;
    
19.         pToBeDeleted->m_pNext = pTmp->m_pNext;
    
20. 
    
21.         //然后删除下一个结点
    
22.         free(pTmp);
    
23.     }
    
24.     else if (pListHead != pToBeDeleted) //如果没有后继结点，而且不是头结点
    
25.     {
    
26.         ListNode *pTmp = pListHead;
    
27. 
    
28.         while (pTmp != NULL)
    
29.         {
    
30.             //找到要删除结点的前一个
    
31.             if (pTmp->m_pNext = pToBeDeleted)
    
32.             {
    
33.                 //删除pToBeDeleted结点
    
34.                 pTmp->m_pNext = pToBeDeleted->m_pNext;
    
35.                 free(pToBeDeleted);
    
36.                 break;
    
37.             }
    
38.         }
    
39.     }
    
40.     else //说明程序只有头结点，删除的也是头结点
    
41.     {
    
42.         free(pToBeDeleted);
    
43.         pListHead = NULL; //这里这个形参被办法返回，所以这个函数的参数定义的有点问题
    
44.     }
    
45. }

复制代码

小X学X森

新手求帮助最好写下代码，嫌烦的话给点思路也可以

BngThea

用无限循环依次遍历各个节点，对数据和目标进行匹配判断，判断成功就删去该节点，然后跳出循环

小X学X森

BngThea 发表于 2017-11-16 11:13
用无限循环依次遍历各个节点，对数据和目标进行匹配判断，判断成功就删去该节点，然后跳出循环

队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢

BngThea

小X学X森 发表于 2017-11-16 12:25
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢

看你给的函数形参形式，应该是操作一个链表吧，所以中间删去一个节点应该很容易办到

而题目中强调了是队列中的一个特定的元素，所以目标元素肯定是存在于队列中的

Brance

遍历链表，如果发现链表某个节点和该待删节点的属性匹配，删除之。
具体图为：

                               
登录/注册后可看大图

SixPy

如果只是链表，做不到与n无关。
不过 python里有 OrderedDict，有序字典。
它既像字典那样直接操作元素，又像链表那样保持元素的插入次序。

zqianglh

小X学X森 发表于 2017-11-16 12:25
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢

if(前驱->next->data==特定) {
temp=前驱->next
前驱->next =前驱->next->next
free(temp); }

SixPy

＜（￥＿＄）＞ 发表于 2017-11-19 12:46
给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的

没看出来，怎么就O(1) 了？

＜（￥＿＄）＞

SixPy 发表于 2017-11-23 12:39
没看出来，怎么就O(1) 了？

如果不是尾节点，只要将后一个结点赋值给要删除的结点，然后删除后一个结点，这个时间复杂度为o(1)应该没什么疑问，对于尾节点，那遍历时跑不掉了，那对于尾节点来说，时间复杂度为o(n)，那总的时间复杂度为o(1)应该就没啥疑问了吧