/*Hello again flipcoders. To compliment my recently posted array routines,here's my assortment of useful templated list routines.Some of these are quite basic routines, some are not, however i'msurprised by how many people have trouble writing basic list routines.I'm fairly sure these are also bug free, (I've tested them thoroughly)but if you find a bug, or have other suggestions or comments, let me know.If nothing more these should be very useful to beginners.To use these all you need to do is have a list (any type) anddefine a few operators for that data type. Allocation and deallocationis done by the caller. Note, this code also assumes that your next-itempointer is called 'next'.For example given the following data type:typedef unsigned short keyType;typedef struct item { item *next; keyType key; long foo; char bar;};The routines will require that you define the following:inline int operator < (item &a, item &b) {return a.key < b.key;}inline int operator == (item &a, item &b) {return a.key == b.key;}If the key is not the entire item, also define these:inline int operator < (item &a, keyType b) {return a.key < b;}inline int operator == (item &a, keyType b) {return a.key == b;}You can then use the routines below like this:item *myList = NULL;for (int i=1; i<100; ++i) { item *addMe = new item; item.key = rand(); Push(myList, addMe);}MergeSort(myList);I hope the rest is mostly self-explanatory.Written on a Mac using Symantec C++ v8.6.Permission to use/copy/modify/distribute hereby granted.[NZ]_i/\/\alc(Malcolm)*/#ifndef MyListUtils#define MyListUtils//This macro is a trick of mine I've never seen used before, it provides a fake//previous-item pointer for the head of the list, so that the special case of//removing an item from the head of the list etc, is eliminated.//However only prev->next actually exists. Accessing the other fields would be bad.//T is the node type, H is the head variable, N is the name of the next ptr.#define fakePrev(T, H, N) (T*)(((unsigned long)&H) + ((unsigned long)H) - ((unsigned long)&H->N))//#define USE_TAIL true //Uncomment if you also wish to keep track //of the end of the list so that inserting at the end is faster.// *** Utilities ***// Returns first item, pointless yeah, but here for completenesstemplate <class TItem>inline TItem *headPeek(TItem *head) { return head;}// Returns last itemtemplate <class TItem>TItem *tailPeek(TItem *head) { TItem *curr = head, *prev = NULL; while (curr != NULL) { prev = curr; curr = curr->next; } return prev;}// Returns true if the list is sortedtemplate <class TItem>Boolean Sorted(TItem *head) { if (head != NULL) { item *other = head->next; while (other != NULL) { if (*other < *head) return false; head = other; other = other->next; } } return true;}// Returns the number of items in the listtemplate <class TItem>inline int ListCount(TItem *head) { int count = 0; while (head != NULL) { ++count; head = head->next; } return count;}// Reverses the listtemplate <class TItem>void Reverse(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { if (head != NULL) {#ifdef USE_TAIL tail = head;#endif TItem *newList = head, *oldList = head->next, *temp; newList->next = NULL; while (oldList != NULL) { temp = oldList; oldList = oldList->next; temp->next = newList; newList = temp; } head = newList; }}// Insert a caller-allocated item at the headtemplate <class TItem>void Push(TItem *&head, TItem *ins#ifdef USE_TAIL , TItem *&tail#endif) {#ifdef USE_TAIL if (head == NULL) tail = ins;#endif ins->next = head; head = ins;}// Insert a caller-allocated item at the tailtemplate <class TItem>void Put(TItem *&head, TItem *ins#ifdef USE_TAIL , TItem *&tail#endif) {#ifdef USE_TAIL if (head == NULL) { head = ins; } else { tail->next = ins; } tail = ins;#else TItem *curr = head, *prev = fakePrev(TItem, head, next);//= NULL; while (curr != NULL) { prev = curr; curr = curr->next; } /*if (prev == NULL) //fakePrev eliminates this head = ins; else*/ prev->next = ins; #endif ins->next = NULL;}// Take off item at the head - caller responsible for deallocationtemplate <class TItem>TItem *Pop(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { TItem *temp = head; if (head != NULL) head = head->next;#ifdef USE_TAIL if (head == NULL) tail = NULL;#endif return temp;}// Insert a caller-allocated item into an ordered listtemplate <class TItem>void Insert(TItem *&head, TItem *ins#ifdef USE_TAIL , TItem *&tail#endif) { TItem *curr = head, *prev = fakePrev(TItem, head, next);//= NULL; while (curr != NULL) { if (*ins < *curr) break; prev = curr; curr = curr->next; } /*if (prev == NULL) //fakePrev eliminates this head = ins; else*/ prev->next = ins; ins->next = curr;#ifdef USE_TAIL if (curr == NULL) tail = ins;#endif}// Remove selected item - caller responsible for deallocationtemplate <class TItem>void Remove(TItem *&head, TItem *rem#ifdef USE_TAIL , TItem *&tail#endif) { TItem *curr = head, *after, *prev = fakePrev(TItem, head, next);//= NULL; while (curr != NULL) { after = curr->next; if (curr == rem) { /*if (prev == NULL) //fakePrev eliminates this head = ins; else*/ prev->next = after;#ifdef USE_TAIL if (head == NULL) tail = NULL;#endif break; } prev = curr; curr = after; }}// *** Searching ***// O(n) : sorted onlytemplate <class TItem, class TKey>TItem *SortedSequentialSearch(TItem *head, TKey find) { for (; head != NULL; head = head->next) if (*head < find) continue; else if (*head == find) return head; else return NULL; return NULL;}// O(n)template <class TItem, class TKey>inline TItem *SequentialSearch(TItem *head, TKey find) { for (; head != NULL; head = head->next) if (*head == find) return head; return NULL;}// *** Combining ***// O(m+n) : both lists sorted onlytemplate <class TItem>TItem *MergeLists(TItem *head1, TItem *head2#ifdef USE_TAIL , TItem *&tail#endif) { if (head1 == NULL) {#ifdef USE_TAIL tail = tailPeek(head2);#endif return head2; } if (head2 == NULL) {#ifdef USE_TAIL tail = tailPeek(head1);#endif return head1; } TItem *combined = NULL, *newTail = fakePrev(TItem, combined, next); do { if (*head1 < *head2) { newTail->next = head1; newTail = head1; head1 = head1->next; if (head1 != NULL) continue; newTail->next = head2;#ifdef USE_TAIL tail = tailPeek(newTail);#endif return combined; } else { newTail->next = head2; newTail = head2; head2 = head2->next; if (head2 != NULL) continue; newTail->next = head1;#ifdef USE_TAIL tail = tailPeek(newTail);#endif return combined; } } while (true);}// *** Sorting ***// O(nlogn) : uses stack memorytemplate <class TItem>void MergeSort(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { if (head != NULL) { if (head->next != NULL) { //Must be at least 2 items TItem *oldhead=head, *heads[2], *tails[2]; int sortMore[2], largest, appendWhichList; sortMore[0] = sortMore[1] = false; heads[0] = tails[0] = oldhead; oldhead = oldhead->next; heads[1] = tails[1] = oldhead; oldhead = oldhead->next; largest = (*tails[1] < *tails[0] ? 0 : 1); while (oldhead != NULL) { //Split up old list if (*tails[largest] < *oldhead) { appendWhichList = largest; } else if (*oldhead < *tails[1-largest]) { appendWhichList = largest; sortMore[largest] = true; largest = 1-largest; } else { appendWhichList = 1-largest; } tails[appendWhichList]->next = oldhead; tails[appendWhichList] = oldhead; oldhead = oldhead->next; } tails[0]->next = NULL; if (sortMore[0]) MergeSort(heads[0]#ifdef USE_TAIL , tails[0]#endif ); tails[1]->next = NULL; if (sortMore[1]) MergeSort(heads[1]#ifdef USE_TAIL , tails[1]#endif ); head = MergeLists(heads[0], heads[1]#ifdef USE_TAIL , tail#endif ); } }}template <class TItem>TItem *QuickSortAux(TItem *&head) { TItem *curr = head->next; if (curr != NULL) { TItem *center = head, *less = NULL, *greater = NULL; do { TItem *after = curr->next; if (*curr < *center) { curr->next = less; less = curr; } else { curr->next = greater; greater = curr; } curr = after; } while (curr != NULL); if (less != NULL) { TItem *last = QuickSortAux(less); last->next = center; head = less; } else { head = center; } if (greater != NULL) { TItem *last = QuickSortAux(greater); center->next = greater; return last; } else { center->next = NULL; return center; } } return head;}// O(nlogn) .. O(n^2) : uses stack memorytemplate <class TItem>inline void QuickSort(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) {#ifndef USE_TAIL TItem *tail;#endif if (head != NULL) tail = QuickSortAux(head);}// O(n) .. O(n^2) : Stabletemplate <class TItem>void InsertionSort(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { TItem *newList = NULL, *oldList = head, *temp, *curr, *prev; while (oldList != NULL) { temp = oldList; oldList = oldList->next; curr = newList, prev = fakePrev(TItem, newList, next); while (curr != NULL) { if (*temp < *curr) break; prev = curr; curr = curr->next; } prev->next = temp; temp->next = curr;#ifdef USE_TAIL if (curr == NULL) tail = temp;#endif } head = newList;}// O(n^2) : Stabletemplate <class TItem>void DualSelectionSort(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { TItem *unsortedhead=head, *curr, *prev; TItem *highhead=NULL, *hightail=NULL, *currhighprev, *movehigh; TItem *lowhead=NULL, *lowtail=NULL, *currlowprev, *movelow; while (unsortedhead != NULL) { curr = unsortedhead; currlowprev = currhighprev = prev = fakePrev(TItem, unsortedhead, next); do { if (*curr < *currlowprev->next) currlowprev = prev; //if (*currhighprev->next < *curr) //Faster, non-stable if (!(*curr < *currhighprev->next)) //Slower, Stable currhighprev = prev; prev = curr; curr = curr->next; } while (curr != NULL); if (currlowprev == currhighprev) break; movehigh = currhighprev->next; movelow = currlowprev->next; if (movehigh == currlowprev) currlowprev = currhighprev; currhighprev->next = movehigh->next; currlowprev->next = movelow->next; if (highhead == NULL) hightail = movehigh; movehigh->next = highhead; highhead = movehigh; if (lowhead == NULL) { lowhead = movelow; } else { lowtail->next = movelow; } lowtail = movelow; } if (lowhead != NULL) { head = lowhead; if (unsortedhead != NULL) { lowtail->next = unsortedhead; prev->next = highhead; } else { lowtail->next = highhead; } #ifdef USE_TAIL tail = hightail; #endif }}// O(n^2) : Stabletemplate <class TItem>void SelectionSort(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { TItem *unsortedhead=head, *curr, *prev; TItem *lowhead=NULL, *lowtail=NULL, *currlowprev, *movelow; while (unsortedhead != NULL) { curr = unsortedhead; currlowprev = prev = fakePrev(TItem, unsortedhead, next); do { if (*curr < *currlowprev->next) currlowprev = prev; prev = curr; curr = curr->next; } while (curr != NULL); movelow = currlowprev->next; currlowprev->next = movelow->next; if (lowhead == NULL) lowhead = movelow; else lowtail->next = movelow; lowtail = movelow; } head = lowhead;#ifdef USE_TAIL tail = lowtail;#endif}// O(n^2) : Stabletemplate <class TItem>void BubbleSort(TItem *&head#ifdef USE_TAIL , TItem *&tail#endif) { TItem *stophere = NULL; while (head != stophere) { TItem *curr = head, *prev = fakePrev(TItem, head, next); TItem *after = curr->next; while (after != stophere) { if (*after < *curr) { curr->next = after->next; prev->next = after; after->next = curr; } prev = curr; curr = after; after = after->next; }#ifdef USE_TAIL if (stophere == NULL) tail = curr;#endif stophere = curr; }}#endif |
