"20151910042-刘鹏-DSA实验08-树结构实验1记录与分析"

需积分: 0 192 浏览量更新于2023-12-19 收藏 8.19MB DOCX 举报

本次实验旨在通过树结构实验来熟悉与树和二叉树有关的数据结构与算法，以及主讲教材Chapter 8的代码片段。实验使用的实验平台为Windows 10 1703 Enterprise中文版，并且使用了Python 3.6.0和Wing IDE Professional 6.0.5-1集成开发环境。在实验中，我完成了题目为"程序代码：12345678910111213141516171819202122232425262728293031323334"的实验内容。通过实验，我对树结构有了更深入的了解，学会了如何使用Python编程语言来实现树结构相关的算法和数据结构。在实践中，我不仅熟悉了树结构的基本概念，还掌握了如何在Python环境下进行相关编程操作。通过实验记录和结果分析来看，我基本掌握了树结构实验内容，并能够运用所学知识进行相关实验操作。在未来的学习中，我将继续深入学习与树和二叉树有关的数据结构与算法，不断提升自己的编程能力和实践技巧。 Overall, this experiment helped me to familiarize myself with data structures and algorithms related to trees and binary trees, and to gain a deeper understanding of the code fragments from Chapter 8 of the main teaching materials. Through using the Windows 10 1703 Enterprise Chinese version, Python 3.6.0 and Wing IDE Professional 6.0.5-1 integrated development environment, I completed the experiment with the program code: 12345678910111213141516171819202122232425262728293031323334. Through this experiment, I gained a deeper understanding of tree structures and learned how to implement tree structure-related algorithms and data structures using the Python programming language. Throughout the experiment, I not only familiarized myself with the basic concepts of tree structures, but also mastered how to carry out related programming operations in Python environment. Based on the experiment records and results analysis, I have basically mastered the content of tree structure experiments and am able to apply the knowledge in practical experiments. In future studies, I will continue to deepen my understanding of data structures and algorithms related to trees and binary trees, constantly improving my programming skills and practical abilities.

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

第 7 页共 40 页

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

def _attach(self,p,t1,t2):

"""Atach trees t1 and t2 as left and right subtrees of external p."""

node = self._validate(p)

if not self.is_leaf(p): raise ValueError('position must be leaf')

if not type(self) is type(t1) is type(t2):

# all 3 trees must be same type

raise TypeError('Tree type must match')

self._size += len(t1) + len(t2)

if not t1.is_empty(): # attached t1 as left subtree of node

t1._root._parent = node

node._left = t1._root

t1._root = None # set t1 instance to empty

t1._size = 0

if not t2.is_empty: # attached t2 as right subtree of node

t2._root._parent = node

node._right = t2._root

t2._root = None # set t2 instance to empty

t2._size = 0

#----------------------------- my main function -----------------------------

运行结果：

2 题

程序代码：

# 8.4.4 Implementing Tree Traversals in Python

class LinkedQueue:

"""FIFO queue implementation using a singly linked list for storage."""

class _Node:

"""Lightweight, nonpublic class for storing a singly linked node."""

__slots__ = '_element','_next' # streamline memory usage

def __init__(self,element,next): # initialize node's field

self._element = element # reference to user's element

self._next = next # reference to next node

def __init__(self):

"""Create an empty queue."""

self._head = None

self._tail = None

self._size = 0 # number of queue elements

def __len__(self):

"""Return the number of elements in the queue."""

return self._size

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

第 8 页共 40 页

def is_empty(self):

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

return self._size == 0

def first(self):

"""Return (but do not remove) the element at the front of the queue."""

if self.is_empty():

raise Empty('Queue is empty')

return self._head._element # front aligned with head of list

def dequeue(self):

"""Remove and return the first element of the queue (i.e., FIFO).

Raise Empty exception if the queue is empty.

"""

if self.is_empty():

raise Empty('Queue is empty')

answer = self._head._element

self._head = self._head._next

self._size -= 1

if self.is_empty(): # special case as queue is empty

self._tail = None # removed head had been the tail

return answer

def enqueue(self,e):

"""Add an element to the back of queue."""

newest = self._Node(e,None) # node will be new tail node

if self.is_empty():

self._head = newest # special case: previously empty

else:

self._tail._next = newest

self._tail = newest # update reference to tail node

self._size += 1

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')

剩余39页未读，继续阅读

生活教会我们

粉丝: 33
资源: 315

"20151910042-刘鹏-DSA实验08-树结构实验1记录与分析"

数据结构实验的树，源程序代码

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

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

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

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

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

20151910042-刘鹏-DSA思考题-08 - Binary Tree and Priority Queue1

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

20151910042-刘鹏-DSA思考题-011

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

最新资源