数据结构总结及网络基础

========================数据结构=====================================

数据结构+算法=程序  数据结构是程序的骨架，算法则是程序的灵魂。

一：数据描述
1、数据：数据是描述客观事物的数值、字符以及能输入给计算机且能被计算机处理的各种符号集合。 
简单的来说，数据就是计算机化的信息。


2、数据元素：是组成数据的基本单位，在计算机中通常被作为一个整体进行考虑和处理。也被称为记录。 
数据项：数据项是数据不可分割的最小单位。一个数据元素可由多个数据项组成。 
比如我们的人类世界中，人、狗都能被称为数据元素，作为整体进行考虑。而眼、鼻、手等就是数据项。


3、数据对象：数据对象是性质相同的数据元素的集合，是数据的子集。 
例如学籍表，每个人（数据元素）都有姓名、年龄等数据项，都属于同一个数据对象。


接下来就是我们最重要的数据结构。 
4、数据结构：我们现实世界中，不同的数据元素之间不是独立的，而是存在某些关系，这些关系就是结构。数据结构是指相互之间存在一种或多种特定关系的数据元素集合。数据结构分为逻辑结构和存储结构 
逻辑结构指的是数据间的关系，而存储结构是逻辑结构的存储映像（计算机中的表现形式）。
逻辑结构：包括：（1）线性结构：线性（2）非线性：集合、树、图（多对多等对应关系）
存储结构：顺序存储、链式存储、索引存储以及散列存储（哈希表）。


顺序存储：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于数组来描述的。优点：节省空间，可以实现随机存取；缺点：插入、删除时需要移动元素，效率低。（数组，栈等）


链式存储：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。特点是元素在物理上可以不相邻，所以每个数据元素包括了一个数据域和一个指针域，数据域用来存放数据，而指针域用来指向其后继结点的位置。优点：插入、删除灵活；缺点：不能随机存取，查找速度慢。


二：基本概念
1、抽象数据类型：
抽象数据类型可以用以下的三元组来表示：
ADT=（D，S，P）
D表示数据对象，S表示D上的关系集、P表示D上的操作集。


2、时间复杂度：
算法运行需要的时间，一般将算法的执行次数作为时间复杂度的度量标准。
每增加一次参数再增加的运算数


3、空间复杂度：
算法占用的空间大小。一般将算法的辅助空间作为衡量空间复杂度的标准。
每增加一次参数再增加的栈数


三：线性表：
顺序存储：顺序表
链式存储：链式表（单链表、循环链表和双链表）


1、顺序表：
顺序表是最简单的一种线性结构，逻辑上相邻的数据在计算机内的存储位置也是相邻的，可以快速定位第几个元素，中间不允许有空，所以插入、删除时需要移动大量元素。初始化是指给顺序表分配一个预定义大小的空间，用基地址elem记录这段空间的首地址
线性表的每个数据元素类型都相同，所以我们完全可以通过数组来实现线性表的顺序存储结构。ArrayList类就是顺序结构线性表的实现
删除和增加某一项时间复杂度为二分之n和二分之（n-1）


2、单链表：
链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不一定相邻，那么怎么表示逻辑上的相邻关系呢？可以给每个元素附加一个指针域，指向下一个元素的存储位置。


单链表每个结点包含两个域：数据域和指针域，定义了结点之后，我们就可以把若干个结点连接在一起，形成一个链表，单链表怎么操作都要从头往后开始。链表每个指针都是指向下一个结点，都是朝向一个方向的，这样的链表称为单向链表，或单链表。


3、循环链表：
循环链表是一个首尾相连的链表，将单链表最后一个结点的地址域改为指向表头结点，就得到了单链循环链表，称为循环单链表。


4、双向链表：
单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？双向链表每个结点包含三个域：数据域和两个指针域，指针域分别存储前后两个元素结点的地址，即前驱和后继。因此指针指向的类型也是结点类型。
创建双向链表也可以用前插法和尾插法，前插法创建的链表和输入顺序正好相反，因此称为逆序建表，尾插法创建的链表和输入顺序一致，因此称为正序建表。LinkedList类则是双链表的实现


四：栈和队列
1、栈是限制仅在一个位置上进行插入和删除的线性表。允许插入和删除的一端为末端，称为栈顶。另一端称为栈底。不含任何数据元素的栈称为空栈。栈又成为后进先出(LIFO)表，后进入的元素最先出来。
由于栈是一个线性表，所以我们上一章说的顺序结构和链式结构对栈来说同样适用。
2、.顺序栈：
栈只能在一端操作，后进先出，是人为规定的，也就是说不允许在中间查找、取值、插入、删除等操作，但顺序栈本身是顺序存储的。
初始化一个空栈，还要先定义个最大的分配空间，顺序结构都是如此，需要预先分配空间
3、链栈：
顺序栈是分配一段连续的空间，需要两个指针，base指向栈底，top指向栈顶。而链栈每个结点的地址是不连续的，只需要一个栈顶指针即可。


4、队列：
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（FIFO）的线性表，允许插入的一端称为队尾，允许删除的一端称为队头。线性表有顺序存储和链式存储，队列作为一种特殊的线性表，也同样存在这两种存储方式。
5、循环队列：
队列的顺序结构每一次出栈后面元素都要变动，若队列相连，队头是可以变化的，队头出列了，下一个元素就变为了队头，问题就解决了。
我们把队列这种头尾相接的顺序存储结构称为循环队列。
可是这时又存在一个问题，我们前面说过head=rear时，证明为空队列，但当存满时，rear也等于head，那么如何判断当前的队列究竟是空队列还是满队列呢？有两个解决办法 
方法一是我们设置一个标志变量flag，当head==rear且flag==0时队列为空，当head==head且flag==1时队列满。
方法二是当队列满时，我们修改条件，我们保留一个元素空间，也就是说，队列满时数组中还有一个保留单元。


6、链式队列：链式存储结构的队列空间肯定够，所以就不需要循环。


五：HashMap内部及散列


1、哈希的区别
（1）数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)


（2）链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)。
我们可以发现，数组和链表几乎是两个极端，一个查找效率高，一个插入删除效率高，那么有没有一种数据结构融合两者的优点呢？没错，就是哈希表。
在哈希表中进行添加，删除，查找等操作，性能都非常高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)，那么是如何做到的呢？首先，哈希表的主干为数组，例如我们要增加或查找某个元素，我们可以将当前元素通过某个函数映射到数组中的某个位置，通过数组下标直接定位即可。这个函数被称为哈希函数。


2、哈希内部设计：
哈希函数：哈希表的主干为数组，例如我们要增加或查找某个元素，我们可以将当前元素通过某个函数映射到数组中的某个位置，通过数组下标直接定位即可。这个函数被称为哈希函数。
设计：哈希函数的设计至关重要，好的哈希函数会尽可能地保证散列的地址分布均匀，但是再好的哈希函数也会出现冲突的情况，比如我们的两个元素通过哈希函数得到同一个存储地址，那么该如何解决呢？哈希冲突的解决方案有很多种，而HashMap采用了链地址法，就是数组+链表的方式，所有通过哈希函数得到同一地址的元素是二维链表表头，然后遍历表头查找。java8用红黑树代替链表，是查询复杂度从N降低到logN


六：串和KMP算法
1、串：串是由零个或多个字符组成的有限序列，经常被称为字符串。一般记为s=”a1a2a3a4..an”
子串：串中任意个数的连续字符组成的序列被称为子串，包含子串的串被称为主串。


2、MKP算法：
匹配T子串在S主串的位置，m是主串长度，n是子串长度，则每一个字符比较最大时间复杂度为O(m*n) m
MKP算法：先进行子串内部比较
分为1个长度，2.3，4。。。
判断T′="abaab"的前缀和后缀是否相等，找相等前缀后缀的最大长度。
长度为1的：前缀"a"，后缀："b"，不等×
长度为2的：前缀"ab"，后缀："ab"，相等√
长度为3的：前缀"aba"，后缀：" aab"，不等×
长度为4的：前缀"abaa"，后缀："baab"，不等×
比前后缀相等的最大长度L，则可以退回到L+1=3位置比较


七、树
1、树与森林的遍历
树的遍历方法主要有以下两种：
（1）先序遍历：若树非空，则遍历方式为：访问根结点，然后从左到右，依次先序遍历每一课子树。
（2）后序遍历：若树非空，则遍历方式为：从左到右，依次后序遍历根结点的每一棵子树，然后访问根结点。
森林的遍历方法主要有以下两种：
（1）先序遍历：若森林非空，则遍历方式为：访问森林第一棵树的根结点，先序遍历第一棵树的根结点的子树，先序遍历剩余的树构成的森林。
（2）中序遍历：若森林非空，则遍历方式为：中序遍历森林中第一棵树的根结点的子树，访问第一棵树的根结点，中序遍历剩余的树构成的森林。
（3）后序遍历：若森林非空，则遍历方式为：后序遍历森林中第一棵树的根结点的子树，然后后序遍历剩余的树构成的森林，最后访问第一棵树的根结点。


2、二叉树：
二叉树（Binary Tree）是n（n≥0）个结点所构成的集合，它或为空树（n = 0）；或为非空树，对于非空树T
二叉树一般采用链式存储方式：每个结点包含两个指针域，指向两个孩子结点，还包含一个数据域，存储结点信息
层次遍历：
一层一层遍历，父节点出来，子节点进去，直到为空
3、哈夫曼树：
哈夫曼树是一种应用广泛的二叉树，可用来构造最优编码，用于信息传输、数据压缩等方面。
哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树，又称为最优二叉树。


4、平衡二叉树（AVL树）：
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每插入一个结点时，先检查是否因为插入而破坏了树的平衡性，若是，找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使其成为新的平衡子树。
红黑树：红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如即时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。红黑树是二叉树的一种，由于红黑树也是二叉查找树，它们当中每一个节点的比较值都必须大于或等于在它的左子树中的所有节点，并且小于或等于在它的右子树中的所有节点。这确保红黑树运作时能够快速的在树中查找给定的值。


5、哈夫曼编码：
根据字符在文件中出现的频率，用0、1的数字串表示各字符的最佳编码方式，称为哈夫曼（Huffman）编码。哈夫曼编码很好地解决了上述两个关键问题，被广泛应用于数据压缩，尤其是远距离通信和大容量数据存储方面，常用的JPEG图片就是采用哈夫曼编码压缩的。
算法设计：
哈夫曼编码的基本思想是以字符的使用频率作为权构建一棵哈夫曼树，然后利用哈夫曼树对字符进行编码。构造一棵哈夫曼树，是将所要编码的字符作为叶子结点，该字符在文件中的使用频率作为叶子结点的权值，以自底向上的方式，通过n?1次的“合并”运算后构造出的一棵树，核心思想是权值越大的叶子离根越近。
哈夫曼算法采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两棵树作为左右子树，构造一棵新树，新树根节点的权值为其左右孩子结点权值之和，将新树插入到树的集合中，求解步骤如下。
（1）确定合适的数据结构。编写程序前需要考虑的情况有：
哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n?1个结点（n?1次的“合并”，每次产生一个新结点），
构成哈夫曼树后，为求编码，需从叶子结点出发走一条从叶子到根的路径。
译码需要从根出发走一条从根到叶子的路径，那么我们需要知道每个结点的权值、双亲、左孩子、右孩子和结点的信息。
（2）初始化。构造n棵结点为n个字符的单结点树集合T={t1，t2，t3，…，tn}，每棵树只有一个带权的根结点，权值为该字符的使用频率。
（3）如果T中只剩下一棵树，则哈夫曼树构造成功，跳到步骤（6）。否则，从集合T中取出没有双亲且权值最小的两棵树ti和tj，将它们合并成一棵新树zk，新树的左孩子为ti，右孩子为tj，zk的权值为ti和tj的权值之和。
（4）从集合T中删去ti，tj，加入zk。
（5）重复以上（3）～（4）步。
（6）约定左分支上的编码为“0”，右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码，从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。算法结束。


6、：带有平衡条件的树


7、数组与广义表
数组是由相同类型的数据元素构成的有序集合。一维数组看一看作一个线性表
二维数组也可以看作一个线性表，是不是可以看作一个线性表X=(X0，X1，X2，…，Xn-1)？只不过每一个数据元素Xi也是一个线性表。
存储：数组一般采用顺序存储结构，因为存储单元是一维的，而数组可以是多维，如何用一组连续的存储单元来存储多维数组呢？以二维数组为例，可以按行序存储，即先存第一行，再存第二行，…；也可以按列序存储，先存第一列，再存第二列，…；现在比较流行的C语言，Java都是按行序存储的。


八、排序：
冒泡：冒泡排序（Bubble Sort）是一种交换排序，基本思想是两两比较相邻的元素，如果他们的顺序错误就把他们交换过来，直到排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（效率低下）


13.好玩贪吃蛇——数字矩阵
一种思路：先填外围一圈，然后把内部看作一个子问题，继续填充


九、贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
在贪心算法中，我们需要注意以下几个问题。
（1）没有后悔药。一旦做出选择，不可以反悔。
（2）有可能得到的不是最优解，而是最优解的近似解。
（3）选择什么样的贪心策略，直接决定算法的好坏。
1、迪科斯彻算法：最短距离
Dijkstra 算法是解决单源最短路径问题的贪心算法，它先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，直到求出从源点到其他各个顶点的最短路径。
Dijkstra算法的基本思想是首先假定源点为u，顶点集合V被划分为两部分：集合S和 V?S。初始时 S 中仅含有源点 u，其中 S 中的顶点到源点的最短路径已经确定。集合V?S中所包含的顶点到源点的最短路径的长度待定，称从源点出发只经过S中的点到达V?S中的点的路径为特殊路径，并用数组dist[]记录当前每个顶点所对应的最短特殊路径长度。


2、prim算法（最小生成树算法）


3、kruskal算法（最小生成树算法）


4、应用（文件压缩）：
哈夫曼编码
============================网络基础=================================
一.拓扑结构：
计算机网络的拓扑结构是引用拓扑学中研究与大小、形状无关的点、线关系的方法，把网络中的计算机和通信设备抽象为一个点，把传输介质抽象为一条线，由点和线组成的几何图形就是计算机网络的拓扑结构。
计算机网络拓扑结构是指网络中各个站点相互连接的形式，在局域网中明确一点讲就是文件服务器、工作站和电缆等的连接形式。现在最主要的拓扑结构有总线型拓扑、星形拓扑、环形拓扑、树形拓扑（由总线型演变而来）以及它们的混合型。顾名思义，总线型其实就是将文件服务器和工作站都连在称为总线的一条公共电缆上，且总线两端必须有终结器；星形拓扑则是以一台设备作为中央连接点，各工作站都与它直接相连形成星型；而环形拓扑就是将所有站点彼此串行连接，像链子一样构成一个环形回路；把这三种最基本的拓扑结构混合起来运用自然就是混合型了！


二：网络交换方式：
网络按交换方式分类：
电路交换
报文交换
分组交换


三、OSI的基本概念
 
OSI是Open System Interconnect的缩写，意为开放式系统互联。
OSI七层参考模型的各个层次的划分遵循下列原则：
1、同一层中的各网络节点都有相同的层次结构，具有同样的功能。
2、同一节点内相邻层之间通过接口（可以是逻辑接口）进行通信。
3、七层结构中的每一层使用下一层提供的服务，并且向其上层提供服务。
4、不同节点的同等层按照协议实现对等层之间的通信。


TCP/IP协议中的应用层处理开放式系统互联模型中的第五层、第六层和第七层的功能。


OSI中的层 功能 TCP/IP协议族
 
应用层 文件传输，电子邮件，文件服务，虚拟终端 TFTP，HTTP，SNMP，FTP，SMTP，DNS，Telnet
 
表示层 数据格式化，代码转换，数据加密 没有协议
 
会话层 解除或建立与别的接点的联系 没有协议
 
传输层 提供端对端的接口 TCP，UDP
 
网络层 为数据包选择路由 IP，ICMP，RIP，OSPF，BGP，IGMP
 
数据链路层 传输有地址的帧以及错误检测功能 SLIP，CSLIP，PPP，ARP，RARP，MTU
 
物理层 以二进制数据形式在物理媒体上传输数据 ISO2110，IEEE802，IEEE802.2


描述：
第一层：物理层（PhysicalLayer)，
 
规定通信设备的机械的、电气的、功能的和过程的特性，用以建立、维护和拆除物理链路连接。具体地讲，机械 特性规定了网络连接时所需接插件的规格尺寸、引脚数量和排列情况等；电气特性规定了在物理连接上传输bit流时线路上信号电平的大小、阻抗匹配、传输速率 距离限制等；功能特性是指对各个信号先分配确切的信号含义，即定义了DTE和DCE之间各个线路的功能；规程特性定义了利用信号线进行bit流传输的一组 操作规程，是指在物理连接的建立、维护、交换信息是，DTE和DCE双放在各电路上的动作系列。在这一层，数据的单位称为比特（bit）。属于物理层定义的典型规范代表包括：EIA/TIA RS-232、EIA/TIA RS-449、V.35、RJ-45等。


第二层：数据链路层（DataLinkLayer):
 
在物理层提供比特流服务的基础上，建立相邻结点之间的数据链路，通过差错控制提供数据帧（Frame）在信道上无差错的传输，并进行各电路上的动作系列。数据链路层在不可靠的物理介质上提供可靠的传输。该层的作用包括：物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。在这一层，数据的单位称为帧（frame）。数据链路层协议的代表包括：SDLC、HDLC、PPP、STP、帧中继等。


第三层是网络层
 
在 计算机网络中进行通信的两个计算机之间可能会经过很多个数据链路，也可能还要经过很多通信子网。网络层的任务就是选择合适的网间路由和交换结点， 确保数据及时传送。网络层将数据链路层提供的帧组成数据包，包中封装有网络层包头，其中含有逻辑地址信息- -源站点和目的站点地址的网络地址。如 果你在谈论一个IP地址，那么你是在处理第3层的问题，这是“数据包”问题，而不是第2层的“帧”。IP是第3层问题的一部分，此外还有一些路由协议和地 址解析协议（ARP）。有关路由的一切事情都在这第3层处理。地址解析和路由是3层的重要目的。网络层还可以实现拥塞控制、网际互连等功能。在这一层，数据的单位称为数据包（packet）。网络层协议的代表包括：IP、IPX、RIP、OSPF等。


第 四层是处理信息的传输层
 
第4层的数据单元也称作数据包（packets）。但是，当你谈论TCP等具体的协议时又有特殊的叫法，TCP的数据单元称为段 （segments）而UDP协议的数据单元称为“数据报（datagrams）”。这个层负责获取全部信息，因此，它必须跟踪数据单元碎片、乱序到达的 数据包和其它在传输过程中可能发生的危险。第4层为上层提供端到端（最终用户到最终用户）的透明的、可靠的数据传输服务。所为透明的传输是指在通信过程中 传输层对上层屏蔽了通信传输系统的具体细节。传输层协议的代表包括：TCP、UDP、SPX等。


第五层是会话层
 
这一层也可以称为会晤层或对话层，在会话层及以上的高层次中，数据传送的单位不再另外命名，而是统称为报文。会话层不参与具体的传输，它提供包括访问验证和会话管理在内的建立和维护应用之间通信的机制。如服务器验证用户登录便是由会话层完成的。


第六层是表示层
 
这一层主要解决拥护信息的语法表示问题。它将欲交换的数据从适合于某一用户的抽象语法，转换为适合于OSI系统内部使用的传送语法。即提供格式化的表示和转换数据服务。数据的压缩和解压缩， 加密和解密等工作都由表示层负责。
 
第七层应用层
 
应用层为操作系统或网络应用程序提供访问网络服务的接口。应用层协议的代表包括：Telnet、FTP、HTTP、SNMP等。


四。网关：
网关（Gateway）[1]  就是一个网络连接到另一个网络的“关口”。也就是网络关卡。
那么网关到底是什么呢？网关实质上是一个网络通向其他网络的IP地址。比如有网络A和网络B，网络A的IP地址范围为“192.168.1.1~192. 168.1.254”，子网掩码为255.255.255.0；网络B的IP地址范围为“192.168.2.1~192.168.2.254”，子网掩码为255.255.255.0。在没有路由器的情况下，两个网络之间是不能进行TCP/IP通信的，即使是两个网络连接在同一台交换机（或集线器）上，TCP/IP协议也会根据子网掩码（255.255.255.0）判定两个网络中的主机处在不同的网络里。而要实现这两个网络之间的通信，则必须通过网关。如果网络A中的主机发现数据包的目的主机不在本地网络中，就把数据包转发给它自己的网关，再由网关转发给网络B的网关，网络B的网关再转发给网络B的某个主机


五：IP地址：
Internet上的每台主机(Host)都有一个唯一的IP地址。IP协议就是使用这个地址在主机之间传递信息，这是Internet 能够运行的基础。IP地址的长度为32位(共有2^32个IP地址)，分为4段，每段8位，用十进制数字表示，每段数字范围为0～255，段与段之间用句点隔开。例如159.226.1.1。IP地址可以视为网络标识号码与主机标识号码两部分，因此IP地址可分两部分组成，一部分为网络地址，另一部分为主机地址。
分为A-E类，A类网络地址最小，主机数量最大。
在一个局域网中，有两个IP地址比较特殊，一个是网络号，一个是广播地址。网络号是用于三层寻址的地址，它代表了整个网络本身；另一个是广播地址，它代表了网络全部的主机。网络号是网段中的第一个地址，广播地址是网段中的最后一个地址，这两个地址是不能配置在计算机主机上的。


六：子网掩码：
子网掩码不能单独存在，它必须结合IP地址一起使用。子网掩码只有一个作用，就是将某个IP地址划分成网络地址和主机地址两部分。
子网掩码是一个32位地址，用于屏蔽IP地址的一部分以区别网络标识和主机标识，并说明该IP地址是在局域网上，还是在远程网上。
子网掩码为255.255.255.255减去主机数就是子网掩码

最后

以上就是哭泣小蘑菇为你收集整理的数据结构总结及网络基础的全部内容，希望文章能够帮你解决数据结构总结及网络基础所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。