python实现线性表_python线性表安装

线性表的定义

线性表是具有相同数据类型的n(n.>=0)个数据元素的有限序列，其中n为表长，n=0时表示该表是一个空表，一般表示为：
L=(a1,a2…an-1,an)
逻辑特性：a1是表头元素，an是表尾元素，除了表头元素，每个元素有且仅有一个直接前驱，除了表尾元素，每个元素有且仅有一个直接后继。
线性表的特点：
–表中元素个数有限。
–表中元素具有逻辑上的顺序性，在序列中各元素排列有其先后次序。
–表中元素都是数据元素，每个元素都是单个元素。
–表中元素的数据类型都相同，即每个元素占用的存储空间大小相同。
线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是存储结构，两者属于不同层次的概念。

顺序表

线性表的顺序存储结构，使用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，即顺序表的逻辑顺序与其物理顺序相同。
下图是C语言表示的顺序表，sizeof()用于计算元素所占存储空间。

顺序表有两种实现方式：

图a 为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。一体式结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。

图b 为分离式结构，表对象里只保存与整个表有关的信息（容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。
在Python官方实现中，list就是一种采用分离式技术实现的动态顺序表,使用list进行插入删除，不需要像C语言一样对该元素后面元素依次移动，简单的代码实现：

class mysqlist():
    def __init__(self,size):
        self.size=size
        self.sqlist=[]
    def listinsert(self,i,x):
        if i<1 or i>self.size:
            print("Insert Location Error！")
            return False
        else:
            self.sqlist.insert(i,x)
            return True
    def listdelete(self,i):
        if i<1 or i>self.size:
            print("Delete Location Error！")
            return False
        else:
            self.sqlist.pop(i)
            return False
    def findelem(self,i):
        if i<1 or i>self.size:
            print("search Location Error！")
            return False
        else:
            return self.sqlist[i]
    def showlist(self):
        return self.sqlist

import random
testsqlist=mysqlist(10)
for i in range(1,12):
    testsqlist.listinsert(i,i*100)
print("插入元素后的顺序表为：",testsqlist.showlist())
for i in range(1,2):
    testsqlist.listdelete(i)
print("删除元素后的顺序表为：",testsqlist.showlist())
print(testsqlist.findelem(5))
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

代码输出结果为：

Insert Location Error！
插入元素后的顺序表为： [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
删除元素后的顺序表为： [100, 300, 400, 500, 600, 700, 800, 900, 1000]
700
1
2
3
4

单链表

线性表的链式存储，他是一种非随机存取的存储结构。通过一组任意存储单元来存储线性表的数据元素，为了建立起数据元素之间的线性关系，对于每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。

首先定义一个不带头结点的链表，**self.head是头指针，指向第一个数据元素。**头指针为“NULL”时则表示一个空表。

class linknode():#每个结点有两个数据成员，结点元素和指向下一个结点的指针
    def __init__(self,item):
        self.item=item
        self.next=None
class  linklist():#初始化单链表，头指针指针域为空
    def __init__(self):
        self.head=None    
1
2
3
4
5
6
7

建立单链表有两种方式，头插法和尾插法：
头插法建立单链表，从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头指针之后：

    def headcreatlist(self, item):
        nod = linknode(item)  # 新建一个结点并赋值
        nod.next = self.head  # 结点指针域指向第一个结点
        self.head = nod  # 头指针指向当前结点
1
2
3
4

尾插法是将新结点插入到当前链表的表尾，需要增加一个尾指针，使其始终指向当前链表的尾结点。

    def tailcreatelist(self, item):
        nod = linknode(item)  # 新建一个结点并赋值,指针域为None
        cur = self.head
        while cur != None:  # 遍历到最后一个元素，指针域为None
            cur = cur.next
        cur.next = nod  # nod成为最后一个结点
1
2
3
4
5
6

其他的方法列举一部分：

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

    def listlength(self):
        nod = self.head  # 头结点指针域指向第一个结点
        nodnum = 0
        while (nod != None):
            nodnum += 1
            nod = nod.next  # 下一个结点
        return nodnum
        # 遍历单链表

    def tralist(self):
        show=[]
        nod = self.head
        while nod != None:
            show.append(nod.item)
            nod = nod.next
        return show

        # 在指定位置插入元素，插入位置为1~length+1,pos==1表示头插法，pos==length+1表示尾插法
        # 找到插入位置的前驱结点，再在其后插入新结点

    def Insertlist(self, pos, item):
        if pos < 1 or pos > self.listlength() + 1:
            print("Insert Position Error!")
            return False
        elif pos == 1:
            self.headcreatlist(item)
        elif pos == self.listlength() + 1:
            self.tailcreatelist(item)
        else:
            nod = linknode(item)
            count = 0
            cur = self.head
            while (count < pos - 1):
                cur = cur.next
                count += 1
            nod.next = cur.next
            cur.next = nod


    # 删除指定位置的结点
    def delete(self, pos):
        if pos < 1 or pos > self.listlength():
            print("Position Error!")
            return False
        else:
            nod=self.head
            coun=0
            while coun<pos-1:
                nod=nod.next
                coun+=1
            ne=nod.next.next
            nod.next=ne



        # 根据位置获取元素
    def Getelembypos(self, pos):
        if pos < 1 or pos > self.listlength():
            print("Position Error!")
            return False
        else:
            cur = self.head
            count = 1
            while count < pos:
                cur = cur.next
                count += 1
            return cur.item

     # 根据结点元素获取结点（保证获取的值唯一）
    def getposbyelem(self, elem):
        cur = self.head
        while (cur != None and cur.item != elem):
            cur = cur.next
        return cur if cur.item == elem else 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

把上面的代码都合并起来，调用函数测试一下：

if __name__ == "__main__":
    ll1=linklist()
    for i in range(10):
        ll1.headcreatlist(i*10)

    len=ll1.listlength()
    print("单链表的长度为：",len)
    sh=ll1.tralist()
    print("头插法建立的链表遍历为：",ll1.tralist())

    # ll2 = linklist()
    for i in range(10):
        ll1.tailcreatelist(i * 100)

    len = ll1.listlength()
    print("单链表的长度为：", len)
    sh = ll1.tralist()
    print("尾插法插法建立的链表遍历为：", ll1.tralist())
    ll1.Insertlist(1,111111)
    ll1.Insertlist(1,111111)
    print("插入元素后的链表遍历为：", ll1.tralist())
    ll1.deleteelem(1)
    ll1.deleteelem(2)
    print("删除元素后的链表遍历为：", ll1.tralist())

    print("第二个位置上的元素为：",ll1.Getelembypos(2))
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

输出为：

单链表的长度为： 10
头插法建立的链表遍历为： [90, 80, 70, 60, 50, 40, 30, 20, 10, 0]
单链表的长度为： 20
尾插法插法建立的链表遍历为： [90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 100, 200, 300, 400, 500, 600, 700, 800, 900]
插入元素后的链表遍历为： [111111, 111111, 90, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 100, 200, 300, 400, 500, 600, 700, 800, 900]
删除元素后的链表遍历为： [111111, 80, 70, 60, 50, 40, 30, 20, 10, 0, 0, 100, 200, 300, 400, 500, 600, 700, 800, 900]
第二个位置上的元素为： 80
1
2
3
4
5
6
7

这里会有一个问题，如果直接尾插法建表，表中没有元素就会报错：AttributeError: ‘NoneType’ object has no attribute ‘next’
报错语句为：
while cur.next != None: # 遍历到最后一个元素，指针域为空
这是因为尾插法建立链表时，插入第一个元素时，self.head是指向第一个元素的，此时为None,所以没有next属性，自然就会报错。
因此第一个结点需要特殊处理，我们一般通过增加头结点的方式来避免这种特殊处理。感兴趣可以了解一下：Python实现单链表（带头结点）