C.Interface.And.Implementations—ring的实现

本文主要是介绍C.Interface.And.Implementations—ring的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1、A ring  is much like a sequence: It holds N values associated with the integer indices zero through N −1 when N is positive. 

2、An empty ring holds no values. Values are pointers. 

3、Like the values in a sequence, values in a ring may be accessed by indexing.

4、Unlike a sequence, however, values can be added to a ring anywhere , and any  value in a ring can be removed. 5、In addition, the values can be renumbered: “rotating” a ring left decrements the index of each value by one modulo the length of the ring; rotating it right increments the indi-ces by one modulo the ring length. 

6、The price for the flexibility of adding values to and removing values from arbitrary locations in a ring is that accessing the  i th value is not guaranteed to take constant time.

简单而言，ring就是一个“环”，底层用“双向链表”进行实现。

                       

在环中的位置定义：

                         

一个带有六个元素的示意图：

插入一个新结点的示意图：

删除结点的示意图：

                     

=========================ring.h=========================

#ifndef RING_INCLUDED
#define RING_INCLUDED#define T Ring_T
typedef struct T *T;//exported functions
extern T     Ring_new   (void);
extern T     Ring_ring  (void *x, ...);
extern void  Ring_free  (T *ring);
extern int   Ring_length(T ring);
extern void *Ring_get   (T ring, int i);
extern void *Ring_put   (T ring, int i, void *x);
extern void *Ring_add   (T ring, int pos, void *x);
extern void *Ring_addlo (T ring, void *x);
extern void *Ring_addhi (T ring, void *x);
extern void *Ring_remove(T ring, int i);
extern void *Ring_remlo (T ring);
extern void *Ring_remhi (T ring);
extern void  Ring_rotate(T ring, int n);#undef T
#endif

========================ring.c=============================

#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include "assert.h"
#include "ring.h"
#include "mem.h"#define T Ring_Tstruct T{struct node{struct node *llink, *rlink;void *value;} *head;int length;
};//functions
T Ring_new(void){T ring;NEW0(ring);ring->head = NULL;return ring;
}T Ring_ring(void *x, ...){va_list ap;T ring = Ring_new();va_start(ap, x);for(; x; x = va_arg(ap, void *))Ring_addhi(ring, x);va_end(ap);return ring;
}void Ring_free(T *ring){struct node *p, *q;assert(ring && *ring);if((p = (*ring)->head) != NULL){int n = (*ring)->length;for(; n-- > 0; p = q){q = p->rlink;FREE(p);}}FREE(*ring);
}int Ring_length(T ring){assert(ring);return ring->length;
}void *Ring_get(T ring, int i){struct node *q;assert(ring);assert(i >= 0 && i < ring->length);//q <- ith node{int n;q = ring->head;if(i < ring->length/2){for(n = i; n-- > 0; )q = q->rlink;}else{for(n = ring->length - i; n-- > 0; )q = q->llink;}}return q->value;
}void *Ring_put(T ring, int i, void *x){struct node *q;void *prev;assert(ring);assert(i >= 0 && i < ring->length);//q <- ith node{int n;q = ring->head;if(i <= ring->length/2){for(n = i; n-- > 0; )q = q->rlink;}else{for(n = ring->length - i; n-- > 0; )q = q->llink;}}prev = q->value;q->value = x;return prev;
}void *Ring_addhi(T ring, void *x){struct node *p, *q;assert(ring);NEW(p);if((q = ring->head) != NULL){p->llink = q->llink;q->llink->rlink = p;p->rlink = q;q->llink = p;}else{ring->head = p->llink = p->rlink = p;}ring->length++;return p->value = x;
}void *Ring_addlo(T ring, void *x){assert(ring);Ring_addhi(ring, x);ring->head = ring->head->llink;return x;
}void *Ring_add(T ring, int pos, void *x){assert(ring);assert(pos >= -ring->length && pos <= ring->length+1);if(pos == 1 || pos == -ring->length)return Ring_addlo(ring, x);else if(pos == 0 || pos == ring->length + 1)return Ring_addhi(ring, x);else{struct node *p, *q;int i = pos < 0 ? pos + ring->length : pos - 1;//q <- ith node{int n;q = ring->head;if(i <= ring->length/2){for(n = i; n-- > 0; )q = q->rlink;}else{for(n = ring->length - i; n-- > 0; )q = q->llink;}}NEW(p);//insert p to the left of q{p->llink = q->llink;q->llink->rlink = p;p->rlink = q;q->llink = p;}ring->length++;return p->value = x;}
}void *Ring_remove(T ring, int i){void *x;struct node *q;assert(ring);assert(ring->length > 0);assert(i >= 0 && i < ring->length);//q <- ith nodeif(i == 0)ring->head = ring->head->rlink;x = q->value;//delete node qq->llink->rlink = q->rlink;q->rlink->llink = q->llink;FREE(q);if(--ring->length == 0)ring->head = NULL;return x;
}void *Ring_remhi(T ring){void *x;struct node *q;assert(ring);assert(ring->length > 0);q = ring->head->llink;x = q->value;//delete node qq->llink->rlink = q->rlink;q->rlink->llink = q->llink;FREE(q);if(--ring->length == 0)ring->head = NULL;return x;
}void *Ring_remlo(T ring){assert(ring);assert(ring->length > 0);ring->head = ring->head->rlink;return Ring_remhi(ring);
}void Ring_rotate(T ring, int n){struct node *q;int i;assert(ring);assert(n >= -ring->length &&n <= ring->length);if(n >= 0)i = n%ring->length;elsei = n + ring->length;//q <- ith node{int n;q = ring->head;if( i <= ring->length/2){for(n = i; n-- > 0; )q = q->rlink;}else{for(n = ring->length - i; n-- > 0; )q = q->llink;}}ring->head = q;
}

这篇关于C.Interface.And.Implementations—ring的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---