-
(2) ∵ 원형 연결 리스트에서는 마지막 노드가 첫번째 노드를 가리키므로, NULL 포인트가 존재하지 않는다.
-
(1) ∵ 배열에서는 인덱스 n번째에 바로 접근가능하므로, 시간복잡도 O(1)로 가장 빠르다
-
(3)
-
(c)
-
p=p->link;
-
q=p;
-
D ∵ 현재 노드가 가르키는 링크가 NULL일때까지 탐색하므로, 최종적으로는 마지막 노드를 가리키게 된다.
-
(4) ∵ 마지막 원소를 삭제한 후, last 포인터가 다시 마지막 노드를 가리키기 위해서는 첫번째 노드부터 다시 탐색해야 하므로 O(n)의 시간복잡도가 소요된다.
node* insert_last(node* head, int value) {
node* p, * temp = (node*)malloc(sizeof(node));
temp->data = value;
temp->link = NULL;
if (head == NULL)
return temp;
else {
for (p = head; p->link; p = p->link);
p->link = temp;
return head;
}
}
int main(void) {
int num, value;
node* head = NULL;
printf("노드의 개수: ");
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
printf("노드 #%d 데이터: ", i);
scanf("%d", &value);
head = insert_last(head, value);
}
printf("생성된 연결 리스트: ");
printl(head);
}int main(void) {
int num, value;
node* head = NULL;
printf("노드의 개수: ");
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
printf("노드 #%d 데이터: ", i);
scanf("%d", &value);
head = insert_first(head, value);
}
int count = 0;
for (node* p = head; p; p = p->link, count++);
printf("노드의 개수: %d", count);
}int main(void) {
int num, value;
node* head = NULL;
printf("노드의 개수: ");
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
printf("노드 #%d 데이터: ", i);
scanf("%d", &value);
head = insert_first(head, value);
}
int sum = 0;
for (node* p = head; p; p = p->link)
sum += p->data;
printf("노드의 합: %d", sum);
}int main(void) {
int num, value;
node* head = NULL;
printf("노드의 개수: ");
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
printf("노드 #%d 데이터: ", i);
scanf("%d", &value);
head = insert_first(head, value);
}
int count = 0;
printf("탐색할 값: ");
scanf("%d", &num);
for (node* p = head; p; p = p->link) {
if (p->data == num)
count++;
}
printf("%d값 : %d개 존재", num, count);
}node* delete(node* head, int value) {
node* pp, * p, * now;
pp = p = now = head; // pp는 이전 노드, p는 pp의 다음노드, now는 현재 가리키는 노드
while (now) { // 리스트 끝에 도달할때까지 반복
if (now->data == value) { // now가 삭제하고자 하는 값의 노드인 경우
node* temp = now; // temp노드에 현재노드(now)를 저장한다 (나중에 free()로 메모리 해제 목적)
if (p == head) { // 삭제하고자 하는 노드가 첫번째 노드인 경우
head = now->link; // head 포인터를 첫번째 노드(삭제될 노드)의 다음 노드를 가리키도록 지정
pp = p = head; // 업데이트된 head 포인터를 다시 pp와 p에 저장
}
else { // 삭제하고자 하는 노드가 첫번째 노드가 아닌 경우
pp->link = now->link; // 이전 노드의 링크가 현재노드(삭제될 노드)의 다음 노드를 가리키도록 지정
p = p->link; // p는 삭제될 노드의 다음노드를 가리키도록 지정
}
now = now->link; // 다음 노드를 탐색해야 하므로, now가 후속노드를 가리키도록 지정
free(temp); // 지정한 값을 가지는 노드를 메모리 해제
}
else { // now노드가 삭제하고자 하는 값이 아닌 경우
pp = p; // pp(이전 노드)가 p(현재 노드)를 가리키도록 지정
p = p->link; // p(현재 노드)는 그 다음 노드를 가리키도록 지정
now = now->link; // 다음 노드를 탐색해야 하므로, now가 후속노드를 가리키도록 지정
}
}
return head; // 새로 바뀐 head 를 반환
}typedef struct node {
char name[10];
int age;
double height;
struct node* link;
} node;void min_max(node* head) {
int min, max;
min = max = head->data;
for (node* p = head; p; p=p->link) {
if (p->data < min)
min = p->data;
if (p->data > max)
max = p->data;
}
printf("최대: %d, 최소: %d", max, min);
}node* delete_odd(node* head) { // 첫번째 노드를 먼저 삭제 후, 이후 짝수번째를 삭제함으로써 홀수번째 노드 제거 방식
node* temp, *pp, *p;
temp = head; // 첫번째 노드를 temp에 지정
head = head->link; // head가 두번째 노드를 가리키도록
free(temp); // 첫번째 노드 메모리 해제
pp = p = head;
int count = 1;
while (p) { // 첫번째 노드가 제거 되었으므로, 이후에는 짝수번째를 계속 제거해주면 된다.
if (count++ % 2 == 0) { // 짝수번째 노드인 경우 제거
node* temp = p;
pp->link = p->link;
p = p->link;
free(temp);
}
else { // 홀수번째 노드인 경우, pp와 p를 각각 한 노드씩 증가
pp = p;
p = p->link;
}
}
return head;
}- 시간복잡도: 두 연결리스트의 크기를 각각 n1, n2라고 하면 O(n1+n2)가 된다.
node* alternate(node* head1, node* head2) {
node* p1, * p2, *new;
p1 = head1; p2 = head2; new = NULL;
while (p1 && p2) {
new = insert_last(new, p1->data);
p1 = p1->link;
new = insert_last(new, p2->data);
p2 = p2->link;
}
for (node* p = p1; p; p = p->link)
new = insert_last(new, p->data);
for (node* p = p2; p; p = p->link)
new = insert_last(new, p->data);
return new;
}- 시간복잡도: 두 연결리스트의 크기를 각각 n1, n2라고 하면 O(n1+n2)가 된다.
node* merge(node* head1, node* head2) {
node* p1, * p2, *new;
p1 = head1; p2 = head2; new = NULL;
while (p1 && p2) {
if (p1->data < p2->data) {
new = insert_last(new, p1->data);
p1 = p1->link;
}
else {
new = insert_last(new, p2->data);
p2 = p2->link;
}
}
for (node* p = p1; p; p = p->link)
new = insert_last(new, p->data);
for (node* p = p2; p; p = p->link)
new = insert_last(new, p->data);
return new;
}typedef struct {
node* list1;
node* list2;
} list;
list split(node* head) {
list l = { NULL, NULL };
node* p = head;
while (p) {
l.list1 = insert_last(l.list1, p->data);
p = p->link;
if (!p)
break;
l.list2 = insert_last(l.list2, p->data);
p = p->link;
}
return l;
}int main(void) {
hnode* list1, * list2, * list3;
list1 = create();
list2 = create();
list3 = create();
insert_last(list1, 3, 6);
insert_last(list1, 7, 3);
insert_last(list1, -2, 2);
insert_last(list1, -9, 0);
insert_last(list2, -2, 6);
insert_last(list2, -4, 4);
insert_last(list2, 6, 2);
insert_last(list2, 6, 0);
printl(list1);
printl(list2);
add(list1, list2, list3);
printl(list3);
}int poly_eval(hnode* head, int x) {
node* p = head->head;
int sum = 0;
for (; p; p = p->link) {
int mul = 1;
for (int i = 0; i < p->exp; i++)
mul *= x;
sum += (p->coef * mul);
}
return sum;
}#include <stdio.h>
#include <stdlib.h>
#define SIZE 100
typedef int element;
typedef struct {
element array[SIZE];
int size;
} list;
void init(list* l) {
l->size = 0;
}
void add(list* l, element item) {
int i = l->size - 1;
while ((i >= 0) && (l->array[i] > item)) {
l->array[i+1] = l->array[i];
i--;
}
l->array[i + 1] = item;
l->size++;
}
void delete(list* l, element item) {
int i = 0;
while ((i < l->size) && (l->array[i] != item))
i++;
for (int j = i; j < l->size - 1; j++)
l->array[i] = l->array[i + 1];
l->size--;
}
void clear(list* l) {
l->size = 0;
}
int is_in_list(list* l, element item) {
int c = 0;
for (int i = 0; i < l->size; i++) {
if (l->array[i] == item)
c++;
}
return c;
}
int get_length(list* l) {
return l->size;
}
int is_empty(list* l) {
return (!l->size);
}
int full(list* l) {
return (l->size == SIZE);
}
void display(list* l) {
for (int i = 0; i < l->size; i++) {
printf("%d->", l->array[i]);
}
puts("");
}
int main(void) {
int num, value;
list* l = (list*)malloc(sizeof(list));
init(l);
while (1) {
printf("삽입(0), 삭제(1): ");
scanf("%d", &num);
printf("값: ");
scanf("%d", &value);
if (num)
delete(l, value);
else
add(l, value);
display(l);
}
}#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct node {
element data;
struct node* link;
} node;
node* add(node* head, element item) {
node* temp = (node*)malloc(sizeof(node));
temp->data = item;
temp->link = NULL;
if (head == NULL)
return temp;
if (head->data > item) {
temp->link = head;
head = temp;
return head;
}
else {
node* p = head;
while ((p->link != NULL) && (p->link->data < item))
p = p->link;
temp->link = p->link;
p->link = temp;
return head;
}
}
node* delete(node* head, element item) {
node* temp = head;
if (head->data == item) {
head = head->link;
free(temp);
}
else {
while ((temp->link != NULL) && (temp->link->data != item))
temp = temp->link;
if (temp == NULL)
return head;
node* remove = temp->link;
temp->link = temp->link->link;
}
return head;
}
node* clear(node* head) {
node* temp, * p = head;
while (p) {
temp = p;
p = p->link;
free(temp);
head = p;
}
return head;
}
int is_in_list(node* head, element item) {
int c = 0;
for (node* p = head; p; p = p->link) {
if (p->data == item)
c++;
}
return c;
}
int get_length(node* head) {
int c = 0;
for (node* p = head; p; p = p->link, c++);
return c;
}
int is_empty(node* head) {
return (head == NULL);
}
void display(node* head) {
for (node* p = head; p; p = p->link)
printf("%d → ", p->data);
puts("NULL");
}
int main(void) {
int num, value;
node* head = NULL;
while (1) {
printf("삽입(0), 삭제(1): ");
scanf("%d", &num);
printf("값: ");
scanf("%d", &value);
if (num)
head= delete(head, value);
else
head = add(head, value);
display(head);
}
}typedef struct node{
int row;
int col;
int value;
struct node* rlink; // rlink는 같은 행에서 0이 아닌 다음 노드의 주소
struct node* clink; // clink는 같은 열에서 0이 아닌 다음 노드의 주소
} node;
h