데이터 구조 와 알고리즘 복습: 유 세 프 문제 선형 표 해결

데이터 구조 와 알고리즘 - 복습: 유 세 프 문제 선형 표 해결
여기 서 유 세 프 문제 가 무엇 인지 개술 하지 않 겠 습 니 다. 일반적인 데이터 구조 교재 에는 이 문제 가 있 습 니 다.다음은 본 문제 에 관 한 선형 표 해법 을 제시 합 니 다.
문제 풀이 방식
아 날로 그 번호: 이 방식 은 단일 순환 링크 에 더욱 적합 합 니 다. 하나의 카운터 로 현재 번호 의 크기 를 기록 하고 지침 으로 규정된 번호 의 출발점 을 가리 킵 니 다.링크 가 비어 있 을 때 까지 링크 를 반복 해서 삭제 합 니 다.순환 링크 이기 때문에 모든 조작 이 편리 합 니 다.이런 방식 의 복잡 도 는 계산 을 통 해 O (n * m) 이다.
추론 수열: 간단 한 수열 의 번호 결 과 를 쓰 고 해당 하 는 배열 의 하 표를 제시 하면 아래 표 와 번호 의 최대 치, 그리고 현재 책상 위의 사람의 총수 의 관 계 를 쉽게 추리 할 수 있다.즉:

（    +    -1）%      =             

잉여 연산 의 작용 을 깊이 이해 해 야 한다.나 는 개인 적 으로 그 가 순환 회전 과 일정한 관계 가 있다 는 것 을 이해한다.
다음은 프로그램 세 션 코드 를 드 립 니 다:

/**
 * Josephus       
 *  n  ，      ，    s      ，     1  ，   m，    m
 *     ，    n      
 *     ：
 *       ，       ：（    +    -1）%      =          
 *   ，     ：
 * 1 2 3 4 5      ：
 * 0 1 2 3 4     3   ，    ，  2   ，         4，    ，           ：
 * 4 1 3 2 5         ：
 * 3 0 2 1 4       ：（    +    -1）%      =          
 *                 
 */
#include 
#include 

/**
 *        
 */
struct SeqList{
    int MAXNUM; //         
    int n;  //             
    int* vals;  // DataType* X;
};
typedef struct SeqList * PSeqList; //      SeqList     

/**
 * 1.         
 * @param m      
 * @return
 */
PSeqList createNullList_Seq(int m){
    PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList));
    if(palist != NULL){
        palist->vals = (int*)malloc(sizeof(int) * m);
        if(palist->vals){
            palist->n = 0;
            palist->MAXNUM = m;
            return palist;
        } else{
            free(palist);
        }
    }
    printf("            
");
    return NULL;
}

/**
 * 2.         
 * @param palist
 * @return
 */
int isNullList_Seq(PSeqList palist){
    if(palist->n == 0)
        return -1;
    else
        return 0;
}

/**
 * 3.    ，             
 * @param palist
 * @param x
 * @return
 */
int locate_seq(PSeqList palist,int x){
    if(isNullList_Seq(palist))
        return -1;
    for(int i=0;i<palist->n;i++)
    {
        if(palist->vals[i] == x)
            return i;
    }
    return -1;
}

/**
 * 4.         ，    
 * @param palist
 * @param position
 * @param x
 * @return
 */
int insertPre_seq(PSeqList palist, int position,int x){
    if(isNullList_Seq(palist))
        return -1;
    if(palist->MAXNUM <= position){
        printf("   ，       
");
        return -1;
    }
    if(position<0 || position>palist->n){
        printf("      %d   
",position);
    }
    for(int i = palist->n; i>=position; i--)
    {
        palist->vals[i] = palist->vals[i-1];
    }
    palist->vals[position] = x;
    palist->n += 1;
    printf("    
");
    return 1;
}

/**
 * 5.         
 * @param palist
 * @param position
 * @return
 */
int deleteP_seq(PSeqList palist,int position){
    if(isNullList_Seq(palist)){
        printf("     ，    
");
        return -1;
    }
    if(position > palist->n || position < 0){
        printf("           %d   ，    
",position);
        return -1;
    }
    for(int i = position; i<palist->n;i++){
        palist->vals[i] = palist->vals[i+1];
    }
    palist->n -= 1;
    printf("    
");
    return 1;
}

/**
 * 6.         
 * @param palist
 * @param x
 * @return
 */
int deleteV_seq(PSeqList palist,int x){
    if(isNullList_Seq(palist)){
        printf("     ，    
");
        return -1;
    }
    if(locate_seq(palist,x) == -1){
        printf("     ，    
");
        return -1;
    }
    deleteP_seq(palist,locate_seq(palist,x));
    printf("    
");
    return 1;
}

/**
 * 7.        
 * @param palist
 * @param data
 */
void initData(PSeqList palist,int data[]){
    for(int i=0;i<11;i++)
    {
        palist->vals[i] = data[i];
        (palist->n)++;
    }
}

/**
 * 8.       
 * @param palist
 */
void printSeqList(PSeqList palist){
    if(isNullList_Seq(palist)){
        printf("     ，    
");
        return;
    }
    for(int i=0;i<palist->n;i++){
        printf("%d,",palist->vals[i]);
    }
    printf("
");
}


void Josephus(PSeqList palist,int s,int m){
    int s1,i,w;
    s1 = s - 1;
    for(i=palist->n;i>0;i--){
        s1 = (s1 + m - 1) % i;
        w = palist->vals[s1];
        printf(" %d   ；",w);
        deleteP_seq(palist,s1);
    }
}

int main(){
    int man[] = {1,2,3,4,5,6,7,8,9,10,11};
    PSeqList palist = createNullList_Seq(100);
    initData(palist,man);
    Josephus(palist,4,4);
}

비판 과 시정 을 환영 합 니 다.