** 구현에 대하여
1. 의사코드의 실제 구현은 C로 하였음
2. 리스트의 원소는 문자(character)로 정하였음
3. 순회(traverse)는 출력으로 시각화하였음
연속적 임의 개체들을 모델링하는 추상자료형
= 원소들의 순서 집단을 저장하기 위한 기초적이고 일반적 목적의 데이터 구조
메소드 | 배열 | 단일연결리스트 | 이중연결리스트 |
---|---|---|---|
init | O(1) | O(1) | O(1) |
get / set | O(1) | O(n) | O(n) |
traverse | O(n) | O(n) | O(n) |
add / remove | O(n) | O(n) | O(n) |
addFirst / removeFirst | O(n) | O(1) | O(1) |
addLast / removeLast | O(1) | O(n) | O(1) |
N
: 현재 최대로 담을 수 있는 원소 개수n
: 저장된 원소 개수r
: 0부터 시작Alg init()
input array V, integer N, integer n
output an empty array V of size N
1. n ← 0
2. return
// 각 원소가 문자(character)를 담는다고 가정
#include<stdio.h>
void init(char** V, int N, int* n){
*V = (char*)malloc(sizeof(char)*N);
*n = 0;
}
int main(){
char* V;
int N, n;
scanf("%d", &N);
init(&V, N, &n);
return 0;
}
Alg traverse()
input array V, integer N, integer n
output none
1. for r←0 to n-1
visit(V[r])
2. return
// 각 원소가 문자(character)를 담는다고 가정
// traverse의 결과가 보이도록 print기능으로 구현
void print(char *V, int n) {
for(int r=0; r<n-1; r++){
printf("%d ", V[r]);
}
printf("\n");
}
add : O(n)
addFirst : O(n)
addLast : O(1)
Alg add(r, e)
input array V, element e, rank r, integer N, integer n,
output none
1. if(r<0 || r>n)
invalidRankException()
2. if(n==N)
fullListException()
3. for i←n-1 downto r
V[i+1] ← V[i]
4. V[r] ← e
5. n ← n+1
6. return
char add(char *V, char e, int r, int N, int *n) {
// 예외처리
if( (r<0)||(r>(*n)) ){
printf("invalid rank exception\n");
return e;
}
if(*n==N){
printf("full list exception\n");
return e;
}
// 삽입 수행
for(int i=*n; i>r; i--)
V[i] = V[i-1];
V[r] = e;
*n += 1;
return e;
}
remove : O(n)
removeFirst : O(n)
removeLast : O(1)
Alg remove(r)
input array V, rank r, integer N, integer n
output element e
1. if(r<0 || r>n-1)
invalidRankException()
2. for i←r to n-2
V[i] ← V[i+1]
3. n ← n-1
return
char Remove(char* V, int r, int* n) {
if( (r<0)||(r>(*n)-1) ){
printf("invalid rank exception\n");
return '0';
}
char e = V[r];
for(int i=r; i<(*n)-1; i++)
V[i] = V[i+1];
*n -= 1;
return e;
}
원형 배열로 구현한다
V
N
f
, 마지막 첨자 l
n
r
: 0부터 시작Alg size()
1. return (N-f+l+1)%N
Alg get(r)
1. if(r<0 || r>size()-1)
invalieRankException()
2. return A[(f+r)%N]
Alg set(r, e)
1. if(r<0 || r>size()-1)
invalidRankException()
2. return A[(f+r)%N]
Alg add(r, e)
1. if(r<0 || r>size())
invalidRankException()
2. if(n==N-1)
fullListException()
3. if(r<n/2)
for i ← 0 to r-1
A[(N+f+i-1)%N] ← A[(f+i)%N]
A[(N+f+r-1)%N] ← e
f ← (N+f-1)%N
else
for i ← n-1 downto r
A[(f+i+1)%N] ← A[(f+i)%N]
A[(f+r)%N] ← e
l ← (l+1)%N
4. return
Alg remove(r)
1. if(r<0 || r>size()-1)
invalidRankException()
2. if(r<n/2)
for i ← r-1 downto 0
A[(f+i+1)%N] ← A[(f+i)%N]
f ← (f+1)%N
else
for i ← r+1 downto n-1
A[(f+i-1)%N] ← A[(f+i)%N]
l ← (N+l-1)%N
헤더와 트레일러가 있는 연결리스트로 구현한다.
L
n
r
: 1부터 시작Alg init()
input none
output singly linked list L with header H, trailer T
1. H ← getNode()
2. T ← getNode()
3. H.next ← T
4. n ← 0
5. return L
#include <stdio.h>
typedef struct _Node {
char e;
struct _Node* next;
} Node;
Node* getNode (){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->next = NULL;
return newNode;
}
void putNode (Node* p){
free(p);
}
Node* init(){
Node* H = getNode();
Node* T = getNode();
H->next = T;
return H;
}
int main(){
Node* L = init();
int n = 0;
return 0;
}
Alg traverse()
input singly linked list L with header H, trailer T
output none
1. p ← H
2. while(p != NULL)
p ← p.next
visit(p.elem)
3. return
void print(Node* H){
Node* p = H->next;
while(p->next != NULL){
printf("%c ", p->e);
p = p->next;
}
printf("\n");
}
add : O(n)
addFirst : O(1)
addLast : O(n)
Alg add(r, e)
input L, rank r, element e, integer n
output none
1. if( r<1 || r>n+1 )
invalidRankException()
2. p ← H
3. for i ← 1 to r
p ← p.next
4. addNodeBefore(p, e, r)
5. n ← n+1
6. return
Alg addNodeBefore(p, e, r)
input L, node p, element e, rank r
output node q
1. q ← getNode() { 새로운 노드 추가 }
2. q.elem ← e
3. q.next ← p
4. p ← H { 링크 잇기 }
5. if( r>1 )
for i ← 1 to r-1
p ← p.next
6. p.next ← q
7. return
char add(Node* H, int r, char e, int* n){
if( (r<1)||(r>(*n)+1) ){
printf("invalid rank exception\n");
return e;
}
Node* p = H;
for(int i=0; i<r; i++)
p = p->next;
addNodeBefore(H, p, r, e);
*n += 1;
return e;
}
void addNodeBefore(Node* H, Node* p, int r, char e){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->e = e;
newNode->next = p;
Node* q = H;
for(int i=0; i<r-1; i++)
q = q->next;
q->next = newNode;
}
remove : O(n)
removeFirst : O(1)
removeLast : O(n)
Alg remove(r)
input L, rank r
output none
1. if( r<1 || r>n )
invalidRankException()
2. p ← H
3. for i ← 1 to r
p ← p.next
4. e ← removeNode(p)
5. n ← n-1
6. return e
Alg removeNode(p, r)
input L, node p, rank r
output none
1. q ← p.next { 임시저장 }
2. e ← p.elem
3. putNode(p) { 노드 할당풀기 }
4. p ← H { 링크 잇기 }
5. if( r>1 )
for i ← 1 to r-1
p ← p.next
6. p.next ← q
5. return e
char Remove(Node* H, int r, int* n){
if( (r<1)||(r>(*n)) ){
printf("invalid rank exception\n");
return '0';
}
Node* p = H;
for(int i=0; i<r; i++)
p = p->next;
char e = removeNode(H, p, r);
*n -= 1;
return e;
}
char removeNode(Node* H, Node* p, int r){
Node* newNext = p->next;
char e = p->e;
putNode(p);
Node* q = H;
for(int i=0; i<r-1; i++)
q = q->next;
q->next = newNext;
return e;
}
헤더와 트레일러가 있는 이중연결리스트로 구현한다.
L
n
r
: 1부터 시작Alg init()
input none
output doublely linked list L with header H, trailer T
1. H ← getNode()
2. T ← getNode()
3. H.next ← T
4. T.prev ← H
5. n ← 0
6. return L
#include <stdio.h>
typedef struct _Node {
char e;
struct _Node* prev;
struct _Node* next;
} Node;
Node* getNode(){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
void putNode(Node* p){
free(p);
}
Node* init(Node** H, Node** T){
*H = getNode();
*T = getNode();
(*H)->next = *T;
(*T)->prev = *H;
return *H;
}
int main(){
Node* H; // Head
Node* T; // Trailer
Node* L = init(&H, &T);
int n = 0;
/*
add(L, 1, 'a', &n);
add(L, 2, 'b', &n);
addLast(T, 'f', &n);
print(L); // a b f
Remove(L, 1, &n);
RemoveLast(T, &n);
print(L); // b
set(L, 1, 'z', n); // z
printf("%c\n", get(L, 1, n)); // z
*/
return 0;
}
Alg traverse()
input list L
output none
1. p ← H.next
2. while(p!=T)
visit(p.elem)
p ← p.next
3. return
void print(Node* H){
Node* p = H->next;
while(p->next != NULL){
printf("%c ", p->e);
p = p->next;
}
printf("\n");
}
Alg get()
input list L, rank r
output element e
1. if( r<1 || r>n )
invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
p ← p.next
4. return p.elem
Alg set()
input list L, rank r, new element e
output element e
1. if( r<1 || r>n )
invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
p ← p.next
4. p.elem ← e
5. return p.elem
char get(Node* H, int r, int n){
if( (r<1)||(r>(n)) ){
printf("invalid rank exception\n");
return '0';
}
Node* p = H->next;
for(int i=0; i<r-1; i++)
p = p->next;
return p->e;
}
char set(Node* H, int r, char e, int n){
if( (r<1)||(r>(n)) ){
printf("invalid rank exception\n");
return '0';
}
Node* p = H->next;
for(int i=0; i<r-1; i++)
p = p->next;
p->e = e;
return p->e;
}
add : O(n)
addFirst : O(1)
addLast : O(1)
Alg add()
input list L, rank r, element e
output none
1. if( r<1 || r>n+1 )
invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
p ← p.next
4. addNodeBefore(p, e)
5. n ← n+1
6. return
Alg addLast()
input list trailer T, element e
output none
1. addNodeBefore(T, e)
2. n ← n+1
3. return
Alg addNodeBefore(p, e)
input list L, node p, element e
output none
1. q ← getNode()
2. q.elem ← e
3. q.next ← p
4. q.prev ← p.prev
5. (p.prev).next ← q
6. p.prev ← q
7. return
char add(Node* H, int r, char e, int* n){
if( (r<1)||(r>(*n)+1) ){
printf("invalid rank exception\n");
return '0';
}
Node* p = H->next;
for(int i=0; i<r-1; i++)
p = p->next;
addNodeBefore(p, e);
*n += 1;
return e;
}
char addLast(Node* T, char e, int* n){
addNodeBefore(T, e);
*n += 1;
return e;
}
void addNodeBefore(Node* p, char e){
Node* newNode = getNode();
newNode->e = e;
newNode->next = p;
newNode->prev = p->prev;
(p->prev)->next = newNode;
p->prev = newNode;
}
remove : O(n)
removeFist : O(1)
removeLast : O(1)
Alg remove()
input list L, rank r
output element e
1. if( r<1 || r>n )
invalidRankException()
2. p ← H.next
3. for i ← 1 to r-1
p ← p.next
4. e ← removeNode(p)
5. n ← n-1
6. return e
Alg removeLast()
input list trailer T
output element e
1. e ← removeNode(T.prev)
2. n ← n-1
3. return e
Alg removeNode()
input list L, node p
output element e
1. e ← p.elem
2. (p.prev).next ← p.next
3. (p.next).prev ← p.prev
4. putNode(p)
5. return e
char Remove(Node* H, int r, int* n){
if( (r<1)||(r>(*n)) ){
printf("invalid rank exception\n");
return '0';
}
Node* p = H->next;
for(int i=0; i<r-1; i++)
p = p->next;
char e = RemoveNode(p);
*n -= 1;
return e;
}
char RemoveLast(Node* T, int* n){
char e = RemoveNode(T->prev);
*n -= 1;
return e;
}
char RemoveNode(Node* p){
char e = p->e;
(p->prev)->next = p->next;
(p->next)->prev = p->prev;
putNode(p);
return e;
}