当前位置：网站首页 > 技术资源 > 正文

数据结构——数组和链表（数组结构体链表）

off999 2024-10-01 13:48 15 浏览 0 评论

数组和链表

Created: Apr 04, 2020 2:49 PM

01 集合

数据结构是以不同方式将数据组织和分组在一起的容器。当你编写代码来解决问题时，总会涉及到数据-以及如何在计算机内存中存储或构造数据会对你可以执行哪些操作以及执行这些操作的效率产生巨大影响。

在本节中，我们将首先回顾一些您可能至少已经部分熟悉的基本数据结构。然后，随着课程的进行，在解决不同类型的问题时，我们将考虑使用不同结构的利弊。我们将从讨论非常通用的结构（集合）开始。

集合的特性

没有特定的顺序
具有相同类型的对象

02 列表

列表特性

有顺序
没有固定的长度

03 数组

Python中数组和list的区别

数组和列表有一些共同点：

是一些单元的集合
他们是一个顺序的集合

主要区别之一是数组具有索引

要了解这一点，有助于了解如何将数组存储在内存中。创建数组时，始终会为其指定一些初始大小，即它应该能够容纳的元素数量（以及每个元素的大小）。然后，计算机会找到一块内存，并为阵列留出空间。

重要的是，预留的空间是一个连续的块。也就是说，数组的所有元素都是连续的，这意味着它们在内存中都彼此相邻。

数组的另一个关键特性是所有元素的大小都相同。

当我们直观地表示一个数组时，我们通常将其绘制为一系列大小相同且彼此相邻的盒子：

因为所有元素彼此相邻且大小相同，所以这意味着如果我们知道第一个元素的位置，就可以计算任何其他元素的位置。

例如，如果数组中的第一个元素位于内存位置00且元素为24个字节，则下一个元素将位于位置00 + 24 =24。其后的一个元素将位于24 + 24 = 48，等等。

由于我们可以轻松计算数组中任何项目的位置，因此我们可以为每个项目分配一个索引，并使用该索引快速而直接地访问该项目

相反，列表中的元素在内存中可能相邻，也可能不相邻！例如，在本课程的稍后部分，我们将查看链接列表，其中每个列表项都指向下一个列表项，但是这些项本身可能分散在内存的不同位置。在这种情况下，知道列表中第一个项目的位置并不意味着您可以简单地计算其他项目的位置。这意味着我们不能像使用数组那样使用索引直接访问列表项。我们将在短期内更详细地探讨链接列表。

在python中我们可以使用[]创建一个列表

>>> my_list = ['a', 'b', 'c']

>>> my_list

['a', 'b', 'c']

然后我们可以通过索引访问列表中的元素：

>>> my_list[0]

'a'

>>> my_list[1]

'b'

>>> my_list[2]

'c'

我们将不会涉及所有细节，但是您需要在此课程中了解的重要事项如下：如果深入研究，您会发现Python列表实际上是像数组一样实现的（特别是，如果您感到好奇，它的行为就像一个动态数组）。特别是，Python列表的元素在内存中是连续的，可以使用索引对其进行访问。

除了基础数组之外，Python列表还包含一些其他行为。例如，您可以在Python列表上使用pop和append方法之类的东西来添加或删除项。使用这些方法，您实际上可以利用Python列表（例如堆栈）（这是我们稍后将讨论的另一种数据结构）

通常，我们将尽量避免使用pop和append之类的东西，因为这些是高级语言功能，您可能无法使用其他语言来使用。在大多数情况下，我们将忽略Python列表附带的额外功能，而是像使用简单数组一样使用它们。这将使您看到底层数据结构如何工作，而与实现这些结构所使用的语言无关。

这是底线：

- Python list本质上是数组，但还包含其他高级功能
- 在本课程中，我们通常将忽略此高级功能，并将Python列表视为简单数组

这种方法将使您对底层数据结构有更好的了解。

初始化列表

"""An Element has some value associated with it (which could be anything a€”

a number, a string, a character, et cetera), and it has a variable that 

points to the next element in the linked list. """

class Element(object):

    def __init__(self, value):

        self.value = value

        self.next = None

        

"""This code is very similar a€” we're just establishing that a LinkedList is

something that has a head Element, which is the first element in the list.

If we establish a new LinkedList without a head, it will default to None."""

class LinkedList(object):

    def __init__(self, head=None):

        self.head = head

添加节点

def append(self, value):

        """adds a new Element to the end of our LinkedList"""

        cur = self.head

        if self.head:

            while (cur.next):

                cur = cur.next

            cur.next = Element(value)

        else:

            self.head = Element(value)

弹出节点

def pop(self):

        cur = self.head

        if cur == None:

            return None

        if cur.next == None:

            val = cur.value

            self.head = None

            #pdb.set_trace()

            return val

        while cur.next:

            if (cur.next.next == None):

                val = cur.next.value

                cur.next = None

                return val

            cur = cur.next

获取对应位置的节点

def get_position(self, position):

        """Get an Element from a particular position. Assume the first position is "1".

        Return "None" if position is not in the list."""

        if position > 0:

            current = self.head

            counter = 1

            while current:

                if counter == position:

                    return current

                current = current.next

                counter += 1

            # position too large

            return None

        else:

            # position too small

            return None

插入节点

def insert(self, value, position):

        """Insert a new node at the given position. Assume the first position is "1".

        Inserting at position 3 means between the 2nd and 3rd elements."""

        i = position - 1

        cur = self.head

        new_element = Element(value)

        if position > 0:

            if i == 0:

                new_element.next = cur

                self.head = new_element

            else:

                while(i == 2):

                    #pdb.set_trace()

                    cur = cur.next

                    i -= 1

                new_element.next = cur.next

                cur.next = new_element

删除节点

def delete(self, value):

        """Delete the first node with a given value."""

        cur = self.head

        if cur.value == value:

            self.head = cur.next

        else:

            while cur.next:

                if cur.next.value == value:

                    cur.next = cur.next.next

                    break

列表逆序

def reverse(self):

        cur = self.head

        new_list = LinkedList()

        prev_node = None

        while cur:

            new_node = Element(cur.value)

            new_node.next = prev_node

            prev_node = new_node

            cur = cur.next

        

        new_list.head = prev_node

        return new_list

递归实现

递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决

- 1、明确递归终止条件；
- 2、给出递归终止时的处理办法；
- 3、提取重复的逻辑，缩小问题规模。

"""在递去过程中解决问题"""

function recursion(大规模){

    if (end_condition){      // 明确的递归终止条件

        end;   // 简单情景

    }else{            // 在将问题转换为子问题的每一步，解决该步中剩余部分的问题

        solve;                // 递去

        recursion(小规模);     // 递到最深处后，不断地归来

    }

}

"""在归来过程中解决问题"""

function recursion(大规模){

    if (end_condition){      // 明确的递归终止条件

        end;   // 简单情景

    }else{            // 先将问题全部描述展开，再由尽头“返回”依次解决每步中剩余部分的问题

        recursion(小规模);     // 递去

        solve;                // 归来

    }

}
原始序列： A-->B-->None

head.next.next = head

A-->B-->None

↑___| 

head.next = None

A-->B-->None

|________↑

B->A->None

"""

def reverse_recursion(head):

    if head is None or head.next is None:

        return head

    	

    new_head = reverse_recursion(head.next)

    pdb.set_trace()

    head.next.next = head

    head.next = None

    

    return new_head

合并两个列表

def merge(list1, list2):

    merged = LinkedList(None)

    if list1 is None:

        return list2

    if list2 is None:

        return list1

    list1_elt = list1.head

    list2_elt = list2.head

    while list1_elt is not None or list2_elt is not None:

        if list1_elt is None:

            merged.append(list2_elt)

            list2_elt = list2_elt.next

        elif list2_elt is None:

            merged.append(list1_elt)

            list1_elt = list1_elt.next

        elif list1_elt.value <= list2_elt.value:

            merged.append(list1_elt)

            list1_elt = list1_elt.next

        else:

            merged.append(list2_elt)

            list2_elt = list2_elt.next

    return merged

class NestedLinkedList(LinkedList):

    def flatten(self):

        return self._flatten(self.head)

    def _flatten(self, node):

        if node.next is None:

            return merge(node.value, None)

        return merge(node.value, self._flatten(node.next))

linked_list = LinkedList(Node(1))

linked_list.append(3)

linked_list.append(5)

second_linked_list = LinkedList(Node(2))

second_linked_list.append(4)

nested_linked_list = NestedLinkedList(Node(linked_list))

nested_linked_list.append(second_linked_list)

flattened = nested_linked_list.flatten()

node = flattened.head

while node is not None:

    #This will print 1 2 3 4 5

    print(node.value)

    node = node.next

Add one

```python

'''

Add-One:

Problem Statement:

You are given a non-negative number in the form of a list elements.

For example, the number 123 would be provided as arr = [1, 2, 3]

Add one to the number and return the output in the form of a new list.

Example 1:

	input = [1, 2, 3]

	output = [1, 2, 4]

Example 2:

	input = [9, 9, 9]

	output = [1, 0, 0, 0]

Challenge:

One way to solve this problem is to convert the input array into a

number and then add one to it. For example, if we have

input = [1, 2, 3], you could solve this problem by creating the

number 123 and then separating the digits of the output number 124.

But can you solve it in some other way?

'''

import pdb

def add_one(arr):

	'''

	:param: arr - list of digits representing some number x

	return a list with digits representing int (x + 1)

	'''

	output = 1;

	for i in range(len(arr), 0, -1):

		output = output + arr[i -1]

		borrow = output // 10

		pdb.set_trace()

		if borrow == 0:

			arr[i - 1] = output

			break

		else:

			arr[i - 1] = output % 10

			output = borrow

	arr = [borrow] + arr

	index = 0

	while arr[index] == 0:

		index += 1

	return arr[index:]

def test_function(test_case):

	arr = test_case[0]

	solution = test_case[1]

	output = add_one(arr)

	for index, element in enumerate(output):

		if element != solution[index]:

			print("Fail")

			return

	print("Pass")

arr = [0]

solution = [1]

test_case = [arr, solution]

test_function(test_case)

arr = [1, 2, 3]

solution = [1, 2, 4]

test_case = [arr, solution]

test_function(test_case)

arr = [9, 9, 9]

solution = [1, 0, 0, 0]

test_case = [arr, solution]

test_function(test_case)

查找并返回输入数组中连续子数组中的最大和。

"""

Problem Statement

You have been given an array containg numbers. Find and return the largest sum in a contiguous subarray within the input array.

Example 1:

arr= [1, 2, 3, -4, 6]

The largest sum is 8, which is the sum of all elements of the array.

Example 2:

arr = [1, 2, -5, -4, 1, 6]

The largest sum is 7, which is the sum of the last two elements of the array.

"""

def max_sum_subarray(arr):

    """

    :param - arr - input array

    return - number - largest sum in contiguous subarry within arr

    Author: Zhijin Li (lizhijin1993@gmail.com)

    """

    current_sum = arr[0]

    max_sum = arr[0]

    for num in arr[1:]:

    	current_sum = max(num, current_sum + num)

    	max_sum = max(current_sum, max_sum)

    return max_sum

def test_function(test_case):

    arr = test_case[0]

    solution = test_case[1]

    

    output = max_sum_subarray(arr)

    if output == solution:

        print("Pass")

    else:

        print("Fail")

# Test Case 1

arr= [1, 2, 3, -4, 6]

solution= 8 # sum of array

test_case = [arr, solution]

test_function(test_case)

# Test Case 2

arr = [1, 2, -5, -4, 1, 6]

solution = 7   # sum of last two elements

test_case = [arr, solution]

test_function(test_case)

# Test Case 3

arr = [-12, 15, -13, 14, -1, 2, 1, -5, 4]

solution = 18  # sum of subarray = [15, -13, 14, -1, 2, 1]

test_case = [arr, solution]

test_function(test_case)

? 2020 GitHub, Inc.

Terms

Privacy

Security

Status

Help

Contact GitHub

Pricing

API

Training

Blog

About

Pascal's triangle

'''

问题陈述：

查找并返回列表形式的Pascal三角形的第n行。

n从0开始

例如，如果n = 4，则输出= [1、4、6、4、1]

Pascal的Triangle参考：

     https://www.mathsisfun.com/pascals-triangle.html

任何帕斯卡三角形的公式：

        

     [（n）/（k）]

     ---------------------

     [（n！）/（k！（n-k）！）]

参数：-n-索引（从0开始）

return-list（）代表Pascal三角形的第n行

'''

def nth_row_pascal(n):

    if n == 0:

        return [1]

    current_row = [1]

    for i in range(1, n + 1):

        previous_row = current_row

        current_row = [1]

        for j in range(1, i):

            next_number = previous_row[j] + previous_row[j-1]

            current_row.append(next_number)

        current_row.append(1)

    return current_row

def test_function(test_case):

    n = test_case[0]

    solution = test_case[1]

    output = nth_row_pascal(n)

    if solution == output:

        print("Pass")

    else:

        print("Fail")

n = 0

solution = [1]

test_case = [n, solution]

test_function(test_case)

n = 1

solution = [1, 1]

test_case = [n, solution]

test_function(test_case)

n = 2

solution = [1, 2, 1]

test_case = [n, solution]

test_function(test_case)

n = 3

solution = [1, 3, 3, 1]

test_case = [n, solution]

test_function(test_case)

n = 4

solution = [1, 4, 6, 4, 1]

test_case = [n, solution]

test_function(test_case)

			

```

### 偶数排在奇数后

```python

'''

问题陈述：

给定具有整数数据的链表，请以以下方式排列元素：将所有具有偶数的节点放在奇数之后。 不要创建任何新节点，并避免使用任何其他数据结构。 偶数和奇数元素的相对顺序不得更改。

例：

链表= 1 2 3 4 5 6

输出= 1 3 5 2 4 6

'''

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

# Solution

def even_after_odd(head):

    if head is None:

        return head

    even = None

    odd = None

    even_tail = None

    head_tail = None

    while head:

        next_node = head.next

        if head.data % 2 == 0:

            if even is None:

                even = head

                even_tail = even

            else:

                even_tail.next = head

                even_tail = even_tail.next

        else:

            if odd is None:

                odd = head

                odd_tail = odd

            else:

                odd_tail.next = head

                odd_tail = odd_tail.next

        head.next = None

        head = next_node

    if odd is None:

        return even

    odd_tail.next = even

    return odd

def create_linked_list(arr):

    if len(arr) == 0:

        return None

    head = Node(arr[0])

    tail = head

    for data in arr[1:]:

        tail.next = Node(data)

        tail = tail.next

    return head

def print_linked_list(head):

    while head:

        print(head.data, end=' ')

        head = head.next

    print()

def test_function(test_case):

    head = test_case[0]

    solution = test_case[1]

    node_tracker = dict({})

    node_tracker['nodes'] = list()

    temp = head

    while temp:

        node_tracker['nodes'].append(temp)

        temp = temp.next

    head = even_after_odd(head)

    temp = head

    index = 0

    try:

        while temp:

            if temp.data != solution[index] or temp not in node_tracker['nodes']:

                print("Fail")

                return

            temp = temp.next

            index += 1

        print("Pass")

    except Excemption as e:

        print("Fail")

arr = [1, 2, 3, 4, 5, 6]

solution = [1, 3, 5, 2, 4, 6]

head = create_linked_list(arr)

test_case = [head, solution]

test_function(test_case)

arr = [1, 3, 5, 7]

solution = [1, 3, 5, 7]

head = create_linked_list(arr)

test_case = [head, solution]

test_function(test_case)

arr = [2, 4, 6, 8]

solution = [2, 4, 6, 8]

head = create_linked_list(arr)

test_case = [head, solution]

test_function(test_case)

交换节点

'''

问题陈述：

给定一个链表，交换位置i和j处的两个节点。

这些位置基于从0开始的索引。

注意：您必须交换节点，而不仅仅是交换值。

例：

linked_list = 3 4 5 2 6 1 9

位置= 3 4

输出= 3 4 5 6 2 1 9

说明：

位置3上的节点的值为2

位置4上的节点的值为6

交换这些节点将导致最终节点顺序为3 4 5 6 2 1 9

'''

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

def swap_nodes(head, left_index, right_index):

    # if both the indices are same

    if left_index == right_index:

        return head

    left_previous = None

    left_current = None

    right_previous = None

    right_current = None

    count = 0

    temp = head

    new_head = None

    # find out previous and current node at both the indices

    while temp is not None:

        if count == left_index:

            left_current = temp

        elif count == right_index:

            right_current = temp

            break

        if left_current is None:

            left_previous = temp

        right_previous = temp

        temp = temp.next

        count += 1

    right_previous.next = left_current

    temp = left_current.next

    left_current.next = right_current.next

    # if both the indices are next to each other

    if left_index != right_index:

        right_current.next = temp

    # if the node at first index is head of the original linked list

    if left_previous is None:

        new_head = right_current

    else:

        left_previous.next = right_current

        new_head = head

    return new_head

def test_function(test_case):

    head = test_case[0]

    left_index = test_case[1]

    right_index = test_case[2]

    left_node = None

    right_node = None

    temp = head

    index = 0

    try:

        while temp is not None:

            if index == left_index:

                left_node = temp

            if index == right_index:

                right_node = temp

                break

            index += 1

            temp = temp.next

        updated_head = swap_nodes(head, left_index, right_index)

        temp = updated_head

        index = 0

        pass_status = [False, False]

        while temp is not None:

            if index == left_index:

                pass_status[0] = temp is right_node

            if index == right_index:

                pass_status[1] = temp is left_node

            index += 1

            temp = temp.next

        if pass_status[0] and pass_status[1]:

            print("Pass")

        else:

            print("Fail")

        return updated_head

    except Exception as e:

        print("Fail")

def create_linked_list(arr):

    if len(arr) == 0:

        return None

    head = Node(arr[0])

    tail = head

    for data in arr[1:]:

        tail.next = Node(data)

        tail = tail.next

    return head

def print_linked_list(head):

    while head:

        print(head.data, end=" ")

        head = head.next

    print()

arr = [3, 4, 5, 2, 6, 1, 9]

head = create_linked_list(arr)

left_index = 3

right_index = 4

test_case = [head, left_index, right_index]

updated_head = test_function(test_case)

arr = [3, 4, 5, 2, 6, 1, 9]

left_index = 2

right_index = 4

head = create_linked_list(arr)

test_case = [head, left_index, right_index]

updated_head = test_function(test_case)

arr = [3, 4, 5, 2, 6, 1, 9]

left_index = 0

right_index = 1

head = create_linked_list(arr)

test_case = [head, left_index, right_index]

updated_head = test_function(test_case)

python数组长度

上一篇：Python 十大装 B 语法（python必备神器）
下一篇：深入了解编程语言中的数组和列表（编程定义数组）

数据结构——数组和链表（数组结构体链表）

数组和链表

01 集合

02 列表

03 数组

Python中数组和list的区别

初始化列表

添加节点

弹出节点

获取对应位置的节点

插入节点

删除节点

列表逆序

Add one

查找并返回输入数组中连续子数组中的最大和。

Pascal's triangle

交换节点

相关推荐

取消回复欢迎你发表评论:

python 3.8调用dll - Could not find module 错误的解决方法

大学生机械制图搜题软件?7个受欢迎的搜题分享了

Python3.8如何安装Numpy（python3.6安装numpy）

加密Python源码方案 PyArmor（python项目源码加密）

腿身比计算公式，在线计算器，长短腿类型表

编写一个自动生成双色球号码的 Python 小脚本

免费男女身高在线计算器，身高计算公式

将python文件打包成exe程序，复制到每台电脑都可以运行

Python学习入门教程，字符串函数扩充详解

Python数据分析实战-使用replace方法模糊匹配替换某列的值

数据结构——数组和链表（数组 结构体 链表）

数组和链表

01 集合

02 列表

03 数组

Python中数组和list的区别

初始化列表

添加节点

弹出节点

获取对应位置的节点

插入节点

删除节点

列表逆序

Add one

查找并返回输入数组中连续子数组中的最大和。

Pascal's triangle

交换节点

相关推荐

取消回复欢迎 你 发表评论:

python 3.8调用dll - Could not find module 错误的解决方法

大学生机械制图搜题软件?7个受欢迎的搜题分享了

Python3.8如何安装Numpy（python3.6安装numpy）

加密Python源码方案 PyArmor（python项目源码加密）

腿身比计算公式，在线计算器，长短腿类型表

编写一个自动生成双色球号码的 Python 小脚本

免费男女身高在线计算器，身高计算公式

将python文件打包成exe程序，复制到每台电脑都可以运行

Python学习入门教程，字符串函数扩充详解

Python数据分析实战-使用replace方法模糊匹配替换某列的值

数据结构——数组和链表（数组结构体链表）

取消回复欢迎你发表评论: