1、2.2 链表什么是链表？链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表的表示？Dui=“吴坚”，1,“王林”，2,“黄刚”，3,“李丰”，-1节点（由数据区域和指针区域两部分构成）Dui=“吴坚”，1,“王林”，2,“黄刚”，3,“李丰”，-1Dui00=“吴坚”Dui01=1 Dui10=“王林”Dui11=2 .Dui31=?-1尾节点指针想一想：如何访问链表？head=0头指针，指向第一个节点链表的特性（1）同一链表中每个节点的结构均相同（2）每个链表必定有一个头指针，以实现对链表的引用和边界处理（3）链表占用的空间不固定单向链表的基本操作1.单向链表
2、的创建（1）Python中可以使用二维列表来模拟单向链表，用包含两个元素的列表来表示每一个节点，其中第一个元素存储数据，第二个元素存储指针（即后继节点在二维列表中的索引）。（2）创建一个空链表linklist的代码如下：linklist=head=-1（3）创建一个拥有2个节点的链表linklist的代码如下：linklist=6,1,8,-1 head=02.单向链表节点的访问链表节点只能通过头指针（head）进行访问，其他节点通过节点间的指针依次访问。可以设计如下自定义函数输出链表的所有节点：Def display(a,head):p=head while ap1!=-1:print(ap
3、0,end=“”)p=ap1 print(ap0)3.单向链表节点的插入链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的指针，将新节点插入到链表的正确位置。从头部插入新节点nextdata1nextdata2nextdata3-1head单向链表从头部插入新节点new datanextdata1nextdata3data2next-1head代码实现a=“data1”,1,“data2”,2,“data3”,-1head=0a.append(“new_data”,head)head=len(a)-1从中间或者尾部插入新节点该怎么实现呢？从中间插入新节点a=“dat
4、a1”,1,“data2”,2,“data3”,-1head=0P=0a.append(“new_data”,ap1)ap1=len(a)-1从尾部插入新节点a=“data1”,1,“data2”,2,“data3”,-1head=0P=headWhile ap1!=-1 p=ap1a.append(“new_data”,ap1)ap1=len(a)-14.单向链表节点的删除删除单向链表的节点有三种情形：删除头节点、删除中间节点和删除尾节点。data1nextdata2nextdata3-1headdata1nextdata2nextheaddata3-1单向链表删除头节点代码实现a=“dat
5、a1”,1,“data2”,2,“data3”,-1head=0head=ahead1data1nextdata2nextdata3-1headdata1nextdata2nextdata3-1headdata1nextdata2nextdata3-1headdata1nextnexthead单向链表删除中间节点代码实现a=“data1”,1,“data2”,2,“data3”,-1head=0pre=0p=apre1apre1=ap1data1nextdata2nextdata3-1headheaddata1nextdata2nextdata3-1单向链表删除尾部节点代码实现a=“data1
6、”,1,“data2”,2,“data3”,-1head=0pre=headwhile aapre11!=-1 pre=apre1apre1=-1链表节点的删除，并没有将元素从列表中删除，而仅仅是修改了节点指针域的值，通过将被删除节点的前驱节点和其后继节点直接相连的方式实现。尾节点可以直接删除，若删除了头节点，则需要修改头指针。删除节点小结：练一练1.使用python 的二维列表来模拟单向链表，如下代码创建了一个拥有4个节点的链表a：a=“hello”,1,“china”,3,“Olympics”,-1,“winter”,2head=0a11的值为：A.1 B.2 C.0 D.3依次输出各节点
7、数据域的值，则输出内容为_Dhello china winterOlympics2.单向链表中插入新节点的过程如图所示。使用python的二维列表来模拟单向链表，已知插入节点前列表a=“红”,1,“橙”,2,“绿”,3,“青”,-1，则在删除节点“橙”之后，列表a的值为A.“红”,1,“绿”,3,“青”,-1B.“红”,1,“绿”,2,“青”,-1C.“红”,1,“橙”,2,“绿”,3,“青”,-1D.“红”,2,“橙”,2,“绿”,3,“青”,-1D3.在下列列表中将新节点插入到data2和data3中间，则下列步骤不需要的是：data1nextdata2nextdata3nextdata4nextnew datanextA.断开data2与data3的连接B.断开data3与data4的连接C.使new data的指针指向data3D.使data2的指针指向new dataB4.有如下python程序段，表示一个链表及操作：a=5,-1,9,4,7,3,2,1,6,0head=2p=headb=While ap1!=-1:b.append(ap0)p=ap1b.append(ap0)print(b)程序执行后，输出的结果为：A.7,2,9,6,5,5 B.5,9,7,2,6 C.7,2,9,6,5 D.2,9,6C谢 谢
