时间:2008-05-13 05:39:22   来源:论坛整理  作者:  编辑:chinaitzhe

最近老师要我们做一个如下要求的c语言数据结构题：

以知单链线性表la和lb的元素按值非递减排序，从A链表中删除与B链表中相同的元素。

这下面是我自己编的：因为时间的原因省略的部分明天再补上！
我觉得我编的有点复杂化了，所以希望那位知道的高手能否指点下，想求个简单点的思路！有编的整个过程更好。

还想问下：那个指针的箭头在键盘上怎么简单的输出的啊，（如在下面的（1）处。）

void dellist_l(linklist &la,linklist & lb)
{
//以知单链线性表la和lb的元素按值非递减排序
//从A链表中删除与B链表中相同的元素
pa=la;
pa=lb—next; （1）
……
……
}
网友回复:指针的箭头不就是
->

网友回复:减号 大于号

LZ这个写法有点不明白：
void dellist_l(linklist &la,linklist & lb)
为什么不是
void dellist_l(linklist *la,linklist *lb)

网友回复:靠，什么都不懂就开始写程序了。强
网友回复:呵呵，谢谢上面brookmill 的回答，（在这真是丢人哪，呵呵，上个学期学c 时用过，不过现在不记得了，这就是如今大学缺少实践的结果）
对于brookmill 的疑问解释：我是数据结构没学得好！我见我们书上相应的例子是这么写的，所以我也就这么写了。（至于具体有何不同，我现在也不大记得了。这好象应该不影响最后的结果吧）
至于chlaws 的疑问嘛，因为我们班的状况现在都差不多的不大懂，老师补下了作业就要想办法做完拉，所以，不懂也要摸索着写着去啊！呵呵，（说实话，我们班能自己写出这种程序的人不会超过五分之一）
网友回复:这是我补充昨天的，

void dellist_l(linklist &la,linklist & lb)
{
//以知单链线性表la和lb的元素按值非递减排序
//从A链表中删除与B链表中相同的元素
pa=la;
pb=lb->next;
while(pa->next && pb) //处理la链表除最后一个节点外的所有节点
{
while(pa->next && （pa->next->data <pb->next）)
{
pa=pa->next;
}
while(pa->next && （pa->next->data==pb->next）)
{
q=pa->next;
pa->next=q->next; //从A链表中删除与B链表中相同的元素
free(q);
pa=pa->next; //la链表中可能有相同元数
}
while(pb && （pa->next->data>pb->next）)
{
pb=pb->next;
}
}
//此循环结束后pa指向了最后一个节点
pb=lb->next; //pb重新指向lb链表中的第一个元数
while(pb && (pa->data>pb->data))
pb=pb->next;
while(pa->data==pb->data)
{
……
/*按照我的思路这应该是删除la链表中最后一个节点。但要觉得好象这样做不了，
应该让pa指向最后一个接点的前驱节点才行，又觉得这样做的话，
感觉好象将问题复杂化了。所以我觉得我一开始就好象错了，好象应该弄个前驱节点好点。
所以希望那位高人有简单一点的思路请说一下！先谢谢了！*/
}
free(lb);
}


网友回复:要删除 pa 节点的话，是需要保存 pa 的前驱节点的信息。
网友回复:上面的大哥，这个我知道啊，我想知道有什么好办法可以保存 pa 的前驱节点的信息啊。
网友回复:设置一个临时指针用于保存前驱接点的信息.
网友回复:这个似乎是数据结构上面的某个算法吧。
思路LZ可以参考一下：

以知单链线性表la和lb的元素按值非递减排序，从A链表中删除与B链表中相同的元素。

用la和lb第一个结点做比较，
1.假如la < lb,lb指向下一个结点，继续比较，直到la的结点大小或者等于lb.
2.假如在lb上找到某个结点la > lb，la指向下一个结点，继续比较。
3.假如找到某个结点la == lb.則删除該结点。
4.重复上面三个步骤，直到la或者lb任中一个到达链表结尾。

应该一个循环就可以搞定了吧。
网友回复:在数据结构里面，非递减就是说的递増，即la,lb都是递增链表，把这个想通了，这个东东其实还是挺简单的。
网友回复:magicrobot 你好，你应该没仔细看我在5楼写的吧，我觉得你的第一点和第二点好象搞反了吧！
应该是下面这样吧：
1.假如la > lb,lb指向下一个结点，继续比较，直到la的结点大小或者等于lb.
2.假如在lb上找到某个结点la < lb，la指向下一个结点，继续比较。

下面是我设置一个临时指针用于保存前驱接点后的程序：
即在每个“pa=pa->next;”语句前加入“q=pa;”语句。
（希望大家指点下，看有没有出现什么错误或有什么情况没考虑全面的地方和有没有更简单点的实现方法）



void dellist_l(linklist &la,linklist & lb)
{
//以知单链线性表la和lb的元素按值非递减排序
//从A链表中删除与B链表中相同的元素
pa=la;
pb=lb->next;
while(pa->next && pb) //处理la链表除最后一个节点外的所有节点
{
while(pa->next && （pa->next->data <pb->next）)
{
p=pa;
pa=pa->next;
}
while(pa->next && （pa->next->data==pb->next）)
{
q=pa->next;
pa->next=q->next; //从A链表中删除与B链表中相同的元素
free(q);
p=pa;
pa=pa->next; //la链表中可能有相同元数
}
while(pb && （pa->next->data>pb->next）)
{
pb=pb->next;
}
}
//此循环结束后p指向了最后一个节点的前一个节点
pb=lb->next; //pb重新指向lb链表中的第一个元数
while(pb && (p->data>pb->data))
pb=pb->next;
while(p->data==pb->data)
{
p->next=null;
}
free(lb);
}
网友回复:汗，LZ，在未指定la,lb的时候，这两种情况都是并存的，即第一个结点la > lb或者la < lb。

有个简单的实现如下作作参考：

void dellist_l(linklist *la,linklist *lb)
{
//以知单链线性表la和lb的元素按值非递减排序
//从A链表中删除与B链表中相同的元素
linklist * pa;
linklist * pb;
linklist * prev_node = NULL;

/*假设头结点是保存了数据的情况下*/
pa=la;
pb=lb;
while(pa && pb)
{
if(pa->date > pb->date)
{
pb = pb->next;
continue;
}
else if(pa->date < pa->date)
{
pa = pa->next;
continue;
}
else
{
prev_node = pa;
pa = pa->next;
free(prev_node);
}
}

pa = la;
while(pa)
{
printf("pa->date = %d\r\n", pa->date);
pa = pa->next;
}

}
网友回复:汗，LZ，在未指定la,lb的时候，这两种情况都是并存的，即第一个结点la > lb或者la < lb。

有个简单的实现如下作作参考：

void dellist_l(linklist *la,linklist *lb)
{
//以知单链线性表la和lb的元素按值非递减排序
//从A链表中删除与B链表中相同的元素
linklist * pa;
linklist * pb;
linklist * prev_node = NULL;

/*假设头结点是保存了数据的情况下*/
pa=la;
pb=lb;
while(pa && pb)
{
if(pa->date > pb->date)
{
pb = pb->next;
continue;
}
else if(pa->date < pa->date) /*这句打错了，正确的应该是if(pa->date < pb->date) */
{
pa = pa->next;
continue;
}
else
{
prev_node = pa;
pa = pa->next;
free(prev_node);
}
}

pa = la;
while(pa)
{
printf("pa->date = %d\r\n", pa->date);
pa = pa->next;
}

}
网友回复:非常感谢magicrobot 这位高人！谢谢你提供的思路。我非常有感慨。
一看你这程序就知道是个高人啊，应该写过很多这方面的程序吧。
不知道可以在这加你不，希望能向你学习。
网友回复:magicrobot 你好，
我还有几个疑问：
1）对于你的第一句话：“在未指定la,lb的时候，这两种情况都是并存的，即第一个结点la > lb或者la < lb。 ”我有点不明白：我的意思是那话的本意我知道，我不明白的是我哪里犯了这样的错误吗？

2）对于你的这两句：pa=la; pb=lb;
我觉得它指的意思好象是pa，pb分别指向la,lb的头指针吧，
我觉得这应该是这样的：pa=la->next; pb=lb->next;
这样就分别指向了第一个接点。

希望你能再次解答下
网友回复:1.可能是我看错了。
2.
头指針可以是两种，一种是包含数据的，一种是不包含数据的啊。
我写代码的时候，假设了pa,pb是包含数据的。

但是假如pa,pb仅仅是一个头结点（即不含数据），那就应该为pa=la-> next; pb=lb-> next;
这个需要根据链表的数据来看。