Java考研试题之数据结构解法

今天去网上看了一下09年的Java考研试题，看见该题目（图片）：

成都创新互联自2013年起，是专业互联网技术服务公司，拥有项目成都做网站、网站建设、外贸营销网站建设网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元来宾做网站,已为上家服务,为来宾各地企业和个人服务,联系电话:18980820575

先来定义结点（为了简便，省略set/get）：

 
 
 
 
    
  
  
  
  
  1. public class Node  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.  public int data;  
    4.   
  
  
  
  4.  public Node link;  
    5.   
  
  
  
  5. }  
    6.

对于这个Java考研试题，我能想到的两种解法，一个基于递归：

递归版的思路就是，基于当前结点，如果后一个是倒数第K-1，那么当前结点是所求，若不然，返回当前是倒数第几个。

 
 
 
 
    
  
  
  
  
  1. public int printRKWithRecur(Node head,int k)  
    2.   
  
  
  
  2.     {  
    3.   
  
  
  
  3.         if(k==0||head==null||head.link==null)return 0;  
    4.   
  
  
  
  4.         if(_recurFind(head.link,k)>=k)return 1;  
    5.   
  
  
  
  5.         return 0;  
    6.   
  
  
  
  6.     }  
    7.   
  
  
  
  7.     private final int _recurFind(Node node, int k) {  
    8.   
  
  
  
  8.         if(node.link==null)  
    9.   
  
  
  
  9.         {  
    10.   
  
  
  
  10.             return 1;  
    11.   
  
  
  
  11.         }  
    12.   
  
  
  
  12.         int sRet=_recurFind(node.link,k);  
    13.   
  
  
  
  13.         if(sRet==k-1)  
    14.   
  
  
  
  14.         {  
    15.   
  
  
  
  15.             System.out.println("Got:"+node.data);  
    16.   
  
  
  
  16.             return k;  
    17.   
  
  
  
  17.         }  
    18.   
  
  
  
  18.         return sRet+1;  
    19.   
  
  
  
  19.     } 
    20.

对每个结点，该算法都只访问一次，因此复杂度O（N）。

第二解法，相对递归来说，这种方法可以算是消除递归版，而且从某种意义上来说比递归更高效，跟省空间，递归版实际上是把回溯的数据存在栈上，而版方法是自己存储，且利用数组实现一个循环队列，只存储K个元素。

 
 
 
 
    
  
  
  
  
  1. public static class CycleIntQueue  
    2.   
  
  
  
  2.     {  
    3.   
  
  
  
  3.         int[] datas;  
    4.   
  
  
  
  4.         int top=0;  
    5.   
  
  
  
  5.         int num=0;  
    6.   
  
  
  
  6.         public CycleIntQueue(int n)  
    7.   
  
  
  
  7.         {  
    8.   
  
  
  
  8.             datas=new int[n];  
    9.   
  
  
  
  9.         }  
    10.   
  
  
  
  10.           
    11.   
  
  
  
  11.         public void push(int i)  
    12.   
  
  
  
  12.         {  
    13.   
  
  
  
  13.             datas[(top++)%datas.length]=i;  
    14.   
  
  
  
  14.             num++;  
    15.   
  
  
  
  15.               
    16.   
  
  
  
  16.         }  
    17.   
  
  
  
  17.         public int numPushed()  
    18.   
  
  
  
  18.         {  
    19.   
  
  
  
  19.             return num;  
    20.   
  
  
  
  20.         }  
    21.   
  
  
  
  21.           
    22.   
  
  
  
  22.           
    23.   
  
  
  
  23.         public int getButtom()  
    24.   
  
  
  
  24.         {  
    25.   
  
  
  
  25.             return datas[top%datas.length];  
    26.   
  
  
  
  26.         }  
    27.   
  
  
  
  27.     }  
    28.   
  
  
  
  28.     public int printRKWithCycleQueue(Node head,int k)  
    29.   
  
  
  
  29.     {  
    30.   
  
  
  
  30.         if(k==0||head==null)return 0;  
    31.   
  
  
  
  31.         CycleIntQueue queue=new CycleIntQueue(k);  
    32.   
  
  
  
  32.         Node cur=head.link;  
    33.   
  
  
  
  33.         while(cur!=null)  
    34.   
  
  
  
  34.         {  
    35.   
  
  
  
  35.             queue.push(cur.data);  
    36.   
  
  
  
  36.             cur=cur.link;  
    37.   
  
  
  
  37.         }  
    38.   
  
  
  
  38.         if(queue.numPushed() return 0;   
    39.   
  
  
  
  39.           
    40.   
  
  
  
  40.         System.out.println("Got:"+queue.getButtom());  
    41.   
  
  
  
  41.         return 1;  
    42.   
  
  
  
  42.     } 
    43.

本算法，都每个结点也只放一次，另外进行一次入队操作，该操作复杂度O(1),从而，整个算法复杂度仍是O(N).

对于此Java考研试题还有另外一种算法，该算法的空间复杂度为O（1），时间复杂度为O（n）。这在空间复杂度和时间复杂度上应该是比较优化了。

本算法的基本思想如下：既然是查找倒数第K个结点（注意，不是正数，否则就没什么可讨论的了），而且链表是单向的，还不能改变表结构，这就意味着只能从前往后扫描结点。我们首先要知道这个链表有多少个结点（如果总结点数都不知道，何谈倒数？），这个非常简单，只要从头扫描一下链表，再计一下数即可。

在同一时间从事多项工作会大大提升效率，当然，扫描链表也不例外，在扫描链表的同时，还需要做一些其他的工作。既然只能从前向后扫描链表，而且要求倒数第K个结点，那就让我们把这个链表按长度为K分成若干块，而最后扫描的结果要么结点数是K的整数倍（模为0），要么余数（模）不为0（多出几个结点，多出的结点数小于K）。

先看看第二种情况。

假设有12个结点的链表，每一个结点的值从前往后分别是1至12，如下所示：

1  2  3  4  5  6  7  8  9  10  11 12

假设我们要求倒数第5个结点，我们直接就可以看出结果是8.那么用程序如何处理呢？

先按长度为5将上面的结点分成三个区域，如下：

1 2 3 4 5   6 7 8 9 10   11 12

注意，不是物理分，而是使用变量来保存区域的边界（也就是区域最后一个结点的对象）。

从上面的分隔可以看出，最后剩下两个结点，既然是求倒数第5个，而最后剩下了两个，那么还缺5-2=3个，因此，只需要从倒数第二个块（6 7 8 9 10）略过前两个，第三个结点（8）就是我们要求的结果，而5就是题中的k，2就是结点数与k的模，因此，可以推出一个公式，倒数第k个结点就是按长度为k按分成的若干块中的第二块的第（结点数 % k+ 1）个结点。

下面来看看（结点数 % k）为0的情况。假设上面的例子中的k为4，正确的输出结果应为9，分块如下：

1 2 3 4  5 6 7 8  9 10 11 12

从上面的三个块可以看出，结果正好是最后一个块的第一个结点，这时mod为0（mod=结点数 % k），因此，在这种情况也可以使用上面的公式，只是变成了最后一个块。

根据上面的基本思想可以设两个指针，p1和p2，其中p1最终指向倒数第2个完整块，p2最终指向倒数第1个完整块，对于第一种情况，p1指向5，p2指向10，这时可以使p1向后移动（k - mod）个结点即可（从5移动3个正好是8）。而对于第二种情况，p1指向8，p2指向12，而mod=0，这时的结果仍然是mod+1，也就是p1向后移动1个结点就是所求的结果。 为了满足（k=结点数）的情况，需要将p1的初始值设为头结点，这样如果（k=结点数），就直接从头结点向后移动一个结点就是最后的结果，如上面的例子求倒数第12个结点，也就是求正数第1个结点。

下面是这个算法的具体实现（包括核心算法、生成链表及调用核心算法的代码）：

 
 
 
 
    
  
  
  
  
  1. public class Test  
    2.   
  
  
  
  2. {  
    3.   
  
  
  
  3.     static class Node  
    4.   
  
  
  
  4.     {  
    5.   
  
  
  
  5.         public int data;  
    6.   
  
  
  
  6.         public Node nextNode;  
    7.   
  
  
  
  7.     }  
    8.   
  
  
  
  8.     //////////////////////////////////////////  
    9.   
  
  
  
  9.     //  核心算法  
    10.   
  
  
  
  10.     private static int findNode(Node headNode, int k)  
    11.   
  
  
  
  11.     {  
    12.   
  
  
  
  12.         Node p = headNode, p1 = headNode, p2 = null;   
    13.   
  
  
  
  13.         int count = 0;  //  表示结点数  
    14.   
  
  
  
  14.         while (p.nextNode != null)  
    15.   
  
  
  
  15.         {  
    16.   
  
  
  
  16.             p = p.nextNode;  
    17.   
  
  
  
  17.             count++;  
    18.   
  
  
  
  18.             //  遇到k的整数位个结点，进行分块  
    19.   
  
  
  
  19.             if (count % k == 0)   
    20.   
  
  
  
  20.             {                  
    21.   
  
  
  
  21.                 if (p2 != null)  
    22.   
  
  
  
  22.                     p1 = p2;  
    23.   
  
  
  
  23.                 p2 = p;  
    24.   
  
  
  
  24.             }  
    25.   
  
  
  
  25.         }  
    26.   
  
  
  
  26.         //  k超过链表结点数，未找到，返回0  
    27.   
  
  
  
  27.         // 此处也可以用k > count来判断  
    28.   
  
  
  
  28.         if (p2 == null)    
    29.   
  
  
  
  29.         {  
    30.   
  
  
  
  30.             return 0;  
    31.   
  
  
  
  31.         }  
    32.   
  
  
  
  32.         else 
    33.   
  
  
  
  33.         {  
    34.   
  
  
  
  34.             int mod = count % k;  
    35.   
  
  
  
  35.             int offset = mod + 1;  // 任何情况下，最终结果都是p1指向的结点向后移动(mod + 1)个结点  
    36.   
  
  
  
  36.             for (int i = 0; i < offset; i++)  
    37.   
  
  
  
  37.                 p1 = p1.nextNode;  
    38.   
  
  
  
  38.             System.out.println(p1.data);  
    39.   
  
  
  
  39.             return 1;  
    40.   
  
  
  
  40.         }  
    41.   
  
  
  
  41.     }  
    42.   
  
  
  
  42.     ////////////////////////////////////////  
    43.   
  
  
  
  43.     public static void main(String[] args) throws Exception  
    44.   
  
  
  
  44.     {  
    45.   
  
  
  
  45.         //产生一个包含1个头结点和120个结点的链表  
    46.   
  
  
  
  46.         Node headNode = new Node();  
    47.   
  
  
  
  47.         Node p = headNode;  
    48.   
  
  
  
  48.         for (int i = 0; i < 120; i++)  
    49.   
  
  
  
  49.         {  
    50.   
  
  
  
  50.             p.nextNode = new Node();  
    51.   
  
  
  
  51.             p.nextNode.data = i + 1;  
    52.   
  
  
  
  52.             p = p.nextNode;  
    53.   
  
  
  
  53.         }  
    54.   
  
  
  
  54.         p.nextNode = null;  
    55.   
  
  
  
  55.         //  开始查找倒数第k个结点，如果找到，返回1，并输出结点的data值  
    56.   
  
  
  
  56.         System.out.println(findNode(headNode, 12));  
    57.   
  
  
  
  57.     }  
    58.   
  
  
  
  58. } 
    59.

上面程序的输出结果如下：

109
1

新闻名称：Java考研试题之数据结构解法
文章分享：http://www.shufengxianlan.com/qtweb/news47/509147.html

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

广告

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

猜你还喜欢下面的内容

网站设计公司知识

同城分类信息

成都网站建设　　 　自贡托管服务器　　 　成都网络推广　　 　营销型网站建设　　 　成都网站改版　　 　眉山服务器托管　　 　自贡网站建设　　 　校园网站建设方案　　 　vi形象设计　　 　免备案虚拟主机　　 　响应式网站　　 　巴彦网站建设　　 　广安网站制作公司　　 　微信小程序公众号开发　　 　Android开发　　 　中晴建设　　 　成都网站制作公司　　 　成都定制网站　　 　香港虚拟主机　　 　宜宾网站营销推广