数据结构（1）—顺序表
数据结构就是指计算机内部数据的组织形式和存储方法。常用的数据结构，有：线性结构、树、图等。
线性结构最常用，也是最简单的一种数据结构。所谓线性结构，就是指由 n 个数据元素构成的有限序列。直观来讲，它就是一张有限的一维数表。数组就是一种简单而典型的线性数据结构类型。
线性结构主要包括：顺序表、链表、栈、队列等形式。其中，顺序表和链表是从存储形式上区分的，而栈和队列是从逻辑功能上区分的。也就是说，顺序表和链表是线性数据结构的基础，队列和栈是基于顺序表和链表的，它们由顺序表或链表构成。
有时仅仅用线性结构存储管理数据是难以胜任的，一些数据之间存在着“一对多”的关系，这就构成了所谓的树形结构，简称树结构。例如：人工智能领域常用的“博弈树”，数据挖掘和商业智能中使用的“决策树”，多媒体技术中的“哈夫曼树”等都是应用树结构存储管理数据的实例。
还有一种常用的数据结构叫做图状结构，简称图结构。图结构中数据元素之间存在着“多对多”的关系，因此图结构与树结构相比，其线性结构复杂很多。在处理一些复杂的问题中，图结构往往能派上用场，例如：人工智能领域中的神经网络系统、贝叶斯网络等都是应用图结构存储管理数据的实例。
1. 顺序表
在计算机内部存储一张线性表（线性结构的数表），最为方便简单的就是用一组连续地址的内存单元来存储整张线性表。这种存储结构称为顺序存储结构，这种存储结构下的线性表就叫做顺序表。
从上图可以看出，一张顺序表包括以下特征：
有一个唯一的表名来标识该顺序表；
内存单元连续存储，也就是说，一张顺序表要占据一块连续的内存空间；
数据顺序存放，元素之间由先后关系；
数组满足上述特征，因此，数据本身就是一张顺序表。
2. 创建
创建一张顺序表就是在内存中开辟一段连续的存储空间，并给它一个名字进行标识。只有创建了一个顺序表，才能利用该顺序表存放数据元素，也才能对该顺序表进行各种操作。
有两种创建顺序表的方法：一是静态地定义一张顺序表；二是动态地生成一张顺序表。
静态地定义一张顺序表的方法与定义一个数据的方法类似。描述如下：
#define LIST_MAX_SIZE (10) ///< 顺序表最大元素个数 elem_t sqlist[LIST_MAX_SIZE]; ///< 静态方式
为了更完整、更准确地描述一张顺序表，可以把顺序表定义成上面的代码形式。其中 elem_t 是指定的顺序表类型，这里只是一个抽象的描述，要根据实际情况决定 elem_t 的内容。
动态地生成一张顺序表，描述如下：
#define LIST_MAX_SIZE (10) ///< 顺序表最大元素个数
typedef struct
{
elem_t *elem;
int length; ///< 顺序表的有效元素个数
int list_size; ///< 顺序表占据内存大小，单位：sizeof(elem_t)
} sqlist_t; ///< 顺序表结构体类型
/**
* @brief 插入元素到顺序表
*
* @param *L: 所要操作的顺序表
* @return 返回值：0-失败；1-成功；
*
*/
int init_sqlist (sqlist_t *L)
{
L->elem = malloc (LIST_MAX_SIZE * sizeof (elem_t) );
if (!L->elem)
return 0;
L->length = 0;
L->list_size = LIST_MAX_SIZE;
return 1;
}动态生成一张顺序表，可以分为以下两步骤：
（1）定义一个结构体类型 sqlist_t ，其成员包括：指向顺序表的首地址，顺序表中表的长度（表中元素个数），顺序表的存储空间容量（占据内存大小，以 sizeof(elem_t) 为单元），由 LIST_MAX_SIZE 规定；
（2）通过调用初始化函数 init_sqlist() 实现动态生成一张顺序表。函数 init_sqlist() 的参数是一个 sqlist_t 类型的指针变量，因此可以在函数中直接对顺序表进行操作。
初始化函数 init_sqlist() 的作用是动态初始化一个顺序表，其操作步骤如下：
（1）调用标准库函数 malloc() 动态分配一段长度为 LIST_MAX_SIZE * sizeof(elem_t) 的内存空间，并将这段空间的首地址赋值给变量 L->lelem 。
（2）强 L->length 置为0，表明此时刚刚生成一张空的顺序表。将 L->list_size 置为 LIST_MAX_SIZE，表明该顺序表占据内存空间大小为 LIST_MAX_SIZE （以 sizeof(elem_t) 为单位）。
3. 插入元素
在长度为 n 的顺序表中的第 i 个位置插入新元素 item。
所谓在长度为 n 的顺序表中的第 i 个位置插入新元素，是指在顺序表第 i-1 个数据元素和第 i 个数据元素之间插入一个新元素 item，例如顺序表为：
在第 i 个位置插入新元素 item 后，该顺序表变为：
而此时顺序表 A 的长度由 n 变为 n+1。
顺序表中插入元素代码如下：
#ifdef LINE_TABLE_DYNAMIC_EN
/**
* @brief 插入元素到顺序表
*
* @param *sqlist: 所要操作的顺序表
* @param i_pos: 插入位置所在位置
* @param i_value: 插入元素的值
* @return 返回值：0-失败；1-成功；
*
*/
int insert_elem (sqlist_t *sqlist, int i_pos, elem_t i_value)
{
elem_t *base, *insert_ptr, *p;
// 判断位置是否有效
if (i_pos > sqlist->length )
{
printf ("位置：%d, 顺序表长度：%d，插入数据的位置超过有效位置，无效！\n", i_pos, sqlist->length);
return 0;
}
// 存储空间不够，需要重新动态增加
if (sqlist->length >= sqlist->list_size)
{
base = (elem_t*) realloc (sqlist->elem, (sqlist->length + 10) * sizeof (elem_t) );
sqlist->elem = base;
sqlist->list_size += 10;
}
// 将数据右移，将pos位置腾出来
insert_ptr = & (sqlist->elem[i_pos]);
for(p = & (sqlist->elem[sqlist->length - 1]); p >= insert_ptr; p--)
{
*(p + 1) = *p;
}
// 存储到此位置
*insert_ptr = i_value;
// 顺序表长度加1
sqlist->length += 1;
return 1;
}
#else
/**
* @brief 插入元素到顺序表
*
* @param *sqlist: 所要操作的顺序表
* @param *sqlist_len: 顺序表长度
* @param i_pos: 插入位置所在位置
* @param i_value: 插入元素的值
* @return 返回值：0-失败；1-成功；
*
*/
int insert_elem (elem_t *sqlist, int *sqlist_len, int i_pos, elem_t i_value)
{
int j = 0;
// 判断位置是否有效
if ( (*sqlist_len >= LIST_MAX_SIZE) || (i_pos > *sqlist_len))
{
printf ("位置：%d, 线性表长度：%d，插入数据的位置超过最大值，无效！\n", i_pos, *sqlist_len);
return 0;
}
// 将数据右移，将pos位置腾出来
for (j = (*sqlist_len - 1); j >= i_pos; j--)
{
sqlist[j + 1] = sqlist[j];
}
// 存储到此位置
sqlist[i_pos] = i_value;
// 线性表长度加1
*sqlist_len += 1;
return 1;
}
#endif // LINE_TABLE_DYNAMIC_EN以静态顺序表为例，函数 insert_elem() 的作用为在顺序表 sqlist 中第 i_pos 位置上插入 i_value，并将顺序表长度加 1。具体实现过程如下：
（1）判断插入元素位置的合法性。若有效元素个数大于等于最大长度 LIST_MAX_SIZE（*len >= LIST_MAX_SIZE） 或插入位置在有效元素长度之后 (i_pos > *len)，则非法。
（2）将顺序表中从第 i_pos 位置的元素到第 (*sqlist_len - 1) 位置的元素，均顺序地后移一个位置（备注：i_pos 为顺序表中元素的真实下标，从0位置起始）。
（3）最后，在表的第 i_pos 位置上插入元素 i_value，并将表长加1。
4. 删除元素
删除长度为 n 的顺序表中的第 i 个位置的元素，就是指将顺序表第 i 个位置上的元素去掉，例如顺序表为：
删除第 i 位置的元素后，该顺序表变为：
此时，顺序表A的长度由 n 变为 n - 1。
顺序表中删除元素代码，如下：
#ifdef LINE_TABLE_DYNAMIC_EN
/** @brief 从顺序表中删除元素
*
* @param *sqlist: 所要操作的顺序表
* @param *sqlist_len: 顺序表长度
* @param i_pos: 删除元素所在位置
* @return 返回值：0-失败；1-成功；
*
*/
int delete_elem (sqlist_t *sqlist, int i_pos)
{
elem_t *del_item, *q;
// 判断位置是否有效
if (i_pos >= sqlist->length)
{
printf ("位置：%d, 顺序表长度：%d，删除的位置超过最大值，无效！\n", i_pos, sqlist->length);
return 0;
}
// q指向顺序表表尾
q = sqlist->elem + sqlist->length - 1;
// 将数据左移，将pos位置腾出来
del_item = &(sqlist->elem[i_pos]);
for (++del_item; del_item <= q; ++del_item)
{
*(del_item - 1) = *del_item;
}
// 长度减1
sqlist->length -= 1;
return 1;
}
#else
/** @brief 从顺序表中删除元素
*
* @param *sqlist: 所要操作的顺序表
* @param *sqlist_len: 顺序表长度
* @param i_pos: 删除元素所在位置
* @return 返回值：0-失败；1-成功；
*
*/
int delete_elem (elem_t *sqlist, int *sqlist_len, int i_pos)
{
int j = 0;
// 判断位置是否有效
if (i_pos >= *sqlist_len)
{
printf ("位置：%d, 线性表长度：%d，删除的位置超过最大值，无效！\n", i_pos, *sqlist_len);
return 0;
}
// 将数据左移，将pos位置腾出来
for (j = i_pos; j < (*sqlist_len - 1); j++)
{
sqlist[j] = sqlist[j + 1];
}
// 长度减1
*sqlist_len -= 1;
return 1;
}
#endif // LINE_TABLE_DYNAMIC_EN以静态顺序表为例，函数delete_elem()的作用是从顺序表sqlist中删除第 i 位置的元素，并将表的长度值减 1。实现过程如下：
（1）判断要删除的元素是否合法。对于一个长度为 n 的顺序表，删除元素的合法位置 0 ~ n-1；因此 (i_pos >= *sqlist_len)为非法。
（2）将顺序表的第 i 位置以后的元素依次向前移动，这样会将第 i 位置元素覆盖，也就起到删除第 i 位置元素的作用。
（3）最后长度减 1。
5. 示例
#include <stdio.h>
#include <stdlib.h>
#define LINE_TABLE_DYNAMIC_EN ///< 是否开启动态顺序表
#define LIST_MAX_SIZE (10) ///< 顺序表最大元素个数
typedef struct
{
char value[1]; ///< 此处以char为例
} elem_t; ///< 顺序表元素结构体类型
#ifdef LINE_TABLE_DYNAMIC_EN
typedef struct
{
elem_t *elem;
int length; ///< 顺序表的有效元素个数
int list_size; ///< 顺序表占据内存大小，单位：sizeof(elem_t)
} sqlist_t; ///< 顺序表结构体类型
/**
* @brief 插入元素到顺序表
*
* @param *L: 所要操作的顺序表
* @return 返回值：0-失败；1-成功；
*
*/
int init_sqlist (sqlist_t *L)
{
L->elem = (elem_t*) malloc (LIST_MAX_SIZE * sizeof (elem_t) );
if (!L->elem)
return 0;
L->length = 0;
L->list_size = LIST_MAX_SIZE;
return 1;
}
/**
* @brief 插入元素到顺序表
*
* @param *sqlist: 所要操作的顺序表
* @param i_pos: 插入位置所在位置
* @param i_value: 插入元素的值
* @return 返回值：0-失败；1-成功；
*
*/
int insert_elem (sqlist_t *sqlist, int i_pos, elem_t i_value)
{
elem_t *base, *insert_ptr, *p;
// 判断位置是否有效
if (i_pos > sqlist->length )
{
printf ("位置：%d, 顺序表长度：%d，插入数据的位置超过有效位置，无效！\n", i_pos, sqlist->length);
return 0;
}
// 存储空间不够，需要重新动态增加
if (sqlist->length >= sqlist->list_size)
{
base = (elem_t*) realloc (sqlist->elem, (sqlist->length + 10) * sizeof (elem_t) );
sqlist->elem = base;
sqlist->list_size += 10;
}
// 将数据右移，将pos位置腾出来
insert_ptr = & (sqlist->elem[i_pos]);
for(p = & (sqlist->elem[sqlist->length - 1]); p >= insert_ptr; p--)
{
*(p + 1) = *p;
}
// 存储到此位置
*insert_ptr = i_value;
// 顺序表长度加1
sqlist->length += 1;
return 1;
}
/** @brief 从顺序表中删除元素
*
* @param *sqlist: 所要操作的顺序表
* @param i_pos: 删除元素所在位置
* @return 返回值：0-失败；1-成功；
*
*/
int delete_elem (sqlist_t *sqlist, int i_pos)
{
elem_t *del_item, *q;
// 判断位置是否有效
if (i_pos >= sqlist->length)
{
printf ("位置：%d, 顺序表长度：%d，删除的位置超过最大值，无效！\n", i_pos, sqlist->length);
return 0;
}
// q指向顺序表表尾
q = sqlist->elem + sqlist->length - 1;
// 将数据左移，将pos位置腾出来
del_item = &(sqlist->elem[i_pos]);
for (++del_item; del_item <= q; ++del_item)
{
*(del_item - 1) = *del_item;
}
// 长度减1
sqlist->length -= 1;
return 1;
}
#else
elem_t sqlist[LIST_MAX_SIZE]; ///< 静态方式
/**
* @brief 插入元素到顺序表
*
* @param *sqlist: 所要操作的顺序表
* @param *sqlist_len: 顺序表长度
* @param i_pos: 插入位置所在位置
* @param i_value: 插入元素的值
* @return 返回值：0-失败；1-成功；
*
*/
int insert_elem (elem_t *sqlist, int *sqlist_len, int i_pos, elem_t i_value)
{
int j = 0;
// 判断位置是否有效
if ( (*sqlist_len >= LIST_MAX_SIZE) || (i_pos > *sqlist_len) )
{
printf ("位置：%d, 顺序表长度：%d，插入数据的位置超过最大值，无效！\n", i_pos, *sqlist_len);
return 0;
}
// 将数据右移，将pos位置腾出来
for (j = (*sqlist_len - 1); j >= i_pos; j--)
{
sqlist[j + 1] = sqlist[j];
}
// 存储到此位置
sqlist[i_pos] = i_value;
// 顺序表长度加1
*sqlist_len += 1;
return 1;
}
/** @brief 从顺序表中删除元素
*
* @param *sqlist: 所要操作的顺序表
* @param *sqlist_len: 顺序表长度
* @param i_pos: 删除元素所在位置
* @return 返回值：0-失败；1-成功；
*
*/
int delete_elem (elem_t *sqlist, int *sqlist_len, int i_pos)
{
int j = 0;
// 判断位置是否有效
if (i_pos >= *sqlist_len)
{
printf ("位置：%d, 顺序表长度：%d，删除的位置超过最大值，无效！\n", i_pos, *sqlist_len);
return 0;
}
// 将数据左移，将pos位置腾出来
for (j = i_pos; j < (*sqlist_len - 1); j++)
{
sqlist[j] = sqlist[j + 1];
}
// 长度减1
*sqlist_len -= 1;
return 1;
}
#endif // LINE_TABLE_DYNAMIC_EN
int main ( void )
{
elem_t temp;
elem_t *p_sqlist;
int i, pos;
int *sqlist_len;
char t_str[LIST_MAX_SIZE - 1] = {'H', 'E', 'L', 'L', '0', ',', 'T', 'O', 'M'};
#ifdef LINE_TABLE_DYNAMIC_EN
sqlist_t sqlist;
init_sqlist (&sqlist);
p_sqlist = sqlist.elem;
sqlist_len = &sqlist.length;
#else
int length = 0;
p_sqlist = sqlist;
sqlist_len = &length;
#endif // LINE_TABLE_DYNAMIC_EN
// 产生原始数据
for (i = 0; i < LIST_MAX_SIZE - 1; i++)
{
p_sqlist[i].value[0] = t_str[i];
}
// 元素个数从1开始计数
*sqlist_len = LIST_MAX_SIZE - 1;
// 输出原始数据
printf ("1.原始顺序表内容：\n");
for (i = 0; i < *sqlist_len; i++)
{
printf ("%c ", p_sqlist[i].value[0]);
}
printf ("\n表有效长度：%d，剩余长度：%d\n", *sqlist_len, LIST_MAX_SIZE - *sqlist_len);
// 插入一个元素，从0位置起始计
temp.value[0] = '.';
pos = 9;
printf ("\n2.位置%d插入一个元素后，顺序表内容：\n", pos);
#ifdef LINE_TABLE_DYNAMIC_EN
insert_elem (&sqlist, pos, temp);
#else
insert_elem (p_sqlist, sqlist_len, pos, temp);
#endif // LINE_TABLE_DYNAMIC_EN
for (i = 0; i < *sqlist_len; i++)
{
printf ("%c ", p_sqlist[i].value[0]);
}
printf ("\n表有效长度：%d，剩余长度：%d\n", *sqlist_len, LIST_MAX_SIZE - *sqlist_len);
//删除表中元素
pos = 3;
printf ("\n3.位置%d删除一个元素后，顺序表内容：\n", pos);
#ifdef LINE_TABLE_DYNAMIC_EN
delete_elem (&sqlist, pos);
#else
delete_elem (p_sqlist, sqlist_len, pos);
#endif // LINE_TABLE_DYNAMIC_EN
for (i = 0; i < *sqlist_len; i++)
{
printf ("%c ", p_sqlist[i].value[0]);
}
printf ("\n表有效长度：%d，剩余长度：%d\n", *sqlist_len, LIST_MAX_SIZE - *sqlist_len);
return 0;
}示例运行结果，如下图：
参考来源：
1.《妙趣横生的算法（C语言实现）》 杨峰 编著