日志标签 ‘C编程’

名次确定问题(Update:8/10)

2010年7月29日

五位运动员参加比赛,进行结果预测:

A说:B第一,我第三
B说:我第二,E第四
C说:我第一,D第三
D说:C最后,我第三
E说:我第四,A第一

比赛结束,每位选手只说对了一半,编程确定比赛名次。

拿到这道题,我首先想到的是,ABCDE五人有5!个排列次序,对于每个次序都验证题目要求,满足即可break各个循环。于是代码如下:

#include 

int main()
{
	int i,sum=0;
	int a,b,c,d,e;
	int flag=0;

	for(a=1;a<\6;a++)
	{
		for(b=1;b<\6;b++)
		{
			for(c=1;c<\6;c++)
			{
				for(d=1;d<\6;d++)
				{
					for(e=1;e<\6;e++)
					{

						sum=0;
						sum=(b==1||a==3)+(b==2||e==4)+(c==1||d==2)+(c==5||d==3)+(e==4||a==1);
						if(sum==5)
						{
							flag=1;
							printf("e=%d ",e);
							break;
						}
					}

					if(flag)
					{
						printf("d=%d ",d);
						break;
					}
				}
				if(flag)
				{
					printf("c=%d ",c);
					break;
				}
			}
			if(flag)
			{
				printf("b=%d ",b);
				break;
			}
		}
		if(flag)
		{
			printf("a=%d ",a);
			break;
		}
	}
	printf("\n");
	return 0;
}

编译运行。结果错误:11134。原因是这样的:满足上述条件的序列很多,但是遇到第一个满足条件的序列(此时a,b,c都是1,可见没跑几下就break了)时,因为多个break的原因就跳出了所有循环。看来还得加一个筛选条件。既然名字是1~5的任意排序,那么五位选手名次之和肯定是固定的,因此加入此条件即可筛选处最终名次。如下:

						sum=0;
						sum=(b==1||a==3)+(b==2||e==4)+(c==1||d==2)+(c==5||d==3)+(e==4||a==1);
						if(sum==5)
						{
							if((a+b+c+d+e)==15)
							{
							flag=1;
							printf("e=%d ",e);
							break;
							}
						}

这样就OK了。看来除了得到题目表面的信息后,还得学会抓住隐含条件。其实第一个条件也可以有下面的几种表达方式:

                                                //方法1
						sum=0;
						sum+=(b==1&&a!=3)||(b!=1&&a==3);
						sum+=(b==2&&e!=4)||(b!=2&&e==4);
						sum+=(c==1&&d!=2)||(c!=1&&d==2);
						sum+=(c==5&&d!=3)||(c!=5&&d==3);
						sum+=(e==4&&a!=1)||(e!=4&&a==1);
						//方法2
						sum=0;
						sum=(a==3||a==1)+(b==1||b==2)+(c==1||c==5)+(d==2||d==3)+(e==4);

这里还有一个更简单的方法。在我作完后,我觉得这个题目用5重循环是否太多余,就想看看牛人是如何完成的,所以就咨询牛涛,它发过来一个链接,果然很简便。虽然意思是一样的但是时间复杂度只有N平方而已。我这个N的5次方 e42

Update:8/10

今天一位同学留言说,判断条件应该再加一条判断a,b,c,d,e互不相等。这个条件在我做这个题的时候就想过,可当时总觉的两个判断条件即可。但是,为什么上面的代码也可以显示处正确的答案?那是因为我加入了break。恰好第一组名词就互不相等。如果把每个break都删除了,就会发现有两组结果,其中一个结果就有重复的名次。

其实这个题目属于一个穷举类的题目,应该在程序中让它列出所有的可能(尽管本题中的答案只有一个),而不是找到一个就立刻停止。

实现cp命令(4)

2010年7月28日

现在我们已经实现了my_cp。那么我们来运行一下下面的命令吧:

gues@huangwei-desktop:~/code/shell_command$ ./my_cp -r dir/ newdir/ -r
my_cp: can't get file status of "-r" : no this file or directory.

问题出来了,我们并没有考虑到多个重复选项的情况,因此上面命令把末尾的-r当成了文件名。如果用cp执行上面的指令,那么是成功的,因为多个重复选项在cp命令下就相当于一个。因此我们下面来修改代码。
你可以让检查选项处的param_r=1;改为param+=1;然后再加入下面的代码,当出现这种情况的时候,让其出错。

if(param_r>1)
{
printf("my_cp:invalid options.\n");
exit(1);
}

为了完美一些,我们可以这样做。首先我们将原来index_r改成数组index,记录出现-r的位置。我们可以让这个数组全部初始化为0,如果参数中,第i个参数为-r或者-R,那么就将index[i]赋值为i。并且这时候的param_r就要累计出现合法(对于本程序,合法选项就是-r或-R了)选项的个数。

	//check the legality of the options,only -r or -R
	for(i=1;i<\argc;i++)
	{
		if(argv[i][0]=='-')
		{
			if((!strcmp(argv[i],"-r")||!strcmp(argv[i],"-R")))
			{
				param_r+=1;
				index[i]=i;
			}
			else
			{
				printf("my_cp:invalid options: %s\n",argv[i]);
				exit(1);
			}
		}
	}

那么在计算源文件数目的时候也相应的就有了小改动。

	if(param_r)
	{
		num=argc-1-param_r;
		src_num=num-1;
	}
	else
	{
		num=argc-1;
		src_num=num-1;
	}
	if(num<\2)
	{
		printf("my_cp: [option]  \n");
		exit(1);
	}

提取目标文件的时候,就有些小麻烦,但是也是可以解决的。我们从命令行参数末尾开始,找到那个不是选项的那个参数,因为目标文件总是靠近末尾的。比如:./my_cp dir/ newdir/ -r -r

	//extract the dest path
	for(i=argc-1;i>\0;i--)
	{
		if(!strcmp(argv[i],"-r")||!strcmp(argv[i],"-R"))
			continue;
		else
			break;
	}
	if(i==argc-1)
	{
		strcpy(dest_path,argv[i]);
	}
	else
	{
		strcpy(dest_path,argv[i]);
	}

好了,改完上面的代码,下面就和以前的一样了。这样就可以避免开始的时候我们所举的例子的错误。

字节对齐

2010年7月23日

今天在看结构体和共用体部分的时候,遇到了一个新名词“内存对齐”。先引入问题吧。如下:

struct student
{
	char name[20];
	int age;
	char sex;
	char phone[15];
};
struct student p1;

sizeof(p1)=?
这个很简单得出答案,即20+4+1+15=40Byte。如果将phone[15]改为phone[16],结果是44。难道不是41吗?

这里便要引入内存对齐的概念。内存为了提高访问效率,便规定以结构体中最大的基本单位长度为对齐标准。即实际分配的内存大小是对齐标准的整数倍(必要条件)。在上面的结构体中,最大的基本类型是int。因此以4Byte为对其标准。所以实际内存大小应该为4的整数倍,即为44Byte.

也许你有疑惑:name[20]不是要20Byte吗,为什么以4Byte为对齐标准?请注意这里的基本类型。name[20]是一个字符串数组,数组属于复合的数据类型。复合的数据类型还有结构体,共用体。基本的数据类型是整型,字符型,浮点型。如果你还有不解,那么看下题:

struct score
{
	float english;
	float math;
	float computer;
};
struct student
{
	char name[10];
	int age;
	char sex;
	struct score st_score;
};

在student结构体中含有数据类型为struct score这样的变量。struct score的大小为12Byte,也是struct student结构体中最大的数据类型,但是我们的对齐标准是4Byte,就如我们刚说的那样,内存的对齐标准是取结构体中最大的基本数据类型,这里我们取sizeof(int)。

再看下面的问题:

union data1
{
	int i;
	char c;
	char str[9];
};
struct data2
{
	int i;
	char c;
	char str[9];
};

sizeof(struct data1)=? sizeof(struct data2)=?
对于前者,由于共用体的存储大小由最大的成员来决定,因此上题中共用体的存储大小为9Byte,考虑到内存对齐,它以sizeof(int)=4Byte来对齐,因此实际内存分配大小是12Byte。对于后者,存储大小是4+1+9=14Byte,这个结构体以4对齐,因此实际分配大小为16Byte。

现在你应该对于共用体和结构体的内存对齐有所了解了。那么再接着往下看:

struct data
{
	char c;
	double d;
	char ch;
}

sizeof(struct data)=?
有了上面的理解,10肯定不会是答案,那么会是16吧。也错。正确答案是24。你可能会感到莫名其妙:按照上面所说的方法,以8为对齐标准,那么10不是8的倍数,那就是16呀。为什么呢?请你耐心看下面。

首先我们知道结构体变量是分配的连续内存空间。d毫无疑问是分配8Byte,对于d“前面”的c,按照对齐标准我们应该分配8Byte,而d后面的ch,按照对齐标准也应该分配8Byte。因此结果是24。

如果这样:

struct data
{
	double d;
	char c;
	char ch;
}

sizeof(struct data)=16。

因为内存没必要分别为c和ch分配8Byte来进行对齐,将它们放在一个8byte里就可以实现内存对齐。上面在引入内存对齐概念的时候,我用括号特别注释必要条件便是说明此处内容。

my_shell.c代码分析

2010年7月16日

大三的时候,那时候因为课程需要,我们调试过my_shell.c程序。当时只是对整个程序的结构了解,在涉及linux系统调用函数的时候就不是很清楚”为什么会这样做?”。my_shell.c程序核心函数便是do_cmd函数,此函数是整个程序的核心,负责对用户输入的命令进行执行。

本文便是分析do_cmd函数,以达到对my_shell.c程序有深入的理解。此函数会涉及文件操作中的相关系统调用函数,如果你和我一样调试并分析过前面所说的my_ls.c程序,那么接下来所述的内容对你来说并不困难。

我们按照如下方式定义do_cmd函数:

void do_cmd(int argcount, char arglist[100][256]);

其中,argcount是统计用户输入命令中选项的个数,arglist数组存储每个选项。比如输入:ls -l /那么此时argcount=3,而arglist[0],arglist[1],arglist[2]中分别存储的是:ls,-l,/。

首先此函数会检查用户输入的命令行参数中是否存在后台运行符。利用for循环,对arglist数组中的每个参数与”&”进行比较。由于arglist中的元素是字符串,那么应该选用strcmp函数,而不是利用==来判断。此外即便找到了后台运行符,还应该检查是否”&”位于参数末尾。如果i==argcount-1为假,那么便出错。实现代码如下:

//check if the command include character of running in the background
	for(i=0;i<\argcount;i++)
	{
		if(strncmp(arg[i],"&",1)==0)
		{
			if(i==argcount-1)
			{
				background=1;
				arg[argcount-1]=NULL;
				break;
			}
			else
			{
				printf("wrong command\n");
				return;
			}
		}
	}//for

接下来,检测命令行参数是否含有>,<,|符号,检测方法与上出代码原理类似。由于本程序要求用户输入的命令行参数只能包含上述符号其中之一,所以当flag大于一时,错误。参数中符号合法,接下来提取文件名,存于字符串file中。程序中分别有三个if语句依次针对出现>,<,|时的情况。我们只要分析出现管道符号的情况。

在分析之前首先弄起出管道符号的作用。比如下面命令:

edsionte@edsionte-laptop:~$ ls -l / | wc -c
1513

管道符号前后分别是两个shell命令,前命令的输出作为后命令的输入。

如果检测出命令行中含有管道符号,即how=have_pipe。然后将命令行中两个shell命令分离出来,前命令依然存于arg数组中,而后命令存于argnext数组中。实现命令如下:

if(how==have_pipe)
	{
		for(i=0;arg[i]!=NULL;i++)
		{
			if(strncmp(arg[i],"|",1)==0)
			{
				arg[i]=NULL;
				int j;
				for(j=i+1;arg[j]!=NULL;j++)
				{
					argnext[j-(i+1)]=arg[j];
				}
				argnext[j-(i+1)]=arg[j];
				break;
			}
		}
	}

接下来就要用到进程控制的内容了。我们fork一个新的进程,让它去执行命令行参数中的命令。当命令行中不包含管道符号时,只需fork一个进程,比如ls -l / > a;我们只需fork一个新进程,让其(if(pid==0))执行ls命令即可;否则,我们必须fork两个信进程,前一个进程执行|前的命令,另外一个进程执行|后的命令。至于另个进程如何”通信”,如何让前一个命令的输出称为后者的输入?不着急,后面会详细说明。

1.如果所输命令中不包含<,>,|,how==normal(0);那么调用exe族函数即可让子进程去执行所输的命令。如下:

			if(pid==0)
			{
				if(!(find_command(arg[0])))
				{
					printf("%s: command not found\n",arg[0]);
					exit(0);
				}
				execvp(arg[0],arg);
				exit(0);
			}

find_command函数是在指定目录下去查找命令arg[0]对应的可执行程序。

2.如果命令行中包括输出重定向符号>,how==out_redirect(1);那么需在上述代码中exe函数前添加下面的代码:

				fd=open(file,O_RDWR|O_CREAT|O_TRUNC,0644);
				dup2(fd,1);//make the file as a standard output stream
				execvp(arg[0],arg);//execute the command

前面我们已经提到file中存储的是输出重定向(或输入重定向)的文件名,因此首先应以可读可写方式打开一个文件,并且档要打开的文件存在时,会清空源文件数据,这些我们在前面的博文中都有解释。我们知道标准输出输入的文件描述符为:1,0,利用dup2函数就可以将fd,1同时指向file文件,实现将标准输出重定向到我们刚已打开的文件。

3.如果命令行中包含输入重定向符号<,how==out_redirect(2);那么添加如下代码:

				fd=open(file,O_RDONLY);
				dup2(fd,0);//make the file as a standard output stream
				execvp(arg[0],arg);//execute the command

这里只涉及到读取文件,因此以只读方式打开文件。

4.如果命令行中包含管道符号,how==have_pipe(3);如同我们在上面所述的,子进程还需再fork一个进程(暂且叫它子子进程,child_child_process)。首先让子子进程去执行管道符号前面的shell命令,并将输出结果暂存于tempfile文件中;让子进程去执行管道符号后面的shell命令,并读取tempfile文件,将其作为第二个命令的输入。这样,子进程和子子进程实现了管道”通信”。具体代码实现其实是上述2和3的结合,具体如下:

			if(pid==0)//child_process
			{
				int pid2;
				int status2;
				int fd2;

				if((pid2=fork())<\0)
				{
					printf("fork2 error\n");
					return;
				}
				else if(pid2==0)//child_child_process
				{
					if(!(find_command(arg[0])))
					{
						printf("%s: command not found\n",arg[0]);
						exit(0);
					}
					fd2=open("/tmp/tempfile",O_WRONLY|O_CREAT|O_TRUNC,0644);
					dup2(fd2,1);
					execvp(arg[0],arg);
					exit(0);
				}

				if(waitpid(pid2,&status2,0)==-1)//waiting for child_child_process
				{
					printf("wait for child_child process error\n");
				}

				if(!(find_command(argnext[0])))
				{
					printf("%s:command not found\n",argnext[0]);
					exit(0);
				}

				fd2=open("/tmp/tempfile",O_RDONLY);
				dup2(fd2,0);
				execvp(argnext[0],argnext);

				if(remove("/tmp/tempfile"))
				{
					printf("remove error\n");
				}
				exit(0);
			}

上出1~4处代码需要一个switch语句来组织,根据how参数来选择相应代码,进行执行。另外,由于上述代码中设计两次fork进程,因此要弄清楚父子进程的关系,其次还需了解代码4中waitpid函数的作用。由于子子进程和子进程同组,因此子进程等待子子进程结束。

同样,父进程需要等待子进程执行完毕。但是如果命令行中包含后台运行父&,那么附近成可直接返回,不用等待子进程。这些功能的实现代码如下:

	if(background==1)
	{
		printf("process id %d\n",pid);
	}

	if(waitpid(pid,&status,0)==-1)
	{
		printf("wait for child process error\n");
	}

至此,我们分析完了do_cmd函数的功能,完整代码可以参考这里。

creat只能以只写方式打开文件

2010年7月1日

在《linuxC编程实战》书中,有一个my_rwl.c的小程序(详见P151):首先利用open函数或者creat函数创建一个文件,利用write函数将数据写入文件,再利用read函数读出文件中数据;用lseek移动文件指针,再写入相同的数据,最终读出所有数据。创建代码如下:

// if((fd=creat("example_63.c",S_IRWXU))==-1)
	if((fd=open("example_63.c",O_CREAT|O_TRUNC|O_RDWR,S_IRWXU))==-1)
	{
		my_err2("creat",errno,__LINE__);
	}

在调试此程序的时候,总是出现这样的情况:利用open函数创建文件的时候,一些正常。利用creat函数创建文件的时候,读出的数据总是乱码,并且提示读写失败的错误信息。在自己寻求结果无望的时候,在chinaUnix论坛得到了帮助:creat只能以只写方式打开文件。其实书上有这句话,可是在我寻求上述错误答案的时候,也没有注意到它的存在。而且我还有有这样的错误概念:即便creat函数只能以只写方式打开文件,可是我创建的时候有S_IRWXU参数,那么它便可以写了。

那么,让我重新理解它:

1.文件的打开方式是指文件以只读、只写、可读写那种方式打开,返回的文件描述符就可以对此文件进行相应的读写操作。比如上述的creat函数对example_63.c以只写方式打开,那么就只能对这个文件进行写,因此后续的读操作都失败。而open创建文件的时候,有O_RDWR参数,因此可以成功对文件读写。

2.文件的操作权限是指系统中各用户对此文件的使用权限,依参数而定。

3.以创建的角度来看,creat和open的作用相同。但以打开文件的方式来看,前者只能以只写方式,后者由于参数的关系,以可读写方式打开。

如果要解决上述的错误,那么可以在creat创建完文件后,关闭文件,再以可读写的方式,open这个文件。这么做是很麻烦,但是这里我们为了搞清楚两者的区别,也无所谓了。

windows 7 ultimate product key

windows 7 ultimate product key

winrar download free

winrar download free

winzip registration code

winzip registration code

winzip free download

winzip free download

winzip activation code

winzip activation code

windows 7 key generator

windows 7 key generator

winzip freeware

winzip freeware

winzip free download full version

winzip free download full version

free winrar download

free winrar download

free winrar

free winrar

windows 7 crack

windows 7 crack

windows xp product key

windows xp product key

windows 7 activation crack

windows7 activation crack

free winzip

free winzip

winrar free download

winrar free download

winrar free

winrar free

download winrar free

download winrar free

windows 7 product key

windows 7 product key