您现在的位置是：首页 > Python

当前栏目

python实现线性表

Python 存储数据

2023-03-02 11:22:49 时间

## 线性表的定义 ##

线性表是具有相同数据类型的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

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

python实现线性表

相关文章