C++代写：CS204-B-tree

发表于 | 分类于
次需要代写的需求是用C++实现一个B-tree，给了基本的框架代码，以及给定的输入和输出样式。虽然不难写，但是这种需求稍微有一个Bug，就会导致排查相当麻烦。

Files to hand in are

1
2
3
4
5
6
BTree.cpp
InternalNode.cpp
InernalNode.h
LeafNode.cpp
LeafNode.h
authors.csv

Files

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BTreeDriver.cpp
BTreeDebugDriver.cpp
BTree.cpp
BTree.h
BTreeNode.cpp
BTreeNode.h
InternalNode.cpp
InernalNode.h
LeafNode.cpp
LeafNode.h
Makefile (uses BTreeDebugDriver.cpp to produce BTree)
Makefile2 (uses BTreeDriver.cpp to produce BTree2)
QueueAr.cpp
QueueAr.h
vector.h
vector.cpp
dsexceptions.h

Description

Your program will read a file that contains a series of integers that it will insert into a BTree, and then print to the screen a breadth first traversal of the BTree. Your task will be to provide the implementation code for the BTree, InternalNode, and LeafNode classes. Since the insert methods for the nodes will be quite long, you should add new methods so that no method is more than 30 lines long. We will not grade on style, but the TAs and I will be of little help with poor quality code. You may only alter those files that will be handed in. The program will take three command line parameters: 1) filename; 2) M, the number of children that internal nodes have; and 3) L, the number of integers each leaf node holds. The input file will not include more than 1000 integers. Since only integers will be stored in the BTree class, I did not implement it as a template. When a node splits, the new node created will always contain at least as many entries as the remaining old node, and will contain the larger values. The output must match that shown in the sample.

There is one change in the data structure from the book’s; the internal nodes should keep track of the minimum value for every child. You will find this easier than not having the minimum for the first child.

How did I write this code so fast? I used procedural abstraction. I thought about the tasks, their subtasks, and the subtasks of those subtasks. (You should write them down.) If I could state a subtask, then I planned on writing a separate function to do just that subtask. I found that the tasks of the InternalNode class matched that of the LeafNode class, so I postponed as much work on the InternalNode class as long as possible so that I could learn from my LeafNode mistakes. I worked top down with stubs for the subtasks, and got that iteration to compile without warnings! This avoids making the same mistake repeatedly—the compiler is a very good teacher. When I could do even minimal testing, I did it. What I learned from debugging kept me from duplicating those mistakes in later code, and reminded me of issues that I had forgot about. Sometimes when I addressed a new issue in a method I discovered that I had to add a lot of code. If there is a whole lot of new code, the issue deserved its own method with an appropriate name. It is a simple matter of cutting and pasting, and keeps each method short, and understandable. By the time I was done my LeafNode class had nine methods, and no method has more than 30 lines. Once the LeafNode class worked perfectly, I copied the LeafNode class methods as InternalNode class methods, and did a search and replace from values to keys! Though there are child sibling and parent issues for the InternalNode class, the basic LeafNode code provided a great starting point. In the end my InernalNode class had 13 methods. In comparison to the first time I wrote this with long insert functions a few years ago, the debugging was much faster this time because of the small methods