没有合适的资源?快使用搜索试试~ 我知道了~
20151910042-刘鹏-DSA实验06-栈与队列实验1
需积分: 0 1 下载量 43 浏览量
2022-08-08
17:45:34
上传
评论
收藏 1.91MB DOCX 举报
温馨提示
试读
29页
3. 阅读实验教材第2章的问题,将C程序转化为Python程序(选做)。三、实验平台Windows 10 1703 Enterprise 中文版;Wing ID
资源推荐
资源详情
资源评论
云南大学数学与统计学院数学系信息与计算科学专业
第 1 页 共 29 页
云南大学数学与统计学院
上机实践报告
课程名称:数据结构与算法实验
年级:2015 级
上机实践成绩:
指导教师:陆正福
姓名:刘鹏
上机实践名称:数组序列实验
学号:20151910042
上机实践日期:2017-04-10
上机实践编号:No.06
组号:
上机实践时间:上午 3、4 节
一、实验目的
1. 熟悉与栈、队列等有关的数据结构与算法;
2. 熟悉主讲教材 Chapter 6 的代码片段。
二、实验内容
1. 线性表有关的数据结构设计与算法设计;
2. 调试主讲教材 Chapter 6 的 Python 程序;
3. 阅读实验教材第 2 章的问题,将 C 程序转化为 Python 程序(选做)。
三、实验平台
Windows 10 1703 Enterprise 中文版;
Python 3.6.0;
Wing IDE Professional 6.0.5-1 集成开发环境。
四、实验记录与实验结果分析
1 题
基于适配器模式,用数组实现栈逻辑结构
程序代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 6.1.2 Simple Array-Based Stack Implementation
class Empty(Exception):
"""Error attempting to access an element from an empty container."""
pass
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = [] # nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
云南大学数学与统计学院数学系信息与计算科学专业
第 2 页 共 29 页
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def push(self,e):
"""Add element e to the top of the stack."""
self._data.append(e) # new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1] # the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty('Stack is empty')
return self._data.pop() # remove last item from list
#----------------------------- my main function -----------------------------
a = ArrayStack()
print('1: the length of a is',a.__len__())
a.push(8)
print('2: ',a._data)
a.push('LiuPeng')
print('3: ',a._data)
a.push('1 + 2 + 3')
print('4: ',a._data)
print('5: ',a.pop())
print('6: now the length of a is',a.__len__())
程序代码 1
运行结果:
运行结果 1
代码分析:
这几行代码,最核心的部分是用适配器模式,把一个列表作为底层实际结构,嵌入到类里面,使之看起来像是一个栈。
这种模式是最终重要的,之前仅仅是草草看了这一段代码,翻译了一遍,还是有很多收获的。
云南大学数学与统计学院数学系信息与计算科学专业
第 3 页 共 29 页
2 题
利用栈逻辑结构,实现将一个文本文件(utf-8)按照行顺序反向输出。
程序代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# 6.1.3 Reversing Data Using a Stack
class Empty(Exception):
"""Error attempting to access an element from an empty container."""
pass
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = [] # nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self,e):
"""Add element e to the top of the stack."""
self._data.append(e) # new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty('Stack is empty')
return self._data[-1] # the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise Empty('Stack is empty')
return self._data.pop() # remove last item from list
def iter(self):
return iter(self._data)
云南大学数学与统计学院数学系信息与计算科学专业
第 4 页 共 29 页
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import codecs
def reverse_file(filename):
"""Overwrite given file with its contents line-by-line reversed."""
S = ArrayStack()
original = codecs.open(filename,'r',encoding='utf-8')
for line in original:
S.push(line.rstrip('\n'))
# we will re-insert newlines whth writing
original.close
# now we ovrewrite with contents in LIFO order
output = codecs.open(filename,'w',encoding='utf-8')
# reopening file overwrites original
while not S.is_empty():
output.write(S.pop() + '\n') # re-insert newline characters
output.close()
#----------------------------- my main function -----------------------------
import codecs
S_1 = ArrayStack()
a = S_1.iter()
original = codecs.open('TEST_6.1.3.txt','r',encoding='utf-8')
for line in original:
S_1.push(line)
original.close
for i in a:
print(i.rstrip('\n'))
reverse_file('TEST_6.1.3.txt')
print('\n-------------------------')
S_2 = ArrayStack()
a = S_2.iter()
original = codecs.open('TEST_6.1.3.txt','r',encoding='utf-8')
for line in original:
S_2.push(line)
# we will re-insert newlines whth writing
original.close
for i in a:
print(i.rstrip('\n'))
程序代码 2
运行结果:
云南大学数学与统计学院数学系信息与计算科学专业
第 5 页 共 29 页
运行结果 2
代码分析:
可以看到,这段代码与课本上的类稍有不同,加了一个 iter 方法,进行了迭代器生成。因为这里的 ArrayStack 就是用
一个列表伪装了一个栈,所以内部必然支持迭代器生成。我加了一个迭代器,目的是输出所有的栈元素。当然,也可以通
过文件,直接输出所有的行。
剩余28页未读,继续阅读
资源评论
蔓誅裟華
- 粉丝: 19
- 资源: 304
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功