张扬

心随我动
<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

统计

  • 随笔 - 6
  • 文章 - 0
  • 评论 - 0
  • 引用 - 0

常用链接

留言簿

随笔分类

随笔档案

收藏夹

1111

搜索

  •  

最新评论

阅读排行榜

评论排行榜

2009年8月9日

qsort()排序函数的使用qsort函数应用大全

在c++中qsort()排序函数的使用qsort函数应用大全

qsort包含在<stdlib.h>头文件中,此函数根据你给的比较条件进行快速排序,通过指针移动实现排序。排序之后的结果仍然放在原数组中。使用qsort函数必须自己写一个比较函数。

函数原型:

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

用法以及参数说明:

Sorts the num elements of the array pointed by base, each element size bytes long, using the comparator function to determine the order.

The sorting algorithm used by this function compares pairs of values by calling the specified comparator function with two pointers to elements of the array.

The function does not return any value, but modifies the content of the array pointed by base reordering its elements to the newly sorted order.

base Pointer to the first element of the array to be sorted.(数组起始地址)
num Number of elements in the array pointed by base.(数组元素个数)
size Size in bytes of each element in the array.(每一个元素的大小)
comparator Function that compares two elements.(函数指针,指向比较函数)
1、The function must accept two parameters that are pointers to elements, type-casted as void*. These parameters should be cast back to some data type and be compared.
2、The return value of this function should represent whether elem1 is considered less than, equal to, or greater than elem2 by returning, respectively, a negative value, zero or a positive value.
Return Value none (无返回值)

七种qsort排序方法

<本文中排序都是采用的从小到大排序>

一、对int类型数组排序

int num[100];

Sample:

int cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

qsort(num,100,sizeof(num[0]),cmp);

二、对char类型数组排序(同int类型)

char word[100];

Sample:

int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}

qsort(word,100,sizeof(word[0]),cmp);

三、对double类型数组排序(特别要注意)

double in[100];

int cmp( const void *a , const void *b )
{
return *(double *)a > *(double *)b ? 1 : -1;
}

qsort(in,100,sizeof(in[0]),cmp);

四、对结构体一级排序

struct In
{
double data;
int other;
}s[100]

//按照data的值从小到大将结构体排序,关于结构体内的排序关键数据data的类型可以很多种,参考上面的例子写

int cmp( const void *a ,const void *B)
{
return (*(In *)a)->data > (*(In *)B)->data ? 1 : -1;
}

qsort(s,100,sizeof(s[0]),cmp);

五、对结构体二级排序

struct In
{
int x;
int y;
}s[100];

//按照x从小到大排序,当x相等时按照y从大到小排序

int cmp( const void *a , const void *b )
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}

qsort(s,100,sizeof(s[0]),cmp);

六、对字符串进行排序

struct In
{
int data;
char str[100];
}s[100];

//按照结构体中字符串str的字典顺序排序

int cmp ( const void *a , const void *b )
{
return strcmp( (*(In *)a)->str , (*(In *)B)->str );
}

qsort(s,100,sizeof(s[0]),cmp);

七、计算几何中求凸包的cmp

int cmp(const void *a,const void *B) //重点cmp函数,把除了1点外的所有点,旋转角度排序
{
struct point *c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) < 0) return 1;
else if( !calc(*c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) < dis(d->x,d->y,p[1].x,p[1].y)) //如果在一条直线上,则把远的放在前面
return 1;
else return -1;
}
:

c++中加载头文件 \"iostream\"

c中qsort函数包含在<stdlib.h>的头文件里,strcmp包含在<string.h>的头文件里

posted @ 2009-08-09 19:45 张扬 阅读(261) | 评论 (0)编辑 收藏

2009年7月25日

十万个数中如何找出两个不同的呢

有10亿个整数,要求选取重复次数最多的100个整数
要解答这个问题,首先要弄清楚下面几个条件。
(1)有内存限制吗?
(2)整数的范围是多少?有符号,无符号,32位还是64位?
(3)整数集的内容大吗?(即出现的整数空间的大小大吗?)
(4)如果只需要求模糊解,怎么解?
(5)求数组中的第k大元素?
(6)相关问题:求一个整数列中出现次数最多的整数
(7)相关问题:有一个整数数组,请求出两两之差绝对值最小的值,记住,只要得出最小值即可,不需要求出是哪两个数。

(1)如果没有内存限制,且假设是32位无符号的整数。最方便的办法就是建立一个整形数组,int hash[2^32](赞不考虑程序的虚地址空间上限),然后对这10亿个数进行一次遍历,这样,可以得到这2^32个数各自出现的次数,再对这个hash数组进行取第k大元素,100次后,就可以取出这出现次数最多的前100个数。遍历10亿个数的时间复杂度是O(n),n=10^10,求第k大元素的时间复杂度是O(m),m=2^32(=4294967296),那么本算法的时间复杂度是O(n),空间复杂度是O(s),s=2^32。内存要2^32*4=16G
(2)如果有内存限制,或者必须满足程序虚地址空间上限。那么可以对整数空间进行分段处理,比如只提供512M内存,则将2^32个整数划分成32个空间0~2^(27)-1,2^(27)~2^(28)-1,...,31*2^(27)~2^(32)-1。对原来的10亿个数遍历32次,每次遍历,得到每个空间的整数的出现次数,并求出此空间中,出现次数最多的前100个整数,保存下来。这样32次之后,就得到了出现次数前3200的整数,再对这3200个整数取第k大元素,得到出现次数最多的前100个整数。这个算法的时间复杂度也是O(n),空间复杂度降低多少不知道,但是内存使用降低不少。
(3)如果整数空间比较小,也就是说这10亿个数中有很多重复的数,最方便的办法估计就是维护一个HashTable对象ht,key就是整数值,value就是该整数值出现的次数。遍历这10亿个元素,得到ht后再对这个ht求第k大元素。那么这个算法的时间复杂度就是O(n),n=10^10,空间复杂度是O(m),m为整数空间大小。
(4)随机采样(或者将原来的顺序打乱,然后再顺序采样)。对样本中的整数进行出现次数的统计,这个时候采用HashTable的办法最好,时间复杂度是O(n)。如果对使用的空间有所限制,那么只能对该样本进行排序,再对排序后的样本进行100次遍历得到出现次数最多的前100个整数,则时间复杂度是O(nlogn),空间复杂度是O(1)。
(5)好像有两种算法。假设要求数组a[1...n]中第k大元素。
    (a)递归快排算法。若n <44(经验值)则直接排序返回第k大元素,否则,将1到n分成n/5个组,每个组5个元素,然后求这n/5个组的每组的中项元素,再求这n/5个中项元素的中项元素mm(注意,这里也可以用递归调用自身的方法)。然后对数组a根据mm分成三组,a1中的所有元素小于mm,a2中的所有元素等于mm,a3中的所有元素大于mm,如果|a1|>=k,则第k大元素在a1中,如果|a1|+|a2|>=k|a1|,则第k大元素就是mm,如果k>|a1|+|a2|,则第k大元素在a3中,再继续递归调用。这个算法的时间复杂度是O(n)。(注意,这里的中项mm也可以随机选择a中的元素,其时间复杂度也近似于O(n),而且系数也比较小)。
    (b)基于位查找(仅对于无符号整数的查找)。将32位整数的二进制位分为4段,每段8位,先比较a中所有元素高8位,找出第k大元素高8位的范围,再对应这高8位的范围在次高八位中找第k大元素的范围,...这样4次之后就可以找到第k大元素的。可以举个例子便于理解,在10个3位整数中找第k大元素,将3位分成3段,每段1位,每位之可能是0,1。如果这10个数的最高位0的个数m大于等于k,则第k大元素的最高位为0,再在最高位为0的元素中找次高位为第k大元素;如果10个数中最高位0的个数m大于k,则在最高位为1的元素中找此高位为第m-k大元素。...
(6)这个问题是前面那个问题的特例。有没有特殊的解法使效率又提高一些呢?我觉得没有,因为1和100本来就是常数级,和n比它们的差别是忽略不计的。
(7)简单的解法是对这个数组排序,然后再对排好序的数组进行一次遍历就可得到两两绝对值最差的最小值,时间复杂度是O(nlogn)。网上说求a的min,max和长度n,如果Dmax = (max-min+1)/n = 0,那么就说明数组a中有重复的元素,直接返回0。但是如果Dmax = (max-min+1)/n > 0,那么就以Dmax为箱的长度装入a的元素,再在箱内和箱间比较。我不懂为什么,但是这个空间复杂度是O(max),而且好像如果a是1, 2, 3...100,那么Dmax就是1了,那么a不是没有动吗?还有人说够找数组b,b[i] = a[i] - a[i+1],则a[i]-a[j]=b[i]+b[i+1]+...+b[j-1]也不知下文了,看来这个题比较搞啊。就是奥赛题,BS。

posted @ 2009-07-25 20:52 张扬 阅读(444) | 评论 (0)编辑 收藏

2009年7月23日

【命令提示符】-----Windows XP中实用命令及操作技巧(图)

想在命令提示符窗口中输入重复命令时,只须按F7键,就会出现图形界面,然后选择你想输入的命令即可。
  
  一“符”安天下利用命令提示符解决系统问题
  
  一天比比在外看电影,电影中有一个老道士,只要简单地画一个符就可以让村民躲避妖魔鬼怪,比比为老道士所画的那道神奇的符而惊叹不已。这让我想到了在Windows下也有一道符——命令提示符。虽然时至今日,命令提示符中的DOS命令早已被许多人遗忘,然而在实际的电脑操作过程中,命令提示符仍然焕发着无限生机。越来越多的人已经知道在命令提示符下解决一些在Windows中所无法完成的操作,本文将帮助初学这道“符”的朋友快速掌握它的使用方法。这样你也将会成为电影中那个法力无边的道士。
  
  一、初识命令提示符
  
  从Windows 2000开始,MS-DOS已经被更名为“命令提示符”,成为了Windows的一个应用程序,它的运行环境也受到了系统的限制。
  
  当打开“运行”,输入“cmd”回车,即可打开命令提示符窗口。我们就可以像在纯DOS中一样来执行相关的命令,按Alt+Enter键即可在全屏/窗口之间进行切换。命令提示符的命令有许多,一般情况下分为内部命令和外部命令,内部命令是随command.com装入内存的,不需要再去读取文件而可以直接使用,而外部命令则是需要事先由磁盘设备装入到内存,并以COM和EXE为扩展名的程序。本文将以在Windows XP中使用命令提示符来介绍一些比较实用的命令应用及操作。
  
  二、基础篇:活用命令提示符命令
  
  1.目录转换不累人
  
  CD命令是改变目录的命令,也是我们最常使用的命令之一。例如,我们想进入当前XYZ目录下名为ABC的子目录,那么只要执行“CD ABC”即可,如果再想返回XYZ父目录,那么只要执行“CD..”命令,如果想在“C:\>”状态下一下子转到ABC目录,那么只要执行“CD XYZ \ABC”命令即可。如果要从很“深”的目录路径中一下子返回根目录,那么我们没有必要一步一步地执行“CD..”命令,这时只要执行“CD\”命令即可。
  
  提示:如果想改变当前磁盘驱动器盘符,例如想从“C:\WINDOWS\SYSTEM32”命令提示符状态下转到D盘根目录,那么需要执行“D:”命令,同样如果想转到G盘,那么只要执行“G:”命令,然后才能使用CD命令来改变当前目录路径。
  
  2.灵活显示目录和文件
  
  Dir命令可以说是使用得最多的命令之一,它的功能在默认情况下是用来显示一个目录下的所有文件及子目录,另外还显示该目录所在驱动器的卷标及卷的序号。使用方法是直接在命令提示符下输入 “dir”并按回车执行即可(命令提示符中的所有字符无大小写之分)。
  
  (1)分页显示
  
  如果所要显示的目录中包含的文件和子文件夹非常多,你往往会看不清一些文件,这时只要带一个参数“/p”就可以在查看完一个窗口中的内容后再按任意键即可跳到下一个窗口中去,直到全部显示完毕为止。
  
  提示:如果再加参数“/w”,那么显示的内容将以分列的形式直接显示文件名,文件或文件夹创建的日期时间及占用空间大小等信息将不会被显示。其中带有“[]”号的表示为子目录,其余的为文件。
  
  (2)偷窥你的隐藏文件
  
  在默认情况下如果只使用dir命令而不带任何参数,那么将不会显示所有隐藏项目,如果使用dir /a命令,则将显示所有隐藏项目。如果只想显示隐藏项目,那么可以使用dir /a:H命令(图1,H表示隐藏的属性)。另外,文件或文件夹的属性值还可以用“D”来表示目录,“R”表示只读,“A”表示准备存档的文件,“S”表示系统文件,如果在以上值前加“-”则表示否。如果只想显示非只读文件或文件夹,那么就使用dir /a:-R命令。



(3)分类显示
  
  在查找过程中,我们可以使用参数“/O”让文件按某一顺序来进行分类显示,例如按扩展名字母顺序显示,这时就可以在“/O”的后面加参数“E”,命令形式为“dir /O:E”。另外“/O”的后面为“N”表示按名称显示,为“S”表示按文件大小显示,为“D”表示按日期时间先后顺序显示,为“G”表示组目录优先显示,如果每个值前加“-”则排序顺序正好相反。
  
  提示:Dir支持通配符查找,例如要想查找扩展名为doc的所有文件,那么只要执行“DIR *.DOC”命令即可。“*.*”表示所有文件;“a?b.*”表示文件名由三个字符组成,其中第一个字符为“a”,最后一个字符为“b”,中间为任意一个字符,扩展名为任意文件。
  
  3.更改命令提示符的状态
  
  在默认情况下,命令提示符的状态为“当前系统盘\Documents and Settings\当前用户名”下,如果你希望一打开命令提示符即可进入“Windows\system32”状态下,那么你可以按照如下的方法进行设置:
  
  依次点击“开始→控制面板→性能和维护→管理工具→计算机管理”,然后在打开的“计算机管理”左侧窗口中依次展开“系统工具→本地用户和组→用户”,然后在右侧窗口中双击当前登录的用户名,在打开的“属性”对话框中单击“配置文件”标签卡,然后在“主文件夹”下的“本地路径”文本框中键入你想更改的当前盘符或当前目录,如“C:\Windows\system32”(图2),最后单击 “应用→确定”并重新启动计算机即可。


三、应用篇:命令提示符解决系统问题
  
  1.修复受损的系统文件
  
  我们在平时操作电脑的过程中可能会因为某个误操作而丢失了一些重要的系统文件,系统因此变得非常不稳定,老是出现错误提示,如果是为此而重新安装系统的话,那必将浪费你好长的时间,其实使用SFC文件检测器命令就可以轻松地帮你检测并修复受损的系统文件。
  
  具体方法:插入系统安装光盘,然后在命令提示符窗口中输入“sfc /scannow”命令并回车,这时sfc文件检测器将立即扫描所有受保护的系统文件。在大约几分钟的时间里,SFC会检测并修复好受保护的系统文件。
  
  小提示:如果身边没有Windows XP安装盘,但以前在硬盘上备份了安装盘文件的话,可以通过下面的小小设置即可让文件检测器从硬盘上的安装文件中来恢复系统文件。
  
  在注册表中展开“HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Setup”子键,然后在右侧窗口中修改Installation Sources、ServicePackSourcePath和SourcePath三个键值为硬盘上的系统安装程序路径,例如Windows XP的安装原文件存放在E盘\CDXP文件夹中,那么修改以上三个键的键值为“E:\CDXP”。这样再使用SFC命令时,则可以直接使用硬盘上的安装文件来恢复系统而不需要插入安装光盘。
  
  2.三把利剑斩杀木马病毒
  
  如今,一些木马病毒采用了许多新技术,令我们防不胜防,然而使用一般的杀毒软件只能查出却不能杀死这些最新的木马病毒,原因是这些木马病毒进程隐藏得很好,按照一般的方法不能结束木马病毒进程而且木马病毒程序具有很强的自我复制保护功能。这时我们可以在命令提示符下使用tasklist、taskkill及Del命令来斩杀木马病毒。
  
  首先在命令提示符下执行“tasklist /v”命令,这时系统将显示当前所有运行进程的详细信息(不带任何参数则只显示简要的信息),显示内容包括图像名、用户名、PID、会话及内存使用等(图3),如果查到木马病毒进程为a.exe,其所对应的PID值为X,那么这时可以执行“taskkill /f /t a.exe”或“taskkill /f X”来结束进程,其中参数“/f”表示强制结束进程,这对于那些顽固的进程比较有效,最后在Windows故障恢复控制台下执行“Del a.exe”即可彻底删除木马病毒


小提示:执行“tasklist /svc”则可以显示每个进程所对应的服务,这将有利于我们查看可疑服务。另外还可以查看和斩杀远程计算机上的黑客进程,例如远程计算机的IP为192.168.0.55,用户登录名和密码分别为“zla169”及“123456”,那么执行“tasklist /s 192.168.0.55 /u zla169 /p 123456”即可查看远程计算机上运行的进程,执行“taskkill /s 192.168.0.55 /u zla169 /p 123456 /f /t a.exe”即可强行结束远程计算机上进程名为a.exe的进程。
  
  3.给杀不死的进程贴上“生死符”
  
  有的时候遇到一个“搞怪”的进程,就连常用的进程管理器都无法杀死它。这时,我们就可以动用命令提示符来为它贴上一道生死符将它制服。
  
  第一步:打开进程管理器窗口,然后找到那个连进程管理器都不能杀死的进程,如果当前进程管理器的“进程”一栏中无法查到该进程的“PID(进程标志符)”,请在任务管理器中的“进程”选项卡中点击菜单“查看→选择列”,选择“PID(进程标志符)”项即可。最后查出该进程的进程标志。
  
  第二步:输入ntsd -c q -p PID回车即可终止该进程。
  
  只有System、SMSS.EXE和CSRSS.EXE进程不能被该命令杀死。前两个是纯内核态的,最后那个是Win32子系统,ntsd本身需要它。
  
  小提示:如果对某个命令提示符的参数不太清楚,可以通过输入该命令并且在后面添加“/?”回车即可。例如我们想查看“cmd”命令的参数,只要敲入“cmd /?”即可。
  
  比比有话说:Windows命令提示符下的命令还有很多,我们可以通过在命令提示符下执行“help”命令即可查看所有的内部命令。针对每一个命令,例如对于COPY命令,我们可以通过“COPY /?”的方法来查看它大概的使用方法。在命令提示符下能解决许多在Windows下显得有点难解决的问题,只要你掌握了方法,相信对你一定会很有用。


posted @ 2009-07-23 09:44 张扬 阅读(319) | 评论 (0)编辑 收藏

2009年7月7日

一、进程和程序的关系

1.进程是动态的,程序时静态的,进程是程序的一次执行过程,程序时一组代码的集合。
2. 进程暂时的,程序时永久的。进程是一个状态变化的过程,程序可以长久保存。
3. 进程和程序的组成不同。进程的组成包括程序、数据和进程控制块。

posted @ 2009-07-07 18:11 张扬 阅读(126) | 评论 (0)编辑 收藏

2009年6月29日

最常用的字符实体

显示结果 描述 实体名称 实体编号
  空格 &nbsp;   
< 小于号 &lt; <
> 大于号 &gt; >
& 和号 &amp; &
" 引号 &quot; "
' 撇号  &apos; (IE不支持) ''

posted @ 2009-06-29 11:36 张扬 阅读(127) | 评论 (0)编辑 收藏

2009年6月26日

main主函数执行完毕后,是否可能会再执行一段代码?(朗讯的一道笔试题)

 

可以,可以用_onexit 注册一个函数,它会在main 之后执行;

如果你需要加入一段在main退出后执行的代码,可以使用atexit()函数,注册一个函数。  
 
语法:  
  #include   <stdlib.h>  
  int   atexit(void   (*function")(void));  
  #include   <stdlib.h>  
  #include   <stdio.h>    
  void   fn1(   void   ),   fn2(   void   ),   fn3(   void   ),   fn4(   void   );    
  int   main(   void   )  
  {  
        atexit(   fn1   );  
        atexit(   fn2   );  
        atexit(   fn3   );  
        atexit(   fn4   );  
        printf(   "This   is   executed   first.\n"   );  
  }   
  void   fn1()  
  {  
        printf(   "next.\n"   );  
  }   
  void   fn2()  
  {  
        printf(   "executed   "   );  
  }    
  void   fn3()  
  {  
        printf(   "is   "   );  
  }    
  void   fn4()  
  {  
        printf(   "This   "   );  
  }  

结果:

This   is   executed   first.  
 This   is   executed   next.  

posted @ 2009-06-26 08:42 张扬 阅读(395) | 评论 (0)编辑 收藏
仅列出标题