C语言 顺序表

顺序表底层逻辑是数组，是用一段物理地址连续的存储单位依次存储数据元素的，

首先先创建一个结构体类型

typedef int SLDataType;//方便以后存储别的类型的数据

typedef struct SeqList
{
    SLDataType* arr;
    int size;//有效数据的个数
    int capacity;//空间大小
}SL;

1初始化顺序表

void SLInit(SL*ps)
{
    ps->arr = NULL;
    ps->capacity = ps->size = 0;
}

2

//在插入时，需要先检查空间是否充足（头插，尾插，指定位置插入）

void SLCheckCapacity(SL* ps)//检查空间是否充足
{
    assert(ps);
    if (ps->capacity == ps->size)
    {
        SLDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SLDataType* tem = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
        if (tem == NULL)//扩容是否成功
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tem;
        ps->capacity = newcapacity;
    }

3 尾插

void SLPushBack(SL* ps, SLDataType x)
{
    SLCheckCapacity(ps);
    assert(ps);
        ps->arr[ps->size++] = x;
}

4 尾删

void SLPopBack(SL* ps)//尾删
{
    assert(ps&&ps->size);
    --ps->size;
}

5 头插 

void SLPushFront(SL* ps, SLDataType x)//头插
{
    assert(ps);
    SLCheckCapacity(ps);
    for (int i = ps->size; i>0; i--)//整体往后面退一位
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

 6 头删

void SLPopFront(SL* ps)//头删
{
    assert(ps && ps->size);
    for (int i =0; i<ps->size-1; i++)//整体往前移动一位
    {
        ps->arr[i] = ps->arr[i+1];
    }
    --ps->size;
}

7 顺序表的销毁

void SLDestroy(SL* ps)
{
    if (ps->arr)
    {
        free(ps->arr);
        ps->arr = NULL;
    }
    ps->capacity = ps->size = 0;
} 

打印顺序表的数据 

void SLPrint(SL ps)//打印
{
    for (int i = 0; i < ps.size; i++)
    {
        printf("%d", ps.arr[i]);
    }
    printf("\n");
} 

全部代码

#include"SeqList.h"
void SLInit(SL*ps)
{
    ps->arr = NULL;
    ps->capacity = ps->size = 0;
}
void SLDestroy(SL* ps)
{
    if (ps->arr)
    {
        free(ps->arr);
        ps->arr = NULL;
    }
    ps->capacity = ps->size = 0;
}
void SLCheckCapacity(SL* ps)//检查空间是否充足
{
    assert(ps);
    if (ps->capacity == ps->size)
    {
        SLDataType newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SLDataType* tem = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
        if (tem == NULL)//扩容是否成功
        {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tem;
        ps->capacity = newcapacity;
    }

}
void SLPushBack(SL* ps, SLDataType x)//尾插 先检查空间是否充足
{
    SLCheckCapacity(ps);
    assert(ps);
        ps->arr[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDataType x)//头插
{
    assert(ps);
    SLCheckCapacity(ps);
    for (int i = ps->size; i>0; i--)//整体往后面退一位
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}
void SLPrint(SL ps)//打印
{
    for (int i = 0; i < ps.size; i++)
    {
        printf("%d", ps.arr[i]);
    }
    printf("\n");
}
void SLPopBack(SL* ps)//尾删
{
    assert(ps&&ps->size);
    --ps->size;
}
void SLPopFront(SL* ps)//头删
{
    assert(ps && ps->size);
    for (int i =0; i<ps->size-1; i++)//整体往前移动一位
    {
        ps->arr[i] = ps->arr[i+1];
    }
    --ps->size;
}

#define  _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* arr;
    int size;//有效数据的个数
    int capacity;//空间大小
}SL;
void SLInit(SL* ps);//初始化顺序表
void SLDestroy(SL* ps);//顺序表的销毁
void SLPrint(SL ps);//打印
//尾插 头插
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
//尾删 头删
void SLPopBack(SL* ps);
void SLPopFront(SL*ps);
 

#include"SeqList.h"
void SLTest01()
{
    SL s1;
    SLInit(&s1);
    SLPushBack(&s1, 1);
    SLPushBack(NULL,2);
    SLPopBack(&s1);
    SLPopBack(&s1);
    SLPopBack(&s1);
    SLPrint(s1);
    SLDestroy(&s1);
};
int main()
{
    SLTest01();
    return 0;
} 

 补充三个

一 在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)//注意pos是下标
{
    assert(ps);
    assert(pos >= 0 && pos < ps->size);
    SLCheckCapacity(ps);
    for (int i = ps->size; i > pos; i--)//从pos开始到size-1的数据 都往后移动一位
    {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[pos] = x;

ps->size++;
}

二 删除指定位置的数据
void SLErase(SL* ps, int pos)
{
    assert(ps);
    assert(ps->size);
    for (int i = pos; i < ps->size-1; i++)
    {
        ps->arr[i] = ps->arr[i+1];
    }

ps->size--;
}

三 查找数据

int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
    for (int i = 0; i < ps->size; i++)
    {
        if (ps->arr[i] == x)
            return i;
    }
    return -1;
}

    int find = SLFind(&s1, 1);
    if (find < 0)
    {
        printf("没有此数据");
    }
    else
    {
        printf("找到了对应数据下标的数：%d ", find);

    }