왕도 데이터 구조 (링크)

링크 정의

typdef struct Node{
    ElemType     data;
    struct Node  *next;
}Node,*LinkList;

1. 앞장 서지 않 는 점 을 삭제 하 는 싱글 체인 시트 의 중간 값 이 x 인 점 을 재 귀적 으로 사용 합 니 다.

void delX（LinkList &L,ElemType x){
    Node *p;
   if(L==null)    return ;
    if(L->data==x){
        p=L;
        L=L->next;
        free(p);    
        delX(L,x);
    }
    else
        delX(L->next,x);
}

2. 앞장 서 는 노드 의 단일 링크 에서 x 의 노드 를 삭제 합 니 다.

void delX(LinkList &L,ElemType x){
    Node *p=L->next,*pre=L,*q;
    while(p!=null){
            if(p->data!=x){
                    pre=p;
                    p=p->next;
           }
            else{
                   q=p;
                   p=p->next;
                   pre->next=p;
                   free(q);
                }
        }
}

3. 끝 에서 끝까지 역수출 선두 결점 의 단일 체인 표 각 결점 의 값

void reversePrint(LinkList &L){
    while(L->next!=null)
        reversePrint(L->next);
    printf(L->data);
}

4. 선두 노드 의 단일 체인 테이블 에서 최소 값 의 노드 삭제 (유일)

LinkList delMinNode(LinkList &L){
    Node *pre=L,*p=pre->next;
    Node *minpre=pre,*minp=p;
    while(p!=null){
        if(p->datadata){
               minp=p;
               minpre=pre;
          }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
    return L;
}

5. 앞장 서 는 결점 의 단일 체인 시 계 를 그 자리 에서 거꾸로 놓는다. 즉, 공간 복잡 도 는 O1 이다.

Linklist reverse(LinkList L){
    Node *p,*r;
    p=L->next;
    L->next=null;
    while(P!=null){
    r=p->next;
    p->next=L->next;
    L->next=p;
    p=r;
    }
    return L;
}

6. 앞장 서 는 결점 의 단일 체인 표 요 소 를 증가 시킨다.

void sort(LinkList &L){
    Node *p=L->next,*pre;
    Node *r=p->next;
    p->next=null;
    p=r;
    while(p!=null){
        r=p->next;
        pre=L;
        while(pre->next!=null&&pre->next->datadata)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
      }
}

7. 무질서 한 선두 결점 의 단일 체인 테이블 에서 s, t 사이 의 결점 삭제

void rangeDel(LinkList &L,int min,int max){
    Node *pr=L,*p=->next;
    while(p!=null){
        if(p->data>min&&p->datanext=p->next;
            free(p);
            p=pr->next;
           }
        else{
            pr=p;
            p=p->next;
           }
    }
}

8. 두 개의 단일 체인 시트 의 공공 결산 점 을 찾는다.
 

LinkList searchSame(LinkList L1,LinkList L2){
    int len1=Length(L1),len2=Length(L2);
    LinkList longList,shortList;
    if(len1>len2){
        longList=L1->next;
        shortList=L2->next;
        len=le1-len2;
        }
    else{
        longList=L2->next;
        shortList=L1->next;
        len=le2-len1;
        }
    while(len--)
        longList=longList->next;
    while(longList!=null){
        if(longList==shortList)
            return longList;
        else{
            longList=longList->next;
            shortList=shortList->next;
        }
    }
    return null;
}

9. 선두 결점 을 가 진 단일 체인 표를 지정 하고 head 를 헤드 포인터 로 설정 하 며 증가 순서에 따라 링크 의 각 노드 의 데이터 요 소 를 출력 하고 저장 공간 을 방출 합 니 다 (배열 을 보조 공간 으로 사용 할 수 없습니다)

void min_del(LinkList &head){
    while(head->next!=null){
        Node *pre=head;
        Node *p=pre->next;
        while(p->next!=null){
            if(p->next->datanext->data)
                pre=p;
            p=p->next;
         }
        printf(pre->next->data);
        Node *u=pre->next;
        pre->next=u->next;
        free(u);
      }
    free(head);
}    

10. 선두 결점 을 가 진 단일 체인 표 A 를 두 개의 단일 체인 표 AB 로 분해 하 는데 그 중에서 A 에는 원래 표 의 번호 가 홀수 인 요소 B 에 짝수 요 소 를 포함 하고 상대 적 인 순서 가 변 하지 않 는 다.

LinkList disCreat(LinkList &A){
    int i=0;
    B=(LinkList)malloc(sizeof(LinkList));
    B->next=null;
    Node *ra=A,*rb=B;                //ra,rb         AB      
    
    Node *p=A->next;
    A->next=null;                    //  A
    while(p!=null){
        i++;
        if(i%2==0){
            rb->next=p;
            rb=p;
            }
        else{
            ra->next=p;
            ra=p;
           }
        p=p->next;
    }
    ra->next=null;
    rb->next=null;
    return B;
}

11. C = {a1, b1, a2,... an, bn} 을 선형 표 로 설정 합 니 다.선두 노드 의 단일 체인 시트 로 저장 하고 A = {a1... an}, B = {b1,... bn} 으로 나 눕 니 다.

LinkList disCreat(LinkList &C){
    LinkList A=(LinkList)malloc(sizeof(Node));
    LinkList B=(LinkList)malloc(sizeof(Node));
    A->next=null;
    B->next=null;
    Node *p=C->next,*q;
    Ndde *ra=A;
    while(p!=null){
        ra->next=p;
        ra=p;
        p=p->next;
        q=p->next;
        p->next=B->next;
        B->next=p;
        p=q;
    }
    ra->next=null;
    return A,B;
}

12. 질서 있 는 선형 표 에 수치 가 같은 요소 가 존재 한다. 만약 에 저장 방식 이 단일 체인 표 라면 수치 가 같은 요 소 를 제거 하여 표 의 요 소 를 중복 하지 않도록 한다.

void delSame(LinkList &L){
    Node *p=L->next,*q;
    if(p==null)        return ;
    while(p->next!=null){
            q=p->next;
            if(p->data==q->data){
                  p->next=q->next;
                  free(q);
               }
            else
                p=p->next;
        }
}

13. 요소 값 의 증가 순서에 따라 배 열 된 선형 표 가 두 개 있다 고 가정 하면 모두 단일 체인 표 형식 으로 저장 된다.현 재 는 두 개의 단일 체인 표를 원소 값 의 체감 순서에 따라 배 열 된 단일 체인 표 로 병합 하고 원래 두 개의 단일 체인 표 의 결점 을 이용 하여 귀 합 된 단일 체인 표를 저장 해 야 한다.

void mergeLink(LinkList &A,LinkList &B){
    Node *r,*pa=A->next,*pb=B->next;
    A->next=null;
    while(pa&&pb){
        if(pa->data<=pb->data){
            r=pa->next;
            pa->next=A->next;
            A->next=pa;
            
            pa=r;
        }
        else{
            r=pb->next;
            pb->next=B->next;
            B->next=pb;
            
            pb=r;
            }
   if(pa)
         pb=pa;
   while(pb!=null){
            r=pb->next;
            pb->next=A->next;
            A->next=pb;
            pb=r;
        }
    free(pb);
}

14. A 와 B 는 두 개의 단일 체인 표 로 그 요소 가 점점 질서 가 있 고 AB 에서 공공 요소 가 단일 체인 표 C 를 형성 하 며 A, B 의 결점 을 파괴 해 서 는 안 된다.

LinkList findSame(LinkList &A,LinkList &B){
    Node *p=A->next,*q=B->next,*r,*s;
    LinkList C=(LinkList)malloc(sizeof(Node);
    r=C;
    while(p!=null&&q!=null){
        if(p->datadata)
           p=p->next;
        else if(p->data>q->data)
          q=q->next;
        else{
          s=(Node)malloc(sizeof(Node));
          s->data=p->data;
          r->next=s;
          r=s;
          p=p->next;
          q=q->next;
        }
       }
    r->next=null;
}        

15. l 링크 A, B 는 각각 두 개의 집합 을 나타 내 는데 그 요소 가 점점 증가 하고 배열 되 며 A ∩ B 를 구하 고 A 링크 에 저장 합 니 다.

LinkList Un(LinkList &A,LinkList &B){
    Node *pa=A->next,*pb=B->next,*pc=A,*q;
    while(pa&&pb){
        if(pa->data==pb->data){
             pc->next=pa;
             pc=pa;
             pa=pa->next;
             q=pb;
             pb=pb->next;
             free(q);
            }
         else if(pa->datadata){
             q=pa;
             pa=pa->next;
             free(q);
            }
         else{ 
             q=pb;
             pb=pb->next;
             free(q);
            }
    if(pa)
        pb=pa;
    while(pb){
            q=pb;
            pb=pb->next;
            free(q);
            }
    pc->next=null;
    free(B);
    return A;
}

16. 두 정수 서열, A = a1,... am;B=b1...bn;이미 두 개의 링크 에 저장 되 어 B 가 A 의 하위 열 인지 아 닌 지 를 판단 합 니 다.

bool isChild(LinkList &A,LinkList &B){
    Node *p=A,*pre=p,*q=B;
    if(Linklength(A)data==pb->data){
            pa=pa->next;
            pb=pb->next;
        }
        else {
            pre=pre->nextx;
            p=pre;
            q=B;
          }
     if(q=null)
            return true;
      else
            return false;
 }