顺序表与单链表

用户3577892

发布于 2021-02-23 15:10:30

9460

发布于 2021-02-23 15:10:30

文章被收录于专栏：数据科学CLUB

顺序表
Python顺序表中基本操作的实现
- list其他操作
- list内置操作的时间复杂度
单链表
python单链表基本操作的实现
- 单个节点实现
- 单链表的实现
顺序表与单链表的对比

顺序表

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequent ial List

)_{\circ}

其特点是, 逻辑上相邻的数据元素，其物理次序也是相邻的。假设线性表的每个元素需占用

个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。则线性表中第

i+1

个数据元素的存储位置

\operatorname{LOC}\left(a_{i+1}\right)

和第

个数据元素的存储位置 LOC

\left(a_{i}\right)

之间满足下列关系：

\operatorname{LOC}\left(a_{i+1}\right)=\operatorname{LOC}(a_{i})+l

一般来说，线性表的第

个数据元素

a_{i}

的存储位置为：

\operatorname{LOC}(q)=\operatorname{LOC}(q)+(i-1) \times l

a = [1,2,3,4,4,5]

id(a[1])-id(a[0])

id(a[2])-id(a[1])

id(a[0]) + 32*3 == id(a[3])

True

Python顺序表中基本操作的实现

Python的 list 和 tuple采用了顺序表的实现技术,具有顺序表的所有性质

初始化

顺序表的初始化操作就是构造一个空的顺序表。

alist = []

取值

取值操作是根据指定的位置序号i，获取顺序表中第i个数据元素的值。由于顺序存储结构具有随机存取的特点，可以直接通过数组下标定位得到,elem[i-1]单元存储第i个数据元素。

时间复杂度为

\mathrm{O}(1)

a[2]

查找

查找操作是根据指定的元素值e，查找顺序表中第1个与e相等的元素。若查找成功，则返回该元素在表中的位置序号;若查找失败，则返回0。

平均时间复杂度为

\mathrm{O}(n)

a.index(4)

插入

线性表的插入操作是指在表的第

个位置插人一个新的数据元素

, 使长度为

的线性表

\left(a_{1}, \cdots, a_{i-1}, a_{i}, \cdots, a_{n}\right)

变成长度为

n+1

的线性表

\left(a_{1}, \cdots, a_{i-1}, e, a_{i} ;, q\right)

一般情况下，在第

i(1 \leqslant i \leqslant n)

个位置插入一个元素时，需从最后一个元素即第

个元素开始，依次向后移动一个位置，直至第

个元素（共

n-i+1

个元素 )。

顺序表插入算法的平均时间复杂度为

\mathrm{O}(n)_{\circ}

Python中有多种方法向表中插入某一元素

[1, 2, 3, 4, 4, 5]

# 在列表尾部添加一个对象
# 官方：same as s[len(s):len(s)] = [x]
a.append(0)
a

[1, 2, 3, 4, 4, 5, 0]

# 在列表尾部添加一个序列
# 官方：same as s[len(s):len(s)] = t
a.extend([9])
a

[1, 2, 3, 4, 4, 5, 0, 9]

# 在指定位置插入元素
a.insert(2,8)
a

[1, 2, 8, 3, 4, 4, 5, 0, 9]

a.pop(2)

删除

线性表的删除操作是指将表的第

\mathrm{i}

个元素删去，将长度为

的线性表

\left(a_{1}, \cdots, a_{i-1}, a_{i}, a_{i+1}, \cdots, a_{n}\right)

变成长度为

n-1

的线性表

\left(a_{1}, \cdots, a_{i-1}, a_{i+1}, \cdots, a_{n}\right)

一般情况下, 删除第

i(1 \leqslant i \leqslant n)

个元素时需将第

i+1

个至第

个元素（共

n-i

个元素 ) 依次向前移动一个位置

(i=n \text { 时无需移动 })_{\circ}

顺序表删除算法的平均时间复杂度为

\mathrm{O}(n)

# 从a中删除a[i]等于x的第一项
a.remove(4)
a

[1, 2, 8, 3, 4, 5, 0, 9]

# 返回i处的元素值，并将其从a中删除
a.pop(-1)
a

[1, 2, 8, 3, 4, 5, 0]

list其他操作

b = [1,2,3,4,4]
len(b)

min(b)

max(b)

b.count(4)

5 in b

False

2 in b

True

# 反转
b.reverse()
b

[4, 4, 3, 2, 1]

# 删除某几项
del b[1:3]
b

[4, 2, 1]

# 清空
b.clear()
b

[]

list内置操作的时间复杂度

单链表

线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的

)_{\circ}

因此，为了表示每个数据元素

a_{i}

与其直接后继数据元素

a_{i+1}

之间的逻辑关系，对数据元素

a_{i}

来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置

)_{\circ}

这两部分信息组成数据元素

a_{i}

的存储映像，称为结点( node )。它包括两个域：其中存储数据元素信息的域称为数据域; 存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。

个结点（

a_{i}(1 \leqslant i \leqslant n)

的存储映像 ) 链结成一个链表，即为线性表

\left(a_{1}, a_{2}, \cdots, a_{n}\right)

示意图

python单链表基本操作的实现

单个节点实现

class LNode(object):
    def __init__(self,elem,next = None):
        self.elem = elem
        self.next = next

单链表的实现

单链表的初始化

class SingleLinkList(object):
    def __init__(self):
        self.__head = None
#         头结点的指针域置空

判断链表是否为空

def is_empty(self):
    return self.__head == None

链表长度

def length(self):
# p初始时指向头节点
    p = self.__head
    count = 0
# 尾节点指向None，当未到达尾部时
    while p != None:
        count += 1
#     将cur后移一个节点
        p = p.next
    return count

取值

和顺序表不同，链表中逻辑相邻的结点并没有存储在物理相邻的单元中，这样，根据给定的结点位置序号i'在链表中获取该结点的值不能像顺序表那样随机访问，而只能从链表的首元结点出发，顺着链域 next 逐个结点向下访问。

单链表取值算法的平均时间复杂度为

\mathrm{O}(n)

def get_elem(self,i):
#     p为扫描指针
    p = self.__head
    while p != None and 0<i<self.length():
        i -= 1
        p = p.next
    return p.elem

查找

链表中按值查找的过程和顺序表类似，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。

其平均时间复杂度也为

\mathrm{O}(n)_{\circ}

def loc_elem(self,elem):
    p = self.__head
    while p != None:
        if p.elem == elem:
            return True
        else:
            p = p.next
    return False

插入

假设要在单链表的两个数据元素a和b之间插入一个数据元素x, 已知p为其单链表存储结构中指向结点a的指针

步骤：

查找结点

a_{i-1}

并由指针

指向该结点。

生成一个新结点*s。
将新结点*s 的数据域置为 e。
将新结点*s 的指针域指向结点 a

_{i}

将结点p 的指针域指向新结点s。

时间复杂度为

\mathrm{O}(n)

def insert(self, pos, elem):
    node = LNode(elem)
    count = 0
# p用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
    p = self.__head
    while count < (pos-1):
        count += 1
        p = p.next
# 先将新节点node的next指向插入位置的节点
    node.next = p.next
# 将插入位置的前一个节点的next指向新节点
    p.next = node

删除

要删除单链表中指定位置的元素，同插人元素一样，首先应该找到该位置的前驱结点。如图所示，在单链表中删除元素b时，应该首先找到其前驱结点a。为了在单链表中实现元素a、b和c之间逻辑关系的变化,仅需修改结点a中的指针域即可。假设p为指向结点a的指针，则修改指针的语句为

p->n e x t=p->n e x t->n e x t

时间复杂度为

\mathrm{O}(n)

# 按值删除
def remove_1(self, elem):
    cur = self.__head
    pre = None
    while cur != None:
        if cur.elem == elem:
#             先判断此结点是否是头节点
#             头节点
            if cur == self.__head:
                self.__head = cur.next
            else:
                pre.next = cur.next
            break
        else:
            pre = cur
            cur = cur.next
            
# 按位置删除

def remove_2(self,i):
    p = self.__head
    count = 0
    while p != None:
        if count != i-1:
            p = p.next     
            count += 1
        else:
            p.next = p.next.next
        break

创建单链表

头插法

(1) 创建一个只有头结点的空链表。

(2) 根据待创建链表包括的元素个数

, 循环

次执行以下操作:

生成一个新结点*p;
输入元素值赋给新结点*p 的数据域;
将新结点*p 插人到头结点之后。

尾插法

(1) 创建一个只有头结点的空链表。

(2) 尾指针 r 初始化，指向头结点。

(3) 根据创建链表包括的元素个数

, 循环

次执行以下操作:

生成一个新结点*p;
输入元素值赋给新结点*p 的数据域;
将新结点p 插入到尾结点r之后;
尾指针 r 指向新的尾结点*p。。

# 头插法
def add(self, elem):
#     先创建一个保存item值的节点
    node = LNode(elem)
#     将新节点的链接域next指向头节点，即__head指向的位置
    node.next = self.__head
#     将链表的头_head指向新节点
    self.__head = node

# 尾插法
def append(self, elem):
    node = LNode(elem)
    # 先判断链表是否为空，若是空链表，则将_head指向新节点
    if self.is_empty():
        self.__head = node
    # 若不为空，则找到尾部，将尾节点的next指向新节点
    else:
        p = self.__head
        while p.next != None:
            p = p.next
        p.next = node