1.顺序表
顺序表：使用一段连续的物理地址依次存储数据元素的线性结构，通常底层是数组，并且有着增删查改的接口的数据结构。
知识拓展：线性表
线性表，我们规定逻辑结构上是线性的，物理结构上不一定是线性的数据结构称为线性表。
线性表包括：顺序表、链表、栈、队列、字符串…
2.静态与动态
//静态顺序表 typedef int int_n; typedef struct seqlist { int_n arr_n[100]; int size_n; int capacity_n; }; //动态顺序表 typedef int int_t; typedef struct SeqList { int_t* arr; int size; int capacity; }SL;
思考：静态顺序表与动态顺序表的优劣在哪里？
动态顺序表更加灵活一些。
结论：由于动态顺序表的灵活优势，因而首选动态顺序表。
3.动态顺序表的实现
详细思路请点击link链接，LINK
下面是一些功能函数声明和顺序表原型都放在.h文件中。
顺序表是由一个原型和一系列接口（功能）组成的：因而我们首先升级一个数组为动态顺序表原型：
//动态顺序表 typedef int int_t; typedef struct SeqList { int_t* arr; int size; int capacity; }SL;
实现各种顺序表的功能接口：
//顺序表初始化的功能 void SLinit(SL* psl); //顺序表尾插 void SLpushback(SL* psl,int_t n); //顺序表头插 void SLpushfront(SL* psl,int_t n); //顺序表中间插 void SLinnert(SL* psl, int pos, int_t n); //顺序表打印 void SLprint(SL* psl); //顺序表尾删 void SLpopback(SL* psl); //顺序表头删 void SLpopfront(SL* psl); //顺序表中间删 void SLpopinnert(SL* psl,int pos); • 16
下面是具体实现一些函数功能接口：
#include"SeqList.h" void SLPrintArr(SL* psl) { for (int i = 0; i < psl->size; i++) { printf("%d ", *(psl->arr + i)); } printf("\n"); } void SLInit(SL* psl) { assert(psl);//思考1：这里为什么需要断言？ psl->arr = NULL; psl->capacity = 0; psl->size = 0; } void SLCheckCapacity(SL* psl) { if (psl->capacity == psl->size)//已满，扩容 { int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity; SLDataType* tarr = (SLDataType*)realloc(psl->arr, sizeof(SLDataType) * newcapacity);//思考：realloc的本地扩容与异地扩容分析 if (tarr == NULL) { perror("realloc fail"); exit(-1); } psl->arr = tarr; psl->capacity = newcapacity; } } void SLDestroy(SL* psl) { assert(psl); free(psl->arr); psl->arr = NULL; psl->capacity = psl->size = 0; } void SLPushBack(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); psl->arr[psl->size++] = x; } void SLPushFront(SL* psl, SLDataType x) { assert(psl); SLCheckCapacity(psl); int end = psl->size - 1; while (end >= 0) { psl->arr[end + 1] = psl->arr[end]; end--; } psl->arr[0] = x; psl->size++; } void SLPopBack(SL* psl)//思考2：在删除元素的时候，需要及时free吗？ { assert(psl); assert(psl->size > 0); psl->size--; } void SLPopFront(SL* psl) { assert(psl); assert(psl->size>1);//假设没有 思考3：过度删除之后，进行头插 int start = 1; while (start < psl->size) { psl->arr[start-1] = psl->arr[start]; start++; } psl->size--; } 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->arr[end+1] = psl->arr[end]; end--; } psl->arr[pos] = x; psl->size++; } void SLErase(SL* psl, int pos) { assert(psl); assert(psl->size > 0); assert(pos >= 0 && pos < psl->size); int end = pos + 1; while (end < psl->size) { psl->arr[end-1] = psl->arr[end]; end++; } psl->size--; } SLDataType* SLFind(SL* psl, int num) { assert(psl); assert(psl->size > 0); for (int i = 0; i < psl->size; i++) { if (psl->arr[i] == num) { return &(psl->arr[i]); } } printf("未查找到!\n"); return NULL; }
思考1：因为顺序表的实现是默认为非空指针的，所以需要assert检查一下是否为空指针。
思考2：不需要，因为空间释放不支持分期付款
思考3：这是一种错误情景：过度删除之后在进行头插，这种时候数据出错误，但是编译器并不会报错，size可能会变成负数。
那为什么没有崩溃？因为没有越界访问。
反思：当前出现的错误可能是之前出现的错误，为自己埋下的坑。
解决有两种方法：一是if检查二是assert断言一下。
下面是测试代码源文件内容（在test.c文件中）：
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" int main() { SL sl; SLinit(&sl); SLpushback(&sl,1); SLpushfront(&sl, 1); SLpushfront(&sl, 1); SLpushfront(&sl, 1); SLpushfront(&sl, 1); SLprint(&sl); SLinnert(&sl, 1, 3); SLprint(&sl); SLpopback(&sl); SLprint(&sl); SLpopfront(&sl); SLprint(&sl); SLpopinnert(&sl,3); SLprint(&sl); return 0; }
4.相关练习题
三道题目的思路方法预览：
1.移除元素
//三条思路 //1.传统的覆盖 //2.开新数组 //3.双指针 int removeElement(int* nums, int numsSize, int val) { int i = 0; int p1 = 0;//探路者 int p2 = 0;//守家者 for(i = 0;i<numsSize;i++) { if(nums[p1]==val) { p1++; } else { nums[p2++] = nums[p1++]; } } return p2; }
2.删除有序数组中的重复项
int removeDuplicates(int* nums, int numsSize) { int src = 1; int dest = 0; while(src<numsSize) { if(nums[src]==nums[dest]) { src++; } else { dest++; nums[dest] = nums[src]; src++; } } return dest+1; }
3.合并两个有序数组
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int i1 = m - 1; int i2 = n - 1; int k = nums1Size - 1; while(i1>=0 && i2>=0) { if(nums1[i1]>nums2[i2]) { nums1[k--] = nums1[i1--]; } else { nums1[k--] = nums2[i2--]; } } while(i2>=0) { nums1[k--] = nums2[i2--]; } }
EOF
