【免费】20151910042-刘鹏-DSA实验11-查找表实验1资源-CSDN文库

需积分: 0 97 浏览量 2022-08-08 19:52:13 上传评论收藏 56KB DOCX 举报

资源详情

资源评论

资源推荐

云南大学数学与统计学院数学系信息与计算科学专业

第 1 页共 15 页

云南大学数学与统计学院

上机实践报告

课程名称：数据结构与算法实验

年级：2015 级

上机实践成绩：

指导教师：陆正福

姓名：刘鹏

上机实践名称：查找树实验

学号：20151910042

上机实践日期：2017-05-14

上机实践编号：No.11

组号：

上机实践时间：上午 3、4 节

一、实验目的

1. 熟悉与查找树有关的数据结构与算法

2. 熟悉主讲教材 Chapter 11 的代码片段

二、实验内容

1. 与查找树有关的数据结构设计与算法设计

2. 调试主讲教材 Chapter 11 的 Python 程序

三、实验平台

Windows 10 1703 Enterprise 中文版；

Python 3.6.0；

Wing IDE Professional 6.0.5-1 集成开发环境。

四、实验记录与实验结果分析

# 11.6.2 Python Implementation

class Tree:

"""Abstract base class representing a tree structure."""

#------------------- nested Position class -------------------

class Position:

"""An abstraction representing the location of a single element."""

def element(self):

"""Return the element stored at this Position."""

raise NotImplementedError('must be implemented by subclass')

def __eq__(self,other):

"""Return True if other Positon represents the same location."""

raise NotImplementedError('must be implemented by subclass')

def __ne__(self,other):

"""Return True if other does not represent the same location."""

return not (self == other)

#---------- abstract methods that concrete subclass must support ----------

def root(self):

"""Return Position representing the tree's root (or None if empty)."""

raise NotImplementedError('must be implemented by subclass')

def parent(self,p):

云南大学数学与统计学院数学系信息与计算科学专业

第 2 页共 15 页

"""Return Position representing p's parent (or None if p is root)."""

raise NotImplementedError('must be implemented by subclass')

def num_children(self,p):

"""Return the number of children that Position p has."""

raise NotImplementedError('must be implemented by subclass')

def children(self,p):

"""Generate an iteration of Positions representing p's children."""

raise NotImplementedError('must be implemented by subclass')

def __len__(self):

"""Return the total number of elements in the tree."""

raise NotImplementedError('must be implemented by subclass')

#---------- concrete methods implemented in this class ----------

def is_root(self,p):

"""Return True if Position p represents the root of the tree."""

return self.root() == p

def is_leaf(self,p):

"""Return True if Positoin p does not have any children."""

return self.num_children == 0

def is_empty(self):

"""Return True if the tree is empty."""

return len(self) == 0

#---------- new methods in this section ----------

def depth(self,p):

"""Return the number of levels separating Positon p from the root."""

if self.is_root(p):

return 0

else:

return 1 + self.depth(self.parent(p))

def _height1(self): # works, but O(n^2) worst-case time

"""Return the height of the tree."""

return max(self.depth(p) for p in self.positions() if self.is_leaf(p))

def _height2(self,p):

"""Ruturn the height of the subtree rooted at Postion p."""

if self.is_leaf(p):

return 0

else:

return 1 + max(self._height2(c) for c in self.children(p))

def height(self,p=None):

"""Return the height of the subtree rooted ar Position p.

剩余14页未读，继续阅读

评论收藏

内容反馈

陌陌的日记

粉丝: 11
资源: 319

20151910042-刘鹏-DSA实验11-查找表实验1

评论0

最新资源

20151910042-刘鹏-DSA实验11-查找表实验1

评论0

20151910042-刘鹏-11-位运算1

20151910042-刘鹏-DSA思考题-011

20151910042-刘鹏-DSA思考题-021

20151910042-刘鹏-DSA实验03-算法分析1

20151910042-刘鹏-DSA思考题-041

20151910042-刘鹏-DSA思考题-05 - Stack and Queue1

20151910042-刘鹏-MC实验03-离散对数问题实验1

20151910042-刘鹏-DSA实验05-数组序列实验1

20151910042-刘鹏-DSA实验06-栈与队列实验1

20151910042-刘鹏-DSA实验04-递归实验1

20151910042-刘鹏-DSA实验08-树结构实验1

20151910042-刘鹏-DSA实验15-存储管理与B-树实验1

20151910042-刘鹏-CN实验02-候选平台预备实验1

20151910042-刘鹏-AG实验01-图搜索算法1

20151910042-刘鹏-DSA实验10-映射-哈希表-跳表实验1

20151910042-刘鹏-AG实验07-中国邮递员问题1

20151910042-刘鹏-DSA实验01-高级语言基本编程实验1

20151910042-刘鹏-DSA实验13-文本处理实验1

20151910042-刘鹏-DSA实验14-图结构实验1

20151910042-刘鹏-DSA实验12-排序与选择实验1

20151910042-刘鹏-DSA思考题-12 - Dictionary1

20151910042-刘鹏-AG实验06-有向图的弧连通度1

20151910042-刘鹏-DSA实验07-链表与表的抽象化实验1

20151910042-刘鹏-DSA思考题-13 - 1

20151910042-刘鹏-DSA思考题-14 - 1

最新资源