数据结构实践

本篇将根据自考实践要求对「数据结构」一科进行简要的复习，代码实现使用 C++ 语言实现。

实践

已知 Q 是一个非空队列，S 是一个空栈。编写算法，仅用队列和栈的 ADT 函数和少量工作变量，将队列 Q 的所有元素逆置。

栈的基本 ADT 函数有：

置空栈。函数原型为: void MakeEmpty(SqStack s);
元素e入栈。函数原型为: void Push(SqStack s,ElemType e);
出栈，返回栈顶元素。函数原型为: ElemType pop(SqStack s);
判断栈是否为空。函数原型为: int isEmpty(SqStack s);

队列的基本ADT函数有：

元素e入队。函数原型为：void enQueue(Queue q,ElemType e);
出队，返回队头元素。函数原型为：ElemType deQueue(Queue q);（3）（3）判断队是否为空。函数原型为：int isEmpty(Queue q);

题目要求：

编程实现队列和栈的ADT函数
仅用队列和栈的ADT函数和少量工作变量，编写将队列Q的所有元素逆置的函数
测试该函数

// 栈的基本 ADT 函数有：

// 1. 置空栈。函数原型为: `void MakeEmpty(SqStack s);`
// 2. 元素e入栈。函数原型为: `void Push(SqStack s,ElemType e);`
// 3. 出栈，返回栈顶元素。函数原型为: `ElemType pop(SqStack s);`
// 4. 判断栈是否为空。函数原型为: `int isEmpty(SqStack s);`
#include <iostream>

using namespace std;

#define StackSize 10
typedef int ElemType;

// 栈结构
class SqStack {
private:
    ElemType data[StackSize];
    int top;
public:
    SqStack(): top(-1) {}

    // 1. 置空栈
    void makeEmpty() {
      this->top = -1;
    }

    // 2. 元素e入栈
    void push(ElemType e) {
      if (this->isFull()) {
        std::cout << "栈满" << std::endl;
        return;
      }

      this->data[++this->top] = e;
    }

    // 3. 出栈，返回栈顶元素
    ElemType pop() {
      if (this->isEmpty()) {
        std::cout << "栈空" << std::endl;
        return -1;
      }

      return this->data[this->top--];
    }

    // 4. 判断栈是否为空
    bool isEmpty() {
      return this->top == -1;
    }

    // 5. 栈满
    int isFull() {
      return this->top == StackSize;
    }
};

// 队列的基本ADT函数有：

// （1）元素e入队。函数原型为：void enQueue(Queue q,ElemType e);
// （2）出队，返回队头元素。函数原型为：ElemType deQueue(Queue q);（
// （3）判断队是否为空。函数原型为：int isEmpty(Queue q);
#define QueueSize 10

// 队列结构
class Queue {
private:
    ElemType data[QueueSize];
    int front, real;
public:
    Queue(): front(0), real(0) {}

    // 队列是否已满
    int isQueueFull() {
      return (this->real + 1) % QueueSize == this->front;
    }

    // 元素e入队
    void enQueue(ElemType e) {
      if (isQueueFull()) {
        std::cout << "队列满" << std::endl;
        return;
      }

      this->data[this->real] = e;
      // 循环意义下的 +1
      this->real = (this->real + 1) % QueueSize;
    }

    // 出队列
    ElemType deQueue() {
      if (this->isEmpty()) {
        std::cout << "队列空" << std::endl;
        return -1;
      }

      ElemType e = this->data[this->front];
      this->front = (this->front + 1) % QueueSize;

      return e;
    }

    // 判断队列是否为空
    int isEmpty() {
      return this->front == this->real;
    }
};

// 队列元素倒序, 这里注意要用 & 取引用才有副作用
void reverseQueue(Queue &q) {
  SqStack s;
  int val;

  while (!q.isEmpty()) {
    val = q.deQueue();
    s.push(val);
  }

  while (!s.isEmpty()) {
    val = s.pop();
    q.enQueue(val);
  }
}

// (1) 编程实现队列和栈的ADT函数
// (2) 仅用队列和栈的ADT函数和少量工作变量，编写将队列Q的所有元素逆置的函数。
// (3) 测试该函数
int main() {
  cout << "准备测试 stack 数据结构" << endl;
  SqStack s;

  cout << "[stack] 1. test SqStack.push" << endl;
  int testData1[] = {109, 108, 107};
  for (int i = 0; i < 3; i++) {
    s.push(testData1[i]);
  }

  cout << "[stack] 2. test SqStack.isEmpty: " << (s.isEmpty() ? "" : "非") << "空栈" << endl;
  cout << "[stack] 3. test SqStack.pop: " << s.pop() << endl;
  cout << "[stack] 4. test SqStack.makeEmpty" << endl;
  s.makeEmpty();

  cout << "[stack] 5. check stack now is empty: " << (s.isEmpty() ? "" : "非") << "空栈" << endl;
  cout << "============================================" << endl;

  cout << "准备测试 queue 数据结构" << endl;
  Queue q;

  cout << "[queue] 1. test SqStack.push" << endl;
  for (int i = 0; i < 3; i++) {
    q.enQueue(testData1[i]);
  }

  cout << "[queue] 2. test Queue.isEmpty: " << (q.isEmpty() ? "空队列" : "非空队列") << endl;
  while (!q.isEmpty()) {
    cout << "[queue] 3. test Queue.pop: " << q.deQueue() << endl;
  }

  cout << "[queue] 4. check queue now is empty: " << (q.isEmpty() ? "空队列" : "非空队列") << endl;
  cout << endl << endl;
  cout << "============================================" << endl;

  cout << "仅用队列和栈的ADT函数和少量工作变量，编写将队列Q的所有元素逆置的函数。" << endl;
  const int reverseTestData[] = {11,12,13,14,15};
  for (int i = 0; i < 5; i++) {

    q.enQueue(reverseTestData[i]);
  }
  reverseQueue(q);

  while(!q.isEmpty()) {
    cout << "reverseQueue deQueue: " << q.deQueue() << endl;
  }

  return 0;
}

排序

选择排序

基本思想: 每一趟在待排序的记录中选出关键字最小的记录，依次存放在已排好序的记录序列的最后，直到全部排序完为止。


#include <iostream>
using namespace std;

void SelectSort(int arr[], int n) {
  int k;
  for (int i = 0; i < n; i++) {
    k = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[k]) {
        k = j;
      }
    }

    if (k != i) {
      swap(arr[i], arr[k]);
      int temp = arr[i];
      arr[i] = arr[k];
      arr[k] = temp;
    }
  }
}

int main() {
  int arr[] = {4, 3, 2, 9, 8, 6, 7, 1, 5, 10};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << sizeof(arr[0]) << "\n";

  SelectSort(arr, n);

  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
}

插入排序

基本思想: 每次将一个待排序的记录按其关键字的大小插入到前面已经排序好的文件中的适当位置，直到全部记录插入完位置。

void InsertSort(int arr[], int n) {
  int i, j, tmp;
  // 对顺序表做直接插入排序
  for(i = 1; i < n; i++) {
    // 当前值比上一个值小，则交换位置
    if (arr[i] < arr[i - 1]) {

      tmp = arr[i];
      // 对有序区逐项向后 diff，寻找合适的插入位置
      for(j = i - 1; j >= 0 && tmp < arr[j]; j--) {
        arr[j + 1] = arr[j];
      }
      arr[j + 1] = tmp;
    }
  }
}

冒泡排序

冒泡排序的基本思想是：通过相邻元素之间的比较和交换，使娇小的元素逐渐从底部移向顶部，就像水底下气泡一样逐渐向上冒泡。

void BubbleSort(int *arr, int n) {
  int i, j, flag, temp;
  for (i = 0; i < n; i++) {
    flag = 0;

    // 从右向左对比
    for (j = n - 1; j >= i; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr[j], arr[j - 1]);
       // temp = arr[j];
       // arr[j] = arr[j - 1];
       // arr[j - 1] = temp;
        flag = 1;
      }
    }

    if (flag == 0) return;
  }
}