双向循环链表

第五周要求：

（1）void CreateList_R(DuLinkList &L, int n) //对已经初始化的（已经有头结点的）循环双链表插入n个元素。后插法，L为尾指针。

（2）void ListDisplay(DuLinkList L)  //正序显示链表元素数据。L为尾指针。

（3）void ReverseDisplay(DuLinkList L) //逆序显示链表元素数据。L为尾指针。

（4）int MergeList(DuLinkList &La, DuLinkList &Lb) //合并两个循环双链表。要求原有的两个表各自的数据都是递增的，且原来的单个表中不允许有重复数据（但同一个数据可以出现在两个表中）。合并成一个表后的数据依然保持递增，且不允许有重复数据。合并后使用La的头结点，并通过La得到合并后链表的尾指针。函数返回值为合并后表中包含的元素个数。将合并后不再使用的结点空间释放掉。

下面给出存储结构和初始化函数。

typedef struct DuLNode

{

        ElemType data;

        struct DuLNode *prior;

        struct DuLNode *next;

}DuLNode, *DuLinkList;

Status InitList(DuLinkList &L)  //L为尾指针

{

        L = new DuLNode;

        L->next = L;

        L->prior = L;

        return OK;

}

一、后插法

void CreateList_R(DuLinklist &L,int n)  //后插法
{
    DuLNode *r,*p;
    r = L;
    for (int i = 0; i < n; i++)
    {
        p = new DuLNode;
        cin >> p->data;
        r->next = p;
        p->prior = r;
        r = p;
    }
    r->next = L;
    L->prior = r;
    L = r;
    return;
}

二、排序递增

void Order(DuLinklist L)//链表节点排序
{
    DuLNode *p = L->next->next, *q = L->next->next;
    DuLNode *r = NULL;
    if (!p)
        return ;
    int i = 0, temp = 0, flag = 1;
    while (q!=L->next) {
        q = q->next;
        ++i;//数据节点个数i
    }
    while (flag && i >= 0) {//冒泡排序
        flag = 0;
        while (p->next != L->next) {
            if (p->data > p->next->data) {
                temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
                flag = 1;//标志置为1表示本轮有交换
            }
            if (p->data == p->next->data) {//相同数据只保存一个，p1p2向后移一位
                r = new DuLNode;
                r = p->next;
                r->next->prior = r->prior;
                r->prior->next = r->next;
                delete r;
            }
            p = p->next;
        }
        --i;
        p = L->next->next;//重新指向首元结点为下轮准备
    }
    return;
}

三、合并

int MergeList(DuLinklist &La, DuLinklist &Lb)
{
    DuLNode *p,*q;
    q = Lb->next;
    p = q->next;
    Lb->next = La->next;
    La->next = p;
    p->prior = La;
    delete q;
    int n = 0;
    DuLNode *r= Lb->next->next;
    if (!r) return n;
    while (r != Lb->next) {
        r = r->next;
        ++n;//数据节点个数i
    }
    return n;
}

四、顺序显示

void ListDisplay(DuLinklist L)
{
    DuLNode *p = L->next ->next;
    while (!p)
        return ;
    while (p!=L->next )
    {
        cout << p->data;
        p = p->next;
        cout << "   ";
    }
    cout << " 
";
    cout << "--------------------------------------------------------------------
";
    return ;
}

五、逆序显示

void ListDisplay_R(DuLinklist L)
{
    DuLNode *p = L;
    while (!p)
        return;
    while (p != L->next)
    {
        cout << p->data;
        p = p->prior;
        cout << "   ";
    }
    cout << " 
";
    cout << "--------------------------------------------------------------------
";
    return;
}

六、元素个数

int Number(DuLinklist L)
{
    int n = 0;
    DuLNode *p = L->next->next;
    if (!p) return n;
    while (p != L->next) {
        p = p->next;
        ++n;//数据节点个数i
    }
    return n;
}

测试：

int main()
{
    cout << "创建A链表，输入A链表元素个数
";
    int n;
    cin >> n;
    cout << "输入元素数据：
";
    DuLinklist La=NULL;
    InitDuLNode(La);
    CreateList_R(La, n);
    cout << "创建B链表，输入B链表元素个数
";
    int m;
    cin >> m;
    cout << "输入元素数据：
";
    DuLinklist Lb = NULL;
    InitDuLNode(Lb);
    CreateList_R(Lb, m);
    cout << "--------------------------------------------------------------------
";
    cout << "A链表： ";
    Order(La);
    ListDisplay(La);
    cout << "B链表： ";
    Order(Lb);
    ListDisplay(Lb);
    MergeList(La, Lb);//合并后Lb为新链表的尾指针
    Order(Lb);//先排序删掉相同的元素节点再计算个数
    cout << "合并后有" << Number(Lb) << "个元素： ";
    ListDisplay(Lb);
    cout << "逆序为：";
    ListDisplay_R(Lb);
    char ch = _getwch();
}

结果：