用Linked List实现一个Matrix，需要保证这个矩阵的存储方式是稀疏的，此外还需要实现基本的矩阵运算，这个作业的难点是在行列交叉的数据查找、插入以及删除。
Introduction
We are now fast-forwarding in time several steps after you presented your designs from phase 1 to the client. A few iterations of tweaking and discussion have repeated, and we now have a much better idea of the ADT that we need to implement. You may notice that some things have been added, and some taken away, this is normal for a project like this (and shows why it’s a good idea to settle on a design before you spend large chunks of time developing the actual code). The ADT is almost nalized, and now we can start to work on the implementation.
The ADT
The starter code provided in a1.py represents an almost complete ADT. The class hierarchy is settled, and all of the methods have been outlined, at least at their highest level. We’ve decided which exception types we need, but not exactly when and where they should be raised, and we haven’t gured out yet which methods will need to be over-ridden in children classes. These nal elements of the design should be your rst task.
Implementation
Once we’re ready to implement the actual Matrix class and its sub-classes, we need to think about a sensible data structure that we can use. Obviously we could simply have lists of lists, but this seems impractical. What if the client wants to create a 1000 x 1000 matrix, but only cares about 1 or 2 values. We’d be using up millions of times more space than we actually need. Fortunately, we’ve learned about linked lists in lecture. Maybe they can help us.
Linked Data Structure
Suppose we have the matrix:
A D G
B E H
C F I
Each element can be held in a node like in a linked list, with A pointing to B , etc.
This would be ne if all we cared about were the columns, but sometimes we’re going to need to deal with rows, so maybe each node could have a link to the node, beside it as well (i.e, A could also link to D). We could create a linked data structure, that can hold a matrix of elements.
This is a nice start, but doesn’t help us with our initial problem of saving space, since every node has to be created for us to be able to gure out where we are in the matrix. If we didn’t have a D node, we wouldn’t know if the item to the right of A was supposed to be in column 1 or 2 or 20. So let’s add a set of index nodes that tell us the index of each row or column. Since we want to have a single point of entry into the data structure, we’ll also add an extra node with no data, but that can be used as the head of the structure.
None 0 1 2
0 A D G
1 B E H
2 C F I
So now let’s see what happens when we don’t have all the nodes. Let’s say that our matrix is all 0s, except for A, G and F.
A 0 G
0 0 0
0 F 0
We could create the matrix like this:
None 0 1 2
0 A G
2 F
Notice now that we only need to create nodes for the data that actually exists in our matrix. Any node that doesn’t exist, we know must have a value of 0 (or whatever other default value we want to ascribe).
Make sure you fully understand this data structure before moving on. Try drawing out what it would look like with dierent matrices).
Your Task
Your task is to complete the code in a1.py using the linked data structure described above.
In particular, you may not use any other Python data structure (e.g., lists, dictionaries) in completing your code. You may add other methods if you wish, but you must at least implement the ADT as provided in the starter code.
Hints & Tips
- Plan everything before you write anything
- Draw lots of pictures
- Think about boundary cases (inserting at the beginning/end of a row/col, empty matrices, etc)
- If you’re stuck, you can go with the simpler approach of just creating every node, even those with default values, this won’t get you full marks, but it’s better than not having any of your code work
- Searching in a 2-dimensional system like this can be very confusing. Finding the intersection of a row and a column is dicult. Maybe there’s an easier way? (remember: you can add to the Node class as well).
- Don’t forget to include your representation invariants
- Remember that this must be 100% your own work. You may ask for clarication on Piazza, but you should not discuss this assignment with your classmates, or look for help elsewhere
- If you don’t understand something about the matrix mathematics, ask me, and I’ll explain it or post a tutorial on Piazza (I don’t want to test your linear algebra knowledge).