ITeye博客

游骑兵打先锋

cm14k · 共 26 篇文章

java正则表达式

正则表达式是一种强大而灵活的文本处理工具。使用正则表达式,我们能够以编程的方式构造复杂的文本模式,并对输入的字符串进行搜索。 简单的来说,正则表达式就是以某种方式来描述字符串。 java从jdk1.4开始支持正则表达式。 一、简介 java.util.regex 是一个用正则表达式所订制的模式来对字符串进行匹配工作的类库包。 它包括两个类: Pattern 和 Matcher Pattern 正则表达式的编译表示形式 Matcher 通过解释 Pattern 对 character sequence 执行匹配操作的引擎。 指定为字符串的正则表达式必须首先被编译为Pattern的实例。然后,可…

2011-04-04 12:38 · Java · 评论(0)

Linux内核链表(二)

4)遍历 遍历是链表最经常的操作之一,为了方便核心应用遍历链表,Linux链表将遍历操作抽象成几个宏。 在介绍遍历宏之前,我们先看看如何从链表中访问到我们真正需要的数据项: a)由链表结点到数据项变量 由上面的分析可知,内核链表中仅保存了数据项结构中list_head成员变量的地址,那么我们如何通过这个list_head成员访问到作为它的所有者的节点数据呢?在list.h文件中有一个list_entry(ptr,type,member)宏,其中ptr是指向该数据中list_head成员的指针,也就是存储在链表中的地址值,type是数据项的类型,member则是数据项类型定义中list_hea…

2011-04-01 22:06 · 内核之旅 · 评论(0)

Linux内核链表

一、链表数据结构简介 链表是一种常用的组织数据的数据结构,它通过指针将一系列数据节点连接成一条数据链,是线性表的一种重要实现方式。相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。 通常链表包括两个域:数据域和指针域,数据域用于存储数据,指针域用于建立与下一个节点的联系。链表一般可以分为单链表、双链表、循环链表等多种类型。 1、单链表 单链表是最简单的链表结构,它的结点包括两个域:数据域用来存储结点的数据信息;指针域用来存储数据元素的直接后继地址,即用来建立与下一…

2011-04-01 17:28 · 内核之旅 · 评论(0)

编写第一个内核模块

内核模块是Linux内核向外部提供的一个接口,其全称是 动态可加载内核模块(Loadabkle Kernel Module,LKM)。 Linux 内核之所以提供模块机制,是因为它本身是一个单内核( monolithic kernel )。单内核的最大优点是效率高,因为所有的内 容都集成在一起,但其缺点是可扩展性和可维护性相对较差,模块机制就是为了弥补这一缺陷。 一、什么是模块 模块是具有独立功能的程序,它可以被单独编译,但不能独立运行。它在运行时被链接到内核作为内核的一部分在内核空间运行,这与运行在用户空间的进程是不同的。模块通常由一组函数和数据结构组成,用来实现一种文件系统、一个驱动程序…

2011-03-30 20:07 · 内核之旅 · 评论(0)

求组合数

求组合数 从n个数里面取m个数 (递归实现) /** * Description: * 求组合数(递归法) * 从n个数里面取m个数 算法分析: * 用递归的方法,每选出一个数字之后就把这个数字去掉,用剩余的数字继续递归 * @author cm * */ public class Combination { private int m; private int[] res; //存放结果数组 private int[] arr; //被选择的数组 private int count = 0; private int total = 0; //总数 /** * @param m 选择的个数 …

2011-03-26 20:23 · 算法分析 · 评论(0)

结构体的初始化

定义一个结构体: #define LENGTH 256 struct book { char title[LENGTH]; char author[LENGTH]; float value; }; 初始化方法: (1)使用一个花括号括起来、逗号分隔的初始化项目列表进行初始化。每个初始化项目必须和要初始化的结构体成员类型相匹配。(类似于数组的初始化) 例如: struct book java = { "Thinking in Java", "Bruce Eckel", 108.00 }; (2)结构体的指定初始化项目 C99支持结构体的指定初始化项目,其语法与数组的指定初始化项目相似。只是,结…

2011-03-19 23:29 · C/C++ · 评论(0)

访问XHTML元素

为了动态修改XHTML元素,必须能访问XHTML元素,DOM提供了2种方式来访问XHTML元素: -- 根据id访问 -- 利用节点关系访问 (1)根据ID访问XHTML元素 document.getElementByID(idVal) : 返回文档中id属性值为idVal的XHTML元素 例如: <script type="text/javascript"> function accessById() { alert(document.getElementById("a").innerHTML + "\n" + document.getElementById("b").value); } …

2011-03-13 09:59 · Web开发 · 评论(0)

背包问题

与0-1 背包问题类似,所不同的是在选择物品i 装入背包时,可以选择物品i 的一部分,而不一定要全部装入背包. 算法分析: 首先计算每种物品的单位重量的价值, 然后依贪心策略,将尽可能多的单位重量价值最高的物品装入背包. 实现: /* * description: 背包问题 * 问题描述:与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择 * 物品i的一部分,而不一定要全部装入背包. * 算法分析:贪心算法 * 首先计算每种物品的单位重量的价值,然后依贪心策略,将尽可能多的单位重量价值最高的物品装入背包. * * date: 2010/12/5 * auther:cm */ i…

2010-12-14 18:27 · 算法分析 · 评论(0)

0-1背包问题

0-1背包问题: 给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的总容量为c。 问:应该如何选择装入背包的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包,因此该问题称为0-1背包问题。 该问题的形式化描述是: 0-1背包问题具有最优子结构性质,可用动态规划法解决。 解法一: 动态规划 算法分析: 1)设m(i, j)是背包容量为j,可选物品为0,1,...,i时0-1背包问题的最优值。 2)递归式 m(i, j) = 0 j=0 m(i, j) = 0 i=0 && j < wi m(i, j) = vi i=0…

2010-12-14 18:00 · 算法分析 · 评论(0)

装载问题

装载问题 有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船,集装箱总重量小于等于c1+c2,要求定一个合理的装载方案可将这n个集装箱装上这两艘轮船。 可以证明,如果一个给定装载问题有解,则采用下面的策略可得到最优的装载方案: 1)首先将第一艘轮船尽可能装满 2)将剩余的集装箱装上第二艘轮船 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和接近第一艘轮船载重量c1. 该问题类似于0-1背包问题,可以用动态规划法解决。 用回溯法解装载问题时,用子集树表示其解空间显然是最合适的。 回溯法实现: /* * 装载问题 * 有一批共n个集装箱要装上两艘载重量分别为c…

2010-12-12 18:16 · 算法分析 · 评论(0)

最优装载问题

问题描述: 有一批集装箱要装上一艘载重量为C的轮船,要求在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。 算法分析: 采用重量轻者先装的贪心选择策略,可产生最优装载问题的最优解。 算法实现: OptinalLoading.java /* * 最优装载 * 有一批集装箱要装上一艘载重量为C的轮船。 * 要求在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。 * 算法分析: * 采用重量最轻者先装的贪心选择策略 * * date: 2010/12/12 * auther:cm * */ import java.util.Arrays; public class OptinalLoa…

2010-12-12 11:13 · 算法分析 · 评论(0)

C 标准库qsort函数的使用

快速排序(quick sort)是最有效的排序算法之一。 C实现的快速排序算法的函数名为qsort(), qsort()函数对数据对象数据进行排序。其函数原型在头文件stdlib.h中 其原型为: void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *,const void *)); 第一个参数为指向要排序的数组头部指针,因为任何数据类型的指针可以转化成void类型指针,故qsort()的第一个参数可以指向任何类型的数组; 第二个参数为要排序的元素数量; 第三个参数为数组中数据对象的大小。因为q…

2010-11-30 20:02 · C/C++ · 评论(0)

喝汽水问题

问题描述: 1元钱一瓶汽水,喝完后两个空瓶换一瓶汽水,问:你有20元钱,最多可以喝到几瓶汽水? 这个问题其实是个比较典型的递推问题,每2个空瓶都可以再换1瓶新的汽水,这样一直递推下去,直到最后不能换到汽水为止。 解法一: /* * description: * 1元钱一瓶汽水,喝完后两个空瓶换一瓶汽水,问:你有20元钱,最多可以喝到几瓶汽水? * * auther: cm * date:2010/11/28 */ #include <stdio.h> #define MONEY 20 //钱数 #define PRICE 1 //汽水单价 #define PERCOUNT 2 //兑换规则 …

2010-11-28 21:51 · 算法分析 · 评论(0)

最大子段和(三)

最大子段和问题 解法三: 算法分析: 对于序列a,设j代表当前序列的终点,i代表当前序列的起点 分析:如果a[i]是负的,那么它不可能是最大子段的起点,因为任何包含a[i]为起点的子段都可以通过 用a[i+1]为起点而得到改进。类似的,任何负的子段都不可能是最优子段的前缀(原理相同). 如果在循环中检测到a[i]到a[j]的子段是负的,那么可以推进i. 结论:不仅能把i推进到i+1,而且可以一直推进到j+1. 原因:令p为i+1和j之间的任一下标。开始于下标p的任意子段都不大于从下标i开始并包含从a[i]到a[p-1]的子段, 因为a[i]到a[p-1]这个子段不是负的(j是使得从下标i开始…

2010-11-21 10:04 · 算法分析 · 评论(0)

最大子段和(二)

最大子段和问题 解法二:分治法 算法分析: 最大子段和可能在三处出现。 1)整个出现在输入数据的左半部 2)整个出现在右半部。 3)跨越输入数据的中部从而位于左右两半部分之中 前两种情况可以递归求解,第三种情况的最大和可以通过求出前半部分的最大和(包含前半部分的最后一个元素) 以及后半部分的最大和(包含后半部分的第一个元素)而得到,前后两部分和相加。 三部分中的最大者,即为最大子段和. 例如: 前半部分 后半部分 4 -3 5 -2 -1 2 6 -2 其中前半部分的最大子段和为6(A1到A3),而后半部分的最大子段和为8(A6到A7); 前半部分包含其最后一个元素的最大和为4(A1到A4)…

2010-11-20 19:15 · 算法分析 · 评论(0)