本文主要是介绍C.Interface.And.Implementations—sequence的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、A sequence holds N values associated with the integer indices zero through N−1 when N is positive.
2、An empty sequence holds no values.
3、Like arrays, values in a sequence may be accessed by indexing;
4、they can also be added to or removed from either end of a sequence.
5、Sequences expand automatically as necessary to accommodate their contents. Values are pointers.
6、they can be used as arrays, lists, stacks, queues, and deques, and they often subsume the facilities of separate
ADTs for these data structures.
sequence底层数据结构如下图所示：
其中左边部分阴影为上一节“dynamic array”，length为sequence中目前的元素总共数目，head为array中第一个元素的位置。可以看出，通过循环的dynamic array来实现sequence的。
==========================seq.h=============================
#ifndef SEQ_INCLUDED
#define SEQ_INCLUDED#define T Seq_T
typedef struct T *T;//exported functions
extern T Seq_new (int hint);
extern T Seq_seq (void *x, ...);
extern void Seq_free (T *seq);
extern int Seq_length(T seq);
extern void *Seq_get (T seq, int i);
extern void *Seq_put (T seq, int i, void *x);
extern void *Seq_addlo (T seq, void *x);
extern void *Seq_addhi (T seq, void *x);
extern void *Seq_remlo (T seq);
extern void *Seq_remhi (T seq);#undef T
#endif
======================seq.c==========================
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include "assert.h"
#include "seq.h"
#include "array.h"
#include "arrayrep.h"
#include "mem.h"#define T Seq_Tstruct T{struct Array_T array;int length;int head;
};//static functions
static void expand(T seq){int n = seq->array.length;Array_resize(&seq->array, 2*n);if(seq->head > 0){void **old = &((void **)seq->array.array)[seq->head];memcpy(old+n, old, (n-seq->head)*sizeof(void *));seq->head += n;}
}//functions
T Seq_new(int hint){T seq;assert(hint >= 0);NEW0(seq);if(hint == 0)hint = 16;ArrayRep_init(&seq->array, hint, sizeof(void *),ALLOC(hint*sizeof(void *)));return seq;
}T Seq_seq(void *x, ...){va_list ap;T seq = Seq_new(0);va_start(ap, x);for( ; x; x = va_arg(ap, void *))Seq_addhi(seq, x);va_end(ap);return seq;
}void Seq_free(T *seq){assert(seq && *seq);assert((void *)*seq == (void *)&(*seq)->array);Array_free((Array_T *)seq);
}int Seq_length(T seq){assert(seq);return seq->length;
}void *Seq_get(T seq, int i){assert(seq);assert(i >= 0 && i < seq->length);return ((void **)seq->array.array)[(seq->head + i)%seq->array.length];
}void *Seq_put(T seq, int i, void *x){void *prev;assert(seq);assert(i >= 0 && i < seq->length);prev = ((void **)seq->array.array)[(seq->head + i)%seq->array.length];((void **)seq->array.array)[(seq->head + i)%seq->array.length] = x;return prev;
}void *Seq_remhi(T seq){int i;assert(seq);assert(seq->length > 0);i = --seq->length;return ((void **)seq->array.array)[(seq->head+i)%seq->array.length];
}void *Seq_remlo(T seq){int i = 0;void *x;assert(seq);assert(seq->length > 0);x = ((void **)seq->array.array)[(seq->head+i)%seq->array.length];seq->head = (seq->head + 1)%seq->array.length;--seq->length;return x;
}void *Seq_addhi(T seq, void *x){int i;assert(seq);if(seq->length == seq->array.length)expand(seq);i = seq->length++;return ((void **)seq->array.array)[(seq->head+i)%seq->array.length] = x;
}void *Seq_addlo(T seq, void *x){int i = 0;assert(seq);if(seq->length == seq->array.length)expand(seq);if(--seq->head < 0)seq->head = seq->array.length-1;seq->length++;return ((void **)seq->array.array)[(seq->head+i)%seq->array.length] = x;
}这篇关于C.Interface.And.Implementations—sequence的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
