Übungsblatt 2, Aufgabe 2

ADS_2.2_acritox.cpp

# kompilieren:
g++ -o ADS_2.2_acritox -Wall ADS_2.2_acritox.cpp

# ausführen:
./ADS_2.2_acritox
head: 0x83B8008, tail: 0x83B8018     
node 0: 0x83B8028                    
node 1: 0x83B8038                    
node 2: 0x83B8048                    
node 3: 0x83B8058                    
node 4: 0x83B8068                    
node 5: 0x83B8078                    
node 6: 0x83B8088                    
node 7: 0x83B8098                    
node 8: 0x83B80A8                    
node 9: 0x83B80B8                    
node 10: 0x83B80C8                   
node 11: 0x83B80D8
node 12: 0x83B80E8
node 13: 0x83B80F8
node 14: 0x83B8108
node 15: 0x83B8118
node 16: 0x83B8128

list:
data: 0, addr: 0x83B8028, prev: 0x83B8008, next: 0x83B8038, np: 0x30
data: 1, addr: 0x83B8038, prev: 0x83B8028, next: 0x83B8048, np: 0x60
data: 2, addr: 0x83B8048, prev: 0x83B8038, next: 0x83B8058, np: 0x60
data: 3, addr: 0x83B8058, prev: 0x83B8048, next: 0x83B8068, np: 0x20
data: 4, addr: 0x83B8068, prev: 0x83B8058, next: 0x83B8078, np: 0x20
data: 5, addr: 0x83B8078, prev: 0x83B8068, next: 0x83B8088, np: 0xE0
data: 6, addr: 0x83B8088, prev: 0x83B8078, next: 0x83B8098, np: 0xE0
data: 7, addr: 0x83B8098, prev: 0x83B8088, next: 0x83B80A8, np: 0x20
data: 8, addr: 0x83B80A8, prev: 0x83B8098, next: 0x83B80B8, np: 0x20
data: 9, addr: 0x83B80B8, prev: 0x83B80A8, next: 0x83B80C8, np: 0x60
data: 10, addr: 0x83B80C8, prev: 0x83B80B8, next: 0x83B80D8, np: 0x60
data: 11, addr: 0x83B80D8, prev: 0x83B80C8, next: 0x83B80E8, np: 0x20
data: 12, addr: 0x83B80E8, prev: 0x83B80D8, next: 0x83B80F8, np: 0x20
data: 13, addr: 0x83B80F8, prev: 0x83B80E8, next: 0x83B8108, np: 0x1E0
data: 14, addr: 0x83B8108, prev: 0x83B80F8, next: 0x83B8118, np: 0x1E0
data: 15, addr: 0x83B8118, prev: 0x83B8108, next: 0x83B8128, np: 0x20
data: 16, addr: 0x83B8128, prev: 0x83B8118, next: 0x83B8018, np: 0x100

found node with value 7 at 0x83B8098, will delete the next 4 nodes now.
deleted node (data: 8, addr: 0x83B80A8)
deleted node (data: 9, addr: 0x83B80B8)
deleted node (data: 10, addr: 0x83B80C8)
deleted node (data: 11, addr: 0x83B80D8)

mirrored list:
data: 16, addr: 0x83B8128, prev: 0x83B8018, next: 0x83B8118, np: 0x100
data: 15, addr: 0x83B8118, prev: 0x83B8128, next: 0x83B8108, np: 0x20
data: 14, addr: 0x83B8108, prev: 0x83B8118, next: 0x83B80F8, np: 0x1E0
data: 13, addr: 0x83B80F8, prev: 0x83B8108, next: 0x83B80E8, np: 0x1E0
data: 12, addr: 0x83B80E8, prev: 0x83B80F8, next: 0x83B8098, np: 0x60
data: 7, addr: 0x83B8098, prev: 0x83B80E8, next: 0x83B8088, np: 0x60
data: 6, addr: 0x83B8088, prev: 0x83B8098, next: 0x83B8078, np: 0xE0
data: 5, addr: 0x83B8078, prev: 0x83B8088, next: 0x83B8068, np: 0xE0
data: 4, addr: 0x83B8068, prev: 0x83B8078, next: 0x83B8058, np: 0x20
data: 3, addr: 0x83B8058, prev: 0x83B8068, next: 0x83B8048, np: 0x20
data: 2, addr: 0x83B8048, prev: 0x83B8058, next: 0x83B8038, np: 0x60
data: 1, addr: 0x83B8038, prev: 0x83B8048, next: 0x83B8028, np: 0x60
data: 0, addr: 0x83B8028, prev: 0x83B8038, next: 0x83B8008, np: 0x30

// ADS, Uebungsblatt 2, Aufgabe 2
// 03.11.2009
// Andreas Loibl <aloibl@mytum.de>
 
#include <stdio.h>
#include <stdlib.h>
 
struct node
{
	int data;
	unsigned int np;
};
 
node *new_node()
{
	node *n = (node *) malloc(sizeof(node));
	n->np = NULL;
	return n;
}
 
node *next(node *cur, node *prev)
{
	return (struct node*)(cur->np ^ (unsigned int)prev);
}
 
node *prev(node *cur, node *next)
{
	return (struct node*)(cur->np ^ (unsigned int)next);
}
 
node *insert(node *after, node *before, int data)
{
	node *tmp = new_node();
	tmp->data = data;
	tmp->np = (unsigned int)after ^ (unsigned int)before;
	after->np ^= (unsigned int)before ^ (unsigned int)tmp;
	before->np ^= (unsigned int)after ^ (unsigned int)tmp;
	return tmp;
}
 
node *search_node(int value, node *head, node *tail, node** prev_ptr)
{
	node *next_ptr = NULL;
	*prev_ptr = NULL;
	node *cur_ptr = head;
 
	while(next(cur_ptr, *prev_ptr)!=tail)
	{
		next_ptr = next(cur_ptr, *prev_ptr);
		*prev_ptr = cur_ptr;
		cur_ptr = next_ptr;
		if(cur_ptr->data == value) return cur_ptr;
	}
	return NULL;
}
 
void delete_node(node *prev_ptr, node *del)
{
	node *next_ptr = next(del, prev_ptr);
	prev_ptr->np ^= (unsigned int)del;
	prev_ptr->np ^= (unsigned int)next_ptr;
	next_ptr->np ^= (unsigned int)del;
	next_ptr->np ^= (unsigned int)prev_ptr;
	free(del);	
}
 
int main(int argc, char *argv[])
{
	node *head = new_node();
	node *tail = new_node();
	head->np = (unsigned int)tail;
	tail->np = (unsigned int)head;
	node *cur_ptr = head;
	node *prev_ptr = NULL;
	node *next_ptr = NULL;
 
	printf("head: 0x%X, ", (unsigned int)head);
	printf("tail: 0x%X\n", (unsigned int)tail);
 
	// fill list
	for(int i=0; i < 17; i++)
	{
		cur_ptr = insert(cur_ptr, tail, i);
		printf("node %d: 0x%X\n", i, (unsigned int)cur_ptr);
	}
 
	// search node with value 7
	if((cur_ptr = search_node(7, head, tail, &amp;prev_ptr)))
	{
		// delete the following 4 nodes (8,9,10,11)
		for(int i=0; i < 4; i++)
		{
			delete_node(cur_ptr, next(cur_ptr, prev_ptr));
		}
	}
 
	// mirror
	node *tmp;
	tmp = head;
	head = tail;
	tail = tmp;
 
	// delete all nodes
	prev_ptr = NULL; cur_ptr = head;
	while(next(cur_ptr, prev_ptr)!=tail)
	{
		delete_node(cur_ptr, next(cur_ptr, prev_ptr));
	}
 
	// delete head and tail
	free(head);
	free(tail);
 
	return 0;
}

ADS_2.2_acritox.cpp