18 대학원 진학 - 데이터 구조 복습 노트 - 선형 표 01

제2 장 선형 표 시험 강 요구: 1. 선형 표 의 정의 와 기본 조작 2. 선형 표 의 실현 (자주 명제 에서 크기 문제 가 모두 있 고 2 개 이상 의 알고리즘 디자인 문제 가 있 을 수 있다): 1. 순서 저장 2. 체인 식 저장 3. 선형 표 의 응용 본 장 시험 점: 1. 선형 표 의 논리 구조 2. 순서 저장 구조 3.체인 식 저장 구조 1. 단일 체인 표 2. 순환 링크, 양 방향 링크 3. 순서 표 와 링크 의 비교 (구체 적 인 문제 시 어떻게 선택 하 는 지)
1. 논리 구조 (제목 이 비교적 적 음) 1. 선형 구조의 기본 특징: 데이터 요소 의 질서 있 는 집합 (순서 가 있 음)

1)    “    ”；
2)    “    ”；
3)        “    ”；
4)        “    ”；

2. 추상 적 인 데이터 형식의 선형 표 정 의 는 다음 과 같다.

ADT list        
{
        ：
    D={Ai|}

        ：
    R1={Ai-1，Ai}
    {     （a1a2a3an   a      ）}

        ：
           /new
          /delete
         /use/ via address use
         /change data that was in i position
}ADT list

3. 구체 적 인 조작 1) 작업 Initlist (& L) crate a null line list 초기 화;2) 폐기 작업 DestroyList (& L) {If (! null List) destroy list;} 3) 참조 작업 a. ListEmpty (L) 에 요소 가 있 습 니까?b.ListLength(L) how much elements? c.PriorElem(L,cur_e,&pre_e) before element； d.NextElem(L,cur_e,&next_e) next element； e.GetElem(L,i,&e) get position i element; f.LocateElem(L,e,compare()) current elements same with e; g.ListTraverse(L,visit() ) visit every element of list L just once, which with some stable rule; 4) 가공 조작 a. ClearList (& L) set list L with null;b.PutList(&L,I,&e) put position i element; c.listInsert(&L,I,e)insert element e to position i of list L; d.Listdelete(&L,I,&e)delete element was in position i of list L; 4. 상기 기본 조작의 조합 을 이용 하여 더욱 복잡 한 조작 을 실현 할 수 있다.

For Instance 0：
Assume that： there have two sets A and B,called LA and LB,and now we need a new set A = AUB.
Transform :
find different LA with LB elements and insert into LA;
Analysis:
visit LA,LB, compare LA with LB,and insert into LA;
Operation:
a.Visit LB;  getElem(L,B,I)-e;
b.Compare elements of LB with LA;   locateElem(LA,e,compare());
c. if same,skip,else insert;        ListInsert(LA,n+1,e)

For instance 1:
    “              ”    LA LB，     LC        ；
Analysis：
    a.Init LC null;
    b.Get cur_e from LA and LB;
    c.If Ai <= Bj insert Ai into LC, else insert Bj;
    d.Until list over repeat step 23;
    e.Other elements via rule insert;
Code :
Void margeList(list La,list Lb,list &Lc)
{
Initlist(Lc);
I = j = 1; k=0;
La_len = listlength(La);
Lb_len = listlength(Lb);

While(i <= La_len &&j<=Lb_len)
While(j<=Lb_len)
{
Getelem(La,i,ai);
Getelem(Lb,j,bj);

If (ai <= bj)
{Listinsert(Lc,++k,ai);++i;}
Else
{Listinsert(Lc,++k,bj);++j;}
}

while (i <= La_len)
{
Getelem(La,i,ai);
Listinsert(Lc,++k,ai);++i;}
}
While(j<=Lb_len)
{
Getelem(Lb,j,bj);
Listinsert(Lc,++k,bj);++j;
}

}//marge