python实现线性表

ゝ一世哀愁。 2022-10-28 12:27 237阅读 0赞

## 线性表的定义 ##

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

## 顺序表 ##

线性表的顺序存储结构，使用一组地址连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻，即顺序表的逻辑顺序与其物理顺序相同。  
下图是C语言表示的顺序表，sizeof()用于计算元素所占存储空间。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70][]  
顺序表有两种实现方式：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70 1]

图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))

代码输出结果为：

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

## 单链表 ##

线性表的链式存储，他是一种非随机存取的存储结构。通过一组任意存储单元来存储线性表的数据元素，为了建立起数据元素之间的线性关系，对于每个链表结点，除了存放元素自身的信息之外，还需要存放一个指向其后继的指针。  
![在这里插入图片描述][20210207104314706.png]  
首先定义一个不带头结点的链表，\*\*self.head是头指针，指向第一个数据元素。\*\*头指针为“NULL”时则表示一个空表。

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

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

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

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

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

其他的方法列举一部分：

#判断是否为空
        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

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

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))

输出为：

单链表的长度为： 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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70]: /images/20221024/af0510c138114de78168ab3ccf2d8911.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdWxhbmJh_size_16_color_FFFFFF_t_70 1]: /images/20221024/9e85a26d83dc44bda14b95c76e201b93.png
[20210207104314706.png]: /images/20221024/1efc3dfd07174402845ae5c9861870cd.png
[Python]: https://blog.csdn.net/liulanba/article/details/113767736