数据结构作业

Question 1

有 5 个元素 ，其进栈次序 ABCDE ，在各种可能的出栈次序中以元素 C、D 最先出栈(即 C 第一个且 D 第二个出栈)的次序有哪几个?

把各种可能写出来：

A,B,E,D,C
C,D,E,B,A

Question 2

在一个算法中需要建立多个栈(假设 3 个栈或以上)时可以选用以下 3 种方案之一， 试问这些方案各有什么优缺点?

(1) 分别用多个顺序存储空间建立多个独立的顺序栈。

(2) 多个栈共享一个顺序存储空间。

(3) 分别建立多个独立的链栈

1. 分别用多个顺序存储空间建立多个独立的顺序栈。

优点:

• 简单易实现：每个栈都有自己的存储空间，操作互不影响，容易理解和实现。
• 独立性：每个栈的操作不会影响到其他栈，错误或异常在一个栈中不会影响到其他栈。
• 性能：在空间充足的情况下，每个栈的操作（如压栈、弹栈）都能保持较高的性能。

缺点:

• 空间利用率低：每个栈分配固定的空间，可能会导致部分栈用不完空间而浪费，尤其是在栈大小变化较大时。
• 不灵活：一旦栈空间满了，要么就无法再添加元素，要么需要进行空间的重新分配，增加复杂度。

2. 多个栈共享一个顺序存储空间。

优点:

• 高空间利用率：多个栈共享同一个存储空间，可以动态分配空间给需要扩容的栈，减少了空间浪费。
• 灵活性：相对于固定空间的顺序栈，共享空间的栈在处理不同栈的大小变化时更加灵活。

缺点:

• 实现复杂：需要精心设计算法来管理共享的存储空间，避免栈之间的相互干扰。
• 栈溢出处理更复杂：当一个栈溢出时，需要考虑如何在不影响其他栈的情况下进行扩容。
• 性能开销：在某些情况下，为了管理共享空间，可能需要额外的性能开销，比如更复杂的空间分配算法。

3. 分别建立多个独立的链栈

优点:

• 动态空间分配：每个元素都通过指针连接，只要系统内存允许，就可以无限添加元素，不受初始分配空间大小的限制。
• 空间利用高：每个栈只占用它实际所需的内存空间，没有空间浪费。
• 灵活性高：适合处理栈大小频繁变化的场景。

缺点:

• 额外的空间开销：每个栈元素除了数据外，还需要额外的空间存储指向下一个元素的指针。
• 性能开销：与顺序栈相比，链栈的操作（如压栈、弹栈）可能需要更多的指针操作，导致性能稍微下降。
• 实现复杂度：相比于顺序栈，链栈在实现上更加复杂，尤其是在处理指针操作时需要更多的注意以避免内存泄露等问题。

选择哪种方案，需要根据实际应用的需求、空间和性能的考虑来决定。例如，如果预计每个栈的大小变化不大，且对空间利用率要求不高，可以选择方案1。如果对空间利用率有较高要求，可以考虑方案2或方案3，具体选择取决于是否更倾向于简化实现（偏好使用动态内存分配的灵活性和可扩展性）。如果更倾向于简化实现，可以选择方案3，因为虽然它在某些方面（如空间和性能开销）可能不如顺序栈高效，但它提供了更好的灵活性和动态内存管理，特别是在不确定每个栈将需要多大空间的情况下。

总的来说，选择最合适的栈实现方案需要权衡以下因素：

• 空间效率：共享空间的方案在多个栈空间需求差异大时最有效，而链栈则对单个栈的动态空间需求管理最优。
• 实现复杂性：独立顺序栈最简单易实现，共享空间顺序栈实现最复杂，链栈虽然管理灵活但需要处理额外的指针操作。
• 性能需求：顺序栈在空间连续且预分配足够时，性能最优。链栈在动态操作频繁时可能稍逊一筹，但优于空间管理复杂的共享空间顺序栈。
• 栈的大小和变化频率：如果栈的大小变化不频繁且相对固定，独立的顺序栈可能更合适。如果栈的大小经常变化，链栈可能更有优势。共享空间顺序栈适合栈的数量多但总体空间需求相对固定的场景。

综上所述，每种方案都有其适用场景，选择哪种取决于具体需求、预期的使用模式以及对空间和性能的权衡。在设计时，考虑未来可能的需求变化和扩展性也是非常重要的。

QUestion 3

简述以下算法的功能(假设 ElemType 为 int 类型)。

void fun(Elem Type a[],int n)
{
    int i; Elem Type e;
    SqStack * stl,*st2;
    InitStack(st1);
    InitStack(st2);
    for(i=0;i<n;i++)
        if(a[i]%2==1)
            Push(st1,a[i]);
        else 
            Push(st2,a[i]);
    i=0;
    while(!StackEmpty(st1))
    {
        Pop(st1,e);
        a[i++]=e;
    }
    while(!StackEmpty(st2))
    {
        Pop(st2,e;)
        a[i++]=e;
    }
    DestroyStack(st1);
    DestroyStack(st2);
        
}

这段代码的功能是对一个整型数组进行分类排序。数组 a[] 中的元素根据是奇数还是偶数被分成两组，先将所有奇数放到数组的前半部分，然后将所有偶数放到数组的后半部分。这个过程通过使用两个栈（st1 和 st2）来实现，其中 st1 用于存储奇数元素，st2 用于存储偶数元素。

具体步骤如下：

1. 初始化两个栈 st1 和 st2。
2. 遍历数组 a[]，将奇数元素推入栈 st1，将偶数元素推入栈 st2。
3. 在数组 a[] 中，从位置0开始，先将栈 st1 中的元素（即所有奇数元素）依次弹出并存储回数组，这样做的结果是所有的奇数元素将被按照从栈顶到栈底的顺序（即它们原本在数组中的相反顺序）放置在数组的前半部分。
4. 接着，将栈 st2 中的元素（即所有偶数元素）依次弹出并存储回数组，这样做的结果是所有的偶数元素将被按照从栈顶到栈底的顺序（即它们原本在数组中的相反顺序）放置在数组的后半部分。
5. 最后，销毁两个栈以释放资源。

注意，由于这个过程中先处理的是奇数，后处理的是偶数，因此最终数组中奇数都位于偶数之前。另外，由于栈的先进后出（FILO）特性，数组中每组数字（奇数或偶数）的顺序将与它们原本的顺序相反。

Question 4

简述以下算法的功能(顺序栈的元素类型力 ElemType)。

void fun(SqStack * &st,ElemType x)
{
    SqStack * tmps;
    ElemType e;
    InitStack(tmps);
    while(!StackEmpty(st))
    {
        Pop(st,e);
        if(e!=x) 
            Push(tmps,e);
    }
    while(!StackEmpty(tmps))
    {
        Pop(tmps,e);
        Push(st,e);
    }
    DestroyStack(tmps);
}

上面代码的功能是在一个顺序栈（SqStack 类型）中删除所有等于 x 的元素。它通过使用一个临时栈 tmps 来实现，过程可以分为以下几个步骤：

1. 初始化临时栈：通过 InitStack(tmps); 初始化一个空的临时栈 tmps。

2. 从原栈中删除元素：通过 while(!StackEmpty(st)) 循环检查原栈 st 是否为空。在循环内部，使用 Pop(st,e); 从原栈顶弹出元素 e。然后检查这个元素是否等于给定的值 x：

   • 如果 e != x，说明这个元素不应该被删除，因此将其通过 Push(tmps,e); 压入临时栈 tmps 中。
   • 如果 e == x，这个元素就被排除了，不会被放入临时栈中。

3. 将临时栈中的元素回填到原栈：完成上述步骤后，所有不等于 x 的元素都被存储在了临时栈 tmps 中。接下来，通过 while(!StackEmpty(tmps)) 循环将这些元素从临时栈中弹出，并压回原栈 st。这一步骤确保了原栈 st 中的元素是最初除了所有 x 元素之外的元素，但顺序可能与最初的顺序相反。

4. 销毁临时栈：最后，通过 DestroyStack(tmps); 销毁临时栈 tmps，释放其占用的资源。

综上所述，这个函数的作用是从栈中移除所有等于 x 的元素，但这个过程会导致栈中剩余元素的顺序与原始顺序相反。

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