ITeye博客

从零开始

pengcc · 共 27 篇文章

[置顶] C语言常见算法实现

C语言常见算法主要收集一些经常用到的算法,有些笔试面试中经常考到,自己在学习的过程中与大家分享,希望对学习算法和C语言的朋友有帮助。 1,汉诺塔算法的C语言实现 2,八皇后问题的C语言实现 3,费时数列的C语言实现 4,八枚硬币问题的C语言实现 5,三色旗解法的C语言实现 6,巴斯卡三角形算法的C语言实现 7,背包问题的C语言实现 8,Eratosthenes筛选求质数的C语言实现

2010-07-04 11:03 · 评论(0)

Linux设备模型

看LDD3中设备模型一章,觉得思维有些混乱。这里从整体的角度来理理思路。 本文从四个方面来总结一些内容: 1.底层数据结构:kobject,kset. 2.linux设备模型层次关系:bus_type,device,device_driver. 3.集成:PCI设备驱动模型实例及设备,设备驱动注册源码的简单分析. 4.面向对象的思想在linux设备模型中的应用分析. 一、底层数据结构:kobject,kset 先说说模型的意义: 总体来说是为了系统地管理所有设备。 kobject 结合面向对象的思维。这个kobject属于最基础的结构,也就是最高抽象层(有点像java中的Cobject类)。…

2011-03-01 00:22 · Linux · 评论(0)

C语言高效编程的的四大绝招

编写高效简洁的C语言代码,是许多软件工程师追求的目标。本文就工作中的一些体会和经验做相关的阐述,不对的地方请各位指教。 第一招:以空间换时间 计算机程序中最大的矛盾是空间和时间的矛盾,那么,从这个角度出发逆向思维来考虑程序的效率问题,我们就有了解决问题的第1招--以空间换时间。 例如:字符串的赋值。 方法A:通常的办法: #define LEN 32 char string1 [LEN]; memset (string1,0,LEN); strcpy (string1,"This is a example!!"); 方法B: const char string2[LEN] ="This is…

2011-02-26 00:11 · C语言 · 评论(0)

BSS段、数据段、代码段、堆与栈

***BSS段:***BSS段(bss segment)通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文Block Started by Symbol的简称。BSS段属于静态内存分配。 ***数据段:***数据段(data segment)通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。 ***代码段:***代码段(code segment/text segment)通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定,并且内存区域通常属于只读, 某些架构也允许代码段为可写,即允许修改程序。在代码段中,也有可能…

2011-02-24 23:29 · C语言 · 评论(0)

Linux slab 分配器

动态内存管理 内存管理的目标是提供一种方法,为实现各种目的而在各个用户之间实现内存共享。内存管理方法应该实现以下两个功能: 最小化管理内存所需的时间 最大化用于一般应用的可用内存(最小化管理开销) 内存管理实际上是一种关于权衡的零和游戏。您可以开发一种使用少量内存进行管理的算法,但是要花费更多时间来管理可用内存。也可以开发一个算法来有效地管理内存,但却要使用更多的内存。最终,特定应用程序的需求将促使对这种权衡作出选择。 每个内存管理器都使用了一种基于堆的分配策略。在这种方法中,大块内存(称为 堆 )用来为用户定义的目的提供内存。当用户需要一块内存时,就请求给自己分配一定大小的内存。堆管理器会…

2011-02-24 23:22 · Linux · 评论(0)

C语言计算程序运行时间问题

#include "stdio.h" #include "stdlib.h" #include "time.h" int main(void) { long i = 10000000L; clock_t start, finish; double duration; /*测量一个事件持续的时间*/ printf("Time to do %ld empty loops is ", i ); start = clock(); while(i--) ; finish = clock(); duration = (double)(finish - start) / CLOCKS_PER_SEC; p…

2011-02-22 23:43 · C语言 · 评论(1)

使用 /proc 文件系统来访问 Linux 内核的内容

/proc 文件系统是一个虚拟文件系统,通过它可以使用一种新的方法在 Linux 内核空间和用户空间之间进行通信。在/proc 文件系统中,我们可以将对虚拟文件的读写作为与内核中实体进行通信的一种手段,但是与普通文件不同的是,这些虚拟文件的内容都是动态创建的。 创建并删除 /proc 项 要在 /proc 文件系统中创建一个虚拟文件,请使用 create_proc_entry 函数。这个函数可以接收一个文件名、一组权限和这个文件在 /proc 文件系统中出现的位置。 create_proc_entry 的返回值是一个 proc_dir_entry 指针(或者为 NULL ,说明在 creat…

2011-02-22 00:02 · 评论(0)

最简单的内核模块例子

#include <linux/kernel.h> #include <linux/module.h> #include <linux/init.h> static int __init hello_init(void) { printk(KERN_INFO "Hello world\n"); return 0; } static void __exit hello_exit(void) { printk(KERN_INFO "Goodbye world\n"); } module_init(hello_init); module_exit(hello_exit); •static int …

2011-02-20 18:47 · Linux · 评论(0)

Linux内核模块与应用程序的区别

用户态程序 Linux内核模块 运行 用户空间 内核空间 入口 main() module_init()指定; 出口 无 module_exit()指定; 编译 gcc –c Makefile 连接 ld insmod 运行 直接运行 insmod 调试 gdb kdbug, kdb, kgdb等 Linux内核模块的优点与缺点 优点 使得内核更加紧凑和灵活 修改内核时,不必全部重新编译整个内核。系统如果需要使用新模块,只要编译相应的模块,然后使用insmod将模块装载即可 模块的目标代码一旦被链接到内核,它的作用域和静态链接的内核目标代码完全等价。 缺点 由于内核所占用的内存是不会被换出的…

2011-02-19 00:32 · Linux · 评论(0)

Linux中inittab 文件解析

init的进程号是1,从这一点就能看出,init进程是系统所有进程的起点,Linux在完成核内引导以后,就开始运行init程序,。 init程序需 要读取配置文件/etc/inittab。inittab是一个不可执行的文本文件,它有若干行指令所组成。在Redhat系统中,inittab的内容 如下所示(以“###"开始的中注释为笔者增加的): # inittab This file describes how the INIT process should set up # Default runlevel. The runlevels used by RHS are: # 0 - halt…

2011-02-17 23:11 · Linux · 评论(0)

系统引导管理器GRUB

本文重点介绍了GRUB的menu.lst的写法,另外通过GRUB命令行引导系统也做了详述;这些无论是对Windows版本的WINGRUB还是Linux版本的GRUB都是适用的; 目录索引 一、什么是多重操作系统引导管理器,什么是GRUB; 1、什么是多重操作系统引导管理器及工作原理; 2、什么是GRUB;为什么我要选择GRUB; 1)什么是GRUB; 2)“GRUB太不好用”──对GRUB的认识的误区; 3)为什么要选择GRUB; 二、GRUB软件包版本选择和安装; 1、Linux版本的GRUB及Windows版本的GRUB的说明; 2、GRUB的Windows版本WINGRUB; 3、GR…

2011-02-17 00:10 · Linux · 评论(0)

C语言排序算法汇总

几种排序算法的比较和选择 1. 选取排序方法需要考虑的因素: (1) 待排序的元素数目n; (2) 元素本身信息量的大小; (3) 关键字的结构及其分布情况; (4) 语言工具的条件,辅助空间的大小等。 小结: (1) 若n较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时,用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。 (3) 若n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。快速排序是目前基于比较的内部排序法中被…

2011-01-13 00:09 · 评论(0)

C语言排序算法之“希尔排序法”

算法思想简单描述: 在直接插入排序算法中,每次插入一个数,使有序序列只增加1个节点,并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离(称为增量)的数,使得数移动时能跨过多个元素,则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组,每组中 记录的下标相差d.对每组中全部元素进行排序,然后再用一个较小的增量对它进行,在每组中再进行排序。当增量减到1时,整个要排序的数被分成一组,排序完成。 void shell_sort(int *x, int n) { int h, j, k, t; …

2011-01-13 00:07 · 评论(0)

C语言排序算法之“插入排序法”

插入法是一种比较直观的排序方法。它首先把数组头两个元素排好序,再依次把后面的元素插入适当的位置。把数组元素插完也就完成了排序。 void insert(int *a,int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a; /*temp为要插入的元素*/ j=i-1; while(j>=0&&temp<a[j]) { /*从a开始找比a小的数,同时把数组元素向后移*/ a[j+1]=a[j]; j--; } a[j+1]=temp; /*插入*/ } }

2011-01-13 00:04 · 评论(0)

C语言排序算法之“快速排序法”

快速法定义了三个参数,(数组首地址*a,要排序数组起始元素下标i,要排序数组结束元素下标j). 它首先选一个数组元素(一般为a[(i+j)/2],即中间元素)作为参照,把比它小的元素放到它的左边,比它大的放在右边。然后运用递归,在将它左,右两个子数组排序,最后完成整个数组的排序。下面分析其代码: void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*选取的参照*/ do { while(a--<k && m<j) m++; /* 从左到右找比k大的元素*/ while(a[n]>k &&…

2011-01-13 00:04 · 评论(0)