木其工作室 http://www.xmsydw.com
Department of Computing and Information Systems
COMP10002 Foundations of Algorithms
Semester 2, 2014
Assignment 2
Learning Outcomes
In this project you will demonstrate your understanding of dynamic memory and linked data structures.
You will also extend your skills in terms of program design, testing, and debugging.
Trees, Trees, Trees
The Binary Search Tree (BST) is a linked data structure that can be used to implement a dictionary data
structure. In this project you will write an “interpreter” that manipulates items in a BST, supporting a
small number of operations such as inserting and printing.
To get started, copy and study the program ass2-skel.c linked from the assignment FAQ page at
http://people.eng.unimelb.edu.au/ammoffat/teaching/10002/ass2/. The FAQ page is also
linked from the LMS. The skeleton program compiles cleanly, and provides the framework necessary for
a simple “language” for manipulating binary search trees.
Commands in this language are all one letter long, and have either zero or one string arguments
each. A stub function is provided for each type of command that is to be implemented; and the main
program and auxiliary functions are all complete and should not require any modification. Each stage of
the project requires that you implement one or more of the following commands:
“i”, insert an item;
“p”, generate a simple printout of the tree that has been built;
“t”, tabulate some statistics about the tree that has been formed;
“r”, rotate an item one level closer to the root;
“s”, generate a snazzy printout of the tree that has been built; and
“f”, free all of the space currently allocated to the tree, and restart from an empty tree.
The program can either take its input from stdin or from a file named on the command line. In the latter
case, the commands are echoed as they are read, to provide understandable output. The interpreter loop
ends, and the program exits, when end of file is encountered.
Stage 1 – Inserting and Printing (9/15 marks)
Complete the functions do insert() and do print s().
Insertion should follow the usual binary tree ordering, and youmay simply call strcmp() to establish
ordering. If a string is already present in the tree, and another insert command for that string is issued,
the tree should be left unchanged. That is, the tree should not contain duplicate strings. Note that there is
no use of polymorphism in this project, and you do not need to make use of function pointers or void*
pointers. That is, your code will be more like listops.c than treeops.c; and should all be in one file.
The function do print s() draws a simple picture of the tree as it stands at that point in time,
without changing the tree at all. The root of the tree should be against the left margin. The strings should
be reverse alphabetic down the page, with each node of the tree indented five more characters than its
1parent. Here is one possible sequence of inputs and outputs (turn the page 90 degrees clockwise to see
the tree):
> i mary
> i had
> i a
> i little
> i lamb
> p
mary
little
lamb
had
a
>
Stage 2 – Tree Size (11/15 marks)
Now add in the body of the do tabulate() function. It prints a small table reporting the number of
items in the tree, and the average and maximum depth in the tree of those items. The root of the tree is
at depth 1. Continuing on from the previous example, a “t” command would report:
> t
size : 5
avg depth: 2.60
max depth: 4
>
Stage 3 – Edge Rotations (13/15 marks)
Ok, now for something different. The diagram on the next page shows what is meant by an edge rotation
in a BST: starting with the tree on the left, a rotation at the node whose key is the string “d” results in the
tree on the right; conversely, starting with the tree on the right, an edge rotation at the node whose key
is “b” results in the tree on the left. Note how one of the subtrees is reassigned in a manner that ensures
that the post-rotation tree is still a binary search tree. A rotation alters the structure of a tree, but not
its contents. For example, if subtree E is larger than subtree A, the tree on the right will have a smaller
average node depth, and thus better average searching and insertion characteristics.
Write the body of the function do rotate() that identifies the location of its argument in the tree,
and then rotates the tree at that position. If the argument string is at the root of the tree, or if the
argument string does not appear anywhere in the tree, then the original tree should be returned unchanged.
Warning: there are a lot of pointers to be re-assigned, and multiple cases to be considered. Draw pictures
on paper first, before you try and write the code. Continuing the same example, we would have:
2b
b
b d
A
C A E C
E
rotate at
rotate at
d
d
Edge rotation in a Binary Search Tree. The lower node is “rotated” in to the position
previously occupied by its parent, then subtrees are rearranged and all pointers
updated so that the tree is still in alphabetic order.
> r had
> p
mary
little
lamb
had
a
> t
size : 5
avg depth: 2.40
max depth: 4
>
Stage 4 – Resetting the Tree (14/15 marks)
The “f” command frees up all space that has been allocated to the tree and its strings by making calls to
free(), and resets the tree back to an empty initial state:
> f
> t
size : 0
>
The tree should be freed up from the leaves back toward the root, so that you don’t end up with a memory
leak caused by unreachable data.
Stage 5 – Snazzy Printing (15/15 marks)
For one last mark, add the details of the second “snazzy” print command. For the same tree as before,
(after rotating “had”), the output would be
3> s
+--
+--mary
| | +--
| +--little
| | +--
| +--lamb
| +--
had
| +--
+--a
+--
>
There are more examples linked from the FAQ page.
Purely for Fun (and not for submission)
Implement a “d” command that deletes the indicated string from the tree. If the string is a leaf, deletion is
easy. If it is an internal node, locate the alphabetically next node and swap it in to the position occupied
by the string being deleted.
The boring stuff...
This project is worth 15% of your final mark. A rubric explaining the expectations that you will be
marked will be provided shortly via the LMS.
You need to submit your program for assessment; detailed instructions on how to do that will be
posted on the LMS once submissions are opened. Submission will not be done via the LMS; instead you
will need to log in to a Unix server and submit your files to a software system known as submit. You
can (and should) use submit both early and often – to get used to the way it works, and also to check
that your program compiles correctly on our test system, which has some different characteristics to the
lab machines. Only the last submission that you make before the deadline will be marked.
You may discuss your work during your workshop, and with others in the class, but what gets typed
into your program must be individual work, not copied from anyone else. So, do not give hard copy
or soft copy of your work to anyone; do not “lend” your “Uni backup” memory stick to others for any
reason at all; and do not ask others to give you their programs “just so that I can take a look and get
some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a very
firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their
acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program
that undertakes deep structural analysis of C code identifying regions of similarity will be run over all
submissions in “compare every pair” mode. Students whose programs are so identified will be referred
to the Student Center. See https://academichonesty.unimelb.edu.au for more information.
Deadline: Programs not submitted by 10:00am on Monday 20 October will lose penalty marks at
the rate of two marks per day or part day late. Students seeking extensions for medical or other “outside
my control” reasons should email Alistair, ammoffat@unimelb.edu.au as soon as possible after those
circumstances arise.
Marks and a sample solution will be available on the LMS by Monday 3 November.
And remember, algorithms are fun!
4
相关推荐
c语言,二叉树的建立和遍历操作。数据结构Bitree
数据结构 二叉树 用C语言创建与遍历 前序 中序遍历 后序遍历
构造二叉树 求根结点 打印 返回双亲 左孩子 右孩子 左兄弟 右兄弟 判空 求深度 先序遍历 中序遍历 后序遍历 层序遍历 特定位置插入子树 删除结点子树 清空二叉树 销毁
实现了二叉树的前向生成以及前向遍历。属于二叉树的基本操作。
C语言二叉树三种遍历算法及其广义表表示 VS2012编写 基于先序遍历的构造算法:输入是二叉树的先序序列,但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用’.’字符表示。 分别利用先序遍历、中序遍历、...
利用c语言实现对二叉树的建立和非递归的中序遍历
这是一个关于二叉树的C语言源码,它实现了二叉树的建立和三种遍历方式。
一个经典的C语言二叉树结构源程序,非常适合学习数据结构的朋友们,也适合自学者。绝对无误,在VC++6.0上运行通过。
数据结构C语言二叉树实验代码 1.掌握二叉树的特点,以及的二叉链表存储结构。 2.熟练掌握二叉树的各种操作,如建立、遍历、查找和输出。 3.并利用已经掌握的知识进行实际应用。
C语言二叉树的创建与遍历
C语言二叉树程序,初学者可以学习一下,很有帮助的
C语言二叉树PPT课件.pptx
C语言二叉树PPT学习教案.pptx
C语言 二叉树 C 数据结构 用C语言实现建立一棵二叉树 支持插入,删除结点,画出二叉树
二叉树遍历,先根,中根,后根,及程序分析。c语言实现
利用递归方式完成二叉树的简单创建以及遍历。
利用C语言编写的二叉树前序遍历程序,并有实验分析
C语言 二叉树实验报告,创建并输出二叉树,输出内容有:图形、数的深度、数的叶子数量。然后根据所创建的二叉树进行线序遍历,创建一棵先序线索二叉树链表,并非递归地输出先序遍历序列。包含各函数算法,源代码。
C语言实现二叉树的前中后序遍历,已经经过了测试,可以直接使用。能运行出结果。欢迎下载!