✨✨ 最近在重温数据结构的知识, 这篇blog主要写数据结构中的线性表, 记录自己用python实现这些数据结构以及对应的基本操作方法，方便今后回顾。
一 . 线性表定义:
零个或多个数据元素的有限序列;
二. 线性表的存储结构:
-
顺序存储 -- eg.数组List 、 元组Tupple
线性表的顺序存储结构, 是指用一段地址连续的存储单元依次存储线性表中的数据元素. 线性表是用数组来实现的, 支持随机存取,即访问元素的时间复杂度为O(1); 但是在操作插入和删除元素的时候，由于要满足地址的连续性，所以要移动很多的元素位置，因此，插入或者删除一个顺序表的元素的时间复杂度是O(n)。
-
链式存储 -- 链表(linked_list)
链表是指物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现的，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域链表失去了顺序表的随机存取特点，即每次从中取一个元素都要从头开始找，这样耗费了一些时间，查找的时间复杂度为O(n)；但是在做插入和删除的时候，就方便了很多，只需要做一点指针修改就可以了( O(1) )。
三. 数组
数组下标是从0开始的, 数组中存储的数据连续，支持快速随机访问。
(Python中list是封装好的数组, 可以直接使用)。
四. 单链表
单链表是链表的一种。链表由结点所构成, 结点包括存放数据元素的数据域和存放后继元素地址的指针域.
- python实现单链表
# -*- coding=utf-8 -*- # Python版本实现的单链表 class Node(object): def __init__(self, item): self.item = item # item存放的是数据元素 self.next = None # next指向下一元素的地址 ''' get_length() 获取链表长度; is_empty() 判断链表是否为空 travel() 遍历整个链表 insert(index, value) 指定位置添加元素 remove(value) 删除结点 ''' class Single_linked_list(object): def __init__(self, node = None): self.head = None # 头部 def get_length(self): '''获取链表长度''' length = 0 cur = self.head while cur != None: length += 1 cur = cur.next return length def is_empty(self): '''判断链表是否为空''' if self.head == None: return True else: return False def travel(self): '''遍历链表''' cur = self.head while cur != None: print(cur.item) cur = cur.next def insert(self, index, value): '''指定位置添加元素''' if index < 0 or index > self.get_length(): print('error index') elif index == 0: # 在头部插入结点 node = Node(value) cur = self.head node.next = cur self.head = node else: cur = self.head # 用来指向index-1 的位置，初始从头结点开始移动到指定位置 count = 0 node = Node(value) # 初始化要插入的值 while count < index - 1: count += 1 cur = cur.next node.next = cur.next # 先将新节点node的next指向插入位置的节点 cur.next = node # 再将插入位置的前一个节点的next指向新节点 def remove(self, index): '''删除指定下标的结点''' if index < 0 or index >= self.get_length()-1: print('Wrong index') elif self.is_empty(): print('No node exists') elif index == 0: cur = self.head self.head = cur.next elif index == self.get_length(): cur = self.head for i in range(self.get_length()-2): cur = cur.next cur.next = None else: cur = self.head for i in range(index -1): cur = cur.next cur.next = cur.next.next if __name__ == "__main__": obj = Single_linked_list() obj.insert(0,2) obj.insert(1,5) obj.insert(2,4) obj.travel() print('------') obj.remove(1) obj.travel()
五. 顺序表与链表的对比
<总结>:
- 若线性表需要频繁查找, 很少进行插入和删除操作时, 宜采用顺序存储结构.
- 对于插入和删除数据越频繁的操作, 单链表的优势就越是明显.
- 当线性表中元素个数变化比较大时, 最好用单链表结构, 这样可以不考虑存储空间大小的问题.
文章来源: 博客园
客服
