有双向循环链表结点定义为:
struct node
{
int data;
struct node *front,*next;
};
有两个双向循环链表A,B,知道其头指针为:pHeadA,pHeadB,请写一函数将两链表中data值相同的结点删除。
用两个向量A_vec、B_vec分别存储链表A、B的元素值,将A_vec、B_vec排序,用类似归并排序的方法把A_vec、B_vec中值相同的元素放到向量common_vec中。分别遍历链表A、B,用二分查找法查看每个节点元素是否在common_vec中。
// 链表结点
template <typename T>
class dc_list_node
{
public:
dc_list_node(const T &item = T(), dc_list_node<T> *p_front = NULL, dc_list_node<T> *p_next = NULL):
m_item(item), mp_front(p_front), mp_next(p_next)
{}
T m_item;
dc_list_node<T> *mp_front;
dc_list_node<T> *mp_next;
private:
dc_list_node(const dc_list_node<T> &);
dc_list_node<T> &operator=(const dc_list_node<T> &);
};
void dc_list_erase_node_with_equal_value(dc_list_node<int> *&p_headA, dc_list_node<int> *&p_headB)
{
if (p_headA == NULL || p_headB == NULL)
return;
// A_vec存储链表A的元素值,B_vec存储链表B的元素值
std::vector<int> A_vec, B_vec, common_vec;
dc_list_node<int> *p_node;
A_vec.push_back(p_headA->m_item);
p_node = p_headA->mp_next;
while (p_node != p_headA)
{
A_vec.push_back(p_node->m_item);
p_node = p_node->mp_next;
}
B_vec.push_back(p_headB->m_item);
p_node = p_headB->mp_next;
while (p_node != p_headB)
{
B_vec.push_back(p_node->m_item);
p_node = p_node->mp_next;
}
// 将A_vec和B_vec排序
std::sort(A_vec.begin(), A_vec.end());
std::sort(B_vec.begin(), B_vec.end());
// 合并A_vec和B_vec相同的元素值到common_vec
std::size_t i = 0, j = 0;
while (i < A_vec.size() && j < B_vec.size())
{
if (A_vec[i] < B_vec[j])
++i;
else if (A_vec[i] > B_vec[j])
++j;
else
{
common_vec.push_back(A_vec[i]);
++i;
++j;
}
}
// 分别遍历链表A和B,删除在元素值common_vec中的结点
p_node = p_headA;
for (i = 0; i < A_vec.size(); ++i)
{
if (std::binary_search(common_vec.begin(), common_vec.end(), p_node->m_item)) // 当前结点是值相同的结点
{
if (p_node == p_headA && p_node->mp_next == p_headA) // 链表中只有头结点一个结点
{
delete p_headA;
p_headA = NULL;
break;
}
else if (p_node == p_headA) // 当前结点是头结点
{
p_headA = p_node->mp_next;
p_headA->mp_front = p_node->mp_front;
p_node->mp_front->mp_next = p_headA;
p_node = p_headA;
}
else
{
dc_list_node<int> *p_next = p_node->mp_next, *p_front = p_node->mp_front;
p_next->mp_front = p_front;
p_front->mp_next = p_next;
delete p_node;
p_node = p_next;
}
}
else
p_node = p_node->mp_next;
}
p_node = p_headB;
for (i = 0; i < B_vec.size(); ++i)
{
if (std::binary_search(common_vec.begin(), common_vec.end(), p_node->m_item)) // 当前结点是值相同的结点
{
if (p_node == p_headB && p_node->mp_next == p_headB) // 链表中只有头结点一个结点
{
delete p_headB;
p_headB = NULL;
break;
}
else if (p_node == p_headB) // 当前结点是头结点
{
p_headB = p_node->mp_next;
p_headB->mp_front = p_node->mp_front;
p_node->mp_front->mp_next = p_headB;
p_node = p_headB;
}
else
{
dc_list_node<int> *p_next = p_node->mp_next, *p_front = p_node->mp_front;
p_next->mp_front = p_front;
p_front->mp_next = p_next;
delete p_node;
p_node = p_next;
}
}
else
p_node = p_node->mp_next;
}
}
分享到:
相关推荐
用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
双向循环链表的基本操作,用C语言编写,包括创建,插入,删除,查找,获值等……
C++实现的带头结点的双向循环链表, 数据结构课设.。
利用双向循环链表来实现对长整数的存储。每个节点只存储四位十进制数字。选择该数据结构来完成长整数的加减运算是因为要对长整数进行运算,需要对长整数进行存储,所以选择用链表对长整数存储,又由于存储的顺序是从...
单链表实现双向循环链表单向链表存在一个弊端就是,当需要获取某个结点p的前驱时,需要从头指针开始遍历链表,获得“前驱”的...在双向链表中有两个指针域,一个是指向前驱结点的prev,一个是指向后继结点的next指针。
一个精简的双向循环链表C语言实现,与大家共享
C语言版双向循环链表,双向循环链表经典程序,用于指针进行编写的C语言程序。。。
double linked list双向循环链表,数据区指针,表头有数据大小
本人自己编写的双向循环链表源码,分享给大家,存在什么问题请指出
用单向链表存储航班信息,双向链表存储乘客信息,并可以订票,退票和查询的航班订票系统!
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法。(Java描述)
双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现 双向循环链表 C++实现
双向循环链表,由包含2个指针的节点组成。 DNode.h,DNode类,继承自Node,增加了一个指针,注意这里继承的类型是protected,只能在本子类中访问父类的protect和public的字段,因为,使用getNextNode方法拿返回值...
数据结构课程设计报告基于双向循环链表的通讯录设计
双向的循环链表的C++源代码 实现正逆序遍历,链表归并,插入,删除,查询等基本操作
双向循环链表的程序,包括循环链表的生成,链表结点的插入和删除。
数据结构课程设计实现双向循环链表,我这有详细的课程设计说明书以及答辩ppt,有需要的可以留言哈 ,仅供参考 嘿嘿
循环双向链表,实现了插入、查找特定的节点、删除等功能,是自己花了半天的时间写完的。