本节目标
了解线性表结构
能够自己实现顺序表
顺序表oj题
1.线性表概念
1线性表线性表（linear list）
是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
数组结构形式
链表结构形式
我们今天来实现顺序表结构，即数组结构形式的顺序表。
2.顺序表实现
3.顺序表相关OJ题练习
顺序表实现
概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
结构
1 静态顺序表：使用定长数组存储。
2 动态顺序表：使用动态开辟的数组存储。
静态顺序表
顺序表都以数组形式，静态顺序表示定长数组。
//顺序表的静态存储 #define N 7 //定长为7个元素的顺序表 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 capicity; //容量空间大小 }SeqList;
如何实现动态开辟数呢？
void *malloc( size_t size );
<stdlib.h>
Allocates memory blocks.
这是个动态开辟内存空间的函数。
函数的返回值：void*无类型的指针，需要根据自己开辟数据类型的指针强制转换。
函数的常数：size_t字节大小，根据自己需要开辟空间大小。
接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
线性表就是存数据的一种数据结构，而增删查改等接口的实现是这种数据结构的学习的基础！
// 顺序表的动态存储 typedef struct SeqList { SLDataType* array; // 指向动态开辟的数组 size_t size ; // 有效数据个数 size_t capicity ; // 容量空间的大小 }SeqList; // 基本增删查改接口 // 顺序表初始化 void SeqListInit(SeqList* psl); // 顺序表销毁 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);
// 顺序表初始化 void SeqListInit(SeqList* psl) { psl->array = NULL; psl->size = 0; psl->capacity = 0; }
// 顺序表销毁 void SeqListDestory(SeqList* psl) { free(psl->array); //释放空间，防止内存泄漏 psl->array = NULL; }
// 顺序表打印 void SeqListPrint(SeqList* psl) { int i = 0; for(i=0;i<psl->size;i++) { printf("%d ",psl->array[i]); } printf("\n"); }
// 检查空间，如果满了，进行增容 void SeqListCheckCapacity(SeqList* psl) { // 满了就要扩容 if (psl->size == psl->capacity) { int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(psl->array, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->array = tmp; psl->capacity = newcapacity; } } }
// 顺序表尾插 void SeqListPushBack(SeqList* psl, SLDataType x) { SeqListCheckCapacity(psl); psl->array[psl->size] = x; psl->size++; }
// 顺序表头插 void SeqListPushFront(SeqList* psl, SLDataType x) { SeqListCheckCapacity(psl); int i = 0; for (i = psl->size; i >0; i--) { psl->array[i]=psl->array[i-1]; } psl->array[i] = x; psl->size++; }
//顺序表尾删 void SeqListPopBack(SeqList* psl) { psl->size--; }
// 顺序表头删 void SeqListPopFront(SeqList* psl) { int end = 0; while (end<psl->size) { psl->array[end] = psl->array[end+1]; end++; } psl->size--; }
// 顺序表查找 int SeqListFind(SeqList* psl, SLDataType x) { if (psl == NULL) return 0; int i = 0; for (i = 0; i < psl->size; i++) { if (psl->array[i] == x) { printf("找到了、下标为：%d\n", i); return i; } } printf("找不到\n"); return -1; }
// 顺序表在pos位置插入x void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) { SeqListCheckCapacity(psl); if (psl->size > pos) { int i = 0; for (i = psl->size; i>pos; i--) { psl->array[i] = psl->array[i - 1]; } psl->array[i] = x; psl->size++; } else { printf("该位置不存在\n"); } }
// 顺序表删除pos位置的值 void SeqListErase(SeqList* psl, size_t pos) { if (psl == NULL) return 0; if (psl->size > pos) { int i = 0; for (i = pos; i < psl->size-1; i++) { psl->array[i] = psl->array[i + 1]; } psl->size--; } }
