《以后再也不怕别人问「单链表」的问题啦.doc》由会员分享，可在线阅读，更多相关《以后再也不怕别人问「单链表」的问题啦.doc（4页珍藏版）》请在三一文库上搜索。
1、以后再也不怕别人问单链表的问题啦写在之前在程序设计里，我们经常需要将同为某个类型的一组数据元素作为一个整体来使用，需要创建这种元素组，用变量来记录它们或者传入函数等等等等，线性表就是这样一组元素的抽象，它是某类元素的集合并且记录着元素之间一种顺序关系，是最基本的数据结构之一，在实际程序中运用非常广泛，比如 Python 中的 list 和 tuple 都可以看作是线性表的实现。基于各种实际操作等方面的综合考虑，我们提出了两种实现线性表的形式：顺序表和链表。顺序表是将表中的元素顺序存放在一大块连续的存储区间里，所以在这里元素间的顺序是由它们的存储顺序来表示的。链表则是将表中元素存放在一系列的结点
2、中（结点的存储位置可以是连续的，可以是不连续的，也就意味着它们可以存在任何内存未被占用的位置），这些结点通过连接构造起来，结点分为数据域和指针域。这次我们要学习的单链表就是链表的一种实现形式，数据域保存着作为表元素的数据项，指针域保存同一个表里的下一个结点的标识。在正式说单链表之前，我先来说一下很多人在学习链表之初都傻傻分不清的两个东西：头结点和头指针。头结点的设立是为了操作的统一和方便，是放在第一个元素的节点之前，它的数据域一般没有意义，并且它本身也不是链表必须要带的。那设立头节点的目的是什么呢？其实就是为了在某些时候可以更方便的对链表进行操作，有了头结点，我们在对第一个元素前插入或者删除结
3、点的时候，它的操作与其它结点的操作就统一了。头指针顾名思义，是指向链表第一个结点的指针，如果有头结点的话，那么就是指向头结点的指针。它是链表的必备元素且无论链表是否为空，头指针都不能为空，因为在访问链表的时候你总得知道它在什么位置，这样才能通过它的指针域找到下一个结点的位置，也就是说知道了头指针，整个链表的元素我们都是可以访问的，所以它必须要存在，这也就是我们常说的标识，这也就是为什么我们一般用头指针来表示链表。单链表n 个结点链接成一个链表，这也就是平时书上所说的链式存储结构，因为这个链表中的每个结点中只包含一个指针域，所以又叫单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑
4、次序链接在一起。单链表的第一个结点的存储位置叫做头指针，最后 self.data = data self.next = None单链表的基本操作首先我们先来创建一个链表类：class LinkList(object): def _init_(self): self.head = Node(None) # 判断链表是否为空 def IsEmpty(self): p = self.head # 头指针 if p.next = None: print(List is Empty) return True return False # 打印链表 def PrintList(self): if self
5、.IsEmpty(): return False p = self.head while p: print(p.data,end= ) p = p.next1.创建单链表创建单链表的过程其实就是一个动态生成链表的过程，说简单点就是从一个空链表开始，依次建立各个元素的结点，并把它们逐个插入链表，时间复杂度为 O(n)：def InitList(self,data): self.head = Node(data0) # 头结点 p = self.head # 头指针 for i in data1: node = Node(i) p.next = node p = p.next下面我们来测试一下：#
6、 testlst = LinkList()data = 1, 4, 5, 8, 2, 3lst.InitList(data)lst.PrintList()输出结果如下：1 4 5 8 2 32.计算单链表的长度在使用链表的时候，经常需要求表的长度，为此我们可以创建一个球表长的函数，这个函数就是从左到右扫描，遍历表中的所有结点并完成计数，时间复杂度为 O(n)：def LengthList(self): if self.IsEmpty(): return 0 p = self.head cnt = 0 while p: cnt += 1 p = p.next return cnt下面我们来测试一
7、下：# testlst = LinkList()data = 1, 4, 5, 8, 2, 3lst.InitList(data)print(lst.LengthList()输出的结果如下：63.单链表的插入假设我们要将结点 s 插入到 结点 p 的后面，只需要将结点 s 插入到结点 p 和 结点 p.next 之间即可，说起来简单，那么到底如何插入呢？请看下图：由上图我们可以看到，单链表结点的插入根本不需要惊动其它结点，只需要让 s.next 和 p.next 的指针稍作改变即可。让 p 的后继结点改为 s 的后继结点，再把 s 的后继结点变成 p 的后继结点。这里一定要切记，插入操作的顺序
8、不能改变，至于为什么，你可以拿起纸笔手动的画一下，结果一下子就会出来（对于单链表的表头和表尾的特殊情况，操作是相同的）。# 单链表的插入(在第 s 个结点后面插入 data)def InsertList(self,s,data): if self.IsEmpty() or s self.LengthList(): print(Insert failed！) return p = self.head index = 1 while index 由上图可以看出，我们只需要一步就可以实现删除操作，那就是让 p.next 直接为 p 的 next 的 next，p 的 next 为 q，所以也就是 p
9、.next = q.next，时间复杂度为 O(n)。# 单链表的删除(删除第 s 个结点)def DeleteList(self, s): if self.IsEmpty() or s self.LengthList(): print(Delete failed! ) return p = self.head index = 1 while index self.LengthList(): print(Read failed! ) return p = self.head index = 1 while index self.LengthList(): print(Insert failed！) return p = self.head index = 1 while index self.LengthList(): print(Delete failed! ) return p = self.head index = 1 while index self.LengthList(): print(Read failed! ) return p = self.head index = 1 while index s: index += 1 p = p.next print(第 个值为 .format(s, p.data)