`
pxjianke
  • 浏览: 22238 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

不用链表实现一个算法

阅读更多
题目:有n个人坐成一个圈,从1开始数,数到3,3的人被剔除。按着这样继续下去。直到最后留下一个人为止。问这个人的序号是多少?
我原来用java加上链表,没有实现出来。很悲哀。
回家想了一下用以下方法实现出来:
先定义类LinkForm:
public class LinkForm {
private int inum;
private int iflag; 

public int getInum() {
return inum;
}

public void setInum(int inum) {
this.inum = inum;
}

public int getIflag() {
return iflag;
}

public void setIflag(int iflag) {
this.iflag = iflag;
}
public String toString(){
StringBuilder sb=new StringBuilder();
sb.append("inum:");
sb.append(inum<10?"0"+inum:inum);
sb.append("   ");
sb.append("iflag:");
sb.append(iflag);
sb.append("   ");

return sb.toString();
}
}
在主类中。我定义如下:
import java.util.ArrayList;
import java.util.List;

public class MathSort {

protected List<LinkForm> init(int n) {
List<LinkForm> list = new ArrayList<LinkForm>(n);
for (int i = 0; i < n; i++) {
LinkForm form = new LinkForm();
form.setIflag(1);
form.setInum(i + 1);
list.add(form);
}
return list;
}

public void print(List<LinkForm> list) {
System.out.println("********************");
for (LinkForm form : list) {
System.out.println(form.toString());
}
}

public void sort(List<LinkForm> list) {
int n = list.size();
if (n > 2) {
int m = 0;
int icount = 0;
while (n - icount >1) {
for (int i = 0; i < n; i++) {
LinkForm form = list.get(i);
if (form.getIflag()>0) {
m++;
}
if (m % 3 == 0&& m!=0 ) {
m = 0;
form.setIflag(0);
list.set(i, form);  
print(list);
icount++;
}

}
}
print(list);
for(LinkForm form:list){
if(form.getIflag()>0){
System.out.println(form.getInum());
}
}
} else {
System.out.println(n);
}
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MathSort sort = new MathSort();
List<LinkForm> list = sort.init(12);
sort.sort(list);
}

}
最终实现了题目所提出来的要求。现在回想起来,很郁闷啊。居然没有完成这个。现在记下来,以备自己将来使用。
0
0
分享到:
评论
1 楼 pxjianke 2010-07-12  
修改后真正不使用链表
public class LinkForm {
private int inum;
private int iflag;

public int getInum() {
return inum;
}

public void setInum(int inum) {
this.inum = inum;
}

public int getIflag() {
return iflag;
}

public void setIflag(int iflag) {
this.iflag = iflag;
}
public String toString(){
StringBuilder sb=new StringBuilder();
sb.append("inum:");
sb.append(inum<10?"0"+inum:inum);
sb.append("   ");
sb.append("iflag:");
sb.append(iflag);
sb.append("   ");

return sb.toString();
}
}
在主类中。我定义如下:
public class MathSort {
protected LinkForm[] init(int n) {
LinkForm[] list = new LinkForm[n];
for (int i = 0; i < n; i++) {
LinkForm form = new LinkForm();
form.setIflag(1);
form.setInum(i + 1);
list[i]=form;
}
return list;
}

public void print(LinkForm[] list) {
System.out.println("********************");
for (LinkForm form : list) {
System.out.println(form.toString());
}
}

public void sort(LinkForm[] list) {
int n = list.length;
if (n > 2) {
int m = 0;
int icount = 0;
while (n - icount > 1) {
for (int i = 0; i < n; i++) {
LinkForm form = list[i];
if (form.getIflag() > 0) {
m++;
}
if (m % 3 == 0 && m != 0) {
m = 0;
form.setIflag(0);
list[i]=form;
print(list);
icount++;
}

}
}
print(list);
for (LinkForm form : list) {
if (form.getIflag() > 0) {
System.out.println(form.getInum());
}
}
} else {
System.out.println(n);
}
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MathSort sort = new MathSort();
LinkForm[] list = sort.init(12);
sort.sort(list);
}
}

相关推荐

    基于链表实现的排序算法以及性能分析

    在链表实现时,我们可以使用一个哨兵结点来简化实现过程。 插入排序 插入排序是一种简单的排序算法,它的基本思想是将未排序的序列中的每个元素插入到已排序的序列中。这种算法的时间复杂度为O(n^2)。在链表实现时...

    插入,选择排序的链表实现及快速,希尔,冒泡排序算法实现合集

    链表实现中,遍历每个元素,将每个元素插入到已排序部分的正确位置,形成一个有序序列。`insert_sort_linken_list.c`文件应该包含了链表版插入排序的实现。 2. 选择排序(Selection Sort) 选择排序是一种不稳定的...

    c语言链表的排序算法-排序链表最快的算法是什么?.pdf

    链表排序算法的性能分析和优化是一个非常重要的研究方向。选择合适的排序算法和优化链表的缓存性能是提高链表排序速度的关键。同时,我们还需要考虑到具体的计算机环境和链表的特点,以便选择最适合的排序算法和优化...

    数据结构的双链表算法

    在C++中实现双链表,通常会定义一个结构体(或类)来表示链表节点,包括数据域和两个指针域。同时,还需要提供一个链表类,包含对链表的操作方法如插入、删除、遍历等。这些方法可能需要通过迭代或递归的方式来完成...

    C++ 链表实现两个一元多项式相加

    总的来说,C++中链表实现一元多项式的加法是一种巧妙而实用的方法,它结合了数据结构和算法的知识,展示了计算机科学的魅力。通过熟练掌握这样的编程技巧,不仅可以提高编程能力,还能为解决更复杂的问题打下坚实的...

    几种排序算法的实现(链表)

    这里我们主要探讨的是使用链表实现的排序算法。链表是一种非连续、非顺序的存储结构,每个元素称为节点,包含数据域和指针域,通过指针将节点串联起来。下面我们将详细解析链表实现的几种排序算法,以及它们的优缺点...

    利用双向循环链表实现快速排序算法

    利用了双向循环链表实现了快速排序算法

    链表实现两个多项式的相加

    在计算机科学中,数据结构是算法的基础,而链表作为一种重要的数据结构,有着广泛的应用。本主题关注的是如何使用链表来实现两个多项式的相加。在这个过程中,我们将深入理解链表的特性,并探讨如何利用这些特性来...

    Java算法(链表操作实例)

    在编程领域,算法是解决问题的关键,而链表作为一种基础数据结构,在实现各种复杂算法时扮演着重要角色。本文将深入探讨Java中链表的操作实例,旨在帮助开发者更好地理解和运用链表来解决实际问题。 首先,我们需要...

    多项式相加链表实现.docx

    "多项式相加链表实现" 在计算机科学中,链表是一种常用的数据结构,它可以用来存储和操作多项式。多项式是一种特殊的数学表达式,由变量和系数组成。为了实现多项式的相加操作,我们可以使用链表来存储多项式的每一...

    由链表实现的存储管理 先出页面置换算法、最近最少使用LRU页面置换算法、最佳置换算法

    本主题聚焦于通过链表实现的存储管理,特别是涉及了三种重要的页面置换算法:先出(FIFO)页面置换算法、最近最少使用(LRU)页面置换算法和最佳(OPT)置换算法。 首先,内存分配与回收是存储管理的基础。当一个新...

    数据结构链表倒排方法代码

    1. 创建新链表实现倒排(方法一): 这种方法通过创建一个新的链表,将原链表的节点逐个插入新链表的头部。首先,创建一个新链表`Chain *c`,然后遍历原链表`Chain *this`,每次取出原链表的表头节点`p`,将其插入新...

    数据结构 链表的相关算法的用C++语言实现

    本文将详细介绍一个基于C++语言实现的单向链表数据结构及其相关的算法。该程序主要实现了链表的基本操作,包括创建、删除、插入节点以及遍历打印整个链表的功能。这些功能对于学习数据结构与算法的基础概念非常有...

    SSTF磁盘扫描算法的链表数据结构实现

    SSTF磁盘扫描算法的链表数据结构实现

    链表实现合并多项式

    本话题将探讨如何使用C语言中的链表数据结构来实现两个多项式的合并与打印。链表是一种非连续、非顺序的存储结构,它通过节点间的指针链接来表示数据。在多项式合并的问题中,我们可以利用链表的特性来高效地处理。 ...

    数据结构-链表逆置算法实现

    链表逆置是指将链表中的元素顺序反转,即原本的第一个元素变为最后一个,最后一个元素变为第一个,以此类推。这个过程对于理解和掌握链表操作非常有帮助,尤其是对于初学者,它是数据结构实习中的一个典型问题。 ...

    C语言链表实现的选猴王算法

    《C语言链表实现的选猴王算法》 在编程领域,解决特定问题的方法往往多种多样,其中一种有趣的问题就是“选猴王”算法。这个算法源于一个古老的故事:一群猴子围成一圈,从某个猴子开始按顺序报数,每当报到特定...

    链表栈实现迷宫算法VC平台

    通过以上步骤,我们可以用链表栈在VC++环境中实现迷宫算法,解决实际问题。这个过程既锻炼了对数据结构的理解,也加深了对链表栈操作和递归回溯策略的应用。在实际编程中,结合图形界面展示迷宫和路径,将使问题的...

    大数(链表、数组)实现

    ### 链表实现大数 1. **链表基础知识**:链表是一种线性数据结构,它的元素在内存中不是顺序存放的,而是通过指针链接。链表可以分为单链表、双链表等,这里我们主要关注单链表,因为其更适合表示大数。 2. **节点...

Global site tag (gtag.js) - Google Analytics