1. 顺序表
1.1 顺序表的概念及其结构
基本概念:
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采 用数组存储,在数组中完成增删查改。如图1,它有如下特点:
- 存储空间连续,既允许元素的顺序访问,又可以随机访问。
- 要访问指定元素,可以使用索引(下标)来访问,时间复杂度为O(1);
- 要在其中增加或者删除一个元素,都要涉及后面所有元素的向前或向后移动，时间复杂度为O(n);
- 可以方便的存储表中的任一结点，存储速度快;
- 长度固定，分配内存之前必须知道数组的长度;
- 无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率提高；
存储结构:
顺序表一般可以分为:
1.静态顺序表:使用定长数组存储;
2.动态顺序表:使用动态开辟的数组存储;
静态分配和动态分配有什么不同呢？其实也就是数组的不同。在静态分配时，我们在编写的时候，就已经确定了数组的大小。而动态分配时，没有确定它的大小，是根据动态分配语句在运行时才将它的大小进行分配。这样有一点的好处就是，在静态分配时，当我想要存放顺序表的数据元素过超过 100的时候则会产生错误溢出，而动态分配时，如果一旦超过了分配的空间大小，可以再重新分配一块内存空间，把旧的空间和所增加的数据元素转移到新申请的空间上，这样就不会产生溢出的问题了。这是动态分配的一个优点。
代码如下:
//顺序表的静态存储 #define N 8 typedef int SLDataType; typedef struct SeqList { SLDataType array[N];//定长数组 size_t size;//有效数组的个数 }SeqList; //顺序表的动态存储 typedef int SLDataType; typedef struct SeqList { SLDataType* array;//指向动态开辟的数组 size_t size;//有效数据的个数 size_t capacity;//空间容量的大小 }SeqList; /*注解:我们发现这里用的是指针,指针是存放一个存储单元地址的.顺序表根据第一个数据元素的地址和数据元素的大小,就可以算出任意数据元素的位置.即只定义第一个元素的指针即可，描述整个顺序表。但它仅仅是个地址，没有确切的空间，因此我们使用是要开辟空间; SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType)); 详细代码下面讲解;*/
静态顺序表的定长数组导致N定大,空间开少了不够用,开多了浪费,所以现实中都是使用动态顺序表,使用倍增-复制的办法来支持动态扩容，将顺序表变成“可变长度”的。下面我将实现动态顺序表;
1.2 顺序表的插入(头插,尾插,插入指定位置）
1)头插法:每一次在顺序表的最前方插入,其他数据后移
void SeqListPushFront(SL* ps, SLDataType x) { //如果没有空间，或者空间不足，我们可以增容 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//对数组进行二倍增容,使用三目运算符是为了防止0这种情况 SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity); //判断是否增容成功 if(tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //从最后一个元素开始向前遍历到第一个元素，分别将它们向后移动一个位置 for (int i = ps->size - 1; i >= 0; i--) { ps->a[i + 1] = ps->a[i]; } ps->a[0] = x;//将要插入的数据插入到头部 ps->size++;//表长加1 }
2)尾插法:顺序表的末尾增加数据,其他元素不用改变
void SeqListPushBack(SL* ps, SLDataType x) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->size] = x; ps->size++; }
3)指定位置插入:从最后一个元素开始向前遍历到第指定位置，分别将它们向后移动一个位置
void SeqListInsert(SL* ps, int pos, SLDataType x) { //因为顺序表连续存储,所以首先要判断插入位置是否合法; assert(pos >= 0 && pos <= ps->size); //增容 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //从最后一个元素开始向前遍历到第指定位置，分别将它们向后移动一个位置 for (int i = ps->size - 1; i >= pos; i--) { ps->a[i + 1] = ps->a[i]; } //将x插入到指定位置 ps->a[pos] = x; //表长加1 ps->size++; }
1.3 顺序表的删除(头删,尾删,删除指定位置)
1)头删:从删除位置遍历到最后一个元素的位置,将他们依次向前移一个位置;
void SeqListPopFront(SL* ps) { //判断顺序表当前长度是否为0 assert(ps->size > 0); //从删除位置开始遍历到最后一个元素位置，将他们分别前移一个位置。 for (int i = 1; i < ps->size; i++) { ps->a[i - 1] = ps->a[i]; } //表长减一 ps->size--; }
2)尾删:将表长减去1即可;
void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--; }
3)删除指定位置:首先判断指定位置是否合法然后从指定位置的下一个元素依次向前移动一步.
void SeqListErase(SL* ps, int pos) { assert(pos >= 0 && pos < ps->size); for (int i = pos + 1; i < ps->size; i++) { ps->a[i - 1] = ps->a[i]; } ps->size--; }
1.4 顺序表的查找
查找:顺序表的一端开始，依次将每个元素的关键字同给定值 K 进行比较，直到相等或比较完毕还未找到.
int SeqListFind(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; }
1.5 顺序表的接口实现(供大家考察是否掌握）
大家可以参考其提供的接口进行练习考查是否已经掌握.
// 顺序表的动态存储 typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 size_t size ; // 有效数据个数 size_t capicity ; // 容量空间的大小 }SeqList; // 基本增删查改接口 // 顺序表初始化 void SeqListInit(SeqList* psl, size_t capacity); // 顺序表销毁 void SeqListDestory(SeqList* psl); // 顺序表打印 void SeqListPrint(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);
