[[410561]]

本文轉載自微信公眾號「python與大數據分析」，作者一只小小鳥鳥 。轉載本文請聯系python與大數據分析公眾號。

線性表(linear list)是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。本文結合了互聯網上的一些代碼，以及結合百度百科關于線性順序表的定義，實現了全部代碼。

在稍復雜的線性表中，一個數據元素可由多個數據項(item)組成，此種情況下常把數據元素稱為記錄(record)，含有大量記錄的線性表又稱文件(file)。

線性表中的個數n定義為線性表的長度，n=0時稱為空表。在非空表中每個數據元素都有一個確定的位置，如用ai表示數據元素，則i稱為數據元素ai在線性表中的位序。

線性表的相鄰元素之間存在著序偶關系。如用(a1，…，ai-1，ai，ai+1，…，an)表示一個順序表，則表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。當i=1,2，…，n-1時，ai有且僅有一個直接后繼，當i=2，3，…，n時，ai有且僅有一個直接前驅 [1] 。

需要轉換思想的是，線性表中的參數也好，最大數量也好，要在列表序號基礎上加1

代碼如下：

# 線性表（linear list）是數據結構的一種，一個線性表是n個具有相同特性的數據元素的有限序列。 
# 在稍復雜的線性表中，一個數據元素可由多個數據項（item）組成，此種情況下常把數據元素稱為記錄（record），含有大量記錄的線性表又稱文件（file）。 
# 線性表中的個數n定義為線性表的長度，n=0時稱為空表。在非空表中每個數據元素都有一個確定的位置，如用ai表示數據元素，則i稱為數據元素ai在線性表中的位序。 
# 線性表的相鄰元素之間存在著序偶關系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一個順序表，則表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。當i=1,2，…，n-1時，ai有且僅有一個直接后繼，當i=2，3，…，n時，ai有且僅有一個直接前驅 [1]  。 
# 1）MakeEmpty(L) 這是一個將L變為空表的方法 
# 2）Length（L） 返回表L的長度，即表中元素個數 
# 3）Get（L，i） 這是一個函數，函數值為L中位置i處的元素（1≤i≤n） 
# 4）Prior（L，i） 取i的前驅元素 
# 5）Next（L，i） 取i的后繼元素 
# 6）Locate（L，x） 這是一個函數，函數值為元素x在L中的位置 
# 7）Insert（L，i，x）在表L的位置i處插入元素x，將原占據位置i的元素及后面的元素都向后推一個位置 
# 8）Delete（L，p） 從表L中刪除位置p處的元素 
# 9）IsEmpty(L) 如果表L為空表(長度為0)則返回true，否則返回false 
# 10）Clear（L）清除所有元素 
# 11）Init（L）同第一個，初始化線性表為空 
# 12）Traverse（L）遍歷輸出所有元素 
# 13）Find（L，x）查找并返回元素 
# 14）Update（L，x）修改元素 
# 15）Sort（L）對所有元素重新按給定的條件排序 
# 16) strstr(string1,string2)用于字符數組的求string1中出現string2的首地址 
class Sequencelist(object): 
    def __init__(self, datatype=int, maxlength=10): 
        self.maxlength = maxlength 
        self.currentnum = 0 
        self.data = [None] * self.maxlength 
        self.datatype = datatype 
 
    def __setitem__(self, key, value): 
        if not isinstance(key, int): 
            raise TypeError 
        if not isinstance(value, self.datatype): 
            raise TypeError("數據類型不符合{0}".format(self.datatype)) 
        if 0 <= key <= self.currentnum: 
            self.data[key-1] = value 
        else: 
            raise IndexError 
 
    def __getitem__(self, key): 
        if not isinstance(key, int): 
            raise TypeError 
        if 1 <= key <= self.currentnum: 
            return self.data[key-1] 
        else: 
            raise IndexError 
 
    def __len__(self): 
        return self.currentnum 
 
    def __repr__(self): 
        return '__repr__={}'.format(str(self.data)) 
 
    def __str__(self): 
        return '__str__={}'.format(str(self.data[:self.currentnum])) 
 
    def isempty(self): 
        return self.currentnum == 0 
 
    def isfull(self): 
        return self.currentnum == self.maxlength 
 
    def maxlength(self): 
        return self.maxlength 
 
    def makeempty(self): 
        self.clear() 
 
    def length(self): 
        return self.__len__() 
 
    def count(self): 
        return self.__len__() 
 
    def get(self, key): 
        return self.__getitem__(key) 
 
    def set(self, key,value): 
        self.__setitem__(key,value) 
 
    def prior(self, key): 
        assert key>1 and key <self.currentnum+1 ,'數組越界' 
        return self.data[key-2] 
 
    def next(self, key): 
        assert key>=1 and key <self.currentnum, '數組越界' 
        return self.data[key] 
 
    def locate(self, value,start=0): 
        for i in range(start,self.currentnum): 
            if self.data[i]==value: 
                return i+1 
        raise ValueError("{} is not find in list".format(value)) 
 
    def index(self,value,start=0): 
        return self.locate(value,start) 
 
    def append(self,value): 
        if self.isfull(): 
            print('list is full') 
            return 
        else: 
            self.data[self.currentnum]=value 
            self.currentnum+=1 
 
    def insert(self, key, value): 
        if not isinstance(key,self.datatype): 
            raise TypeError 
        if key<1: 
            raise IndexError 
        if key>=self.currentnum: 
            self.append(value) 
        else: 
            for i in range(self.currentnum,key-1,-1): 
                self.data[i]=self.data[i-1] 
            self.data[key-1]=value 
            self.currentnum+=1 
 
    def delete(self, key): 
        if not isinstance(key, self.datatype): 
            raise TypeError 
        if key < 1 and key>self.currentnum: 
            raise IndexError 
        else: 
            for i in range(key-1,self.currentnum): 
                self.data[i]=self.data[i+1] 
            self.currentnum-=1 
 
    def pop(self): 
        return self.delete(self.currentnum) 
 
    def clear(self): 
        self.__init__() 
 
    def init(self): 
        self.__init__() 
 
    def reverse(self): 
        i,j=0,self.currentnum-1 
        while i<j: 
            self.data[i],self.data[j]=self.data[j],self.data[i] 
            i,j=i+1,j-1 
            #print(self.data) 
 
    def find(self, value,start=0): 
        return self.locate(self,value,start) 
 
    def update(self, key,value): 
        self.__setitem__(key,value) 
 
    def sort(self): 
        for i in range(0,self.currentnum-1): 
            for j in range(i+1,self.currentnum): 
                if self.data[i]>self.data[j]: 
                    self.data[i],self.data[j]=self.data[j],self.data[i] 
 
    def strstr(string1, string2): 
        pass 
 
 
if __name__ == '__main__': 
    a=Sequencelist() 
    a.append(1) 
    a.append(2) 
    a.append(3) 
    print(a) 
    print(repr(a)) 
    b=a.locate(2) 
    print(b) 
    print(a.isempty()) 
    print(a.isfull()) 
    print(len(a)) 
    print(a.length()) 
    #print(a.prior(1)) 
    # AssertionError: 數組越界 
    print(a.prior(2)) 
    print(a.prior(3)) 
    print(a.next(1)) 
    print(a.next(2)) 
    print(a) 
    print(a.get(2)) 
    a.insert(2,4) 
    print(a) 
    a.delete(2) 
    print(a) 
    print(a.length()) 
    a.pop() 
    print(a) 
    print(a.length()) 
    a.update(2,4) 
    print(a) 
    print(a.index(4)) 
    # print(a.index(5)) 
    # ValueError: 5 is not find in list 
    print(a) 
    a.reverse() 
    print(a) 
    a.append(3) 
    a.append(5) 
    # a.append(2) 
    print(a) 
    a.sort() 
    print(a) 

結果如下：

C:\python\pyproject\pythonalgorithms\venv\Scripts\python.exe C:/python/pyproject/pythonalgorithms/sequencelist.py 
__str__=[1, 2, 3] 
__repr__=[1, 2, 3, None, None, None, None, None, None, None] 
2 
False 
False 
3 
3 
1 
2 
2 
3 
__str__=[1, 2, 3] 
2 
__str__=[1, 4, 2, 3] 
__str__=[1, 2, 3] 
3 
__str__=[1, 2] 
2 
__str__=[1, 4] 
2 
__str__=[1, 4] 
__str__=[4, 1] 
__str__=[4, 1, 3, 5] 
__str__=[1, 3, 4, 5] 
 
Process finished with exit code 0