python线性表

顺序表

顺序表，将元素顺序地存放在一块连续的存储区里，元素间的顺序关系由它们的存储顺序自然表示。

数据元素本身连续存储，每个元素所占的存储单元大小固定相同，元素的下标是其逻辑地址，而元素存储的物理地址（实际内存地址）可以通过存储区的起始地址Loc (e0)加上逻辑地址（第i个元素）与存储单元大小（c）的乘积计算而得，即：Loc(ei) = Loc(e0) + c*i，时间复杂度为O(1)。
如果元素的大小不统一，则须采用图b的元素外置的形式，将实际数据元素另行存储，而顺序表中各单元位置保存对应元素的地址信息（即链接）
顺序表完整信息=元素集合+整体情况信息【元素个数+容量】
顺序表的两种实现方式：

一体式：完整信息在一个表中
分离式：表中只存整体情况信息，外链实际元素集合；动态顺序表：容量可以在使用中动态变化
顺序表的操作：增加和删除，各分为尾部O(1)、非保序O(1)、保序O(n)
python中list和tuple，更多是用list，分离式技术实现的动态顺序表
ist实现采用了如下的策略：在建立空表（或者很小的表）时，系统分配一块能容纳8个元素的存储区；在执行插入操作（insert或append）时，如果元素存储区满就换一块4倍大的存储区。但如果此时的表已经很大（目前的阀值为50000），则改变策略，采用加一倍的方法。引入这种改变策略的方式，是为了避免出现过多空闲的存储位置。
单向链表

创建一个链表中的节点类(item,next)
class Node():
    def __init__(self,item):#节点初始条件有值
        self.item=item
        self.next=None

#创建链表的类
class SingleLink():
    #初始化，给定链表的头部属性
    def  __init__(self,node=None):
        self.__head=node
    #判断链表是否为空，即判断链表的head指针是否指向空
    def is_empty(self):
        return self.__head==None #为None返回True，不为None，False


    #判断链表的长度
    def length(self):
        if self.is_empty():
            return 0
        else:
            currentnode=self.__head #代表currentnode指向当前节点的游标与head指针指向同一个节点
            lengthcount=1#对比注释部分另一个方法，lengthcount=0
            while currentnode.next!=None:
                lengthcount+=1
                currentnode=currentnode.next
            return lengthcount


    #遍历整个链表
    def travel(self):
        if self.is_empty():
            return None
        else:
            allitemlist = []
            currentnode = self.__head
            allitemlist.append(currentnode.item)#先加入第一个
            while currentnode.next != None:
                currentnode = currentnode.next#尽管最后一个currentnode.next==None,但已经加入过
                allitemlist.append(currentnode.item)
            return allitemlist


    #链表头部加入元素
    def add(self,newitem):
        newnode = Node(newitem)
        if self.is_empty():
            self.__head = newnode
        else:
            newnode.next = self.__head
            self.__head = newnode




    #尾部添加元素,需要判断是否为空
    def append(self,newitem):
        newnode=Node(newitem)
        if self.is_empty():#类之间的函数调用用self.func
            self.__head = newnode
        else:
            currentnode=self.__head
            while currentnode.next!=None:
                currentnode=currentnode.next
            currentnode.next = newnode




    #指定位置添加元素，根据位置分为头部添加，尾部添加，中间位置添加，中间位置添加时需找到添加位置的前一个节点
    def insert(self,position,newitem):
        if position <=0:
            self.add(newitem)
        elif position >= self.length():#大于等于链表长度
            self.append(newitem)
        else:
            currentnode=self.__head
            positioncount=0
            newnode=Node(newitem)
            while positioncount<(position-1):#currentnode为插入位置前一个的节点
                currentnode=currentnode.next
                positioncount+=1
            newnode.next=currentnode.next
            currentnode.next=newnode





    #删除节点，再循环条件内查找
    def remove(self,item):
        currentnode = self.__head
        prenode = None
        while currentnode!=None:  # 判断是否找到
            if currentnode.item == item:  # 找到删除的值对应的节点
                if prenode == None:  # 如果前一个节点为空，则当前节点为第一个节点
                    self.__head = currentnode.next
                else:
                    prenode.next = currentnode.next
                break#注意break
            else:
                prenode = currentnode  # 将当前节点给前一个节点
                currentnode = currentnode.next  # 当前节点为其next的指向
        # 如果找到，判断curentnode是否为第一个节点


    #查找节点
    def search(self,item):
        currentnode=self.__head
        Found=False
        while not Found and currentnode!=None:#此处是currentnode，最后一个值也可找
            if currentnode.item==item:
                 Found=True
            else:
                currentnode=currentnode.next
        return Found






    #更新链表某个位置的值
    def update(self,position,newitem):
        if (position<0) or (position>self.length()):
            return False
        else:
            currentnode=self.__head
            positioncount=0
            while positioncount<position:
                currentnode=currentnode.next

                positioncount+=1
            currentnode.item=newitem




    #清空链表
    def clear(self):
        self.__head=None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

单向循环链表

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

class SingleCircleLink():
    def __init__(self,node=None):
        self.__head=node


    #判断链表是否为空
    def is_empty(self):
        if self.__head==None:
            return True


    #返回链表的长度
    def length(self):
        if self.is_empty():#判断是否为空
            return 0
        else:
            currentnode=self.__head
            lengthcount=1
            while currentnode.next!=self.__head:
                lengthcount+=1
                currentnode=currentnode.next
        return lengthcount

    #遍历整个链表
    def travel(self):
        if self.is_empty():
            return None
        else:
            allitemlist = []
            currentnode=self.__head
            allitemlist.append(currentnode.item)
            while currentnode.next!=self.__head:
                currentnode=currentnode.next
                allitemlist.append(currentnode.item)
            return allitemlist

    #在头部添加一个节点
    def add(self,newitem):
        newnode=Node(newitem)
        if self.is_empty():
            self.__head=newnode
            newnode.next=self.__head#此句是将新插入节点的next指向头部，实现单向循环
        else:
            currentnode=self.__head#currentnode用来找尾节点
            while currentnode.next!=self.__head:
                currentnode=currentnode.next
            newnode.next=self.__head
            currentnode.next=newnode#将尾部节点的next连接到newnode
            self.__head=newnode#将head指针给newnode


    #在尾部添加一个节点
    def append(self,newitem):
        newnode=Node(newitem)
        if self.is_empty():
            self.__head = newnode
            newnode.next = self.__head#此句是将新插入节点的next指向头部，实现单向循环
        else:
            currentnode = self.__head  # currentnode用来找尾节点
            while currentnode.next != self.__head:
                currentnode = currentnode.next
            currentnode.next=newnode
            newnode.next=self.__head



    #在任意位置添加一个节点
    def insert(self,position,newitem):
        newnode=Node(newitem)
        if position <=0:
            self.add(newitem)
        elif position >= self.length()-1:
            self.append(newitem)
        else:
            currentnode=self.__head
            positioncount=0
            while positioncount<(position-1):#注意此时的currrentnode指向的插入位置的前一个节点
                currentnode=currentnode.next
                positioncount+=1
            newnode.next=currentnode.next
            currentnode.next=newnode


    #删除一个节点
    def remove(self,item):
        if self.is_empty():
            return 0
        else:
            currentnode=self.__head
            prenode=None
            while  currentnode.next!=self.__head:#因为循环为currentnode.next,所以需单独考虑最后一个节点的匹配情况，如110所示
                if currentnode.item==item:
                    if prenode == None:  # 删除的是第一个节点
                        searchnode = self.__head
                        self.__head = currentnode.next
                        while searchnode.next != self.__head:
                            searchnode = searchnode.next
                        searchnode.next = self.__head  # 替换最后一个节点的__head值
                    else:
                        prenode.next = currentnode.next  # 还没到最后一个节点
                    break
                else:
                    prenode=currentnode
                    currentnode=currentnode.next
            if currentnode.item==item:#考虑最后一个节点
                if currentnode==self.__head:#如果最后一个节点是头节点，则链表为空
                    self.__head=None
                else:
                    prenode.next=self.__head#其他更改前一个prenode.next指向head


    #查找一个节点
    def search(self,item):
        if self.is_empty():
            return False
        else:
            currentnode=self.__head
            if currentnode.item == item:#放在外面，相当于currentnode.next=self.__head也进行了判断，避免了最后一个元素无法判断
                return True
            else:
                while currentnode.next!=self.__head:
                    currentnode=currentnode.next
                    if currentnode.item==item:
                        return True
            return False



    #更新链表某个位置的值,索引从0开始
    def update(self,position,newitem):
        if (position<0) or (position>self.length()):
            return False
        else:
            currentnode=self.__head
            positioncount=0
            while positioncount<position:
                currentnode=currentnode.next
                # currentnode=currentnode.getnext()
                positioncount+=1
            currentnode.item=newitem

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

双向链表 pre\next

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


class DoubleLink():
    def __init__(self,node=None): #可以先构造一个node=Node(100)
        self.__head=node


    #判断是否为空
    def is_empty(self):
        return self.__head==None

   #判断长度
    def length(self):
        if self.is_empty():
            return 0
        else:
            currentnode=self.__head
            lengthcount=1#注意此处为1,为0时不需要判断为空的情况
            while currentnode.next!=None:
                lengthcount+=1
                currentnode=currentnode.next
            return lengthcount

    #遍历链表
    def travel(self):
        if self.is_empty():
            return None
        else:
            allitemlist=[]
            currentnode=self.__head
            allitemlist.append(currentnode.item)
            while currentnode.next!=None:
                currentnode=currentnode.next
                allitemlist.append(currentnode.item)
            return allitemlist

    #头部添加
    def add(self,newitem):
         newnode=Node(newitem)
         self.__head.pre=newnode
         newnode.next = self.__head
         self.__head = newnode
         # newnode.next.pre = newnode  # 此为双向链表增加的，新增节点的next指向的节点的pre为新增的节点


    #尾部添加
    def append(self,newitem):
        newnode=Node(newitem)
        if self.is_empty():
            self.__head=newnode

            # newnode.pre=None 等于None不需要改变就为默认
            # newnode.next=None
        else:
            currentnode=self.__head
            while currentnode.next!=None:
                currentnode=currentnode.next
            currentnode.next=newnode
            newnode.pre=currentnode#新增的
            # newnode.next=None 等于None不需要改变就为默认


    #任意位置添加
    def insert(self,position,newitem):
        if position <=0:
            self.add(newitem)
        elif position >= self.length():
            self.append(newitem)
        else:
            positioncount=0
            newnode=Node(newitem)
            currentnode=self.__head
            while positioncount <(position-1):#要插入位置的前一个
                currentnode=currentnode.next
                positioncount+=1
            #在currentnode后插入
            newnode.next = currentnode.next
            newnode.pre=currentnode
            currentnode.next.pre=newnode
            currentnode.next = newnode


    #删除某一元素
    def remove(self,item):
        currentnode=self.__head
        Found=False
        while  currentnode!=None:
            if currentnode.item==item:
                if currentnode.pre == None:  # 若果删除的是第一个
                    self.__head = currentnode.next
                elif currentnode.next == None:  # 如果删除的是最后一个
                    currentnode.pre.next = currentnode.next
                else:  # 如果是中间，因为此处有pre属性，所以相比之前，后两种不能合并
                    currentnode.pre.next = currentnode.next
                    currentnode.next.pre = currentnode.pre
                break
            else:
                currentnode=currentnode.next



    #查找某一个元素
    def search(self,item):
        currentnode=self.__head
        Found=False
        while not Found and currentnode!=None:
            if currentnode.item==item:
                Found= True
            else:
                currentnode=currentnode.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116