用与n无关的方法删除队列的特定元素？
本帖最后由 小X学X森 于 2017-11-16 10:33 编辑给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的
typedef int ElementType;
struct ListNode
{
struct ListNode *m_pNext;
ElementType m_Data;
};
void DeleteNode(ListNode *pListHead, ListNode *pToBeDeleted)
{
assert(pListHead != NULL && pToBeDeleted != NULL);
if (pToBeDeleted->m_pNext != NULL) //说明还有后继结点
{
ListNode *pTmp = pToBeDeleted->m_pNext;
//直接把后一个结点赋值给要删除的结点
pToBeDeleted->m_Data = pTmp->m_Data;
pToBeDeleted->m_pNext = pTmp->m_pNext;
//然后删除下一个结点
free(pTmp);
}
else if (pListHead != pToBeDeleted) //如果没有后继结点，而且不是头结点
{
ListNode *pTmp = pListHead;
while (pTmp != NULL)
{
//找到要删除结点的前一个
if (pTmp->m_pNext = pToBeDeleted)
{
//删除pToBeDeleted结点
pTmp->m_pNext = pToBeDeleted->m_pNext;
free(pToBeDeleted);
break;
}
}
}
else //说明程序只有头结点，删除的也是头结点
{
free(pToBeDeleted);
pListHead = NULL; //这里这个形参被办法返回，所以这个函数的参数定义的有点问题
}
}
本帖最后由 小X学X森 于 2017-11-16 10:35 编辑
新手求帮助最好写下代码，嫌烦的话给点思路也可以 用无限循环依次遍历各个节点，对数据和目标进行匹配判断，判断成功就删去该节点，然后跳出循环 本帖最后由 小X学X森 于 2017-11-16 12:31 编辑
BngThea 发表于 2017-11-16 11:13
用无限循环依次遍历各个节点，对数据和目标进行匹配判断，判断成功就删去该节点，然后跳出循环
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢 小X学X森 发表于 2017-11-16 12:25
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢
看你给的函数形参形式，应该是操作一个链表吧，所以中间删去一个节点应该很容易办到
而题目中强调了是队列中的一个特定的元素，所以目标元素肯定是存在于队列中的 遍历链表，如果发现链表某个节点和该待删节点的属性匹配，删除之。
具体图为：
https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1510825716611&di=b08c612957692ede71abe94545b76c83&imgtype=0&src=http%3A%2F%2Fpic002.cnblogs.com%2Fimages%2F2010%2F27612%2F2010101713455649.png 如果只是链表，做不到与n无关。
不过 python里有 OrderedDict，有序字典。
它既像字典那样直接操作元素，又像链表那样保持元素的插入次序。 小X学X森 发表于 2017-11-16 12:25
队列不能在中间直接删除一个元素的吧？可是如果队列中没有这个点的话要怎么退出循环呢
if(前驱->next->data==特定) {
temp=前驱->next
前驱->next =前驱->next->next
free(temp); } ＜（￥＿＄）＞ 发表于 2017-11-19 12:46
给你一个时间复杂度为o(1)的方案，还没调试，大概思路是这样的
没看出来，怎么就O(1) 了？ SixPy 发表于 2017-11-23 12:39
没看出来，怎么就O(1) 了？
如果不是尾节点，只要将后一个结点赋值给要删除的结点，然后删除后一个结点，这个时间复杂度为o(1)应该没什么疑问，对于尾节点，那遍历时跑不掉了，那对于尾节点来说，时间复杂度为o(n)，那总的时间复杂度为o(1)应该就没啥疑问了吧
页:
[1]