제2 장 선형 표

제2 장 선형 표
앞 에 쓰 면 코드 를 쓰 는 것 이 시 를 쓰 는 것 과 같 습 니 다. 데이터 구 조 는 당시 300 수 와 같 습 니 다. 숙독 하고 외 워 쓰 는 것 이 기본 적 인 기능 이기 때문에 한가 할 때 종이 에 많이 쓸 수 있 습 니 다.
대강

선형 표 의 정의 와 기본 조작

선형 표 의 실현 2.1 순서 저장 구조 2.2 체인 식 저장 구조 2.3 선형 표 의 응용

2.1 선형 표 의 기본 개념 과 실현
1. 선형 표 의 논리 적 특성 은 하나의 표 두 요소 만 있 고 하나의 표 미 요소 만 있 으 며 표 두 요 소 는 전구 가 없고 표 미 요 소 는 후계 요소 가 없 으 며 다른 것 은 하나의 전구 와 후계 요소 만 있다.2. 선형 표 의 저장 구 조 는 저장 소 를 찾 습 니 다. 순서 표 체인 식 저장 소: 링크 2.1 순서 표 순서 표 는 선형 표 의 모든 요소 가 논리 적 인 순서에 따라 지 정 된 위치 에서 시 작 된 연속 적 인 저장 공간 에 순서대로 저장 하 는 것 입 니 다.2.2 링크 는 링크 저장 에 있어 모든 노드 는 저 장 된 요소 자체 의 정 보 를 포함 할 뿐만 아니 라 요소 간 의 논리 적 관계 정보 도 포함한다. 즉, 전구 노드 는 후계 노드 의 주소 정 보 를 포함한다.2.3 두 가지 비교 순서 표: 랜 덤 액세스, 정적 분배, 연속 저장 공간 링크 점용: 랜 덤 액세스, 동적 분배, 노드 저장 공간 이 용 률 이 순서 표 보다 낮은 순서 표 에 하나의 요 소 를 삽입 할 때 여러 요 소 를 이동 해 야 합 니 다.링크 가 요 소 를 삽입 할 때 요 소 를 이동 할 필요 가 없습니다.3. 링크 5 가지 형식 3.1 싱글 링크 선두 결점 의 head - > next = = NULL 링크 는 빈 앞장 이 없 는 노드 의 head = = NULL 링크 는 빈 3.2 더 블 링크 3.3 순환 싱글 링크 선두 결점 의 head - > next = = head 링크 는 빈 앞장 이 없 는 노드 의 head = = NULL 링크 는 빈 3.4 순환 더 블 링크 선두 결점 의 head - > ne 이다.xt = = = head & & head - > prior = = head 링크 가 비어 있 고 앞장 서지 않 는 노드 의 head = = NULL 링크 는 비어 있 습 니 다 3.4 정적 링크 입 니 다.
2.2 선형 표 의 기본 조작
2.2.1 선형 표 의 정의
같은 특성 을 가 진 데이터 요소 의 유한 한 서열시퀀스 에 포 함 된 요소 개 수 를 선형 표 의 길이 라 고 합 니 다.
2.2.2 선형 표 의 구조 정의
#define maxSize 100
1. 순서 표 의 구조 정의
typedef struct{ int data[maxSize]; int length; }Sqlist;
약자
int A[maxSize]; int n;
2. 단일 체인 표 노드 정의
typedef struct LNode{ int data; struct LNode * next; }LNode;
3. 더 블 링크 노드 의 정의
typedef struct DLNode{ int data; struct DLNode * prior; struct DLNode * next; }DLNode;
2.2.3 순서 표 의 알고리즘 조작
1. 포 지 셔 닝 x

int locateElem(Sqlist L,int x){
    for(int i=1;i<=L.length;i++)
        if(x<L.data[i]){
            return i;
        }
    return i;
}

2. 요소 삽입 x

void insert(Sqlist &L,int x){
    int p = locateElem(x);
    //     
    for(int i=L.length;i>=p;i--){
        data[i+1] = data[i];
    }
    L.data[p]=x;
    ++L.length;
}

3. 순서 표 L 에서 p 로 표 시 된 요 소 를 삭제 하고 요소 할당 을 e 에 게 삭제 합 니 다.

int listDelete(Sqlist &L,int p,int &e){
    if(p<1||p>L.length) return 0;
    e=L.data[p];
    for(int i=p;i<=L.length;i++)
        L.data[i] = L.data[i+1];
    --L.length;
    return 1;
}

4. 순서 표 초기 화

void InitList(Sqlist &L){
    L.length = 0;
}

5 、 L 이 지정 한 위치 p 의 요 소 를 e 로 되 돌려 줍 니 다.

int GetElem(Sqlist L,int p,int &e){
    if(p<1||p>L.length) return 0;
    e=L.data[p];
    return 1;
}

2.2.4 단일 체인 표 의 알고리즘 조작
1. A, B 두 개의 선도 적 인 노드 가 있 는 질서 있 는 단일 체인 표 는 A 와 B 를 비 체감 질서 있 는 단일 체인 표 C 로 합 친다.

void merge(LNode *&A,LNode *&B,LNode *&C){
    LNode *p=A->next; //  A B           
    LNode *q=B->next;
    C=A;
    C->next=NULL;  //   A              
    LNode *r=C;
    free(B);
    while(p!=NULL&&q!=NULL){
        if(p->data < q->data){
            r->next=p;
            p=p->next;
            r=r->next;
        }
        else{
            r->next=q;
            q=q->next;
            r=r->next;
        }
    }
    r->next=NULL; //
    if(p!=NULL) r->next=p;
    if(q!=NULL) r->next=q;
}

2. 꼬리 삽입 법 으로 링크 만 들 기

void CreatListR(LNode *&C,int a[],int n){
    LNode *r,*s;
    C=(LNode *)malloc(sizeof(LNode));
    C->next=NULL;
    r=C; //r     C
    for(int i=0;i<n;i++){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=a[i];
        r->next=s;
        r=r->next;
    }
    r->next=NULL;
}

3. 헤드 삽입 법 으로 링크 만 들 기

void CreatListF(LNode *&C,int a[],int n){
    LNode *s;
    C=(LNode *)malloc(sizeof(LNode));
    C->next=NULL;
    for(int i=0;i<n;i++){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=a[i];
        s->next=C->next;
        C->next=s;
    }
}

헤드 삽입 법 이 마지막 으로 얻 은 링크 순서 와 원래 배열 의 순 서 는 반대 이다.
4. 이전의 링크 를 점차적으로 줄 이 고 질서 있 는 링크 로 합 친다.
헤드 삽입 법 을 사용 하면 실현 할 수 있다.

void merge(LNode *&A,LNode *&B,LNode *&C){
    LNode *p=A->next;
    LNode *q=B->next;
    LNode *s;
    C=A;
    C->next=NULL;
    free(B);
    while(p!=NULL&&q!=NULL){
        if(p->data > q->data){
            s=p;
            p=p->next;
            s->next=c->next;
            c->next=s;  //C       ，          s
        }else{
            s=q;
            q=q->next;
            q->next=c->next;
            c->next=s;
        }
    }
    while(p!=NULL){
        s=p;
        p=p->next;
        s->next=c->next;
        c->next=s;
    }
    while(q!=NULL){
        s=q;
        q=q->next;
        s->next=c->next;
        c->next=s;
    }
}

5. 노드 삽입 - > a - > b 노드 삽입 s

s->next = a->next;
a->next = s;

6 、 결점 하나 삭제 - > a - > b

q=a->next;  // q  b,               
a->next=a->next->next;
free(q);

7. 링크 C (선두 노드) 에 x 의 요소 가 있 는 지 찾 습 니 다. 존재 하면 이 노드 를 삭제 하고 1 을 되 돌려 줍 니 다.

int SearchAndDelete(LNonde *&C, int x){
    LNode *p,*q;
    p=C;  //  p    C   C->next,                           
    //    
    while(p->next!=NULL){
        if(p->next->data==x){
            break;
        }
        p=p->next; //  p
    }


    if(p->next==NULL){
        return 0;
    }
    else{
        q=p->next; //q         
        p->next = p->next->next;
        free(q);
        return 1;
    }
}

2.2.5 쌍 련 표 의 알고리즘 조작
1. 꼬리 삽입 법 으로 더 블 링크 만 들 기

void CreatDlistR(DLNode *&L,int a[],int n){
    DLNode *s,*r;
    L=(DLNode *)malloc(sizeof(DLNode));
    L->next=NULL;
    r=L;
    for(int i=0;i<n;i++){
        s=(DLNode *)malloc(sizeof(DLNode));
        s->data=a[i];
        r->next=s;
        s->prior=r; //            prior  ，      next  
        r=s;
    }
    r->next=NULL;
}

2. 결점 값 이 x 인 결점 을 찾 습 니 다. 결점 반환 포인터 가 존재 합 니 다. 그렇지 않 으 면 NULL 로 돌아 갑 니 다.

DLNode* Search(DLNode *C,int x){
    DLNode *p =C->next;
    while(p!=NULL){
        if(p->data==x){
            break;
        }
        p=p->next;
    }
    return p; //               p,       ，    while   p   NULL
}

3, 삽입점 알고리즘 p < - > q 삽입점 s

s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

4. p 결점 을 삭제 한 후계 결점 알고리즘 p < - >

q=p->next;
p->next = q->next;
q->next->prior = p;
free(q);

2.2.6 순환 더 블 링크 의 알고리즘 작업
p 포인터 가 순환 링크 를 따라 표 끝까지 가 는 조건 을 판단 하 는 것 은 p - > next = = head 이다.