专项代码1 常见大题代码合辑知识点梳理—2024届高考信息技术二轮复习知识点梳理

专项代码1 常见大题代码合辑 插入排序（通过链表实现） 原理： 第一步：先创建一个只有一个元素的链表。 第二步：依次生成节点，再将节点放置到链表中指定位置。 第三步：输出链表节点。 import random # 插入排序（链表实现）[678, 668, 267, 440, 795] ls = [] # 链表 ls[0]是值，ls[1]是指针 v = [random.randint(1, 1000) for i in range(5)] # 待排序的数 ls.append([v.pop(0), -1]) # 将第一个节点放入 head = 0 p = q = 0 while len(v) != 0: p = q = head while p != -1 and ls[p][0] > v[0]: q = p p = ls[p][1] if p!=head: #不放在链表头上 ls.append([v.pop(0), ls[q][1]]) ls[q][1] = len(ls) - 1 else: #放在链表头上 ls.append([v.pop(0), head]) head=len(ls)-1 p = head while p != -1: print(ls[p][0]) p = ls[p][1] 循环队列（通过链表实现） 原理： 入队：将节点添加到链表尾部（因为队列从尾部进入） 出队：删除当前头节点（因为队列出队是从头部出队） import random # 循环队列功能（链表实现） ls = [] # 链表 ls[0]是值，ls[1]是指针 head = 0 p = q = 0 for i in range(1,6):#生成5个值的队列 ls.append([i-1,i]) ls[len(ls)-1][1]=0#将队列最后一个指向第一个 #出队（出队完成后还是一个圈） p=head while ls[p][1]!=head:#找到最后一个节点 p=ls[p][1] head=ls[head][1] ls[p][1]=head #入队 p=head while ls[p][1] !=head: p=ls[p][1] ls.append([7,ls[p][1]]) ls[p][1]=len(ls)-1 数组插入（通过二分实现） 将ls数组中的值，插入到ls2中指定位置，插入结束了 ls2中的值依然有序 原理: 第一步:将原始值直接排序 第二步:通过对分查找法查找到对应的值插入的位置 第三步:插入值 import random ls=[random.randint(1,100) for i in range(5)] ls2=[random.randint(1,100) for i in range(10)] ls.sort() ls2.sort() for k in ls: i,j,m=0,len(ls2)-1,0 while i<=j: m=(i+j)//2 if k<ls2[m]: j=m-1 else: i=m+1 ls2.insert(i,k) #插入到数组中指定位置。第一个参数是位置第二个参数是值 print(ls2) 插入排序（for循环版本） import random n = 5 a=[random.randint(1,100) for i in range(n)]#生成随机数 for i in range(n): key = a[i] for j in range(i-1,-2,-1): if key >= a[j]: break else: a[j + 1] = a[j] a[j + 1] = key print(a) [16, 65, 2, 33, 11] 计数排序（通过双重循环实现） import random n = 5 a=[random.randint(1,100) for i in range(n)]#生成随机数[82, 43, 60, 27, 30] ls=[0]*n for i in range(n): for j in range(n): if a[i]<a[j]: ls[i]+=1 print(a) so=[] k=0 while len