数据结构新帖来了~

珍妮王小钰

程序设计 =数据结构+算法◎★Jû    khuen  FJKLC6unhqtwxAop√∵ ←→ ←→
再简单的说数据结构就是关系，数据元素相互之间存在的一种或多种特定关系的集合。
F传统上，把数据结够分成逻辑结构>和物理结构
逻辑结构：指数据对象中数据元素之间的相互关系，也是我们今后最需要关注和讨论的问题。
    物理结构：是指数据的逻辑结构在计算机中的存储形式。


逻辑结构之：
K集合结构（集合结构中的数据元素除了同属于一个集合外，它们之间没有其他不三不四的关系= =）
K线性结构：线性结构中的数据元素之间是一对一的关系。◎ -◎ -◎-◎ - ◎
K树形结构：树形结构中的数据元素之间存在一种一对多的层次关系（像3.。。）
K图形结构：图形的数据元素是多对多的关系。

珍妮王小钰

◎★Jû    khuen  FJKLC6unhqtwxAop√∵ ←→ ←→

Once an item is added, it stays in that position relative to the other elements that came before and came after it. Collections such as these are often referred to as linear data structures.

Two ends : front/ top. — rear/ bottom/ right

top

base

A stack (sometimes called a “push-down stack”) is an ordered collection of items where the addition of new items and the removal of existing items always takes place at the same end. This end is commonly referred to as the “top.” The end opposite the top is known as the “base.”

The most recently added item is the one that is in position to be removed first. This ordering principle is sometimes called LIFO, last-in first-out. It provides an ordering based on length of time in the collection. Newer items are near the top, while older items are near the base.

base : old  not remove but first remove.  remove: reverse of put~~! example: web browser !

( an ordered collection of items where items are added to and removed from the end called the “top.” Stacks are ordered LIFO)

The only book whose cover is visible is the one on top. To access others in the stack, we need to remove the ones that are sitting on top of them

The order that they are removed is exactly the reverse of the order that they were placed

Table 1: Sample Stack Operations

Stack Operation

Stack Contents

Return Value

s.isEmpty()

[]

True

s.push(4)

[4]

s.push('dog')

[4,'dog']

s.peek()

[4,'dog']

'dog'

s.push(True)

[4,'dog',True]

s.size()

[4,'dog',True]

3

s.isEmpty()

[4,'dog',True]

False

s.push(8.4)

[4,'dog',True,8.4]

s.pop()

[4,'dog',True]

8.4

s.pop()

[4,'dog']

True

s.size()

[4,'dog']

2

Implementclass and list
ex: if we have the list [2,5,3,6,7,4], we need only to decide which end of the list will be considered the top of the stack and which will be the base. Once that decision is made, the operations can be implemented using the list methods such as append and pop.


that the end of the list will hold the top element of the stack
class Stack:
     def __init__(self):
         self.items = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)


二进制？？

??What is value of 25 expressed as an octal number?

What is value of 256 expressed as a hexidecimal number?
What is value of 26 expressed in base 26?


Queue(FIFO manner. FIFO, first-in first-out. It is also known as “first-come first-served.”

（only one way in and only one way out.）
If you are last in line, you must wait for all the other tasks to print ahead of you

• Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
• enqueue(item) adds a new item to the rear of the queue. It needs the item and returns nothing.
• dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
• isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the queue. It needs no parameters and returns an integer.
  
  

Table 1: Example Queue Operations

Queue Operation

Queue Contents

Return Value

q.isEmpty()

[]

True

q.enqueue(4)

[4]

q.enqueue('dog')

['dog',4]

q.enqueue(True)

[True,'dog',4]

q.size()

[True,'dog',4]

3

q.isEmpty()

[True,'dog',4]

False

q.enqueue(8.4)

[8.4,True,'dog',4]

q.dequeue()

[8.4,True,'dog']

4

q.dequeue()

[8.4,True]

'dog'

q.size()

[8.4,True]

2

class Queue:    def __init__(self):        self.items = []    def isEmpty(self):        return self.items == []    def enqueue(self, item):        self.items.insert(0,item)    def dequeue(self):        return self.items.pop()    def size(self):        return len(self.items)q = Queue()q.enqueue('hello')q.enqueue('dog')q.enqueue(3)q.dequeue()3，dog,hello ?right
Simulation: Hot PotatoSimulation: Printing Tasks¶



A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items.

• Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.
• addFront(item) adds a new item to the front of the deque. It needs the item and returns nothing.
• addRear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.
• removeFront() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.
• removeRear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.
• isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the deque. It needs no parameters and returns an integer.
  
  

    Table 1: Examples of Deque Operations¶

Deque Operation

Deque Contents

Return Value

d.isEmpty()

[]

True

d.addRear(4)

[4]

d.addRear('dog')

['dog',4,]

d.addFront('cat')

['dog',4,'cat']

d.addFront(True)

['dog',4,'cat',True]

d.size()

['dog',4,'cat',True]

4

d.isEmpty()

['dog',4,'cat',True]

False

d.addRear(8.4)

[8.4,'dog',4,'cat',True]

d.removeRear()

['dog',4,'cat',True]

8.4

d.removeFront()

['dog',4,'cat']

True

区别：

①ArrayList是可变长度的数组列表，也是一个泛型类，可以存放任意类型的对象。内部是有一个Object类型数组类存放对象。 它的所有方法都是默认在单一线程进行，因此不具有线程安全性。ArrayList只能在数组末尾添加数据，但更用于查询数据和修改数据。

②LinkedList是双向链表，所有操作默认都是双向链表的操作，因为它实现了deque接口和list接口 。它是使用结点<Node>来存放数据的，一个指向链表头的结点frist和另一个指向链表结尾的结点last。linkedList更便于在链表头或者链表尾插入数据和删除数据，但查询效率要低于ArrayList。

---------------------

版权声明：本文为CSDN博主「程序猿_阿海」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/hai1991yu/article/details/81162334

[size=12.600000381469727px]

[size=12.600000381469727px]

• OrderedList() creates a new ordered list that is empty. It needs no parameters and returns an empty list.
• add(item) adds a new item to the list making sure that the order is preserved. It needs the item and returns nothing. Assume the item is not already in the list.
• remove(item) removes the item from the list. It needs the item and modifies the list. Assume the item is present in the list.
• search(item) searches for the item in the list. It needs the item and returns a boolean value.
• isEmpty() tests to see whether the list is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the list. It needs no parameters and returns an integer.
• index(item) returns the position of item in the list. It needs the item and returns the index. Assume the item is in the list.
• pop() removes and returns the last item in the list. It needs nothing and returns an item. Assume the list has at least one item.
• pop(pos) removes and returns the item at position pos. It needs the position and returns the item. Assume the item is in the list.
  
  
  LinkedList 特点
  • 双向链表实现
  • 元素时有序的，输出顺序与输入顺序一致
  • 允许元素为 null
    
  
  
  • 要找到某个结点，必须从头开始遍历。（查询慢，增删快）
    
  • 和 ArrayList 一样，不是同步容器
    
  
  
  
  Programming Exercises
  • Modify the infix-to-postfix algorithm so that it can handle errors.
    InfixToPostfix

    rom Stack import Stack
    	from ParenChecker import parenChecker
    	def infixToPostfix(tokenList):
    	opStack = Stack()
    	prec = {"^": 4, "*": 3, "/": 3, "+": 2, "-": 2, "(": 1}
    	postfixList = []
    	# tokenList = list(infix.split(" "))
    	charTokens = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    	numTokens = "1234567890"
    	print ("token list: ", tokenList)
    	for token in tokenList:
    	if token in charTokens or token in numTokens or token.isdigit():
    	postfixList.append(token)
    	elif token == "(":
    	opStack.push(token)
    	elif token == ")":
    	topToken = opStack.pop()
    	while topToken != "(":
    	postfixList.append(topToken)
    	topToken = opStack.pop()
    	else:
    	while (not opStack.is_empty()) and \
    	(prec[opStack.peek()] >= prec[token]):
    	postfixList.append(opStack.pop())
    	opStack.push(token)
    	while not opStack.is_empty():
    	postfixList.append(opStack.pop())
    	return ' '.join(postfixList)
    	def validateInput(expr):
    	if not expr:
    	return False
    	expr = expr.strip()
    	parenList = []
    	for e in expr:
    	if e == '(' or e == ')':
    	parenList.append(e)
    	parenExpr = ''.join(parenList)
    	if not parenChecker(parenExpr):
    	return False
    	tokenList = expr.split(" ")
    	sanitizedTokList = []
    	for t in tokenList:
    	t = t.strip()
    	sanitizedTokList.append(t)
    	if t.isdigit():
    	continue
    	elif t == '+' or t == '-' or t == '/' or t == '*' or t == '^':
    	continue
    	elif t == '(' or t == ')':
    	continue
    	else:
    	return False
    	return sanitizedTokList
    	def readInput():
    	print ("Enter infix expression with space.")
    	infix = input("infix expression: ")
    	tokList = validateInput(infix)
    	while not tokList:
    	print ("Bad Input! Please enter valid infix expression")
    	print ("Enter infix expression with space.")
    	infix = input("infix expression: ")
    	return tokList
    	def main():
    	infix = readInput()
    	postfix = infixToPostfix(infix)
    	print ("ostfix expression: ", postfix)
    	if __name__ == '__main__':
    	main()

  • Modify the postfix evaluation algorithm so that it can handle errors.
    PostfixEval

    from Stack import Stack
    	def postfixEvaluator(pfix):
    	pfixList = pfix.split(" ")
    	opStack = Stack()
    	for tok in pfixList:
    	if tok.isdigit():
    	opStack.push(int(tok))
    	else:
    	if opStack.size() < 2:
    	print ("Invalid postfix expression")
    	return None
    	second = opStack.pop()
    	first = opStack.pop()
    	ans = doMath(tok, first, second)
    	if ans is None:
    	return ans
    	opStack.push(ans)
    	return opStack.pop()
    	def doMath(operator, x, y):
    	if operator == '*':
    	return (x * y)
    	elif operator == "+":
    	return (x + y)
    	elif operator == '-':
    	return (x - y)
    	elif operator == "/":
    	if y == 0:
    	return None
    	return (float(x)/y)
    	elif operator == '^':
    	if x == 0:
    	return None
    	elif y == 0:
    	return 1
    	else:
    	return x ** y
    	return None
    	def readInput():
    	print ("Enter postfix expression separated by space.")
    	pfix = input("Expression: ")
    	return pfix
    	def main():
    	postfix = readInput()
    	result = postfixEvaluator(postfix)
    	print("Result: ", result)
    	if __name__ == '__main__':
    	main()

  • Implement a direct infix evaluator that combines the functionality of infix-to-postfix conversion and the postfix evaluation algorithm. Your evaluator should process infix tokens from left to right and use two stacks, one for operators and one for operands, to perform the evaluation.
    Please refer to InfixCalc.py for implementation and InfixCalc_inout.txt for sample input/output.

    from InfixToPostfix import infixToPostfix
    	from InfixToPostfix import readInput
    	from PostfixEval import postfixEvaluator
    	def infixCalc(infixExpr):
    	postfix = infixToPostfix(infixExpr)
    	print ("ostfix: ", postfix)
    	ans = postfixEvaluator(postfix)
    	return ans
    	def main():
    	infixExpr = readInput()
    	ans = infixCalc(infixExpr)
    	print ("Result: ", ans)
    	if __name__ == '__main__':
    	main()

    Enter infix expression with space.
    	infix expression: ( 2 + 3 ) ^ ( 1 + 4 )
    	token list:  ['(', '2', '+', '3', ')', '^', '(', '1', '+', '4', ')']
    	Postfix:  2 3 + 1 4 + ^
    	Result:  3125
    	===========================================================================
    	Enter infix expression with space.
    	infix expression: ( 2 + 4 ) * 3
    	token list:  ['(', '2', '+', '4', ')', '*', '3']
    	Postfix:  2 4 + 3 *
    	Result:  18

  • Turn your direct infix evaluator from the previous problem into a calculator.
    Please refer to Calculator.py, Tokenizer.py and Calculator_inout.py for implementation, and sample input/output.

    from Tokenizer import tokenizer
    	from Tokenizer import readInput
    	from ParenChecker import parenChecker
    	from InfixToPostfix import infixToPostfix
    	from PostfixEval import postfixEvaluator
    	def calculator():
    	while True:
    	expr = readInput()
    	tokens = tokenizer(expr)
    	parens = []
    	for t in tokens:
    	if t == '(' or t == ')':
    	parens.append(t)
    	if not parenChecker(''.join(parens)):
    	print ("arenthesis mismatch. Please try again..")
    	continue
    	if (tokens is not None) or (len(tokens) >= 1):
    	postfix = infixToPostfix(tokens)
    	print ("postfix: ", postfix)
    	result = postfixEvaluator(postfix)
    	print ("ANS: ", result)
    	print ("press any key to continue, \'n\' to exit.")
    	ch = input()
    	if ch == 'n':
    	break
    	def main():
    	calculator()
    	if __name__ == '__main__':
    	main()

    def tokenizer(expr):
    	if expr is None:
    	return None
    	expr = expr.strip()
    	tokenList = []
    	accum = []
    	for t in expr:
    	if t.isdigit():
    	accum.append(t)
    	continue
    	elif len(accum) > 0:
    	tokenList.append(''.join(accum))
    	accum = []
    	if t == '+' or t == '-' or t == '/' or t == '*' or t == '^':
    	tokenList.append(t)
    	elif t == '(' or t == ')':
    	tokenList.append(t)
    	if len(accum) > 0:
    	tokenList.append(''.join(accum))
    	return tokenList
    	def readInput():
    	print ("Enter expression for calculator: ")
    	expr = input()
    	return expr
    	def main():
    	expr = readInput()
    	tknList = tokenizer(expr)
    	print ("TokenList: ", tknList)
    	if __name__ == '__main__':
    	main()

    Enter expression for calculator:
    	2+3
    	token list:  ['2', '+', '3']
    	postfix:  2 3 +
    	ANS:  5
    	press any key to continue, 'n' to exit.
    	a
    	Enter expression for calculator:
    	6+7*2
    	token list:  ['6', '+', '7', '*', '2']
    	postfix:  6 7 2 * +
    	ANS:  20
    	press any key to continue, 'n' to exit.
    	a
    	Enter expression for calculator:
    	(1+4)^(2+3)
    	token list:  ['(', '1', '+', '4', ')', '^', '(', '2', '+', '3', ')']
    	postfix:  1 4 + 2 3 + ^
    	ANS:  3125
    	press any key to continue, 'n' to exit.
    	a
    	Enter expression for calculator:
    	((2+3)*(1+4))
    	token list:  ['(', '(', '2', '+', '3', ')', '*', '(', '1', '+', '4', ')', ')']
    	postfix:  2 3 + 1 4 + *
    	ANS:  25
    	press any key to continue, 'n' to exit.
    	Enter expression for calculator:
    	token list:  []
    	postfix:
    	Invalid postfix expression
    	ANS:  None
    	press any key to continue, 'n' to exit.

    
    
    
    
    
    
    
    
    
  • Implement the Queue ADT, using a list such that the rear of the queue is at the end of the list.
    Refer to QueueADT.py and QueueADTClient.py for implementation and sample input/output 过

    # Implementation of Queue ADT
    	class Queue:
    	def __init__(self):
    	self.items = []
    	def is_empty(self):
    	return self.items == []
    	def enqueue(self, value):
    	self.items.append(value)
    	def dequeue(self):
    	return self.items.pop(0)
    	def size(self):
    	return len(self.items)

    Client for testing QueueADT？？ ?️是时间？

    from QueueADT import Queue
    	import datetime as dt
    	import time
    	def testQueueADT():
    	Q = Queue()
    	times = []
    	NUMS = [1000, 10000, 100000, 1000000]
    	for N in NUMS:
    	Q = Queue()
    	start = dt.datetime.now()
    	for i in range(N):
    	Q.enqueue(i)
    	end = dt.datetime.now()
    	elapsed = ((end - start).microseconds*1000)/N
    	print ("Enqueue for %d items: %d" % (1000, elapsed))
    	print ("==================================================")
    	times = []
    	for N in NUMS:
    	Q = Queue()
    	for i in range(N):
    	Q.enqueue(i)
    	start = dt.datetime.now()
    	for i in range(N):
    	Q.dequeue()
    	end = dt.datetime.now()
    	elapsed = ((end - start).microseconds*1000)/N
    	print ("Dequeue for %d items: %d" % (1000, elapsed))
    	def main():
    	testQueueADT()
    	if __name__ == '__main__':
    	main()

    Enqueue for 1000 items: 570
    	Enqueue for 1000 items: 543
    	Enqueue for 1000 items: 558
    	Enqueue for 1000 items: 551
    	==================================================
    	Dequeue for 1000 items: 970
    	Dequeue for 1000 items: 3880
    	Dequeue for 1000 items: 3726
    	Dequeue for 1000 items: 82

  • Design and implement an experiment to do benchmark comparisons of the two queue implementations. What can you learn from such an experiment?
    Refer to QueueADTClient.py and QueueADTClient_inout.txt. we learn that with List implementation one of the enqueue/dequeue operation would be O(n) and if we need both enqueue/dequeue operation be O(1) then we need to resort to linked list implementation of Queue.

    from QueueADT import Queue
    	import datetime as dt
    	import time
    	def testQueueADT():
    	Q = Queue()
    	times = []
    	NUMS = [1000, 10000, 100000, 1000000]
    	for N in NUMS:
    	Q = Queue()
    	start = dt.datetime.now()
    	for i in range(N):
    	Q.enqueue(i)
    	end = dt.datetime.now()
    	elapsed = ((end - start).microseconds*1000)/N
    	print ("Enqueue for %d items: %d" % (1000, elapsed))
    	print ("==================================================")
    	times = []
    	for N in NUMS:
    	Q = Queue()
    	for i in range(N):
    	Q.enqueue(i)
    	start = dt.datetime.now()
    	for i in range(N):
    	Q.dequeue()
    	end = dt.datetime.now()
    	elapsed = ((end - start).microseconds*1000)/N
    	print ("Dequeue for %d items: %d" % (1000, elapsed))
    	def main():
    	testQueueADT()
    	if __name__ == '__main__':
    	main()

    
    Enqueue for 1000 items: 570
    
    Enqueue for 1000 items: 543
    
    
    Enqueue for 1000 items: 558
    
    
    Enqueue for 1000 items: 551
    
    
    ==================================================
    
    
    Dequeue for 1000 items: 970
    
    
    Dequeue for 1000 items: 3880
    
    
    Dequeue for 1000 items: 3726
    
    
    Dequeue for 1000 items: 82
    
    
  • It is possible to implement a queue such that both enqueue and dequeue have <span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="O(1)" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">?(1)O(1) performance on average. In this case it means that most of the time enqueue and dequeue will be <span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="O(1)" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">?(1)O(1) except in one particular circumstance where dequeue will be <span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="O(n)" role="presentation" style="box-sizing: border-box; display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">?(?)O(n).
    Please refer to QueueLinkedList.py and QueueLinkedListClient.py for the linked list implementation of Queue. Here both enqueue and dequeue operations are O(1) 没有循环    ？～

    from QNode import Node
    	class Queue:
    	def __init__(self):
    	self.front = None
    	self.back = None
    	self.N = 0
    	def enqueue(self, data):
    	temp = Node(data)
    	if self.front is None:
    	self.front = temp
    	self.back = self.front
    	else:
    	self.back.setNext(temp)
    	self.back = self.back.getNext()
    	self.N += 1
    	def dequeue(self):
    	if self.isEmpty():
    	print ("Queue is EMPTY!")
    	return None
    	temp = self.front
    	if self.front.getNext() is None:
    	self.front = None
    	self.back = None
    	else:
    	self.front = self.front.getNext()
    	self.N -= 1
    	return temp
    	def qprint(self):
    	if not self.isEmpty():
    	node = self.front
    	while not node is None:
    	print (node.data, end=" -> ")
    	node = node.getNext()
    	print("null")
    	else:
    	print ("Queue is EMPTY!")
    	def isEmpty(self):
    	return self.N == 0
    	def size(self):
    	return self.N

    from QueueLinkedList import Queue
    	def testQueueLinkedList():
    	Q = Queue()
    	while True:
    	print ("Choose operation: ")
    	print (" 1 - Enqueue\n",
    	"2 - Dequeue\n",
    	"3 - Size\n",
    	"4 - Exit\n")
    	choice = input()
    	if choice == '1':
    	Q = enqueue(Q)
    	elif choice == '2':
    	Q = dequeue(Q)
    	elif choice == '3':
    	getSize(Q)
    	elif choice == '4':
    	break
    	else:
    	print ("BAD Choice! Choose from 1 to 4 numbers")
    	def dequeue(Q):
    	if not Q.isEmpty():
    	node = Q.dequeue()
    	print ("Dequeued: ", node.data)
    	Q.qprint()
    	else:
    	print ("Queue is EMPTY!")
    	return Q
    	def getSize(Q):
    	size = Q.size()
    	print ("Size of Queue: ", size)
    	def enqueue(Q):
    	data = input("Data to be enqueued: ")
    	if (data is not None) or len(data) > 0:
    	Q.enqueue(data)
    	Q.qprint()
    	else:
    	print ("Bad data. Plz try again..")
    	return Q
    	def main():
    	testQueueLinkedList()
    	if __name__ == '__main__':
    	main()

  • Consider a real life situation. Formulate a question and then design a simulation that can help to answer it. Possible situations include:
    • Cars lined up at a car wash
    • Customers at a grocery store check-out
    • Airplanes taking off and landing on a runway
    • A bank teller
      
      
    Be sure to state any assumptions that you make and provide any probabilistic data that must be considered as part of the scenario.
  • Modify the Hot Potato simulation to allow for a randomly chosen counting value so that each pass is not predictable from the previous one.（Hot potato game with randomness）
    Please refer to HotPotatoRand.py for implementation and HotPotatoRand_inout.txt for input/output examples

    from Queue import Queue
    	def hotPotato(players, num):
    	simQ = Queue()
    	for p in players:
    	simQ.enqueue(p)
    	while simQ.size() > 1:
    	for i in range(num):
    	simQ.enqueue(simQ.dequeue())？？？
    	simQ.dequeue()
    	return simQ.dequeue()
    	def readInput():
    	print ("Enter player names, comma separated")
    	names = input()
    	while True:
    	num = input("Enter count: ")
    	if num.isdigit():
    	num = int(num)
    	break
    	else:
    	print ("Bad Input. Please try again.")
    	name_list = names.split(",")
    	name_list = [n.strip() for n in name_list]
    	return (name_list, num)
    	def main():
    	players, num = readInput()
    	winner = hotPotato(players, num)
    	print ("Winner is: ", winner)
    	if __name__ == '__main__':
    	main()

    随机：

  • from Queue import Queue
    	import random
    	def hotPotato(players):
    	if players is None or len(players) <= 1:
    	return players
    	simQ = Queue()
    	plsize = len(players)。。。。。。
    	for p in players:
    	simQ.enqueue(p)
    	while simQ.size() > 1:
    	r = random.randint(plsize, plsize*2)。。？2。。
    	for i in range(r):
    	simQ.enqueue(simQ.dequeue())
    	simQ.dequeue()
    	return simQ.dequeue()
    	def readInput():
    	print ("Enter player names, comma separated")
    	names = input()
    	#    while True:
    	#        num = input("Enter count: ")
    	#        if num.isdigit():
    	#            num = int(num)
    	#            break
    	#        else:
    	#            print ("Bad Input. Please try again.")
    	name_list = names.split(",")
    	name_list = [n.strip() for n in name_list]
    	return (name_list)
    	def main():
    	players = readInput()
    	winner = hotPotato(players)
    	print ("Winner is: ", winner)
    	if __name__ == '__main__':
    	main()

  • Implement a radix sorting machine. A radix sort for base 10 integers is a mechanical sorting technique that utilizes a collection of bins, one main bin and 10 digit bins. Each bin acts like a queue and maintains its values in the order that they arrive. The algorithm begins by placing each number in the main bin. Then it considers each value digit by digit. The first value is removed and placed in a digit bin corresponding to the digit being considered. For example, if the ones digit is being considered, 534 is placed in digit bin 4 and 667 is placed in digit bin 7. Once all the values are placed in the corresponding digit bins, the values are collected from bin 0 to bin 9 and placed back in the main bin. The process continues with the tens digit, the hundreds, and so on. After the last digit is processed, the main bin contains the values in order.
    Refer to RadixSort.py for implementation and RadixSort_inout.txt for sample input/output.
  • Another example of the parentheses matching problem comes from hypertext markup language (HTML). In HTML, tags exist in both opening and closing forms and must be balanced to properly describe a web document. This very simple HTML document:
    <html>   <head>      <title>         Example      </title>   </head>   <body>      <h1>Hello, world</h1>   </body></html>
    
    
    is intended only to show the matching and nesting structure for tags in the language. Write a program that can check an HTML document for proper opening and closing tags.
    Please refer to HTMLTagValidator.py for implementation and HTMLTagValidator_inout.txt for sample input/output.

    from Stack import Stack
    	def validateHTMLTags(htmlStr):
    	stack = Stack()
    	hsize = len(htmlStr)
    	i = 0
    	while i < hsize:
    	tag = []
    	openTag = True
    	if htmlStr == '<':
    	tag.append('<')
    	i += 1
    	if htmlStr == '/':
    	openTag = False
    	i += 1
    	while (i < hsize) and htmlStr == ' ':
    	i += 1
    	while (i < hsize) and (htmlStr.isalpha() or htmlStr.isdigit()):
    	tag.append(htmlStr)
    	i += 1
    	while (i < hsize) and htmlStr != '>':
    	i += 1
    	if (i >= hsize):
    	return False
    	tag.append(htmlStr)
    	htmTag = ''.join(tag)
    	# print ("tag: ", htmTag)
    	if openTag:
    	stack.push(htmTag)
    	elif stack.is_empty():
    	return False
    	else:
    	topTag = stack.pop()
    	# print("popped: ", topTag)
    	# print("htmTag: ", htmTag)
    	if topTag != htmTag:
    	return False
    	i += 1
    	if not stack.is_empty():
    	return False
    	return True
    	def readinput():
    	print ("Enter html string: ")
    	htmlStr = input()
    	return htmlStr
    	def main():
    	html = readinput()
    	isValid = validateHTMLTags(html)
    	print("Input HTML String Valid? ", isValid)
    	if __name__ == '__main__':
    	main()

  • Extend the program from Listing 2.15 to handle palindromes with spaces. For example, I PREFER PI is a palindrome that reads the same forward and backward if you ignore the blank characters.
  • To implement the length method, we counted the number of nodes in the list. An alternative strategy would be to store the number of nodes in the list as an additional piece of data in the head of the list. Modify the UnorderedList class to include this information and rewrite the lengthmethod.
    Please refer to LinkedList.py for unordered link list implementation and LinkedListClient.py for testing the main class LinkedList.py
  • Implement the remove method so that it works correctly in the case where the item is not in the list.
    refer to remove method in LinkedList.py and LinkedListClient.py testing methods.
  • Modify the list classes to allow duplicates. Which methods will be impacted by this change?
    ？？
  • Implement the __str__ method in the UnorderedList class. What would be a good string representation for a list?
    ？
  • Implement __str__ method so that lists are displayed the Python way (with square brackets).
    LinkedList.py has 'str' method which represents(prints) the LinkedList like python lists and LinkedList.py allows for duplicates nodes as well - remove method deletes the first first occurance of the data from head if found.
  • Implement the remaining operations defined in the UnorderedList ADT (append, index, pop, insert).
    Refer to SLList.py for implementation of append, index, pop and insert. Test client code is written in SLListClient.py
  • Implement a slice method for the UnorderedList class. It should take two parameters, startand stop, and return a copy of the list starting at the start position and going up to but not including the stop position.
    Please refer the slice(start, stop) method in SLList.py - testing method has been added in SLListClient.py
  • Implement the remaining operations defined in the OrderedList ADT.
    Please refer to OrderedList.py for operations implementation and OrderedListClient.py for testing OrderedList.py class
  • Consider the relationship between Unordered and Ordered lists. Is it possible that inheritance could be used to build a more efficient implementation? Implement this inheritance hierarchy.
    ？
  • Implement a stack using linked lists.
    Please refer to StackLinkedList.py for implementation and StackLinkedListClient.py for test client code.

    class Node:
    	def __init__(self, data):
    	self.data = data
    	self.next = None？？
    	class Stack:
    	def __init__(self):
    	self.head = None？？
    	self.N = 0？？？
    	def __str__(self):
    	dataList = []
    	curr = self.head
    	while curr is not None:
    	dataList.append(curr.data)
    	curr = curr.next
    	print (dataList)
    	def pop(self):
    	if self.isEmpty():
    	print ("Stack is EMPTY!")
    	return None
    	node = self.head。。。。
    	self.head = self.head.next
    	node.next = None。。。。。
    	self.N -= 1
    	return node
    	def push(self, data):
    	node = Node(data)
    	node.next = self.head
    	self.head = node
    	self.N += 1
    	def isEmpty(self):
    	return self.N == 0
    	def size(self):
    	return self.N

    from StackLinkedList import Stack
    	def testStackAPIs():
    	stack = Stack()
    	while True:
    	print ("Choose Operation\n",
    	"1 - Push(data)\n",
    	"2 - Pop()\n",
    	"3 - Size()\n",
    	"4 - Exit()")
    	choice = input("Choice: ")
    	if choice == '1':
    	stack = pushStack(stack)
    	stack.__str__()
    	elif choice == '2':
    	stack = popStack(stack)
    	stack.__str__()
    	elif choice == '3':
    	stackSize(stack)
    	stack.__str__()
    	elif choice == '4':
    	break
    	else:
    	print ("Bad Choice. Please choose a valid operation")
    	continue
    	def stackSize(stack):
    	size = stack.size()
    	print("Stack Size: ", size)
    	def pushStack(stack):
    	data = input("Enter data: ")
    	stack.push(data)
    	return stack
    	def popStack(stack):
    	node = stack.pop()
    	if node is not None:
    	print ("opped: ", node.data)
    	else:
    	print ("opped: ", node)
    	return stack
    	def main():
    	testStackAPIs()
    	if __name__ == '__main__':
    	main()

  • Implement a queue using linked lists.
    Please refer to QueueLinkedList.py for implementation and QueueLinkedListClient.py for test client code.

    from QNode import Node
    	class Queue:
    	def __init__(self):
    	self.front = None
    	self.back = None
    	self.N = 0
    	def enqueue(self, data):
    	temp = Node(data)
    	if self.front is None:
    	self.front = temp
    	self.back = self.front
    	else:
    	self.back.setNext(temp)
    	self.back = self.back.getNext()
    	self.N += 1
    	def dequeue(self):
    	if self.isEmpty():
    	print ("Queue is EMPTY!")
    	return None
    	temp = self.front
    	if self.front.getNext() is None:
    	self.front = None
    	self.back = None
    	else:
    	self.front = self.front.getNext()
    	self.N -= 1
    	return temp
    	def qprint(self):
    	if not self.isEmpty():
    	node = self.front
    	while not node is None:
    	print (node.data, end=" -> ")
    	node = node.getNext()
    	print("null")
    	else:
    	print ("Queue is EMPTY!")
    	def isEmpty(self):
    	return self.N == 0
    	def size(self):
    	return self.N

    from QueueLinkedList import Queue
    	def testQueueLinkedList():
    	Q = Queue()
    	while True:
    	print ("Choose operation: ")
    	print (" 1 - Enqueue\n",
    	"2 - Dequeue\n",
    	"3 - Size\n",
    	"4 - Exit\n")
    	choice = input()
    	if choice == '1':
    	Q = enqueue(Q)
    	elif choice == '2':
    	Q = dequeue(Q)
    	elif choice == '3':
    	getSize(Q)
    	elif choice == '4':
    	break
    	else:
    	print ("BAD Choice! Choose from 1 to 4 numbers")
    	def dequeue(Q):
    	if not Q.isEmpty():
    	node = Q.dequeue()
    	print ("Dequeued: ", node.data)
    	Q.qprint()
    	else:
    	print ("Queue is EMPTY!")
    	return Q
    	def getSize(Q):
    	size = Q.size()
    	print ("Size of Queue: ", size)
    	def enqueue(Q):
    	data = input("Data to be enqueued: ")
    	if (data is not None) or len(data) > 0:
    	Q.enqueue(data)
    	Q.qprint()
    	else:
    	print ("Bad data. Plz try again..")
    	return Q
    	def main():
    	testQueueLinkedList()
    	if __name__ == '__main__':
    	main()

  • Implement a deque using linked lists.
    Please refer to DequeLinkedList.py for Deque implementation and DequeLinkedListClient.py for client test code
    
    

    class Node:
    	def __init__(self, data):
    	self.data = data
    	self.next = None
    	class Deque:
    	def __init__(self):
    	self.head = None
    	self.tail = None
    	self.N = 0
    	def __str__(self):
    	plist = []
    	curr = self.head
    	while curr is not None:
    	plist.append(curr.data)
    	curr = curr.next
    	print (plist)
    	def addFront(self, data):
    	node = Node(data)
    	node.next = self.head
    	self.head = node
    	if self.tail is None:
    	self.tail = self.head
    	self.N += 1
    	def removeFront(self):
    	if self.isEmpty():
    	print ("Deque is Empty!")
    	return None
    	node = self.head
    	self.head = self.head.next
    	node.next = None
    	if self.head is None:
    	self.tail = None
    	self.N -= 1
    	return node
    	def addRear(self, data):
    	node = Node(data)
    	if self.isEmpty():
    	self.tail = node
    	self.head = self.tail
    	else:
    	self.tail.next = node
    	self.tail = self.tail.next
    	self.N += 1
    	def removeRear(self):
    	if self.isEmpty():
    	print ("Deque is Empty!")
    	return None
    	# check if size is 1
    	if self.size() == 1:
    	node = self.tail
    	self.tail = None
    	self.head = None
    	self.N -= 1
    	return node
    	curr = self.head
    	while curr.next.next is not None:
    	curr = curr.next
    	node = curr.next
    	self.tail = curr
    	self.tail.next = None
    	self.N -= 1
    	return node
    	def isEmpty(self):
    	return self.N == 0
    	def size(self):
    	return self.N

    test

  • from DequeLinkedList import Deque
    	def testDeque():
    	dq = Deque()
    	while True:
    	print ("Choose Operation\n",
    	"1 - AddFront(data)\n",
    	"2 - RemoveFront()\n",
    	"3 - AddRear(data)\n",
    	"4 - RemoveRear()\n",
    	"5 - Size()\n",
    	"6 - Exit()")
    	choice = input("Enter choice: ")
    	if choice == '1':
    	dq = addFront(dq)
    	dq.__str__()
    	elif choice == '2':
    	dq = removeFront(dq)
    	dq.__str__()
    	elif choice == '3':
    	dq = addRear(dq)
    	dq.__str__()
    	elif choice == '4':
    	dq = removeRear(dq)
    	dq.__str__()
    	elif choice == '5':
    	dequeSize(dq)
    	dq.__str__()
    	elif choice == '6':
    	break
    	else:
    	print ("Bad Choice - please choose valid operation")
    	continue
    	def dequeSize(deque):
    	print ("Deque Size: ", deque.size())
    	def removeRear(deque):
    	node = deque.removeRear()
    	if node:
    	print ("Removed: ", node.data)
    	else:
    	print ("Removed: ", node)
    	return deque
    	def addRear(deque):
    	data = input("Enter data: ")
    	deque.addRear(data)
    	return deque
    	def removeFront(deque):
    	node = deque.removeFront()
    	if node is not None:
    	print ("Removed: ", node.data)
    	else:
    	print ("Removed: ", node)
    	return deque
    	def addFront(deque):
    	data = input("Enter data: ")
    	deque.addFront(data)
    	return deque
    	def main():
    	testDeque()
    	if __name__ == '__main__':
    	main()

    
    
    
    
    
    
    
    
    
  • Design and implement an experiment that will compare the performance of a Python list with a list implemented as a linked list.
    Approach: List in python has array implementation - what this means is elements of list are stored in contiguous memory locations. So operations like index(), search()(binary search - if data is sorted), sort() can be really efficient. Cons here is when the list is full and we need to add more data to it, python has to copy the old list to a bigger contiguous space, similarly when we have removed a lot of elements from the list we need to resize() it to smaller size - this again requires copy to smaller contiguous memory locations. Experimentation is left as an exercise to user
  • Design and implement an experiment that will compare the performance of the Python list based stack and queue with the linked list implementation.
    In Contrast Linked List implementation works really well when we need to add elements as we never have to copy the whole list (unlike List in python), or when we need to remove lot of elements from the linked list - This implementation ensures optimal usage of memory. Though there are associated overheads of maintaining pointers. Indexing and Search (BinarySearch) can be challenging and deteriorate performance when implemented in linked list. Experimentation is left as an exercise
  • The linked list implementation given above is called a singly linked list because each node has a single reference to the next node in sequence. An alternative implementation is known as a doubly linked list. In this implementation, each node has a reference to the next node (commonly called next) as well as a reference to the preceding node (commonly called back). The head reference also contains two references, one to the first node in the linked list and one to the last. Code this implementation in Python.
    Please refer to DoublyLinkedList.py file for implementation and APIs and DoublyLinkedListClient.py for client test code.
  • Create an implementation of a queue that would have an average performance of O(1) for enqueue and dequeue operations.
    
    QueueLinkedList.py has implementation with front and back pointers which keep track of the head and tail of the queue - this helps in implementing Enqueu and Dequeue operations in O(1). Please refer to QueueLinkedListClient.py for client test code.

    from QueueLinkedList import Queue
    	def testQueueLinkedList():
    	Q = Queue()
    	while True:
    	print ("Choose operation: ")
    	print (" 1 - Enqueue\n",
    	"2 - Dequeue\n",
    	"3 - Size\n",
    	"4 - Exit\n")
    	choice = input()
    	if choice == '1':
    	Q = enqueue(Q)
    	elif choice == '2':
    	Q = dequeue(Q)
    	elif choice == '3':
    	getSize(Q)
    	elif choice == '4':
    	break
    	else:
    	print ("BAD Choice! Choose from 1 to 4 numbers")
    	def dequeue(Q):
    	if not Q.isEmpty():
    	node = Q.dequeue()
    	print ("Dequeued: ", node.data)
    	Q.qprint()
    	else:
    	print ("Queue is EMPTY!")
    	return Q
    	def getSize(Q):
    	size = Q.size()
    	print ("Size of Queue: ", size)
    	def enqueue(Q):
    	data = input("Data to be enqueued: ")
    	if (data is not None) or len(data) > 0:
    	Q.enqueue(data)
    	Q.qprint()
    	else:
    	print ("Bad data. Plz try again..")
    	return Q
    	def main():
    	testQueueLinkedList()
    	if __name__ == '__main__':
    	main()