제1장 제2 절 연습 문제 20 연결 두 순환 단일 체인 표

문제 설명
두 개의 순환 싱글 체인 시트 가 있 습 니 다. 링크 헤드 포인 터 는 각각 h1 과 h2 입 니 다. 하나의 함 수 를 작성 하여 링크 h2 를 링크 h1 에 연결 한 후에 링크 뒤의 링크 는 순환 링크 형식 을 유지 하도록 요구 합 니 다.
알고리즘 사상
이것 은 두 개의 순환 단일 체인 표 이기 때문에 그것들 을 연결 하여 새로운 순환 단일 체인 표를 형성 하 는 것 만 고려 하면 된다.그러면 우 리 는 먼저 첫 번 째 순환 단일 체인 표 h1 의 끝 점 을 찾 은 다음 에 next 도 메 인 이 다른 순환 단일 체인 표 h2 의 첫 번 째 데이터 도 메 인 을 가 진 결점 (즉, 머리 노드 의 next 도 메 인 이 가리 키 는 그 결점) 을 가리 키 게 한다. 이때 순환 단일 체인 표 h2 의 머리 노드 를 방출 할 수 있다.마지막 으로 순환 싱글 체인 표 h2 의 끝 점 을 찾 아 next 도 메 인 으로 하여 금 순환 싱글 체인 표 h1 의 두 절 점 을 다시 가리 키 게 하면 됩 니 다.이렇게 해서 두 개의 순환 단일 체인 표를 연결 시 켜 하나의 순환 단일 체인 표를 형성 했다.
알고리즘 설명

//       “      ”
LNode* FindRear(LNode *head)
{
    LNode *p=head->next;
    while(p->next!=head){
        p=p->next;  
    }
    return p;
}
//         
LinkList Connect(LNode *head1, LNode *head2)
{
    LNode *r1=FindRear(head1);
    LNode *r2=FindRear(head2);
    LNode *p=head2->next;

    r1->next=p;
    free(head2);
    r2->next=head1;

    return head1;
}

구체 적 인 코드 는 첨부 파일 참조.
첨부 파일

#include<stdio.h>
#include<stdlib.h>

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

LinkList CreatList(LNode*);
LinkList Connect(LNode*, LNode*);
LNode* FindRear(LNode*);
void Print(LNode*);

int main(int argc,char* argv[])
{
    LNode *head1;
    head1=(LNode*)malloc(sizeof(LNode));
    head1=CreatList(head1);

    LNode *head2;
    head2=(LNode*)malloc(sizeof(LNode));
    head2=CreatList(head2);

    Print(head1);
    Print(head2);

    head1=Connect(head1, head2);

    Print(head1);

    return 0;
}
//          
LinkList CreatList(LNode *head)
{
    LNode *L;
    LNode *r=head;
    ElemType x;
    scanf("%d",&x);
    while(x!=999){
        L=(LNode*)malloc(sizeof(LNode));
        L->data=x;
        r->next=L;
        r=L;
        scanf("%d",&x);
    }
    r->next=head;
    return head;
}
//            
LinkList Connect(LNode *head1, LNode *head2)
{
    LNode *r1=FindRear(head1);
    LNode *r2=FindRear(head2);
    LNode *p=head2->next;

    r1->next=p;
    free(head2);
    r2->next=head1;

    return head1;
}
//        
LNode* FindRear(LNode *head)
{
    LNode *p=head->next;
    while(p->next!=head){
        p=p->next;  
    }
    return p;
}
//      
void Print(LNode *head)
{
    LNode *p=head->next;
    while(p!=head){
        printf("%4d",p->data);
        p=p->next;
    }
    printf("
");
}