python3 数据结构 线性表

定义

线性表的定义是描述其逻辑结构，而通常会在线性表上进行的查找、插入、删除等操作。

线性表作为一种基本的数据结构类型，在计算机存储器中的映象（或表示）一般有两种形式，一种是顺序映象，一种是链式映象。

线性表的顺序存储

1.定义：若将线性表L=(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间，这种机制表示为线性表的顺序存储结构。

2.特点：

逻辑上相邻的元素 ai, ai+1，其存储位置也是相邻的；存储密度高，方便对数据的遍历查找。对表的插入和删除等运算的效率较差。

3.程序实现

在Python中，list存放于一片单一连续的内存块，故可借助于列表类型来描述线性表的顺序存储结构，而且列表本身就提供了丰富的接口满足这种数据结构的运算。

L = [1,2,3,4] L.append(10) #尾部增加元素 #[1, 2, 3, 4, 10] L.insert(1,20) #插入元素 #[1, 20, 2, 3, 4, 10] L.remove(3) #删除元素 #[1, 20, 2, 4, 10] L[4] = 30 #修改 #[1, 20, 2, 4, 30] L.index(2) #查找 #2

线性表的链式存储

1.定义：将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块，称为结点，每个结点（尾节点除外）中都持有一个指向下一个节点的引用，这样所得到的存储结构为链表结构。

2.特点

逻辑上相邻的元素 ai, ai+1，其存储位置也不一定相邻；存储稀疏，不必开辟整块存储空间。对表的插入和删除等运算的效率较高。逻辑结构复杂，不利于遍历。

3.程序实现

class Node(self,data,next=None): self.data = data self.next = next class Linklist(): def __init__{self}: self.head = Node(None) def linklist(self,list1): # p = self.head for i in list1: p.next = Node(i) p = p.next def show_link(self): # p = self.head.next while p is not None: print(p,end=" ") p = p.next print() def get_length(self): # p = p.head n=0 while p.next is not None: n += 1 p = p.next return p def empty(self): if self.get_length() == 0: return True else: return False def clear(self): self.head.next = None def add_link(self,data): node = Node(data) p = self.head.next while p is not None: p = p.next p = node def insert(self,index,data): if index<0 or index>self.get_length(): return IndexError("index out of range") p = self.head.next for i in range(index): p = p.next node = Node(data) node.next = p.next p.next = node def del_node(self,data): p = self.head while p.next and p.next.data != data: p = p.next if p.next == None: raise ValueError("value is error") else: p.next = p.next.next def get_data(self,index): if index<0 or index>self.get_length(): return IndexError("index out of range") p = self.head.next for i in range(index): p = p.next return p.data