链表的两种写法

指针实现

1 // 双向链表 2 struct Node { 3     int value; // data 4     Node *prev, *next; // pointers 5 }; 6 Node *head, *tail; 7  8 void initialize() { // create an empty list 9     head = new Node();10     tail = new Node();11     head->next = tail;12     tail->prev = head;13 }14 15 void insert(Node *p, int value) { // insert data after p16     q = new Node();17     q->value = value;18     p->next->prev = q; q->next = p->next;19     p->next = q; q->prev = p;20 }21 22 void remove(Node *p) { // remove p23     p->prev->next = p->next;24     p->next->prev = p->prev;25     delete p;26 }27 28 void recycle() { // release memory29     while (head != tail) {30         head = head->next;31         delete head->prev;32     }33     delete tail;34 }

数组实现

1 // 数组模拟链表 2 struct Node { 3     int value; 4     int prev, next; 5 } node[SIZE]; 6 int head, tail, tot; 7  8 int initialize() { 9     tot = 2;10     head = 1, tail = 2;11     node[head].next = tail;12     node[tail].prev = head;13 }14 15 int insert(int p, int value) {16     q = ++tot;17     node[q].value = value;18     node[node[p].next].prev = q;19     node[q].next = node[p].next;20     node[p].next = q; node[q].prev = p;21 }22 23 void remove(int p) {24     node[node[p].prev].next = node[p].next;25     node[node[p].next].prev = node[p].prev;26 }

邻接表的插入和查找

1 // 邻接表：加入有向边(x, y)，权值为z 2 void add(int x, int y, int z) { 3     ver[++tot] = y, edge[tot] = z; // 真实数据 4     next[tot] = head[x], head[x] = tot; // 在表头x处插入 5 } 6  7 // 邻接表：访问从x出发的所有边 8 for (int i = head[x]; i; i = next[i]) { 9     int y = ver[i], z = edge[i];10     // 一条有向边(x, y)，权值为z11 }

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 using namespace std; 8 const int INF=0x3f3f3f3f; 9 const int maxn=300000+10;10 int n;11 12 struct node {13 int v, index;14 bool operator < (const node &a) const {15 return v
            
              s;19 20 int main() {21 int n;22 scanf("%d", &n);23 int x;24 scanf("%d", &x);25 s.insert((node){x,1});26 for (int i=2; i<=n; ++i) {27 scanf("%d", &x);28 set
             
              ::iterator r=s.lower_bound((node){x,0}), l=r;29 --l;30 if (r==s.end()) {31 printf("%d %d\n", x-(l->v), l->index);32 }33 else if(r==s.begin()) {34 printf("%d %d\n", (r->v)-x, r->index);35 }36 else if (x-(l->v)<=(r->v)-x) {37 printf("%d %d\n", x-(l->v), l->index);38 }39 else {40 printf("%d %d\n", (r->v)-x, r->index);41 }42 s.insert((node){x,i});43 }44 return 0;45 }