Shulou(Shulou.com)06/02 Report--

The content of this article mainly focuses on how to analyze the sequence table in the Python data structure and algorithm. The content of the article is clear and clear. It is very suitable for beginners to learn and is worth reading. Interested friends can follow the editor to read together. I hope you can get something through this article!

0. Learning goal

Linear tables can be represented in many ways in computers, and linear tables with different storage methods also have different names and characteristics. Linear tables have two basic storage structures: sequential storage structure and chain storage structure. This section will introduce the characteristics of sequential storage structure and the implementation of various basic operations.

Through this section, you should master the following:

Sequential Storage and implementation of Linear Table

Realization of basic Operation of sequence Table

Using the basic operation of sequential table to realize complex algorithm

1. Sequential storage structure of linear tables 1.1 basic concepts of sequential tables

The sequential storage of linear table is that the data elements of linear table are stored in a group of continuous storage units in logical order, that is, two adjacent data elements in logical structure are also stored in the physical storage location in the computer. This storage method allocates a whole memory block to the whole linear table to save the elements of the linear table. The logical relationship between the data elements in the linear table is represented by the physical position of the data elements in the computer. The linear table represented by sequential storage structure is referred to as sequential table (Sequential List).

The sequence table has the following two basic characteristics:

The storage space occupied by all the elements of the sequential table is continuous.

The data elements in the sequential table are stored in logical order in the storage space.

Because all data elements of a linear table belong to the same data type, each element occupies the same space (number of bytes). Therefore, it is convenient to find an element in this structure, that is, as long as you know the sequence header address and the size of the bytes each data element occupies in memory, you can find the address of the I ii data element. By using the sequence number of a specific element, the data element can be accessed in a constant time, so it can be said that the sequential table has the characteristic of random access according to the sequence number of the data element.

Assuming that the storage address of the first data element in the linear table (that is, the address of the first byte of the ordered table, also known as the first address) is id (A1), and each data element occupies k bytes, the storage address of the I element ai in the linear table in the computer is:

Id (ai) = id (A1) + (I − 1) × k (1 ≤ I ≤ n)

As you can see from the above formula, the process of accessing sequential table data elements requires only one multiplication and one addition. Since these two operations require only constant time, it can be said that sequential table access can be done in constant time.

That is, the storage address of each data element in the sequence table in the computer storage space is uniquely determined by the sequence number in the element's online table. Suppose there is a linear table of length n (A1 ~ 2), then its sequential storage structure in the computer can be represented by the following figure:

1.2 advantages and disadvantages of sequential tables

Advantages of sequential tables:

Simple and easy to use

Quick access to elements

Disadvantages of the sequence table:

Fixed size: the size of the order table is static (you need to specify the order table size before use)

Inserting elements based on location is more complex: to insert an element at a given location, you may need to move an existing element to create an empty location to insert a new element at the desired location; if you want to add an element at the beginning, then the shift operation is more expensive.

In order to solve the defect that the sequence table has a fixed size, the concept of dynamic sequence table is proposed.

1.3 dynamic sequence table

Dynamic sequential table (also known as growable sequential table, resizable sequential table, dynamic table) is a randomly accessed, variable-sized sequential table data structure that allows you to add or remove elements. Python's built-in list is a dynamic sequential table.

A simple way to implement dynamic sequential tables is to start with some fixed-size sequential tables. Once the sequence table becomes full, a new sequence table is created that is larger than the original sequence table size; similarly, if there are too few elements in the sequence table, the sequence table size will be reduced.

Next, to better understand the sequence table, we will use Python to implement the sequence table.

two。 The realization of sequence table

In the implementation, the list in Python is used to correspond to the continuous storage space. A maximum of max_size elements can be stored, and an integer variable num_items needs to be defined to save the length of the linear table. Because the index in the Python list starts at 0, the I (1 ≤ I ≤ n) element of the linear table is stored in the list element with the list index I − 1. In order to maintain consistency, the sequence number of the sequential table we implemented also starts from 0 (you can also index from 1 as needed, with simple modification).

2.1 initialization of the sequence table

The initialization of a sequential table requires three pieces of information: the items list is used to store data elements, the max_size is used to store the maximum length of the items list, and the location that num_items uses to record the current use of the items list, that is, the number of data elements in the sequential table.

Class SequentialList: def _ _ init__ (self, max_size=10): self.items = [None] * max_size self.num_items = 0 self.max_size = max_size

The initialization code builds a SequentialList object by creating a list of 10 None values, the initial size of the internal items list max_size is 10 by default, or you can pass a larger sequential table size as the initial size, and the list can grow dynamically as needed. The time complexity of creating a SequentialList object is O (1).

As shown in the following figure, it is a SequentialList object that contains five data elements:

2.2 get the length of the sequence table

The sequence table length here refers to the number of data elements in the order table. Because we use num_items to track the number of items in the order table, to find the sequence table length only needs to overload the value of num_items returned from the object by _ _ len__, so the time complexity is O (1):

Def _ _ len__ (self): return self.num_items

If the number of items in the list is not tracked in the SequentialList object, the time complexity of calculating the sequence table length is O (n).

2.3 read the specified location element

In order to implement the operation of reading the elements of the specified position in the sequence table, we will overload the _ _ getitem__ operation with a complexity of O (1). At the same time, we want to make sure that the index is within an acceptable range of indexes, otherwise an IndexError exception will be thrown like a built-in list class:

Def _ getitem__ (self, index): if index > = 0 and index

< self.num_items: return self.items[index] raise IndexError('SequentialList index out of range') 我们也可以实现修改指定位置元素的操作，只需要重载 __setitem__ 操作，其复杂度同样为O(1)： def __setitem__(self, index, val): if index >

= 0 and index

< self.num_items: self.items[index] = val return raise IndexError("SequentialList assignment index out of range")2.4 查找指定元素 要确定值为 x 的元素在顺序表中的位置，需要依次比较各元素。当查询到第一个满足条件的数据元素时，返回其下标，否则像内置列表类一样引发 ValueError 异常，表示查找失败。 def locate(self, item): for i in range(self.num_items): if self.items[i] == item: return i raise ValueError("{} is not in sequential list".format(item)) 在查找过程中，数据元素比较次数的平均值为(n+1)/2，因此时间复杂度为O(n)。 2.5 在指定位置插入新元素 实现在指定位置插入新元素之前，我们首先看下如何在顺序表末尾追加元素。追加时，如果有空闲空间，只需要在 self.items 列表的末尾再添加一项，而当 self.items 列表填满时，我们必须增加 self.items 列表的大小，为需要追加的新元素创建空间，创建的新 self.items 大小与 self.items 的当前长度成正比。 为了使追加操作在O(1)时间内运行，我们不能在每次需要更多空间时仅增加一个空闲位置，事实证明，每次增加 25% 的空间就足以保证O(1)复杂度。选择增加空间的百分比并不重要，每次增加 10% 或100%的空间，同样可以使时间复杂度为O(1)。这里选择 25% 的原因是可以在不占用太多计算机内存的情况下多次使用追加操作扩展列表。 def __alloc(self): new_size = (self.max_size // 4) + self.max_size + 1 new_items = [None] * new_size for i in range(self.num_items): new_items[i] = self.items[i] self.items = new_items self.max_size = new_size def append(self, item): if self.num_items == self.max_size: self.__alloc() self.items[self.num_items] = item self.num_items += 1 要插入新数据元素到顺序表中，必须为新元素腾出空间，下图表示顺序表中的列表在进行插入操作前后，其数据元素在列表中下标的变化情况： 完成如上的插入操作要经过如下步骤： 1.线性表中指定位置及其之后的元素，依次向后移动一个位置，空出索引为i的位置 2.数据元素 x 插入到第i个存储位置 3.插入结束后使线性表的长度增加 1 需要注意的是，如果线性表空间已满，首先需要分配新的空间。如果提供的索引大于列表的大小，则将新项 x 附加到列表的末尾。插入时间元素操作的时间复杂度为O(n)。 def insert(self, index, item): if self.num_items == self.max_size: self.__alloc() if index < self.num_items and index >

= 0: for j in range (self.num_items-1, index-1 -1): self.items [juni1] = self.items [j] self.items [index] = item self.num_items + = 1 elif index > = self.num_items: self.append (item) else: raise IndexError ("SequentialList assignment index out of range") 2.6 Delete the specified location element

When we delete a data element at a specific index in the list, we must move all the elements after it down to ensure that there is no invalid data in the internal list. The following figure shows the change of the data element subscript of a sequential table before and after the delete operation:

The following steps are required to do this on the online spreadsheet:

1. Delete the element with subscript I from the online table, move forward one position from the element with index 1 to n − 1, and overwrite the deleted data element ai+1 with index I, so as to ensure that the physical positions of logically adjacent elements are also adjacent

two。 Modify the sequence table length to subtract 1

In order to delete the elements of the specified position in the sequence table, we will overload the _ _ getitem__ operation. When deleting data elements on the sequence table, we need to move about half of the elements in the table. Obviously, the time complexity of this algorithm is O (n).

Def _ _ delitem__ (self, index): for i in range (index, self.num_items-1): self.items [I] = self.items [I] self.num_items- = 12.7 other useful operations

In order to make better use of the sequence table, we will introduce some other useful operations.

For example, if you convert a sequential table to a string for printing, you can use the str function to call the _ _ str__ method on the object to create a string representation suitable for printing, and the returned result of _ _ str__ is highly readable:

Def _ str__ (self): s ='['for i in range (self.num_items): s + = repr (self.items [I]) if I < self.num_items-1: s + =','s + ='] 'return s

We can also overload the membership function _ _ contain__ to check whether a data element is one of the elements in the ordered table. The only way to do this is to examine each data element in the sequential table sequentially. If the item is found, True is returned, otherwise the search method of returning False is called linear search, so named because it has a time complexity of O (n):

Def _ _ contains__ (self, item): for i in range (self.num_items): if self.items [I] = item: return True return False

Checking the equality of two sequential tables first requires that the two sequential tables are of the same type and that the two sequential tables must have the same length. When these two prerequisites are met, if all the elements in the two tables are equal, we can say that the two sequential tables are equal, and the time complexity of the equality test is O (n). We overload the _ _ eq__ method to do this:

Def _ eq__ (self, another): if type (another)! = type (self) or self.num_items! = another.num_items: return False for i in range (self.num_items): if self.items [I]! = another.items [I]: return False return True3. Sequential table application

Next, we first test the sequence table of the above implementation to verify the effectiveness of the operation, and then use the basic operations to implement more complex algorithms.

3.1 Application example of sequence table

First initialize a sequence table sample_sqlist and append several elements to it:

Sample_sqlist = SequentialList () sample_sqlist.append (11) sample_sqlist.append (22) sample_sqlist.append (33)

We can directly print the data elements in the sequence table, the length of the sequence table and other information:

Print ('sequence table data element is:', sample_sqlist) print ('sequence table length:', len (sample_sqlist)) print ('sequence table 0 data element:', sample_sqlist [0]) # modify data element sample_sqlist [1] = 2022print ('sequence table data element is:', sample_sqlist)

The output of the above code is as follows:

The sequence table data elements are: [11,22,33]

Sequence table length: 3

The 0th data element in the sequence table: 11

The sequence table data elements are: [11, 2022, 33]

Next, we will demonstrate adding / removing elements at a specified location, and how to find a specified element, and so on:

Print ('add element 2021' at sequence table position 1) sample_sqlist.insert (1, 2021) print ('after adding elements, sequence table data elements are:', sample_sqlist) print ('delete elements at sequence table position 2') del (sample_sqlist [2]) print ('after deleting data The order table data elements are:', sample_sqlist) print ('element 11 has an index of {}' .format (sample_sqlist.locate (11) print ('11 in the sequence table?', 11 in sample_sqlist) print ('22 in the sequence table?', 22 in sample_sqlist)

The output of the above code is as follows:

Add element 2021 at sequence table position 1

After adding elements, the order table data elements are: [11, 2021, 2022, 33]

Delete elements at sequence table location 2

After deleting the data, the order table data elements are: [11, 2021, 33]

The index of element 11 is 0

11 in the sequence table? True

22 in the sequence table? False

3.2 using the basic operation of sequence table to realize complex operation

[1] merge two sequence tables using the basic operation of the sequence table:

Def add_sqlist (sqlist1 Sqlist2): result = SequentialList (max_size=sqlist1.num_items+sqlist2.num_items) for i in range (sqlist1.num_items): result.append (sqlist1 [I]) for i in range (sqlist2.num_items): result.append (sqlist2 [I]) return result# algorithm Test sqlist1 = SequentialList () sqlist2 = SequentialList () for i in range (10): sqlist1.append (I) sqlist2.append (item5) print ('sequential table 1Rom' Sqlist1, 'sequence table 2, sqlist2) # merge sequence table result = add_sqlist (sqlist1, sqlist2) print (' merge sequence table:', result)

You can see that the time complexity of merging two sequential tables is O (n), and the program output is as follows:

Sequence table 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] sequence table 2: [0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

Merge order table: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

[2] generate a new sequence table by using the common data elements in the sequence table sqlist1 and sqlist2:

Def commelem (sqlist1, sqlist2): result = SequentialList () for i in range (sqlist1.num_items): if sqlist1 [I] in sqlist2 and sqlist1 [I] not in result: result.append (sqlist1 [I]) return result# algorithm Test sqlist1 = SequentialList () sqlist2 = SequentialList () for i in range (5): sqlist1.append (item2) sqlist1.append (I) sqlist2.append (item3) print ('sequence Table 1, sqlist1 'sequence table 2, sqlist2) # merge sequence table result = commelem (sqlist1, sqlist2) print (' common elements in two order tables:', result)

You can see that the time complexity of the algorithm is O (N2), and the program output is as follows:

Merge order table: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 5, 10, 15, 20, 25, 30, 35, 40, 45]

Sequence table 1: [0, 0, 2, 1, 4, 2, 6, 3, 8, 4] sequence table 2: [0, 3, 6, 9, 12]

Common elements in two sequential tables: [0,6,3]

Thank you for your reading. I believe you have some understanding of "how to analyze the sequence table in Python data structure and algorithm". Go to practice quickly. If you want to know more related knowledge points, you can follow the website! The editor will continue to bring you better articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.