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;
}