单链表的结点通常由哪几部分构成（ ），结点中数据元素的类型要求（ ） 17．在链式存储结构中，一个存储结点通常存储一个（ ）。 18．顺序表的存储密度和单链表的存储密度各为多少（ ） 19．在顺序表/单链表中访问任意一结点的时间复杂度均为( / ) 20．线性表在( )情况下适合使用顺序存储来实现，在（ ）情况下适合使用链式结构存储情况下来实现 21．线性表若采用链式存储结构，对存储单元的地

17. 一个数据元素和一个指针域。
18. 顺序表的存储密度为 100%，单链表的存储密度小于 100%。
19. 在顺序表中访问任意一结点的时间复杂度为 O(1)，在单链表中访问任意一结点的时间复杂度为 O(n)。
20. 在元素个数固定、频繁进行随机访问的情况下适合使用顺序存储来实现，在元素个数不确定、插入和删除操作频繁的情况下适合使用链式结构存储来实现。
21. 在链式存储结构中，对存储单元的地址没有要求，可以随意分配。

相关问题

1分别在什么情况下用顺序和链式存储结构实现线性表? 2. 设用带头结点的单链表实现线性表。如何判断线性表的元素是否两两不等?

1.

顺序存储结构适用于线性表元素个数较少，存储空间相对充足，且需要频繁进行随机存取的情况。链式存储结构适用于线性表元素个数较多，存储空间受限，且需要频繁进行插入和删除操作的情况。

2.

要判断线性表的元素是否两两不等，可以采用以下算法：

1. 遍历单链表，对于每个结点，将其值与后续所有结点的值进行比较。

2. 如果找到一个与该结点值相等的结点，则说明线性表中存在相同的元素，返回false。

3. 如果遍历完整个单链表，都没有找到相同的元素，则说明线性表中所有元素都不相同，返回true。

本题要求实现一个函数，求带头结点的单链表的表长。

### 回答1：
可以遍历整个单链表，统计节点个数即为表长。具体实现如下：

def get_list_length(head):
    """
    获取带头结点的单链表的表长
    """
    length = 0
    cur = head.next
    while cur:
        length += 1
        cur = cur.next
    return length

其中，head 是带头结点的单链表的头结点。我们通过 head.next 获取实际存储数据的第一个节点，然后循环遍历链表，每经过一个节点 length 加 1，直到遍历到链表末尾。最后返回 length 即为表长。

### 回答2：
单链表是一种链式存储结构，由节点组成，每个节点包含一个数据域和一个指针域。而带头结点的单链表是在链表的第一个节点之前设置一个额外的头结点，目的是方便链表的操作和统一代码逻辑。求带头结点的单链表的表长，即计算链表中节点的数量。

具体实现如下：

1. 定义一个函数 `getLength`，用来求带头结点的单链表的表长。

2. 在函数中，创建一个变量 `length` 并初始化为0，用于记录链表的长度。

3. 判断头结点的指针域是否为空，即链表是否为空。

4. 若为空，说明链表中没有节点，直接返回长度为0。

5. 若不为空，说明链表中至少有一个节点，进入循环。

6. 在循环中，每次将节点的指针域赋值给当前节点，再将当前节点的指针域赋值给下一个节点，即遍历到下一个节点。

7. 每次循环，计数器 `length` 加1，直到链表的最后一个节点的指针域为空。

8. 返回计数器 `length`，即为带头结点的单链表的表长。

这样，就实现了求带头结点的单链表的表长的函数。

例如，以下是一个带头结点的单链表的表长的示例代码：

typedef struct Node {
    int data;
    struct Node* next;
} Node;

int getLength(Node *head) {
    int length = 0;
    Node *current = head->next;  // 当前节点指向第一个节点

    while (current != NULL) {
        current = current->next;
        length++;
    }

    return length;
}

### 回答3：
题目要求实现一个函数，用于求解带头结点的单链表的表长。

解答如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def get_length(head):
    # 表长初始化为0
    length = 0 
    # 当前结点指向头结点的下一个结点
    cur = head.next 
    while cur:
        # 遍历链表，每经过一个结点，表长加1
        length += 1
        cur = cur.next
    return length

首先，我们需要定义一个Node类，用于表示链表的结点。每个结点包括两部分：数据项和指向下一个结点的指针。

接着，我们定义了一个get_length函数，用于求解带头结点的单链表的表长。我们将表长初始化为0，然后遍历链表，每经过一个结点，表长加1。遍历链表的过程是不断将当前结点指向下一个结点，直到当前结点为None，表示已经遍历到了链表的尾部。最后，函数返回表长。

使用该函数可以方便地求解带头结点的单链表的表长。