(
课件网) 初识链表 册 别：选择性必修1 学 科：高中信息技术（浙教版） “老鹰抓小鸡”游戏：“小鸡”队伍中，后面的人拉住前面人的衣服，形成一条链。把每个人想象成一个点，如何存储数据？当有人进队伍，或者有人退出时，数据中这些点的前后关系如何表示？ A B C D E F G H I A B C D F G H I A B C D F G J H I 链表的概念 链表是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表中每个节点一般由“数据区域”和“指针区域”两部分构成。数据区域用于保存实际需要处理的数据元素，指针区域用来保存该节点相邻节点的存储地址，并通过该地址指针来实现从当前节点按顺序走到其相邻的节点。 A B C D E F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 4 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 列表a,头指针head=0 A B C D E F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 4 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 列表a,头指针head=0 A 1 a[0] B 2 a[1] head=0 C 3 a[2] A B C D E F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 4 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 A B C D F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 5 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 头指针head=0 删除元素字母“E” A B C D F G H I A B C D F G J H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 5 4 E 5 5 F 6 6 G 9 7 H 8 8 I -1 9 J 7 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 5 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 头指针head=0 在“G”后面插入元素字母“J” 链表的特性 1.同一链表中每个节点的结构均相同 2.每个链表必定有一个头指针，对实现对链表的引用和边界处理 3.链表占用的空间不固定 链表与数组 比较项目 数组 链表 逻辑结构 数据相邻的元素存储在地址连续的单元中；数据元素之间的邻接关系由存储单元的邻接关系来确定。 把数据元素放在任意的存储单元中（可连续，可不连续），用指针来反映数元素之间的相邻关系统。 元素的访问 可以随机访问，直接提取 要从头指针开始查找 元素的插入与删除 移动量较大，由元素的位置决定 任何位置上的删除，只需修改指针值，不需要移动 1.链表的创建 A B C D E F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 4 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 列表a,头指针head=0 head=0 a=[] n=int(input("请输入人数：")) for i in range(n-1): a.append([chr(65+i),i+1]) a.append([chr(65+n-1),-1]) 链表的基本操作 2.链表的访问 A B C D E F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 4 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 列表a,头指针head=0 head=0 a=[] n=int(input("请输入人数：")) for i in range(n-1): a.append([chr(65+i),i+1]) a.append(['I',-1]) k=head while(a[k][0]!='E'): k=a[k][1] print(k) 输出字母“E”在队伍中的位置 链表的基本操作 链表的基本操作 3.链表元素的删除 head=0 a=[] n=int(input("请输入人数：")) for i in range(n-1): a.append([chr(65+i),i+1]) a.append(['I',-1]) k=head prev=0 while(a[k][0]!='E'): prev=k k=a[k][1] a[prev][1]=a[k][1] print(a) 队伍中删除字母“E” A B C D F G H I 列表索引 数据区域 指针区域 0 A 1 1 B 2 2 C 3 3 D 5 4 E 5 5 F 6 6 G 7 7 H 8 8 I -1 链表的基本操作 4.链表元素的插入 head=0 a=[] n=int(input("请输入人数：")) for i in range(n-1): a.append([chr(65+i),i+1]) a.append(['I',-1]) #删除字母“E”（此处省略） #在“G”后面插入“J” alen=len(a) a.append([ ... ...
