반응형
1.
( ㄴ ) 에서 자료 c를 가져오려면 pop 연산을 3회 수행해야한다.
1회 수행하면 a 를, 2회 수행하면 a 와 b 를 가져올 수 있다.
정답 : ( 3 )
2.
배열로 구현된 리스트가 삽입과 삭제작업이 자주 발생할 때 시간이 가장 많이 소요된다.
특정 원소를 삭제하면 나머지 배열의 다른 원소들을 shift 해야되므로 연결리스트에 비해 시간이 많이 소요된다.
또, 원소를 특정 위치에 삽입하려면 나머지 배열의 다른 원소들을 전부 shift 해야된다.
답 : ( 1 )
3.
#include<stdio.h>
#include<stdlib.h>
typedef int element;
typedef struct CListType {
element data;
struct CListType* link;
}CListType;
void insert_first(CListType** phead, CListType* node) {
if (*phead == NULL) {
*phead = node;
node->link = node;
}
else {
node->link = (*phead)->link;
(*phead)->link = node;
}
}
void insert_last(CListType** phead, CListType* node) {
if (*phead == NULL) {
*phead = node;
node->link = node;
}
else {
node->link = (*phead)->link;
(*phead)->link = node;
*phead = node;
}
}
CListType* create_node(element data) {
CListType* new_node;
new_node = (CListType*)malloc(sizeof(CListType));
new_node->data = data;
new_node->link = NULL;
return new_node;
}
CListType* search(CListType* L, element data) {
CListType* p = L;
do{
if (p->data == data)
return p;
p = p->link;
} while (p != L);
return NULL;
}
4.
int get_size(CListType* L) {
CListType* p = L;
int count = 0;
do {
count++;
p = p->link;
} while (p != L);
return count;
}
5.
이중연결리스트의 장점은 단순 연결 리스트나 원형 연결 리스트에서 어떤 노드의 후속 노드를 찾기는 쉽지만, 선행 노드를 찾으려면 헤드 포인터부터 시작해서 전체를 탐색을 해야한다.
이때, 이중연결리스트를 이용하면 쉽게 선행 노드를 찾을 수 있다는 장점이 있다.
단점으로는 이중연결리스트의 노드가 단순 연결 리스트나 원형 연결 리스트에 비해 메모리가 크고, 구현하는데 조금 더 복잡하다는 점이 있다.
6.
#include<stdio.h>
#include<stdlib.h>
typedef int element;
typedef struct DlistNode {
element data;
struct DlistNode* llink;
struct DlistNode* rlink;
}DlistNode;
void dinsert_node(DlistNode* before, DlistNode* new_node) {
new_node->llink = before;
new_node->rlink = before->rlink;
before->rlink->llink = new_node;
before->rlink = new_node;
}
void dremove_node(DlistNode* phead_node, DlistNode* removed) {
if (removed == phead_node)
return;
removed->llink->rlink = removed->rlink;
removed->rlink->llink = removed->llink;
}
void reverse_display(DlistNode* phead) {
DlistNode* p;
for (p = phead->llink; p != phead; p = p->llink) {
printf("%d ", p->data);
}
printf("\n");
return;
}
void init(DlistNode* phead) {
phead->llink = phead;
phead->rlink = phead;
}
void display(DlistNode* phead) {
DlistNode* p;
for (p = phead->rlink; p != phead; p = p->rlink) {
printf("%d ", p->data);
}
printf("\n");
return;
}
int main(void) {
DlistNode list1 = {};
DlistNode* p[10] = {};
init(&list1);
for (int i = 1; i <= 5; i++) {
p[i] = (DlistNode*)malloc(sizeof(DlistNode));
p[i]->data = i;
dinsert_node(&list1, p[i]);
}
display(&list1);
reverse_display(&list1);
}
7.
DlistNode* search(DlistNode* L, element data) {
DlistNode* p;
for (p = L->rlink; p != L; p = p->rlink) {
if (p->data == data)
return p;
}
return NULL;
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 8장 핵심정리를 가져오도록 하겠습니다.
반응형