연결리스트의응용 류관희 충북대학교 1
체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2
체인연산 체인을역순으로만드는 (inverting) 연산 연산시간 O(length) listpointer invert(listpointer lead) { /* lead 가가리키고있는리스트를역순으로만든다. */ listpointer middle, trail; middle = NULL; while (lead) { trail = middle; middle = lead; lead = lead->link; middle->link = trail; return middle; 단순연결리스트를역순으로만드는함수 3
체인연산 두개의체인 ptr1 과 ptr2 를연결 (concatenation) 하는연산 listpointer concatenate(listpointer ptr1, listpointer ptr2) { /* 리스트 ptr1 뒤에리스트 ptr2 가연결된새로운리스트를생성한다. ptr1 이가리키는리스트는영구히바뀐다. */ listpointer temp; /* check for empty lists */ if(!ptr1) return ptr2; if(!ptr2) return ptr1; /* neither list is empty, find end of first list */ for(temp = ptr1; temp->link; temp = temp->link) ; /* link end of first to start of second */ temp->link = ptr2; 단순연결리스트의연결 4
원형연결리스트연산 리스트의마지막노드에대한포인터 last 를유지함으로써앞이나뒤양쪽에쉽게원소를삽입가능 리스트의앞에삽입 5 void insertfront(listpointer *last, listpointer node) { /* 리스트의마지막노드가 last 인원형리스트의앞에노드를삽입한다. */ if (IS_EMPTY(*first)) { /* 리스트가공백일경우, last 이새로운항목을가리키도록변경시킨다. */ *last = node; node->link = node; else { /* 리스트가공백이아닌경우, 리스트의앞에새로운항목을삽입시킨다. */ node->link = (*last)->link; (*last)->link = node;
원형연결리스트연산 원형리스트의길이계산 int length(listpointer last) {/* 원형리스트 last 의길이를계산한다. */ listpointer temp; int count = 0; if (last) { temp = last; do { count++; temp = temp->link; while (temp!= last); return count; 6
Sparse Matrices 0 12 0 0 0 0 4 0 11 0 0 0 0 0 0 15 inadequacies of sequential schemes (1) # of nonzero terms will vary after some matrix computation (2) matrix just represents intermediate results new scheme Each column (row): a circular linked list with a head node 7
Revisit Sparse Matrices # of head nodes = max{# of rows, # of columns head node down head right next entry node down entry row col value right aij entry i j aij 8
Linked Representation for Matrix 4 4 0 2 11 1 0 12 1 1 5 2 1-4 Circular linked list 3 3-15 9
#define MAX_SIZE 50 /* size of largest matrix */ typedef enum {head, entry tagfield; typedef struct matrix_node *matrix_pointer; typedef struct entry_node { int row; int col; int value; ; typedef struct matrix_node { matrix_pointer down; matrix_pointer right; tagfield tag; union { matrix_pointer next; entry_node entry; u; ; matrix_pointer hdnode[max_size]; 10
Sample input for sparse matrix [0] [1] [2] [3] [4] [0] [1] [2] 4 4 4 0 2 11 1 0 12 2 1-4 3 3-15 11
Read in a Matrix matrix_pointer mread(void) { /* read in a matrix and set up its linked list. An global array hdnode is used */ int num_rows, num_cols, num_terms; int num_heads, i; int row, col, value, current_row; matrix_pointer temp, last, node; printf( Enter the number of rows, columns and number of nonzero terms: ); 12
scanf( %d%d%d, &num_rows, &num_cols, &num_terms); num_heads = (num_cols>num_rows)? num_cols : num_rows; /* set up head node for the list of head nodes */ node = new_node(); node->tag = entry; node->u.entry.row = num_rows; node->u.entry.col = num_cols; if (!num_heads) node->right = node; else { /* initialize the head nodes */ for (i=0; i<num_heads; i++) { term= new_node(); O(max(n,m)) hdnode[i] = temp; hdnode[i]->tag = head; hdnode[i]->right = temp; hdnode[i]->u.next = temp; 13
current_row= 0; last= hdnode[0]; for (i=0; i<num_terms; i++) { printf( Enter row, column and value: ); scanf( %d%d%d, &row, &col, &value); if (row>current_row) { last->right= hdnode[current_row]; current_row= row; last=hdnode[row]; temp = new_node(); temp->tag=entry; temp->u.entry.row=row; temp->u.entry.col = col; temp->u.entry.value = value; last->right = temp;/*link to row list */ last= temp; /* link to column list */ hdnode[col]->u.next->down = temp; hdnode[col]=>u.next = temp; 14
/*close last row */ last->right = hdnode[current_row]; /* close all column lists */ for (i=0; i<num_cols; i++) hdnode[i]->u.next->down = hdnode[i]; /* link all head nodes together */ for (i=0; i<num_heads-1; i++) hdnode[i]->u.next = hdnode[i+1]; hdnode[num_heads-1]->u.next= node; node->right = hdnode[0]; return node; O(max{#_rows, #_cols+#_terms) 15
void mwrite(matrix_pointer node) { /* print out the matrix in row major form */ int i; matrix_pointer temp, head = node->right; Write out a Matrix printf( \n num_rows = %d, num_cols= %d\n, node->u.entry.row,node->u.entry.col); printf( The matrix by row, column, and value:\n\n ); for (i=0; i<node->u.entry.row; i++) { for (temp=head->right;temp!=head;temp=temp->right) printf( %5d%5d%5d\n, temp->u.entry.row, temp->u.entry.col, temp->u.entry.value); head= head->u.next; /* next row */ 16
Erase a Matrix void merase(matrix_pointer *node) { int i, num_heads; matrix_pointer x, y, head = (*node)->right; for(i=0; i<(*node)->u.entry.row; i++) { y=head->right; while (y!=head) { x = y; y = y->right; free(x); x= head; head= head->u.next; free(x); y = head; while (y!=*node) { x = y; y = y->u.next; free(x); free(*node); *node = NULL; O(#_rows+#_cols+#_terms) 17
Doubly Linked Lists We can move easily only in the direction of the links in singly linked list. To move in either direction, it is useful to have doubly linked lists. typedef struct node *node_pointer; typedef struct node { node_pointer llink; element item; node_pointer rlink; ptr = ptr->llink->rlink = ptr->rlink->llink 18
(ex) Doubly linked circular list Head Node llink item rlink ptr 19
(ex) Insertion node node new node void dinsert(nodepointer node, nodepointer newnode) { /* newnode 를 node 의오른쪽에삽입 */ newnode->llink = node; newnode->rlink = node->rlink; node->rlink->llink = newnode; node->rlink = newnode; 20
(ex) Deletion node node deleted void ddelete(nodepointer node, nodepointer deleted) { /* 이중연결리스트에서삭제 */ if (node == deleted) printf("deletion of head node not permitted.\n"); else { deleted->llink->rlink = deleted->rlink; deleted->rlink->llink = deleted->link; free(deleted); 21