2011年五月

【编程之美】单链表是否存在环以及环入口的位置【转载】

原文地址:http://blog.csdn.net/ssfp8762/archive/2009/07/08/4331419.aspx

有一个单链表,其中可能有一个环,也就是某个节点的next指向的是链表中在它之前的节点,这样在链表的尾部形成一环。
1、如何判断一个链表是不是这类链表?
2、如果链表为存在环,如果找到环的入口点?
扩展:判断两个单链表是否相交,如果相交,给出相交的第一个点。

解答:

一、判断链表是否存在环,办法为:

设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。

二、链表环入口的位置计算

当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:

2s = s + nr
s= nr

设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L – a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。

扩展问题:

判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

比较好的方法有两个:

一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。

这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。



socket编程中如何区分不同的网络连接

在网络编程中,服务器程序的代码结构一般如下:

socket() -> bind() -> listen() -> accept()

当有一个新的客户端连接时,accept建立一个新的socket,然后将sockfd返回,接下来数据的发送和接收就都在这个sockfd中进行

但是一直有一个问题我比较困惑:在服务器端,当有数据到达时,协议栈是如何将数据传递到正确的sockfd的呢(服务器端存在多个已连接的客户端)?因为不同的网络连接是使用同一个监听端口,如80端口,不可能为每一个建立的连接分配一个端口(事实也不是这样);

上网搜寻一下,一个比较合理的解释:使用网络连接的源ip+源port来区分不同的数据连接,本身TCP协议中提供,而且可以唯一标识网络连接,因为不可能同一个客户端使用同一个端口进行来连接server的。



平面中两点的最近距离与最远距离

今天看编程之美,看到求平面中两点的最近距离,书中给出了O(nlogn)算法,主要是采用分治的方法来做的,首先将平面的点按x坐标分为两部分,分别求最近点对,然后是合并;合并过程中对于两个点分别在两个区域的分析非常巧妙,有效地减少了需要比较的点对的个数。

在poj中对应的题目3714

然后又看到了扩展问题:如何求平面中最远的两个点的距离

这个就不能继续套用“最近距离点对”的分治策略,上网查了下,原来是使用凸包算法+旋转卡壳算法,poj中对应的题目是2187和3608

这里简单记录下,明天做下这两个题目

关于凸包算法和旋转卡壳算法的介绍:

http://yishan.cc/blogs/gpww/archive/2011/02/16/graham-s-scan.aspx

http://www.cppblog.com/staryjy/archive/2010/09/25/101412.html

http://yishan.cc/blogs/gpww/archive/2011/02/15/1787.aspx

ax操作的时间复杂度为


关于编译器字节对齐的解释与原因

百度百科解释的比较清楚,记录下

http://baike.baidu.com/view/1523557.htm



linux中有关用户与组的命令小结

添加用户:

adduser username #添加用户
passwd username  #为用户设置密码
adduser -g groupname username #添加用户时也添加组
gpasswd -a usename groupname #将用户添加到组中

添加组:

groupadd groupname # 这里不知为何与adduser的命名方式不一样

锁定用户:

passwd username -l  #锁定用户
passwd username -u #解锁用户

永久删除用户:

deluser username
groupdel groupname
gpasswd -d username groupname #从组groupname中删除用户username