数据结构基本知识(1)

向右看齐 2021-11-02 15:31 237阅读 0赞

1:链表的优势在于新增加的元素；而数组在定义的时候已经决定呢内存的空间。链表插入时，只需修改该元素的前一个地址，而数组需要将整体后移。

2：链表的缺点在于读取的效率低，为了知道第三个元素，必须知道第二个或者第四个元素。元素只需要知道索引就可以快速查阅该元素。

3：数据和链表的运行时间：

4：使用循环，程序的性能可能更高，使用递归，程序可能更容易理解。

递归分为俩个部分：基线条件和递归条件。

5： 栈：使用递归的时候通常遇到栈，特点：压入和弹出。每一次递归调用都可以缩小问题的规模，才有意义。

6 ：“分而制之” 是算法的一种重要方法。

7： 各种排序算法：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>算法</td> 
   <td>二分查找</td> 
   <td>简单查找</td> 
   <td>快速排序</td> 
   <td>选择排序</td> 
   <td>旅行商问题</td> 
  </tr> 
  <tr> 
   <td>运行时间</td> 
   <td>O(log N)</td> 
   <td>O(N)</td> 
   <td>O(NlogN)</td> 
   <td>O(N*N)</td> 
   <td>O(n!)</td> 
  </tr> 
 </tbody> 
</table>

8:散列表类似于字典，对于同样的输入，散列表必须有同样的输出。散列表提供了许多映射的功能。例如利用网址映射到，IP地址访问网站。

散列表的用途：模拟映射关系

防止重复

缓存/记住数据，以免服务器再通过处理来生成他们

9 : 网页缓存的作用：1： 使用户更快的查看网页

2： 减少服务器的工作负担

10：散列函数很重要，散列函数可能将所有的按键都映射到一个位置，而最理想的情况是 散列函数将键均匀的映射到散列表的不同位置。           如果被存储到同一位置，则使用链表。