0x01 列表

列表：数据序列，是能存储多个数据的连续存储空间。

• 列表的创建

  a_list = [1,2,3]
  a_list = ['this','is','a','list']
  a_list = ['this','is','test',1,2,3]
  a_list = list('hello')
  # ['h', 'e', 'l', 'l', 'o']
  a_list = list(range(1,20,2))
  # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

• 列表的访问

  a_list = ['this','is','a','list']
  print(a_list[0])
  # this
  print(a_list[-1])
  # list
  print(a_list[5])
  # IndexError: list index out of range
  print(a_list[1:3])
  # ['is', 'a']
  print(a_list[1:])
  # ['is', 'a', 'list']

• 列表的遍历

  a_list = ['this', 'is', 'a', 'list']
  for x in a_list:
    print(x)
  for i in range(len(a_list)):
    print(a_list[i])

  0x02 顺序查找

• 基本实现

  list = list(range(1,20,2))
  # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  x = int(input('请输入要查找的整数：'))
  for i in range(len(list)):
    if i == x:
        print('找到了，整数{}在列表中'.format(x))

• 进行优化，增加查找不到时的反馈

  list = list(range(1, 20, 2))
  print(list)
  # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  sign = False
  x = int(input('请输入要查找的整数：'))
  for i in range(len(list)):
    if list[i] == x:
        print('找到了，整数{}在列表中'.format(x))
        sign = True
  if not sign:
    print('没找到啊')

• 数据查找相关函数

  # 数据查找相关函数
  list = list(range(1, 20, 2))
  # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  print(list.index(13))
  # 6
  # 返回第一个数据为13的下标
  print(list.index(15, 2, 10))
  # 7
  # 返回2到9(10-1)之间第一个数据为15的下标
  temp_list = [1, 1, 1, 1, 1, 2, 3]
  print(temp_list.count(1))
  # 5
  # 返回数据为1的个数

• 使用内置函数实现上述顺序查找算法

  list = [1, 2, 2, 3, 3, 3, 4, 4, 5, 6]
  x = int(input('请输入要查找的整数x:'))
  n = list.count(x)
  if n == 0:
    print('没找到{}'.format(x))
  else:
    j = 0
    for i in range(n):
        j = list.index(x, j, len(list)) + 1
        # 指定范围进行查找
        print('找到了，第{}个数是{}'.format(j, x))

  0x03 二分查找

• 二分查找与顺序查找对比
  

• python实现

  # 二分查找
  list = list(range(1, 20, 2))
  # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  x = int(input('请输入要查找的整数：'))
  start = 0
  end = len(list) - 1
  while start <= end:
    mid = (start + end) // 2
    if list[mid] == x:
        break
    elif x < list[mid]:
        end = mid - 1
    else:
        start = mid + 1
  if start <= end:
    print('找到了，第{}个数是{}'.format(mid + 1, x))
  else:
    print('没找到')

  0x04 添加数据

• python实现

  list = [1, 3, 5, 7, 9, 2, 4, -1, -1]
  # 此处-1表示为空，表示占位符
  x = int(input('请输入整数x:'))
  i = len(list) - 1
  while i >= 0:
    if list[i] != -1:
        break
    i -= 1
  list[i + 1] = x
  print(list)
  # [1, 3, 5, 7, 9, 2, 4, 1, -1]

• 内置函数

  # append(向列表尾部添加数据)
  list = list(range(1,10,2))
  # [1, 3, 5, 7, 9]
  x = int(input('请输入整数x:'))
  list.append(x)
  print(list)
  # [1, 3, 5, 7, 9, 1]
  # ---
  # extend() 函数用于在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表）。
  list = list(range(1,10,2))
  # [1, 3, 5, 7, 9]
  list.extend([1,2,3])
  print(list)
  # [1, 3, 5, 7, 9, 1, 2, 3]
  # ---
  # insert() 函数用于将指定对象插入列表的指定位置。
  list = list(range(1, 10, 2))
  # [1, 3, 5, 7, 9]
  list.insert(1, 100)
  # list.insert(index, obj)
  print(list)
  # [1, 100, 3, 5, 7, 9]

  0x05 删除数据

• python实现

  list = [1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
  x = int(input('请输入要删除的整数x:'))
  n = len(list)
  for i in range(n):
    if list[i] == x:
        list[i] = -1
  print(list)
  # [-1, 3, 5, 7, 9, 2, 4, 6, 8, 10]

• 列表删除操作内置函数

  # pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值
  list = [1, 3, 5, 7, 9]
  list.pop()
  # [1, 3, 5, 7]
  # 默认删除最后一个
  list.pop(1)
  # [1, 5, 7]
  # 删除列表第二个元素
  # ---
  # remove() 函数用于移除列表中某个值的第一个匹配项
  list = [1, 3, 5, 7, 9]
  list.remove(3)
  # [1, 5, 7, 9]

• 问题：删除所有重复元素

  list = [1, 1, 1, 1, 1, 1, 3, 5, 5, 5, 5, 5, 5, 5, 7, 9]
  x = int(input('请输入要删除的整数:'))
  n = list.count(x)
  # n为列表有多少个x，执行n次remove()函数即可删除列表中所有x值
  for i in range(n):
    list.remove(x)
  print(list)
  # [3, 5, 5, 5, 5, 5, 5, 5, 7, 9]