数据结构───顺序表（梦开始的地方）

   种一棵树最好的时间是十年前，其次是现在。

   我写博客只是便利自己。因为遗忘一种自然现象，在未来的某一天，我一定会对某些东西模糊，这时候就可以回来翻翻自己的博客。

 

什么是顺序表？ 

简单来说，就是按顺序依次存储简单元素的线性数据结构，数组就是顺序表，其次就是字符串。

 如何实现顺序表

   创建一个数组分为两种，一种静态，一种动态。在c++中vector就是开辟一个动态数组。vector在c++中是一个对象，可以调用成员方法来进行对数组增删插改。今天既然是来学习顺序表底层逻辑，那就用c语言简单实现一下。

typedef int SLDataType;//顺序表要存储的类型
#define N 100
//创建数据结构--顺序表--静态
typedef struct SqeList {
	SLDataType a[N];
	int size;        //记录当前数据个数
}SL;
 
 
//创建数据结构--顺序表--动态
typedef struct SqeList {
	SLDataType* a;
	int size;        //记录当前数据个数
	int capacity;    //顺序表最大容量
}SL;

下面就动态顺序表各个功能的实现。

 首先初始化顺序表

void SqeListInit(SL* ps) {
	ps->a =NULL;
	ps->size = 0;
    ps->capacity =0;
}

 然后实现插入元素功能，只要添加数据就需要先检查内存够不够，于是先实现增容功能。

//扩容
void SqeListCheckCapacity(SL* ps) {
	if (ps->size == ps->capacity) {
		int newcapacity = ps->capacity == 0 ? SIZEINIT : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("no space to use:");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
}
//插入元素
void SqeListInsert(SL* ps, int pos, SLDataType x) {
	SqeListCheckCapacity(ps);
	assert(pos >=0 && pos <= ps->size);
	memmove(ps->a+pos+1, ps->a+pos, (ps->size - pos) * sizeof(SLDataType));
	ps->a[pos] = x;
	ps->size++;
}

 插入功能完成了，那么头插尾插直接调用即可。

//尾部插入一个数据
void SqeListPushBack(SL* ps,SLDataType x) {
	/*SqeListCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;*/
 
	SqeListInsert(ps, ps->size, x);
}
//顶部插入一个数据
void SqeListPushFront(SL* ps,SLDataType x) {
	//SqeListCheckCapacity(ps);
	//int end = ps->size - 1;
	//while (end >= 0) {
	//	ps->a[end + 1] = ps->a[end];
	//	end--;                  
	//}
	//ps->a[0] = x;
	//ps->size++;
	SqeListInsert(ps, 0,x);
}

 删除元素的话，只要将要删除的元素覆盖掉，可以使用memmove函数，当然也可以写个循环一个一个的移。

//删除尾部数据
void SqeListPopBack(SL* ps) {
	assert(ps->size > 0);
	ps->size--;
}
//删除顶部数据
void SqeListPopFront(SL* ps) {
	assert(ps->size > 0);
	//法一：
	//int begin = 1;
	//while (begin > ps->size) {
	//	ps->a[begin - 1] = ps->a[begin];
	//	begin++;
	//}
	//ps->size--;
	//法二：
	memmove(ps->a, ps->a + 1, (ps->size - 1) * sizeof(SLDataType));
	ps->size--;
}

 接下来实现一下查找，直接暴力枚举，遍历一遍顺序表所有元素。

//查找
int SqeListFind(SL* ps, SLDataType x) {
	for (int i = 0; i < ps->size; i++) {
		if (ps->a[i] == x) {
			return i;
		}
	}
	return -1;
}

对于修改功能，直接赋值就好啦。还有排序功能，各种排序方法，因地适宜。最后也是最重要的，用realloca开辟的空间要归还，避免内存遗漏 ，养成好习惯。

//顺序表销毁
void SqeListDestory(SL* ps) {
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 0;
}

这就是一个简单动态顺序表的实现了。检验所学知识当然就是刷题啦。

例题：1. 两数之和 - 力扣（LeetCode）

 题目要求在一个数组中返回两个数的下标，这两个数相加等于目标值。直接暴力枚举就好啦，如果相等就返回两数下标。

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    *returnSize=2;
    int*ans=(int*)malloc(2*sizeof(int));
    for(int i=0;i
        for(int j=i+1;j
            if(nums[i]+nums[j]==target){
                ans[0]=i;
                ans[1]=j;
                return ans;
            }
        }
    }
    return NULL;
}

 在c语言中返回一个数组需要自己开辟一个静态数组，并且就还要告诉调用方返还数组访问的大小，就是*returnSize的大小。

暴力枚举的时间复杂度为O(n^2)，可以用哈希表的方法将时间复杂度降到O(n)。在c++STL库中有一个unordered_map可以直接用，当然了也可以用数组模拟一个哈希表，这里有现成的就直接用了哈。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        for(int i=0;isize();++i){
            auto it=hash.find(target-nums[i]);
            if(it!=hash.end()){
                return {it->second,i};
            }
            hash[nums[i]]=i;
        }
        return {};
    }
};

  曾经有一位高人说过，过掉题目本身，比用什么方法更重要。好了，完成了第一题现在我也是刷过leetcode的人了，但想要不断巩固和熟练掌握所学内容，就采用刷题的方式，因为每一次通过就是给自己一次的正向反馈，等自己知识储备一定多的时候，再返回来试着用不同的方法解决，优化时间复杂度和空间复杂度。