线性表

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

#define MAXSIZE 20        //存储空间大小

typedef int data_t;

//线性表结构
typedef struct
{
    data_t data[MAXSIZE];        //数组，存储数据元素
    int len;                //线性表长度（从 1 开始）
}sqlist;


//创建线性表
sqlist* create_sqlist()
{
    sqlist* L = (sqlist*)malloc(sizeof(sqlist));
    if (L == NULL)
    {
        perror("malloc");
        return NULL;
    }
    L->len = 0;
    return L;
}


//初始化线性表
int init_sqlist(sqlist* L)
{
    L->len = 0;        //初始化为 0，当增加元素时从 1 开始计数
    return 1;
}


//线性表长度
int length_sqlist(sqlist* L)
{
    return L->len;
}


//返回第 i 个位置的元素（按位置查找）
int get_elem(sqlist* L, int i)
{
    if (L->len == 0 || i < 1 || i > L->len)
        return -1;
    data_t data = L->data[i - 1];
    return data;
}


//返回线性表中与给定值相等的元素的位置（按值查找）
int get_locate(sqlist* L, data_t data)
{
    //线性表为空
    if (L->len == 0)
        return -1;

    //遍历查找
    int i = 0;        //i 为下表，返回 i+1
    while (i < L->len)
    {
        if (L->data[i] == data)
            return i + 1;
        ++i;
    }
    //遍历完整个线性表都没有找到
    if (i >= L->len)
        return -1;
}


//插入元素
int insert_elem(sqlist* L, int loca, data_t data)
{
    if (L->len == MAXSIZE)    //线性表已满
        return -1;
    if (loca < 1 || loca > L->len + 1)    //可以插到最后一个元素的后面，所以插入的位置可以等于线性表长度+
        return -1;

    //开始插入
    for (int i = L->len - 1; i >= loca - 1; --i)    //len 和 loca 都是从 1 开始的，但是 i 是下标，所以 len 和 loca 都要减 1
    {
        L->data[i + 1] = L->data[i];
    }
    L->data[loca - 1] = data;        //插入新元素
    ++L->len;

    return 1;
}


//删除元素(按位置删除)
int delete_elem(sqlist* L, int loca)
{
    if (L->len == 0)
        return -1;
    if (loca < 1 || loca > L->len)
        return -1;

    //开始删除
    for (int i = loca; i < L->len; ++i)        //将该位置（从 0 开始）后面的数依次前移
        L->data[i - 1] = L->data[i];
    L->len--;

    return 1;
}

//修改元素(按位置查找)
int change_elem(sqlist* L, int loca, data_t data)
{
    if (L->len == 0)
        return -1;
    if (loca < 1 || loca > L->len)
        return -1;

    //开始修改
    L->data[loca - 1] = data;

    return 1;
}


//打印线性表
void show_sqlist(sqlist* L)
{
    for (int i = 0; i < L->len; ++i)
        printf("%d ", L->data[i]);
    printf("\n");
}



int main()
{
    int i;        //下标
    int len;          //长度

    //创建线性表
    sqlist* L = create_sqlist();

    //线性表的长度
    printf("新建线性表的长度：len = ");
    len = length_sqlist(L);
    printf("%d\n", len);

    //在头位置插入
    printf("在第一个位置插入5个数：");
    for (i = 1; i <= 5; ++i)
        insert_elem(L, 1, i);

    //打印
    show_sqlist(L);

    //求长度
    printf("插入5个元素后的线性表长度：len = ");
    len = length_sqlist(L);
    printf("%d\n", len);

    //按位置查找(从 1 开始)
    int elem = get_elem(L, 3);
    printf("第 3 个位置的元素为：%d\n", elem);

    //按值查找
    int loca = get_locate(L, 4);
    printf("4 在第 %d 个位置\n", loca);

    //删除元素
    delete_elem(L, 1);
    printf("删除第 1 个元素：");
    show_sqlist(L);

    //修改元素
    printf("将第 2 个位置的数据改为 100：");
    change_elem(L, 2, 100);
    show_sqlist(L);


    return 0;
}

链表