北航数据结构笔记系列二

10.13 BUAA ASE数据结构课程

1.斐波那契数列

• #字典1.0
  fibdic={'1':1,'2':1}
  sum2=0
  def fun2(n):
  	global sum2
  	global fibdic
  	if fibdic.get(str(n))!=None:
  		sum2+=1
  		return fibdic[str(n)]
  	else:
  		sum2+=1
  		fibdic[str(n)]=fun2(n-1)+fun2(n-2)
  		return fibdic[str(n)]
  print(fun2(25),sum2)
  
  #字典2.0
  sum4=0
  def fun4(n,d):
  	global sum4
  	if n in d:
  		sum4+=1
  		return d[n]
  	else:
  		sum4+=1
  		ans=fun4(n-1,d)+fun4(n-2,d)
  		d[n]=ans
  		return ans
  d={0:1,1:1}
  print(fun4(24,d),sum4)
  

• #iaPal,回文串
  def isPal(s):
  	if len(s)<=1:
  		return True
  	else:
  		if s[0]==s[-1]:
  			return isPal(s[1:-1])
  		else:
  			return False
  s=input()
  print(isPal(s))
  

2.集合的操作

3.模块

4.文件

• #读取绝对路径
  f=open('D:/常用文件/学习/编程/pycharm/test.txt','r')
  f=open('D:\\常用文件\\学习\\编程\\pycharm\\test.txt','r')
  f=open(r'D:\常用文件\学习\编程\pycharm\test.txt','r')
  f.close()
  

• f=open('test.txt','r')
  string1=f.read()
  print('string1:',string1)
  
  f=open('test.txt','r')
  string2=f.readline()
  print('string2:',string2)
  
  f=open('test.txt','r')
  string3=f.readlines()
  print('string3:',string3)
  
  f.close()
  
  f=open('test.txt','a')
  f.write('java or python\n')
  f.close()
  

5.程序的构成&数据结构

1.抽象

2.类

类属性、类方法、类的实现

class:类

object:对象

def:定义方法

#类的创建(分数)
from math import *
class Fraction:   
    def __init__(self,top,bottom):
        self.num = top
        self.den = bottom
    def __str__(self):  #重载方法
        return str(self.num)+'/'+str(self.den)
    def __add__(self, other):
        # return str(self.num*other.den+self.den*other.num)+'/'+str(self.den*other.den)
        newnum=self.num*other.den+self.den*other.num
        newden=self.den*other.den
        g=gcd(newnum,newden)
        newden//=g
        newnum//=g
        return Fraction(newnum,newden)
    def show(self): #定义方法
        print(str(self.num)+'/'+str(self.den))


myfraction = Fraction(4,5)
f1=Fraction(1,3)
f2=Fraction(1,3)
print('-----------------1.打印输出-----------------------------------')
print(myfraction)
myfraction.show()
print()
print('1--', myfraction)
print('------------------2.分数加----------------------------------------------')
print(f1+f2)

3.栈

• Stack(),栈的实例化

• push(item),压栈（元素入栈）

• s
  

4.栈的实例----十进制转二进制（任意进制）

5.队列

• 作业：队列模拟循环链表