亲宝软件园·资讯

展开

C++,python单链表

机器学习入坑者 人气:0

一、链表的基本概念

链表是数据元素的线性集合(Linear Collection),物理存储不连续。那么,这种设计的优点是什么?缺点又是什么?

链表的基本结构:

链表是由一系列的“节点”组成在一起的集合,节点(Node)由数据域(data)和指针域(next)组成。

从功能上看,data负责存储数据,next负责存储下一个节点的位置。当然,用更加严格的语句来讲,next存储的是其直接后继的地址,关于直接后继的定义见:

链表的分类:

常见的链表种类有:单向链表、双向链表、单向循环链表、双向循环链表,将会在后面文章中单独介绍各种链表的结构和代码实现,以及对应的链表操作。

链表的基本操作:

链表的基础操作包含:插入、删除、查找、合并等,此外还有:反转、排序、深度复制等。

链表的优点:

链表的缺点:

二、单链表

基本结构:

单链表的结构含有四个概念:头指针、头结点、普通Node、尾结点,下面分别介绍:

单链表的基本操作:

针对单链表常见的操作有:增、改、查、删等,

常用的操作如下:

(1)增

对链表添加元素一般有三种方法:头插法(add)、尾插法(append)、任意位置插入法(insert)。

(2)改

改动链表中某个节点的data

(3)查

查找分为按值查找和按位置查找两种,前者表示按照值查找对应位置,后者表示按位置查找对应值;

(4)删

删除分为按值删除和按位置删除两种;前者表示按照值删除对应节点,后者表示按照位置删除对应节点;

实现说明:

按照自己目前所看的资料,一般都会实现下面介绍的这些函数,具体介绍放在python和C++实现中。

1.python实现

(1)节点设计

按照单链表的定义可知,节点包含数据域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

(2)链表类:Single_Linked_List

上述Node类对象即为链表的基本组成结构,可以用于实现头结点、普通节点和尾结点。

因此,链表类只需要提供头指针:

class Single_Linked_List:
    def __init__(self, node=None):
        self.__head = node

(3)判断链表是否为空:is_empty()函数

实际上,只需要判断头指针是否指向Node类对象(或是否等于None),就可判断一个链表是否为空:

def is_empty(self):
    """判断链表是否为空"""
    if self.__head == None:
        return True
    else:
        return False

(4)头插法:add()函数

在链表头进行节点插入是很常见的插入操作,这种方式使得“先插入的节点在链表尾部”。头插法需要将头指针指向新的节点,并让新的节点指向原来的头结点:

def add(self, data):
    """Add dnode into head
    """ 
    # 创建新节点
    node = Node(data)
    # 令新的节点指向原来的头结点
    node.pointer = self.__head
    # 令头指针指向新的节点
    self.__head = node

(5)尾插法:append()函数

如果想要链表节点次序和插入次序相同,就需要使用尾插法。在插入之前需要判断链表是否为空,如果不为空才能进行插入(可以调用前面定义的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

(6)在任意位置插入:insert()函数

前面介绍的头插法和尾插法,其原理相对简单,但是并不能完全满足插入需求。如果知道目标插入的位置,可以采用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

(7)计算链表长度:get_length()函数

对于调用者和类内部的其它函数来做,链表长度是一个非常有用的值。比如在插入函数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

(8)遍历所有节点:traversal()函数

链表、树、图等结构都需要遍历操作,其中链表的遍历比较简单,只需要依次的访问所有节点即可。

def traversal(self):
    current = self.__head
    i = 0
    # 循环结束的条件依旧是节点的pointer指向不为空
    while current !=  None:
        print("Element {} is {} ".format(i, current.data))
        current = current.pointer
        i += 1

(9)搜索:search()函数

前面提到搜索有按值搜索和按位置搜索两种,它们的原理和实现都十分相似,所以仅以按值搜索为例。

需要注意的是,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

(10)删除:delete()函数

上述的查找中以“按值查找”为例,这次删除中同样以“按值删除”为例,“按位置删除”的实现与之类似。

按值删除,即删除目标值对应的目标节点。在进行遍历时,需要记录当前节点和当前节点的前一个节点。因为,一旦查找大目标值所在的目标节点,需要令目标节点的前一个节点指向目标节点的下一个节点,即完成节点的删除。

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   

2.C++实现

前面的python实现中已经分析了各个函数的作用,以及对应的实现过程。虽然python和C++的语法不同,但是核心过程是类似的,所以下面不再重复对过程的叙述。

(1)节点设计

由于C++的指针必须指定类型,所以需要使用空指针NULL作为pointer的值。

class Node{
public:
    int data;
    Node *pointer=NULL;
};

(2)链表类:SingleLinkedList

遵循声明和实现分类的策略,先对各个函数进行声明。

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;
};

(3)判断链表是否为空:isEmpty()函数

bool SingleLinkedList::isEmpty() {
    // 头结点不指向任何结点,为空
    if (head->pointer == NULL) {
        return true;
    }
    else {
        return false;
    }
}

(4)头插法:add()函数

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;
    }
}

(5)尾插法:append()函数

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;
}

(6)在任意位置插入:insert()函数

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;
    }
};

(7)计算链表长度:getLength()函数

int SingleLinkedList::getLength() {
    int counter = 0;
    Node *current = head;
    // 遍历链表,直到最后一个元素
    while (current->pointer!=NULL)
    {
        counter++;
        current = current->pointer;
    }
    return counter;
}

(8)遍历所有节点:traversal()函数

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;
    }
}

(9)搜索:search()函数

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;
}

(10)删除:remove()函数

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;
    }
}

总结:

在使用python实现时,头结点数据域data是有效的。这种方式使得代码中需要很多的“if-else”判断结构,增加了代码的复杂性。

在使用C++实现时,头结点数据域data是无效的,这种方式使得代码更加简洁。

加载全部内容

相关教程
猜你喜欢
用户评论