4.1 SINGLY LINKED LISTS AND CHAINS
앞서 stack, queue 등은 배열같은 sequential mapping으로도 잘 작동했지만,
그게 효율적이지 않은 경우도 있다.
배열 2개로 singly linked list를 표현할 수 있다.
하나는 값을 저장하고, 하나는 다음 node를 가리킨다. 끝을 0으로 표시하기위해, 0 index는 사용하지 않는다.
공간을 더 사용하고, insertion이나 deletion에서 시간을 확보한다(바로바로 접근 가능). 이는 나쁘지 않은 교환이다.(특히 node 하나의 크기가 크면,,)
(array에서 중간 값 지우고 넣고 하려면 나머지들을 다 옮겨야됨)
4.2 REPRESENTING CHAINS IN C
Linked list
- node 공간은 structure로 구현한다.
malloc함수로 새로운 node를 할당받는다.- deletion 후에 필요없어진 node는
free함수로 deallocate한다.
structure 예시)
typedef struct node {
int data;
struct node *link;
} node;OR
typedef struct node *nodelink; //Incomplete type
typedef struct node {
int data;
nodelink link;
} node;이 다음 linked-list를 선언하고 싶으면,
nodelink first = NULL;
이러면 우리는 first라는 이름의 linked-list를 얻은 것이다.
이게 첫번째 node를 가리켜야하는데 아직 첫번째 node가 없으니 NULL로 표시해준다.
첫번째 node는 MALLOC으로 할당받아서 first와 연결해주면 된다.
Insertion과 Deletion에선 (1)처음 node일 경우와 (2)아닌 경우로 나눠서 봐야된다.
또 Deletion의 경우엔 trail pointer 정보도 있어야 한다.
(그래야 삭제할 node 이전 node의 link를 다음 node link로 바꿀 수 있다.)
4.3 LINKED STACKS AND QUEUES
array로도 stack이나 queue가 잘 표현됐지만,
stack이나 queue가 여러개 있으면 효율적으로 공간을 사용하기 어려웠다.
malloc으로 push나 addq일때마다 node 만들어서 추가해준다.
Linked Stack
typedef stack* stackPointer;
typedef struct stack{
int data; //구조체 같은게 와도 된다
stackPointer link;
} stack;
//여러 stack을 효율적으로 쓰려는거니까.. 공간때문도 있긴하지만
#define MAX_STACK 10
stackPointer top[MAX_STACK]; //top이 첫번째(top) node를 가리킴처음엔 모든 top을 NULL로 assign한다.(empty list)
push, pop구현은 쉽네 뭐
Linked Queue
typedef queue* queuePointer;
typedef struct queue{
int data; //구조체 같은게 와도 된다
queuePointer link;
} queue;
//여러 queue를 효율적으로 쓰려는거니까.. 공간때문도 있긴하지만
#define MAX_QUEUE 10
queuePointer front[MAX_QUEUE], rear[MAX_QUEUE];front와 queue 배열 두개가 있다.
addq 구현이 stack의 push처럼 단순하지가 않다. queue는 empty queue인지 아닌지 보고 나서 빈 queue라면 front값을 그걸 가리키도록 해야된다.
deleteq나 pop하고나면 썼던 memory는 free 해줘야한다.
이런 방식의 구현(linked stack&queue)은 link라는 추가 공간이 들긴 하지만,
시간 절약, 간단하게 표현되는 점 등을 생각하면 나쁘지 않은 교환이다.4.4 POLYNOMIALS
4.4.1 Polynomial Representation
typedef struct polyNode *polyPointer;
typedef struct polyNode {
int coef;
int expon;
polyPointer link;
} polyNode;
polyPointer a, b;각 node는 하나의 항을 나타낸다.
4.4.2 Adding Polynomials
a와 b는 linked list로 표현된 다항식
a->expon == b->expon
: 새로운 node에 (a->coef) + (b->coef)
a->expon != b->expon
: expon이 더 큰 항을 새로운 node에 복사
만들어진 새로운 node은 다항식 c에 붙인다.
(붙일때마다 link 따라서 c의 끝으로 갈 순 없으니, 포인터 하나 만들어서 늘어나는 c의 끝을 계속 따라가게 하자)
자세한 code는 생략(p.163)
c가 일단 빈 node 하나를 가리키게 만든다. 계산이 끝난 후 해당 node는 제거한다.
모양새가 이쁘진 않지만, 이렇게 하면 computation을 줄일 수 있다.
(c가 비어있는 경우도 따로 생각하는 것보단 차라리 이게 나은듯)
(간단한 작업 하나 추가로 나머지 부분을 일반화시켜서 더 간단하게 만들 수 있네)
queue도 아닌데 비어있는 경우 따로 생각하나?
: 뒤를 따라가는 node 처리 때문에 그렇다.
Analysis (padd)
모든 operations이 single unit of time이 걸린다고 가정하면 횟수에 의해 전체 시간이 결정된다.
각 다항식 길이를 n과 m이라고 할때, 어떤 경우(statement)를 보더라도 n+m을 넘지 않는다.(자세한 분석은 p.164)
따라서 O(n+m)이다. (다항식 더하는건 어떤 algorithm이더라도 모든 항은 다 봐야하므로 어느정도 최적이라고 할 수 있다.
4.4.3 Erasing Polynomials
Erase Polynomial 1
여러 다항식을 계산할때는 중간 결과를 저장하는 temp가 필요한데,
이거는 필요없어지면 다 deallocate 해줘야 한다.
erase 함수에서 포인터 두개 이용해서 쭉 나아가며 다 free시킨다.
4.4.4. Circular List Representation of Polynomials
Erase Polynomial 2
필요없는 node는 4.4.3처럼 erase해도 되지만, 따로 모아뒀다가 나중에 필요할때 가져와서 사용해도 된다.
즉, 필요없는걸 avail list에 저장해뒀다가 필요가 생기면 꺼내오고, 꺼내오려는데 비어있으면 그때 malloc을 쓰면된다.
즉, 이 경우 malloc과 free 대신 getNode와 retNode를 쓴다.
(이게 malloc free보다 당연히 빠르니까 쓰는거겠지? 자주 node 만들고 지우고 할거면 더 빠르게 하려고)
polyPointer getNode(void) {
polyPointer temp;
if (avail) {
temp = avail;
avail = avail->link;
}
else
MALLOC(temp, (*polyPointer))
return temp;
}void retNode(polyPointer node) {
node->link = avail;
avail = node;
}Circular List Representation
(singly linked list이면서 마지막 node의 link가 NULL인 경우 이를 chain이라고 한다.)
마지막 node의 link가 NULL이 아니라 첫번째 node를 가리킨다면, 이를 Circular List라고 한다.
이런 Cricular list는 node수에 상관없이 후자 방법을 사용해 바로 지워버릴 수 있다.
(avail에 전부 연결해버리고, 앞부분 가리키던 포인터는 NULL로 만들면 됨.)
chain도 이렇게 지울 수 있지않나,,
뭐 circular면 어떤 node를 가리키는 포인터를 넣어도 다 지울 수 있단게 장점이긴하네Empty Circular List Representation
Circular list는 빈 list를 따로 처리해야되는 문제때문에 보통 header node란걸 만들어서 제일 앞에 넣어둔다.(일반 node와 구분하기위해 polynomial에선 보통 expon -1인 node로 설정)
빈 list의 header node는 자기 자신을 가리킨다.
4.4.5 Summary
singly linked list(chain), singly linked circular list 에 대해 알아봤다.
Polynomial을 표현하는덴 circular list가 더 낫다는 점도 알아봤다.(padd할때도 좀 간편하고,,)
4.5 ADDITIONAL LIST OPERATIONS
4.5.1 Operations For Chains
Chain에 대한 여러 기능을 하는 함수를 만들어둬야 할때가 있다.
1. getNode
2. retNode
는 이미 만들었고,
3. invert : link 거꾸로 만드는 함수
4. concatenate : 두 list를 이어붙이는 함수
도 만들어보자.
invert
4가지 경우로 나눠서 생각한다.
1) node가 없는 경우
2) node가 1개인 경우
3) node가 2개인 경우
4) node가 3개 이상인 경우
listPointer invert(listPointer lead) {
listPointer trail, middle = NULL;
while(lead) {
trail = middle;
middle = lead;
lead = lead->link;
middle->link = trail;
}
return middle;
}일단 3개 이상인 ★가장 일반적인 경우만 먼저 생각해서 code를 작성하고,
예외적인 경우는 나중에 조금씩 수정하며 처리해준다.concatenate
listPointer concatenate(listPointer ptr1, listPointer ptr2) {
listPointer temp = ptr1;
if (!ptr1) return ptr2; //ptr1 empty인 경우
if (!ptr2) return ptr1; //ptr2 empty인 경우
for (; temp->link; temp = temp->link) ;
temp->link = ptr2;
return ptr1;
}4.5.2 Operations For Circulary Linked List
circular list는 항상 last 포인터로 끝을 표시해두면 좋다. 그래서 제일 앞이나 제일 뒤에 node를 자유롭게 insert할 수 있다. (last가 없으면, 제일 앞에 node를 넣을때 마지막 node의 link 바꾸러 끝까지 또 가봐야됨.)
insertFront
(header node가 없는 경우인 듯 하다.)
//empty검사할때 굳이 last 쓴 이유는 처음 가리키는 포인터 하나 더 입력받긴 그러니까..
void insertFront(listPointer *last, listPointer node){ //node를 insert
if (!(*last)) {
*last = node;
node->link = node;
}
else {
node->link = (*last)->link;
(*last)->link = node;
}
}length
길이 구하는 함수인데.. 뭐 empty인지 아닌지 조건 따지고 해보면 어렵지않게 할 수 있음. p.173
4.6 EQUIVALANCE CLASSES
≡ 가 arbitrary equivalance relation symbol일때,
1) reflexive : x≡x
1) symmetric : x≡y, y≡x
2) transitive : x≡y, y≡z, x≡z
세 조건을 모두 만족하는 set에 대해 equivalence relation이라고 한다.
ex) = relationship은 equivalence relation이다.
equivalence relation을 이용해 동치 관계에 있는 원소들을 모아 equivalence class를 만들 수 있다.
0≡4, 3≡1, 6≡10, 8≡9, 7≡4, 6≡8, 3≡5, 2≡11, 11≡0
이면
{0,2,4,7,11}; {1,3,5}; {6,8,9,10}
으로 나눌 수 있다.
(이 필요성을 VLSI를 이용해 설명하는데,, 궁금하면 책 p.174)
Equivalence class 만드는 방법
1단계: 일단 모든 순서쌍 <i,j>를 읽어오거나 저장해둔다.
2단계: 일단 0이 들어간 equivalence class부터 찾아보자.
<0,j>부터 앞에 0이 있는 모든 pair를 찾아서 j를 출력한다.(j는 0과 equivalence class이므로)
transitivity에 의해 <j,k>도 0과 equivalence class이므로 이에 해당하는 k도 찾아서 출력한다.(여러번 갈수도있음)
이렇게 0에 대해 모든 equivalence class를 출력했으면 다음으로 넘어간다.
이미 출력된 class면 넘긴다.(예를들어 0과 1이 같은 class인데, 0할때 1이 같이 출력됐으면 1은 pass)
2단계를 계속 하며 equivalence class를 모두 찾으면 된다.
Data 표현법
배열에 <i,j>를 i번째 row에 j들을 순서대로 저장할 수 있지만, 이는 공간이나 시간이나 꽤 낭비된다.
그래서 chain이 원소인 1차원 배열을 활용하자.
Equivalence Algorithm
seq는 chain이 원소인 1차원 배열이다.
1단계:
<i,j>가 나오면 seq[i] list에 j를, seq[j] list에 i를 저장한다.
즉, 1단계에선 해당 숫자와 직접적으로 연관된 모든 숫자를 작성한다.
1단계 code는 그냥 뭐 malloc으로 할당받아서 list에 연결시켜주는거라 생략.
MALLOC(x, sizeof(*x))
x->data = j; x->link = seq[i]; seq[i] = x;
이런식으로 순서쌍 다 해주면 됨.(반대로 seq[j]에도 넣어야됨)2단계:
out 1차원 배열을 이용해 해당 숫자가 출력됐는지 확인한다.(됐으면 FALSE, 아니면 TRUE)
그래서 출력했으면 out을 FALSE로 만들어줘야한다.
0부터 시작해서 일단 해당 row의 직접 연관된 숫자는 모두 출력하고, transitivity로 연결된 다른 row도 출력한다.
직접 연관된 숫자 출력 후 stack에 넣음으로써 transitivity를 모두 찾는다.
(아래 code에서는 그냥 link를 변경해서 stack에 넣어준다.)
for (i=0; i<n; i++) {
if (out[i]) {
printf("New class: %5d", i);
out[i] = FALSE;e
x = seq[i]; top = NULL; //둘다 nodePointer type
for(;;) { //남은 class 찾기
while(x) {
j = x->data;
if (out[j]) {
printf("%5d", j); out[j] = FALSE;
//아래는 직접연관된 숫자 stack에 넣고 x=x->link로 가는 과정
y = x->link;
x->link = top;
top = x;
x = y;
}
} //x와 직접 연관된 숫자 출력 끝
if (!top) break; //class 모두 출력 완료
x = seq[top->data]; top = top->link;
}
}
}Analysis (equivalence class)
stack에 최대 2m개 들어갈 수 있고, 바깥 for문은 n번 반복하니까,
O(m+n)이다. (m은 node 개수) (n은 코드에 나옴)
1단계 코드도 보면 O(m+n)이므로 전체 time complexity는 O(m+n)이다.
어떤 equivalence class 찾는 프로그램도 최소 m+n번은 다 봐야하므로 일정 요소내에서 최적이라고 할 수 있다.
space requirement도 O(m+n)인데, 나중에 O(n)인 경우 보자고하네(chapter 5)
4.7 SPARSE MATRICES
sparse matrix도 linked list로 나타내보자.
우선 두개의 노드 종류가 있다.
header node와 entry node.
header node는 next, down, right fields가 있고,
next는 다음 header node를, down은 같은 column의 다음 nonzero node를, right는 같은 row의 다음 nonzero node를 가리킨다.
entry node는 row, col, val, down, right fields가 있고,
앞 세개는 배열에 저장했던 것처럼 세정보가 저장된다.
down과 right도 header node와 같다.
각 row와 col과 header node는 circular list가 되도록 구현한다.
그림을 보고 오해하면 안되는게,
row i의 header node는 column i의 header node 역할도 한다.
즉, 그림에선 잘 보이게하려고 H0, H1 등을 두개씩 적었지만 사실 저 둘은 같은 node이다.
모든 header node의 header도 있다.(H) 여기에 row개수, col개수, term개수를 저장하기때문에 얘는 entry node이다. header들도 모두 이 header와 함께 circular list로 연결된다.
예시)
<i,j>의 값이 non zero가면 이를 sparse matrix에 넣어야하는데,
row i와 column j에 모두 연결시켜야 한다. 즉 i header와 j header 두개의 다른 list에 연결된다.
Representation implementation
header와 entry가 다른 node이지만,
공통되는 부분이 있기도 하고 둘을 같이 취급하기위해서
union을 이용해 하나의 structure로 구현한다.
(구분을 위해 enum tagField도 사용한다.)
#define MAX_SIZE 50
typedef enum {head, entry} tagfield;
typedef struct {
int row;
int col;
int val;
} entryNode;
typedef matrixNode *matrixPointer
typedef struct {
matrixPointer down;
matrixPointer right;
tagfield tag;
union {
matrixPointer next; //header node
entryNode entry; //entry node
} u;
} matrixNode;4.7.2 Sparse Matrix Input
header node의 수는 max(numRows, numCols)이다.
header의 next를 처음에는 해당 행(column)의 마지막 node를 따라가도록 함.
code내의 last 포인터는 해당 열(row)의 마지막 node를 따라고도록 함.
왜냐하면 바로바로 해당 (row,col)에 대해 나오면 붙여야되니까.
다 하고 마지막에 header들 next로 연결.
자세한 code는 p.182
4.7.3 Sparse Matrix Output
print하기..
p.184
4.7.4 Erasing a Sparse Matrix
전부 free 이용해서 system에 return하기
p.185
4.8 DOUBLY LINKED LISTS
singly linked list는 몇몇 제한사항이 있다.
한 방향으로만 갈 수 있기 때문에, p위치에서 이전 위치로 가려면 처음부터 시작하거나 그 이전위치에서 시작해야 한다.
또 삭제를 하려면 이전 node의 정보가 필요하기때문에 막 삭제할 순 없었다.
이 제한사항을 극복하기위해 Doubly linked list를 사용한다.
두개의 link fields를 가진다. 하나는 이전 node를, 하나는 다음 node를 가리킨다.
typedef struct node *nodePointer;
typedef struct node {
nodePointer llink;
int data;
nodePointer rlink;
} node;Circular 일수도 있고, 아닐수도 있다.
앞서 봤듯이 Header node가 있으면 좀 간편해질 수 있기 때문에 집어 넣는것도 좋다.
insertion/deletion 간단하게 작성된다.(p.188/p.189)
(여기 code는 header node 있다고 가정하고 작성돼있음)
