数据结构(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语言实现)》 杨峰 编著