数据结构(1)—顺序表
admin 于 2022年03月06日 发表在 C/C++开发笔记

1. 数据结构基础

数据结构就是指计算机内部数据的组织形式和存储方法。常用的数据结构,有:线性结构、树、图等。

线性结构最常用,也是最简单的一种数据结构。所谓线性结构,就是指由 n 个数据元素构成的有限序列。直观来讲,它就是一张有限的一维数表。数组就是一种简单而典型的线性数据结构类型。

线性结构主要包括:顺序表、链表、栈、队列等形式。其中,顺序表和链表是从存储形式上区分的,而栈和队列是从逻辑功能上区分的。也就是说,顺序表和链表是线性数据结构的基础,队列和栈是基于顺序表和链表的,它们由顺序表或链表构成。

有时仅仅用线性结构存储管理数据是难以胜任的,一些数据之间存在着“一对多”的关系,这就构成了所谓的树形结构,简称树结构。例如:人工智能领域常用的“博弈树”,数据挖掘和商业智能中使用的“决策树”,多媒体技术中的“哈夫曼树”等都是应用树结构存储管理数据的实例。

还有一种常用的数据结构叫做图状结构,简称图结构。图结构中数据元素之间存在着“多对多”的关系,因此图结构与树结构相比,其线性结构复杂很多。在处理一些复杂的问题中,图结构往往能派上用场,例如:人工智能领域中的神经网络系统、贝叶斯网络等都是应用图结构存储管理数据的实例。

2. 顺序表

在计算机内部存储一张线性表(线性结构的数表),最为方便简单的就是用一组连续地址的内存单元来存储整张线性表。这种存储结构称为顺序存储结构,这种存储结构下的线性表就叫做顺序表。

顺序表示意图顺序表示意图.png

从上图可以看出,一张顺序表包括以下特征:

  • 有一个唯一的表名来标识该顺序表;

  • 内存单元连续存储,也就是说,一张顺序表要占据一块连续的内存空间;

  • 数据顺序存放,元素之间由先后关系;

数组满足上述特征,因此,数据本身就是一张顺序表。

2.1 创建

创建一张顺序表就是在内存中开辟一段连续的存储空间,并给它一个名字进行标识。只有创建了一个顺序表,才能利用该顺序表存放数据元素,也才能对该顺序表进行各种操作。

有两种创建顺序表的方法:一是静态地定义一张顺序表;二是动态地生成一张顺序表。

静态地定义一张顺序表的方法与定义一个数据的方法类似。描述如下:

#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) 为单位)。

2.2 插入元素

在长度为 n 的顺序表中的第 i 个位置插入新元素 item。

所谓在长度为 n 的顺序表中的第 i 个位置插入新元素,是指在顺序表第 i-1 个数据元素和第 i 个数据元素之间插入一个新元素 item,例如顺序表为:

公式1.png

在第 i 个位置插入新元素 item 后,该顺序表变为:

公式2.png

而此时顺序表 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。

2.3 删除元素

删除长度为 n 的顺序表中的第 i 个位置的元素,就是指将顺序表第 i 个位置上的元素去掉,例如顺序表为:

公式3.png

删除第 i 位置的元素后,该顺序表变为:

公式4.png

此时,顺序表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。

2.4 示例

#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;
}

示例运行结果,如下图:

线性表运行结果.png

参考来源:

1.《妙趣横生的算法(C语言实现)》                           杨峰  编著

注意:本站所有文章除特别说明外,均为原创,转载请务必以超链接方式并注明作者出处。 标签:数据结构,顺序表