Day1：绪论以及顺序表

一、绪论

图灵奖获得者
   编程 == 数据结构 + 算法

描述事物
   事流程算法           C   面向过程
   物数据数据结构       C++ 面向对象

数据结构：管理数据的结构
   本身无意义

离散点常量变量结构体联合体枚举
线性数组链表栈队列线性表（动态数组 + 链表）顺序表
树：树二叉树有序二叉树 AVL 完全二叉树 23树 B B+ RB树哈夫曼树。。
图：多对多

补充：x86->32位操作系统 x64->64位

二、顺序表的思路及逐步优化(模仿vector的思路) 1.原始的实现思路

每push一个数据，就要开辟一块内存，再memcpy拷贝过去。

衡量代码性能：
① 时间 ② 空间

空间层面：已然没法优化了
时间层面：每次插入数据都要开内存都要拷贝

若 10W个数据开10W次内存！！！！
只好浪费空间来节约时间！

vector 1.5倍->下面采用位运算符>>右移，实现50%的效果。
每次需要申请内存的时候，申请当前内存大小的1.5倍。
要么是len的1.5倍要么是len+1

相关vector内存管理机制->见文章vector内存机制和性能分析 - 百度文库 (baidu.com)

新增变量capacity，表示当前开辟的空间容量

区分 len->实际有的元素个数

（也要考虑边界：当capacity=0时，至少得开辟1个吧。。。）

同样的，何时需要新开capacity->当capacity<=len时，才进行开辟&拷贝
//计算需要申请的内存大小   //>>1 右移一位 等同于除以2
capacity = capacity + (((capacity >> 1) > 1) ? (capacity >> 1) : 1 );

2.边界和条件的判定：

例：

①删除指定n th位置元素时：

优先判断输入的n是否符合要求（0-(len-1)之间）,判断len or 顺序表是否为空

->若前面写好了pop_front 和pop_back，可以判定n==0和n==(len-1)调用相对应的函数即可。

②push_back(const DATA_TYPE& data)

优先判断是否为空的一个顺序表（若空，只需要新开辟一块内存即可，无需memcpy） ->分类

初版代码：(发现两部分的代码有重合部分)->优化

typedef int DATA_TYPE;
void push_back(const DATA_TYPE& data)
{
	if (NULL == pArr)
    {
		DATA_TYPE* pNew = new DATA_TYPE[len+1];
		pArr = pNew;
		pArr[len++] = data;
	}
	else
    {
		DATA_TYPE* pNew = new DATA_TYPE[len+1];
		delete[] pArr;
		pArr = pNew;
		pArr[len++] = data;
	}
}

优化合并后的代码：合并相同部分的代码->更加简洁

（即将pArr不为NULL时，增添的步骤拉出来单独处理）

void push_back(const DATA_TYPE& data)
{   
    DATA_TYPE* pNew = new DATA_TYPE[len + 1];
	if (pArr)
    {
		memcpy(pNew, pArr, sizeof(DATA_TYPE)*len);
		delete[] pArr;
	}
	pArr = pNew;
	pArr[len++] = data;
}

添加capacity申请空间机制的更优代码：

void MyVector::push(const T& data)
{
	//0 判断是否需要申请内存
	if (capacity <= len)
	{//需要申请
		//计算需要申请的内存大小   //>>1 右移一位 等同于除以2
		capacity = capacity + (((capacity >> 1) > 1) ? (capacity >> 1) : 1);
		T* pNew = new T[capacity];
		if (pArr)
        {
			memcpy(pNew, pArr, sizeof(T)*len);
			delete[] pArr;
		}
		pArr = pNew;
	}
	pArr[len++] = data;
}

③析构函数：

也需要先判断pArr(存放首地址的指针)是否为NULL->再去决定是或否要delete

3.数据操作的基本流程类似：

step1：新定义一个指针pNew，开辟新的连续内存

step2：memcpy拷贝（效率更高，不用for）->常用sizeof

step3：释放pArr指向的内存段

step4：pArr指向新开的内存段pNew

step5：操作数据 & 更改len

4.进一步的完善：

C++类进行封装，模板类_Ty类型更好的适应多种类型数据存储（对于自定义类型的数据，需要重载相应的运算符即可）->注：模板类用多文件实现的时候，声明和定义必须放在头文件中实现，原因见下-------C++为什么要求把类声明和类实现进行分离？又为什么要求模板类的类声明和类实现要都放在头文件而不能分离? - 知乎 (zhihu.com)

三、代码实现

1.类的声明：

template
class MyVector
{public:
	MyVector();
	~MyVector();
	int& GetLen();
	//增
	void push_back(const _Ty& data);
	void push_front(const _Ty& data);
	void push_appoint(const _Ty& data, int k);		//注意：k表示下标
	//删
	void pop_back();
	void pop_front();
	void pop_appoint(int k);
	//遍历
	void travel();

protected:
	_Ty* pArr;			//指向数组的首地址
	int len;			//当前使用量
	int capacity;		//当前申请的总容量
};

2.push函数的实现 ①push_back

template
inline void MyVector<_Ty>::push_back(const _Ty& data)
{
	if (capacity <= len)
	{
		capacity +=((capacity >> 1)>1) ? (capacity >> 1) : 1;
		_Ty* pNew = new _Ty[capacity];
		if (pArr)				
		{
			memcpy(pNew, pArr, sizeof(_Ty) * len);
			delete[]pArr;
		}
		pArr = pNew;			//	至此完成了pArr对应部分的更新
	}
	pArr[len++] = data;
}

②push_front()

template
inline void MyVector<_Ty>::push_front(const _Ty& data)
{
	_Ty* pNew=nullptr;
	if (capacity <= len)
	{
		capacity += ((capacity >> 1) > 1) ? (capacity >> 1) : 1;
	}
	if (pArr)				
	{
		pNew = new _Ty[capacity]{ 0 };
		memcpy(pNew + 1, pArr, sizeof(_Ty) * len);
		delete[]pArr;
	}
	else
	{
		pNew = new _Ty[capacity];
	}
	pArr = pNew;			
	pArr[0] = data;
	//cout << pArr[0] << endl;
	len++;
}

③push_appoint()

template
inline void MyVector<_Ty>::push_appoint(const _Ty& data, int k)
{
	if (k<0 || k>(len - 1))
	{
		cout << "index error" << endl;
	}
	else if(k==0)
	{
		push_front(data);
	}
	else if (k == len - 1)
	{
		push_back(data);
	}
	else
	{
		_Ty* pNew = nullptr;
		if (capacity <= len)
		{
			capacity += ((capacity >> 1) > 1) ? (capacity >> 1) : 1;
		}
		if (pArr)				
		{
			pNew = new _Ty[capacity]{0};
			memcpy(pNew, pArr, sizeof(_Ty) * k);//拷k个过去
			pNew[k] = data;
			memcpy(pNew + k+1, pArr + k, sizeof(_Ty) * (len - k - 1));
			delete[]pArr;
			pArr = pNew;
		}
		else
		{
			pArr = new _Ty(0);
			pArr[0] = data;
		}			
		len++;
	}
}

3.pop函数实现 ① pop_back()

template
inline void MyVector<_Ty>::pop_back()
{
	if (pArr == nullptr)
	{
		cout << "数组为空，删除失败" << endl;
	}
	if (len == 1)
	{
		delete[]pArr;
		pArr = nullptr;
		len--;
	}
	else
	{
		_Ty* pNew = new _Ty[capacity];
		//cout << pArr[len-1]<<"t";
		memcpy(pNew, pArr, sizeof(_Ty) * (len - 1));
		delete[]pArr;
		pArr = nullptr;
		pArr = pNew;
		len--;
	}
}

②pop_front()

template
inline void MyVector<_Ty>::pop_front()
{
	if (pArr == nullptr)
	{
		cout << "数组为空，删除失败" << endl;
	}
	if (len == 1)
	{
		delete[]pArr;
		pArr = nullptr;
		len--;
	}
	else
	{
		_Ty* pNew = new _Ty[capacity];
		memcpy(pNew, pArr + 1, sizeof(_Ty) * (len - 1));
		delete[]pArr;
		pArr = nullptr;
		pArr = pNew;
		len--;
	}
}

③pop_appoint()

template
inline void MyVector<_Ty>::pop_appoint(int k)
{
	if (k<0 || k>(len - 1))
	{
		cout << "index error" << endl;
	}
	else if (k == 0)
	{
		pop_front();
	}
	else if (k == len - 1)
	{
		pop_back();
	}
	else
	{
		if (len == 1)
		{
			delete[]pArr;
			pArr = nullptr;
			len--;
		}
		else
		{
			_Ty* pNew = new _Ty[capacity]{0};
			memcpy(pNew, pArr, sizeof(_Ty) * k);
			memcpy(pNew + k, pArr + k + 1, sizeof(_Ty) * (len - k - 1));
			delete[]pArr;
			pArr = pNew;
		}
	}
}

四、其他补充笔记：

day1补充：数据结构&算法之顺序表__Doris___的博客-CSDN博客

Day1：绪论以及顺序表

C/C++/C#相关栏目本月热门文章