一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
二、顺序表
2.1 顺序表的概念和结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为：
1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。
注意：顺序表在数据结构中要求数据必须时连续存储的。
2.2 静态顺序表
静态顺序表的定义：
#define N 100//方便修改要存储数据的个数 //顺序表要求存储的数据从0开始，连续依次存储 struct SeqList { int a[N]; int size;//记录了存储多少个数据 };//当前结构体，是一个静态的顺序表，不实用 //出现的问题：出现浪费空间或者空间不够用的情况
2.3 动态顺序表
动态顺序表的定义：
//动态的顺序表，更加的实用 typedef int SLDateType; typedef struct SeqList { SLDateType* a; int size;//存储有效数据的个数 int capacity;//空间的大小 }SeqList;
2.4 顺序表管理顺序
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
2.4.1 初始化
在实现这些功能之前，我们要先对数据进行初始化
void SeqListInit(SeqList* ps) { assert(ps); ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType)); if (ps->a == NULL) { perror("malloc faild:"); exit(-1); } ps->size = 0; ps->capacity = 4; } void test() { SeqList s; SeqListInit(&s); }
注意：我们要将结构体的地址传过去,这样我们改变的是指针指向的对象，就是实参。
exit(-1)是让程序以异常方式退出整个程序。
return是返回函数，如果后面有程序还会继续执行。
2.4.2 销毁
我们使用动态开辟内存，要及时释放空间置为空指针，否则会造成数据泄漏
void SeqListDestroy(SeqList* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; }
2.4.3 尾插
注意：size是实际存储数据个数，前面的数据个数是下一个数据的下标
//判断是否增容 void SeqCheck(SeqList* ps) { assert(ps); if (ps->size == ps->capacity) { SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDateType))); if (tmp == NULL) { perror("realloc"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } } void SeqListPushBack(SeqList* ps, SLDateType x) { assert(ps); SeqCheck(ps); ps->a[ps->size] = x; ps->size++; }
2.4.4 尾删
所以删除时只需要让size–就可以了
当然还得要考虑一个严谨的问题
void SLPopBack(SL* ps) { // 温柔的检查 //if (ps->size == 0) //return; // 暴力的检查 assert(ps->size > 0); //ps->a[ps->size - 1] = 0; ps->size--; }
2.4.5 头插
在插入前，我们要先把数据向后挪，再将数据插入表中。在挪动过程中我们要注意增容问题，空间不足时，要及时增容。
void SeqListPushFront(SeqList* ps, SLDateType x) { assert(ps); SeqCheck(ps); int end = ps->size - 1; while (end>=0) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[0] = x; ps->size++; }
2.4.6 头删
头删时数据要从前向后挪动。
void SeqListPopFront(SeqList* ps) { assert(ps); assert(ps->size > 0); for (int i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--; }
2.4.7 在pos位置插入
在插入前，我们要先判断pos位置是否有效。
void SeqListInsert(SeqList* ps, int pos, SLDateType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SeqCheck(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; }
2.4.8 在pos位置删除
void SeqListErase(SeqList* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; }
2.5 总体代码
SeqList.h
#pragma once // SeqList.h #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int SLDateType; typedef struct SeqList { SLDateType* a; int size; int capacity; }SeqList; // 对数据的管理:增删查改 void SeqListInit(SeqList* ps); void SeqListDestroy(SeqList* ps); void SeqListPrint(SeqList* ps); void SeqListPushBack(SeqList* ps, SLDateType x); void SeqListPushFront(SeqList* ps, SLDateType x); void SeqListPopFront(SeqList* ps); void SeqListPopBack(SeqList* ps); // 顺序表查找 int SeqListFind(SeqList* ps, SLDateType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, int pos, SLDateType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int pos); void SeqListModify(SeqList* ps, int pos, SLDataType x);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"SeqList.h" void SeqCheck(SeqList* ps) { assert(ps); if (ps->size == ps->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * (sizeof(SLDataType))); if (tmp == NULL) { perror("realloc"); free(ps->a); ps->a = NULL; } ps->a = tmp; ps->capacity *= 2; } } void SeqListInit(SeqList* ps) { assert(ps); ps->a = (SLDataType*)malloc(4 * sizeof(SLDataType)); if (ps->a == NULL) { perror("malloc faild:"); exit(-1); } ps->size = 0; ps->capacity = 4; } void SeqListDestroy(SeqList* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } void SeqListPrint(SeqList* ps) { assert(ps); for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]); printf("\n"); } void SeqListPushBack(SeqList* ps, SLDataType x) { assert(ps); /*SeqCheck(ps); ps->a[ps->size] = x; ps->size++;*/ SeqListInsert(ps, ps->size, x); } void SeqListPushFront(SeqList* ps, SLDataType x) { assert(ps); //SeqCheck(ps); //int end = ps->size - 1; //while (end>=0) //{ // ps->a[end + 1] = ps->a[end]; // end--; //} //ps->a[0] = x; //ps->size++; SeqListInsert(ps, 0, x); } void SeqListPopFront(SeqList* ps) { assert(ps); /*assert(ps->size > 0); for (int i = 0; i < ps->size - 1; i++) { ps->a[i] = ps->a[i + 1]; } ps->size--;*/ SeqListErase(ps, 0); } void SeqListPopBack(SeqList* ps) { assert(ps); //assert(ps->size > 0); //ps->size--; SeqListErase(ps, ps->size - 1); } int SeqListFind(SeqList* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; } void SeqListInsert(SeqList* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos <= ps->size); SeqCheck(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[pos] = x; ps->size++; } void SeqListErase(SeqList* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size); int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; ++begin; } ps->size--; } void SeqListModify(SeqList* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); ps->a[pos] = x; }
2.6 相关面试题
1.移除数组
思路一: 遍历整个数组，查找到每一个val，碰到val就把他覆盖掉（数组后面的元素向前挪动数据）【时间复杂度为O(N*N)，空间复杂度为O(1)】
思路二:把不是val的值拷贝到新的数组里（双指针（数组））【时间复杂度O(N),空间复杂度O(N)】【不符合题意】
思路三:双指针，但是不开辟新的数组
int removeElement(int* nums, int numsSize, int val) { int left=0,right=numsSize-1; while(left<=right) { if(nums[left]==val) { nums[left]=nums[right]; right--; } else left++; } return left; }
2. 删除排序数组中的重复项。
int removeDuplicates(int* nums, int numsSize){ if(numsSize==0) return 0; int left=0,right=1; while(right<numsSize) { if(nums[right]!=nums[left]) { left++; nums[left]=nums[right]; } right++; } return left+1; }
3. 合并两个有序数组
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int p1 = m - 1, p2 = n - 1; int end = m + n - 1; int cur; while (p1 >= 0 || p2 >= 0) { if (p1 == -1) { cur = nums2[p2--]; } else if (p2 == -1) { cur = nums1[p1--]; } else if (nums1[p1] > nums2[p2]) { cur = nums1[p1--]; } else { cur = nums2[p2--]; } nums1[end--] = cur; } }
2.7 顺序表问题
问题：
- 我们在从开头或中间插入数据时，要先挪动数据才能插入，这样会有时间上的浪费。
- 增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。当我们增容100个空间，而只需要插入5个数据，这就会浪费95个空间。（浪费空间，不能按需释放和申请空间）
基于顺序表的缺点，就出现了链表，下一期小羊将带来链表的干货~
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~
