顺序表及其实现

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

typedef int dataType;
#define MAX_SIZE 100

// 2.2.2 顺序表(顺序存储的线性表)
typedef struct
{
    dataType a[MAX_SIZE];
    int size;
}seqList;

// 1.顺序表的初始化/置空表
void init(seqList *slt)
{
    slt->size = 0;
}

// 2.在顺序表尾部追加值为x的元素
void append(seqList *slt,dataType x)
{
    if(slt->size == MAX_SIZE)
    {
        printf("顺序表是满的，无法追加！\n");
        exit(1);
    }
    slt->a[slt->size++] = x;
}

// 3.判断顺序表是否为空
int empty(seqList slt)
{
    return !slt.size;
}

// 4.打印顺序表各结点的值
void display(seqList slt)
{
    if(empty(slt))
        printf("顺序表是空的！\n");
    else
    {
        for (int i = 0; i < slt.size; i++)
            printf("%d ",slt.a[i]);
        printf("\n");
    }
}

// 5.查找顺序表中值为x的结点位置
int find(seqList slt, dataType x)
{
    int i = 0;
    while (i < slt.size && slt.a[i] != x) i++;
    return i < slt.size ? i : -1;
}

// 6.获取顺序表第i个结点的值
dataType get(seqList slt,int i)
{
    if(i < 1 || slt.size < i)
    {
        printf("访问越界！\n");
        exit(1);
    }
    return slt.a[i-1];
}

// 7.在顺序表的position位置插入值为x的结点
void insert(seqList *slt, int position,dataType x)
{
    if(slt->size == MAX_SIZE)
    {
        printf("顺序表是满的，无法插入！");
        exit(1);
    }
    if(position < 0 || position > slt->size)
    {
        printf("插入的位置非法，无法插入！");
        exit(1);
    }
    for (int i = slt->size; i > position; i--)
        slt->a[i] = slt->a[i-1];
    slt->a[position] = x;
    slt->size+=1; // 或slt->size++;
}

// 8.删除顺序表第position位置的结点
void del(seqList *slt, int position)
{
    if(empty(*slt))
    {
        printf("顺序表是空的，无法删除！");
        exit(1);
    }
    if(position < 0 || position >= slt->size)
    {
        printf("删除的位置非法，无法删除！\n");
        exit(1);
    }
    for (int i = position; i < slt->size-1; i++)
        slt->a[i] = slt->a[i+1];
    slt->size-=1; // 或slt->size--;
}

// 9.中点优先递归遍历顺序表
void listOrder(seqList list, int low, int high)
{
    if(low <= high)
    {
        int mid = (low+high)/2;
        printf("%d ",list.a[mid]);
        listOrder(list,low,mid-1);
        listOrder(list,mid+1,high);
    }
}

// 10.从键盘输入创建顺序表
void scanCreateList(seqList *list)
{
    printf("请输入整数序列，以9999作为结尾：\n");
    dataType x;
    scanf("%d",&x);
    while (x != 9999 && list->size < MAX_SIZE)
    {
        list->a[list->size++] = x;
        scanf("%d",&x);
    }
}

// 11.把顺序表前后两部分位置对调(0-m,m+1-n变为m+1-n,0-m)
void divList(seqList *L, int m)
{
    int i, j, x, last = L->size-1;
    for (i = 1; i <= m; i++)
    {
        x = L->a[0];
        for (j = 1; j <= last ; j++)
            L->a[j-1] = L->a[j];
        L->a[last] = x;
    }
}

int main()
{
    seqList slt; // 定义顺序表
    init(&slt); // 初始化顺序表
    display(slt); // 打印顺序表
    append(&slt,1); append(&slt,2); // 追加元素
    display(slt);
    printf("%d\n",find(slt,2)); // 按值查找
    printf("%d\n",get(slt,2)); // 按位查找
    insert(&slt,0,3); // 插入元素
    display(slt);
    listOrder(slt,0,slt.size-1);
    printf("\n");
    seqList L;
    init(&L);
    scanCreateList(&L);
    display(L);
    divList(&L,4);
    display(L);
    return 0;
}