1.2数据结构的简单应用课件2024-2025学年高二上学期选择性必修1《数据与数据结构》第1章浙教版（2019）

1.3数据结构的简单应用 信息技术 选考课程 学习目标 1、了解一维数组和二维数组的表示的方法及处理效率的差别。 2、了解数组的访问、插入、删除基本操作。 3、了解链表的访问、插入、删除基本操作。 4、通过了解数组和链表的数据合并过程，理解不同数据结构会导致处理效率的不同。 一、数组的访问/插入/删除 姓名 年龄 身高 体重 阮启发 16 185 121 周宇田 16 173 90 彭嘉华 16 180 120 …… …… …… …… 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] 一维数组：每列是一批相同性质和类型的数据 用一个数组名和下标来唯一确定数组元素，通过数组名[下标索引]的方式来直接访问数组元素，效率高。 “阮启发” “周宇田” “彭嘉华” ........ 问题来了：这样需要四个数组才能保存这些数据，有没有更好的办法呢？ 一、数组的访问/插入/删除 年龄 身高 体重 16 185 121 16 173 90 16 180 120 …… …… …… 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=0 i=1 i=2 行优先存储 sc[1][0] sc[1][1] sc[1][2] 16 185 121 16 173 90 ...... 二维数组 利用二维数组来组织和存储数据，通过数组名[行下标索引]来访问数据元素，通过数组名[行下标索引][列下标索引]来访问数据项，注意第一个元素的行列索引为0。 二维数组在程序的实现效率上更高！ sc[i] i=... 一、数组的访问/插入/删除 不同数据结构会导致处理效率的不同 ①数组元素插入 ②数组元素删除 基于数组存储的连续性 1. 基于数组的算法设计与描述 n=m=5 （1）将数组a中所有元素存储到数组c（辅助数组）的前n个位置中； a 19 16 12 8 5 b 20 15 14 10 4 c 2.不同数据结构会导致处理效率的不同 基于数组的数据合并 6 2.不同数据结构会导致处理效率的不同 1. 基于数组的算法设计与描述 （2）将数组c右边的m个元素赋值为–1（c(n+1)直到c(n+m)）； a 19 16 12 8 5 b 20 15 14 10 4 c -1 -1 -1 -1 -1 -1是监视哨 即该位置目前没有实际数据 7 2.不同数据结构会导致处理效率的不同 1. 基于数组的算法设计与描述 n=m=5 （3）变量p（数据插入位置）赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n ； a 19 16 12 8 5 b 20 15 14 10 4 c -1 -1 -1 -1 -1 0 i p tot 8 2.不同数据结构会导致处理效率的不同 （4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）： 19 16 12 -1 8 5 b 20 15 14 10 4 c -1 -1 -1 -1 0 i p tot ①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。 9 2.不同数据结构会导致处理效率的不同 （4）将数组b中元素b(i)逐个插入到数组c中（1≤i≤m）： -1 5 19 16 12 8 b 20 15 14 10 4 c -1 -1 -1 0 i p tot ①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； 10 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。 19 16 12 8 5 -1 b 20 15 14 10 4 c 0 i tot p ③如果c(p)=–1，那么直接将b(i)存储到c(p)中，同时tot值增加1； 11 二、链表的访问/插入/删除 指由多个节点（由数据域和指针域组成）链接成的序列，通过节点的指针域将多个节点按数据元素的逻辑顺序链接在一起。常见的有：单向链表、双向链表、循环链表。 李丰 ^ 黄刚 王林 吴坚 头节点 数据域 指针域 head 空指针 头指针 注意：和数组不同，链表在内存中的存储是不连续的，所以不能直接用下标索引的方式来访问数据元素，而是要通过头指针进行访问，其他节点通过节点间的指针依次访问。如：想要访问“黄刚”，则访问的顺序是“吴坚”“王林”“黄刚” 二、链表的访问/插入/删除 Green的前驱节点是Blue，后继节点是Yellow ①链表元素插入 ②链表元素删除 基于链表的数据合并：链表b合并到链表a 链表a: head_a 指针p1 指针p 链表b: head_b 指针q1 指针q 4 指针p、q：指向两个链表的当前节点 指针p1、q1：指向两个链表的当前节点的前驱节点 14 基于数组和链表的数据合并操作小结 1、从用两种数据结构分别来解决同一个问题的过程可知，不同数据结构会导致算法的不同，而且解决问题的效率也不同。 2、 用数组实现合并，共需要移动的次数达到次，而用链表实现时，向链表a中插入一个节点，最多需要5次指针操作，全部合并完成最多需要5n次指针操作，比数组处理低一个数量级。 15 链表和数组优缺点 总结：当数据要频繁地访问使用的时候，可以用数组这种数据结构存储，当数据要频繁地做插入和删除操作时，可以用链表来存储。 数组的优点 (1)随机访问性强 (2)查找速度快 数组的缺点 (1)插入和删除效率低 (2)可能浪费内存 (3)内存空间要求高，必须有充足的连续内存空间 链表的优点 (1)插入删除速度快 (2)内存利用率高，不会浪费内存 (3)大小没有固定，拓展灵活 链表的缺点 不能随意查找，必须从第一个开始遍历，查找效率低 存储数据的空间（信息域+指针域）大于数组 访问 插入 删除 数组 快 慢 慢 链表 慢 快 快 表格内容 建议抄个笔记 入栈出栈补充练习 一个栈的入栈顺序是abcde，则栈的输出序列不可能的是（ ) A、edcba B、decba C、dceab D、abcde 做题技巧：在输出序列中任意元素后面不可能出现比该元素小并且是升序（指的是元素的序号）的两个元素 $$