数据结构（python）-----顺序表，链表_用python来编写一个数据结构的顺序表和链表

数据结构（python）

一、数据结构引入

顺序表：按照顺序将同种类型的数据存储起来，查找的时候根据第一个数据的物理地址得到查找数据的物理位置
L0+索引*数据位数

二、顺序表

1.基本顺序表与元素外围顺序表

顺序表：列表中元素类型相同，列表中的元素是连续存储的，每个存储单元有一个地址号。查询时按照地址号查询。
元素外围顺序表：类表中元素类型不同，每个元素占的空间大小不同，所以给每个元素先申请一个地址空间，然后把她们对应的地址空间按顺序存储起来，每个地址作为存储单元也有一个地址号。查询时先查找到地址，在按照地址去找对应的元素。

2.顺序表的结构与实现

1）.顺序表结构

2）.元素存储区替换

一体式和分离式的区别：
当列表增加元素时

3）.元素存储区扩充

三、链表

链表的实现方式：吧数据分为两部分：数据区和链接区
链表的作用：可以将内存中所有分散的碎片内存用起来

数组和链表区别

链表基础：https://blog.csdn.net/weixin_44568633/article/details/104569283

1.数组在内存中的地址是连续相邻的，而链表在内存的地址是散列的，不连续的。
2.数组可以快速查找，链表可以快速插入和删除。

数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

li=[200,400,600]
分别用三个地址空间存储200，400，600
然后在200存储区域后面在用一块地方来指向400的存储空间，600同样，这样就用一跟线将200，400，600链接起来了。

1.单项链表

线性表描述的时怎么存放，栈描述的是怎么操作

2.单链表的操作

3.python中变量标识的本质

本质：指向对应的地址空间
10找一个地址空间存储起来，a是一个内存，存储10所对应的地址。
20找一个地址空间存储起来，b是一个内存，存储20所对应的地址。
a,b=b,a即改变a和b的地址空间指向。


变量a也可以指向一个函数或者一个类的地址。
紫色是节点的使用方法：一个数据元素和一个链接区。

4.单链表和节点的定义代码

当我们实例化一个单链表对象时，第一个节点指向为空；
在实例化一个节点对象，
让单链表对象指向节点对象，在往后面append其他节点，就形成了单链表。

头插法 add()：
思想：
1.实例化一个node节点；（然后按照2.3.执行，如果3.2.顺序会使head后面的链表丢失）
2.节点的链接区node.next指向原头部指向的链表；
3.链表头部head指向节点node

insert()
思想：
1.创建一个游标pre，作用同cur，用游标遍历链表
2.当游标指向（pos-1）索引时，退出循环
3.创建一个节点node，使节点的链接区指向pre.next，游标pre指向节点node

remove：
删除元素的思想：
创建两个游标，pre指向None，代表cur的前一个游标，cur指向self.__head
循环遍历节点，当游标cur指向要删掉的节点，即cur.elem=item(要删掉的节点)时，使pre的下一节点为cur的下一个节点，即pre.next=cur.next

游标往后循环遍历的思想（pre和cur同时后移）：
pre指向cur，即pre=cur
cur指向cur的下一个元素，即cur=cur.next

情况1：删掉中间的节点
情况2：删除的元素是头节点：self.__head=cur.next
情况3：

或者尾节点

"""
一：创建一个链表对象  此时head为空，没有指向任何node
二：创建一个节点对象，存入数据与数据的地址
三：链表对象的head指向第一个节点的数据地址
四：剩下数据继续创建节点串到链表中
"""

class Node(object):
    def __init__(self,elem,next=None):
        self.elem=elem #指向节点数据区
        self.next=next #指向节点链接区
class Singlelinklist(object): #类表示一个数据类型，实例化一个对象才是具体的值，因此保存头节点属于对象属性，且一旦实例化对象就应该先去保存头节点。
    '''
    单链表
    类表示一个数据类型，实例化一个对象才是具体的值，因此保存头节点属于对象属性，且一旦实例化对象就应该先去保存头节点。
    '''
    def __init__(self,node=None): #指向第一个节点，默认为空表示此链表为空链表
        self.__head=node
    def is_empty(self):
        return self.__head==None
    def le
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20