线性表定义

线性表是n (n ≥ 0)个具有相同特性的数据元素的有限序列。记作：（a1, a2, …, ai-1, ai, ai+1, …, an）

线性表相关概念

直接前驱元素：ai-1领先于ai, 称ai-1是ai的直接前驱元素

直接后继元素：ai+1是 ai 的直接后继元素

前驱元素：a1, a2,…, ai-1均称为ai的前驱元素

后继元素：ai+1, ai+2,…, an均称为ai的后继元素

线性表的长度：线性表所含的数据元素个数 n 称为线性表的长度

空线性表：长度为零的线性表（即不包含任何数据元素的线性表）称为空线性表

位序：元素在顺序表的第几个位置

顺序表特点

顺序表具有以下特点：

元素在内存中的物理地址是连续的，因此可以通过下标快速访问和修改元素。
元素的插入和删除操作比较耗时，需要移动其他元素的位置来保持顺序。
顺序表的大小固定，当容量不足时需要进行扩容操作。
支持随机访问，即可以通过下标直接访问任意位置的元素。

顺序表适用于元素数量固定且频繁进行随机访问的场景，例如需要高效地查找、修改或删除元素的情况。然而，如果需要频繁进行插入和删除操作，顺序表的性能会受到影响，此时链表等数据结构可能更合适。

顺序表基本操作

基本操作

初始化操作:init_sqlist
判空操作:empty_sqlist
判满操作:is_full_sqlist
求长度运算:size
查找元素操作: search_sqlist
插入元素操作: insert_sqlist
删除元素操作: delete_sqlist
修改元素操作: modify_sqlist

实现代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

//数据类型
typedef int DataType;

typedef struct SqList 
{
    DataType* mem;      //连续内存
    int size;           //记录当前元素个数
    int maxSize;        //最大元素个数
}SqList;
//创建
SqList* create_sqlist();
//插入
void insert_sqlist(SqList* sqlist, DataType data);
//删除
void erase_sqlist_index(SqList* sqlist, int index);         //位序方式删除
void erase_sqlist_data(SqList* sqlist, DataType data);      //位序方式删除
void erase_sqlist_all(SqList* sqlist, DataType data);       //删除所有相同的数据
//查找
int search_sqlist(SqList* sqlist, DataType data);
//遍历
void print_sqlist(SqList* sqlist);
//销毁
void destory_sqlist(SqList* sqlist);
//万金油
bool empty_sqlist(SqList* sqlist);
int size_sqlist(SqList* sqlist);

int main() 
{
    SqList* sqlist = create_sqlist();
    insert_sqlist(sqlist,1);
    insert_sqlist(sqlist,3);
    insert_sqlist(sqlist,2);
    insert_sqlist(sqlist,66);
    insert_sqlist(sqlist,88);
    insert_sqlist(sqlist,88);
    insert_sqlist(sqlist,88);
    insert_sqlist(sqlist,99);
    print_sqlist(sqlist);
#if 0
    //按照位序删除测试
    erase_sqlist_index(sqlist, 1);
    print_sqlist(sqlist);
    erase_sqlist_index(sqlist, 2);
    print_sqlist(sqlist);
#endif
#if 0
    //按照数据做删除
    erase_sqlist_data(sqlist, 88);
    print_sqlist(sqlist);
#endif
    //删除掉所有一样的
    erase_sqlist_all(sqlist, 88);
    print_sqlist(sqlist);

    destory_sqlist(sqlist);
    sqlist = NULL;


    return 0;
}
SqList* create_sqlist()
{
    SqList* sqlist = (SqList*)calloc(1, sizeof(SqList));
    assert(sqlist);
    return sqlist;
}
void insert_sqlist(SqList* sqlist, DataType data)
{
    assert(sqlist);
    if (sqlist->size == sqlist->maxSize) 
    {
        sqlist->maxSize += 10;
        DataType* temp = realloc(sqlist->mem, sqlist->maxSize * sizeof(DataType));
        assert(temp);
        sqlist->mem = temp;
    }
#if 0
    //没有任何操作的插入方式
    sqlist->mem[sqlist->size++]=data;
#endif
    //有序插入方式
    sqlist->mem[sqlist->size] = data;
    //调整插入元素
    //1.交换到第一次小于他的位置
    //2.交换到0下标
    for (int i = sqlist->size; i > 0; i--) 
    {

        if (sqlist->mem[i - 1] > sqlist->mem[i]) 
        {
            DataType temp = sqlist->mem[i - 1];
            sqlist->mem[i - 1] = sqlist->mem[i];
            sqlist->mem[i] = temp;
        }
        else
        {
            break;  //插入元素大于前面不需要调整
        }
    }
    sqlist->size++;
    //自己课后写一写按照位序的方式插入
}
void erase_sqlist_index(SqList* sqlist, int index)
{
    assert(sqlist);
    //位序的有效性
    if (index <= 0 && index > sqlist->size) 
    {
        printf("序号无效!\n");
        return;
    }
    //顺序的表的删除是数组的伪删除
    //后面元素依次往前移动，覆盖删除元素
    for (int i = index - 1; i < sqlist->size - 1; i++) 
    {
        sqlist->mem[i] = sqlist->mem[i + 1];
    }
    //伪删除操作
    sqlist->size--;
}
void erase_sqlist_data(SqList* sqlist, DataType data)
{
    int pos = search_sqlist(sqlist, data);
    if (pos == -1) 
    {
        printf("未找到相关数据,无法删除!\n");
        return;
    }
    erase_sqlist_index(sqlist, pos + 1);
}
void erase_sqlist_all(SqList* sqlist, DataType data)
{
#if 0
    //效率稍微差一点
    int pos = -1;
    while ((pos=search_sqlist(sqlist, data)) != -1) 
    {
        erase_sqlist_index(sqlist, pos + 1);
    }
#endif
    //换种方式
    for (int i = 0; i < sqlist->size;) 
    {
        if (sqlist->mem[i] == data) 
        {
            for (int j = i; j < sqlist->size - 1; j++) 
            {
                sqlist->mem[j] = sqlist->mem[j + 1];
            }
            sqlist->size--;
        }
        else 
        {
            i++;
        }
    }
}

int search_sqlist(SqList* sqlist, DataType data)
{
    for (int i = 0; i < sqlist->size; i++) 
    {
        if (sqlist->mem[i] == data) 
        {
            return i;
        }
    }
    //返回0并不能作为没有找到的标准
    return -1;
}
void print_sqlist(SqList* sqlist)
{
    for (int i = 0; i < sqlist->size; i++) 
    {
        printf("%d\t", sqlist->mem[i]);
    }
    printf("\n");
}
void destory_sqlist(SqList* sqlist)
{
    assert(sqlist);
    free(sqlist->mem);
    sqlist->mem = NULL;
    free(sqlist);
}
bool empty_sqlist(SqList* sqlist)
{
    return sqlist->size==0;
}
int size_sqlist(SqList* sqlist)
{
    return sqlist->size;
}

顺表应用案例

顺序表是一种常见的数据结构，它可以用于许多应用场景，下面列举几个常见的应用：

数组：顺序表可以用于实现数组，数组是一种常见的数据结构，它可以用于存储一组相同类型的数据。在顺序表中，数组的每个元素都存储在连续的内存空间中，可以通过下标来访问。
多项式：顺序表可以用于实现多项式，多项式是一种常见的数学概念，它可以表示为一系列项的和，每个项包含一个系数和一个指数。在顺序表中，多项式的每个项可以存储在一个元素中，可以按照指数的大小顺序排列。
缓存：顺序表可以用于实现缓存，缓存是一种常见的技术，用于提高数据访问速度。在顺序表中，可以将最近访问的数据存储在前面的元素中，这样可以更快地访问最近使用的数据。
排序：顺序表可以用于实现排序算法，排序是一种常见的算法，用于将数据按照一定的顺序排列。在顺序表中，可以使用不同的排序算法，如冒泡排序、插入排序、快速排序等。
数据存储仓库：顺序表可以用于实现简单的数据库，数据库是一种常见的数据存储和管理系统，用于存储和管理大量数据。在顺序表中，可以将数据存储在不同的元素中，可以使用不同的算法来实现数据的查询、插入、删除等操作。

总的来说，顺序表是一种非常常见的数据结构，可以用于许多应用场景。在实际应用中，我们需要根据具体情况选择合适的数据结构和算法，以提高程序的效率和可维护性。

北屋教程网

专注编程知识分享，从入门到精通的编程学习平台

数据结构之顺序表