你所能用到的数据结构（一）

 无损编码的霍夫曼编码以及其余的各种编码由于要使用比较复杂的数据结构，所以按照我昨天说的，我决定从数据结构开始写起。数据结构和算法很难完全的分开，好的数据结构能够提升算法的效率，而如果没有算法，单纯的谈数据结构，那么数据结构的应用价值就会大大的降低。那么，就从最基本的开始这一个系列吧。

成都创新互联公司是专业的和平网站建设公司，和平接单;提供网站建设、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行和平网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

一、总是让人很抽象的算法分析

     算法分析基本是所有数据结构与算法的***章要讲的内容，大0表示法什么的总是让人很抽象，对于初学者，其实这一章的意义并不是很大，因为你很遇到在实际开发中一些大数据集的问题，在小规模数据的时候，各个算法之间的差别很难分辨出来。这就好比计算5个数的和，大家所用的时间基本都会差不多，但是要是计算5000个数的和，那么天才和一般人之间的差距就会体现出来了，这也就是为什么对于一个大型企业，一个人才远远比10个干事的人重要的原因。

     算法分析的还有一个作用就是让学计算机的明白，计算机虽然快，但是计算机不是***的，计算机再牛逼也不能很容易的就处理成万上亿的数据的。比如说我们用的QQ,虽然经常说腾讯抄袭，网络即时通信软件但从技术上来说不是特别难，难的是几千万人同时在线一点也不开，你的好友下线了，你马上就能收到通知，这一点不是很容易就能做到的。反例就是铁道部的订票网站，为什么经常崩溃，被万人辱骂，算法和优化的失败就是很大的原因。优化是商业软件一个永恒的主题，如果在最初学习的时候能有这样一个概念，我相信对于以后是有很大帮助的。

     下面来说说大O表示法吧，从O(N)说起，不说那些算法时间复杂度上界什么什么的，如果你对这个有兴趣的话，可以查阅一下算法的书籍，我觉得这个东西最简单的理解方式就是利用循环，对于一个循环从1到N，然后对一个数组a赋值，也就是for(int i=0;i

     对于其他的大O表示法的问题基本都可以按照这个方法类推，对于一个算法能达到O(N)已经是非常非常牛逼的，极个别的比如二分查找可以达到很快的速度，但是不能忽视它前面的需要进行排序预处理。如果对于一个排序算法，按照一个人的正常思维，首先，你需要将待排序的所有数浏览一遍，然后才能确定哪个大哪个小，这样才能进行排序，如此一来对于一组待排序的数，你需要浏览两遍数组才能完成，那么这个人眼扫描算法的效率就是O(N*N)的。

     为了直观的显示效率的意义，按照我写这一系列文章重点一定要突出实际的编程，采用C++写了一段程序来显示随着规模的增长，冒泡和快速算法所用的时间的增长，为了对比，加入了空白对照组，先展示结果吧。

  

     ***行和第二行是两个空循环，可以看到，第二行的数据规模是***行的两倍，其处理时间也差不多是两倍，也就是算法复杂度是O(N)。

     第三行和第四行分别是两个不同规模的冒泡排序，冒泡排序算法复杂度是O(N*N)，可以看到第三行是第四行处理速度大约4倍。

     第五行和第六行分别是两个不同规模的快速排序，快速排序的算法复杂度是O(N*LogN），至于为什么，放在后面的文章中再分析。

     N*LogN这个是非常小的，所以***两行所耗费的时间差不多，从这三组数据可以看出一个好的算法对于一个软件的运行速度影响之大，一个冒泡算法处理30000个数据时快速排序处理100000的将近40倍，所以说算法可以说是衡量一个工程师好与坏的重要标准。

     下面贴出所有代码，clock函数是用来计时的， 这里要提出的一点是这里的冒泡和快速排序算法不是我写的，都是复制的，毕竟目前介绍的重点还不是这个，另外这个快速排序是标准里面的，很有参考学习价值。

 
 
 
 
      
  
  
  
  1. int main() 
    2.   
  
  
  
  2. { 
    3.   
  
  
  
  3.     const long int num=100000; 
    4.   
  
  
  
  4.    
    5.   
  
  
  
  5.   clock_t begin, end; 
    6.   
  
  
  
  6.   double  cost; 
    7.   
  
  
  
  7.  
    8.   
  
  
  
  8.   int dat[num]; 
    9.   
  
  
  
  9.   srand( (unsigned int)time(0) ); 
    10.   
  
  
  
  10.   for (int i = 0; i < 30000; i++){ 
    11.   
  
  
  
  11.        dat[i] = rand(); 
    12.   
  
  
  
  12.   } 
    13.   
  
  
  
  13.   begin = clock(); 
    14.   
  
  
  
  14.   for(int loop=0;loop<10000000;loop++); 
    15.   
  
  
  
  15.   end = clock(); 
    16.   
  
  
  
  16.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    17.   
  
  
  
  17.   cout<<"loop for 10000000 values:"<  
  
  
  
  18.  
    19.   
  
  
  
  19.   begin = clock(); 
    20.   
  
  
  
  20.   for(int loop=0;loop<20000000;loop++); 
    21.   
  
  
  
  21.   end = clock(); 
    22.   
  
  
  
  22.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    23.   
  
  
  
  23.   cout<<"loop for 20000000 values:"<  
  
  
  
  24.  
    25.   
  
  
  
  25.     
    26.   
  
  
  
  26.   bubble(dat,30000); 
    27.   
  
  
  
  27.    
    28.   
  
  
  
  28.   srand( (unsigned int)time(0) ); 
    29.   
  
  
  
  29.   for (int i = 0; i < 15000; i++){ 
    30.   
  
  
  
  30.        dat[i] = rand(); 
    31.   
  
  
  
  31.   } 
    32.   
  
  
  
  32.  
    33.   
  
  
  
  33.   bubble(dat,15000); 
    34.   
  
  
  
  34.    
    35.   
  
  
  
  35.  
    36.   
  
  
  
  36.   srand( (unsigned int)time(0) ); 
    37.   
  
  
  
  37.   for (int i = 0; i < 100000; i++){ 
    38.   
  
  
  
  38.        dat[i] = rand(); 
    39.   
  
  
  
  39.   } 
    40.   
  
  
  
  40.  
    41.   
  
  
  
  41.   begin = clock(); 
    42.   
  
  
  
  42.   quickSort(dat,100000); 
    43.   
  
  
  
  43.   end = clock(); 
    44.   
  
  
  
  44.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    45.   
  
  
  
  45.   cout<<"qsort for 1000000 values:"<  
  
  
  
  46.  
    47.   
  
  
  
  47.      
    48.   
  
  
  
  48.    srand( (unsigned int)time(0) ); 
    49.   
  
  
  
  49.   for (int i = 0; i < 50000; i++){ 
    50.   
  
  
  
  50.        dat[i] = rand(); 
    51.   
  
  
  
  51.   } 
    52.   
  
  
  
  52.   begin = clock(); 
    53.   
  
  
  
  53.   quickSort(dat,50000); 
    54.   
  
  
  
  54.   end = clock(); 
    55.   
  
  
  
  55.   cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    56.   
  
  
  
  56.   cout<<"qsort for 500000 values:"<  
  
  
  
  57.   int i; 
    58.   
  
  
  
  58.   cin>>i; 
    59.   
  
  
  
  59.   return 0; 
    60.   
  
  
  
  60. } 
    61.   
  
  
  
  61.  
    62.   
  
  
  
  62. void quickSort(int numbers[], int array_size) 
    63.   
  
  
  
  63. { 
    64.   
  
  
  
  64.   q_sort(numbers, 0, array_size - 1); 
    65.   
  
  
  
  65. } 
    66.   
  
  
  
  66.  
    67.   
  
  
  
  67.  
    68.   
  
  
  
  68.  
    69.   
  
  
  
  69. void q_sort(int numbers[], int left, int right) 
    70.   
  
  
  
  70. { 
    71.   
  
  
  
  71.   int pivot, l_hold, r_hold; 
    72.   
  
  
  
  72.  
    73.   
  
  
  
  73.   l_hold = left; 
    74.   
  
  
  
  74.   r_hold = right; 
    75.   
  
  
  
  75.   pivot = numbers[left]; 
    76.   
  
  
  
  76.   while (left < right) 
    77.   
  
  
  
  77.   { 
    78.   
  
  
  
  78.     while ((numbers[right] >= pivot) && (left < right)) 
    79.   
  
  
  
  79.       right--; 
    80.   
  
  
  
  80.     if (left != right) 
    81.   
  
  
  
  81.     { 
    82.   
  
  
  
  82.       numbers[left] = numbers[right]; 
    83.   
  
  
  
  83.       left++; 
    84.   
  
  
  
  84.     } 
    85.   
  
  
  
  85.     while ((numbers[left] <= pivot) && (left < right)) 
    86.   
  
  
  
  86.       left++; 
    87.   
  
  
  
  87.     if (left != right) 
    88.   
  
  
  
  88.     { 
    89.   
  
  
  
  89.       numbers[right] = numbers[left]; 
    90.   
  
  
  
  90.       right--; 
    91.   
  
  
  
  91.     } 
    92.   
  
  
  
  92.   } 
    93.   
  
  
  
  93.   numbers[left] = pivot; 
    94.   
  
  
  
  94.   pivot = left; 
    95.   
  
  
  
  95.   left = l_hold; 
    96.   
  
  
  
  96.   right = r_hold; 
    97.   
  
  
  
  97.   if (left < pivot) 
    98.   
  
  
  
  98.     q_sort(numbers, left, pivot-1); 
    99.   
  
  
  
  99.   if (right > pivot) 
    100.   
  
  
  
  100.     q_sort(numbers, pivot+1, right); 
    101.   
  
  
  
  101. } 
    102.   
  
  
  
  102.  
    103.   
  
  
  
  103. void bubble(int a[],int length) 
    104.   
  
  
  
  104. { 
    105.   
  
  
  
  105.      
    106.   
  
  
  
  106.    clock_t begin, end; 
    107.   
  
  
  
  107.   double  cost; 
    108.   
  
  
  
  108.     int temp; 
    109.   
  
  
  
  109.  
    110.   
  
  
  
  110.     begin = clock(); 
    111.   
  
  
  
  111.     for(int j=0;j<=length-1;j++) 
    112.   
  
  
  
  112.     {  
    113.   
  
  
  
  113.        for (int i=0;i  
  
  
  
  114.         if (a[i]>a[i+1]) 
    115.   
  
  
  
  115.         {  
    116.   
  
  
  
  116.             temp=a[i]; 
    117.   
  
  
  
  117.             a[i]=a[i+1]; 
    118.   
  
  
  
  118.             a[i+1]=temp; 
    119.   
  
  
  
  119.         } 
    120.   
  
  
  
  120.     } 
    121.   
  
  
  
  121.     end = clock(); 
    122.   
  
  
  
  122.    cost = (double)(end - begin) / CLOCKS_PER_SEC; 
    123.   
  
  
  
  123.    cout<<"bubble for "<  
  
  
  
  124.      
    125.   
  
  
  
  125. } 
    126.

      我写的“你所能用到的”这个系列，重点在于实现，如果你需要补充各种知识，请参考一些书籍，我一直的观点是编程就像游泳一样，游泳重要的是要下水试而不是什么游泳理论，当你学会了游泳之后，游泳理论可以帮你快速提高，但如果只会游泳理论，你是永远也不会游泳，所以我的系列里保证所有贴出的代码是一定都能用的，能运行处结果的，这样对于初学者是一个成就感的反馈。

本文标题：你所能用到的数据结构（一）
网页URL：http://www.hantingmc.com/qtweb/news31/222481.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

ChatGPT知识

分类信息网站

响应式网站建设公司　　 　成都酒店服定制　　 　攀枝花网站建设　　 　成都网络推广　　 　网站推广　　 　LED显示屏　　 　四川电信机房托管　　 　成都定制网站开发　　 　成都包装设计公司　　 　雅安服务器托管　　 　成都网站制作　　 　微官网开发　　 　手机网站制作设计　　 　移动服务器托管　　 　新网创想　　 　软文平台　　 　成都富士康招工　　 　正泰动物制药　　 　手机APP开发　　 　域名注册