双向链表

野性酷女 2022-04-04 05:48 262阅读 0赞

###  ###

题目描述

构建一个双向链表并进行删除和插入操作，按要求输出。

输入

输入：

第一行输入元素个数M

第二行输入M个元素

第三行输入删除位置

第四行输入插入位置和插入元素

第五行输入输出时的起始位置

输出

按要求的起始位置输出链表

样例输入

8  
1 2 3 4 5 6 7 8  
6  
6 6  
5

样例输出

5 6 7 8 1 2 3 4

##### 分析： #####

此题考察链表的多方面知识。我在此题卡了一个早上，真吓人。  
分析一下我卡的原因，一是为考虑根本不需要删除的时候怎么办（即第三行直接换行 ）。然后插入的时候出入的的位置是最后一个数的后面怎么办。

#include"stdio.h"
    #include"string.h"
    typedef struct a{
      long long data;
      long long subscript;
      struct a *pre;
      struct a *next;
    }*LinkList,Node;
    //创建一个链表
    void CreateListTail(LinkList *L,long long n)
    {
        LinkList p,r;
        long long i;
        (*L)=(LinkList)malloc(sizeof(Node));
        r=(*L);
        for(i=1;i<=n;i++)
        {
            p=(LinkList)malloc(sizeof(Node));
            scanf("%lld",&(p->data));
            p->subscript=i;
            p->pre=r;
            r->next=p;
            r=p;
        }
        r->next=(*L)->next;
        (*L)=(*L)->next;
        (*L)->pre=r;
    }
    //删除指点结点
    void Delete(LinkList *L,long long DeleteLocation)
    {
        LinkList pre,T;
        pre=*L;T=*L;
        if(DeleteLocation==1)
        {   T->pre->next=T->next;
            *L=pre->next;
            T->next->pre=T->pre;
    
        }
        else
        {/*while(T->subscript!=DeleteLocation)
        {
            pre=T;
            T=T->next;
        }*/
        DeleteLocation--;
        while(DeleteLocation--)
        {
            pre=T;
            T=T->next;
        }
    
        T->next->pre=pre;
        pre->next=T->next;
        }
    }
    //在指定位置插入一个指定的值
    void Insert(LinkList *L,long long InsertionPosition,long long digit)
    {
        LinkList pre,T,P;
        P=(LinkList)malloc(sizeof(Node));
        P->data=digit;
        P->subscript=InsertionPosition;
        P->next=NULL;
        P->pre=NULL;
        T=*L;
        pre=*L;
        if(InsertionPosition==1)
        {
            T->pre->next=P;
            P->pre=T->pre;
            P->next=T;
            T->pre=P;
            *L=P;
    
    
        }
        else
        {while(T->subscript<InsertionPosition&&pre->subscript<=T->subscript)
        {
            pre=T;
            T=T->next;
        }
        if(pre->subscript>T->subscript)
        {
            P->next=T;
            T->pre=P;
            pre->next=P;
            P->pre=pre;
        }
        else
        {pre->next=P;
        P->pre=pre;
        P->next=T;
        T->pre=P;
        }
        }
    }
    //刷新该结点的链表的位置值
    void Plash(LinkList *L)
    {
        LinkList T;
        long long count=1;
        T=*L;
        T->subscript=count;
        T=T->next;
        while(T!=*L)
        {
            T->subscript=++count;
            T=T->next;
        }
    }
    //从指定的位置输出
    void PUSH(LinkList *L,long long Mark,long long number)
    {
        LinkList T,P;
        T=*L;
        P=T;
       /* while(T->subscript<Mark)
        {
            T=T->next;
        }*/
        Mark--;
        while(Mark--)
        {
            T=T->next;
        }
        P=T->pre;
        while(T!=P)
        {
            printf("%lld ",T->data);
            T=T->next;
        }
    
        printf("%d \n",T->data);
    }
    int main()
    {
        LinkList L,P;
        long long m,i,InsertionPosition,DeleteLocation,digit,Mark,q;
        char DeleteLocation1,c;
        while(~scanf("%lld",&m))
        {  q=0;
            CreateListTail(&L,m);
            scanf("%c",&c);
            scanf("%c",&DeleteLocation1);
            DeleteLocation=DeleteLocation1-'0';
            if(DeleteLocation>=1&&DeleteLocation<=m)
            {Delete(&L,DeleteLocation);q=1;}
    
            Plash(&L);
    
            scanf("%lld%lld",&InsertionPosition,&digit);
    
            Insert(&L,InsertionPosition,digit);
            Plash(&L);
            scanf("%lld",&Mark);
    
            PUSH(&L,Mark,m+q);
    
        }
    }