양방향 연결 리스트에서의 추가/삭제 연산을 구현해본다.이중연결리스트

컴파일 실행환경

없음

본문내용

1. 우선 다음과 같이 이중연결리스트의 구조체를 선언하고, 생성함수를 작성한다.
typedef struct dnode_elm * dnode;
struct dnode_elm {
int item;
dnode next;
dnode prev;
}
typedef struct dlist* Dlist;
struct dlist {
dnode head;
dnode tail;
int size;
}
Dlist createDlist( ) {
Dlist D = (Dlist)malloc( sizeof(struct dlist) );
D->head = D->tail = null;
D->size = 0;
return D;
}


2. [3점] 특정 item 값이 저장된 노드 x를 찾는 함수를 작성한다. 이 search 함수는 item
값이 저장된 dnode가 있다면 그 노드를 리턴하고, 없다면 null을 리턴한다.
dnode search( Dlist D, int item )


3. [5점] insertAtHead 함수를 작성한다. 이 함수는 item을 저장할 dnode를 생성하여,
D의 head에 추가하는 함수이다.
void insertAtHead( Dlist D, int item )

==>교수님께서 짜주신 코드를 사용할 것!



4. [5점] 특정 item 값이 저장된 노드 x를 제거하는 함수 delete를 작성한다. (x를 찾기
위해서, search 함수를 이용한다.)
void deletex( Dlist D, dnode x )


5. [5점] 하나의 리스트를 노드 x에서 분리하는 함수 split을 작성한다. 이 함수는 노드
x와 오른쪽에 위치한 노드들을 새로운 리스트로 만들어 리턴한다. 기존의 리스트 D
는 노드 x의 왼쪽에 있는 노드들로만 구성된다.
Dlist split( Dlist D, dnode x )


6. [5점] 두 리스트를 하나의 리스트로 합병하는 함수 join을 작성한다. 이 함수는 두 리
스트를 차례로 연결한 후, 합병된 리스트를 리턴한다.
Dlist join( Dlist D1, Dlist D2 )

참고 자료

없음