顺序表-数据结构

一、结构定义

顺序表是通常是数组，要求数据连续存储。顺序表又分为定长顺序表和变长顺序表，本文实现后者。

1、头文件

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

2、定长顺序表

#define MAX 100
定长顺序表结构
typedef struct SqList {int arr[MAX];int size;
}Sq;

3、变长顺序表

//变长顺序表 
typedef struct SqList {int* arr;int size;int capacity;
}Sq;

二、功能实现

1、初始化

//初始化
bool Sq_init(SqList* S) {//检查空指针if (S == NULL){printf("init false");exit(-1);}S->arr = (int*)malloc(sizeof(int) * 30);//检查malloc是否成功if (S->arr == NULL) {printf("malloc false");return false;}S->capacity = 30;S->size = 0;return true;
}

2、扩容

//检查数组、满则扩容
bool Sq_Check(SqList* S)
{if (S->size == S->capacity){int newcapacity = S->capacity + 30;int* arr_tmp = (int*)realloc(S->arr, newcapacity * sizeof(int));if (arr_tmp == NULL) {printf("realloc false");exit(-1);}S->arr = arr_tmp;S->capacity = newcapacity;}
}

3、插入

//头插
bool Sq_PushFront(SqList* S,int value)
{if (S == NULL)exit(-1);Sq_Check(S);for (int i = S->size; i > 0; i--){S->arr[i] = S->arr[i - 1];}S->arr[0] = value;S->size++;return true;
}
//尾插
bool Sq_PushBack(SqList* S, int value)
{if (S == NULL)exit(-1);Sq_Check(S);S->arr[S->size] = value;S->size++;return true;
}

4、删除

//头删
int Sq_PopFront(SqList* S)
{//头删就是把序号为0的元素删除//若需要删除序号为x的元素//只需要更改i的初始值和循环次数即可if (S == NULL)exit(-1);//让后一项覆盖前一项，重复size-1次int ret = S->arr[0];for (int i = 0; i < S->size - 1; i++){S->arr[i] = S->arr[i + 1];}S->size--;return ret;
}
//尾删
int Sq_PopBack(SqList* S)
{if (S == NULL)exit(-1);int ret = S->arr[S->size - 1];S->size--;return ret;
}

5、查询

//查
int Sq_Select(SqList* S, int x)
{if (S == NULL)exit(-1);if (x >= S->size)exit(-1);return S->arr[x];
}

6、主函数及打印

void Sq_Print(SqList* S)
{for (int i = 0; i < S->size; i++){printf("%d ", S->arr[i]);}printf("\n");
}
int main(){SqList* S = (SqList*)malloc(sizeof(SqList));Sq_init(S);Sq_PushBack(S, 1);Sq_PushBack(S, 2);Sq_PushBack(S, 3);Sq_PushFront(S, 4);Sq_Print(S);Sq_PopBack(S);Sq_PopFront(S);Sq_Print(S);printf("%d",Sq_Select(S, 1));return 0;
}

三、效果图