阅读完成大概需要10分钟 | 2019-03-29 | 原创 | 有编程基础者适宜

个人博客 | B站空间

1. 我的理解

• 数据结构?什么是数据结构?

  • 就是数据(比如学生成绩等这些具有实际意义的东西)通过某种关系关联起来, 方便我们使用计算机统计和其他操作, 这样就是数据结构.

  • 在我看来数据结构就是个工具, 基于基本类型, 而形成的, 它的重点只是研究操作(数据元素)对象的关系, 根据不同问题对于数据操作的的特点(比如经常需要和插入删除元素), 使用不同的数据结构, 可以更加高效的解决问题.

• 算法就是解决问题的具体方法.

数据结构 + 算法 = 程序.

2. 算法:

数据结构只是静态的描述数据元素之间的关系, 高效的程序需要在 数据结构的基础上数据和选择算法.

• 算法是为了解决实际问题而设计的.
• 数据结构是算法需要处理的问题载体.
• 数据结构于算法相辅相成.

2.1. *算法的特性

输入:有0或多个输入.
输出:至少有一个输出(有1或以上的输出).
有穷性: 有始有终.
确定性: 每一步都有确定的含有, 不会出现二义性.
可行性: 算法的每一步都是可行的.

2.2. 统计算法的效率: 算法效率的度量

因为解决问题算法有多种, 货比三家, 那么我们需要 一把尺子来衡量算法的好坏, 来帮助我们判断优劣算法.

2.2.1. 时间复杂度(运行消耗时间的度量)

2.2.1.1. *事后统计法

记录程序运所消耗的时间, 作为参照物.

缺点: 这样有很多不确定性, 严重依赖于计算机硬件以及运行环境.

了解即可

实现方法: 获取在算法执行前获取时间戳并且赋值, 在算法完成时再获取并且减去执行前的时间戳.

--Lua代码
time = os.clock()
--代码
print(os.clock() - time)

2.2.1.2. 事前分析估算

假设每一行指令在计算机上运行速度固定, 通过计数算法中代码执行步数的多少, 来衡量算法效率(简单来说: 数执行了多少行).

判断规则:

• 只关注最高次项: 只关系操作数量的最高次项, 其他次项的常数忽略(因为大部分情况是人工数的, 偷懒而已啦).
• 最坏的时间复杂度: 我们分析的算法复杂度往往都是最坏的时间复杂度.
• 常数项记为1.

大O表示法 :
O(_执行行数)

O(₅)==O(₁),以后O(常数)都写成O(1)
O(N⁴+N³+N)==O(N⁴)

比如:

void sum(int a,int b)
{
   int s;  //1
   s = a + b;  //2
   std::cout<< s <<std::endl;  //3
}

这个就是O(₃) ==_{(因为常数记为1)}== O(₁)
注意: O(_n)!=O(₁)

又比如:

void fun(int n)
{
    int s = 1;
    for( ; s < n ; )
      s * = 2;
}

要想结束循环: 2^x=N; 即 x=log₂N, 记为O(_logN)
O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(n!)<O(x^x)
是不是觉得很复杂? 其实只要数, 执行了多少行即可.

2.2.2. 空间复杂度(占用存储空间大小的量度)

使用S(f(n))表示, 有空再更新, 敬请期待.

3. 数据结构

如果说 数组, 指针 等这些 基本的数据类型 是花瓶材料(粘土), 那么数据结构出现的那些线性表, 栈等 那些, 就是 就是各种各样的花瓶, 不同的 花 使用不同的容器, 在效率来说也许更加高效.

基本功能:删除元素, 查找元素, 添加(插入)元素, 遍历全表.
它们都是类型相同的数据的集合.
元素有限.
想不出来了2333.

4.1. 线性结构

线性表包括: 数组(顺序表), 链表, 队列, 栈等.

4.1.1 线性表

数学定义: 具有相同数据类型的 N (>=0) 个数据元素的有限序列(连续的).

顺序表_{(其实就是数组)}

1. 地址连续, 直接定义数组使用的栈空间, 使用new开辟空间使用堆空间, 这个主要用开辟堆空间, 可以用参数同态分配数组长度.
2. 原则上长度无法增减, 需要重新开辟新空间, 再拷贝原来的的数据,一般都实际大小都要大于开辟的空间.

简单实现(原创):

template<class T>
class Arr
{
  T* data;//指针
  unsigned int len;//长度
public:
Arr(unsigned int s)
{
  len=s;
  data=new T[s];
};// 构造
~Arr()
{
  delete[] data;//释放内存
}//构析
  T &operator[](int i)
{
  if(i<0||i>size)
    exit(EXIT_FAILURE);
  return data[i];
}//运算符重载 [i]
};

使用

Arr<type> data(len);
data[0]=(type)data
//---// 
Arr<int> int_data(10);
int_data[0]=100;
std::cout<<int_data[0]<<std::endl;

基于vector实现:

本家:

#include<vector>

初始化:

vector<type> p;
vector<type> p(int len);//设置初始大小.
vector<type> p(int len, type data)//设置大小, 并且设置每个的内容都为data.

//在这里导入参数vector<type> s, vector<type>是数据类型
vector<type> p(vector<type> s);//初始化一个和s内容相同的向量.
//假设x和y是向量t的两个元素指针,并且x<y.
vector<type> p(vector<type> *x,vector<type> *y);//初始化一个向量, 内容范围是t向量的x指针到y指针位置.

常用的API:

vector<type> s;


s.size();//获取元素个数
s.empty();//是否为空
s.clear();//清空所有的

vector<type> p;
p=s;//拷贝s的内容到p中.不是指针的操作.已经重载运算符.

==、!=、>、>=、<、<= 也适用. 返回值真1,假0.(某种程度上来说也是bool)

4.2. 非线性表

非线性结构: 树, 图等.