/*本程序实现在两个循环双链表(head1,head2)中删除相同节点(head3)*/
#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
    int num;
    struct Node *left;
    struct Node *right;
}node;
//打印链表
int show_list(node *head)
{
/*
    node *p=head->left;
    do
    {
        printf("%d \n",p->num);
        p=p->left;
    }while(p!=head->left);
    printf("\n");
    return 0;
*/

    node *p=head;
    do
    {
        printf("%d ",p->num);
        p=p->right;
    }while(p!=head);
    printf("\n");
    return 0;

}
//创建双循环链表
node *creat_list(node *head,int str[],int x)
{
    int i;
    node *p,*q;
    head=(node *)malloc(sizeof(node));
    for(i=0;i<x;i++)
    {
        p=(node *)malloc(sizeof(node));
        p->num=str[i];
        p->right=NULL;
        if(i==0)
        {
            p->left=NULL;
            head=p;
        }
        else
        {
            p->left=q;
            q->right=p;
        }
        q=p;
    }
    q->right=head;
    head->left=q;
    return head;
}
/*查找相同节点*/
node *find_node(node *head,node *p_node)
{
    node *p=head;
    do
    {
        if(p->num==p_node->num)
        {
            return p;
        }
        else
        {
            p=p->right;
        }
    }while(p!=head);
    return NULL;
}
//向相同节点链表插入节点
node *creat_node(node *head,node *p_node)
{
    node *p=NULL;
    node *q=NULL;
    if(head==NULL)
    {
        head=(node *)malloc(sizeof(node));
        p=head;
        p->num=p_node->num;
        p->left=p;
        p->right=p;
        return head;
    }
    else
    {
        q=head;
        while(q->right->num!=head->num)
        {
            q=q->right;
        }
        p_node->right=q->right;//右链接
        q->right->left=p_node;
        p_node->left=q;//左链接
        q->right=p_node;
        return head;
    }
}
//得到相同节点链表
node *get_list(node *head1,node *head2)
{
    node *p=head1,*q=NULL,*head=NULL;
    do
    {
        q=find_node(head2,p);
        if(q!=NULL)
        {
            head=creat_node(head,q);
            /*第二次运行到这里产生无限循环，为什么？求解？难道是head2改变了吗？不会吧？*/
            show_list(head2);
        }
        p=p->right;
    }while(p!=head1);
    return head;
}
/*删除相同节点(前面遇到问题暂未实现)*/
del_node(node *head1,node *head2,node *head3)
{}
int main()
{
    int str1[]={1,2,3,4,6};
    int str2[]={4,5,6,7,8};
    int m=sizeof(str1)/sizeof(str1[0]);
    int n=sizeof(str2)/sizeof(str2[0]);
    node *head1=NULL,*head2=NULL,*head3=NULL;

    head1=creat_list(head1,str1,m);
    head2=creat_list(head2,str2,n);
    head3=get_list(head1,head2);

    printf("链表1:");
    show_list(head1);
    printf("链表2:");
    show_list(head2);

    if(head3==NULL)
    {
        printf("没有相同节点!\n");
    }
    else
    {
        printf("相同节点:");
        show_list(head3);
    }

    del_node(head1,head2,head3);

    printf("链表1:");
    show_list(head1);
    printf("链表2:");
    show_list(head2);
    return 0;
}

下面是对以上程序的大体解释：
head1=creat_list(head1,str1,m);//先创建循环双向链表1(即head1),元素为数组str1中的元素1,2,3,4,6
head2=creat_list(head2,str2,n);//再创建循环双向链表2(即head2),元素为数组str2中的元素4,5,6,7,8
head3=get_list(head1,head2);//找到链表1和链表2中相同的节点，也就是都有的节点，就是4和6,将这些相同的节点组成循环双向链表3(即head3)
del_node(head1,head2,head3);//然后将链表1和链表2中的节点4和6都删去
这时链表1变成1,2,3，链表2变成6,7,8
就是这个过程

get_list()里的show_list(head2)是测试用的，修改正确后注释掉
如果这个程序改好了，最后期望的的结果应该是：
链表1：1,2,3,4,6
链表2：4,5,6,7,8
相同节点：4,6
链表1：1,2,3
链表2：5,7,8

现在遇到的问题是，第二次运行到get_list()函数里的show_list(head2)时产生无限循环，而且是4和6的无限循环。分析分析，就算是这里有错误，也不应该是head2发生变化啊，怎么会产生循环呢？show_list(head2)应该打印出来是4,5,6,7,8啊，怎么会这样，是哪里错了？链表head2到底改变没有？你把这个程序运行了没有？

[ 本帖最后由 小小战士 于 2012-11-11 02:56 编辑 ]