보고서#6 (due 5/25)

(1)

보고서#6 (due 5/25)



제출 방법:

 대학 학습플랫폼(Lms)에 명시된 기간내 제출해야 한다.

 설정된 제출 기간 5/25이며, 기한이 지나면 제출할 수 없음에 유의하

기 바랍니다.

1

(2)

문제 (1)



배열과 그 크기를 매개변수로 전달받아서 배열 각 요소에 대해서 요소 값을 포함하는 노드를 생성하고, 리스트의 첫번째로 삽입하 여 구성된 리스트를 반환하는 consList()를 작성하라. insert_first ()를 이용하라. 예를 들면 다음과 같다.

7 5 3 1

1 3 5 7 ^null

List1

(3)

문제 (2)



2개의 연결리스트 list1, list2가 데이터 값의 오름차순으로 정렬되 어 있다고 가정한다. 이 2개 리스트를

오름차순 정렬상태를 유지 하면서

합병하고, 그 결과 리스트를 반환하는 merge()를 작성하 라. 예를 들면 다음과 같다.

1 3 5 7 ^null

List1

2 4 5 ^null

List2

1 2 3 4

List

5 5 7 ^null

(4)

문제 (3)



다음과 같이 main() 함수를 작성하고, 테스트하라.

main() {

ListNode *list1, *list2, *list;

int a[] = {7, 5, 3, 1}, b[] = {5, 4, 2};

// 배열을 매개변수로 전달받아서 리스트 생성 list1 = consList(a, 4);

list2 = consList(b, 3);

// 리스트 합병

list = merge(list1, list2);

// 리스트 출력

print_list(list1); print_list(list2); print_list(list);

return 0;

}

(5)

#include <stdio.h>

#include <stdlib.h>

typedef struct ListNode { // 리스트 노드 타입 정의 int data;

struct ListNode* link;

} ListNode;

ListNode* insert_first(ListNode* head, int value);

ListNode* consList(int a[], int size);

ListNode* merge(ListNode* list1, ListNode* list2);

void print_list(ListNode* head);

int main() {

ListNode *list1, *list2, *list;

int a[] = { 7,5,3,1 }, b[] = { 5,4,2 };

list1 = consList(a, 4);

print_list(list1);

list2 = consList(b, 3);

print_list(list2);

list = merge(list1, list2);

print_list(list);

return 0;

}

(6)

ListNode* insert_first(ListNode* head, int value)

// 노드를 생성하여 리스트의 첫번째 노드로 삽입후 반환 {

ListNode* p;

p = (ListNode*)malloc(sizeof(ListNode));

p->data = value; p->link = NULL;

if (head == NULL) head = p;

else {

p->link = head;

head = p;

}

return head;

}

(7)

void print_list(ListNode* head) // head: 헤드 포인터

{

ListNode* p = head;

while(p != NULL) {

printf("\t%d", p->data);

p = p->link;

}

printf("\n");

}

ListNode* consList(int a[], int size) { ListNode* list = NULL;

for (int i = 0; i < size; i++) { list = insert_first(list, a[i]);

}

return list;

}

(8)

ListNode* merge(ListNode* list1, ListNode* list2) {

ListNode* p = list1, * q = list2, * r = NULL, * list = NULL;

bool first = true; // boolean variable

while (p != NULL && q != NULL) {// 2개 리스트 모두가 노드 포함하면 if (p->data <= q->data) {

if (first) { // 리스트의 첫번째 노드이면 list = p; r = p; first = false;

}

else {

r->link = p; r = p;

}

p = p->link;

} else {

if (first) { // 리스트의 첫번째 노드이면 list = q; r = q; first = false;

}

else {

r->link = q; r = q;

}

q = q->link;

}

} // else

// 어느 한 쪽 리스트가 소진될 경우에 if (p != NULL)

r->link = p;

else if (q != NULL) r->link = q;

return list;

}