왕도 데이터 구조 링크 연습 문제 실현 (지속 업데이트)

1. 링크 정의 및 기본 동작

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode, *LinkList;

//     
void printLinkList(LinkList L){
    LNode *p = L->next;
    while(p!= nullptr){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("
");
}
//        
void createLinkList(LinkList &L){
    LNode *p;int x;
    scanf("%d",&x);
    while(x!=11){
        p = (LNode *) malloc(sizeof(LNode));
        p->data = x;
        p->next = L->next;
        L->next = p;
        scanf("%d",&x);
    }
}
//      
void InitLinkList(LinkList &L){
    L = (LinkList) malloc (sizeof(LNode));
    L ->next = nullptr;
}

첫 번 째 문제: 재 귀 알고리즘 을 설계 하여 앞장 서지 않 는 노드 의 단일 체인 테이블 L 의 모든 값 이 x 인 노드 를 삭제 합 니 다.

//1.          x      ，               
//             
void test1(LinkList &L,int x){
    LNode *p ;
    if(L== nullptr){
        return ;
    }
    if(L->data==x){
        p = L;
        L = L ->next;
        free(p);
        test1(L,x);
    }else
        test1(L->next,x);
}

두 번 째 문제: 선두 노드 의 단일 체인 표 에서 모든 값 이 x 인 노드 를 삭제 하고 그 공간 을 방출 합 니 다. 값 이 x 인 노드 가 유일 하지 않다 고 가정 하고 알고리즘 을 만들어 상기 작업 을 실현 합 니 다.

void test2(LinkList &L,int x){
    LNode *p = L;LNode *q = L->next;
    LNode * f;
    while(q!= nullptr){
        if(q->data == x){
            f = q;
            q = q -> next;
            p ->next = q;
            free(f);
        }else{
            p = q;
            q = q->next;
        }
    }
}

세 번 째 문제: L 을 선두 노드 의 단일 체인 표 로 설정 하고 알고리즘 을 작성 하여 각 노드 의 값 을 끝 에서 끝까지 역방향 으로 출력 합 니 다.

void test3(LinkList L){
    if(L->next!= nullptr) test3(L->next);
    if(L!= nullptr) printf("%d ",L->data);
}

네 번 째 문제: 선두 노드 의 단일 체인 테이블 L 에서 최소 값 의 효율 적 인 알고리즘 을 삭제 합 니 다. (최소 값 노드 가 유일 하 다 고 가정 합 니 다.)

void test4(LinkList &L){
    LNode *p = L; LNode *q = L->next;
    LNode *minptr; int min = q->data;
    while(q->next!= nullptr){
        p = q;
        q = q->next;
        if(q->datadata;
            minptr = p;
        }
    }
    minptr->next = minptr->next->next;
}

다섯 번 째 문제: 알고리즘 을 시험 적 으로 작성 하여 선두 노드 의 단일 체인 표를 그 자리 에서 역 설정 하고 공간 복잡 도 요구 o (1)

void test5(LinkList &L){
    LNode *p = L;
    LNode *q = p->next;
    L->next = nullptr;
    while(q!= nullptr){
        p = q;
        q = q ->next;
        p->next = L->next;
        L->next = p;
    }
}

여섯 번 째 문제: 선두 노드 의 단일 체인 표 L 이 있 고 하나의 알고리즘 을 디자인 하여 요 소 를 질서 있 게 한다.

//  :            o(n2)
void test6(LinkList &L){
    if(L->next== nullptr) return;
    LNode *p = L->next; LNode *q = p->next;
    p->next = nullptr;
    //   q              
    LNode *r; LNode *pre;
    while(q!= nullptr){
        r = q->next;
        //      
        pre = L;
        while(pre->next!= nullptr&&pre->next->data<=q->data){
            pre = pre->next;
        }
        //pre      
        q->next = pre->next;
        pre->next = q;
        q = r;
    }
}

일곱 번 째 문제: 표 두 노드 가 있 는 단일 체인 표 에 설 치 된 모든 요소 노드 의 데이터 값 이 무질서 합 니 다. 함 수 를 작성 하여 표 에 있 는 두 값 사이 에 있 는 모든 요 소 를 삭제 합 니 다.

void test7(LinkList &L,int a,int b){
    LNode *p = L;LNode *q = L->next;
    LNode *f;
    while(q!= nullptr){
        if(q->data>a&&q->datanext = q->next;
            free(f);
            q = p->next;
        }else {
            p = q;
            q = q->next;
        }
    }
}

여덟 번 째 문제: 두 개의 단일 체인 표를 정 하고 알고리즘 을 작성 하여 두 개의 체인 표 의 공공 노드 를 찾 습 니 다.

사고방식: A, B 체인 시 계 를 동시에 옮 겨 다 닌 다. 만약 에 A 체인 시계 가 옮 겨 다 닌 후에 B 체인 시계 에서 옮 겨 다 닌 다 면 B 체인 시계 가 옮 겨 다 닌 후에 A 체인 시계 에서 두 개의 체인 시 계 를 옮 겨 다 니 면 반드시 공공 노드 에서 교차한다

LNode * test8(LinkList &headA,LinkList &headB ){
    auto p = headA, q = headB;
    while(p != q) {
        if(p) p = p->next;
        else p = headB;
        if (q) q = q->next;
        else q = headA;
    }
    return p;
}

미 완성 지속 업데이트!