}

4、请写出判断“点是否在简单多边形内部”的算法。（本题20分）
//相对正确的解题思路：从该点向某一个方向做一条射线，如果与多边形相交的点是奇数个，则在多边形内；否则，可能在多边形内。
//不太正确的解题思路：如果一个点在一个多边形内，那么从该点向上、向下、向左、向右都应与简单
//多边有交点,点在某一条边上算在多边形内（下面的程序代码也有问题）。
#include<stdio.h>
#define N 10
typedef struct Node
{
    float x;
    float y;
}XYNode,Nodes[N+1];
void main()
{
    int i,up=0,down=0,left=0,right=0;
    int x0,x1,x2,y0,y1,y2;
    char flag = 'Y';
    XYNode point;
    Nodes a;
    for(i=0;i<N;i++)
    {
        printf("please input the %dst coordinate:",i+1);
        scanf("%f,%f",&a[i].x,&a[i].y);
    }
    a[N].x = a[0].x;      //使起点和终点的坐标相同
    a[N].y = a[0].y;
    while(flag!='n' && flag !='N')
    {
        printf("Now, please input the Point's coordinate:");
        scanf("%f,%f",&point.x,&point.y);
        for(i=0;i<N;i++)
        {
            if((a[i].x>point.x && a[i+1].x<=point.x)||(a[i].x<point.x && a[i+1].x>=point.x))
            {
                x1 = a[i].x;
                y1 = a[i].y;
                x2 = a[i+1].x;
                y2 = a[i+1].y;
                x0 = point.x;
                y0 = (y1-y2)*(x0-x1)/(x1-x2) + y1;
                if(y0==point.y)
                {
                    up =1; down = 1; left = 1; right = 1;
                    break;
                }
                else if(y0>point.y)
                    up = 1;
                else
                    down = 1;
            }//if
            if((a[i].y>point.y && a[i+1].y<=point.y)||(a[i].y<point.y && a[i+1].y>=point.y))
            {
                x1 = a[i].x;
                y1 = a[i].y;
                x2 = a[i+1].x;
                y2 = a[i+1].y;
                y0 = point.y;
                x0 = (x1-x2)*(y0-y1)/(y1-y2) + x1;
                if(x0==point.x)
                {
                    up =1; down = 1; left = 1; right = 1;
                    break;
                }
                else if(x0>point.y)
                    right = 1;
                else
                    left = 1;
            }//if
        }//for
        if(up && down && left && right)
            printf("Yes,the point is in the polygon.\n");
        else
            printf("No,the point is not in the polygon.\n");
        while(getchar()!='\n');     //接收多余的字符
        printf("would you like to go on?<Y/N>");
        flag = getchar();           //flag只接收第一个字符
        while(getchar()!='\n');     //接收多余的字符
    }//while
}

5、从平均时间、最坏情况，辅助存储和稳定性的角度，对各种内部排序方法进行比较。
（建议用表格方式进行比较，本题20分）
严蔚敏数据结构289页

6、定义一个双向循环链表，并写出其定位、插入和删除算法。（本题20分）
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode,*DuLinkList;

Status GetElem_DuL(DuLinkList L,int i,ElemType *e)
{
    int j = 1;
    DuLNode *p;
    p = L->next;
    while(p!=L && j<i)
    {
        p = p->next;
        j++;
    }
    if(p==L || j!=i)
        return ERROR;
    *e = p->data;
    return OK;
}

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e)
{//在带头结点的双链循环链表L中第i个位置之前插入元素e
 //i的合法位置为1<=i<=表长+1
    int j;
    DuLNode *p,*s;
    if(i<1) //如果i的值小于1，则返回错误
        return ERROR;
    j = 1;
    p = L->next;
    while(p!= L && j<i)
    {
        p = p->next;
        j++;
    }
    if(j<i) //查找完循环链表后，如果j<i，则表明i的位置不合法
        return ERROR;
    if(!(s = (DuLNode *)malloc(sizeof(DuLNode))))
        return ERROR;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;
    return OK;
}

Status ListDelete_DuL(DuLinkList &L,int i,ElemType *e)
{//删除带头结点的双链循环线性表L的第i个元素，i的合法位置为1<=i<=表长
    int j;
    DuLNode *p;
    if(i<1)
        return ERROR;
    j = 1;
    p = L->next;
    while(p!=L && j<i)
    {
        p = p->next;