You must do every programming assignment by yourself. You are permitted to
get help ONLY from the TAs and the instructor. When you have completed the
program, and tested it sufficiently so that you are comfortable that it
works on any input, submit it for grading according to the submission
instructions
at the end of this handout. The file you submit should be an
assembly language file called intersection.asm. This is the only file you need to submit.
This program is going to make use of a common data structure, the linked list.
The Linked-List
As discussed in class, a linked-list is a set of elements connected to each
other via pointers. We often refer to these elements as "nodes." Each node
in a linked-list is comprised of k+1 words. The first word contains a pointer
to (i.e., the address of) the next node, and the remaining k words contain
data associated with that node. The first word of the last node contains x0000,
indicating that there are no more nodes in the list. We refer to x0000 as
the null pointer.
In programming lab 3, each node in our linked lists will consists of two words.
The first word will contain a pointer to the next node. The second word will
contain a pointer to a character string representing the name of the person
associated with that node. A character string consists of ASCII codes stored
in consecutive memory locations, one ASCII code per location. The string is
null-terminated, i.e., the end of a string is signified by the NULL character
which is ASCII code x00.
Below is a graphical representation of two linked-lists. One consists
of three nodes, representing three people: Chen, Grey, and Patel. The other
consists of three nodes, representing Brown, Chen, and Patel. Note that each
linked list terminates with the null pointer x0000. Note also that each
character string terminates with a null entry x0000. Finally, note that each
list has a list head (memory locations x4000 and x4001 in the example) which
contain pointers to the first node in their respective linked lists.
Below we show the layout in memory of the two linked lists described above.
Address | Contents | Description |
x4000 | x4050 | Pointer to the first node of the first list |
x4001 | x4100 | Pointer to the first node of the second list |
x4002 | x0000 | Pointer to the first node of the third list (which you will create from existing nodes), initially invalid |
... | ... | |
x4050 | x4150 | Next-pointer |
x4051 | x4025 | Pointer to the first ASCII code of the last name |
... | ... | |
x4025 | x0043 | ASCII code for "C" |
x4026 | x0068 | ASCII code for "h" |
x4027 | x0065 | ASCII code for "e" |
x4028 | x006E | ASCII code for "n" |
x4029 | x0000 | NULL character which signifies the end of the major |
... | ... | |
x4077 | x0047 | ASCII code for "G" |
x4076 | x0072 | ASCII code for "r" |
x4077 | x0065 | ASCII code for "e" |
x4078 | x0079 | ASCII code for "y" |
x4079 | x0000 | NULL character which signifies the end of the last name |
... | ... | |
x4100 | x5000 | Next-pointer |
x4101 | x5650 | Pointer to the first ASCII code of the last name |
... | ... | |
x4150 | x4550 | Next-pointer |
x4151 | x4077 | Pointer to the first ASCII code of the last name |
... | ... | |
x454E | x0000 | Next-pointer, x0000 indicates the end of the list |
x454F | x5500 | Pointer to the first ASCII code of the last name |
x4550 | x0000 | Next-pointer, x0000 indicates the end of the list |
x4551 | x5525 | Pointer to the first ASCII code of the last name |
... | ... | |
x5000 | x454E | Next-pointer |
x5001 | x5600 | Pointer to the first ASCII code of the last name |
... | ... | |
x5500 | x0050 | ASCII code for "P" |
x5501 | x0061 | ASCII code for "a" |
x5502 | x0074 | ASCII code for "t" |
x5503 | x0065 | ASCII code for "e" |
x5504 | x006C | ASCII code for "l" |
x5505 | x0000 | NULL character which signifies the end of the last name |
... | ... | |
x5525 | x0050 | ASCII code for "P" |
x5526 | x0061 | ASCII code for "a" |
x5527 | x0074 | ASCII code for "t" |
x5528 | x0065 | ASCII code for "e" |
x5529 | x006C | ASCII code for "l" |
x552A | x0000 | NULL character which signifies the end of the last name |
... | ... | |
x5600 | x0043 | ASCII code for "C" |
x5601 | x0068 | ASCII code for "h" |
x5602 | x0065 | ASCII code for "e" |
x5603 | x006E | ASCII code for "n" |
x5604 | x0000 | NULL character which signifies the end of the major |
... | ... | |
x5650 | x0042 | ASCII code for "B" |
x5651 | x0072 | ASCII code for "r" |
x5652 | x006F | ASCII code for "o" |
x5653 | x0077 | ASCII code for "w" |
x5654 | x006E | ASCII code for "n" |
x5655 | x0000 | NULL character which signifies the end of the last name |
... | ... |
Finding suitable tenants
Overview:
A realtor is trying to rent out apartment units and is struggling to find
the right tenants. They need to find tenants that earn at least $75,000/year.
Additionally, they would prefer to rent to tenants that have at least three
children. Fortunately, the realtor has a list of people,
organized as a linked list, that
earn over $75,000/year and another list of
people, also organized as a linked list, that have at least three children
-- both lists are stored in memory. The
realtor wants you to provide them
with a list of all the people, also organized as a linked list, that earn over
$75,000/year who have at least three children.
Your Job:
Write a program in LC-3 assembly language that takes as input two linked
lists stored in memory, the first one containing the names of all people who earn
over $75,000/year, and the second one containing the names of all people who have
at least three children, and produce as output a third linked list, also stored in memory,
containing the names of people who earn over $75,000 and have at least three children.
More specifically, the result of your program will be 3 linked lists: people
who earn over $75,000/year who have fewer than three children, people that have at least three children
and earn less than $75,000/year, and people who earn over $75,000/year
and have at least three children. You will achieve this by removing from the first
linked list those people who have at least three children, and from the second list
those people who earn more than $75,000/year, and produce the third list
from people who are removed from the first two lists.
In the example linked lists shown above, if the first list consisted of people
earning more than $75,000 (Chen, Grey, and Patel), and the second list
consisted of people with at least three children (Brown, Chen, and Patel), your result
would be: The first list consists of the single node Grey, the second list
consists of the single node Brown, and the third list consists of the two
nodes Chen and Patel.
Finally, assume LC-3 is sufficiently constrained that you can not waste
space. That is, you are not allowed to create any additional nodes to help
you solve this assignment, but instead you will construct your third list
from nodes removed from your first list.
The address of the first node of the list (the list head) of people that
earn over $75,000/year will be stored at location x4000. The address of
the first node of people with at least three children will be stored at location x4001.
You will store the address of the first node of the result at location x4002.
A node will consist of two words: a pointer to the next node and a pointer
to a character string. All nodes in each list will be ordered in alphabetical
order, based on their names. Each of the three final lists must also be
sorted in alphabetical order based on person's name. The string of characters
will represent the name of the individual in question. For purposes of this
lab, we will assume no two people have the same name. Thus, each name uniquely
identifies one individual who either earns $75,000/year, has at least three children,
or both. The string will be null-terminated and stored in memory like so:
one ASCII character per memory location, the last character will be the null character.
Notes