日志标签 ‘C编程’

分治算法之快速排序

2011年5月4日

快速排序算法也是基于分治思想的一种排序算法,它的基本操作即为比较-交换。

快速排序算法的基本思想是从待排序的序列中选取一个比较标准K(通常选取第一个元素),然后将其余元素依次跟K进行比较。在比较的过程中将大于K的元素移到K的后面,将小于K的元素移到K的前面,最后的结果是将原始序列分为两个子序列,而K元素则恰好位于两个子列中间。上述过程称为一趟快速排序,接下来依次为两个子序列进行快速排序,依次递归。当子序列的长度小于1时,递归停止。此时,原始序列已经成为一个有序的序列了。

根据上面的思想,快速排序算法的代码实现如下所示。quickSort函数对原始序列递归进行快速排序,每次排序时先通过partiton函数得到序列中p到r元素间的分界点q,然后再分别对两个子序列p到q-1和q+1到r进行快速排序。

void quickSort(int *a, int p, int r)
{
	if (p < r) {
		int q = partition(a, p, r);
		quickSort(a, p, q - 1);
		quickSort(a, q + 1, r);
	}
}

partition函数是快速排序算法的关键。该函数选取待排序序列的第一个元素作为基准,通过反复的比较-交换将p到r之间的元素分成两组子序列,一组子序列的元素全部小于x,另一组子序列的元素全部大于x。

在具体的比较-交换过程中,设置两个记录点low和high,并在初始时将基准保存到x中。然后不断进行下面两种扫描:

1.将high从右至左扫描,直到a[high] < x为止,由于此时的a[high]是第一个小于基准x的元素,因此将a[high]和x交换。

2.将low从左至右扫描,直到a[low] >= x为止,由于此时的a[low]是第一个不小于基准x的元素,因此将a[low]和x交换。

当low小于high时会一直持续上述两种扫描,否则称其完成了一次划分过程。每一次的划分过程就会得到分界位置,返回为quickSort函数。

int partition(int *a, int p, int r)
{
	int x, low, high;

	x = a[p];
	low = p;
	high = r;

	while (low < high) {
		while (low < high && a[high] >= x)
			high--;
		if (low < high) {
			a[low] = a[high];
			a[high] = x;
			low++;
		}
		output_data(a, n);

		while (low < high && a[low] < x)
			low++;
		if (low < high) {
			a[high] = a[low];
			a[low] = x;
			high--;
		}
		output_data(a, n);
	}
	a[low] = x;
	return low;
}

在partition函数中,选择第一个元素p作为基准可以保证该函数正常退出。如果选取最后一个元素r作为基准,而该元素又恰好是最大元素,那么partition函数就会返回r,这使得quickSort无限递归下去。完整的代码可在这里下载

C/S模型中的并发服务器

2011年4月20日

网络通信程序中最经典的模型就是客户端/服务器(C/S)模型。该模型中的服务器程序通常处于长时间运行的状态,当客户端程序主动对服务器程序发出网络请求时,服务器程序才做出具体的回应。也就是说,服务器大多数处于等待状态,只有收到客户端的网络请求才被唤醒,当处理完客户端的请求时候,又将处于等待状态。

上述同时只能处理一个客户端请求的服务器被称为迭代服务器(iterative server),这样的C/S模型只能应对那些简单的应用。大多数情况下我们希望服务器可以同时服务多个客户端程序,即服务器程序既能处理客户端发送来的请求同时又能接收其他客户端发送的请求。这样的服务器称为并发服务器(concurrent server)。

Linux中实现并发服务器的方法很简单:每当客户端对服务器有网络请求时,服务器程序就fork一个子服务器进程来处理这个客户的请求,而主服务器程序仍处于等待其他客户端网络请求的状态。基于这个原理,并发服务器的基本模型如下:

	if ((sockfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
		my_error("socket", errno, __LINE__);
	}

	if (bind(sockfd, (struct sockaddr *)&my_addr,
				sizeof(struct sockaddr_in)) == -1) {
		my_error("bind", errno, __LINE__);
	}

	if (listen(sockfd, BACKLOG) == -1) {
		my_error("listen", errno, __LINE__);
	}

	while (1) {
		sin_size = sizeof(struct sockaddr_in);
		if ((client_fd = accept(sockfd, (struct sockaddr *)&remote_addr, &sin_size)) == -1) {
			my_error("accept", errno, __LINE__);
			continue;
		}

		if ((pid = fork()) == 0) {
			close(sockfd);
			process_client_request(client_fd);
			close(client_fd);
			exit(0);
		} else if (pid > 0)
			close(client_fd);
		else
			my_error("fork", errno, __LINE__);
	}

每当accept()接收到一个TCP连接时,主服务器进程就fork一个子服务器进程。子服务器进程调用相应的函数,通过client_fd(连接套接字)对客户端发来的网络请求进程处理;由于客户端的请求已被子服务进程处理,那么主服务器进程就什么也不做,通过sockfd(监听套接字)继续循环等待新的网络请求。

这里我们需要特别强调的是,在父子进程中需要关闭相应的套接字描述符。从上述代码中可以看到,子服务进程在处理客户端的网络请求之前关闭了监听套接字,主服务进程则关闭了连接套接字,子服务进程在处理完客户端请求后关闭了连接套接字。最后一种关闭套接字的情形比较合乎常理,这里我们重点关注前两种关闭套接字的情况。

我们的问题是:子服务进程关闭了监听套接字,服务器是否还能监听其他连接请求;父服务进程关闭了连接套接字,服务器是否还能够处理客户端请求。

如果理解了文件的的引用计数,这个问题就会迎刃而解。每个文件都有一个引用计数,该引用计数表示当前系统内的所有进程打开该文件描述符的个数。套接字是一种特殊的文件,当然也有引用计数。

在并发服务器这个例子当中,在accept函数之前,sockfd的引用计数为1;在fork函数执行之前,sockfd和client_fd的引用计数分别为1;当fork执行后,由于子进程复制了父进程的资源,所以子进程也拥有这两个套接字描述符,则此时sockfd和client_fd的引用计数都为2。只有当子进程处理完客户请求时,client_fd的引用计数才由于close函数而变为0。由于父服务器进程的主要任务是监听客户请求,则它关闭了连接套接字client_fd;而子进程的主要任务是处理客户请求,它不必监听其他客户请求,因此子进程关闭了sockfd。由上可知,父子进程关闭相应的套接字并不会影响其所负责的通信功能。

我们可以通过下面的两幅示意图更进一步了解fork函数执行前后的客户端和服务器之间的状态。

父子进程关闭相应套接字后客户端和服务器端的状态如下:

这就是监听套接字和连接套接字两者的最终状态,子进程处理客户请求,父进程监听其他客户请求。这样的并发服务器看似完美,但是会产生许多僵死进程,这是为什么?下文将会分析。

分治算法之合并排序

2011年4月13日

分治算法的基本思想是将一个规模为n的问题分解成k个规模较小的子问题,这些子问题相互独立并且与原问题相同。先递归的解决这些子问题,然后再将各个子问题的解合并到原问题的解当中。

合并排序算法是用分治策略实现对n个元素进行排序的算法。其基本思想是将待排序元素分成大小大致相同的两个子集合,分别对两个子集合进行排序,最终将排好序的两个子集合合并成一个排好序的集合。合并排序算法可递归的伪代码表达如下:

void mergeSort(int *a, int left, int right)
{
	int i;
	if (left < right) {
		i = (left + right) / 2;
		mergeSort(a, left, i);
		mergeSort(a, i + 1, right);
		merge(a, b, left, i, right);
		copy(a, b, left, right);
	}
}

在mergeSort函数内,不断的进行递归调用以缩小问题规模;merge函数用于将两个排好序的子序列合并成一个大的有序序列,并存储在数组b中;最后利用copy函数将b数组的序列再重新拷贝到数组a中,完成合并排序。

上述的mergeSort函数中,递归调用是整个算法的关键步骤。mergeSort函数不断的平分待排序的数列集合,如果当前数列集合两端的序号分别为left和right,那么平分后的两个数列集合序号分别是left到i和i+1到right。这种不断平分并递归的结果是使得当前的待排序集合中只剩下一个元素,接着再进行两两子序列集合的合并。

正如上面所说的,这些待合并的子序列都已排好序。并且最初一批待合并的子序列集合中只有一个元素,合并后元素数量为2,再次合并为4,依次类推。

根据上述的描述,我们可以将递归形式的合并排序算法改进成非递归的形式。在上述递归形式中,我们是从整个序列出发,逐渐平分再递归。而非递归形式的排序算法则先让整个序列中相邻的元素两两进行排序,形成n/2个长度为2的已排好序的子序列。接着再将它们排成长度为4的子序列,以此类推。该算法结束结束时是将两个已经排好序的子序列排成一个有序序列。

根据上面的思路,非递归形式的合并算法可参考如下代码。mergeSort函数依次对整个待排序的序列中长度为1、2、4、8的子序列进行排序。s即为当前正进行排序的子序列集合的元素个数。

void mergeSort(int a[], int n)
{
	int *b = NULL;
	int s = 1;
	int count = 1;

	b = (int *)malloc(sizeof(int) * n);
	while (s < n) {
		printf("sort %d:\n", count++);
		mergePass(a, b, s, n);
		s += s;
		printf("sort %d:\n", count++);
		mergePass(b, a, s, n);
		s += s;
	}
	free(b);
}

mergePass函数的作用是大小为s的相邻子序列。通过while循环将整个序列分成n/s个大小为s的子序列,由于这写子序列内部已经排好序,则调用merge函数直接进行合并即可。

void mergePass(int x[], int y[], int s, int n)
{
	int i = 0;
	int j;

	while (i < n - 2 * s) {
		merge(x, y, i, i + s - 1, i + 2 * s -1);
		i = i + 2 * s;
	}

	if (i + s < n)
		merge(x, y, i, i + s - 1, n - 1);
	else
		for (j = i; j <= n - 1; j++)
			y[j] = x[j];

	for (i = 0; i < n; i++)
		printf("%d ", y[i]);
	printf("\n");
}

merge函数的作用是合并两个相邻的子序列,这两个子序列的序号分别为l到m和m+1到r。

void merge(int c[], int d[], int l, int m, int r) 
{
	int i, j, k;
	
	i = l;
	j = m + 1;
	k = l;
	while ((i <= m) && (j <= r))
		if (c[i] <= c[j])
			d[k++] = c[i++];
		else 
			d[k++] = c[j++];
	
	int q;
	if (i > m)
		for (q = j; q <= r; q++)
			d[k++] = c[q];
	else
		for (q = i; q <= m; q++)
			d[k++] = c[q];
}

以上就是合并算法的核心函数,完整代码可以从这里下载

Linux下的socket编程-基于Qt的客户端

2011年3月20日

上文中对面向连接的C/S模型中的服务器进行了简单描述,本文将说明如何编写一个客户端应用程序。与服务器程序不同,客户端程序要求有友好的交互界面,因此本文所示的客户端程序采用Qt和linux C共同完成。客户端的界面部分采用Qt完成,而与服务器间具体的通信部分则通过linux C语言完成。

1.界面设计

通过Qt Designer可快速设计好客户端界面,并对四个按钮所对应的信号和槽函数进行连接。客户端所对应的类为ClientUI。

2.与服务器间通信的编程

由于Qt是对C++的一种扩展,因此我们必须将使用Linux C编写的客户端通信程序封装成类,这里我们将其定义为ClientConnection。

我们已经对客户端的界面和通信部分分别定义了两个类,但是如何将两者结合在一起?方法很简单。将ClientConnection类的对象cli作为ClientUI类的成员,然后在具体的槽函数中对应相应的通信函数。和上文分析服务器编程的方法不同,本文将以分析客户端对应的槽函数的方式来说明如何编写客户端程序。

2.1连接按钮的槽函数

在连接按钮对应的槽函数中,首先创建客户端套接字描述符;然后从输入框中获得服务器的IP地址;再通过connect函数创建一个连接。

connect函数的原型如下:

     #include < sys/socket.h >
     int connect(int sockfd, const struct sockaddr *addr, socklen_t addrlen);

connect函数用于在sockfd套接字上创建一个连接,sockfd即客户端套接字;addr即为服务器端的套接字地址;addrlen为addr的长度。我们将connect函数封装成ClientConnection类中的connectingSocket函数,该成员函数在连接按钮所对应的槽函数中被调用。:

int ClientConnection::connectingSocket()
{
    if (::connect(sockfd, (struct sockaddr *)&serv_addr,
                          sizeof(struct sockaddr)) == -1) {
        return 0;
    }

    return 1;
}

在该槽函数中,可以这样使用连接函数:

    if (cli.connectingSocket() == 1) {
        ui->statusLabel->setText("connecting to server success!");
    } else {
        ui->statusLabel->setText("ERROR:connecting to server fail!");
        //exit(1);
    }

当客户端连接至服务器成功后,客户端就可以跟服务器端进行数据的传送。

2.2 修改按钮的槽函数

该槽函数的工作比较简单,使得文本编辑区可被编辑。

2.3 应用按钮的槽函数

在该槽函数中,将文本编辑区的数据发送至服务器端;或从服务器接受数据显示在这个文本编辑区中。发送和接受数据的API仍然是send和recv函数,不过这里我们将这两个函数封装成ClientConnection类中的sendData成员和recvData成员:

int ClientConnection::recvData(char *buf)
{
    if ((recvbytes = recv(sockfd, buf, MAX_DATA_NUM, 0)) == -1) {
        return 0;
    }

    buf[recvbytes] = '\0';
    return 1;
}

int ClientConnection::sendData(char *msg, int len)
{
    if (send(sockfd, msg, len, 0) == -1) {
        printf("send error!\n");
        return 0;
    }

    return 1;
}

这两个成员函数在该槽函数的适当位置被调用。

2.4退出按钮的槽函数

退出按钮的槽函数中只需断开客户端和服务器之间的连接即可。

参考:

1.Qt Assistant

2.Linux C编程实战;童永清 著;人民邮电出版社;

Linux下的socket编程-服务器

2011年3月15日

我们都知道,同一台计算机上的进程可以通过IPC(进程间通信)机制进行通信;而不同机算计上运行的进程则通过网络IPC,即套接字(socket)进行通信。Linux下的socket API是基于BSD套接口而是实现的,通过这些统一的API就可以轻松实现进程间的网络通信。此外,socket API即可用于面向连接(TCP)的数据传输,又可用于无连接(UDP)的数据传输。一般使用Client/Server交互模型进行通信。

本文以及下文将实现一个面向连接的C/S通信模型。本文首先介绍服务器端的实现。

1.创建套接字

#include < sys/socket.h >
int socket(int domain, int type, int protocol);

通过socket函数可以创建一个套接字描述符,这个描述符类似文件描述符。通过这个套接字描述符就可以对服务器进行各种相关操作。

该函数包含三个参数,domain参数用于指定所创建套接字的协议类型。通常选用AF_INET,表示使用IPv4的TCP/IP协议;如果只在本机内进行进程间通信,则可以使用AF_UNIX。参数type用来指定套接字的类型,SOCK_STREAM用于创建一个TCP流的套接字,SOCK_DGRAM用于创建UDP数据报套接字。参数protocol通常取0。对于本文所描述的服务器,创建套接字的示例代码如下:

	if((sockfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {

		printf("socket error!\n");
		exit(1);
	}

2.绑定套接字

对于服务器而言,它的IP地址和端口号一般是固定的。服务器的IP即为本地IP,而服务器的端口号则需要显示的指定。通过bind函数可将服务器套接字和一个指定的端口号进行绑定。

在具体介绍绑定函数之前,先说明一下socket中的套接字地址结构。由于套接字是通过IP地址和端口号来唯一确定的,因此socket提供了一种通用的套接字地址结构:

   struct sockaddr {
               sa_family_t sa_family;
               char        sa_data[14];
           }

sa_family指定了套接字对应的协议类型,如果使用TCP/IP协议则改制为AF_INET;sa_data则用来存储具体的套接字地址。不过在实际应用中,每个具体的协议族都有自己的协议地址格式。比如TCP/IP协议组对应的套接字地址结构体为:

struct sockaddr_in {
	short int sin_family; /* Address family */
	unsigned short int sin_port; /* Port number */
	struct in_addr sin_addr; /* Internet address */
	unsigned char sin_zero[8]; /* Same size as struct sockaddr */
};

struct in_addr {
	unsigned long s_addr;
};

该地址结构和sockaddr结构均为16字节,因此通常在编写基于TCP/IP协议的网络程序时,使用sockaddr_in来设置具体地址,然后再通过强制类型转换为sockaddr类型。

绑定函数的函数原型如下:

       #include < sys/socket.h >
       int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);

参数sockfd即服务器的套接字描述符;addr参数指定了将socket绑定到的本地地址;addrlen则为所使用的地址结构的长度。示例代码如下:

	memset(&my_addr, 0, sizeof(struct sockaddr_in));
	my_addr.sin_family = AF_INET;
	my_addr.sin_port = htons(SERV_PORT);
	my_addr.sin_addr.s_addr = htonl(INADDR_ANY);

	if(bind(sockfd, (struct sockaddr *)&my_addr,
				sizeof(struct sockaddr_in)) == -1) {

		printf("bind error!\n");
		exit(1);
	}

注意在上述代码中,将IP地址设置为INADDR_ANY,这样就既适合单网卡的计算机又适合多网卡的计算机。

3.在套接字上监听

对于C/S模型来说,通常是客户端主动的对服务器端发送连接请求,服务器接收到请求后再具体进行处理。服务器只有调用了listen函数才能宣告自己可以接受客户端的连接请求,也就是说,服务器此时处于被动监听状态。listen函数的原型如下:

       #include < sys/socket.h >
       int listen(int sockfd, int backlog);

sockfd为服务器端的套接字描述符,backlog指定了该服务器所能连接客户端的最大数目。超过这个连接书目后,服务器将拒绝接受客户端的连接请求。示例代码如下:

        #define BACKLOG 10
	if(listen(sockfd, BACKLOG) == -1) {

		printf("listen error!\n");
		exit(1);
	}

4.接受连接

listen函数只是将服务器套接字设置为等待客户端连接请求的状态,真正接受客户端连接请求的是accept函数:

      #include < sys/socket.h >
       int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);

accept函数中所使用的参数都在上面的API中有所描述。accept函数执行成功后将返回一个代表客户端的套接字描述符,服务器进程通过该套接字描述符就可以与客户端进行数据交换。

5.数据传输

由于socket适用多个数据传输协议,则不同的协议就对应不同的数据传输函数。与TCP协议对应的发送数据和接受数据的函数如下:

       #include < sys/socket.h >
       #include < sys/types.h >
       ssize_t send(int sockfd, const void *buf, size_t len, int flags);
       ssize_t recv(int sockfd, void *buf, size_t len, int flags);

从这两个函数的原型可以看书,socket中的数据传输函数与普通文件的读写函数类似,只不过第一个参数需要传递套接字描述符;buf指定数据缓冲区;len为所传输数据的长度;flag一般取0。示例代码如下:

	while (1) {
		sin_size = sizeof(struct sockaddr_in);
		if ((client_fd = accept(sockfd, (struct sockaddr *)&remote_addr, &sin_size)) == -1) {
			printf("accept error!\n");
			continue;
		}
		/*
                 *进行相应的数据处理;
                 */
	}

如示例代码所示,通过while循环使得服务器对客户端进行持续监听。如果客户端有连接请求则新建一个代表客户端的套接字描述符,进而进行对客户端数据的接受和发送。

上述的几个函数属于网络编程中最基本的也是最关键的几个API,依次通过上述的方法就可以完成服务器端的程序的编写,具体的过程还可以参考下图:

正如上图所示,在处理完客户端的数据传输请求后,必须通过close函数关闭客户端的连接。

参考:

1.Linux C编程实战;童永清 著;人民邮电出版社;

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