图12-1 包含5个值的环
环 与序列非常相似：它包含N个值，分别关联到整数索引0到N-1（当N为正值时）。空的环不包含任何值。其中的值都是指针。与序列中的值类似，环中的值也可以用索引访问。
不同于序列的是，值可以添加到环中任意位置 ，而环中的任何 值都可以被删除。此外，环中的值还可以重新编号：将环左“旋”，会将每个值的索引减1并对环的长度取模，将环右旋，则将各个索引值加1并对环的长度取模。虽然在环中可以在任意位置添加/删除值，但这种灵活性的代价是，访问第i个值不保证在常数时间内完成。
顾名思义，环是双链表的抽象，但Ring ADT只披露了一点点信息，即环是一个不透明指针类型的实例：
〈ring.h 〉≡ #ifndef RING_INCLUDED #define RING_INCLUDED #define T Ring_T typedef struct T *T; 〈exported functions 131〉 #undef T #endif
向该接口中任何例程传递的T值为NULL，都是已检查的运行时错误。
环通过下列函数创建，与Seq接口中类似的函数相对应：
〈exported functions
131〉≡
extern T Ring_new (void);
extern T Ring_ring(void *x, ...);
Ring_new创建并返回一个空环。Ring_ring创建并返回一个环，用函数的非NULL指针参数来初始化环中的值。参数列表结束于第一个NULL指针参数。因而
Ring_T names;
...
names = Ring_ring("Lists", "Tables", "Sets", "Sequences", "Rings", NULL);
会用给出的五个值创建一个环，并将其赋值给names。参数列表中的值将关联到索引0～4。Ring_ring的参数列表的可变部分传递的指针假定为void指针，因此在传递char或void以外的指针时，程序员必须提供转换，参见7.1节。Ring_new和Ring_ring可能引发Mem_Failed异常。
〈exported functions
131〉+≡
extern void Ring_free (T *ring);
extern int Ring_length(T ring);
Ring_free释放*ring指定的环并将*ring清零。如果ring或*ring是NULL指针，则为已检查的运行时错误。Ring_length返回ring中值的数目。
在长度为N的环中，各个值分别关联到整数索引值0到N-1。这些值通过下列函数访问：
〈exported functions
131〉+≡
extern void *Ring_get(T ring, int i);
extern void *Ring_put(T ring, int i, void *x);
Ring_get返回ring中的第i个值。Ring_put将ring中第i个值改为x，并返回原值。i等于或大于N将造成已检查的运行时错误。
通过下列函数，可以向环中任何位置添加值：
〈exported functions
131〉+≡
extern void *Ring_add(T ring, int pos, void *x);
Ring_add将x添加到ring中的pos位置处，并返回x。在一个N值环中，位置指定了值之间 的地点，如图12-1所示，其中给出了一个包含5个值（整数0～4）的环。
图12-1 包含5个值的环
中间一行数字是索引，上面一行是正位置，下面一行是非正位置。非正位置指定了从环末尾算起的各个地点，不需要了解环的长度。对空环来说，位置0和1也是有效的。Ring_add可以接受两种形式的位置。指定不存在的位置（包括正位置大于环长度加1，或负位置绝对值大于环的长度），是已检查的运行时错误。
添加一个新值，会将其右侧所有值的索引加1，并将环的长度加1。Ring_add可能引发Mem_Failed异常。
下列各函数
〈exported functions
131〉+≡
extern void *Ring_addlo(T ring, void *x);
extern void *Ring_addhi(T ring, void *x);
等效于Seq接口中名称相似的对应函数。Ring_addlo等效于Ring_add(ring, 1, x)，而Ring_addhi等效于Ring_add(ring, 0, x)。Ring_addlo和Ring_addhi可能引发Mem_Failed异常。
下列函数
〈exported functions
131〉+≡
extern void *Ring_remove(T ring, int i);
删除并返回ring中的第i个值。删除值，会将其右侧剩下的值的索引都减1，并将环的长度减1。i大于或等于ring的长度，是已检查的运行时错误。
与Seq接口中名称相似的函数类似，下列各函数
〈exported functions
131〉+≡
extern void *Ring_remlo(T ring);
extern void *Ring_remhi(T ring);
删除并返回位于ring的低/高端的值。Ring_remlo等效于Ring_remove(ring, 0)，而Ring_remhi等效于Ring_remove(ring, Ring_length(ring)-1)。向Ring_remlo或Ring_remhi传递空环，是已检查的运行时错误。
“环”这个名称来自下列函数
〈exported functions
131〉+≡
extern void Ring_rotate(T ring, int n);
该函数左“旋”或右“旋”ring，将其中的值重新编号。如果n为正值，ring向右旋转n个值（顺时针），各个值的索引加n然后对ring的长度取模。将一个包含字符串A到H的八值环，向右旋转3个位置，如图12-2所示，箭头指向第一个元素。
图12-2 向右旋转3个位置的八值环
如果n为负值，ring向左转旋转n个值（逆时针），各个值的索引减n然后对环的长度取模。如果n模环的长度得0，那么Ring_rotate没有效果。n的绝对值大于ring的长度，是已检查的运行时错误。
本实现将环表示为一个包含两个字段的结构：
〈ring.c 〉≡ #include <stdlib.h> #include <stdarg.h> #include <string.h> #include "assert.h" #include "ring.h" #include "mem.h" #define T Ring_T struct T { struct node { struct node *llink, *rlink; void *value; } *head; int length; }; 〈functions 134〉
head字段指向由node结构构成的一个双链表，node结构中的value字段保存了环中的值。head指向关联到索引0的值，后续值保存在通过rlink字段链接的各结点中，各结点的llink字段指向其前趋。图12-3给出了一个六值环的结构。虚线从llink字段发出，按逆时针方向环行，实线从rlink字段发出，按顺时针方向环行。
图12-3 包含6个元素的环
空环的length字段为0，head字段为NULL，即为Ring_new的返回值：
〈functions
134〉≡
T Ring_new(void) {
T ring;
NEW0(ring);
ring->head = NULL;
return ring;
}
Ring_ring首先创建一个空环，然后调用Ring_addhi将Ring_ring的各个指针参数添加到环的末尾，直至遇到第一个NULL指针：
〈functions
134〉+≡
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;
}
释放环时，首先释放各个node结构实例，而后释放Ring_T结构实例（即环的首部）。释放结点的次序并不重要，因此Ring_free只是按照rlink指针的方向释放各个结点。
〈functions
134〉+≡
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);
}
下列函数
〈functions
134〉+≡
int Ring_length(T ring) {
assert(ring);
return ring->length;
}
返回环中的值的数目。
Ring_get和Ring_put都必须找到环中的第i个值。这等效于遍历链表到第i个node结构实例，由下列代码块完成。
〈q ← ith node
136〉≡
{
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;
}
该代码循最短路径找到第i个结点：如果i不大于环长度的一半，则代码经由第一个for循环，通过rlink指针按顺时针方向找到想要的结点。否则，代码经由第二个for循环，通过llink指针按逆时针方向找到目标结点。例如，在图12-3中，值0到3可沿顺时针方向找到，值4和5则需沿逆时针方向找到。
给出该代码块之后，Ring_get和Ring_put两个访问函数很容易实现：
〈functions 134〉+≡ void *Ring_get(T ring, int i) { struct node *q; assert(ring); assert(i >= 0 && i < ring->length); 〈q ← ith node 136〉 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 136〉 prev = q->value; q->value = x; return prev; }
向环添加值的函数必须分配一个结点，初始化它，并将其插入到双链表中正确的位置。这些函数还必须处理向空环添加结点的情形。Ring_addhi是这些函数中最简单的一个：它将一个新的结点添加到head指向的结点左侧，如图12-4所示。阴影标记出了新结点，右侧图中的加粗线表明了需要改变的链接。以下是代码：
〈functions 134〉+≡ void *Ring_addhi(T ring, void *x) { struct node *p, *q; assert(ring); NEW(p); if ((q = ring->head) != NULL) 〈insert p to the left of q 137〉 else 〈make p ring's only value 137〉 ring->length++; return p->value = x; }
向空环添加一个值很容易：将ring->head指向新的结点，该结点的链接指向结点本身。
〈make p ring's only value 137〉≡ ring->head = p->llink = p->rlink = p;
如图12-4所示，Ring_addhi将q指向环中第一个结点，并将新结点插入到其左侧。这个插入操作涉及初始化新结点的链接，以及重定向q的llink和q的前趋结点的rlink：
〈insert p to the left of q 137〉≡ { p->llink = q->llink; q->llink->rlink = p; p->rlink = q; q->llink = p; }
图12-4 在head的左侧插入一个新结点
图12-5的系列图中第二到第五幅图，分别说明了这四个语句各自的效果。在每一步，加重的弧线表示新的链接。当q指向双链表中唯一的结点时，重新绘制此系列图是很有裨益的，留给读者完成。
Ring_addlo几乎同样容易，但新添加的结点会变为环中第一个 结点。要完成这个转换，可以首先调用Ring_addhi，然后将环右旋一个位置（即将head设置为其前趋）：
〈functions
134〉+≡
void *Ring_addlo(T ring, void *x) {
assert(ring);
Ring_addhi(ring, x);
ring->head = ring->head->llink;
return x;
}
Ring_add是向环添加值的三个函数中最复杂的，因为它需要处理前一节描述的任意位置，其中包括向环的两端添加值的情形。向环的两端添加值的特例可通过Ring_addlo和Ring_addhi处理（空环的处理亦涵盖于其中），首先通过位置值得到该位置右侧 的值的索引，然后将新结点添加到其左侧，如上文的代码块所述。
图12-5 向q的左侧插入一个新结点
〈functions 134〉+≡ 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 136〉 NEW(p); 〈insert p to the left of q 137〉 ring->length++; return p->value = x; } }
前两个if语句涵盖了对环两端的位置的处理。对i的初始化，处理了对应于索引1到ring->length-1的位置。
删除值的三个函数比添加值的函数要容易，因为边界条件更少一些，唯一的边界条件是删除环中最后一个值时。Ring_remove是三个函数中最通用的：它找到第i个结点，并将其从双链表中删除：
〈functions 134〉+≡ 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 node 136〉 if (i == 0) ring->head = ring->head->rlink; x = q->value; 〈delete node q 139〉 return x; }
如果i是0，Ring_remove会删除第一个结点，因而必须将head重定向到下一个结点。
添加一个结点涉及四次指针赋值，删除一个结点只需要两次：
〈delete node
q 139〉≡
q->llink->rlink = q->rlink;
q->rlink->llink = q->llink;
FREE(q);
if (--ring->length == 0)
ring->head = NULL;
图12-6中的第二和第三幅图，分别说明了该代码块开头两个语句各自的效果。受到影响的链接以加重弧线显示。<delete node q 194>中的第三个语句会释放结点，最后两个语句将ring的length字段减1，如果刚好删除了环中最后一个结点，则将head指针置为NULL。同样，对于从单结点和两结点环中删除结点的情形来说，重新绘制该序列图也是有裨益的。
Ring_remhi的实现类似，但更容易查找要删除的结点：
〈functions 134〉+≡ 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 q 139〉 return x; }
图12-6 删除结点
如上所示，Ring_addlo的实现是通过调用Ring_addhi并将ring的head字段指向其前趋。可以用“对称”（指步骤相反，如同镜像对称）的惯用法来实现Ring_remlo：将ring的head指向其后继，然后调用Ring_remhi即可。
〈functions
134〉+≡
void *Ring_remlo(T ring) {
assert(ring);
assert(ring->length > 0);
ring->head = ring->head->rlink;
return Ring_remhi(ring);
}
最后一个操作是对环进行旋转。如果n是正值，那么将顺时针方向旋转一个N值环，这意味着索引为n模N的值将成为新的head。如果n是负值，那么环将逆时针旋转，这意味着head将移动到索引为n + N的值。
〈functions 134〉+≡ 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; else i = n + ring->length; 〈q ← ith node 136〉 ring->head = q; }
这里使用代码块<q←ith node 136>，确保了旋转沿最短路径进行。
[Knuth，1973a]和[Sedgewick，1990]两书都详细阐述了操作双链表的算法。
Icon中提供的一些向列表删除和添加值的操作，与Ring提供的操作类似。习题12.4探讨了Icon的实现。Ring_add中指定位置的方案，即取自Icon。
12.1 重写Ring_free中的循环，消除对变量n的使用，使用链表结构确定循环何时结束。
12.2 仔细考察Ring_rotate的实现。解释第二个if语句的后项为何必须写作i=n+ring->length。
12.3 对Ring_get(ring, i)的调用通常会后接另一个调用，如Ring_get(ring, i+1)。修改环的实现，使得环能够记录最近访问的索引及对应结点，并在可能的情况下使用该信息，以避免<q←ith node 136>中的循环。在添加或删除值时，不要忘记更新该信息。对此设计一个测试程序，测量此项改进带来的好处。
12.4 Icon实现了列表，它类似于环，是数组的双链表，每个数组包含N个值。这些数组用作环形缓冲区，类似Seq实现中的数组。查找第i个值，通常需要在列表中遍历i/N个数组，然后计算第i个值在目标数组中的索引。添加一个值，或者将其添加到某个现存数组中的空槽位，或者需要添加一个新数组。删除一个值，将使数组中空出一个槽位，如果该值是数组中最后一个值，那么将数组从列表中删除并释放。该表示比本章描述的实现更为复杂，但对大的环来说，其性能更好。使用该表示重新实现环，并测量这两个实现的性能。需要多大的环，才能检测到改进带来的好处？