C语言数据结构之顺序结构（Sequence）
简单的顺序结构，通常称之为序列
定义数据结构struct Sequence，用数组来保存数据！！！结构体成员int *elts，其实是整数数组，只保存整数数据，也只能测试整数！！！实现基本功能，创建、释放、追加、插入、删除、更改、查找、判断、逐项操作等功能sequence_new 创建sequence_free 释放sequence_is_empty 是否为空sequence_is_full 是否已满sequence_append 追加数据sequence_insert 插入数据sequence_remove 删除数据sequence_set 更改数据sequence_get 获取数据sequence_reverse 倒置序列sequence_foreach 对序列进行逐项操作我在每个函数前面加了一个mg_做为自己的命名空间标识，namespace很重要！！！C++中的封装，在C语言中基本可以完成，只要实现了上述功能！！！
代码如下：
/* filename: seq.c */
#include
#include
/* compile : gcc seq.c -o seq
run : ./seq */
/**/
#define SSIZE 32
/* function pointer with int arg and without return */
typedef void (*MgFunc) (int val);
/* define Sequence datatype */
typedef struct _Sequence Sequence;
struct _Sequence {
int *elts; //elements
int size; //size
int maxsize; //maxsize
};
/* create a new sequence */
Sequence *
mg_sequence_new (void)
{
Sequence *seq = (Sequence*) malloc (sizeof(Sequence));
seq->size = 0; seq->maxsize = SSIZE;
seq->elts = (int*) malloc (seq->maxsize * sizeof(int));
return seq;
}
/* free the sequence */
void
mg_sequence_free (Sequence *seq)
{
free (seq->elts);
free (seq);
}
/* sequence is empty return 1 else return 0 */
int
mg_sequence_is_empty (Sequence *seq)
{
if (seq->size == 0) return 1;
return 0;
}
/* sequence is full return 1 else return 0 */
int
mg_sequence_is_full (Sequence *seq)
{
if (seq->size == seq->maxsize) return 1;
return 0;
}
/* append a val into sequence */
void
mg_sequence_append (Sequence *seq, int val)
{
seq->elts[seq->size] = val;
seq->size = seq->size + 1;
if (seq->size >= seq->maxsize)
printf ("Warnning: Sequence is full!\n");
}
/* insert a val at idx into sequence */
void
mg_sequence_insert (Sequence *seq, int idx, int val)
{
for (int i = seq->size - 1; i >= idx; i--)
seq->elts[i+1] = seq->elts[i];
seq->elts[idx] = val;
seq->size = seq->size + 1;
}
/* set a val at idx of sequence */
void
mg_sequence_set (Sequence *seq, int idx, int val)
{
seq->elts[idx] = val;
}
/* remove a val at idx of sequence */
void
mg_sequence_remove (Sequence *seq, int idx)
{
for (int i = idx; i <= seq->size; i++)
seq->elts[i] = seq->elts[i+1];
seq->size = seq->size - 1;
}
/* get a val at idx of sequence */
int
mg_sequence_get (Sequence *seq, int idx)
{
return seq->elts[idx];
}
/* reverse the sequence */
void
mg_sequence_reverse (Sequence *seq)
{
for (int i = 0, j = seq->size - 1; i < seq->size / 2; i++, j--)
{
int tmp = seq->elts[i];
seq->elts[i] = seq->elts[j];
seq->elts[j] = tmp;
}
}
/* call mgfunc on each element */
void
mg_sequence_foreach (Sequence *seq, MgFunc mgfunc)
{
for (int i = 0; i < seq->size; i++)
mgfunc (seq->elts[i]);
}
/* ---------------------------------------- */
/* define function for MgFunc */
void
out_integer (int val)
{
printf ("%d ", val);
}
/**/
int
main (int argc, char *argv[])
{
Sequence *seq = mg_sequence_new ();
for (int i = 0; i < 10; i++)
mg_sequence_append (seq, i + 1000);
printf ("Test sequence new, append, foreach method:\n");
mg_sequence_foreach (seq, out_integer);
printf ("\nTest sequence insert method:\n");
mg_sequence_insert (seq, 5, 8888);
mg_sequence_foreach (seq, out_integer);
printf ("\nTest sequence reverse method:\n");
mg_sequence_reverse (seq);
mg_sequence_foreach (seq, out_integer);
printf ("\nTest sequece remove method:\n");
mg_sequence_remove (seq, 5);
mg_sequence_foreach (seq, out_integer);
printf ("\n");
mg_sequence_free (seq);
return 0;
}
/* -----(:/.^.\:)-----*/
编译运行，结果如下：
songvm@ubuntu:~/works/xdn/soo$ gcc seq.c -o seq
songvm@ubuntu:~/works/xdn/soo$ ./seq
Test sequence new, append, foreach method:
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009
Test sequence insert method:
1000 1001 1002 1003 1004 8888 1005 1006 1007 1008 1009
Test sequence reverse method:
1009 1008 1007 1006 1005 8888 1004 1003 1002 1001 1000
Test sequece remove method:
1009 1008 1007 1006 1005 1004 1003 1002 1001 1000
基本完成了上述功能，并通过测试！！！注意：没有对出错情况做限制！！！
将功能扩展一下，让序列可以保存更多的数据类型
上面的序列只能保存整型数据，完全可以将其改造成保存多种类型数据，就是用void*替换原来的int！！！因为void*和long的sizeof值都是8字节，所以既可以保存指针类型数据也可以保存长整型数据！！！而double的sizeof值也是8字节，所以还可以保存浮点型数据！！！C++中的多态就是这么做的吧？！？不在限制数组的长度，理论上可以无限制分配内存，事实上要根据使用场合来做出限制！！！
代码如下：
/* filename: seqv.c */
#include
#include
/* compile : gcc seqv.c -o seqv
run : ./seqv */
/**/
#define SPSIZE 8
/* function pointer with void* arg and without return */
typedef void (*MgFunc) (void *val);
/* define Sequence datatype */
typedef struct _Sequence Sequence;
struct _Sequence {
int size; //size
int ps; //page size
void **elts; //elements
};
/* create a new sequence */
Sequence *
mg_sequence_new (void)
{
Sequence *seq = (Sequence*) malloc (sizeof(Sequence));
seq->size = 0; seq->ps = 1;
seq->elts = (void**) malloc (seq->ps * SPSIZE * sizeof(void*));
for (int i = 0; i < SPSIZE; i++)
seq->elts[i] = NULL;
return seq;
}
/* free every elements */
void
mg_sequence_free_elements (Sequence *seq)
{
for (int i = 0; i < seq->size; i++)
free (seq->elts[i]);
}
/* free the sequence */
void
mg_sequence_free (Sequence *seq)
{
free (seq->elts);
free (seq);
}
/* sequence is empty return 1 else return 0 */
int
mg_sequence_is_empty (Sequence *seq)
{
if (seq->size == 0) return 1;
return 0;
}
/* sequence is full return 1 else return 0 */
/*int
mg_sequence_is_full (Sequence *seq)
{
if (seq->size == seq->maxsize) return 1;
return 0;
}
*/
/* */
int
mg_sequence_size (Sequence *seq)
{
return seq->size;
}
/* append a val into sequence */
void
mg_sequence_append (Sequence *seq, void *val)
{
seq->elts[seq->size] = val;
seq->size = seq->size + 1;
if (seq->size == seq->ps * SPSIZE)
{
seq->ps = seq->ps + 1;
seq->elts = realloc (seq->elts, seq->ps * SPSIZE * sizeof(void*));
}
}
/* insert a val at idx into sequence */
void
mg_sequence_insert (Sequence *seq, int idx, void *val)
{
for (int i = seq->size - 1; i >= idx; i--)
seq->elts[i+1] = seq->elts[i];
seq->elts[idx] = val;
seq->size = seq->size + 1;
}
/* set a val at idx of sequence */
void
mg_sequence_set (Sequence *seq, int idx, void *val)
{
seq->elts[idx] = val;
}
/* remove a val at idx of sequence */
void
mg_sequence_remove (Sequence *seq, int idx)
{
for (int i = idx; i <= seq->size; i++)
seq->elts[i] = seq->elts[i+1];
seq->size = seq->size - 1;
}
/* get a val at idx of sequence */
void *
mg_sequence_get (Sequence *seq, int idx)
{
return seq->elts[idx];
}
/* reverse the sequence */
void
mg_sequence_reverse (Sequence *seq)
{
for (int i = 0, j = seq->size - 1; i < seq->size / 2; i++, j--)
{
void *tmp = seq->elts[i];
seq->elts[i] = seq->elts[j];
seq->elts[j] = tmp;
}
}
/* call mgfunc on each element */
void
mg_sequence_foreach (Sequence *seq, MgFunc mgfunc)
{
for (int i = 0; i < seq->size; i++)
mgfunc (seq->elts[i]);
}
/* ---------------------------------------- */
/* define function for MgFunc */
void
out_longint (void *val)
{
printf ("%ld ", (long)(val));
}
/**/
void
test_sequence_longint (void)
{
Sequence *seq = mg_sequence_new ();
for (long i = 0; i < 10; i++)
mg_sequence_append (seq, (void*)(i + 1000));
printf ("Test sequence new, append, foreach method:\n");
mg_sequence_foreach (seq, out_longint);
printf ("\nTest sequence insert method:\n");
mg_sequence_insert (seq, 5, (void*)(8888));
mg_sequence_foreach (seq, out_longint);
printf ("\nTest sequence reverse method:\n");
mg_sequence_reverse (seq);
mg_sequence_foreach (seq, out_longint);
printf ("\nTest sequence remove method:\n");
mg_sequence_remove (seq, 5);
mg_sequence_foreach (seq, out_longint);
printf ("\nSequence page size : %d\n", SPSIZE);
printf ("Sequence size : %d\n", seq->size);
printf ("Sequence page : %d\n", seq->ps);
printf ("Sequence val at index 9 is %ld\n", (long)mg_sequence_get(seq, 9));
mg_sequence_free (seq);
}
/*
void
out_string (void *val)
{
printf ("%s ", (char*)val);
}
//
void
test_sequence_string (void)
{
char *buff[6] = {"Not", "Only", "Test", "Here", "Another", "Behind"};
Sequence *seq = mg_sequence_new ();
for (int i = 0; i < 6; i++)
mg_sequence_append (seq, buff[i]);
mg_sequence_foreach(seq, out_string);
printf ("\n");
mg_sequence_free (seq);
}
//
void
test_sequence_string_malloc (void)
{
Sequence *seq = mg_sequence_new ();
for (int i = 1000; i < 1010; i++)
{
char *buf = (char*) malloc (16);
sprintf (buf, "demo-%d", i);
mg_sequence_append (seq, buf);
}
mg_sequence_foreach(seq, out_string);
printf ("\n");
mg_sequence_free_elements (seq);
mg_sequence_free (seq);
}
*/
/**/
int
main (int argc, char *argv[])
{
test_sequence_longint ();
//test_sequence_string ();
//test_sequence_string_malloc ();
return 0;
}
/* -----(:/.^.\:)-----*/
编译运行，结果如下：
songvm@ubuntu:~/works/xdn/soo$ gcc seqv.c -o seqv
songvm@ubuntu:~/works/xdn/soo$ ./seqv
Test sequence new, append, foreach method:
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009
Test sequence insert method:
1000 1001 1002 1003 1004 8888 1005 1006 1007 1008 1009
Test sequence reverse method:
1009 1008 1007 1006 1005 8888 1004 1003 1002 1001 1000
Test sequence remove method:
1009 1008 1007 1006 1005 1004 1003 1002 1001 1000
Sequence page size : 8
Sequence size : 10
Sequence page : 2
Sequence val at index 9 is 1000
songvm@ubuntu:~/works/xdn/soo$
再测试一下序列中保存字符串
将上面代码中的注释去掉sprintf 函数，用printf格式将内容输出到字符串中
代码如下：
/* filename: seqv.c */
#include
#include
/* compile : gcc seqv.c -o seqv
run : ./seqv */
/* Sequence page size */
#define SPSIZE 8
/* function pointer with void* arg and without return */
typedef void (*MgFunc) (void *val);
/* define Sequence datatype */
typedef struct _Sequence Sequence;
struct _Sequence {
int size; //size
int ps; //page size
void **elts; //elements
};
/* create a new sequence */
Sequence *
mg_sequence_new (void)
{
Sequence *seq = (Sequence*) malloc (sizeof(Sequence));
seq->size = 0; seq->ps = 1;
seq->elts = (void**) malloc (seq->ps * SPSIZE * sizeof(void*));
for (int i = 0; i < SPSIZE; i++)
seq->elts[i] = NULL;
return seq;
}
/* free every elements */
void
mg_sequence_free_elements (Sequence *seq)
{
for (int i = 0; i < seq->size; i++)
free (seq->elts[i]);
}
/* free the sequence */
void
mg_sequence_free (Sequence *seq)
{
free (seq->elts);
free (seq);
}
/* sequence is empty return 1 else return 0 */
int
mg_sequence_is_empty (Sequence *seq)
{
if (seq->size == 0) return 1;
return 0;
}
/* sequence is full return 1 else return 0 */
/*int
mg_sequence_is_full (Sequence *seq)
{
if (seq->size == seq->maxsize) return 1;
return 0;
}
*/
/* */
int
mg_sequence_size (Sequence *seq)
{
return seq->size;
}
/* append a val into sequence */
void
mg_sequence_append (Sequence *seq, void *val)
{
seq->elts[seq->size] = val;
seq->size = seq->size + 1;
if (seq->size == seq->ps * SPSIZE)
{
seq->ps = seq->ps + 1;
seq->elts = realloc (seq->elts, seq->ps * SPSIZE * sizeof(void*));
}
}
/* insert a val at idx into sequence */
void
mg_sequence_insert (Sequence *seq, int idx, void *val)
{
for (int i = seq->size - 1; i >= idx; i--)
seq->elts[i+1] = seq->elts[i];
seq->elts[idx] = val;
seq->size = seq->size + 1;
}
/* set a val at idx of sequence */
void
mg_sequence_set (Sequence *seq, int idx, void *val)
{
seq->elts[idx] = val;
}
/* remove a val at idx of sequence */
void
mg_sequence_remove (Sequence *seq, int idx)
{
for (int i = idx; i <= seq->size; i++)
seq->elts[i] = seq->elts[i+1];
seq->size = seq->size - 1;
}
/* get a val at idx of sequence */
void *
mg_sequence_get (Sequence *seq, int idx)
{
return seq->elts[idx];
}
/* reverse the sequence */
void
mg_sequence_reverse (Sequence *seq)
{
for (int i = 0, j = seq->size - 1; i < seq->size / 2; i++, j--)
{
void *tmp = seq->elts[i];
seq->elts[i] = seq->elts[j];
seq->elts[j] = tmp;
}
}
/* call mgfunc on each element */
void
mg_sequence_foreach (Sequence *seq, MgFunc mgfunc)
{
for (int i = 0; i < seq->size; i++)
mgfunc (seq->elts[i]);
}
/* ---------------------------------------- */
/* define function for MgFunc to output long int */
void
out_longint (void *val)
{
printf ("%ld ", (long)(val));
}
/**/
void
test_sequence_longint (void)
{
Sequence *seq = mg_sequence_new ();
for (long i = 0; i < 10; i++)
mg_sequence_append (seq, (void*)(i + 1000));
printf ("Test sequence new, append, foreach method:\n");
mg_sequence_foreach (seq, out_longint);
printf ("\nTest sequence insert method:\n");
mg_sequence_insert (seq, 5, (void*)(8888));
mg_sequence_foreach (seq, out_longint);
printf ("\nTest sequence reverse method:\n");
mg_sequence_reverse (seq);
mg_sequence_foreach (seq, out_longint);
printf ("\nTest sequence remove method:\n");
mg_sequence_remove (seq, 5);
mg_sequence_foreach (seq, out_longint);
printf ("\nSequence page size : %d\n", SPSIZE);
printf ("Sequence size : %d\n", seq->size);
printf ("Sequence page : %d\n", seq->ps);
printf ("Sequence val at index 9 is %ld\n", (long)mg_sequence_get(seq, 9));
mg_sequence_free (seq);
}
/* define function for MgFunc to output char* */
void
out_string (void *val)
{
printf ("%s ", (char*)val);
}
/* */
void
test_sequence_string (void)
{
char *buff[6] = {"Not", "Only", "Test", "Here", "Another", "Behind"};
Sequence *seq = mg_sequence_new ();
for (int i = 0; i < 6; i++)
mg_sequence_append (seq, buff[i]);
mg_sequence_foreach(seq, out_string);
printf ("\n");
mg_sequence_free (seq);
}
/* */
void
test_sequence_string_malloc (void)
{
Sequence *seq = mg_sequence_new ();
for (int i = 1000; i < 1010; i++)
{
char *buf = (char*) malloc (16);
sprintf (buf, "demo-%d", i);
mg_sequence_append (seq, buf);
}
mg_sequence_foreach(seq, out_string);
printf ("\n");
mg_sequence_free_elements (seq);
mg_sequence_free (seq);
}
/**/
int
main (int argc, char *argv[])
{
//test_sequence_longint ();
test_sequence_string ();
test_sequence_string_malloc ();
return 0;
}
/* -----(:/.^.\:)-----*/
编译运行，结果如下：
songvm@ubuntu:~/works/xdn/soo$ gcc seqv.c -o seqv
songvm@ubuntu:~/works/xdn/soo$ ./seqv
Not Only Test Here Another Behind
demo-1000 demo-1001 demo-1002 demo-1003 demo-1004 demo-1005 demo-1006 demo-1007 demo-1008 demo-1009
songvm@ubuntu:~/works/xdn/soo$ valgrind --leak-check=yes ./seqv
==10181== Memcheck, a memory error detector
==10181== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==10181== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==10181== Command: ./seqv
==10181==
Not Only Test Here Another Behind
demo-1000 demo-1001 demo-1002 demo-1003 demo-1004 demo-1005 demo-1006 demo-1007 demo-1008 demo-1009
==10181==
==10181== HEAP SUMMARY:
==10181== in use at exit: 0 bytes in 0 blocks
==10181== total heap usage: 16 allocs, 16 frees, 1,472 bytes allocated
==10181==
==10181== All heap blocks were freed -- no leaks are possible
==10181==
==10181== For counts of detected and suppressed errors, rerun with: -v
==10181== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
songvm@ubuntu:~/works/xdn/soo$
结果如预期！下一步研究字符串！！！