Sammenkædede datastrukturer udgør et fleksibelt alternativ til forskellige statiske (faste) kombinationer af arrays og structures.

41.1 Sammenkædede datastrukturer (1) 41.4 Mutation af cons celler 41.2 Sammenkædede datastrukturer (2) 41.5 Funktioner på lister 41.3 Kædede lister ala Lisp 41.6 Indsættelse og sletning af elementer i en liste

 

41.1.  Sammenkædede datastrukturer (1)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Sammenkædede datastrukturer opbygges typisk af dynamisk allokerede structs, der sammenbindes af pointere. Pointere var emnet i kapitel 22 og structures har været et af vore emner i denne lektion, startende i afsnit 39.1.

Når én struct via en pointer refererer til en struct af samme type taler vi undertiden om selvrefererende typer, eller på engelsk self-referential structures.

Som det fremgår, også af figur 41.1, er selvrefererende strukturer en konkret implementation af rekursive datatyper. Se også afsnit 32.1.

Figur 41.1    En rekursiv struktur i forhold til en self-referential structure med pointere

41.2.  Sammenkædede datastrukturer (2)
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Vi lader nu op til at studere enkelt-kædede lister. Dette er lineære strukturer, der ofte bruges som et alternativ til arrays. Arrays er mere effektive at slå op i, men langt mindre effektive ved indsættelser og sletninger af elementer. Sidstnævnte illustreres i afsnit 41.6.

Herunder, i program 41.1 ser vi mod blåt den afgørende byggeklods for enkelt-kædede lister. Feltet next er en pointer til en struct, som svarer til værtstrukturen af next. Den røde struct er et forsøg på en rekursiv struktur. Rekursiviteten optræder fordi feltet next har samme type som den omkringliggende struct. Vi genfinder altså helheden (strukturen) i detaljen (et felt i strukturen). Rekursive datatyper, ala den røde struktur, er ulovlige i C. Den blå struktur er derimod OK.

1
2
3
4
5
6
7
8
9
10
11

/* Illegal recursive data structure */
struct first_list {
  int                data;
  struct first_list  next;
};

/* Legal self-referential data structure */
struct second_list {
  int                 data;
  struct second_list  *next;
};

I de kommende afsnit vil vi udvikle et listebegreb, med udgangspunkt i den blå struktur i program 41.1. Med afsæt i Lisp, som er et LISte Processerings sprog, vil vi kalde denne struktur en cons celle.

41.3.  Kædede lister ala Lisp
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Som sagt er vil vi nu implementere lister, som de findes i Lisp. Det er for øvrigt det samme listebegreb, som nogle måske kender fra programmeringssproget ML. Både Lisp og ML er funktions-orienterede programmeringssprog.

Den strukturelle byggeklods er cons cellen, som vi etablerer først. Se program 41.2.

1
2
3
4
5
6

struct cons_cell {
  void             *data;
  struct cons_cell *next;
};

typedef struct cons_cell cons_cell;

Vi laver nu, i program 41.3, funktionen som hhv. konstruerer og selekterer bestanddele i en cons celle. Funktionen cons allokerer med malloc plads til en cons celle (i alt to pointere). Funktionen head returnerer førstepladsen (en pointer til data bestanddelen) af cons cellen. Funktionen tail returnerer andenpladsen (en pointer til en næste cons celle). I de fleste Lisp systemer taler vi om car and cdr i stedet for head og tail.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* Returns a pointer to a new cons cell, 
   which refers data and next via pointers*/
cons_cell *cons(void *data, cons_cell *next){
 cons_cell *result;
 result = malloc(sizeof(cons_cell));
 result->data = data;
 result->next = next;
 return result;
}

/* Return the head reference of the cons cell */
void *head(cons_cell *cell){
  return cell->data;
}

/* Return the tail refererence f the cons cell */
cons_cell *tail(cons_cell *cell){
  return cell->next;
}

Givet funktionerne cons, head og tail vil vi nu illustrere hvordan de anvendes til simpel og basal listehåndtering. Dette sker i program 41.4. Vi ser først tre punkter p1, p2 og p3 af typen point. (For god ordens skyld viser vi typen point og en point print funktion i program 41.5). På det røde sted laver vi en liste af de tre punkter.

Læg mærke til hvordan adresserne på punkterne overføres som førsteparametre til kaldene af cons. På de blå steder anvender vi selektor funktionerne head og tail i et gennemløb af listen af punkter. Læg mærke til at vi har brug for at caste resultatet af head(points) inden det kan overføres som en parameter til prnt_points. Årsagen er at head returnerer en generisk pointer (en pointer til void(jf. program 41.3). Compileren har brug for en garanti for, at denne pointer peger på et punkt. Ved brug af cast operationen på det lilla sted udsteder programmøren denne garanti. Det kommer ikke på tale at transformere pointeren på nogen måde.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int main(void) {

  cons_cell *points;

  point p1 = {1,2}, p2 = {3,4}, p3 = {5,6};

  points = cons(&p1,
                cons(&p2,
                     cons(&p3,
                          NULL)));

  while (points != NULL) {
    prnt_point(*((point*)(head(points))));
    points = tail(points);
  }
  
  return 0;
}

1
2
3
4
5
6

struct point {int x; int y;};
typedef struct point point;

void prnt_point(point p){
  printf("Point: %i, %i\n", p.x, p.y);
}

Observationen om det binære træ er enkel. Hver cons celle har to pointere, som faktisk begge kan gå til andre cons celler. Hvis dette er tilfældet kan vi helt naturligt forstå en cons celle struktur som et træ. Bladene i træet vil typisk være NULL eller pointere til simple værdier, f.eks. tal.

41.4.  Mutation af cons celler
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

Lad os nu udvide repertoiret af funktioner, som arbejder på cons celler. I afsnit 41.3, nærmere bestemt i program 41.3, så vi hvordan vi lavede funktionerne cons, head og tail. Vi vil nu lave funktioner, der kan ændre head og tail pointerne.

Funktionerne set_head og set_tail er enkle. Vi ser dem i program 41.6.

1
2
3
4
5
6
7
8
9

/* Change the data position of cell to new_head */
void set_head(cons_cell *cell, void *new_head){
  cell->data = new_head;
}

/* Change the next position of cell to new_tail */
void set_tail(cons_cell *cell, cons_cell *new_tail){
  cell->next = new_tail;
}

Eneste punkt på dagsordenen i set_head og set_tail er et assignment af hhv. data- og next pointeren til den pointerværdi, der overføres som anden (og sidste) parameter.

I program 41.7 viser vi et eksempelprogram, som anvender set_head. Vi laver først en liste af tre punkter. På det røde sted udskiftes punktet p1 med p3. Ligeledes udskiftes punktet p2 med p4. Når vi udskriver punkterne i den efterfølgende while-løkke får vi altså outputtet (5,6), (6,7), (5,6).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int main(void) {

  cons_cell *points;

  point p1 = {1,2}, p2 = {3,4}, 
        p3 = {5,6}, p4 = {6,7};

  points = cons(&p1,
                cons(&p2,
                     cons(&p3,
                          NULL)));

  set_head(points,&p3);
  set_head(tail(points), &p4);

  while (points != NULL) {
    prnt_point(*((point*)(head(points))));
    points = tail(points);
  }
  
  return 0;
}

41.5.  Funktioner på lister
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

På basis af listefunktionerne cons, head, tail, set_head og set_tail fra afsnit 41.3 og afsnit 41.4 vil vi nu programmet udvalgte funktioner på enkeltkædede lister. Både listebegrebet og funktionerne er modelleret efter Lisp.

I program 41.8 starter vi med funktionen list_length, der måler længden af en liste. Funktionen tæller altså antallet af elementer i listen.

1
2
3
4
5
6

/* Return the number of elements in list */
int list_length(cons_cell *list){
  if (list == NULL)
    return 0;
  else return 1 + list_length(tail(list));
}

Funktionen list_length tager som parameter en reference til den første cons celle i listen. Med udgangspunkt i denne gennemløbes listen rekursivt, og cons cellerne tælles. Læg mærke til at funktionen tail kaldes for at få fremdrift i rekursionen.

Den næste funktion, i program 41.9 er append, som sammensætter to lister list1 og list2 til én liste. Funktionen tager de to lister som parametre, i termer af to pointere til cons celler. Der returneres en pointer til den sammensatte listes første cons celle.

1
2
3
4
5
6
7
8

/* Append list1 and list2. The elements in list2 are shared between
   the appended list and list2 */
cons_cell *append(cons_cell *list1, cons_cell *list2){
  if (list1 == NULL)
    return list2;
  else return cons(head(list1),
                   append(tail(list1),list2));
}

I append funktionen kopieres cons cellerne i list1. Den sidste cons celle i den kopierede del refererer blot den første cons celle i list2. Læg godt mærke til hvordan rekursion gør det muligt - let og elegant - at gennemføre den beskrevne kopiering og listesammensætning.

I program 41.10 programmerer vi en funktion, member, der afgør om et element el findes i listen list. Både el og list er parametre af member funktionen. Sammenligningen af el og elementerne i listen fortages som pointersammenligning, ala reference lighed af strenge (se figur 28.1).

1
2
3
4
5
6
7
8
9
10

/* Is el member of list as a data element? 
   Comparisons are done by reference equality */
int member(void *el, cons_cell *list){
  if (list == NULL)
    return 0;
  else if (head(list) == el)
    return 1;
  else
    return member(el, tail(list));
}

I lidt større detalje ser vi at member returnerer 0 (false) hvis list er NULL (den tomme liste). Hvis ikke listen er tom sammenlignes el og og head af den første cons celle. Hvis disse peger på forskellige objekter sammenlignes el rekursivt med halen tail(list).

Den sidste liste funktion, som vi programmerer i dette afsnit, er reverse. Se program 41.11. Funktionen reverse vender listen om, således at det første element bliver det sidste, og det sidste element bliver det første.

1
2
3
4
5
6
7

/* Returned list in reverse order */
cons_cell *reverse(cons_cell *list){
  if (list == NULL)
    return NULL;
  else 
    return append(reverse(tail(list)), cons(head(list), NULL));
}

Funktionen reverse virker således: Først, hvis listen er den tomme liste er resultatet også den tomme liste. Hvis listen er ikke tom sammensættes reverse(tail(list)) med listen, der kun består af head(list). Sammensætningen foretages naturligvis med append, som vi programmerede i program 41.9.

Vi viser nu et lidt større program, som bruger alle de funktioner vi har programmeret i program 41.8 - program 41.11. Se program 41.12.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

int main(void) {

  cons_cell *points, *more_points, *point_list, *pl;

  point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p4 = {6,7},
        p5 = {8,9}, p6 = {10,11}, p7 = {12,13}, p8 = {14,15};

  points = cons(&p1,
                cons(&p2,
                     cons(&p3,
                          cons(&p4,NULL))));

  more_points = 
           cons(&p5,
                cons(&p6,
                     cons(&p7,
                          cons(&p8,NULL))));

  printf("Number of points in the list points: %i\n", 
         list_length(points));

  point_list = append(points, more_points);
  pl = point_list;

  while (pl != NULL) {
    prnt_point(*((point*)(head(pl))));
    pl = tail(pl);
  }

  if (member(&p6, points))
    printf("p6 is member of points\n");
  else  printf("p6 is NOT member of points\n");

  if (member(&p6, more_points))
    printf("p6 is member of more_points\n");
  else  printf("p6 is NOT member of more_points\n");

  if (member(&p6, point_list))
    printf("p6 is member of point_list\n");
  else  printf("p6 is NOT member of point_list\n");


  pl = reverse(points);

  while (pl != NULL) {
    prnt_point(*((point*)(head(pl))));
    pl = tail(pl);
  }
  
  return 0;
}

Vi forklarer kort programmet. Vi starter med at lave to lister af hhv. p1, p2, p3 og p4 samt af p5, p6, p7 og p8. På det røde sted kalder vi list_length på den første liste. Vi forventer naturligvis resultatet 4. På det blå sted sammensætter vi de to lister af punkter. Det forventes at give en liste af de otte punkter p1 - p8. På de tre brune steder tester vi om p6 tilhører den første punktliste, den anden punktliste og den sammesatte punktliste. Endelig, på det lilla sted, vender vi den sammensatte liste om ved brug af reverse.

41.6.  Indsættelse og sletning af elementer i en liste
Indhold   Op Forrige Næste   Slide Aggregerede slides    Stikord Programindeks Opgaveindeks 

På dette sted har vi etableret lister (se afsnit 41.5) på grundlag af cons celler (se afsnit 41.3).

Vi vil nu illustrere hvordan man kan indsætte og slette elementer i kædede lister. Det er meget relevant at sammenligne dette med indsættelse og sletning af elementer fra arrays.

På den tilhørende slide side kan du konsultere en billedserie, der viser hvilke skridt der er involveret i at indsætte et element i en kædet liste. Alternativt kan du bruge dette direkte link. Herunder, i program 41.13 , viser et program, som implementerer indsættelsen af et element i en kædet liste.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

/* Insert new_element after the cons-cell ptr_list */
void insert_after(void *new_element, cons_cell *ptr_list){
  cons_cell *new_cons_cell, *ptr_after;
 
  /* Make a new cons-cell around new_element */
  new_cons_cell= cons(new_element,NULL);

  /* Remember pointer to cons-cell after ptr_list */
  ptr_after = tail(ptr_list);

  /* Chain in the new_cons_cell */
  set_tail(ptr_list, new_cons_cell);

  /* ... and connect to rest of list */
  set_tail(new_cons_cell, ptr_after);
}

Der er fire trin involveret, som er omhyggelig kommenteret i program 41.13. Først laves en ny cons celle, hvorfra parameteren new_element kan refereres. Så fastholdes pointeren til det element der kommer efter det nye element. I de to sidste trin indkædes den nye cons celle i listen. Hvis du ikke allerede har gjort det, så følg billedserien på den tilhørende slide og forstå program 41.13 ud fra denne.

Bemærk at insert_after ikke kan bruges til at indsætte et nyt første element i en liste. Dette tilfælde er både specielt og problematisk. 'Specielt' fordi det kræver sin egen indsættelsesteknik. Og 'problematisk' fordi der generelt kan være mere end én reference til det første element. Dette vender vi kort tilbage til i slutbemærkningerne af afsnit 42.4.

Helt symmetrisk til indsættelse af elementer kan vi også programmere sletning af elementer. Konsulter dog først billedserien på den tilhørende slide side Alternativt kan du bruge dette direkte link. Det tilsvarende program er vist i program 41.14.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/* Delete the element after ptr_list. Assume as a
   precondition that there exists an element after ptr_list */
void delete_after(cons_cell *ptr_list){  
  cons_cell *ptr_after, *ptr_dispose;

  /* cons-cell to delete later */
  ptr_dispose = tail(ptr_list);

  /* The element to follow ptr_list */
  ptr_after = tail(ptr_dispose);

  /* Mutate the tail of ptr_list */
  set_tail(ptr_list, ptr_after);

  /* Free storage - only one cons-cell */
  free(ptr_dispose);
}

Vores udgangspunkt er en pointer til den cons celle, som er lige før cons cellen for det element, der skal slettes. I programmet laver vi først en reference ptr_dispose til den cons celle, der skal slettes. Dernæst etablerer vi ptr_after til at pege på cons cellen lige efter elementet, der skal slettes. Nu kan vi i det tredje trin ændre på next pointeren af ptr_list ved hjælp af set_tail. Endelig frigør vi lageret af cons cellen, der refereres af ptr_dispose. Dette gøres på det blå sted med free funktionen, jf. afsnit 26.3.

Sletningen af et element med delete_after virker ikke på det første element. Observationen svarer helt til det tilsvarende forhold for insert_after.

Vi viser i program 41.15 hvordan insert_after og delete_after kan bruges i en praktisk sammenhæng.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int main(void) {

  cons_cell *points, *pl;

  point p1 = {1,2}, p2 = {3,4}, p3 = {5,6}, p_new = {11,12};

  points = cons(&p1,
                cons(&p2,
                     cons(&p3,
                          NULL)));


  insert_after(&p_new, tail(points));  

  pl = points;    
  while (pl != NULL) {
    prnt_point(*((point*)(head(pl))));
    pl = tail(pl);
  }

  printf("\n\n");

  delete_after(points);

  pl = points;    
  while (pl != NULL) {
    prnt_point(*((point*)(head(pl))));
    pl = tail(pl);
  }

  return 0;
}