Lösung zu Blatt 5 der Systemnahe Software I (WS 97/98)

8.1 Tauschen

#include<stdio.h>

void swap(int *a, int *b) {
   int temp = *a;
   *a = *b;
   *b = temp;
}

void main() {
   int i = 17, j = 20;
   printf("Before swap: %d, %d.\n", i, j);
   swap(&i, &j);
   printf("After swap:  %d, %d.\n", i, j);
   exit(0);
}

8.2 Doppelte Liste

/* ein kleines Listenpogramm */

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef int BOOL;

typedef struct node *ListPtr;
typedef struct node { /*Listenelement */
   int key;
   ListPtr prev, next;
} listNode;

BOOL insert(ListPtr *pt, int key) {
   ListPtr newp = (ListPtr)calloc(1, sizeof(listNode)), p = *pt;
   if (!newp) return FALSE; /* Out of memory */
   newp->next = NULL;       /* init new element */
   newp->key = key;
   if (!p) { 
      newp->prev = NULL;
      *pt = newp;
   } else {
      while (p->next) p = p->next;
      p->next = newp;
      newp->prev = p;
   }
   return TRUE;
}

void print(ListPtr p) {
   while (p->prev) p = p->prev;
   while (p) {
      printf("%d", p->key);
      printf(" | ");
      p = p->next;
   }
   printf("\n");
}

ListPtr search(ListPtr p, int key) {
   while (p->prev) p = p->prev;
   while (p && (p->key != key)) p = p->next;
   return (p)?p:NULL;
}

BOOL delete_one(ListPtr *pt, int key) {
   ListPtr p = *pt;
   if (!*pt) return FALSE;
   if (p->key == key) { if (p->next) *pt = p->next; else *pt = p->prev; }
   while (p->prev) p = p->prev;
   while (p && (p->key != key)) p = p->next;
   if (!p) return FALSE;
   if (p->prev) p->prev->next = p->next;
   if (p->next) p->next->prev = p->prev;
   free(p);
   return TRUE;
}

void delete_all(ListPtr p) {
   while (p->prev) p = p->prev;
   while (p) {
      free(p->prev);
      p = p->next;
   }
   free(p);
}

void main() {
   ListPtr p = NULL;
   insert(&p,10);
   insert(&p,20);
   insert(&p,21);
   insert(&p,22);
   print(p);
   p = p->next;
   print(p);
   delete_one(&p, 21);
   print(p);
   if (search(p, 22)) printf("Ja\n"); else printf("Nein\n");
   delete_one(&p, 22);
   if (search(p, 22)) printf("Ja\n"); else printf("Nein\n");
   delete_all(p);
   exit(0);
}

8.1 Einfacher Ring

/* ein kleines Listenpogramm */

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef int BOOL;

typedef struct node *ListPtr;
typedef struct node { /*Listenelement */
   int key;
   ListPtr next;
} listNode;

BOOL insert(ListPtr *pt, int key) {
   ListPtr newp = (ListPtr)calloc(1, sizeof(listNode)), p = *pt;
   if (!newp) return FALSE;
   newp->key = key;
   if (!p) { 
      newp->next = newp;
      *pt = newp;
   } else {
      newp->next = p->next;
      p->next = newp;
   }
   return TRUE;
}

void print(ListPtr p) {
   ListPtr beg = p;
   if (beg) 
      do {
	 printf("%d", beg->key);
	 printf(" | ");
	 beg = beg->next;
      } while (beg != p);
   printf("\n");
}

ListPtr search(ListPtr p, int key) {
   ListPtr beg = p;
   if (!p) return FALSE;
   do {
      beg = beg->next;
   } while ((beg != p) && (beg->key != key));
   return (beg->key == key)?beg:NULL;
}

BOOL delete_one(ListPtr *p, int key) { /* *p to be able to delete the */
   ListPtr beg = *p, prev;             /* actual element */
   if (!*p) return FALSE;
   do {
      prev = beg;
      beg = beg->next;
   } while ((beg != *p) && (beg->key != key));
   if (beg->key != key) return FALSE;
   if (*p == beg) *p = beg->next;
   prev->next = beg->next;
   free(beg);
   return TRUE;
}

void delete_all(ListPtr p) {
   ListPtr beg = p->next, prev;
   if (p) {
      while (p !=beg) {
	 prev = beg;
	 beg = beg->next;
	 free(prev);
      }
      free(p);
   }
}

void main() {
   ListPtr p = NULL;
   insert(&p,10);
   insert(&p,20);
   insert(&p,21);
   insert(&p,22);
   print(p);
   p = p->next;
   print(p);
   delete_one(&p, 22);
   print(p);
   exit(0);
   if (search(p, 22)) printf("Ja\n"); else printf("Nein\n");
   delete_one(&p, 22);
   if (search(p, 22)) printf("Ja\n"); else printf("Nein\n");
   delete_all(p);
   exit(0);
}

8.1 Doppelter Ring

/* ein kleines Listenpogramm */

#include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1

typedef int BOOL;

typedef struct node *ListPtr;
typedef struct node { /*Listenelement */
   int key;
   ListPtr prev, next;
} listNode;

BOOL insert(ListPtr *pt, int key) {
   ListPtr newp = (ListPtr)calloc(1, sizeof(listNode)), p = *pt;
   if (!newp) return FALSE;
   newp->key = key;
   if (!p) { 
      newp->prev = newp->next = newp;
      *pt = newp;
   } else {
      newp->next = p->next;
      newp->prev = p;
      p->next->prev = newp;
      p->next = newp;
   }
   return TRUE;
}

void print(ListPtr p) {
   ListPtr beg = p;
   if (beg) 
      do {
	 printf("%d", beg->key);
	 printf(" | ");
	 beg = beg->next;
      } while (beg != p);
   printf("\n");
}

ListPtr search(ListPtr p, int key) {
   ListPtr beg = p;
   if (!p) return FALSE;
   do {
      beg = beg->next;
   } while ((beg != p) && (beg->key != key));
   return (beg->key == key)?beg:NULL;
}

BOOL delete_one(ListPtr *p, int key) {
   ListPtr beg = *p;
   if (!*p) return FALSE;
   do {
      beg = beg->next;
   } while ((beg != *p) && (beg->key != key));
   if (beg->key != key) return FALSE;
   if (*p == beg) *p = beg->next;
   beg->prev->next = beg->next;
   beg->next->prev = beg->prev;
   free(beg);
   return TRUE;
}

void delete_all(ListPtr p) {
   ListPtr beg = p->next;
   if (p) {
      while (p !=beg) {
	 beg = beg->next;
	 free(beg->prev);
      }
      free(p);
   }
}

void main() {
   ListPtr p = NULL;
   insert(&p,10);
   insert(&p,20);
   insert(&p,21);
   insert(&p,22);
   print(p);
   p = p->next;
   print(p);
   delete_one(&p, 22);
   print(p);
   exit(0);
   if (search(p, 22)) printf("Ja\n"); else printf("Nein\n");
   delete_one(&p, 22);
   if (search(p, 22)) printf("Ja\n"); else printf("Nein\n");
   delete_all(p);
   exit(0);
}