学步园

Graham算法的思路，大概如下：对平面上的点的集合，从中找到有最小的y坐标值的点p，然后根据其它点和p的连线与正x轴所成的角度将平面上的点进行排序，排序后，扫描从p开始的有序列表，如果所有的这些点都在凸包上，那么每三个相继的点，会组成一个左旋，从另一方面说，如果相继的三个点，p1,p2,p3，组成了一个右旋，则可以立即去除p2，因为它不可能在凸包上！如此扫描到p3等于p时，扫描就结束，剩下的点，就全都是凸包上的点了！

这里面有几个难点：

1、如何根据他们的夹角，来对双链表进行排序

2、如何判断左右旋

3、如何扫描

针对第一个问题，在下面的程序中，采用的是简单的选择排序，即每次在无序区内找到最大的元素，将其放到有序区内，因为这是对双链表进行排序，就有双链表的排序特点，但我认为采用插入，即断开结点之间的联系始终不是好的办法，所以采用了这种简单的交换的方法，虽然效率慢了点，但是重在说明问题！

针对第二个问题，判断左右旋，其实可以用一个行列式的值来判定

|x1   x2  x3|

|y2   y2  y3|

|1    1     1 |

若该行列式为正，则为左旋，反之，则为右旋。其实这个行列式是根据点是在直线的上方还是下方而推断出来的，用直线方程也可以判断左右旋。

针对第三个问题看下面的代码中的scan()函数就很清楚了！

下面是用c++写的具体代码：

#include <iostream><br /> #include <cmath><br /> using namespace std;<br /> struct point<br /> {<br /> float x,y;//坐标<br /> float cos;//该点和x轴的正向所形成的角的余弦<br /> struct point *prev,*next;<br /> };<br /> typedef struct point Type;<br /> /*创建一个双向链表*/<br /> void creatLinklist_Du(Type *L,int n)<br /> {<br /> Type *p;<br /> Type *s;<br /> p=L;<br /> cin>>p->x>>p->y;<br /> p->prev=NULL;<br /> p->next=NULL;//初始化第一个结点<br /> int i;<br /> for(i=0;i<n-1;i++)<br /> {<br /> s=new Type;//这里忘记给S分配空间了，所以出错了。<br /> cin>>s->x>>s->y;<br /> s->next=NULL;<br /> s->prev=p;<br /> p->next=s;<br /> p=s;<br /> }<br /> }<br /> void calculateCos(Type *L)//找到y坐标最小的元素，让它是第一个点，并计算每个点的cos值<br /> {<br /> Type *p=L,*pMin=L;<br /> float min=L->y;<br /> while(p)<br /> {//找到y坐标最小的结点<br /> if(min>p->y)<br /> {<br /> pMin=p;<br /> min=p->y;<br /> }<br /> p=p->next;<br /> }<br /> float x0=pMin->x;<br /> float y0=pMin->y;<br /> p=L;<br /> while(p)<br /> {<br /> float x=p->x;<br /> float y=p->y;<br /> if(x==x0 && y==y0)<br /> p->cos=1;<br /> else<br /> p->cos=(x-x0)/sqrt((x-x0)*(x-x0)+(y-y0)*(y-y0));<br /> p=p->next;<br /> }<br /> }<br /> /*简单选择排序*/<br /> void simpleSlectSort(Type *L)//按cos值进行降序排序<br /> {</p> <p> Type *p,*pMax,*q,*temp=new Type;<br /> for(p=L;p->next;p=p->next)<br /> {<br /> pMax=p;<br /> for(q=p->next;q;q=q->next)//找到无序区的最大的cos<br /> {<br /> if(q->cos > pMax->cos)<br /> pMax=q;<br /> }<br /> if(p!=pMax)//将此最大值放进有序区，这里只需要交换两个结点的内容就可以了<br /> {<br /> temp->cos=pMax->cos;<br /> temp->x=pMax->x;<br /> temp->y=pMax->y;<br /> pMax->cos=p->cos;<br /> pMax->x=p->x;<br /> pMax->y=p->y;<br /> p->cos=temp->cos;<br /> p->x=temp->x;<br /> p->y=temp->y;<br /> }<br /> }<br /> }<br /> float area(float x1,float y1,float x2,float y2,float x,float y)//计算三个点的左旋还是右旋<br /> {<br /> return (x1*y2+x2*y+x*y1)-(x*y2+x1*y+x2*y1);<br /> }<br /> void scan(Type *L)//顺序扫描双链表，判断相继的三个点是否组成左旋或是右旋<br /> {<br /> Type *p=L,*p1=L,*p2,*p3;<br /> float temp;<br /> do{<br /> p2=p1->next;<br /> if(p2->next)<br /> p3=p2->next;<br /> else<br /> p3=p;<br /> temp=area(p1->x,p1->y,p2->x,p2->y,p3->x,p3->y);<br /> if(temp>=0.0)//如果temp为正，则为左旋<br /> p1=p1->next;<br /> else<br /> {<br /> p1->next=p3;<br /> p3->prev=p1;<br /> delete p2;<br /> p1=p1->prev;<br /> }<br /> }while(!(p3==p && temp>=0.0));<br /> }<br /> /*输出双向链表中的元素*/<br /> void outputLinklist_Du(Type *L)<br /> {<br /> Type *p;<br /> p=L;</p> <p> while(p)<br /> {<br /> cout<<p->x<<" "<<p->y<<"/t"<<p->cos<<endl;<br /> p=p->next;<br /> }<br /> }</p> <p>int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> Type *L=new Type;<br /> creatLinklist_Du(L,4);<br /> calculateCos(L);<br /> simpleSlectSort(L);<br /> scan(L);<br /> outputLinklist_Du(L);<br /> return 0;<br /> }