[C++知识库]手撕数据结构（1）- 顺序表的设计与实现

顺序表的设计与实现

1 顺序表简介

顺序表是线性表的一种，指用一组连续的内存单元存储线性表的数据元素，这种表也叫线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表。其特点是，逻辑上相邻的数据元素，在物理存储次序上也是相同的。

2 顺序表的特点

顺序表同数据一样，具有随机访问的特点，这点决定了其查找速度快的特点，但是同样的道理，其增加和删除元素所消耗的资源平均来说是较多的，因此，常用数组来描述数据结构中的顺序存储结构。再次，由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态内存分配的一维数组来表示线性表。

3 顺序表的描述

// define a struct to describe the seqlist
typedef struct
{
    Elemtype* elem;			// data point
    int capacity;			// seqlist max size
    int curr_size;			// seqlist current size
}Seqlist;

Elemtype* elem 指针指向当前数据元素的存储空间， int capacity 指当前顺序表所能存储的最大数据量，int curr_size 指当前已经存储数据的数据量

3.1 顺序表的初始化

/*
    ** This function will creat a empty array of elemtype,
    * using malloc to get the address of the heap space
    * set the current size = 0
    * @param seqlist seqlist struct point
    * @param capacity seqlist max size
    * @return value null
*/
void SeqList_Init(Seqlist* seqlist, int capacity)
{
    seqlist->elem = (Elemtype*)malloc(sizeof(Elemtype) * capacity);
    assert(seqlist->elem != NULL);
    seqlist->capacity = capacity;
    seqlist->curr_size = 0;
}

函数描述 : 为顺序表分配内存空间，空间大小为 sizeof(Elemtype) * capacity 字节 ; 将当前已经使用的容量设置为 0 \
传入参数 : \
Seqlist* seqlist  当前顺序表的结构体指针 \
int capacity      当前顺序表的最大容量 \
返回值 : 0        当前功能可不需要返回值判断初始化状态，若需要请自行改写

3.2 顺序表的元素添加

在指定位置添加元素

int Insert_Seqlist_Special(Seqlist* seqlist, int location, Elemtype elem)
{
    if (seqlist->curr_size == seqlist->capacity) return -2;
    if (location > seqlist->capacity || location < 1) return -1;
    for (int j = seqlist->curr_size; j >= location - 1; j--)
    {
        seqlist->elem[j + 1] = seqlist->elem[j];
    }
    seqlist->elem[location - 1] = elem;
    seqlist->curr_size++;
    return 0;
}

函数描述 : 将元素添加至指定位置
判断当前顺序表是否为满，满则返回错误码 -1   
判断指定位置是否合法，不合法则返回错误码 -2 
将指定位置以及之后的元素全部往后移动一位
将元素添加到指定位置

在顺序表尾部添加元素

int Insert_Seqlist_At_Header(Seqlist* seqlist, Elemtype elem)
{
    Insert_Seqlist_Special(seqlist, 1, elem);
    return 0;
}
在头部添加元素，则为在第一个元素的位置添加元素

在顺序表头部添加元素

int Insert_Seqlist_At_End(Seqlist* seqlist, Elemtype elem)
{
    Insert_Seqlist_Special(seqlist, seqlist->curr_size + 1, elem);
    return 0;
}
在尾部添加元素，则为在顺序表最后一个元素之后添加元素

3.3 顺序表的元素删除

删除指定位置的元素

int Erase_seqlist_Special(Seqlist* seqlist, int location)
{
    if (location <1 || location > seqlist->capacity)
    {
        return -2;
    }
    for (int j = location; j < seqlist->curr_size; j++)
    {
        seqlist->elem[j - 1] = seqlist->elem[j];
    }
    seqlist->curr_size--;
    return 0;
}
函数描述 :  删除指定位置的元素  
判断指定位置是否合法，不合法则返回错误码 -2 
将指定位置以及之后的元素全部往前移动一位

删除指定的元素

int Erase_seqlist_Elem(Seqlist* seqlist, Elemtype elem)
{
    Erase_seqlist_Special(seqlist, Find_seqlist_Elem(seqlist, elem));
    return 0;
}
函数描述 :  删除指定元素  
查询指定元素的位置 
删除指定位置的元素

3.4 顺序表的元素查询

查询指定位置的元素数据

Elemtype* Find_seqlist_ByID(Seqlist* seqlist, int location)
{
    if (location <1 || location > seqlist->capacity)
    {
        return NULL;
    }
    return &seqlist->elem[location - 1];
}
函数描述 :  查询指定位置的元素数据  
判断指定位置是否合法，不合法则返回空指针 
返回指定位置元素的指针

查询指定元素数据的位置

int Find_seqlist_Elem(Seqlist* seqlist, Elemtype elem)
{
    for (int i = 0; i < seqlist->curr_size; i++)
    {
        if (seqlist->elem[i] == elem)
        {
            return i + 1;
        }
    }
    return 0;
}  
函数描述 :  查询元素数据的位置
遍历整个顺序表 
返回指定元素的位置，未找到则返回0

3.5 顺序表的元素修改

修改指定位置的元素数据

int Change_Seqlist_ByID(Seqlist* seqlist, int location, Elemtype elem)
{
    seqlist->elem[location - 1] = elem;
    return 0;
}
函数描述 :  直接修改指定位置的元素数据

修改指定的元素数据

int Change_Seqlist_ByElem(Seqlist* seqlist, Elemtype source, Elemtype elem)
{
    Change_Seqlist_ByID(seqlist, Find_seqlist_Elem(seqlist, source), elem);
    return 0;
}
函数描述 :  修改指定元素数据
查询元素数据的位置
修改指定位置的元素数据

4 总结

顺序表可以随机存取表中任一元素，其存储位置可以用一个简单、直观的公式来表示。然而，从另外一方面来看，这个特点也造成了这种存储结构的缺点：在插入或删除操作的时候，需要移动大量的元素。此外由于数据有长度相对固定的静态特性，当表中元素个数较多且变化较大时，操作过程想对复杂，必然导致存储空间的浪费。所有的这些问题，都可以通过线性表的另外一种表示方式–链式存储结构来解决。
好了，今天的分享就到这儿了，下回再见，拜拜！！