A Journey 2 Eternity

Archive for August 2008

When we want to remove all the elements from a linked list, the natural inclination is to use a single pointer to traverse the list, freeing elements as we go. A problem arises, however, when this is implemented. Do we advance the pointer or free the element first? If we advance the pointer first, then the freeing is impossible because we overwrote the pointer to the element to be freed. If we free the element first, advancing the pointer is impossible because it involves reading the next pointer in the element that was just freed. The solution is to use two pointers.

void DeleteAllElement( ListElement **head )
{
	ListElement *deleteMe = *head;
	while( deleteMe ) {
		ListElement *next = deleteMe->next;
		delete deleteMe;

		deleteMe = next;
	}

	*head = NULL;
}

Because elements in a singly-linked list are maintained exclusively with links to the next element, any insertion or deletion of elements in the middle of a list requires modification of the previous element’s link. This may require a traversal of the list, because there’s no other way to find a preceding element. Special care must be taken when dealing with the head of the list.

bool DeleteElement( ListElement **head, ListElement *deleteMe )
{
	ListElement *elem = *head;

	// special case for head
	if( deleteMe == *head ) {
		*head = elem->next;
		delete deleteMe;

		return true;
	}

	while( elem ) {
		if( elem->next == deleteMe ) {
			// elem is element preceding deleteMe
			elem->next = deleteMe->next;
			delete deleteMe;

			return true;
		}
		elem = elem->next;
	}

	// not found
	return false;
}

Operations on any but the first element of a linked list require traversal of some elements of the list, and you must always check for the end of the list.

ListElement Find( ListElement head, int data )
{
	while( head != NULL && head.data != data ) {
		head = head.next;
	}

	return head;
}

The head element of a singly-linked list must always be tracked; otherwise, the list will be lost in memory. This means that the pointer or reference to the head of the list must be updated when a new element is inserted ahead of the first element or when the existing first element is removed from the list. Tracking the head element becomes a problem when you alter the list inside a function or method, because the caller must be made aware of the new head element.

bool InsertInFront( ListElement **head, int data )
{
	ListElement *newElem = new ListElement;
	if( !newElem ) {
		return false;
	}

	newElen->data = data;
	*head = newElem;

	return true;
}

There are three basic kinds of linked list: singly-linked lists, doubly-linked lists and circularly-linked lists. The linked lists figure is below.

Singly-Linked Lists

Singly-Linked Lists

Doubly-Linked Lists

Doubly-Linked Lists

Declaration:

typedef struct ListElement
{
	struct ListElement *next;
	int data;
} ListElement;

typedef struct DoublyLinkedList
{
	struct DoublyLinkedList *next;
	struct DoublyLinkedList *prev;

	int data;
} DoublyLinkedList;

Just override the CHtmlView::OnShowContextMenu funcion and return S_OK.

HRESULT CWebBrowserView::OnShowContextMenu(DWORD dwID, LPPOINT ppt, LPUNKNOWN pcmdtReserved, LPDISPATCH pdispReserved)
{
	CMenu menu;
	int pMenuID = 0;

	VERIFY(menu.LoadMenu(IDR_WEBBROWSER));
	CMenu* pPopup = menu.GetSubMenu(pMenuID);
	ASSERT(pPopup != NULL);

	pPopup->TrackPopupMenu(TPM_LEFTALIGN |TPM_RIGHTBUTTON, ppt->x, ppt->y, this);

	return S_OK;

	// Don’t call the base version
	//return CHtmlView::OnShowContextMenu(DWORD dwID, LPPOINT ppt, LPUNKNOWN pcmdtReserved, LPDISPATCH pdispReserved);
}
Tags: ,

Just override the CHtmlView::OnShowContextMenu funcion and return S_OK.

HRESULT CWebBrowserView::OnShowContextMenu(DWORD dwID, LPPOINT ppt, LPUNKNOWN pcmdtReserved, LPDISPATCH pdispReserved)
{
	return S_OK;

	// Don’t call the base version
	//return CHtmlView::OnShowContextMenu(DWORD dwID, LPPOINT ppt, LPUNKNOWN pcmdtReserved, LPDISPATCH pdispReserved);
}
Tags: ,

Pages

Categories

August 2008
M T W T F S S
« Apr   Sep »
 123
45678910
11121314151617
18192021222324
25262728293031

Blog Stats

  • 26,880 hits