Journal Articles
Browse in : |
All
> Journals
> CVu
> 115
(21)
|
Note: when you create a new publication type, the articles module will automatically use the templates user-display-[publicationtype].xt and user-summary-[publicationtype].xt. If those templates do not exist when you try to preview or display a new article, you'll get this warning :-) Please place your own templates in themes/yourtheme/modules/articles . The templates will get the extension .xt there.
Title: Difference Structures in C/C++
Author: Administrator
Date: 03 August 1999 13:15:32 +01:00 or Tue, 03 August 1999 13:15:32 +01:00
Summary:
Body:
Difference structures are a Prolog technique but they can be adapted to C and C++ as follows: Imagine having a linked list, but as well as a pointer to the head of the list you also have a pointer to its last element. (When the list is empty or there is only one item, the two pointers will be equal.) Code to maintain such a list shouldn't be too difficult if you can write linked list code, so I'll leave it as an exercise but I'll assume you're using:
typedef struct Item { void* data; struct Item* next; } Item; typedef struct { Item* firstElement; Item* lastElement; } List;
(In C++ you would of course use a class with methods and possibly a template, but I won't do that here for the benefit of the C programmers.)
With a pointer to the last element, you can do some powerful things. For example, you can concatenate two lists very quickly:
void concat(List* first, const List* second) { if (first->lastElement) first->lastElement->next=second->firstElement; if (second->lastElement) first->lastElement=second->lastElement; }
(Note that no copy of the second list is made.) Or if you want a queue:
void queueItem(List* addTo,void* d) { Item* i=malloc(sizeof(Item)); i->data=d; i->next=NULL; if (addTo->lastElement) addTo->lastElement->next=i; else addTo->firstElement=i; addTo->lastElement=i; } void* getItem(List* getFrom) { void* ret=NULL; Item* i=getFrom->firstElement; if (i) { getFrom->firstElement=getFrom->firstElement->next; if(!(getFrom->firstElement)) getFrom->lastElement=NULL; ret=i->data; free(i); } return ret; }
Some implementations of queues use doubly-linked lists, but the above uses less memory. You can also rotate a list quickly (but only in one direction with single links):
void rotate(List* l) { if(l->firstElement) { l->lastElement->next=l->firstElement; l->lastElement=l->firstElement; l->firstElement=l->firstElement->next; l->lastElement->next=NULL; } }
When writing code like that you have to keep a clear head. The order of assignments is crucial - if in doubt, simulate on paper. Bearing in mind that one or more of the parameters might be an empty list is also important (although it is reasonable to insist that the parameters themselves will not be NULL - add asserts if desired).
Notes:
More fields may be available via dynamicdata ..