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

1.3数据结构的简单应用信息技术选考课程学习目标1、了解一维数组和二维数组的表示的方法及处理效率的差别。2、了解数组的访问、插入、删除基本操作。3、了解链表的访问、插入、删除基本操作。4、通过了解数组和链表的数据合并过程，理解不同数据结构会导致处理效率的不同。一、数组的访问/插入/删除姓名年龄身高体重阮启发16185121周宇田1617390彭嘉华16180120……………………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个位置中；a19161285b201514104c2.不同数据结构会导致处理效率的不同基于数组的数据合并2.不同数据结构会导致处理效率的不同1.基于数组的算法设计与描述（2）将数组c右边的m个元素赋值为–1（c(n+1)直到c(n+m)）；a19161285b201514104c-1-1-1-1-1-1是监视哨

即该位置目前没有实际数据2.不同数据结构会导致处理效率的不同1.基于数组的算法设计与描述

n=m=5（3）变量p（数据插入位置）赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n；a19161285b201514104c-1-1-1-1-10iptot2.不同数据结构会导致处理效率的不同（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值增加1。19161285-1b201514104c0itotp③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1；二、链表的访问/插入/删除指由多个节点（由数据域和指针域组成）链接成的序列，通过节点的指针域将多个节点按数据元素的逻辑顺序链接在一起。常见的有：单向链表、双向链表、循环链表。李丰^黄刚王林吴坚头节点数据域指针域head空指针头指针注意：和数组不同，链表在内存中的存储是不连续的，所以不能直接用下标索引的方式来访问数据元素，而是要通过头指针进行访问，其他节点通过节点间的指针依次访问。如：想要访问“黄刚”，则访问的顺序是“吴坚”

“王林”

“黄刚”二、链表的访问/插入/删除Green的前驱节点是Blue，后继节点是Yellow①链表元素插入②链表元素删除基于链表的数据合并：链表b合并到链表a链表a:head_a指针p1指针p链表b:head_b指针q1指针q4指针p、q：指向两个链表的当前节点指针p1、q1：指向两个链表的当前节点的前驱节点基于数组和链表的数据合并操作小结

链表和数组优缺点总结：当数据要频繁地访问使用的时候，可以用数组这种数据结构存储，当数据要频繁地做插入和删除操作时，可以用链表来存储。数组的优点(1)随机访问性强

(2)查找速度快数组的缺点(1)插入和删除效率低(2)可能浪费内存(3)内存空间要求高，必须有充足的连续内存空间链表的优点(1)插入删除速度快(2)内存利用率高，不会浪费内存(3)大小没有固定，拓展灵活链表的缺点

不能随意查找，必须从第一个开始遍历，查找效率低

存储数据的空间（信息域+指针域）大于数组访问插入删除