数据结构---线性表之顺序表

1.线性表的概念

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表的概念

顺序表是线性表的一种：顺序表的逻辑结构是线性的，物理结构一定是线性的

1.静态顺序表

静态顺序表
#define MAXNUM 100
typedef int DateType;//顺序表可能存不同类型的数据，好修改struct Seqlist {DateType arr[MAXNUM];int size;//存入内存的有效数据个数；
}

顺序表的缺点很明显，数组的空间大小是定值，给小了存不下容易丢失数据，给大了容易浪费空间，于是就引出了动态顺序表

2.动态顺序表

typedef int DateType;typedef struct Seqlist {DateType* arr;int Capcity;//动态内存开辟的空间大小，后续我们需要用这个来判断空间够不够int size;//有效数据个数
}SL;

动态顺序表完美解决了静态顺序表空间的问题，可以扩容空间

3.动态顺序表的接口实现

SeqList.h

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{SLDataType* array;  // 指向动态开辟的数组size_t size ;       // 有效数据个数size_t capicity ;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

SeqList.c

// 顺序表初始化
void SeqListInit(SeqList* psl) {assert(psl);psl->array = NULL;psl->capicity = psl->size = 0;
}
// 检查空间，如果满了，进行增容
static void CheckCapacity(SeqList* psl) {if (psl->capicity == psl->size) {int NewCapacity = psl->capicity == 0 ? 4 : psl->capicity * 2;SLDataType* New = (SLDataType*)realloc(psl->array, NewCapacity * sizeof(SLDataType));if (New == NULL) {perror("realloc fail");return;}psl->array = New;}
}
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x) {assert(psl);//判断空间CheckCapacity(psl);psl->array[psl->size++] = x;
}
// 顺序表尾删
void SeqListPopBack(SeqList* psl) {assert(psl);psl->size--;
}
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x) {assert(psl);CheckCapacity(psl);//挪动数据for (int i = psl->size; i > 0; i++) {psl->array[i] = psl->array[i - 1];}psl->array[0] = x;psl->size++;
}
// 顺序表头删
void SeqListPopFront(SeqList* psl) {assert(psl);assert(psl->size);for (int i = 0; i < psl->size - 1; i++) {psl->array[i] = psl->array[i + 1];}psl->size--;
}
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x) {for (int i = 0; i < psl->size; i++) {if (psl->array[i] == x) {return i;}}return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, int pos, SLDataType x) {assert(psl);assert(pos >= 0 && pos <= psl->size);CheckCapacity(psl);if (pos == psl->size) {psl->array[pos] = x;psl->size++;return;}for (int i = psl->size; i > pos; i--) {psl->array[i] = psl->array[i - 1];}psl->array[pos] = x;psl->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, int pos) {assert(psl);assert(psl->size);assert(pos >= 0 && pos < psl->size);if (pos == psl->size - 1) {psl->size--;return;}for (int i = pos; i<psl->size-1; i++) {psl->array[i] = psl->array[i + 1];}psl->size--;}
// 顺序表销毁
void SeqListDestory(SeqList* psl) {assert(psl);free(psl->array);psl->array = NULL;psl->capicity = psl->size = 0;
}// 顺序表打印
void SeqListPrint(SeqList* psl) {assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->array[i]);}printf("\n");
}