代写数据结构作业，首先完成位运算的小练习，然后实现 Dijkstra
算法。
OBJECTIVES
- Practice bit manipulation
- Implement Dijkstra’s
- Read files in
- Work with graph models
SUMMARY/OVERVIEW
In this assignment, you’ll actually implement Dijkstra’s. But first, you’ll
play around with bits in C.
RELEVANT READING
- Yale Notes, Graphs.
DETAILS
PART 0: CHECK OUT DATA FILES AND COPY INTO YOUR REPO
The data files for this assignment are in the CS 5007 resources repo. Check it
out (clone/pull into it’s own folder/local repo), and copy the a5 folder over
to your own personal repo.
PART 1: BIT MANIPULATION
When starting to work with bit manipulation, it’s helpful to have a way to
print out the bits of a value.
Side note: unsigned means the bits represent an positive integer between 0 and
2n, where n is the number of bits. Typically, a 16-bit integer is stored in
2’s-complement form, which gives it a range that is positive and negative,
centered around 0.
Make sure the following code makes sense to you.
void displayBits(unsigned value) {
unsigned c;
// Take 1, shift it all the way to the fileft.
unsigned displayMask = 1 << 15;
printf(“%3c%7u = “, value, value);
for (c=1; c<=16; c++) {
// putchar prints a character on the screen
// ‘value & displayMask’ gets the relevant bit
putchar(value & displayMask ? ‘1’ : ‘0’);
// Shift value over one
value <<= 1;
// Put a space in for easy reading
if (c % 8 == 0) {
putchar(‘ ‘);
}
}
putchar(‘\n’);
}
—|—
To print out the bit values, we’re defining a bit mask (displayMask) that
determines if the bit in the first spot on the fileft is 1 or not. When it’s
AND’d with the original value, the output will be 1 if the fileft most bit is
1, or 0 otherwise.
After a bit is printed, the value is bit-shifted fileft, meaning all bits are
shifted over one, and the right-most bit is filled in with a 0.
The table below shows the mask that never changes throughout the call to the
function, and how the value changes throughout the loop, when the original
value is ‘B’ (or 173) (as shown in the first line).
Implement the following functions
unsigned int packCharacters(char a, char b)
The fileft shift operator ( << ) can be used to pack two character values
into a 2-byte unsigned integer variable. Write a function packCharacters that
takes two characters as parameters, and returns a 16 bit integer that is
holding the packed characters.
A Hint: To pack two characters into an unsigned integer variable, assign the
first character to the to the unsigned variable, shift the unsigned variable
fileft by 8 bit positions, and combine the unsigned variable with the second
character using the bitwise inclusive OR operator. The function should print
the characters in their bit format before and after they are packed into the
unsigned integer to prove that the characters are in fact packed correctly in
the unsigned variable.
Example: Printing the output of packCharacters(‘B’, ‘i’) should result in:
01000010 01101001
void unpackCharacters(unsigned int packedInt)
Using the right shift operator, the bitwise AND ( && ) operator, and a
mask, write function unpackCharacters that takes the unsigned integer from
above and unpacks it into two characters. This is the reverse operation of the
packCharacters function above. As a note: 65280 = 11111111 00000000. This
might be helpful as a mask for this function. Print the input integer and
output characters.
int power2(int num, int pow)
Left shifting an unsigned integer by 1 bit is equivalent to multiplying the
value by 2. Write function power^2 that takes two integer arguments, number
and pow and calculates (number * 2^pow). Use the shift operator to calculate
the result. The program should print the values as integers and as bits.
PART 2: IMPLEMENTING DJIKSTRA’S
In this part of the assignment, you’ll implement Dijkstra’s algorithm. There
are two parts to this: first, you need to read in the graph. Then, you need to
design your own data structures and implement Dijkstra’s to answer some
questions.
We’re providing you with three data files to use:
- miles.csv: a .csv (comma seperated values) file that stores the distance in miles between two cities in matrix form.
- nodes.csv: a .csv file that names all the nodes (cities) and their IDs
- edges.csv: a .csv file that species all the edges between two cities and their time.
Please note: Dijkstra’s is a common algorithm, and a classic intro algorithm
to implement. You can surely find implementations and information online.
However, we’re assigning this because implementing it is valuable to YOU,
particularly when you give it a good shot on your own before relying on
looking at other implementations.
In that vein, we encourage you to focus on trying to do this part all your
own. If you do refer to resources online, please note that in your source file
(in the notes at the top).
File Processing
Now, you haven’t read in files yet. Here’s a snippet of code that reads a file
in character by character:
#include
void readFile() {
FILE *cfPtr;
if ((cfPtr = fopen(“sample.txt”, “r”)) == NULL) {
printf(“File could not be opened\n”);
} else {
char c;
while (!feof(cfPtr)) {
c = fgetc(cfPtr);
printf(“%c\n”, c);
}
}
}
int main() {
readFile();
return 0;
}
—|—
Other functions that might be helpful:
- char *fgets(char *line, int maxchars, FILE *fp) that reads a line from a file
- int fscanf(FILE*, char *format, …) that reads a formatted line from a file
Graphs as a matrix and answering distance questions
You’ll be able to answer questions about the distance between two cities by
using the miles.csv file. It contains the distance between two cities as a
matrix: read in this file as a matrix (two-dimensional array), and implement
Dijkstra’s using this matrix.
No example of the file because it’s very large :)
A value of -1 means there is no edge between those cities.
Graphs as an adjacency list and time questions
Answer the questions about time using the nodes.csv and edges.csv files.
Implement your graph as an adjacency list, and implement Dijkstra’s using this
kind of graph representation.
The nodes represent locations. The file looks something like:
0001,Aberdeen
0002,Abilene
0003,Akron
0004,Albany
0005,Albuquerque
0006,Alexandria
The edges represent the time between cities. It looks something like this:
Abilene_TX Akron_OH 12 52 59
Abilene_TX Albany_GA 9 25 59
Abilene_TX Albany_OR 25 21 43
Abilene_TX Alexandria_VA 15 34 14
Abilene_TX Alexandria_LA 2 52 50
Abilene_TX Alhambra_AZ 5 19 53
Abilene_TX Alhambra_CA 11 17 29
Abilene_TX Alief_TX 2 07 42
Abilene_TX Aliso_Viejo_CA 11 18 08
Abilene_TX Allentown_PA 17 16 12
The columns are: source city, dest city, hours, mins, seconds to get from
source city to dest city.
QUESTIONS TO ANSWER
- What is the shortest path from Seattle_WA to Boston_MA? Please print out the path and the total distance.
- What is the fastest path from Seattle_WA to Boston_MA? Please print out the path and the total time.
- What is the shortest path from Minneapolis_MN to Ann Arbor_MI? Please print out the path and the total distance.
- What is the fastest path from Ann Arbor_MI to Minneapolis_MN? Please print out the path and the total time.
Sample output (can be formatted differently)
Seattle to Boston: 3,742.2 miles
Seattle -> Minneapolis -> Ann Arbor -> Boston (this is not the path; it's just representative)
PART 3: CHECK STYLE ISSUES
Please be sure to follow the Google C++ Style Guide for your C code.
Since you used clint for the last assignment, it is still available for you to
use this assignment. If you followed the directions last time, you DO NOT need
to copy clint.py to your a5 directory this time. Run clint as such:
bash% clint.py a5.c
No style-checking tool is perfect, but you should try to clean up any problems
that clint detects unless clint ags something that is definitely not a problem
in this particular context (but be sure you have very good reasons to ignore
any warnings).
SUBMISSION DETAILS
In your class git repo, we want to see a directory called “a5”. In that
folder, we want to see:
- a5_bits.c (for Part 1)
- a5_matrix.c (implementing Dijkstra’s using a matrix graph rep)
- a5_list.c (implementing Dijkstra’s using an adjacency list rep)
- a5.h
- Makefile
- The data files we provided you
We do NOT want to see: - Any other files
- Any executable file (e.g., fsort)
- back up files (.DS_Store, foobar.c~, …)
Make sure your repo is tagged! It must be tagged a5-final, and pushed before
the assignment deadline.
Makefile: For this assignment, create your own Makefile. - We will test your code by running make run; your run target should compile your code (if needed) and run the executable, printing out the answers to the questions noted above.
- Also include a target memcheck, so that when we run make memcheck, it compiles your code (if needed) and runs valgrind on the appropriate executable, generating the memory report.
Please make notes about other resources you have used for this assignment.
It might be helpful to have a README.md that describes any resources you’ve
used and why. It could be a good place to show the output of your code as well
(we will run your code, but it’s usually good to have a note about how to run
it and what to expect as the output. Think of this as a practice of writing up
what you did, why, and what you found out).
