【数据结构】

前言

数据结构

1.什么是数据结构？

2.什么是算法？

3.数据结构和算法的重要性

4.如何学好数据结构和算法

5.数据结构和算法书籍及资料推荐

提示：以下是本篇文章正文内容，下面案例可供参考

一、什么是数据结构？

1、什么是数据结构？

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

2、什么是算法？

算法(Algorithm);就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

3、数据结构和算法的重要性

在校园招聘的笔试中：

当前校园招聘笔试一般采用Qnline Judge形式，一般都是20-30道选择题，3-4道编程题。

在校园招聘的面试中：

某学长CVTE面试：

1.怎么计算一个类到底实例化了多少对象？

2如果还有一个派生类继承了这个类，那么如何计算这两个类，各自实例化了多少对象？

3.你了解联合体和结构体吗？

4.如何测试一个机器是大端还是小端？

5.你了解队列和栈吗？

6.怎么用两个栈实现一个队列。

7.你使用过模版吗？

8.写一个比较两个数大小的模板函数。

9.你使用过容器吗？

10.判断两个链表是否相交。

11.vector和数组的区别。

12.你在学校里做的最满意的一个项目是什么？简述一下这个项目。

某学长腾讯的面试：
1、自我介绍

2.学习STL县体是怎么开展的？

3、如果一款产品给你怎么检测内存泄露？

4、进程间通信方式，共享内存是怎么实现的，会出现什么问题，怎么解决？

5,TCP为什么是可靠的？可靠是怎么保证的？ 为什么要三次握手？为什么三次握手就可以可靠？

Http数据分包问题；

Vector相关：

Hashmap相关;

红黑树的原理、时间复杂度等；

10、 Memcpv和memmove的区别；

11、客户端给服务器发送数据，意图发送aaa，然后再发bbb，但;中情况，如何处理？

12、游戏的邮件服务器中每天会有玩家频繁的创建邮件和删除邮件，海量数据、大小不
怎么存储，邮件是怎么到内存的？

13、写一道算法题

二、时间复杂度 空间复杂度

1、算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅連发展，计算机的存储容最已经达到了很高的程度。所以我们如今已经不需要再特別关注一个算法的空间复杂度。

2、时间复杂度

时间复杂度的概念；

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个西数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。—个算法所花费的时间与其中语句的执行次数成正北例，算法中的基本操作的执行次数，为算法的时间复杂度。

Func1 执行的基本操作次数：

F(N) = N° + 2 * N + 10= 10

F(N) = 130

V = 100 F(N) = 10210

N = 1000 F(N) = 1002010

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大0的渐进表示法。

大口符号 (Big O notation)：是用于描述西数渐进行为的数学符号。

推导大0阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数西数中，只保留最高阶项。

3、如果最高阶项存在目不是1，则去除与这个项目相乘的常数。得到的结果就是大0阶。
使用大O的渐讲表示法以后，Func1的时间复杂度：ON2

F(N) = 100

N = 100 F(N) = 10000

•N=1000 F(N)= 1000000

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界）

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数（下界）

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)。

代码如下；

代码如下；

3、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为文个也没大大意义，所以空间复杂度算的是变量的个数，空间复杂度计算规则其本跟实践复杂度类似，也使用大o渐进表示法。

代码如下；

总结

这里对文章进行总结：
以上就是今天要讲的内容，本文仅仅简单介绍了数据结构的使用，而数据结构提供了大量能使我们快速便捷地处理数据的方法。