Description
PA – Redux: Boustrophedonic Lists
• See Piazza for due date and time
o Grading the next day
• Submit program to perforce in your student directory
o Sub directory called:
/PA_Redux/…
o Fill out your PA_Redux Submission Report.pdf
Place it in the same directory as your solution
Enter the final Changelist number of your submission
Write up a quick discussion in the report
• What you learned from this assignment so far
• Programming Assessment
o Extra credit for PA1 – More practice with linked lists… (kind of)
• Write a single function: remove()
o Signature and structure need exactly the same
o Place function in file named (see supplied files):
Boustrophedonic.cpp:
• Function
Boustrophedonic.h:
• Declaration and structure
struct Node
{
Node *pNorth;
Node *pSouth;
Node *pEast;
Node *pWest;
}
void remove( Node *head, int row, int col);
• Assumptions
o Boustrophedonic list is complete and pristine before you remove one node
o Only one node will be removed in the function
o The head node will not be removed
o The dimensions of the list are not given
o Boustrophedonic list has an even number of columns
o Boustrophedonic list has no restrictions on number of rows
o On deletion, horizontal and vertical connections are preserved across the deleted node
Optimized C++
Programming Assignment
1
Optimized C++ PA -Redux
Creating a Boustrophedonic List
Boustrophedonic – Greek word:
• A method of writing shown in early Greek inscriptions, in which the lines run alternately from
right to left and from left to right, as the furrows made in plowing a field, the plow passing
alternately backward and forward.
struct Node
{
Node *pNorth;
Node *pSouth;
Node *pEast;
Node *pWest;
}
• Start with the first node and continue in the Boustrophedonic path way, follow the RED LINE.
o Start with the head, and sequentially go from 0 to 11 in the Boustrophedonic way
0 1 2 3
7 6 5 4
8 9 10 11
a
e
head
North
West East
South
Optimized C++
Programming Assignment
2
Optimized C++ PA -Redux
• Next we create the vertical connections.
0 1 2 3
7 6 5 4
8 9 10 11
d c b a
e f g h
head
• Create the vertical connections between row 0 {0,1,2,4} and row 1 {7,6,5,4}.
o Find arrow a between 3 and 4.
That arrow goes down, from 3 to 4.
o Alternate direction of a, (a goes down in RED)
b goes up YELLOW,
c goes down BLUE,
d goes up YELLOW.
• Similar for the connections between row 1 {7,6,5,4} and row 2 {8,9,10,11}
o Alternate direction of e, (e goes down in RED)
f goes up YELLOW,
g goes down BLUE,
h goes up YELLOW.
Optimized C++
Programming Assignment
3
Optimized C++ PA -Redux
• Drawing the list with all the links displayed.
o Each node actually has 4 pointers, most are nulls.
North, South, East, West
o Here the list is drawn with GREEN links showing the explicit null pointers.
0
0
0
0 0 0
0 0
0 0
0
0 0
0 0 0 0
0
0
0
0 0 0
0 0 0
0 0 0
0
0
head
• Rows and Columns
o Rows and columns are not provided, nor are they added in the Node structure.
o You need to calculate these as you walk the list.
o The lists will vary in dimensions, Row x Column (row,col)
o There will be an even number of columns.
(0,0) (0,1) (0,2) (0,3)
(1,0) (1,1) (1,2) (1,3)
(2,0) (2,1) (2,2) (2,3)
0
0
0
0 0 0
0 0
0 0
0
0 0
0 0 0 0
0
0
0
0 0 0
0 0 0
0 0 0
0
0
head
Optimized C++
Programming Assignment
4
Optimized C++ PA -Redux
• Deletion
o Remove only one node at a time
o Keep horizontal connections, through the deleted node
Fix adjacent nodes connections
o Keep vertical connections, through the delete node
Fix adjacent nodes connections
o Many examples to follow
Delete Node (1,2) 0
0
0
0 0 0
0 0
0 0
0
0 0
0 0 0 0
0
0
0
0 0
0 0 0
0 0 0
0
0
head
Delete Node (1,1) 0
0
0
0 0 0
0
0 0
0
0
0 0 0 0
0
0
0
0 0
0 0 0
0 0 0
0
0
head
Optimized C++
Programming Assignment
5
Optimized C++ PA -Redux
Fall 2015 Keenan
Delete Node (1,0) 0
0
0
0 0 0
0 0
0 0
0
0 0
0 0 0 0
0
0
0
0 0
0 0 0
0 0 0
0
head
0
Delete Node (0,2) 0
0
0
0 0
0 0
0 0 0 0
0 0 0 0
0
0
0
0 0 0
0 0
0 0 0
0
0
head
0
Optimized C++
Programming Assignment
6
Optimized C++ PA -Redux
Fall 2015 Keenan
Delete Node (0,3) 0
0
0
0 0
0 0
0 0
0
0 0
0 0 0 0
0
0
0 0 0
0 0
0 0 0
0
0
head
0
Delete Node (2,3) 0
0
0
0 0 0
0 0
0 0
0
0 0
0 0 0
0
0
0
0 0 0
0 0 0
0 0
0
0
head
Optimized C++
Programming Assignment
7
Optimized C++ PA -Redux
Fall 2015 Keenan
Delete Node (0,1) 0
0
0
0 0
0 0
0 0
0
0 0
0 0 0 0
0
0
0
0 0 0
0 0
0 0 0
0
0
head
Delete Node (1,3) 0
0
0
0 0 0
0
0 0
0
0
0 0 0 0
0
0
0
0 0
0 0 0
0 0 0
0
0
head
Optimized C++
Programming Assignment
8
Optimized C++ PA -Redux
Fall 2015 Keenan
Delete Node (2,0) 0
0
0
0 0 0
0 0
0
0
0 0
0 0 0
0
0
0
0
0 0 0
0 0 0
0 0
0
0
head
General:
• Write all programs in cross-platform C or C++.
o Optimize for execution speed and robustness.
• Create a programming file for each problem, for example
o Student directory
/PA_Redux/…
o Make sure that each problem can be compiled and run through the checked in solution
• Do all your work by yourself
o Feel free to talk with others about setup, version control, ideas
o But do not copy your friend’s code.
Please don’t – I can tell with my difference tools
o Feel free to share ideas
• Check in the problems multiple times, at least 3 times per problem
o Have reasonable check-in comments
o Seriously, I’m checking
• Make sure that your program compiles and runs
o Warning level 4, some times that is not possible due to MS headers…
o Your code should be squeaky clean.
• We are using Perforce
o You should have received the document describing how to login.
Please look at the documentation and videos under the reference directory
o Submit program to perforce in your student directory
Sub directory called: /PA_Redux/…
• As described above
o All your code must compile from perforce with no modifications.
Otherwise it’s a 0, no exceptions
o Only Visual Studio 2013 allowed
Optimized C++
Programming Assignment
9
Optimized C++ PA -Redux
Simple check list to make sure that everything is checked in correctly
• Do they compile and run without any errors?
• Warning level 4 free?
• Submitted it into /PA_Redux directory?
• Can you delete you local drive, regrab the PA_Redux directory?
o Is all the code there?
Most assignments will have hints in a section like this.
• Do many little check-ins
o Iteration is easy and it helps.
o Perforce is good at it.
• Think about performance, did you read the Code Complete chapters?
o A lot of good ideas in there.
Optimized C++
Programming Assignment
10
Optimized C++ PA -Redux
Optimized C++
Programming Assignment
11
