【问题描述】输入n个整数,创建一个双向循环链表进行存储。这些整数从第二个开始,递增有序(设a2<a3<…<an) (ai为第i个整数)。试编写程序,创建双向循环链表,依次将输入的整数存储在该链表的各节点中。然后,将第一个结点删除并插入链表中的适当位置,使整个链表递增有序。

【输入形式】先输入整数的个数,再输入整数列。
【输出形式】以整数递增的顺序,依次输出双向循环链表各个节点存储的整数。

【样例输入】5 3 1 2 4 5
【样例输出】1 2 3 4 5

【样例说明】输入数据的第一个数是整数的个数,其后是整数列,该整数列从第二个开始,递增有序,数据间以空格分开。
【评分标准】根据输入的数据创建双向循环链表,并把原来部分有序的链表处理成有序的链表并输出。

 

我猜是这么实现,可能和别的地方不太一样

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,flag=0;
typedef struct Node
{
    int x;
    Node *next;
    Node *pre;
}Node;
int main()
{
    scanf("%d",&n);
    Node *fir=(Node*)malloc(sizeof(Node));
    Node *head=(Node*)malloc(sizeof(Node));
    head->next=fir;
    head->pre=fir;
    fir->next=NULL;
    fir->pre=head;
    scanf("%d",&fir->x);
    Node *p;
    for(int i=2;i<n;i++)
     {
        p=(Node*)malloc(sizeof(Node));
        scanf("%d",&p->x);
        p->pre=head->next;
        (head->next)->next=p;
        head->next=p;
        p->next=NULL;
     }
    p=(Node*)malloc(sizeof(Node));
    scanf("%d",&p->x);
    p->pre=head->next;
    (head->next)->next=p;
    head->next=p;
    p->next=head->pre;
    int j=2;
    if((fir->x)<((fir->next)->x))
     {
        flag=1;
     }
    if(!flag)
     {
        for(Node *i=fir->next;;i=i->next)
         {
            if((fir->x)<((i->next)->x))
             {
                head->pre=fir->next;
                fir->next=i->next;
                fir->pre=i;
                i->next=fir;
                (i->next)->pre=fir;
                break;
             }
        if(j==n-1)
         {
            if((fir->x)>=((i->next)->x))
             {
                head->pre=fir->next;
                fir->next=head->pre;
                fir->pre=i->next;
                (i->next)->next=fir;
              }
            break;
         }
        j++;
        }
     }
     j=1;
     for(Node *i=head->pre;;i=i->next)
      {
        printf("%d ",i->x);
        if(j==n) break;
        j++;
      }
    return 0;
}

分类: OI线性表

欢迎来到睿屿青衫

avatar
 
微笑晕爱心心碎调皮难过尴尬惊讶惊吓酷泪奔吐彩虹害羞敲打喝彩抠鼻吐星星眼擦汗大笑蛋糕呲牙瞌睡咒骂吃瓜贪财骷髅鬼脸委屈奋斗笑哭摸头小纠结点赞笑崩发呆绿帽狂汗亲嘴么么机智抑郁色鄙视坏笑白眼左哼哼右哼哼捂嘴鼓掌可怜香肠嘴闭嘴墨镜认错思考拒绝鲜花愤怒嘟嘴不忍直视嘘emm流泪yeah睡觉扔鞋石化生病抽烟吐血偷笑衰兔牙害怕震惊捂嘴笑打盹疑问亲亲指开心喜欢阴险郁闷坏笑2搞怪汪好奇汪机智汪冷漠汪搞怪哈摆拍柴柴犬生气柴流泪柴张嘴柴挥爪柴佩服勾引拳头胜利赞踩滑稽
  订阅  
提醒