和大家请问一个有关链表的数据结构有关问题(可能很蠢,欢迎拍砖)
和大家请教一个有关链表的数据结构问题(可能很蠢,欢迎拍砖)
我定义了一个单项链表,做了一个以值为条件的删除函数(删除第一次出现对应值的节点),没有使用当前和其之前的两个指针一起移动的方式,而使用了next-> next,不知道能不能从理论上提高程序速度(实际不太好测)?我主想要是指针付值和next-> next的相对速度问题。呵呵!想的不太成熟,请多多指教了!以下附上程序:
struct dNode
{
int data;
struct dNode *pnext;
};
int deleteNode(struct dNode ** headnode,int data)
{
struct dNode *pNode = 0;
struct dNode *dFreeNode = 0;
if(!headnode || !(*headnode))
return 0;
pNode = (*headnode);
if(pNode-> data == data){
*headnode = pNode-> pnext;
free(pNode);
pNode = 0;
return 1;
}
if(!(pNode-> pnext))
return 0;
pNode = (*headnode);
do{
if(pNode-> pnext-> data == data){
dFreeNode = pNode-> pnext;
pNode-> pnext = dFreeNode-> pnext;
free(dFreeNode);
dFreeNode = 0;
pNode = 0;
return 1;
}
pNode = pNode-> pnext;
}while(pNode-> pnext-> pnext);
if(pNode-> pnext-> data == data){
dFreeNode = pNode-> pnext;
pNode-> pnext = 0;
free(dFreeNode);
dFreeNode = 0;
pNode = 0;
return 1;
}
return 0;
}
------解决方案--------------------
你这个做法的效率应该会比使用一个当前指针和一个前向指针的方法低, 一般来说在c语言中(在c++中由于有虚函数,虚继承等的影响会变得复杂一点)增加一个指针赋值与加深一层指针引用的深度的代价差不多,不过对你这个实现而言
pNode-> pnext-> data == data;
pNode-> pnext-> pnext;
这两条语句都增加了深度,而两个指针的方法只会增加一个指针赋值语句,相比而言两个指针的
方法效率要高一些.
------解决方案--------------------
测试结果表明:多一个pNext访问比做一个赋值操作快
------解决方案--------------------
呵呵, 楼主,
好像 数据结构中链表删除算法 就是这个样子的 ···········
------解决方案--------------------
删除节点:
从head 开始寻找指定节点,将该删除节点的前节点的next指针指向节点的后续节点,
然后释放当前的被删除节点。
呵呵,
不正是标准的算法么?
我定义了一个单项链表,做了一个以值为条件的删除函数(删除第一次出现对应值的节点),没有使用当前和其之前的两个指针一起移动的方式,而使用了next-> next,不知道能不能从理论上提高程序速度(实际不太好测)?我主想要是指针付值和next-> next的相对速度问题。呵呵!想的不太成熟,请多多指教了!以下附上程序:
struct dNode
{
int data;
struct dNode *pnext;
};
int deleteNode(struct dNode ** headnode,int data)
{
struct dNode *pNode = 0;
struct dNode *dFreeNode = 0;
if(!headnode || !(*headnode))
return 0;
pNode = (*headnode);
if(pNode-> data == data){
*headnode = pNode-> pnext;
free(pNode);
pNode = 0;
return 1;
}
if(!(pNode-> pnext))
return 0;
pNode = (*headnode);
do{
if(pNode-> pnext-> data == data){
dFreeNode = pNode-> pnext;
pNode-> pnext = dFreeNode-> pnext;
free(dFreeNode);
dFreeNode = 0;
pNode = 0;
return 1;
}
pNode = pNode-> pnext;
}while(pNode-> pnext-> pnext);
if(pNode-> pnext-> data == data){
dFreeNode = pNode-> pnext;
pNode-> pnext = 0;
free(dFreeNode);
dFreeNode = 0;
pNode = 0;
return 1;
}
return 0;
}
------解决方案--------------------
你这个做法的效率应该会比使用一个当前指针和一个前向指针的方法低, 一般来说在c语言中(在c++中由于有虚函数,虚继承等的影响会变得复杂一点)增加一个指针赋值与加深一层指针引用的深度的代价差不多,不过对你这个实现而言
pNode-> pnext-> data == data;
pNode-> pnext-> pnext;
这两条语句都增加了深度,而两个指针的方法只会增加一个指针赋值语句,相比而言两个指针的
方法效率要高一些.
------解决方案--------------------
测试结果表明:多一个pNext访问比做一个赋值操作快
------解决方案--------------------
呵呵, 楼主,
好像 数据结构中链表删除算法 就是这个样子的 ···········
------解决方案--------------------
删除节点:
从head 开始寻找指定节点,将该删除节点的前节点的next指针指向节点的后续节点,
然后释放当前的被删除节点。
呵呵,
不正是标准的算法么?