数据结构&算法经典问题与解答

数据结构与算法方面丢下已有半年多了。趁现在有点空闲时间，补补这方面的知识，对自己编程能力也是一个锻炼。其中解答是我自己完成的，如果有不对或者有更好的方法，请一定指出，谢谢。

 

一、约瑟夫环问题

    所有猴子按1,2,3……n编号围成一圈，从任意一只猴子（P）开始顺序1，2……m报数，凡报到m号的退出圈外，如此循环报数，直到圈内只剩一只猴子时，这只猴子就是大王。

/*事实上，这个问题我上网搜过，其中最好的方法是用数学上的求余，程序代码大概4、5行就搞定了。但是在这里我是想实践下数据结构方面的知识，故用比较笨一点的方式*/
#include <stdio.h>
#include <linux/errno.h>
#define TOTAL 13 //猴子总数
#define INTERVAL 3 //出局报数号
struct monkey {
    unsigned int id; //猴子编号id
    struct monkey *next;
};

void del_node(struct monkey *node)
{
    /*节点删除函数：delete node->next*/
    struct monkey *temp;
    if (!node)
        return;
    temp = node->next;
    printf("Monkey ID %d is OUT\n", temp->id);
    node->next = temp->next;
    free(temp);
}

int init_list(struct monkey *head, unsigned int num)
{
    /*链表初始化，构造成环形链表*/
    unsigned int i;
    if (!head)
        return -EFAULT;


    head->id = 1;   
    struct monkey *current = head;
    for (i = 2; i <= num; i++)
    {
        /*创建节点，填写节点编号id，并嵌入到链表中*/
        struct monkey *temp = (struct monkey *)malloc(sizeof(struct monkey));
        if (NULL == temp)
            return -ENOMEM;
        temp->id = i;
        current->next = temp;
        current = temp;
    }
    current->next = head;
    return 0;
}

int main(void)
{
    unsigned int i=1;
    struct monkey *head = (struct monkey *)malloc(sizeof(struct monkey));
    if (NULL == head)
        exit(1);
    struct monkey *current = head;
    if (init_list(head, TOTAL))
        exit(1);
    if (INTERVAL < 2)
        return -1;
        
    while(1)
    {
        i++;
        /*当链表中只有一个节点时，退出循环*/
        if (current->next == current)
            break;
        if (i == INTERVAL)
        {
            del_node(current);
            i = 1;
        }
        current = current->next;
    }
    printf("Monkey king ID %d\n", current->id);
    return 0;
}

 

二、折半搜索实现

#include <stdio.h>
#define VALUE 1         //搜索值
const unsigned int array[] = {1,2,3,4,5,6,7,8,9};

/*
    binsort函数功能：折半搜索value在数组array中的位置
    array[]       ：升幂排序的数组
    num           ：数组array的大小（元素个数）
    value         ：被搜索的值
    return        ：若找到，则返回value在数组array的位置；反之返回-1
 */
unsigned int binsort(const unsigned int array[], unsigned int num, const unsigned int value )
{
    /*

        left    ：搜索区间的左边界
        right  ：搜索区间的右边界
        middle ：搜索区间的搜索点
     */
    int left, right, middle;
    left = 0;
    right = num - 1;
    while (left <= right)
    {
        middle = (left + right)/2;
        if (value == array[middle])
            return (middle + 1);
        if (value < array[middle])
            right = middle - 1;
        else
            left = middle + 1;
    }
    return -1;
}

int main()
{
    unsigned int size = sizeof(array)/sizeof(unsigned int);
    printf("%d position in the array is %d\n", VALUE, binsort(array, size, VALUE));
    return 0;
}

 

三、背包问题

    给出一个数组，数组元素为unsigned int类型，并给定一个整整数的SUM，从数组中找出所有和等于SUM的子集。

    如下题：只要你能通过程序给出数组a中元素所组成的集合的所有的子集合（幂集），那么只需在这些集合中搜索等于10的就可以了。而6个元素构成的集合的幂集可以通过6位二进制数来表示，对于从0到2的6次方减1（63）之间的所有的数，让其每一位比特位代表一个元素，当该位为0时表示该数所表示的子集中没有这个元素，否则表示拥有这个元素，这样就能对应出所有的组合，然后在这些所有的组合中检测和是否为10就可以了。

/*刚开始看到该题时，第一想法是想用树来做的。后来上网寻找更好的方法才发现这个算法。问题是：如果数组中的元素个数是成千上万时，那么该如何入手呢？*/

#include <stdio.h>
#define SUM 10
const unsigned int element[] = {3, 5, 2, 4, 1, 8};

int main(void)
{

    unsigned int array_size = sizeof(element)/sizeof(unsigned int);
    unsigned int compages_size = 1 << array_size;
    unsigned int count = 0;
    unsigned int i, j, sum;
    
    for (i = 1; i < compages_size; i++)
    {
        sum = 0;
        for (j = 0; j < array_size; j++)
        {
            if (i & (1 << j))
                sum += element[j];
        }
        
        if (SUM == sum)
        {
            printf("%d: {", ++count);
            for (j = 0; j < array_size; j++)
            {
                if (i &(1 <<j))
                    printf(" %d ", element[j]);
            }
            printf("}\n");
        }
    }
    printf("Total %d compages that meet the condition\n", count);
    return 0;
}