[데이터 구조] 헤드 노드 를 포함 한 단일 체인 표

18819 단어 shujujiegou
  • 단일 체인 표 구조 체
  • 헤드 삽입 법 구축 싱글 체인 표
  • 꼬리 삽입 법 구축 싱글 체인 표
  • 링크 를 옮 겨 다 니 기
  • 두 개의 링크 를 직접 합병
  • 질서 있 는 링크 합병
  • 단일 체인 표 에 위 치 를 정 하고 요 소 를 삽입 합 니 다
  • 주 함수 호출
  • 목차
  • 목록
  • 부분 별 실현
  • 단일 체인 표 구조 체
  • 헤드 삽입 법 구축 싱글 체인 표:
  • 꼬리 삽입 법 구축 싱글 체인 표
  • 링크 를 옮 겨 다 니 기
  • 두 개의 링크 를 직접 합병
  • 질서 있 는 링크 합병
  • 단일 체인 표 에 위 치 를 정 하고 요 소 를 삽입 합 니 다
  • 주 함수 호출
  • 모든 코드

  • 각 부분 실현
    싱글 체인 테이블 구조 체
    typedef struct tagNode
    {
        int data;//   
        struct tagNode *next;//   ,       
    }Node,*LinkList;/*LinkList       */

    헤드 삽입 법 구축 싱글 체인 시트:
    L 은 선두 결점 을 가 진 빈 사슬 시계 헤드 포인터 이 고 n 은 단일 사슬 표 에 입력 할 요소 갯 수 입 니 다.L - > next 는 항상 단일 체인 시트 의 첫 번 째 요 소 를 가리 키 며 처음에는 빈 곳 을 가리 키 고 있 습 니 다.헤드 삽입 법 을 사용 하려 면 삽입 할 요 소 를 새로운 노드 저장 소 를 만 들 고 L - > next 가 가리 키 는 노드 를 s - > next 에 부여 해 야 합 니 다. 마지막 으로 L - > next 가 새로 삽 입 된 노드 s 를 가리 키 면 헤드 삽입 법 이 완 료 됩 니 다.
    void CreateHeadList(LinkList L,int n)//   
    {
        LinkList s;
        while(n--)
        {
            s=(LinkList)malloc(sizeof(Node));/*     */
            scanf("%d",&s->data);
            s->next=L->next;/*                     ,    */
            L->next=s;
        }
    }
    

    꼬리 삽입 법 구축 싱글 체인 시트
    L 은 선두 결점 을 가 진 빈 사슬 시계 헤드 포인터 이 고 n 은 단일 사슬 표 에 입력 할 요소 갯 수 입 니 다.꼬리 삽입 법 을 실현 하려 면 구조 체 포인터 p 가 링크 의 마지막 요 소 를 항상 가리 키 고 링크 에 요 소 를 사용 하지 않 을 때 머리 결 점 을 가리 키 는 것 을 정의 해 야 합 니 다.매번 삽입 할 때마다 삽입 할 새로운 노드 저장 소 를 만 듭 니 다.p - > next 로 하여 금 새로 만 든 결점 을 가리 키 게 하면 끝 삽입 법 이 완성 되 고 마지막 으로 포인터 p 로 하여 금 새로운 마지막 결점 을 가리 키 게 합 니 다.
    void CreateTailList(LinkList L,int n)//   
    {
        LinkList p,s;
        p=L;/*     p     */
        while(n--)
        {
            s=(LinkList)malloc(sizeof(Node));
            scanf("%d",&s->data);
            p->next=s,p=s;/*    */
        }
        p->next=NULL;/*             */
    }

    링크
    끝 점 이 비어 있 을 때 까지 처음부터 포인터 의 다음 노드 를 옮 겨 다 니 기 시작 합 니 다.
    void ListTraverse(LinkList L)//    
    {
        LinkList p=L->next;/*         ,        ,   
                    */
        while(p)/*        */
        {
            printf("%d ",p->data);
            p=p->next;/*      */
        }
        printf("
    "
    ); }

    두 개의 링크 를 직접 병합 하 다.
    두 개의 단일 체인 테이블 L, O 는 먼저 체인 테이블 L 의 마지막 결점 을 찾 아서 이 결점 의 지침 역 이 체인 테이블 O 의 머리 결점 후의 첫 번 째 결점 을 가리 키 게 하면 합병 을 완성 할 수 있다.
    void ListContact1(LinkList L,LinkList O)
    {
        LinkList p=L;
        while(p->next)
        {
            p=p->next;
        }/*       */
        p->next=O->next;
    }

    병합 순서 링크
    두 개의 단일 체인 표 의 질서 있 는 선형 표 로 합병 하 는 방법 은 순서 표 가 합 쳐 진 홍보 이 고 꼬리 삽입 법 으로 합 쳐 진 링크 에 새로운 요 소 를 삽입 하 는 것 이다.
    void ListContact2(LinkList L,LinkList O,LinkList H)
    {
        LinkList l,o,h,s;
        l=L->next;
        o=O->next;
        h=H;/*     h          */
        while(l&&o)/* l  o    ,           ,    */
        {
            s=(LinkList)malloc(sizeof(Node));/*     */
            s->next=NULL;
            if(l->data<o->data)
            {
                s->data=l->data;
                l=l->next;
            }
            else
            {
                s->data=o->data;
                o=o->next;
            }
            h->next=s;/*        */
            h=s;
        }
        while(l)/*             */
        {
            s=(LinkList)malloc(sizeof(Node));
            s->next=NULL;
            s->data=l->data;
            h->next=s;
            h=s;
            l=l->next;
        }
        while(o)
        {
            s=(LinkList)malloc(sizeof(Node));
            s->next=NULL;
            s->data=o->data;
            h->next=s;
            h=s;
            o=o->next;
        }
    }
    

    단일 체인 시트 에 위 치 를 정 하고 요 소 를 삽입 합 니 다.
    void ListInsert(LinkList L,int i,int e)
    {
        LinkList p=L,s;
        while(p&&i>1)
        {
            p=p->next;
            i--;
        }
        s=(LinkList)malloc(sizeof(Node));
        s->data=e;
        s->next=p->next;
        p->next=s;
    }

    주 함수 호출
    int main()
    {
        int n,m,i,e;
        LinkList L,O,H;
        L=(LinkList)malloc(sizeof(Node));
        L->next=NULL;/*        */
        O=(LinkList)malloc(sizeof(Node));
        O->next=NULL;
        H=(LinkList)malloc(sizeof(Node));
        H->next=NULL;
        printf("      ,             ,             ,            ,            :");
        scanf("%d%d%d%d",&n,&m,&i,&e);//n  L   ,m  O   ,i        ,e        
        printf("       ,       :");
        CreateHeadList(L,n);//   
        ListTraverse(L);
        printf("       ,       :");
        CreateTailList(O,m);//   
        ListTraverse(O);
        ListContact2(L,O,H);
        ListTraverse(H);
        ListContact1(L,O);
        ListTraverse(L);
        ListInsert(H,i,e);
        ListTraverse(H);
        return 0;
    }

    모든 코드
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct tagNode
    {
        int data;
        struct tagNode *next;
    }Node,*LinkList;
    
    
    void CreateHeadList(LinkList L,int n)//   
    {
        LinkList s;
        while(n--)
        {
            s=(LinkList)malloc(sizeof(Node));
            scanf("%d",&s->data);
            s->next=L->next;
            L->next=s;
        }
    }
    
    void CreateTailList(LinkList L,int n)//   
    {
        LinkList p,s;
        p=L;
        while(n--)
        {
            s=(LinkList)malloc(sizeof(Node));
            scanf("%d",&s->data);
            p->next=s,p=s;
        }
        p->next=NULL;
    }
    
    void ListTraverse(LinkList L)//    
    {
        LinkList p=L->next;
        while(p)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("
    "
    ); } void ListContact1(LinkList L,LinkList O) { LinkList p=L; while(p->next) { p=p->next; } p->next=O->next; } void ListContact2(LinkList L,LinkList O,LinkList H) { LinkList l,o,h,s; l=L->next; o=O->next; h=H; while(l&&o) { s=(LinkList)malloc(sizeof(Node)); s->next=NULL; if(l->data<o->data) { s->data=l->data; l=l->next; } else { s->data=o->data; o=o->next; } h->next=s; h=s; } while(l) { s=(LinkList)malloc(sizeof(Node)); s->next=NULL; s->data=l->data; h->next=s; h=s; l=l->next; } while(o) { s=(LinkList)malloc(sizeof(Node)); s->next=NULL; s->data=o->data; h->next=s; h=s; o=o->next; } } void ListInsert(LinkList L,int i,int e) { LinkList p=L,s; while(p&&i>1) { p=p->next; i--; } s=(LinkList)malloc(sizeof(Node)); s->data=e; s->next=p->next; p->next=s; } int main() { int n,m,i,e; LinkList L,O,H; L=(LinkList)malloc(sizeof(Node)); L->next=NULL; O=(LinkList)malloc(sizeof(Node)); O->next=NULL; H=(LinkList)malloc(sizeof(Node)); H->next=NULL; printf(" , , , , :"); scanf("%d%d%d%d",&n,&m,&i,&e);//n L ,m O ,i ,e printf(" , :"); CreateHeadList(L,n);// ListTraverse(L); printf(" , :"); CreateTailList(O,m);// ListTraverse(O); ListContact2(L,O,H); ListTraverse(H); ListContact1(L,O); ListTraverse(L); ListInsert(H,i,e); ListTraverse(H); return 0; }

    좋은 웹페이지 즐겨찾기