数据结构-链表(2)

约瑟夫问题

n 个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 8 m = 3

对于这个问题我们用完全可以用循环队列来解决，但是这里我们为了加深一下对链表的操作，我们来用单循环链表来解决。很好类比，单循环链表也是一个圈，我们完全可以用它来模拟这个队伍。

定义结点、

//
typedef struct Node
{
    int data;
    struct Node* pNext;
} Node,*PNODE;
//

为了还原，这里我就没有添加头结点，同时也避免了循环时对头结点的判断，避免了产生与普通数据结点不同的操作，保证所有结点都一样，操作没有差别。

//
PNODE createList(int num)
{
    PNODE pHead,pTail;

    int i;
    for(i = 1; i<= num; ++i)
    {
        if(i == 1)//创建首节点
        {
            pHead = (PNODE) malloc(sizeof(PNODE));
            pHead->data =i;
            pHead->pNext=pHead;//首节点指针域指向自己，构成一个圈
            pTail =pHead;//尾指针指向当前结点
        }
        else
        {
            PNODE pnew = (PNODE)malloc(sizeof(Node));
            pnew->data = i;
            pnew->pNext=pHead;//新结点构建完毕
            pTail->pNext=pnew;//添加到尾指针所指结点之后
            pTail = pnew;//尾指针后移
        }
    }
    return pHead;
}
//

对于删除，我们只需要找到首节点后指定位置的结点并删除即可，同时在使指针指向新的结点，并返回

//
PNODE deleteList(PNODE pHead,int pos)
{
    if(pos == 0)
        return NULL;//不支持直接删除首节点
        //这样我们可以避免删除pHead指向的节点后我们还需要找到它的前驱元素使它指向新的首节点
    PNODE p = pHead;
    int i = 0;
    while(i < pos-1)
    {
        p = p->pNext;
        i++;
    }
    PNODE ptemp = p->pNext;
    p->pNext = ptemp->pNext;
    //printf("删除了%d\n",ptemp->data);
    free(ptemp);
    pHead= p->pNext;
    return pHead;//我们让被删节点的后一个节点作为新首节点
    //同样也避免了首节点被删除的可能
}
//

输入输出

//
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    PNODE pHead = createList(m);
    while(pHead->pNext != pHead)
    {
        pHead = deleteList(pHead,n-1);
        //printf("删除了%d",)
    }
    printf("%d",pHead->data);
    return 0;
}
//

两个单链表的归并 

归并（merge）：将两种以上相同性质的文件数据归并在一起。

例: 男生从高到矮排成一队，女生从高到矮排成一队，现在我们要让他们合并成一队，这就是归并。

首先ab两队都指向第一位，进行比较

b的比较小，则把b的放入c中，b和c都后移一位，再比较a和b的当前项

a的比较小，放入c中，a和c后移一位

a已经都放入c中，不再需要比较，只需要把b剩下的都放入c中，归并结束

 

例

假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写程序将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

//
PNODE mergeList(PNODE p1,PNODE p2)
{
    PNODE p3 = (PNODE)malloc(sizeof(NODE));//归并后存储结果的链表
    PNODE pTail = p3;
    p1 = p1->pNext;
    p2 = p2->pNext;
    while(p1 != NULL && p2 != NULL)//只要有一个循环到尾，结束循环
    {
        if(p1->val < p2->val)
        {
            PNODE pNew = (PNODE)malloc(sizeof(NODE));
            pNew->val = p1->val;
            pNew->pNext = NULL;//新结点构建完毕
            pTail->pNext = pNew;//将新结点添加到p3尾部
            pTail = pNew;//尾指针指向新结点
            p1 = p1->pNext;//p1指针后移

        }
        else
        {
            PNODE pNew = (PNODE)malloc(sizeof(NODE));
            pNew->val = p2->val;
            pNew->pNext = NULL;
            pTail->pNext = pNew;
            pTail = pNew;
            p2 = p2->pNext;
        }
    }
    while(p1!=NULL)//如果因为p2归并结束，将p1剩下的放入p3中
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->val = p1->val;
        pNew->pNext = NULL;
        pTail->pNext = pNew;
        pTail = pNew;
        p1 = p1->pNext;
    }
    while(p2!=NULL)//如果因为p1归并结束，将p2剩下的放入p3中
    {
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->val = p2->val;
        pNew->pNext = NULL;
        pTail->pNext = pNew;
        pTail = pNew;
        p2 = p2->pNext;
    }
    return p3;
}
//

来试一下这个函数

//
int main(void)
{
    PNODE pList1 = createList();
    PNODE pList2 = createList();
    PNODE pList3 = mergeList(pList1,pList2);
    traverseList(pList1);
    traverseList(pList2);
    traverseList(pList3);

    return 0;
}
//

输出结果：创建的两个链表

/*
第1个元素为1
第2个元素为5
第3个元素为9
遍历结束
第1个元素为2
第2个元素为8
第3个元素为22
第4个元素为44
第5个元素为66
遍历结束
*/

归并结果

/*
第1个元素为1
第2个元素为2
第3个元素为5
第4个元素为8
第5个元素为9
第6个元素为22
第7个元素为44
第8个元素为66
遍历结束
*/

取出位置长度单链表中间结点

普通方法：遍历一遍，计算链表长度，再取出链表中间结点时间复杂度为O（L+L/2）

快速方法：利用快指针和慢指针，两个指针*fast和*slow,都指向首结点，slow向后移动，fast以二倍的速度向后移动，当fast到达链表尾部时，slow正好指向链表中间。

//
int getMid(PNODE pHead)
{
    PNODE fast,slow;
    fast = slow = pHead->pNext;
    while(fast->pNext != NULL)//fast->pNext == NULL说明到尾节点
    {
        if(fast->pNext->pNext != NULL)//如果不满足说明下一个是尾节点，只能后移一位
        {
            slow=slow->pNext;
            fast = fast->pNext->pNext;
        }
        else
        {
            fast = fast->pNext;
        }
    }
    return slow->val;
}
//

 

《数据结构-链表(2)》有26个想法

  15. best CBD Oil说：
    回复

    I’m extremely inspired along with your writing skills and also with the structure in your blog. Is that this a paid topic or did you customize it your self? Either way stay up the excellent quality writing, it is rare to see a great weblog like this one today..|

发表评论

邮箱地址不会被公开。 必填项已用*标注