数据结构作业

Question 1

简述线性表的两种存储结构的 主要特点。

Question 2

简述对单链表设置头结点的主要作用。

Question 3

对于顺序表 L，指出以下算法的功能。

void fun(SqList * &L)
{
  int i, j = 0;
  for (i = 1; i < L -> length; i++)
  {
    if (L -> data[i] > L -> data[j])
    {
      j = i;
    }
  }
  for (i = j; i < L -> length - 1; i++)
  {
    L -> data[i] = L -> data[i + 1];
  }
  L -> length--;
}

这段代码定义了一个名为 fun 的函数，其参数是一个指向 SqList 类型的指针。SqList 是一个顺序表的结构，具有长度 (length) 和一个数据数组 (data)。函数的功能可以分为两个主要步骤：

1. 查找最大元素的位置： 第一个 for 循环遍历顺序表 L，比较每个元素与当前已找到的最大元素（初始时为第一个元素）。如果找到一个更大的元素，就更新 j 来记录这个更大元素的索引。

2. 删除最大元素： 第二个 for 循环从找到的最大元素的位置开始，将后面的每个元素向前移动一位，覆盖掉最大元素。这实际上是从顺序表中删除了最大元素。最后，顺序表的长度减一，以反映删除操作。

即：这个函数的功能是从顺序表 L 中删除最大的元素。如果存在多个最大元素，它只会删除第一个遇到的最大元素。

Question 4

对于顺序表L，指出以下算法的功能。

void fun(SqList * &L, ElemType x)
{
  int i, j = 0;
  for (i = 1; i < L -> length; i++)
  {
    if (L -> data[i] <= L -> data[j])
    {
      j = i;
    }
  }
  for (i = L -> length; i > j; i--)
  {
    L -> data[i] = L -> data[i - 1];
  }
  L -> data[j] = x;
  L -> length++;
}

这段 C 代码定义了一个名为 fun 的函数，该函数接收两个参数：一个是指向顺序表L的指针的引用（SqList * &L），另一个是 ElemType 类型的变量 x。SqList 是顺序表的类型，ElemType 是顺序表中元素的类型。这段代码的功能是将新元素 x 插入到顺序表 L 中的特定位置，并确保顺序表的顺序性不被破坏。下面是该算法的详细解释：

1. 首先，它通过一个循环找到顺序表中最小元素的位置 j。这是通过比较 L -> data[i] 和 L -> data[j] 完成的，其中 i 从1遍历到L -> length - 1（注意，顺序表的索引在这个上下文中似乎是从 0 开始）。如果发现更小的元素，就更新j的值。

2. 接下来，函数通过另一个循环将位置j之后的所有元素向后移动一位，为新元素x腾出空间。这个循环从 L -> length 开始，直到j位置，每次循环都将当前元素移动到它前一个位置的后面。

3. 最后，新元素 x 被插入到j位置，顺序表的长度 L -> length 增加 1。

总的来说，这个算法的功能是将新元素 x 插入顺序表 L 中最小元素的位置，从而保持顺序表中元素的顺序。如果顺序表中有多个相同的最小元素，x 将被插入到这些元素的最后一个位置之后。

Question 5

对于不带头结点的单链表 L1 , 其结点类型为 LinkNode , 指出以下算法的功能 。

void fun1(LinkNode * &L1, LinkNode * &L2)
{
  int n = 0, i;
  LinkNode * p = L1;
  while (p != NULL)
  {
    n++;
    p = p -> next;
  }
  p = L1;
  for (i = 1; i < n/2; i++)
  {
    p = p -> next;
  }
  L2 = p -> next;
  p -> next = NULL;
}

上面代码的功能是将不带头结点的单链表 L1 分割成两个链表。原链表 L1 在分割后保留前半部分的节点，而新链表 L2 包含原链表 L1 的后半部分节点。具体操作如下：

1. 通过一个循环计算链表 L1 的长度 n。

2. 再次从链表 L1 的开始遍历，直到达到中点之前的位置（即 n/2 ），这里利用了整数除法的性质，当 n 是奇数时，n/2 会自动取整，确保 L2 始终包含 L1 后半部分的节点。

3. 设置 L2 为 p->next，即 L1 中点之后的第一个节点，这样 L2 成为了第二个链表的头结点。

4. 将 p->next 设置为 NULL，断开 L1 和 L2，此时 p 位于 L1 的中点，将其 next 指针设置为 NULL 可以确保 L1 链表在中点断开，只包含前半部分的节点。

即：这个算法的功能是将一个单链表分成两个部分，前半部分仍然是原链表 L1，而后半部分成为新的链表 L2。

公众号：AI悦创【二维码】