프로그래머 면접 보전 의 데이터 구조 기초 - 순환 링크 (조세 프 링 문제)

1862 단어 데이터 구조
순환 체인 테이블, 즉 단일 체인 테이블 은 바늘 이 머리 를 가리 키 는 지점 이다. 물론 순환 체인 테이블 을 구축 할 때 체인 테이블 을 바늘 이 머리 를 가리 키 는 지점 으로 할 수 있다. 그러나 본 사례 는 한 노드 만 있 는 순환 체인 테이블 (즉 next 바늘 이 자신의 결점 을 가리 키 는 것) 을 구축 한 다음 에 이 순환 체인 테이블 에 노드 를 삽입 하여 최종 순환 체인 테이블 (코드 참조) 을 실현 한다.여기 서 저 는 '위 두 결점' 의 노드 (즉, 처음에 만 든 노드) 를 기본적으로 지 정 했 습 니 다. 뒤에서 K 번 째 노드 를 찾 을 때 도 이 '위 두 결점' 을 사 용 했 습 니 다.
#include 
#include 
#include 
#define NUM 0;

using namespace std;
//      ,         (       )
typedef struct Node
{
    int data;
    struct Node *next;
}node;
void Josephus(int n, int k, int m)
//n          ,k          ,m        
{
    node* p ;
    node* report;
    //node* head;
    node* curr;
    //creat the circulate list
    //     
    //                p,             。
    p = (node*)malloc(sizeof(node));
    p->data = 1;
    p->next = p;
    curr = p;
    for(int i = 2;i <= n;i++)
    {
        node* t = (node*)malloc(sizeof(node));
        t->data = i;
        t->next = curr->next;
        curr->next = t;
        curr = t;

    }
    //         , curr       
    report = curr->next; //   curr->next           ,    1   (    )
    //   k   
    for(int j = 1; j < k ;j++)
    {
        report = p;
        p = p->next;
    }
    //          
    while(n--)
    {
        for(int s = m-1; s >0 ; s--)
        {
            report = p;
            p = p->next;
        }
        report->next = p->next;
        printf("%d->",p->data);
        free(p);
        p = report ->next ;
    }

}
int main()
{
    Josephus(15,6,2);
    return 0;
}

출력 결과:
7->9->11->13->15->2->4->6->10->14->3->8->1->12->5-> Process returned 0 (0x0)   execution time : 2.293 s Press any key to continue.

좋은 웹페이지 즐겨찾기