- 作业标题：CSCI 2122 - Systems Programming - lab7 Searching Binary Trees and Constructing Maps
- 课程名称：Dalhouse University CSCI 2122 Systems Programming
- 完成周期：2天
1. Introduction
This lab is designed to introduce you to depth-first search (DFS), breadth-first search (BFS), and maps (dictionaries). By the end of this lab, you will be expected to understand how to implement those search algorithms and data structures.
In this lab you are expected to perform the basics of cloning your Lab 7 repository from the GitLab course group. A link to the course group can be found here and your repository can be found in the Lab7 subgroup. See the Lab Technical Document for more information on using git. You will notice that your repository has a file in the Lab7 directory named delete this file. Due to the limitations of GitLab, we are not able to push completely empty directories. Before you push your work to your repository (which should be in the Lab7 directory anyway), make sure to first use the git rm command to remove the extra file. If you do not, your pipeline could fail.
2. Tree and Graph Traversals
In the last lab you were expected to build a binary tree and print the state of that tree in a variety of configurations (in-order, pre-order, post-order, and reverse order). The manner and order in which you move through the trees in order to produce an outcome is referred to as a traversal. Traversals come in many types and throughout your university career in Computer Science you are likely to run into many, especially in your Algorithms Analysis classes.
In this lab we will go over, and implement, two of the more well-known traversal algorithms.
In the last lab, you created a binary tree, which consisted of a hierarchal configuration of nodes. Each node consisted of a data pointer, as well as pointers to two potential child nodes. As you inserted data into your binary tree, you followed an algorithm for deciding how to navigate through each node in order to find the correct place to store the incoming data. The rules on the nodes were very specific: once you were in a node, there was no way to go backwards; nodes could only be added as children of nodes who didn’t already have children in the designated place; there was no path through the tree which would have you visit the same node twice. As such, the structure of a binary tree is very restrained, which prevents you from running into more complicated structures, such as nodes which create a path that leads back to a node you’ve visited, which is called a cycle.
A tree is a specific type of structure known as a graph, which is not the bar-chart kind of graph. Graphs are a
collection of nodes, also called vertices, which are connected by a series of paths from one node to another, called edges. Graphs, like trees, come in a variety of different types, including directed graphs (you can only travel forward down an edge, but not backward) and undirected graphs (edges can be travelled in both directions). It’s also possible for edges to have weights, which give you the ability to measure things such as distance, or cost, between vertices.
Graphs can be visualized as a variety of things, including the time cost it takes to perform a series of tasks, or the cities in a province which are connected by highways. There are many algorithms used for generating valuable data from graphs, but in this lab we are going to restrict ourselves to binary trees and two specific traversals: depth-first search, and breadth-first search.
3. Lab 7 Function Contracts
In this lab you will be responsible for fulfilling two lab contracts: the Search contract, and the Dictionary contract. Each contract is designed to test you on some of the things you’ve learned throughout the instruction portion of this lab. All contracts must be completed exactly as the requirements are laid out. Be very careful to thoroughly read the contract instructions before proceeding. This does not, however, preclude you from writing more functions than you are asked for. You may write as many additional functions as you wish in your C source files.
All contracts are designed to be submitted without a main function, but that does not mean you cannot write a main function in order to test your code yourself. It may be more convenient for you to write a C source file with a main function by itself and take advantage of the compiler’s ability to link files together by accepting multiple source files as inputs. When you push your code to Gitlab, you don’t need to git add any of your extra main function source files.
For those of you who are concerned, when deciding which naming conventions you want to use in your code, favour consistency in style, not dedication to a style that doesn’t work. The contracts in this document are worth the following points values, for a total of 10
。。。
4. Submission
4.1. Required Files
Each file must be contained in the directory listed in the structure requirement diagram below. These files include:
- bintree.c
- bintree.h
- dictionary.c
- dictionary.h
- Makefile (for search)
- Makefile (for dictionary)
You may submit other files that your Makefile needs to function correctly. Note that the above files are simply the minimum requirements to pass the pipeline. Any additional files will not count against you.
4.2. Submission Procedure and Expectations
Your code will be submitted to your Lab 7 GitLab repository using the same method as outlined in the Lab Technical Document. Refer to that document if you do not remember how to submit files via the GitLab service. A link to your repository can be found in the Lab7 subgroup of the CSCI 2122 GitLab group here.
。。。
