数据结构基础知识03--高考信息技术一轮，二轮复习 数据结构基础知识（浙教版2019）

数据结构基础知识（三） 【知识要点】 一、“数据合并”问题简化成合并两个有序数据序列的问题，对如何使用数组解决数据合并问题进行了分析并设计了算法。下面将对算法进行修改和优化，避免插入数据时其他数据元素的移动，并编程实现该功能。 算法设计： ①初始化3个数组a，b，c，元素个数分别为m，n和n+m。数组a和数组b用来存储已有的两个有序数据（降序），数据使用随机函数randint(start,end)产生；数组c用于保存合并后的所有数据（降序），所有数组元素的值初始化为0。②使用变量i指向数组a当前未处理数据中要处理的数据元素的位置，初始化为0；变量j指向数组b当前未处理数据中要处理的数据元素的位置，初始化为0；变量k指向数组c中可加入元素的位置，初始化为0。 ③重复以下操作，直至数组a或数组b中的数据元素全部合并入数组c中：比较a[i]和b[j]的大小，若a[i]≥b[j]，则将a[i]放入数组c中，并将i和k的值增加1；否则，将b[j]放入数组c中，并将j和k的值增加1。④如果数组a或数组b中尚有未处理的数据元素，那么将剩余数据元素按原有顺序依次存入数组c中，合并完成，输出数组c。 from random import randint a=[0]*20;b=[0]*15;c=[0]*35 #创建数组 a[0]=randint(95,100) for i in range(1,20): # 随机产生降序数据序列一 a[i]=a[i-1]-randint(1,5) b[0]=randint(95,100) for i in range(1,15): # 随机产生降序数据序列二 b[i]=b[i-1]-randint(1,5) print(" 原始数据序列一为： ",a) print(" 原始数据序列二为： ",b) 方法一：通过双指针逐个遍历二数组元素，将较大的存入合并数组中 i=0;j=0;k=0 while(i<20 and j>15): # 合并数据直至某个数组数据合并完成 if a[i] >=b[j]: c[k]=a[i];i=i+1;k=k+1 else: c[k]=b[j];j=j+1;k=k+1 while i < 20: # 当数据序列一中还有数据时的处理 c[k]=a[i];i=i+1;k=k+1 while j < 15: # 当数据序列二中还有数据时的处理 c[k]=b[j];j=j+1;k=k+1 print("合并后的数据序列为：",c) 方法二：将b数组元素依次插入a数组中 for m in range(len(b)): a.append(b[m]) tmp = a[-1] n=len(a)-2 while tmp>a[n] and n>0: a[n+1]=a[n] n=n-1 a[n]=tmp print(a) (2)将两个有序链表中的数据合并到一个链表中。 from random import randint data_a=[];head_a=-1 data_b=[];head_b=-1 tmp=randint(95,100) data_a.append([tmp,head_a]) head_a=0 for i in range(1,20): tmp=data_a[i-1][0]-randint(1,5) data_a.append([tmp,data_a[i-1][1]]) data_a[i-1][1]=i print("链表结构的原始数据序列一") print(data_a) tmp=randint(95,100) data_b.append([tmp,head_b]) head_b=0 for i in range(1,25): tmp=data_b[i-1][0]-randint(1,5) data_b.append([tmp,data_b[i-1][1]]) data_b[i-1][1]=i print("链表结构的原始数据序列二") print(data_b) k_a = head_a;q_a = head_a;k_b = head_b while(k_a != -1 and k_b != -1): if data_a[k_a][0] >= data_b[k_b][0]: q_a = k_a k_a = data_a[k_a][1] else: if k_a == head_a: # 在链表d