一、什么是顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。换句话说就是一个动态开辟的数组，然后用一个结构体来封装这一个动态数组，再增加两个结构体成员记录数组中保存数据的情况。
二、顺序表的增删查改
2.1 结构体的声明
typedef int SLDataType; typedef struct SeqList { SLDataType* data; int sz; int capacity; }SL;
2.2 顺序表的初始化
void SeqListInit(SL* ps) { assert(ps); ps->data = (SLDataType*)malloc(sizeof(SLDataType) * 4); if (ps->data == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->sz = 0; }
2.3 顺序表检查容量
void check_capacity(SL* ps) { assert(ps); if (ps->capacity == ps->sz) { SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps->data = tmp; ps->capacity *= 2; } }
2.4 顺序表尾部插入数据
void SeqListPushBack(SL* ps,SLDataType x) { /*assert(ps); check_capacity(ps); ps->data[ps->sz] = x; ps->sz++;*/ SeqListInsert(ps, ps->sz, x); }
2.5 顺序表头部插入数据
void SeqListPushFront(SL* ps, SLDataType x) { /*assert(ps); check_capacity(ps); int i = ps->sz - 1; for (i; i >= 0; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[0] = x; ps->sz++;*/ SeqListInsert(ps, 0, x); }
2.6 顺序表尾部删除数据
void SeqListPopBack(SL* ps) { /*assert(ps); assert(ps->sz > 0); ps->sz--;*/ SeqListErase(ps, ps->sz - 1); }
2.7 顺序表头部删除数据
void SeqListPopFront(SL* ps) { /*assert(ps); assert(ps->sz > 0); int i = 0; for (i = 0; i < ps->sz - 1; i++) { ps->data[i] = ps->data[i + 1]; } ps->sz--;*/ SeqListErase(ps, 0); }
2.8 顺序表查找数据
int SeqListFind(SL* ps, SLDataType x) { assert(ps); int i = 0; for (i = 0; i < ps->sz; i++) { if (ps->data[i] == x) { printf("找到了，下标为:%d\n", i); return i; } } printf("找不到!\n"); return -1; }
2.9 顺序表任意位置插入数据
void SeqListInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->sz); check_capacity(ps); int i = 0; for (i = ps->sz - 1; i >= pos; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[pos] = x; ps->sz++; }
2.10 顺序表任意位置删除数据
void SeqListErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->sz); int i = 0; for (i = pos; i < ps->sz - 1; i++) { ps->data[i] = ps->data[i + 1]; } ps->sz--; }
2.11 顺序表打印数据
void Print(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->sz; i++) { printf("%d ", ps->data[i]); } printf("\n"); }
2.12 顺序表销毁
void SeqListDestroy(SL* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->capacity = ps->sz = 0; }
三、顺序表汇总
SeqList.h
#pragma once / //SeqList.h #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int SLDataType; typedef struct SeqList { SLDataType* data; int sz; int capacity; }SL; //函数声明 extern void SeqListInit(SL* ps); extern void SeqListDestroy(SL* ps); extern void SeqListPushBack(SL* ps, SLDataType x); extern void SeqListPushFront(SL* ps, SLDataType x); extern void SeqListPopBack(SL* ps); extern void SeqListPopFront(SL* ps); extern void Print(SL* ps); extern int SeqListFind(SL* ps, SLDataType x); extern void SeqListInsert(SL* ps, int pos, SLDataType x); extern void SeqListErase(SL* ps, int pos);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 / //SeqList.c #include "SeqList.h" void SeqListInit(SL* ps) { assert(ps); ps->data = (SLDataType*)malloc(sizeof(SLDataType) * 4); if (ps->data == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->sz = 0; } void SeqListDestroy(SL* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->capacity = ps->sz = 0; } void check_capacity(SL* ps) { assert(ps); if (ps->capacity == ps->sz) { SLDataType* tmp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps->data = tmp; ps->capacity *= 2; } } void SeqListPushBack(SL* ps,SLDataType x) { /*assert(ps); check_capacity(ps); ps->data[ps->sz] = x; ps->sz++;*/ SeqListInsert(ps, ps->sz, x); } void Print(SL* ps) { assert(ps); int i = 0; for (i = 0; i < ps->sz; i++) { printf("%d ", ps->data[i]); } printf("\n"); } void SeqListPushFront(SL* ps, SLDataType x) { /*assert(ps); check_capacity(ps); int i = ps->sz - 1; for (i; i >= 0; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[0] = x; ps->sz++;*/ SeqListInsert(ps, 0, x); } void SeqListPopBack(SL* ps) { /*assert(ps); assert(ps->sz > 0); ps->sz--;*/ SeqListErase(ps, ps->sz - 1); } void SeqListPopFront(SL* ps) { /*assert(ps); assert(ps->sz > 0); int i = 0; for (i = 0; i < ps->sz - 1; i++) { ps->data[i] = ps->data[i + 1]; } ps->sz--;*/ SeqListErase(ps, 0); } int SeqListFind(SL* ps, SLDataType x) { assert(ps); int i = 0; for (i = 0; i < ps->sz; i++) { if (ps->data[i] == x) { printf("找到了，下标为:%d\n", i); return i; } } printf("找不到!\n"); return -1; } void SeqListInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->sz); check_capacity(ps); int i = 0; for (i = ps->sz - 1; i >= pos; i--) { ps->data[i + 1] = ps->data[i]; } ps->data[pos] = x; ps->sz++; } void SeqListErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->sz); int i = 0; for (i = pos; i < ps->sz - 1; i++) { ps->data[i] = ps->data[i + 1]; } ps->sz--; }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 / //test.c #include "SeqList.h" void test_SeqListPushBack(void) { SL sl; SeqListInit(&sl); SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPushBack(&sl, 5); SeqListInsert(&sl, 2, 9); SeqListErase(&sl, 3); Print(&sl); SeqListFind(&sl, 4); } void test_SeqListPushFront(void) { SL sl; SeqListInit(&sl); SeqListPushFront(&sl, 1); SeqListPushFront(&sl, 2); SeqListPushFront(&sl, 3); SeqListPushFront(&sl, 4); SeqListPushFront(&sl, 5); Print(&sl); } void test_SeqListPopBack(void) { SL sl; SeqListInit(&sl); SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPushBack(&sl, 5); Print(&sl); SeqListPopFront(&sl); Print(&sl); SeqListPopFront(&sl); Print(&sl); SeqListPopFront(&sl); Print(&sl); SeqListPopFront(&sl); Print(&sl); SeqListPopFront(&sl); Print(&sl); } int main() { //test_SeqListPushBack(); //test_SeqListPushFront(); test_SeqListPopBack(); return 0; }
