数据结构之顺序表 | 小尹的博客

线性表

逻辑定义

线性表是一种由n个数据元素（结点）a(1), a(2), …, a(n)组成的有限序列，其中n为元素的个数即表的长度，n为0时表示空表。

a(1), a(2), …, a(i-1), a(i), a(i+1), …, a(n)

线性表的逻辑特征：

有且仅有一个开始元素a(1)，它没有前趋，仅有一个直接后继a(2)
有且仅有一个终端元素a(n)，它没有后继，仅有一个直接前趋a(n-1)
其余元素a(i)（ 2 <= i <= n-1 ）称为内部元素，有且仅有一个直接前趋a(i-1)和一个直接后继a(i+1)

基本运算

InitList(L) //构造一个空的线性表L
ListLength(L) //返回线性表L中元素个数
GetNode(L, i) //返回第i个元素L[i]（ 1 <= i <= ListLength(L) ）
LocateNode(L, x) //返回表L中第一个值为x的元素的位置，若没有符合的元素则返回0
InsertList(L, i, x) //在第i个元素之前插入一个值为x的新元素（表长度+1）
DeleteList(L, i) //删除第i个元素（表长度-1）

顺序表

将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，这种存储方法叫做顺序存储，用这种方法存储的线性表称为顺序表。

首先定义顺序表的表长和数据类型：

1 2	#define LIST_SIZE 100 typedef int DataType;

然后定义一个顺序表

typedef struct seq
{
    DataType data[LIST_SIZE];
    int length;
}SeqList;

顺序表的插入运算

//i表示插入位置，x表示插入元素
void InsertList(SeqList *l, int i, DataType x)
{
    //判断位置i是否合法
    if (i < 1 || i > l->length + 1)
    {
        printf("position error");
        return;
    }
    //判断顺序表空间是否已满
    if (l->length >= LIST_SIZE)
    {
        printf("overflow");
        return;
    }
    //从最后一个元素到新元素插入位置的元素，依次后移一位
    for (size_t j = l->length - 1; j >= i -1; j--)
    {
        l->data[j + 1] = l->data[j];
    }
    //插入新元素
    l->data[i - 1] = x;
    //表长度+1
    l->length++;
}

当插入位置在表末尾时，时间复杂度为O(1)；当插入表头时，时间复杂为O(n)；平均下来，顺序表插入的时间复杂度为O(n/2)，即O(n)。

顺序表的删除运算

//i表示删除位置，返回被删除的元素
DataType DeleteList(SeqList *l, int i)
{
    //判断位置i是否合法
    if (i < 1 || i > l->length)
    {
        printf("position error");
        exit(0);
    }
    //保存将被删除的元素
    DataType x = l->data[i];
    //从删除元素的后一个元素开始，依次前移一位
    for (size_t j = i; j <= l->length; j++)
    {
        l->data[j - 1] = l->data[j];
    }
    //表长度-1
    l->length--;
    return x;
}

顺序表删除运算的时间复杂度等同于插入运算。

打印顺序表

void printListInfo(SeqList *l)
{
    printf("list length = %d\n", l->length);
    for (int *i = l->data; i < l->data + l->length; i++)
    {
        printf("%d ", *i);
    }
    printf("\n");
}

初始化一个顺序表，并测试插入运算和删除运算

int main(int argc, char *argv[])
{
    SeqList s;
    s.length = 0;
    for (size_t i = 1; i < 10; i++)
    {
        s.data[i - 1] = i;
        s.length++;
    }
    printListInfo(&s);
    InsertList(&s, 4, 888);
    printListInfo(&s);
    DeleteList(&s, 5);
    printListInfo(&s);
	return 0;
}

输出结果

list length = 9
1 2 3 4 5 6 7 8 9
list length = 10
1 2 3 888 4 5 6 7 8 9
list length = 9
1 2 3 888 5 6 7 8 9

顺序表逆置，时间复杂度为O(n)

void Converts(SeqList *l)
{
    DataType x;
    for (size_t i = 0; i < l->length / 2; i++)
    {
        x = l->data[i];
        l->data[i] = l->data[l->length - 1 - i];
    }
}