2022年阅读书单

本文目录

1. 1、线性表的概念
2. 2、线性表的顺序存储结构的操作（创建、遍历、查找、插入和删除）
3. THE END!

1、线性表的概念

线性表是零个或多个数据元素的有限序列。
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。在C语言中可以采用一维数组来实现。

2、线性表的顺序存储结构的操作（创建、遍历、查找、插入和删除）

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

#define MAX_DATA_SIZE (100)
typedef int ElemType;

typedef struct SquareList_S
{
    ElemType data[MAX_DATA_SIZE];    // 数组存储线性表的数据元素
    int length;                        // 线性表的当前长度
} SqList;

// 1. 创建线性表（初始化线性表）
int InitSquareList(SqList* SL, int n)
{
    int i = 0;
    int x = 0;

    printf("请输入元素：\n");

    SL->length = n;

    for (i = 0; i < n; i++)
    {
        scanf("%d", &x);
        SL->data[i] = x;
    }

    return 0;
}


// 2.查找：获取线性表中的第i个位置的元素 时间复杂度 O(1)
int GetElemInSquareList(SqList* SL, int i, ElemType *e)
{
    if (SL->length == 0 || i < 1 || i > SL->length)
    {
        return -1;
    }

    *e = SL->data[i-1];

    printf("查找的元素是：%d\n", *e);

    return 0;
}

// 3.顺序遍历输出线性表中的元素
int TravesalSquareList(SqList* SL)
{
    int i = 0;

    for (i = 0; i < SL->length; i++)
    {
        printf("%d\t", SL->data[i]);
    }

    printf("\n");
    return 0;
}

// 4.插入元素 时间复杂度 O(n)
int InsertElemSquareList(SqList* SL, int i, int e)
{
    int k = 0;
    if (SL->length == MAX_DATA_SIZE) //线性表已经满了
    {
        return -1;
    }
    if (i<1 || i > SL->length+1) //插入位置不在合理范围内
    {
        return -1;
    }

    if (i <= SL->length) // 若插入位置不在表尾
    {
        for (k = SL->length-1; k >=i-1; k--)
        {
            SL->data[k+1] = SL->data[k]; // 后移一个位置
        }
    }

    SL->data[i-1] = e;
    SL->length++;

    return 0;
}


// 5.删除元素 时间复杂度 O(n)  平均时间复杂度O(n)
int DeleteElemSquareList(SqList*SL, int i, int *e)
{
    int k = 0;
    if (SL->length == 0)
    {
        printf("空线性表！\n");
        return -1;
    }

    if (i<1 || i > SL->length)
    {
        printf("请输入合理的删除位置！i=%d\n", i);
    }

    *e = SL->data[i-1];

    if (i < SL->length) //如果删除不是最后位置
    {
        for (k = i; k <= SL->length-1; k++) //前移一个位置
        {
            SL->data[k-1] = SL->data[k];
        }
    }

    SL->length--;

    return 0;
}


int main(int argc, char *argv[])
{
    SqList L = {0}; //数组创建在栈上
    ElemType ele = 0;
    // 1.初始化线性表
    InitSquareList(&L, 5);
    // 2.顺序输出线性表
    TravesalSquareList(&L);
    // 3.查找元素
    GetElemInSquareList(&L, 2, &ele);
    // 4.插入元素
    InsertElemSquareList(&L, 2, 50);
    TravesalSquareList(&L);
    // 5.删除元素
    DeleteElemSquareList(&L, 2, &ele);
    printf("删除的元素是: %d\n", ele);
    TravesalSquareList(&L);

    return 0;
}

THE END!

---

本博文只能阅读，谢绝转载，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2963033731@qq.com