当前位置：个人在线分享 > 线性表和链表

线性表和链表

作者 : admin 本文共4964个字，预计阅读时间需要13分钟 发布时间： 2024-06-10 共2人阅读

一，线性结构

1.Array

Array文档：可以自行阅读相关文档来了解Array

class array.array(typecode[, initializer])

线性表和链表插图 

 

array.append(x)：添加元素到数组末尾

array.count(x)：计算元素出现次数

array.extend(iterable)：将迭代器中的元素依次添加到数组末尾，不过要注意元素的类型要一致，要不然会抛出TypeError

array.fromfile(f, n)：读取文件中n个元素，如果文件中元素数量小于n，抛出EOFError，不过之前写入的数据仍然存在。

array.fromlist(list)：与上例差不多，相当于for x in list: a.append(x)，类型要一致。

array.fromstring(s)：与上例差不多。

array.index(x)：返回第一次元素出现的下标。

array.insert(i, x)：将元素x插入到i的位置上。

array.pop([i])：移除i下标的元素并且返回这个值，默认-1（最后一个）。

array.remove(x)：移除掉第一个x元素，不对后续x元素处理。

array.reverse()：反转数组。

array.tofile(f)：把数组内容写到文件中。

array.tolist()：把数组转化为列表，不改变内容。

array.tostring()：把数组转化为字符串。

array.tounicode()：和tostring差不多，但是要注意数组类型是’u’。要不然会抛出ValueError。

文档内容差不多就这些，大部分是写方法，加粗的为不常用的，还有一些方法会有些版本限制，稍微注意。

2.List实现Array部分功能

线性表和链表插图(1) 

3.代码实现

class Array():
    def __init__(self,size):
        self.__size = size
        self.__item = [None]*size
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, index):
        return self.__item[index]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value

    def remove(self,value):
       for i,ele in enumerate(self.__item):
           if ele == value:
               self.__item[i] = None
       return


if __name__ == '__main__':
    a1 = Array(10)
    a1[0] = 1
    a1[1] = 2
    a1[2] = 3
    a1[3] = 4
    a1.remove(2)

    for value in a1:
        print(value)

线性表和链表插图(2) 

 

二，链式结构

1.单链表

1.基本原理

和线性结构不同，链式结构内存不连续的，而是一个个串起来的，这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里可不要混淆了列表和链表（它们的中文发音类似，但是列表 list 底层其实还是线性结构，链表才是真的通过指针关联的链式结构）。 看到指针你也不用怕，这里我们用的 python，你只需要一个简单赋值操作就能实现，不用担心 c 语言里复杂的指针。

先来定义一个链接表的节点，刚才说到有一个指针保存下一个节点的位置，我们叫它 next， 当然还需要一个 value 属性保存值。

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

然后就是我们的单链表 LinkedList ADT:

class LinkedList(object):
    """ 链接表 ADT
    [root] -> [node0] -> [node1] -> [node2]
    """

线性表和链表插图(3) 

 

2.代码实现

class Node():
    def __init__(self,value=None,next=None):
        self.value = value
        self.next = next

    def __str__(self):
        return 'Node:{}'.format(self.value)


class LinkedList():
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.next = None#增加新数据时，将新数据地址与谁关联

    def append(self,value):
        node = Node(value)
        if not self.next:
            self.root.next = node
        else:
            self.next.next = node
        self.next = node
        self.size += 1

    def append_first(self,value):
        node = Node(value)
        if not self.next:
            self.root.next = node
            self.next = node
        else:
            temp = self.root.next
            self.root.next = node
            node.next = temp
        self.size += 1

    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.next:
                yield current
                current = current.next
            yield current
    def find(self,value):
        for n in self.__iter__():
            if n.value == value:
                return n
    def find_count(self,value):
        count = 0
        for n in self.__iter__():
            if n.value == value:
                count += 1
        return count

    def remove(self,value):
        prev = self.root
        for n in self.__iter__():
            if n.value == value:
                if n == self.next:
                    prev.next == None
                    self.next = prev
                prev.next = n.next
                del n
                self.size -= 1
                return True
            prev = n

    def remove_all(self,value):
        prev = self.root
        for n in self.__iter__():
            if n.value == value:
                if n == self.next:
                    prev.next == None
                    self.next = prev
                prev.next = n.next
                del n
                self.size -= 1
                continue
            prev = n






if __name__ == '__main__':
    link = LinkedList()
    link.append(11)
    link.append(11)
    link.append(11)
    link.append(14)
    link.append(15)
    link.append(16)
    for value in link:
        print(value)
    print(link.find(11))
    print(link.find_count(11))
    link.remove(16)
    for value in link:
        print(value)
    link.remove_all(11)
    print("--"*20)
    for value in link:
        print(value)

线性表和链表插图(4) 

2.双链表

上边我们亲自实现了一个单链表，但是能看到很明显的问题，单链表虽然 append 是 O(1)，但是它的 find 和 remove 都是 O(n)的， 因为删除你也需要先查找，而单链表查找只有一个方式就是从头找到尾，中间找到才退出。 我们需要在一个链表里能高效的删除元素， 并把它追加到访问表的最后一个位置，这个时候单链表就满足不了了。

1.基本原理

这里就要使用到双链表了，相比单链表来说，每个节点既保存了指向下一个节点的指针，同时还保存了上一个节点的指针。

class Node(object):
    def __init__(self, value=None, prev=None, next=None):
        self.value, self.prev, self.next = value, prev, next
  • 看似我们反过来遍历双链表了。反过来从哪里开始呢？我们只要让 root 的 prev 指向 tail 节点，不就串起来了吗？
  • 直接删除节点，当然如果给的是一个值，我们还是需要查找这个值在哪个节点？ – 但是如果给了一个节点，我们把它拿掉，直接让它的前后节点互相指过去不就行了？哇欧，删除就是 O(1) 了，两步操作就行啦

 

线性表和链表插图(5) 

 

2.代码实现

class Node():
    def __init__(self,value=None,prev=None,next=None):
        self.value = value
        self.next = next
        self.prev = prev
    def __str__(self):
        return "Node:{}".format(self.value)

class DoubleLinkedList():
    def __init__(self):
        self.size = 0
        self.root = Node()
        self.end = None

    def append(self,value):
        node = Node(value=value)
        #无节点
        if not self.end:
            self.root.next = node  # root节点指向新节点
            node.prev = self.root#新节点指向根节点
            self.end = node#末节点指针指向新节点


        #有节点
        else:
            self.end.next = node#末节点指向新节点
            node.prev = self.end  # 新节点指向末节点
            self.end = node#末节点移动到新节点
        self.size += 1

    def append_first(self,value):
        node = Node(value=value)
        #无节点
        if not self.end:
            self.root.next = node  # root节点指向新节点
            node.prev = self.root  # 新节点指向根节点
            self.end = node  # 末节点指针指向新节点
        else:
            node.prev = self.root#新节点指向根节点
            temp = self.root.next#保存原来的第一个节点
            self.root.next = node#将新节点替换为第一个节点
            node.next = temp#让新节点的下一个节点为原来的第一个节点
            temp.prev = node#将原来的第一个节点的上一个节点设置为新节点
        self.size += 1


    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current
                current = current.next
            return current
        else:
            print("LinkedList is empty")

    #逆向迭代
    def inverse_iter(self):
        current = self.end
        if current:
            while current is not self.root:
                yield current
                current = current.prev
        else:
            print("LinkedList is empty")

    def find(self,value):
        pass

    def find_count(self,value):
        pass

    def remove(self,value):
        pass

    def remove_all(self,value):
        pass

if __name__ == '__main__':
    link = DoubleLinkedList()
    link.append(11)
    link.append(12)
    link.append(13)
    link.append(14)
    link.append(15)

    gen = (link.inverse_iter())
    for value in gen:
        print(value)

 

本站无任何商业行为
个人在线分享 » 线性表和链表
admin

admin 钻石

分享到：

相关推荐

E-->