将双链表中值为x的节点置为首节点

朴灿烈づ我的快乐病毒、 2022-07-27 14:34 76阅读 0赞

问题及代码：

/*
    *Copyright (c)2016,烟台大学计算机与控制工程学院
    *All rights reserved.
    *文件名称：table.cpp
    *作    者：单昕昕
    *完成日期：2016年3月23日
    *版 本 号：v1.0
    *
    *问题描述：将双链表中值为x的节点置为首节点。
    *程序输入：无。
    *程序输出：双链表。
    */
    #include <iostream>
    #include <malloc.h>
    using namespace std;
    
    typedef struct DNode
    {
        int data;
        int freq;
        struct DNode *next;
        struct DNode *prior;
    } DinkList;
    
    void LocateNode(DinkList *&h,int x)
    {
        DinkList *p,*q;
        p=h->next;
        int i=0,j=0;
        //查找x所在的位置
        while(p!=NULL&&p->data!=x)
        {
            p=p->next;
            ++i;
        }
        //删除x节点
        p=h;
        while(j<=i-1&&p!=NULL)
        {
            ++j;
            p=p->next;
        }
        q=p->next;///q=p+1
        p->next=q->next;
        if(p->next!=NULL)
            p->next->prior=p;
        //x插入到头结点位置
        //cout<<p->data<<endl;//4
        //cout<<q->data<<endl;//3
        //cout<<h->next->data<<endl;//9
        q->next=h->next;
        if(h->next!=NULL)
            h->next->prior=q;
        //cout<<h->next->prior->data<<endl;//3
        q->prior=h;
        h->next=q;
    }
    int main()
    {
        DinkList *h,*s;
        h=(DinkList *)malloc(sizeof(DinkList));
        int a[10];
        int i;
        for(i=0; i<10; ++i)//初始化a数组
            a[i]=i;
        h->prior=h->next=NULL;
        for(i=0; i<10; ++i)//头插法
        {
            s=(DinkList *)malloc(sizeof(DinkList));
            s->data=a[i];
            s->next=h->next;
            if(h->next!=NULL)
                h->next->prior=s;
            h->next=s;
            s->prior=h;
        }
        cout<<"原来：";//输出链表
        DinkList *p;
        p=h->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
        int x;
        cout<<"x=";
        cin>>x;
        LocateNode(h,x);//移动x
        cout<<"移动值为"<<x<<"的节点：";
        p=h->next;//输出链表
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
        return 0;
    }

运行结果：

![Center][]

先遍历，找到x节点的位置，再从这个位置删除，最后把这个节点插入到头节点处。

[Center]: /images/20220727/2843fad284ad4295b086720fd5fd2ec2.png