单链表的应用2（单向循环链表变双向循环链表）

落日映苍穹つ 2022-07-26 00:12 229阅读 0赞

假设有一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，他的值为空指针；link为指针域，他指向后继结点。请设计算法，将此表改成双向循环链表。

代码实现：

#include <iostream>
    #include <cstdlib>
    #include <cstdio>
    
    using namespace std;
    
    typedef struct node
    {
        int data;
        struct node *pre;
        struct node *next;
    } LinkTwoList;
    
    LinkTwoList *Create()
    {
        LinkTwoList *head;
        head=(LinkTwoList*)malloc(sizeof(LinkTwoList));
        if(head!=NULL)
        {
            head->pre=NULL;
            head->next=NULL;
            return head;
        }
        else return NULL;
    }
    
    int InsertTwo(LinkTwoList *head,int e)
    {
        LinkTwoList *p;
        LinkTwoList *q=head;
        p=(LinkTwoList*)malloc(sizeof(LinkTwoList));
        if(p!=NULL)
        {
            p->data=e;
            p->pre=NULL;
            p->next=NULL;
            while(q->next!=NULL)
            {
                q=q->next;
            }
            q->next=p;
            return 1;
        }
        return 0;
    }
    
    LinkTwoList* Change(LinkTwoList *head) //变成双向链表后返回一个尾指针
    {
        LinkTwoList *p,*q;
        p=head;
        q=p->next;
        while(q!=NULL)
        {
            q->pre=p;
            p=p->next;
            q=q->next;
        }
        return p;
    }
    
    void Output1(LinkTwoList *head) //从头到尾遍历输出
    {
        LinkTwoList *p;
        p=head->next;
        while(p!=NULL)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }
    
    void Output2(LinkTwoList *tail) //从尾到头遍历输出
    {
        LinkTwoList *p;
        p=tail;
        while(p->pre!=NULL)
        {
            printf("%d ",p->data);
            p=p->pre;
        }
        printf("\n");
    }
    
    void FreeLink(LinkTwoList *head)
    {
        LinkTwoList *p,*q;
        p=head;
        q=NULL;
        while(p!=NULL)
        {
            q=p;
            p=p->next;
            free(q);
        }
    }
    
    int main()
    {
        LinkTwoList *phead,*tail;
        int n,e,flag;
        phead=Create();
        if(phead!=NULL)
        {
            scanf("%d",&n);
            for(int i=0;i<n;i++)
            {
                scanf("%d",&e);
                flag=InsertTwo(phead,e);
            }
            Output1(phead);
            tail=Change(phead);
            Output2(tail);
            FreeLink(phead);
        }
        return 0;
    }