선형 표 의 체인 표시 - 데이터 구조

순서 구조 에 존재 하 는 첨삭 이 어렵 고 다른 조작 도 비교적 불편 한 원인 은 구 조 를 더욱 유연 하고 변화 가 많 으 며 저장 공간 을 충분히 이용 하기 위해 링크 가 생 겼 다.
  체인 구조 에서 순서 구조 와 달리 저장 위치 상의 관 계 를 통 해 논리 적 인 관 계 를 나타 내 고 체인 구조 에서 '화살표' - 지침, 안 내 를 통 해 상호 관 계 를 나타 낸다.
  따라서 링크 에서 모든 데 이 터 를 두 부분 으로 나 누 었 습 니 다. 본 생 의 데이터 부분 (데이터 도 메 인) 과 상호 관계 하 는 부분 인 지침 도 메 인 입 니 다.
C 언어의 구조 체 는 다음 과 같다.
                                

typedef struct LNode{
            ElemType  data;
            struct   LNode   *next;
}

이 구조의 대략적인 저장 구 조 는 검색 데 이 터 를 통 해 분석 합 니 다.

Status GetElem_L(LinkList L,int i;ElemType &e)
{
       p=L->next;
       j=1;
       while(p&&jnext;
               j++;
         }
         e=p->data;
} 



             

이 예 에서 지침 의 '유도' 를 통 해 데이터 간 의 관 계 를 실현 했다.
순서 표 의 증가 와 삭 제 를 구별 합 니 다. 링크 관계 에 지침 역 이 연결 되 어 있 기 때문에 관 계 를 바 꿀 때 지침 의 '안내' 만 바 꾸 면 됩 니 다.
데이터 추가:
주요 한 절 차 는 이 표 에 위 치 를 추가 하 는 앞의 결점 의 '지향' 과 결점 을 추가 하 는 지향 이다.쇠사슬 에 있 는 2 의 '구멍' 만 바 꾸 는 것 과 비슷 하지만 다른 결점 은 바 꿀 필요 가 없다.
4. 567913. 최종 적 으로 실현 되 는 것 은 포인터 가 추가 해 야 할 위 치 를 가리 키 도록 옮 겨 다 니 며 새로운 노드 를 만 드 는 것 이다.

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

삭제 와 마찬가지 로 free () 를 통 해 삭 제 된 노드 를 풀 어야 합 니 다.

Status ListInsert(LinkList& L,int i;ElemType e){
for(p=L,j=0;p&&jnext;
}
s=(ElemType*)malloc(ElemType);
s->data=e;
s->next=p->next;
p->next=s;
return ok；
}

종합 운용 은 2 개의 링크 의 합병 이다.
알고리즘 사상 은 앞의 절 과 일치 하 는데 마지막 에 남 은 부분 링크 에서 더욱 간편 해 졌 다.

Status Linkdelete(LinkList &L,int i;ElemType &e){
for(p=L,j=0;p&&jnext;
}
q=p->next;
p->next=p->next->next;
e=q->data;
free(q);
return ok;
}

이상 은 동적 링크 의 구축 이지 만 링크 의 본질은 하나의 지침 도 메 인 을 더 해서 논리 적 관 계 를 나타 내 는 것 이다. 저장 위치 상의 관계 로 표시 하 는 것 이 아니 라 똑 같은 배열 유형 을 통 해 '지침' 을 추가 하여 상호 간 의 관 계 를 나타 내 는 것 을 알 수 있다. 이것 이 바로 정적 링크 이다.
새 클래스 를 만 드 는 것 입 니 다:

void mergeList(Linklist& L1,LinkList& L2,LinkList& L3){
         pa=L1->next;
         pb=L2->next;
         pc=L3=L1;
         while(p1&&p2)
         {
                 if(p1->data<=p2->data) 
                  {
                       p3->next=p1;
                       p3=p1;
                       p1=p1->next;
                   }
                  else{
                  p3->next=p2;
                  p3=p2;
                  p2=p2->next;
                  }
            if(pa)
              p3->next=p1;
            if(pb)   p3->next=p2;
}
                       

그 중의 cur 는 배열 의 '점' 의 다음 '점' 의 위 치 를 대표 한다.
데 이 터 를 추가 삭제 할 때 링크 와 같 고 '결점' 의 '지침' 을 바 꾸 면 된다.
데이터 조회 에서 링크 처럼 보이 지만 실제 조회 순 서 는 배열 의 저장 순서 에 따라 조회 합 니 다.

typedef struct{
           ElemType  data;//  
            int    cur;//     
}

링크 와 의 차 이 는 첨삭 에서 의 개척 과 방출 은 시스템 이 제공 하 는 함수 가 없 으 므 로 스스로 구축 해 야 한 다 는 것 이다.
만 드 는 방법 은 '쓰레기 창고' 를 만 드 는 것 이다. 삭제 한 수 는 이 쓰레기 창고 에 넣 고 필요 한 수 는 그것 을 꺼 내 는 것 이다.본질은 바로 예비 체인 표를 세 우 는 것 이다.
구체 적 인 절 차 는 3 단계: 1. 공간의 데 이 터 를 정적 링크 로 초기 화 합 니 다.2. 예비 공간 을 만 들 면 노드 를 얻 을 수 있 습 니 다.3. 노드 를 예비 링크 에 연결 합 니 다.
첫 번 째 단계 - 정적 링크 초기 화:

int LocateElem(SlinkList S,ElemType e){
i=S[0].cur;//i        
while(i&&S[i].data!=e){
i=S[i].cur;
}
return i;
}

두 번 째 단계 - 예비 공간 에서 하나의 결점 을 얻는다.
세 번 째 -- 링크
직접 (A - B) 와 (B - A) 를 예 로 들 면.

void InitSpace(SLinklist &space){
for(i=0;i