Solution to 10.3-5 in Introduction to Algorithms, Third Edition
#include <stdio.h>int next;int key;int prev;int L;int F;void print_array();void print_list(int);void print_lists();void create();void exchange(int, int);void compactify_list();void swap_next(int, int);void swap_key(int, int);void swap_prev(int, int);void swap(int, int);void create() {next = 0;key = 0;prev = 0;L = 7;next = 5;key = 9;prev = 0;next = 2;key = 16;prev = 7;next = 3;key = 4;prev = 5;next = 0;key = 1;prev = 2;F = 6;next = 4;key = -1;prev = 0;next = 8;key = -1;prev = 6;next = 1;key = -1;prev = 4;next = 0;key = -1;prev = 8;}void swap_next(int a, int b) {int temp;temp = next;next = next;next = temp;}void swap_key(int a, int b) {int temp;temp = key;key = key;key = temp;}void swap_prev(int a, int b) {int temp;temp = prev;prev = prev;prev = temp;}void swap(int a, int b) {swap_next(a, b);swap_key(a, b);swap_prev(a, b);}void exchange(int h, int x) {if (next == h) { if (prev != 0) next]= h; if (next != 0) prev] = x; swap_key(h, x); next = next; prev = prev; prev = h; next = x;} else { if (prev != 0) next] = x; if (next != 0) prev] = x; if (prev != 0) next] = h; if (next != 0) prev] = h; swap(h, x);}}void compactify_list() {int h = 1;int x = L;while (x != 0) { if (x != h) { if (h == F) F = x; exchange(h, x); } x = next; h++;}L = 1;}void print_list(int i) {while (i != 0) { printf("index: %d, next: %d, key: %d, prev: %d\n", i, next, key, prev); i = next;}}void print_lists() {printf("------- doubly linked list ----------------\n");print_list(L);printf("------- free list ----------------\n");print_list(F);}void print_array() {int i;printf("------- array ----------------\n");for (i = 1; i < 9; i++) { printf("index: %d, next: %d, key: %d, prev: %d\n", i, next, key, prev);} }int main(int argc, const char *argv[]) {create();print_array();compactify_list();print_lists();return 0;}
页:
[1]