高级数据结构.

Presentation on theme: "高级数据结构."— Presentation transcript:

1 高级数据结构

2 数据结构:堆栈(1) 堆栈是数据集合体,其中数据具有“后进先出(LIFO)”性质,即最后加入堆栈的数据总是首先取出. 用途:如表达式计算 2

3 数据结构:堆栈(2) 堆栈的操作 抽象数据类型:尽管不知道堆栈里准备放什么,但操作方式是固定的. 编程实例:stack.py push(x)
pop() isEmpty() 抽象数据类型:尽管不知道堆栈里准备放什么,但操作方式是固定的. 编程实例:stack.py 3

4 数据结构:堆栈(3)

5 数据结构:队列 队列是数据集合体,其中数据具有“先进先出 (FIFO)”性质,即最先进入队列的数据总是首先取出.
队列也是一种抽象数据类型,完全由操作定义其特性. 两个主要操作： enqueue:入队 dequeue:出队 5

6 数据结构:链表(1) 列表成员间的逻辑关系如何表示? 顺序存储,存储位置就表示其先后关系 非顺序存储,先后关系靠链接来表示 6

7 数据结构:链表(2) 链表 插入删除很方便 编程实例:linkedlist.py 7

8 并行计算

9 程序的执行 von Neumann体系结构计算机:程序(指令序列)和数据都存储在内存中
CPU根据程序计数器PC(或称指令指针IP)的内容, 取出当前指令执行,然后PC被赋予下一条要执行的指令的地址. 虽然也存在指令级并行技术,但我们讨论的是程序级的并行. 9 9

10 串行执行程序 CPU执行一个程序时总是从该程序的第一条指令开始,不间断地一直到执行到最后一条指令. 只有一个程序结束,才会去执行下一个程序.
CPU每次由一个程序独占.只要前一个程序还没有结束,下一个程序就不能使用CPU. 缺点:系统资源的利用率不高. 计算机系统中有许多资源.当一个程序在使用某个资源时,其他资源是空闲的.如果允许其他程序使用空闲资源,就能提高系统资源的利用率. 10 10

11 并发执行 计算机程序的执行是由操作系统控制的.现代操作系统都支持所谓"多道程序"或"多任务",即允许多个程序"同时"执行.
"同时":在只有一个CPU的情况下,是不可能有真正的多个程序"同时"运行的,因为CPU在任一时刻只能执行一条指令! 分时使用CPU,即CPU在多个程序之间切换. 这种多个相互独立的程序交叉执行的方式称为并发或并行执行. 多处理器/多核处理器上能真正并行. 11 11

12 进程 进程是指程序的一次执行所形成的实体.程序一旦执行,即创建一个进程.
进程的构成:程序代码+进程状态信息(上下文,包括程序数据的当前值,当前执行点等). 程序与进程:不同程序的执行对应不同的进程;同一个程序多次执行也创建多个进程(相同程序代码+不同上下文). OS调度进程:上下文切换代价高.

13 线程 线程,是指程序(进程)中的一段代码,它构成程序中一个相对独立的执行流. 线程是一个程序内部的多任务机制.
字面意义:线程是程序内部的一个"线索” 线程是一个程序内部的多任务机制. 一个程序中可以有多个执行"线索".

14 进程 vs 线程 进程带有独立的状态信息,而一个进程内的多个线程则共享状态,内存和其他资源
进程有独立的地址空间,而同一进程的多个线程共享地址空间 进程间通信(IPC)较麻烦,而线程之间可通过共享内存通信 进程上下文切换开销大,而线程切换开销小

15 多线程编程 线程原是OS中的概念,是系统的工具,用于系统的功能 线程现在已成为用户程序设计的工具 用在需要并行执行的场合:
科学应用:更快地计算; 解决阻塞:用户输入;在长时间计算期间进行显示服务;多媒体,动画等.

16 Python多线程:thread模块 程序开始执行,即构成主线程.其中随时可以创建新线程去执行特定任务. 线程的创建和启动:
thread.start_new_thread (function, args) 创建新线程并立即返回 新线程启动,向函数function传递参数元组args,并执行function 线程终止:当函数function返回.

17 例eg9_3:thread模块用法 def task(tName,n): for i in range(n): print "%s:%d\n" % (tName,i) print "%s:任务完成!回真身去喽...\n" % tName thread.interrupt_main() print "<老孙>:我是孙悟空!" print "<老孙>:我拔根毫毛变个小猴儿~~~" thread.start_new_thread(task,("<小猴>",3)) print "<老孙>:我睡会儿,小猴儿干完活再叫醒我~~~\n" while True: print "<老孙>:Zzzzzzz\n" 17

18 例eg9_4:thread模块用法 def task(tName,n,delay): for i in range(n): time.sleep(delay) print "%s:%d\n" % (tName,i) print "<老孙>:我是孙悟空!" print "<老孙>:我拔根毫毛变个小猴儿<哼>" thread.start_new_thread(task,("<哼>",5,2)) print "<老孙>:我再拔根毫毛变个小猴儿<哈>" thread.start_new_thread(task,("<哈>",5,4)) print "<老孙>:不管你们喽,俺老孙去也~~~\n" 18

19 Python多线程:threading模块
向构造器传递要执行的函数和参数 t = Thread(target=func,args=(...)) 调用线程对象的start()方法启动线程 t.start()

20 例eg9_5:threading模块用法 def task(tName,n,delay): for i in range(n): sleep(delay) print "%s:%d\n" % (tName,i) print "<老孙>:我是孙悟空!" print "<老孙>:我拔根毫毛变个小猴儿<哼>" t1 = Thread(target=task,args=("<哼>",5,2)) print "<老孙>:我再拔根毫毛变个小猴儿<哈>" t2 = Thread(target=task,args=("<哈>",5,4)) t1.start() t2.start() print "<老孙>:不管你们喽,俺老孙去也~~~\n" 20

21 Python多线程:threading模块
用法II: 定义Thread的子类MyThread,并覆写(重定义)__init__和run方法 class MyThread(threading.Thread): def __init__(self,threadName,delay): threading.Thread.__init__(self) ...... def run(self): 创建MyThread线程对象并调用其start() t = myThread(...) t.start() 21

22 例eg9_6:threading模块用法 class MyThread(Thread): def __init__(self,tName,n,delay): Thread.__init__(self) self.name = tName self.loopnum = n self.delay = delay def run(self): print self.name + ": 上场...\n" task(self.name,self.loopnum,self.delay) print self.name + ": 退场...\n"

23 作业 1. 实现class queue enqueue(self, item) dequeue(self) isEmpty(self)
getLen(self)

24 作业 2. Create and test a Set class to represent a classical set. Your sets should support the following methods: Set(elements) Create a set (elements is the initial list of items in the set). addElement(x) Adds x to the set. deleteElement(x) Removes x from the set, if present. If x is not in the set, the set is left unchanged. member(x) Returns true if x is in the set and false otherwise. intersection(set2) Returns a new set containing just those elements that are common to this set and set2. union(set2) Returns a new set containing all of elements that are in this set, set2, or both. subtract(set2) Returns a new set containing all the elements of this set that are not in set2. (Section 11.8 Programming Problems 19)