526互联

python数据结构上课笔记

发布时间 2023-10-02 20:32:02作者: MrFlySand-飞沙

流程控制

  1. 顺序结构：代码的编译顺序，从上往下一行一行编译。
  2. 代码的执行顺序：从主函数开始，到主函数结束

编译

文本文件--->预处理--->编译--->汇编--->链接

预处理：对所有#字开头的内容展开处理 同时忽略注释文件gcc text.c -o text.i -E

编译： 将展开的文件处理成相应的汇编代码gcc text.i -o text.s -S

汇编：将汇编代码生成.o文件gcc text.s -o text.o -c

链接：链接函数库 执行代码gcc text.o -o text 生成了执行文件text

选择结构

  1. 单分支结构 判断语句为真 执行我们的执行语句
if 判断语句 :
    执行语句
实例
money=1000;
s=int(input('输入取款金额'));
if money>s :
        money-=s;
        print("取款成功余额为:",money);
  1. 双分支结构 判断语句为真 执行我们的执行语句1 为假 执行我们的执行语句2
  if 判断语句 :
      执行语句1
  else：
      执行语句2
实例
  money=1000;
  s=int(input('输入取款金额'));
  if money>s :
          money-=s;
          print("取款成功余额为:",money);
  else :
          print("余额不足");
  1. 多分支结构
if 判断语句1 :
      执行语句1
  elif 判断语句2: 
      执行语句2
  elif 判断语句3: 
      执行语句3
  ........
  else：
      执行语句4

  输入一个学生成绩；
      <60  对不起你没有及格
      <80  哎呦 不错哦 你及格了
      <90  你真不错 
      <100 你简直太棒了 
      ==100 不可能 绝对不可能
      else 

s=int(input('请输入学生成绩'));
  if s<60 :
          print("不好意思你没有及格");
  elif s<80 :
          print("哎呦不错哦，你已经及格了");
  elif s<90 :
          print("你真是太优秀了");
  elif s<100 :
          print("简直很完美");
  elif s==100 :
          print("不可能 绝对不可能");       
  else :
          print("输入错误");
  1. 嵌套分支：
if 
    if
        语句1
    else 
        语句2
else	
    if
        语句3
    else 
        语句4

x=int(input('请输入x'));
y=int(input('请输入y'));

if x>0 : 
        if y>0:
                print("该点在第一象限")
        else:
                print("该点在第四象限")
else:
        if y>0:
                print("该点在第二象限")
        else:
                print("该点在第三象限")

5.条件表达式 条件为真 执行if前面的语句 条件为假 执行else后面的语句

x=int(input('请输入x'));
      y=int(input('请输入y'));  
  print(x,"大于",y)  if x>y else print(x,'小于',y);

循环结构

循环结构：重复做一样的事情。
什么时候开始 到什么时候结束 怎么变化 做什么

  1. while 条件表达式 ：
    循环体

条件为真 就执行循环体。条件为假就结束循环

求1-100的和
num=1
add=0  #累加器
while num<101:
        add+=num
        num+=1;
print(add);

求阶乘 3！=1*2*3
    k=int(input("请输入一个数"))
    num=1
    add=0  #累加器
    mul=1 #累乘器
    while num<=k:
            mul*=num
            num+=1;

    print(mul);

求阶乘和
1！=1
2！=1!*2
3！=2!*3
k=int(input("请输入一个数"))
num=1
add=0  #累加器
mul=1 #累乘器
while num<=k:
        mul*=num
        add+=mul
        num+=1;

print(add);

输入一个数  逆序输出
67354  6735   673     67       6
m=4		m=45  m=453   m=4537   m=45376

45376


k=int(input("请输入一个数"))
m=0
while k!=0 :
        m=m*10+k%10;
        k=k//10 

print(m);

判断一个数是否为回文数字
123321 12321 123421不是

k=int(input("请输入一个数"))
m=0
n=k;
while k!=0 :
      m=m*10+k%10;
      k=k//10 
if m==n:
      print('这个数是回文数字');
else:
      print('这个数不是回文数字');  


range()函数的使用  		
r=range(10)  #只写一个参数 默认从0开始 步长默认为1  不包含十
print(list(r)); [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
r=range(1,10)#只写两个参数 起始和结束为止确定 步长默认为1  不包含十
print(list(r));[1, 2, 3, 4, 5, 6, 7, 8, 9]
r=range(1,10,2)#写三个参数 起始，结束和步长确定
print(list(r));[1, 3, 5, 7, 9]

for循环

for 自定义变量 in 可迭代的对象
      循环体

把1-9的值依次赋值给x	
for x in range(1,10):
    print(x);

求1-100的偶数和	
sum=0
for x in range(0,101,2):
        sum+=x
print(sum);
  1. break：结束循环 一般与if连用 达成条件 结束循环
  2. continue 结束这一轮循环 开始下一轮循环
  • 嵌套循环：外循环循环一次 内循环循环一轮 内循环是外循环的循环体
    *
   ***
  *****
 *******
*********


num=int(input("请输入行数"))
for x in range(1,num+1):
        for y in range(1,num-x+1):
                print(" ",end="");
        for n in range(2*x-1):
                print("*",end="");
        print();

列表

  • 列表类似于其他语言的(数组)链表，为了存储多个元素(数据)
  • lst=['hello',97]
  • 引用数据: 下标引用 下标从0开始
lst=['hello',18]
print(lst) #直接输出整个列表
print(lst[0]);#输出下标为0 也就是列表的第一个数据
print(lst[1]);

'''
输出内容:
hello
18
'''

列表的添加： 给列表添加数据

  1. append() 在列表的末尾添加一个元素
lst.append(100);
print(lst);
lst2=[30,40,50] 
lst.append(lst2) #把整个列表当成元素添加
print(lst)

'''
输出内容
['hello', 18, 100]
['hello', 18, 100, [30, 40, 50]]
'''
  1. extend() 在列表末尾至少添加一个元素
    添加多个元素：lst.extend(lst2) 把列表的每一个元素单独添加
lst=['hello',18]
lst.append(100);
print(lst);
lst2=[30,40,50]
lst.extend(lst2) #把整个列表当成元素添加
print(lst)

'''输出内容
['hello', 18, 100]
['hello', 18, 100, 30, 40, 50]
'''
  1. insert() 在列表的任意位置(索引下标，元素)添加元素
    lst.insert(0,2005); 指定位置 添加内容 其他元素全部后移
    print(lst);

列表的删除

  1. remove() 一次删除一个元素 没有元素就提示错误 相同元素删除前一个
    print(lst)
    lst.remove('hello')
    print(lst)
    lst.remove(1000)
  2. pop() 删除指定索引(下标)的元素 没有指定索引 默认删除最后一个
    lst.pop(3)
    print(lst)
    lst.pop()
    print(lst)
  3. lear(); 清空列表
    lst.clear()
    print(lst)
  4. del 删除列表
    del lst;
    print(lst) 错误 没有该列表

列表的排序

  1. sort 从下到大排序(升序排列)
reverse=True 降序排列  reverse=False
print('排序前列表',lst)
lst.sort()
print('排序后列表',lst)
lst.sort(reverse=True) #降序排列
print('排序后列表',lst)
  1. sorted 从小到大排序(升序排列)
    reverse=True 降序排列 reverse=False
    new_lst=sorted(lst,reverse=False);
    print(new_lst);

区别： sort在原列表中排序 sorted生成新的列表

字典：一个无序的可变序列，以键值对的形式存在
score={'zjy':59,'ls':99}

无序： 字典第一个存放的数据不一定在第一个空间

元组

python中一种有序序列 元组不可被改变

意义：安全 一般用元组

元组的创建方式：

t=('python','hello',119);
print(t);
print(type(t));
t[2]=100; #修改元组内容 会提示错误
t1=(10,20,[30,40],50)
print(t1)
print(type(t1))
t1[2].append(100) #可以修改元组内可变序列的内容 
print(t1)

集合

  1. 集合的创建方式
    s={10,30,70,60,30,50,60} 集合不能有重复的元素 且集合内容无序
    print(s);
    s1=set(range(6));
    print(s1);
    s2=set([11,12,13,14,15]) 将列表转成集合
    print(s2,type(s2))
    s3=set((33,44,55)) 将元组转成集合
    print(s3,type(s3))
    s4=set('python') 将字符串转成集合
    print(s4,type(s4))

  2. 集合的新增
    add 一次添加一个元素
    update 一次添加至少一个元素

  3. 集合的删除：

  • remove() 一次删除一个指定元素 元素不存在则抛出异常
  • discard() 删除指定元素 元素不存在也不抛出异常
  • pop 指定索引的元素
  • clear 清除集合
  1. 集合
  • 两个集合是否相等==、!=
  • 判断子集 issubset A={10,30} B=
  • 判断超集 issuperset
  • 判断没有交集 isdisjoint
  • 交集 intersection print(s1.intersection(s2))
  • 并集 union
  • 差集 difference
  • 对称集 symmetric——difference

函数

  • 什么是函数: 函数是一个功能描绘的过程。
    函数不调用不会执行

  • 为什么会有函数：
    1.防止代码冗余
    2.把一个一个功能模块化
    3.提高代码的可读性和维护性

函数的创建：

def 函数名(形参)
    函数体 
    return ...   //返回函数的结果

def fun(a,b):
    print('a=',a,'b=',b)
    return a+b;

调用函数  
        函数名(实参)
实参:实际的值  把实参结果传递给形参  一一对应 
根据位置来进行实参传递
def fun(a,b):
print('a=',a,'b=',b)
return a+b;

print(fun(10,20));

根据关键字来进行实参传递
def fun(a,b):
print('a=',a,'b=',b)
return a+b;

print(fun(b=10,a=20));


参数的一些变化： 
    def fun(a,b):
    print('a=',a)
    print('b=',b);
    a=900;
    b.append(20)
    print('a=',a)
    print('b=',b);
    return;

n=100
m=[12,13,14]
fun(n,m)
print(n)  n不会变化
print(m)  m会发生变化
  • 函数的返回值： 用return返回结果 return可以结束函数
def fun(m):
old=[]#存放奇数
new=[]#存放偶数
for i in m:
        if i%2:
                old.append(i)
        else:
                new.append(i)
return old,new
lst=[10,19,21,78,66,53,45,90]
print(fun(lst))

1.如果函数没有返回值,那么函数运行时不需要给调用处返回数据 return可以不写
2.函数返回值只有一个 直接返回该类型
3.函数返回值有多个 返回元组类型

函数递归

函数递归：自己调用自己 必须书写结束条件 结束条件一般写在开头

输出1-100

def fun(a):
	if(a<1):
		return;
	fun(a-1);
	print(a);
fun(100)
求阶乘
def fun(a):
        if(a<1):
                return 1;
        return a*fun(a-1);


print(fun(4))
斐波拉契数列

斐波拉契数列：1 1 2 3 5 8 13 21 34 55

def fun(a,0):
	print(a) #1,1
	if(a>100):
		return;
	b=a+b; #1=1+0，2=1+1
	return fun(a,b) #1,1;1,2
fun(1,0)

链表

2.2单顺序表基本操作（作业）

class mysqlist():
    def __init__(self,size):
        self.size=size
        self.sqlist=[]
    # 插入
    def listinsert(self,i,x):
        if i<1 or i>self.size:
            print("Insert Location Error！")
            return False
        else:
            self.sqlist.insert(i,x)
            return True
    # 删除
    def listdelete(self,i):
        if i<1 or i>self.size:
            print("Delete Location Error！")
            return False
        else:
            self.sqlist.pop(i)
            return False
    # 查找元素
    def findelem(self,i):
        if i<1 or i>self.size:
            print("search Location Error！")
            return False
        else:
            return self.sqlist[i]
    # 显示链表
    def showlist(self):
        return self.sqlist
    
    # 插入x作为线性表中的第i个元素
    def insert(self, i, x):
        if self.curLen == self.maxSize: # 判断顺序表的存储空间是否已满
            raise Exception("顺序表满")
        if i < 0 or i > self.curLen:    # 判断参数的值是否满足 0 <= i <+ curLen，若不满足则抛出异常
            raise Exception("插入位置非法")
        for j in range(self.curLen, i-1, -1):
            self.listItem[j] = self.listItem[j-1] # 将插入位置及之后的数据元素后移一个存储位置
        self.listItem[i] = x    # 在位置i处插入新的数据元素
        self.curLen += 1        # 表长加1

import random
testsqlist=mysqlist(10)
for i in range(1,12):
    testsqlist.listinsert(i,i*100)
print("插入元素后的顺序表为：",testsqlist.showlist())
for i in range(1,2):
    testsqlist.listdelete(i)
print("删除元素后的顺序表为：",testsqlist.showlist())
print(testsqlist.findelem(5))
2.3单链表基本操作(作业)

单链表的基本操作：
1、验证链表里面有没有值！
2、从头部插入数值！
3、从尾部插入数值！
4、按指定位置插入数值！
5、删除操作！
6、查找一个节点是否在链表中！
7、按下标查找节点处的数值！
8、给链表排序！
9、修改！

# 创建节点
class Node(object):
    def __init__(self, item):
        self.element = item
        self.next = None
 
 
# 创建单链表类
class SingleLinkList(object):
    def __init__(self):
        self.header = None
        self.length = 0
 
    # 1、判断是否为空
    def is_empty(self):
        if self.header == None:
            return True
        else:
            return False
 
    # 2、头部插入
    def add(self, node):
        if self.is_empty():
            self.header = node
        else:
            node.next = self.header
            self.header = node
            # currentNode = self.header
        self.length += 1
 
    # 3、尾部插入
    def append(self, node):
        current_Node = self.header
        if self.is_empty():
            self.add(node)
        else:
            while (current_Node.next != None):
                current_Node = current_Node.next
            current_Node.next = node
            self.length += 1
 
    # 4、指定位置插入
    def insert(self, node, index):
        current_Node = self.header
 
        if index > self.length + 1 or index <= 0:
            while(index > self.length + 1 or index <= 0):
                print("你要插入的位置不对，请重选位置:")
                index = eval(input())
 
 
        if index == 1:
            self.add(node)
        elif index == 2:
            node.next = self.header.next
            self.header.next = node
            self.length += 1
        else:
            for i in range(1, index - 1):
                current_Node = current_Node.next
            node.next = current_Node.next
            current_Node.next = node
            self.length += 1
 
 
    # 5、遍历
    def travel(self):
        current_Node = self.header
        if self.length == 0:
            print("目前链表没有数据！")
        else:
            print("目前链表里面的元素有:", end=" ")
            for i in range(self.length):
                print("%s " % current_Node.element, end=" ")
                current_Node = current_Node.next
            print("\n")
 
 
    # 6、排序不用交换节点的位置，只需要交换节点上的数据值
    def list_sort(self):
        for i in range(0, self.length - 1):
            current_Node = self.header
            for j in range(0, self.length - i - 1):
                if current_Node.element > current_Node.next.element:
                    temp = current_Node.element
                    current_Node.element = current_Node.next.element
                    current_Node.next.element = temp
 
                current_Node = current_Node.next
 
    # 7、按索引删除
    def delete(self, index):
        if index <= 0 or index > self.length:
            while(index <= 0 or index > self.length):
                print("你输入的下标不对，请重新输入需要删除的值的下标：")
                index=eval(input())
             #   return
        else:
            if index == 1:
                self.header = self.header.next
                currentNode = self.header
            elif index == 2:
                current_Node = self.header
                current_Node.next = current_Node.next.next
            else:
                current_Node = self.header
                for i in range(1, index - 1):
                    current_Node = current_Node.next
                current_Node.next = current_Node.next.next
        self.length -= 1
 
    # 8、查找是否包含,并返回下标
    def isContain(self, num):
        contain = 0
        current_Node = self.header
        for i in range(self.length):
            if current_Node.element == num:
                print("%d在链表中%d处\n" % (num, i+1))#i+1是在正常人认为的位置处，程序员一般是从0开始算起
                contain = 1
            current_Node = current_Node.next
        if contain == 0:
            print("%d不在链表中\n" % num)
 
    # 9、根据下标找节点
    def searchNodeByIndex(self, index):
        current_Node = self.header
        if index <= 0 or index > self.length:
            while(index <= 0 or index > self.length):
                print("你输入的下标不对，请重新输入:")
                index=eval(input())
             #   return 0
        if index > 0 or index <= self.length:
            for i in range(index - 1):
                current_Node = current_Node.next
            return current_Node
 
    # 10、根据下标修改节点的值
    def Alert(self, index, num):#index定义为下标
        current_Node = self.header
        if index <= 0 or index > self.length:
            print("你输入的下标不对，请重新输入!\n")
        else:
            for i in range(index - 1):
                current_Node = current_Node.next
            current_Node.element = num
 
 
def main():
    # 创建一个节点对象
    node1 = Node(1)
    # 创建一个单链表对象
    single_link_list = SingleLinkList()#实例化
 
 
 
    print('''
0、结束所有操作！！！！！！   
1、验证链表里面有没有值！     
2、从头部插入数值！           
3、从尾部插入数值！           
4、按指定位置插入数值！       
5、删除操作！                
6、查找一个节点是否在链表中！ 
7、按下标查找节点处的数值！   
8、给链表排序！              
9、修改！                    
       
          ''')
    while True:
        number=eval(input("输入下一步要进行的相应操作序号："))
        if (number == 1):
            print("正在验证链表里面有没有值：")
            single_link_list.travel()
            print("\n")
 
 
        if (number == 2):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在从头部插入数值：")
            node1=Node(eval(input("输入要插入的值:")))#从头部插入数值
            single_link_list.add(node1)
            print("操作后链表的状态。")
            single_link_list.travel()
 
 
        if (number == 3):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在尾部插入数值：")
            node2 = Node(eval(input("输入要插入的值:")))
            single_link_list.append(node2)
            print("操作后链表的状态。")
            single_link_list.travel()
 
 
        if (number == 4):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在按指定位置插入数值：")
            node3 = Node(eval(input("输入插入的数：")))
            position=eval(input("输入要插入到的位置为："))
            single_link_list.insert(node3, position)
            print("操作后链表的状态。")
            single_link_list.travel()
 
 
        if (number == 5):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在删除：")
            single_link_list.delete(eval(input("输入要删除哪个位置的数：")))
            print("操作后链表的状态。")
            single_link_list.travel()
 
 
        if (number == 6):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在查找一个节点是否在链表中：")
            single_link_list.isContain(eval(input("输入要验证的数：")))
 
 
        if (number == 7):
            print("正在按下标查找节点处的数值：")
            node = single_link_list.searchNodeByIndex(eval(input("输入下标值：")))#查找某节点处的值
            print("这个位置的值为：%s" % node.element)
 
 
        if (number == 8):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在排序：")
            single_link_list.list_sort()
            print("操作后链表的状态。")
            single_link_list.travel()
 
 
        if (number == 9):
            print("目前的链表状态。")
            single_link_list.travel()
            print("正在修改（这是在上面排序后的前提下修改。）：")
            index=eval(input("输入要修改的得位置："))#修改的下角标
            num=eval(input("输入要修改为的数："))#要修改成的那个数
            single_link_list.Alert(index, num)
            print("操作后链表的状态。")
            single_link_list.travel()#遍历一遍
 
 
        if number==0:
            break
 
 
if __name__ == '__main__':
    main()