12数据结构的简单应用课件高二上学期选择性必修1《数据与数据结构》第1章浙教版.pptxVIP

1.3数据结构的简单应用信息技术选考课程

学习目标1、了解一维数组和二维数组的表示的方法及处理效率的差别。2、了解数组的访问、插入、删除基本操作。3、了解链表的访问、插入、删除基本操作。4、通过了解数组和链表的数据合并过程，理解不同数据结构会导致处理效率的不同。

一、数组的访问/插入/删除姓名年龄身高体重阮启宇田1617390彭嘉…xm[i]age[i]sg[i]tz[i]内存xm[0]xm[1]xm[2]python语言为例：xm=[“阮启发”,”周宇田”,”彭嘉华”]age=[16,16,16]sg=[185,173,180]tz=[121,90,120]一维数组：每列是一批相同性质和类型的数据用一个数组名和下标来唯一确定数组元素，通过数组名[下标索引]的方式来直接访问数组元素，效率高。“阮启发”“周宇田”“彭嘉华”........问题来了：这样需要四个数组才能保存这些数据，有没有更好的办法呢？

一、数组的访问/插入/删除年龄身高体重16185121161739016180120………………sc[i][0]sc[i][1]sc[i][2]内存sc[0][0]sc[0][1]sc[0][2]sc=[[16,178,121],[16,173,90],[16,180,120]]#用列表的列表来模拟二维数组i=0i=1i=2行优先存储sc[1][0]sc[1][1]sc[1][2]161851211617390......二维数组利用二维数组来组织和存储数据，通过数组名[行下标索引]来访问数据元素，通过数组名[行下标索引][列下标索引]来访问数据项，注意第一个元素的行列索引为0。二维数组在程序的实现效率上更高！sc[i]i=...

一、数组的访问/插入/删除不同数据结构会导致处理效率的不同①数组元素插入②数组元素删除基于数组存储的连续性

1.基于数组的算法设计与描述n=m=5（1）将数组a中所有元素存储到数组c（辅助数组）的前n个位置中；201514104c2.不同数据结构会导致处理效率的不同基于数组的数据合并

2.不同数据结构会导致处理效率的不同1.基于数组的算法设计与描述（2）将数组c右边的m个元素赋值为–1（c(n+1)直到c(n+m)）；201514104c-1-1-1-1-1-1是监视哨即该位置目前没有实际数据

2.不同数据结构会导致处理效率的不同1.基于数组的算法设计与描述n=m=5（3）变量p（数据插入位置）赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n；201514104c-1-1-1-1-10iptot

2.不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：191612-185b201514104c-1-1-1-10iptot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；④如果c(p)≤b(i)，那么依次将c(tot)，c(tot–1)，…，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。

2.不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：-151916128b201514104c-1-1-10iptot①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；④如果c(p)≤b(i)，那么依次将c(tot)，c(tot–1)，…，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。②如果c(p)＞b(i)，那么使p值增加1；

2.不同数据结构会导致处理效率的不同（4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）：①p值增加1；②如果c(p)＞b(i)，那么使p值增加1；③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；④如果c(p)≤b(i)，那么依次将c(tot)，c(tot–1)，…，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加11b201514104c0itotp③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；

二、链表的访问/插入/删除指由多个节点（由数据域和指针域组成）链接成的序列，通过节点的指针域将多个节点按数据元素的逻辑顺序链接在一起。常见的有：单向链表、双向链表、循环链表。李丰^黄刚王林吴坚头节点数据域指