Doubly Linked List,( Aizu - ALDS1_3C )

时间:2022-04-04 07:18:33

题目链接 : https://vjudge.net/problem/Aizu-ALDS1_3_C

注 :双向链表

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h> 
 4 struct Node{
 5     int key;
 6     struct Node *prior,*next;
 7 };
 8 
 9 Node *nil; //创建头节点 
10 
11 Node* list_search(int key) {          //搜索链返回值为节点地址 
12     Node *cur = nil -> next;
13     while(cur -> key != key && cur != nil) {      //当key值与链中某节点key相同或到达nil停止 
14         cur = cur -> next;
15     } 
16     return cur;    
17 }
18 
19 void init() {                              //初始化头节点 
20     nil = (Node *)malloc(sizeof(Node));    //定义一个指针不为其分配内存,需要动态分配内存 
21     nil -> next = nil;
22     nil -> prior = nil;
23 }
24 
25 void print_list() {                        //打印链表 
26     Node *cur = nil -> next;            //从首节点开始打印 
27     int isf = 0;                        //判断空格输出 
28     while(1) {
29         if(cur == nil) break;
30         if(isf++ > 0) printf(" ");
31         printf("%d",cur ->key);
32         cur = cur -> next; 
33     }
34     printf("\n");
35 }
36 void delete_node(Node *t) {
37     if (t == nil) return; //t为头节点不做处理
38     t -> prior -> next = t -> next;
39     t -> next -> prior = t -> prior; 
40     free(t);                      //删除后释放空间 
41 }
42 
43 void delete_frist() {
44     delete_node(nil -> next);
45 }
46 
47 void delete_last() {
48     delete_node(nil -> prior);
49 }
50 
51 void insert(int key) {                     //理解插入方式 
52     Node *x = (Node*)malloc(sizeof(Node));
53     x -> key = key;
54     x -> next = nil -> next;
55     nil -> next -> prior = x;
56     nil -> next = x;
57     x -> prior = nil;
58 }
59 
60 void delete_key(int key) {
61     delete_node(list_search(key));
62 }
63 int main()
64 {
65     int key, n, i;
66     int size = 0;
67     char com[20];
68     int np = 0,nd = 0;
69     scanf("%d",&n);
70     init();
71     for (i = 0;i < n;i++ ) {
72         scanf("%s%d",com,&key);
73         if (com[0] == 'i') { insert(key);np++;size++; }
74         else if(com[0] == 'd') {
75             if (strlen(com) > 6){
76                 if( com[6] == 'F' ) delete_frist();
77                 else if( com[6] == 'L') delete_last(); 
78                 }
79             else{
80                 delete_key(key); nd++;
81             }
82             size--;
83             }
84         }
85     
86     
87     print_list() ;
88     
89     return 0;
90  }