这篇文章给大家分享的是有关C++和python如何实现单链表的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
链表是数据元素的线性集合(Linear Collection
),物理存储不连续。那么,这种设计的优点是什么?缺点又是什么?
链表的基本结构:
链表是由一系列的“节点”组成在一起的集合,节点(Node)由数据域(data)和指针域(next)组成。
从功能上看,data负责存储数据,next负责存储下一个节点的位置。当然,用更加严格的语句来讲,next存储的是其直接后继的地址,关于直接后继的定义见:
链表的分类:
常见的链表种类有:单向链表、双向链表、单向循环链表、双向循环链表,将会在后面文章中单独介绍各种链表的结构和代码实现,以及对应的链表操作。
链表的基本操作:
链表的基础操作包含:插入、删除、查找、合并等,此外还有:反转、排序、深度复制等。
链表的优点:
插入和删除快;
存储空间不受限制,可动态申请扩充,不需事先开辟内存;
链表的缺点:
相比于数组,链表的需要更多的存储空间(需存储指针);
存储不连续导致其访问时间长;
从反向访问角度,单向链表难以反向访问,扩展为双向链表则需要额外存储反向指针;
每次节点访问都需要从头部开始;
基本结构:
单链表的结构含有四个概念:头指针、头结点、普通Node、尾结点,下面分别介绍:
头指针指向头结点,是单链表的表示,必不可少;
头结点是单链表的第一个节点,其数据域内容一般无效;
普通Node即用于数据存储和直接后继指针存储的节点;
尾结点即链表中最后一个节点,其指针域next为空,其后无节点;
单链表的基本操作:
针对单链表常见的操作有:增、改、查、删等,
常用的操作如下:
(1)增
对链表添加元素一般有三种方法:头插法(add)、尾插法(append)、任意位置插入法(insert)。
(2)改
改动链表中某个节点的data
。
(3)查
查找分为按值查找和按位置查找两种,前者表示按照值查找对应位置,后者表示按位置查找对应值;
(4)删
删除分为按值删除和按位置删除两种;前者表示按照值删除对应节点,后者表示按照位置删除对应节点;
实现说明:
按照自己目前所看的资料,一般都会实现下面介绍的这些函数,具体介绍放在python和C++实现中。
按照单链表的定义可知,节点包含数据域data
和指针域next
:
但是由于next和python的内置函数next()
重名,所以指针域使用pointer
表示。
代码如下:
class Node: def __init__(self, data): """ Args: data: data of node, any type """ self.data = data self.pointer = None
上述Node类对象即为链表的基本组成结构,可以用于实现头结点、普通节点和尾结点。
因此,链表类只需要提供头指针:
class Single_Linked_List: def __init__(self, node=None): self.__head = node
实际上,只需要判断头指针是否指向Node类对象(或是否等于None),就可判断一个链表是否为空:
def is_empty(self): """判断链表是否为空""" if self.__head == None: return True else: return False
在链表头进行节点插入是很常见的插入操作,这种方式使得“先插入的节点在链表尾部”。头插法需要将头指针指向新的节点,并让新的节点指向原来的头结点:
def add(self, data): """Add dnode into head """ # 创建新节点 node = Node(data) # 令新的节点指向原来的头结点 node.pointer = self.__head # 令头指针指向新的节点 self.__head = node
如果想要链表节点次序和插入次序相同,就需要使用尾插法。在插入之前需要判断链表是否为空,如果不为空才能进行插入(可以调用前面定义的is_empty()
函数,但是下述代码没有)。
此外,还需要进行链表的遍历操作,找到最后一个节点。单链表只能从表头开始访问,所以每次尾插都必须遍历。
def append(self, data): """ append node into tail """ node = Node(data) # 头指针为空时即为首节点 if self.__head == None: self.__head = node # 头指针不为空时进行遍历 else: current = self.__head while current.pointer != None: current = current.pointer current.pointer = node
前面介绍的头插法和尾插法,其原理相对简单,但是并不能完全满足插入需求。如果知道目标插入的位置,可以采用insert()
函数实现任意位置的节点插入。
需要注意的是,在实现insert()
函数时必须考虑到“position
”参数可能出现的几种情况。比如python中并没有明确的类型要求,所以要检查“position”是不是int类型。
对于核心的节点插入实现功能,需要找到目标插入位置对应的节点,并使得这个节点指向新节点,让新节点指向原位置节点的后一个节点。这个过程类似于铁链中加入铁环的过程,要保证新铁环和原来的两个铁环相连接。
def insert(self, position, data): """在任意位置插入节点 Args: position:插入节点的位置,int data:插入节点的值 """ if not isinstance(position, int): raise ValueError("expect type is 'int', but got {}".format(position.__class__)) # 头插法 if position <= 0: self.add(data) # 尾插法 elif position > self.get_length(): self.append(data) else: current = self.__head current_position = 0 node = Node(data) # 目的:计算出插入位置 while current_position < position -1: current_position += 1 current = current.pointer # 首先:必须使得当前节点的pointer指针指向新建的node # 其次:必须保证新建的node的pointer指向当前节点的后一个节点 node.pointer = current.pointer current.pointer = node
对于调用者和类内部的其它函数来做,链表长度是一个非常有用的值。比如在插入函数insert()
中,需要判断插入位置是不是大于链表长度。
计算链表长度的实现比较简单,只需要遍历链表的所有节点,并用计数器来统计节点的数目即可。
def get_length(self): """ 获取链表的长度""" # 没有任何node if self.__head == None: return 0 # 节点数统计 else: current = self.__head length = 0 while current != None: current = current.pointer length += 1 return length
链表、树、图等结构都需要遍历操作,其中链表的遍历比较简单,只需要依次的访问所有节点即可。
def traversal(self): current = self.__head i = 0 # 循环结束的条件依旧是节点的pointer指向不为空 while current != None: print("Element {} is {} ".format(i, current.data)) current = current.pointer i += 1
前面提到搜索有按值搜索和按位置搜索两种,它们的原理和实现都十分相似,所以仅以按值搜索为例。
需要注意的是,insert()
函数需要判断链表是否为空,并且需要考虑到目标值不在链表中的情况,分别对应不同的返回值。
def search(self, data): """ 返回值为data的第一个节点""" if self.__head == None: return -1 else: current = self.__head current_position = 0 # 遍历节点 while current != None: # 目标值搜索成功 if current.data == data: return current_position # 目标值搜索不到则继续搜索 else: current_position += 1 current = current.pointer # 目标值不存在于链表中 return False
上述的查找中以“按值查找”为例,这次删除中同样以“按值删除”为例,“按位置删除”的实现与之类似。
按值删除,即删除目标值对应的目标节点。在进行遍历时,需要记录当前节点和当前节点的前一个节点。因为,一旦查找大目标值所在的目标节点,需要令目标节点的前一个节点指向目标节点的下一个节点,即完成节点的删除。
def delete(self, data): """ 删除值为data的第一个节点""" if self.is_empty(): return None # 记录当前节点和前一个节点 current = self.__head piror = None while current != None: # 查找成功分为两种情况 if current.data == data: # 目标节点为头结点 if current == self.__head: self.__head = self.__head.pointer return True # 目标节点不是头结点 # 令目标节点的前一个节点指向目标节点的后一个节点 else: piror.pointer = current.pointer return True # 更新当前节点和前一个节点 else: piror = current current = current.pointer return False
前面的python
实现中已经分析了各个函数的作用,以及对应的实现过程。虽然python和C++的语法不同,但是核心过程是类似的,所以下面不再重复对过程的叙述。
由于C++的指针必须指定类型,所以需要使用空指针NULL
作为pointer
的值。
class Node{ public: int data; Node *pointer=NULL; };
遵循声明和实现分类的策略,先对各个函数进行声明。
class SingleLinkedList { public: SingleLinkedList(); bool isEmpty(); int getLength(); void add(int data); void append(int data); void insert(int position, int data); void traversal(); int search(int data); void remove(int data); private: Node *head; };
bool SingleLinkedList::isEmpty() { // 头结点不指向任何结点,为空 if (head->pointer == NULL) { return true; } else { return false; } }
void SingleLinkedList::add(int data) { // 当原列表仅有头结点时,直接插入新节点即可 if (head->pointer == NULL) { head->pointer = new Node; head->pointer->data = data; } // 当原列表头结点后面含有后继节点时 // 令头结点直接后继为新节点 // 并令新节点的直接后继为原来头结点的直接后继 else { // 临时存储头结点的直接后继 Node *temp = head->pointer; head->pointer = new Node; head->pointer->data = data; head->pointer->pointer = temp; } }
void SingleLinkedList::append(int data) { Node *current = head->pointer; // 找到列表的最后一个节点的位置current // current的指针域为NULL while (current->pointer!=NULL) { current = current->pointer; } // 令current的指针域指向新节点,完成插入 current->pointer = new Node; current->pointer->data = data; }
void SingleLinkedList::insert(int position, int data) { // 头插法 if (position <= 0) { add(data); } // 尾插法 else if (position > getLength()){ append(data); } else { // 令头指针所在的位置为0 int current_position = 0; Node *current = head; Node *prior = NULL; // 查找目标节点位置current,并记录其直接前驱节点piror while (current_position<position) { // 更新当前节点和直接前驱 prior = current; current = current->pointer; current_position++; } // 目标位置的直接前驱prior指向新节点 // 新节点指向目标位置的节点 prior->pointer = new Node; prior->pointer->data = data; prior->pointer->pointer = current; } };
int SingleLinkedList::getLength() { int counter = 0; Node *current = head; // 遍历链表,直到最后一个元素 while (current->pointer!=NULL) { counter++; current = current->pointer; } return counter; }
void SingleLinkedList::traversal() { Node *current; // 指向头结点的直接后继 current = head->pointer; int counter = 1; // 遍历链表,输出每个节点的值 while (current!=NULL) { printf("Element in %d is %d \n", counter, current->data); counter++; current = current->pointer; } }
int SingleLinkedList::search(int data) { int current_position = 1; Node *current = head->pointer; while (current!=NULL) { // 搜索成功返回当前位置 if (current->data == data) { return current_position; } // 继续更新位置; current = current->pointer; current_position++; } // 搜索失败,返回-1 return -1; }
void SingleLinkedList::remove(int data) { Node *current = head->pointer; Node *prior = head; // 遍历链表 while (current!=NULL) { // 查找到目标位置 if (current->data == data) { // 令目标位置的直接前驱指向目标节点的直接后继 prior->pointer = current->pointer; break; } // 更新当前节点和其前驱节点 prior = current; current = current->pointer; } }
感谢各位的阅读!关于“C++和python如何实现单链表”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。