[数据结构]2. 顺序表

1. 介绍

基本概念

顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。线性表是具有相同数据类型的 n 个数据元素的有限序列，在顺序表中，元素之间的逻辑顺序与其物理存储顺序是一致的。
顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素
2. 动态顺序表：使用动态开辟的数组存储

存储方式

顺序表一般采用数组来实现。数组在内存中占据连续的存储区域，每个元素都有唯一的索引，通过索引可以快速访问到对应的元素。例如，一个包含整数元素的顺序表可以用一个整型数组来存储。

优点

• 随机访问效率高：可以通过数组下标直接访问任意位置的元素，时间复杂度为 (O(1))。
• 存储密度高：每个存储单元只存储数据元素本身，没有额外的指针等开销。

缺点

• 插入和删除操作效率低：在插入或删除元素时，需要移动大量元素，平均时间复杂度为 (O(n))。
• 空间分配不灵活：需要预先分配固定大小的存储空间，可能会造成空间浪费或不足。

应用场景

静态顺序表只适用于 确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小。

2. 顺序表操作

SeqList.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;int size;//num of dataint capacity;
}SL;void SLInit(SL* psl);
void SLDestory(SL* psl);
void SLPrint(SL* psl);
//STL naming style
void SLPushBack(SL* psl, SLDatatype x);
void SLPushFront(SL* psl, SLDatatype x);
void SLPopBack(SL* psl);
void SLPopBack(SL* psl);
void SLInsert(SL* psl, int pos, SLDatatype x);
void SLErase(SL* psl, int pos);
int SlFind(SL* psl, SLDatatype x);
void SLModify(SL* psl, int pos, SLDatatype x);

Seqlist.c

#include"SeqList.h"
void SLInit(SL *psl) {assert(psl);psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);if (psl->a == NULL) {perror("malloc fail");return 0;}psl->capacity = 4;psl->size = 0;
}void SLDestory(SL* psl) {assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}void SLPrint(SL* psl) {assert(psl);for (int i = 0; i < psl->size; i++) {printf("%d ", psl->a[i]);}printf("\n");
}void SLCheckCapacity(SL* psl) {assert(psl);if (psl->size == psl->capacity) {SLDatatype* tmp = realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);if (tmp == NULL) {perror("realloc fail");return 0;}psl->a = tmp;psl->capacity *= 2;}
}//Insert data from the back
void SLPushBack(SL* psl, SLDatatype x) {assert(psl);//SLCheckCapacity(psl);//psl->a[psl->size] = x;//psl->size++;//---->SLInsert(psl, psl->size, x);
}//Insert data from the front
void SLPushFront(SL* psl, SLDatatype x) {assert(psl);/*SLCheckCapacity(psl);*///int end = psl->size - 1;//move data//while (end >= 0) {//	psl->a[end + 1] = psl->a[end];//	--end;//}//psl->a[0] = x;//psl->size++;//---->SLInsert(psl, 0, x);
}//Delete data from the back
void SLPopBack(SL* psl) {assert(psl);//if (psl->size == 0)//	return;//assert(psl->size > 0);//psl->size--;SLErase(psl, psl->size - 1);}//Delete data from the front
void SLPopFront(SL* psl) {assert(psl);//assert(psl->size > 0);//int start = 0;//while (start < psl->size - 1) {//	psl->a[start] = psl->a[psl->size + 1];//	start++;//}//psl->size--;SLErase(psl, 0);
}//Inserting data into a data structure
void SLInsert(SL* psl, int pos, SLDatatype x) {assert(psl);assert(pos >= 0 && pos <= psl->size);SLCheckCapacity(psl);int end = psl->size - 1;while (end >= pos) {psl->a[end + 1] = psl->a[end];--end;}psl->a[pos] = x;psl->size++;
}//Removing data from a data structure
void SLErase(SL* psl, int pos) {assert(psl);assert(pos >= 0 && pos < psl->size);//Cannot be inserted after 'size'int start = pos;while (start < psl->size) {psl->a[start - 1] = psl->a[start];++start;}psl->size--;
}//Returns the subscript if found, or -1 if not.
int SlFind(SL* psl, SLDatatype x) {assert(psl);for(int i = 0; i < psl->size; i++) {if (psl->a[i] == x) {return i;}}return -1;
}void SLModify(SL* psl, int pos, SLDatatype x) {assert(psl);assert(0 <= pos && pos < psl->size);psl->a[pos] = x;
}