BBC BASIC Programmers' Reference

User Tools

Site Tools

Trace:
linked_20lists_20using_20structures

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
linked_20lists_20using_20structures [2022/08/25 14:11] – Use PTR() rather than pointer magic richardrusselllinked_20lists_20using_20structures [2024/01/05 00:22] (current) – external edit 127.0.0.1
Line 1: Line 1:
 =====Linked lists using structures===== =====Linked lists using structures=====
  
-//by Richard Russell, May 2006//\\ \\  Structures provide a convenient means to create and manipulate linked lists, because they allow the content of each //node// in the list to be clearly described. Because BBC BASIC doesn't support structure pointers, as such, a degree of sneakiness is required to provide the necessary functionality!\\ \\  I will illustrate the steps required to create, search and read a linked list of structures using the example of an //insertion sort//. Here, the data items that you wish to sort are added one at a time to a list, in the correct place to keep the list sorted. A linked list is particularly suited to this because you can insert a new item anywhere in the list just by manipulating links, without having to move any of the existing items around.\\ \\  We start by deciding the structure of each node in the list. In this example each node will contain a string **item$** and an associated numeric value **misc**. Because it is a linked list each node must also contain a link **link%** which points to the next item in the list (the last item in the list has a link value of zero). Hence we can define a suitable structure for each node in the list as follows:\\ \\ +//by Richard Russell, May 2006//\\ \\  Structures provide a convenient means to create and manipulate linked lists, because they allow the content of each //node// in the list to be clearly described.\\ \\  I will illustrate the steps required to create, search and read a linked list of structures using the example of an //insertion sort//. Here, the data items that you wish to sort are added one at a time to a list, in the correct place to keep the list sorted. A linked list is particularly suited to this because you can insert a new item anywhere in the list just by manipulating links, without having to move any of the existing items around.\\ \\  We start by deciding the structure of each node in the list. In this example each node will contain a string **item$** and an associated numeric value **misc**. Because it is a linked list each node must also contain a link **link%** which points to the next item in the list (the last item in the list has a link value of zero). Hence we can define a suitable structure for each node in the list as follows:\\ \\ 
 <code bb4w> <code bb4w>
-        DIM node{item$, misc, link%}+        DIM node{item$, misc, link%%}
 </code> </code>
 The structure could contain any number of additional members, so long as there is always a link member.\\ \\  We keep track of the start of the linked list by defining a variable **first%** which points to the first node in the list. Initially the list is empty, so we set this variable to zero:\\ \\  The structure could contain any number of additional members, so long as there is always a link member.\\ \\  We keep track of the start of the linked list by defining a variable **first%** which points to the first node in the list. Initially the list is empty, so we set this variable to zero:\\ \\ 
 <code bb4w> <code bb4w>
-        first% = 0+        first%% = 0
 </code> </code>
 Next we start the insertion sort proper. For convenience we will read each data item in turn from a "DATA" statement:\\ \\  Next we start the insertion sort proper. For convenience we will read each data item in turn from a "DATA" statement:\\ \\ 
Line 18: Line 18:
 For each word we need to find where in the list it needs to be inserted to keep the list sorted into an ascending alphabetical sequence. This we do by following the links from the beginning until we either get to the end of the list, or we get to an entry which is //later// in the alphabet than our word:\\ \\  For each word we need to find where in the list it needs to be inserted to keep the list sorted into an ascending alphabetical sequence. This we do by following the links from the beginning until we either get to the end of the list, or we get to an entry which is //later// in the alphabet than our word:\\ \\ 
 <code bb4w> <code bb4w>
-          prev% = 0 +          prev%% = 0 
-          this% = first% +          this%% = first%% 
-          WHILE (this% <> 0) AND (word$ > FNgetitem(node{}, this%)) +          WHILE (this%% <> 0) AND (word$ > FNgetitem(node{}, this%%)) 
-            prev% = this% +            prev%% = this%% 
-            this% = node.link%+            this%% = node.link%%
           ENDWHILE           ENDWHILE
 </code> </code>
 A little explanation is probably necessary at this point. We define two new variables **this%** and **prev%** to point to the node in which we are currently interested, and the //previous// node (the one that links to it), respectively. To begin the search we set **this%** equal to **first%** (the start of the list) and we set **prev%** to zero (because the start of the list has no previous node).\\ \\  The **WHILE** statement loops for as long as we haven't reached the end of the list //and// our data word is greater than the current item. A function **FNgetitem** is used to return the value of the **item$** member for the node pointed to by **this%** and, importantly, it also sets the structure **node{}** to correspond to this node. This makes it easy to follow the links.\\ \\  When the loop has finished we know that, in order to keep the list sorted, we need to insert our new word //after// node **prev%** but //before// node **this%**. We first create a new node to contain the data:\\ \\  A little explanation is probably necessary at this point. We define two new variables **this%** and **prev%** to point to the node in which we are currently interested, and the //previous// node (the one that links to it), respectively. To begin the search we set **this%** equal to **first%** (the start of the list) and we set **prev%** to zero (because the start of the list has no previous node).\\ \\  The **WHILE** statement loops for as long as we haven't reached the end of the list //and// our data word is greater than the current item. A function **FNgetitem** is used to return the value of the **item$** member for the node pointed to by **this%** and, importantly, it also sets the structure **node{}** to correspond to this node. This makes it easy to follow the links.\\ \\  When the loop has finished we know that, in order to keep the list sorted, we need to insert our new word //after// node **prev%** but //before// node **this%**. We first create a new node to contain the data:\\ \\ 
 <code bb4w> <code bb4w>
-          new% = FNnewnode(node{})+          new%% = FNnewnode(node{})
           node.item$ = word$           node.item$ = word$
           node.misc = n%           node.misc = n%
Line 33: Line 33:
 The function **FNnewnode** creates a new node and returns a pointer to it. It also sets the structure **node{}** to correspond to this node for the convenience of setting its members. For the purposes of the example we set the **misc** element to the value of the loop counter **n%**.\\ \\  We must now link this new node into the correct place in the list:\\ \\  The function **FNnewnode** creates a new node and returns a pointer to it. It also sets the structure **node{}** to correspond to this node for the convenience of setting its members. For the purposes of the example we set the **misc** element to the value of the loop counter **n%**.\\ \\  We must now link this new node into the correct place in the list:\\ \\ 
 <code bb4w> <code bb4w>
-          node.link% = this% +          node.link%% = this%% 
-          IF prev% THEN +          IF prev%% THEN 
-            PROCsetlink(node{}, prev%, new%)+            PROCsetlink(node{}, prev%%, new%%)
           ELSE           ELSE
-            first% = new%+            first%% = new%%
           ENDIF           ENDIF
  
Line 44: Line 44:
 Here the procedure **PROCsetlink** sets the link member of node **prev%** to point to node **new%**. If we need to insert the new node at the start of the list (hence **prev%** is zero) we simply set **first%** to point to the new node.\\ \\  Now the insertion sort is complete, and all we need to do is print out the contents of the list in sequence to see if they are correct:\\ \\  Here the procedure **PROCsetlink** sets the link member of node **prev%** to point to node **new%**. If we need to insert the new node at the start of the list (hence **prev%** is zero) we simply set **first%** to point to the new node.\\ \\  Now the insertion sort is complete, and all we need to do is print out the contents of the list in sequence to see if they are correct:\\ \\ 
 <code bb4w> <code bb4w>
-        this% = first% +        this%% = first%% 
-        WHILE this% <> 0 +        WHILE this%% <> 0 
-          word$ = FNgetitem(node{}, this%)+          word$ = FNgetitem(node{}, this%%)
           misc = node.misc           misc = node.misc
           PRINT word$, misc           PRINT word$, misc
-          this% = node.link%+          this%% = node.link%%
         ENDWHILE         ENDWHILE
         END         END
Line 67: Line 67:
 <code bb4w> <code bb4w>
         DEF FNnewnode(RETURN n{})         DEF FNnewnode(RETURN n{})
-        LOCAL P% +        LOCAL p%% 
-        DIM P% DIM(n{})-1 +        DIM p%% DIM(n{})-1 
-        PTR(n{}) = P% +        PTR(n{}) = p%% 
-        = P%+        = p%%
  
-        DEF FNgetitem(RETURN n{}, n%) +        DEF FNgetitem(RETURN n{}, n%%) 
-        IF n% = 0 THEN = "" +        IF n%% = 0 THEN = "" 
-        PTR(n{}) = n%+        PTR(n{}) = n%%
         = n.item$         = n.item$
  
-        DEF PROCsetlink(n{}, n%, l%) +        DEF PROCsetlink(n{}, n%%, l%%) 
-        PTR(n{}) = n% +        PTR(n{}) = n%% 
-        n.link% = l%+        n.link%% = l%%
         ENDPROC         ENDPROC
 </code> </code>
linked_20lists_20using_20structures.1661436673.txt.gz · Last modified: 2024/01/05 00:16 (external edit)