CHAP 6 리스트 (2)

(1)

CHAP 6 리스트 (2)

2021. 5. 12

순천향대학교 컴퓨터공학과

(2)

내용

 리스트 추상 데이터 타입

 배열로 구현된 리스트

 단순 연결 리스트



표현



삽입



삭제



기타 리스트 연산



응용: 다항식

 원형 연결 리스트

(3)

리스트 연산

 리스트 탐색

 리스트 연결

 리스트 역순

(4)

리스트 탐색

 탐색 연산: 특정한 데이터 값을 갖는 노드를 찾는 연산



특정 값 val을 포함하는 노드를 발견하면 그 노 드를 반환



그 값이 발견되지 않으면 null을 반환

head

NULL NULL

p

NULL

(5)

리스트 탐색 알고리즘

head

NULL NULL

p

NULL

ListNode* search_list(ListNode* head, element val) // head: 헤드 포인터

// val: 탐색 데이터

// val을 포함한 노드나 null을 반환 {

typedef struct ListNode { element data;

struct ListNode *link;

} ListNode;

(6)

리스트 연결

 2개의 리스트를 연결하는 연산

 리스트가 비어 있는 경우 고려

 head1이 null이면?

 head2가 null이면?

head1 NULL NULL

head2 NULL NULL

NULL

(7)

리스트 연결 알고리즘

head1 NULL NULL

head2 NULL NULL

NULL

ListNode* concat_list(ListNode* list1, list2) // list1, list2: 헤드 포인터

// 연결된 리스트를 반환 {

typedef struct ListNode { element data;

} ListNode;

(8)

리스트 역순화

 리스트의 노드들을 역순으로 재배치하라.

head NULL NULLNULL

NULL NULL

NULL

head

(9)

리스트 역순화: 분석 (1)

 3개의 포인터 변수 사용



p: 역순으로 만들 리스트를 가리킨다.



q: 역순으로 만들 노드를 가리킨다.



r: 역순화된 리스트를 가리킨다.

(10)

리스트 역순화: 분석(2)

 초기에,



p = head, q = NULL, r = NULL

 다음에,첫번째 노드부터 역순화 작업 수행

head NULL NULLNULL

q p NULL

역순대상 리스트 역순대상 노드

(11)

리스트 역순: 분석(2)

 초기에,



p = head, q = NULL

 다음에,

head NULL NULLNULL

q p NULL

역순대상 리스트 역순대상 노드

(12)

리스트 역순화: 분석 (3)

 다음에,

NULL NULL

p

NULL NULL

r q

NULL NULL

NULL

(13)

리스트 역순화: 분석 (4)

 다음에,

NULL NULL

q p

NULL

r

(14)

리스트 역순화: 분석 (5)

 다음에,

NULL NULL

q p

NULL

NULL NULL

r

(15)

리스트 역순화 알고리즘

ListNode* reverse(ListNode* head) {

// head: 헤드 포인터; 역순환된 리스트 반환 ListNode* p, q, r;

p <- head; // p: 역순으로 변환될 리스트

q <- NULL; // q: 역순으로 만들 노드, r:역순화된 리스트 while p ≠ NULL do

list NULL NULL

q p

NULL

r

(16)

리스트 응용: 다항식

 3장에서 다룬 다항식을 단순 연결 리스트로 표현하려면?

 Ex. A=3x ¹² +2x ⁸ +1

(17)

다항식의 연결리스트 표현

 다음 다항식의 단순 연결 리스트 표현은?

A=3x ¹² +2x ⁸ +1

 노드 타입 정의

A 3 12 2 8 1 0 NULL

(18)

다항식의 덧셈

 다음 2개의 다항식을 더하라

A= 3x ¹² +2x ⁸ +1, B= 8x ¹² -3x ¹⁰ +10x ⁶ C = A + B

A

B

3 ¹² 2 8

8 12 -3 10

1 0

10 6

NULL

(19)

다항식의 덧셈: 분석(1)

(20)

다항식의 덧셈: 분석(2)

(21)

다항식의 덧셈 분석(3)

(22)

리스트 끝에 노드 삽입

 앞서 살펴본 바와 같이, 덧셈 진행 과정에서 결과 다항식은 리스트의 맨 끝에 노드를 삽 입함으로써 구성된다.

 새로운 노드를 리스트의 맨 끝에 삽입하는

알고리듬은?

(23)

삽입 연산: 리스트 맨 끝에 삽입

ListNode* insert_last(ListNode *head, element value) // 리스트 맨 끝에 새로운 노드 삽입후 헤드 포인터 반환

{

typedef struct ListNode {

element data;

} ListNode;

(24)

헤더 노드 사용

 헤더 노드를 사용하면, 노드를 리스트 맨 끝 에 삽입하는 과정이 효율적



헤더 노드는 2개의 포인터 head, tail을 포함



head는 첫번째 노드를 가리키고, tail은 마지막 노드를 가리킨다.



리스트에 포함된 노드의 개수를 나타내는 length 를 가질 수 있다.

len gth

he ad

ta

header

il

헤더노드

(25)

삽입 연산: 헤더 노드 사용

procedure insert_last(ListNode header, ListNode new) // header: 헤더 노드에 대한 포인터

// new: 새로 삽입될 노드 {

if 리스트가 비어 있으면 then

else

len gth

he ad

ta

header

il

(26)

프로그램 6.9

 다항식 덧셈시 헤더 노드 사용

typedef struct ListNode { // 노드 타입

int coef;

int expon;

} ListNode;

typedef struct ListType { // 헤더 노드 타입

int size; // 리스트에 포함된 노드 개수 ListNode *head;

ListNode *tail;

} ListType;

(27)

프로그램 6.9

int main(void) {

ListType *list1, *list2, *list3;

// 연결 리스트 헤더 생성 list1 = create();

list2 = create();

list3 = create();

// 다항식 1을 생성

insert_last(list1, 3, 12);

// 다항식 2를 생성

insert_last(list2, -3, 10);

poly_print(list1); poly_print(list2);

typedef struct ListNode { int coef;

int expon;

} ListNode;

typedef struct ListType { int size;

ListNode *head;

ListNode *tail;

} ListType;

(28)

프로그램 6.9 (다항식 덧셈)

// plist는 연결 리스트의 헤더를 가리키는 포인터, // coef는 계수, expon는 지수

void insert_last(ListType* plist, int coef, int expon) {

ListNode* temp

temp = (ListNode *)malloc(sizeof(ListNode)); // 노드 동적 할당 if (temp == NULL) error("메모리 할당 에러");

temp->coef = coef; // 노드 초기화 temp->expon = expon;

temp->link = NULL;

if (plist->tail == NULL) { // 노드 삽입 plist->head = plist->tail = temp;

}

else {

plist->tail->link = temp;

plist->tail = temp;

(29)

다항식 프로그램

void poly_add(ListType* plist1, ListType* plist2, ListType* plist3) { // list3 = list1 + list2

ListNode* p = plist1->head;

ListNode* q = plist2->head;

int sum;

while (p != NULL && q != NULL) {

if (p->expon == q->expon) { // p의 차수 > q의 차수 sum = p->coef + q->coef;

if (sum != 0) insert_last(plist3, sum, a->expon);

p = p->link; q = q->link;

}

else if (p->expon > q->expon) { // p의 차수 == q의 차수 insert_last(plist3, p->coef, p->expon);

p = p->link;

}

else { // p의 차수 < q의 차수

insert_last(plist3, q->coef, q->expon);

q = q->link;

}

typedef struct ListNode { int coef;

int expon;

} ListNode;

typedef struct ListType { int size;

ListNode *head;

ListNode *tail;

} ListType;

(30)

procedure

poly_add2(p, q: poly) : poly r: poly;

ip, iq, ir, num: integer

ip <- 0; iq<- 0; ir <-0; // 다항식의 현재 항 인덱스 설정 num <- 0; // 결과 다항식의 항 개수

while

ip < p.num and iq < q.num do // 양쪽에 항이 남아 있으면

if

p.terms[ip].expo = q.terms[iq].expo then //차수가 같으면

r.terms[ir].coef <- p.terms[ip].coef + q.terms[iq].coef;

r.terms[ir].expo <- p.terms[ip].expo;

ir++; ip++; iq++; // 인덱스 갱신

else if p.terms[ip].expo > q.terms[iq].expo then // p의 항 차수가 크면

r.terms[ir].coef <- p.terms[ip].coef;

r.terms[ir].expo <- p.terms[ip].expo;

ir++; ip++;

else

// q의 항 차수가 크면

r.terms[ir].coef <- p.terms[iq].coef;

r.terms[ir].expo <- p.terms[iq].expo;

ir++; iq++;

// 어느 한 쪽이 먼저 소진된 경우 처리

ifip < p.num then // p의 나머지 항들을 r로 이동 for i<- ip to p.num-1 do

r.terms[ir++] <- p.terms[i]

num++;

repeat

else if iq < q.num then // q의 나머지 항들을 r로 이동 typedef struct {

float coef;

int expo;

} term_type;

typedef struct { term_type

terms[MAX_SIZE];

int num; // 항 개수 } poly_type;

CHAP 6 리스트 (2)