5.顺序表的尾插
顺序表中对于初学者最为头疼的是特殊情况的考虑和元素的后移前移操作，但是只要动动脑筋，就能运用自如，切忌死记硬背！
插入删除移动问题的见解:
1.
2.
对于插入数据，我们应该从数组尾处开始后移；对于删除数据，我们应该从删除端开始前移
（原因是从另一头移动会造成数据的覆盖）
类比:尾插就是食堂打饭时老老实实在最后一个人的位置后面排着队,并且干饭人的队伍又多了一名成员罢了.
void SeqListPushBack(SeqList* pq, SeqDataType x) { assert(pq); SeqCheckCapacity(pq); pq->a[pq->size] = x; pq->size++; }
6.顺序表的头插
类比:在食堂打饭的时候,你直接插队插到第一个位置去了,就是头插,那么你占了第一个位置,原来的人就必须得全部后移一个位置啦(哈哈)🤣
void SeqListPushFront(SeqList* pq, SeqDataType x) { assert(pq); SeqCheckCapacity(pq); int end = pq->size - 1; while (end >= 0) { pq->a[end + 1] = pq->a[end]; --end; } pq->a[0] = x; pq->size++; }
7.顺序表的尾删
类比:排队打饭时你突然发现阿姨颠勺颠的厉害,不想在这个窗口排队了
void SeqListPopBack(SeqList* pq) { assert(pq); assert(pq->size > 0); --pq->size; }
8.顺序表的头删
类比:你不文明的头插行为被阿姨发现了,在谩骂声下,你不得不离开队伍第一的位置,其他人又可以前进一个位置了
void SeqListPopFront(SeqList* pq) { assert(pq); assert(pq->size > 0); int begin = 0; while (begin < pq->size-1) { pq->a[begin] = pq->a[begin+1]; ++begin; } pq->size--; }
9.顺序表的按值查找
类比:你想找队伍里的小明同学,于是你从队头走到队尾,挨个匹配每个人是否是小明,找到就不找了.
int SeqListFind(SeqList* pq, SeqDataType x) { assert(pq); for (int i = 0; i < pq->size; ++i) { if (pq->a[i] == x) { return i; } } return -1; }
10.顺序表的任意位置插入
类比:又是插队!不过这次你是在下标为pos的位置的前一位插入,这就要从插入的位置到最后一位均后退一位才能行（在数组下标为pos的位置前插入一个e元素）
void SeqListInsert(SeqList* pq, int pos, SeqDataType x) { assert(pq); assert(pos >= 0 && pos <= pq->size); SeqCheckCapacity(pq); int end = pq->size - 1; while (end >= pos) { pq->a[end + 1] = pq->a[end]; --end; } pq->a[pos] = x; pq->size++; }
11.顺序表的任意位置删除
类比:不文明的行为当然不能容忍,这次你又被踢出去了（删除数组下标为pos的元素）
void SeqListErase(SeqList* pq, int pos) { assert(pq); assert(pos >= 0 && pos < pq->size); int begin = pos; while (begin <= pq->size-1) { pq->a[begin] = pq->a[begin+1]; ++begin; } pq->size--; }
上面有很多步骤都是可以复用的，例如头插就是在第一个元素前插入一个元素，尾插就是在最后一个元素后插入一个元素等等，快去找找看看吧！
下面来实战一下吧：
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int ElemType; typedef struct SeqList { ElemType* a; int size; int capacity; }SeqList; void InitSeqList(SeqList* ps) { ps->a = (ElemType*)malloc(sizeof(ElemType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } ps->size = 0; ps->capacity = 4; } void CheckCapacity(SeqList* ps) { if (ps->size == ps->capacity) { int newcapacity = 2 * ps->capacity; ElemType* temp = realloc(ps->a, sizeof(ElemType) * newcapacity); if (temp == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->capacity = newcapacity; ps->a = temp; } } } void SeqListPushBack(SeqList* ps, ElemType e) { CheckCapacity(ps); ps->a[ps->size] = e; ps->size++; } void PrintSeqList(SeqList* ps) { printf("顺序表的打印： "); for (int i = 0; i < ps->size; i++) { printf("%d\t", ps->a[i]); } } void SeqListInsert(SeqList* ps, int j, ElemType e) { assert(j >= 0 && j <= ps->size); CheckCapacity(&ps); for (int i = ps->size - 1; i >= j - 1; i--) { ps->a[i+1] = ps->a[i]; } ps->a[j - 1] = e; ps->size++; } void SeqListDelete(SeqList* ps, int j) { for (int i = j; i <= ps->size - 1; i++) { ps->a[i - 1] = ps->a[i]; } ps->size--; } int FindSeqList(SeqList* ps, ElemType e) { for (int i = 0; i < ps->size; i++) { if (e == ps->a[i]) { return i + 1; } } return 0; } ElemType GetSeqList(SeqList* ps, int j) { assert(j >= 1 && j <= ps->size); return ps->a[j - 1]; } void SeqListClear(SeqList* ps) { ps->a = NULL; ps->size = ps->capacity = 0; } void SeqListDestory(SeqList* ps) { free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } int main() { printf("宋永红的线性表（1）作业：\n"); SeqList pq; //顺序表的初始化 InitSeqList(&pq); //在顺序表的尾上插入数据 SeqListPushBack(&pq, 1); SeqListPushBack(&pq, 2); SeqListPushBack(&pq, 3); SeqListPushBack(&pq, 4); //打印顺序表 PrintSeqList(&pq); printf("\n"); //删除第N个元素 int n = 3; SeqListDelete(&pq, n); printf("删除第%d个数据后",n); PrintSeqList(&pq); printf("\n"); //在第n个位置前插入一个元素 SeqListInsert(&pq, 2, 100); printf("在第2个位置插入100这个数据后"); PrintSeqList(&pq); printf("\n"); //查找第n个元素，存在返回其位序，找不到返回0 int findNums = 100; int ret=FindSeqList(&pq, findNums); if (ret == 0) { printf("要找的%d不存在\n", findNums); } else { printf("%d存在，位序是%d\n", findNums, ret); } //获取第n个元素 ElemType x = GetSeqList(&pq, 2); printf("顺序表第2个位置的元素是%d\n", x); printf("\n"); //清空 SeqListClear(&pq); //销毁 SeqListDestory(&pq); }
打印结果：
为什么有扩容没有缩容？
realloc可以达到缩容的目的，但是是开辟了一块新空间来存放旧空间里的内容，这个步骤是需要消耗时间的，所以缩容的话就相当于是用时间换空间，如果不缩容，就相当于是用空间换时间，第一局：平局
但是第二局：不缩容还有一个好处就是在后面又想插入数据的时候，可以不用再扩容，减少扩容消耗的时间，同时内存对于空间还是比较慷慨的。
所以综合来看没有缩容，但是扩容肯定是必须的
