首页 > 代码库 > 大平神出的一道双向链表题

大平神出的一道双向链表题

Problem Description

有一个包含n个数字的序列,刚开始时它的第i个数字为i。
光标刚开始指向第一个数字(1),现在我们有如下几种操作:
1 -光标左移(保证左边有数字)。
2 -光标右移(保证右边有数字)。
3 x -在光标前面加入一个数字。
4 x -在光标后面加入一个数字。
5 -删除光标前面的那个数字(保证左边有数字)。
6 -删除光标后面的那个数字(保证右边有数字)。
7 -输出光标所指的数字。

Input

输入2个数字n,m表示该序列有n个数,有m个操作。
接下来有m行,每行表示一个操作。
n<=10^5,m<=10^6。

Output

对于每个操作7,输出答案。

Sample Input

5 10 3 1 2 7 5 3 3 1 7 4 8 2 7

Sample Output

2 3 8
  1 #include<string.h>
  2 #include<malloc.h> /* malloc()等 */
  3 #include<stdio.h> /* EOF(=^Z或F6),NULL */
  4 #include<stdlib.h> /* atoi() */
  5 #include<math.h> /* floor(),ceil(),abs() */
  6 #include <time.h>
  7 /* 函数结果状态代码 */
  8 #define TRUE 1
  9 #define FALSE 0
 10 #define OK 1
 11 #define ERROR 0
 12 #define INFEASIBLE -1
 13 #define OVERFLOW 0
 14 
 15 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
 16 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
 17 typedef int ElemType;
 18 
 19 typedef struct DuLNode
 20 {
 21     ElemType data;
 22     struct DuLNode *prior,*next;
 23 }DuLNode,*DuLinkList;
 24 
 25 void read(int &x){
 26     #define CH getchar()
 27     char ch; x=0;for(ch=CH;ch<0||ch>9;ch=CH);
 28     for(;ch>=0&&ch<=9;x=x*10+ch-48,ch=CH);
 29 }
 30 
 31 inline Status InitList(DuLinkList *L, ElemType e)
 32 {
 33     /* 产生双向循环链表L */
 34     *L=(DuLinkList)malloc(sizeof(DuLNode));
 35     if(*L)
 36     {
 37         (*L)->next=(*L)->prior=*L;
 38         (*L)->data = e;
 39         return OK;
 40     }
 41     else
 42         return OVERFLOW;
 43 }
 44 
 45 inline Status ListInsert(DuLinkList L, ElemType e) /* 改进算法2.18 */
 46 {
 47     /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的合法值为0≤i≤表长+1 */
 48     DuLinkList p,s;
 49     p=L->prior; /* 在L中确定第i个元素的位置指针p */
 50     s=(DuLinkList)malloc(sizeof(DuLNode));
 51     s->data=http://www.mamicode.com/e; /* 在第i-1个元素之后插入 */
 52     s->prior=p;
 53     s->next=p->next;
 54     p->next->prior=s;
 55     p->next=s;
 56     return OK;
 57 }
 58 
 59 inline Status ListDelete(DuLinkList L) /* 算法2.19 */
 60 {
 61     /* 删除带头结点的双链循环线性表L的第i个元素,i的合法值为0≤i≤表长+1 */
 62     DuLinkList p;
 63     p = L;  /* 在L中确定第i个元素的位置指针p */
 64     p->prior->next=p->next;
 65     p->next->prior=p->prior;
 66     free(p);
 67     return OK;
 68 }
 69 
 70 inline void ListShow(DuLinkList L)
 71 {
 72     DuLinkList p = L;
 73     printf("%d\n", p->data);               // 注意换行
 74 }
 75 
 76 int main()
 77 {
 78 //    clock_t start, finish;
 79 //    FILE *fp3;
 80 //    freopen("E:\\zust_train\\作死系列\\other\\other\\A input.txt","r",stdin);
 81 //    freopen("E:\\zust_train\\作死系列\\other\\other\\myans.txt","w",stdout);
 82 //
 83 //    start = clock();
 84     int n, m, s, i, e;
 85     DuLinkList L, p, temp;
 86     while(scanf("%d %d", &n, &m) != EOF){
 87         InitList(&L, 1);
 88         p = L;
 89         for(i = 2; i <= n; i++){
 90             ListInsert(L, i);
 91         }
 92         while(m--){
 93             read(s);
 94             if(s == 1){
 95                 p = p->prior;
 96             }
 97             else if(s == 2){
 98                 p = p->next;
 99             }
100             else if(s == 3){
101                 read(e);
102                 ListInsert(p, e);
103             }
104             else if(s == 4){
105                 read(e);
106                 ListInsert(p->next, e);
107             }
108             else if(s == 5){
109                 ListDelete(p->prior);
110             }
111             else if(s == 6){
112                 ListDelete(p->next);
113             }
114             else if(s == 7){
115                 ListShow(p);
116             }
117         }
118     }
119 //
120 //    finish = clock();
121 //    if((fp3 = fopen("output.txt", "w")) == NULL){
122 //        return 0;
123 //    }
124 //    fprintf(fp3, "%s%lf%c", "耗时: ", (double)finish - start, ‘\n‘);
125 //    fclose(stdin);
126 //    fclose(stdout);
127     return 0;
128 }

 

大平神出的一道双向链表题