Universität Ulm,
Fakultät für Mathematik und Wirtschaftswissenschaften,
SAI
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);
}
Ingo Melzer, 02. Dezember 1997